Spring '25 - F25 - CSC 345 - Midterm

General concepts

1. System calls

2. Application Programming Interface (API)

3. User mode

4. Kernel mode

5. Monolithic

6. UNIX

7. Mach

8. Microkernel

9. Message passing

10. Shared memory

(1) New

(2) Ready

(3) Running

(4) Waiting / Blocked

(5) Terminated / Exit

(6) Admitted

(7) Dispatch / Scheduler dispatch

• State 1 → State 2: Admitted
  → happens when the process is admitted to the ready queue.

• State 2 → State 3: Dispatch
  → happens when the scheduler selects the process to run.

So memorize:

1 New → 2 Ready → 3 Running → 4 Waiting → 2 Ready → 5 Terminated

	Child alive?	Parent alive?	Parent called wait()?
Zombies	N	Y	N
Orphans	Y	N	DNM

Easy way to remember:

• Zombie: child died, parent alive, parent has NOT called wait().

• Orphan: child alive, parent died, whether the parent called wait() doesn't matter because the parent is already gone.

• 1) Ordinary

• (2) Unidirectional

• (3) Anonymous

• (4) Parent-child relationship

• (5) Named

• Ordinary (or Anonymous)

• Unidirectional (or Half-duplex)

• Anonymous

• Parent-child (or Parent - child)

• Named

• shm_open

• ftruncate

• SIZE

• mmap

• sprintf

fd = shm_open(name, O_CREAT | O_RDWR, 0666);

ftruncate(fd, SIZE);

ptr = (char *) mmap(0, SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);

sprintf(ptr, "%s", message);

• pthread_exit

• pthread_t

• pthread_create

• my_fun

• pthread_join

Turnaround Time = Completion Time − Arrival Time

FCFS

Gantt: P1(0-2) P2(2-7) P3(7-8) P4(8-12) P5(12-15)

Process	TAT
P1	2
P2	7
P3	8
P4	11
P5	14

---

SJF (non-preemptive)

Gantt: P3(0-1) P1(1-3) P5(3-6) P4(6-10) P2(10-15)

Process	TAT
P1	3
P2	15
P3	1
P4	9
P5	5

---

Priority (non-preemptive, smaller number = higher priority)

Gantt: P2(0-5) P5(5-8) P4(8-12) P3(12-13) P1(13-15)

Process	TAT
P1	15
P2	5
P3	13
P4	11
P5	7

---

Round Robin (q = 3)

Gantt: P1(0-2) P2(2-5) P3(5-6) P4(6-9) P5(9-12) P2(12-14) P4(14-15)

Process	TAT
P1	2
P2	14
P3	6
P4	14
P5	11

Final Answer Table

Process	FCFS	SJF	Priority	RR (q=3)
P1	2	3	15	2
P2	7	15	5	14
P3	8	1	13	6
P4	11	9	11	14
P5	14	5	7	11

Formula: Turnaround Time (TAT) = Completion Time (CT) - Arrival Time (AT)

Process	FCFS	SJF	NPP	RR (q=3)
P1	0	1	13	0
P2	2	10	0	9
P3	7	0	12	5
P4	7	5	7	10
P5	10	2	4	8

Waiting Time = Turnaround Time − Burst Time.

(III-3) [5 points] Which of the algorithms results in the worst average waiting time?

(III- 4) [5 points] Which algorithm yields the best average turnaround time

1. Average Waiting Time

Average Waiting Time = (Sum of Waiting Times) / 5

FCFS: (0 + 2 + 7 + 7 + 11) / 5 = 27 / 5 = 5.4 ms SJF: (1 + 10 + 0 + 5 + 2) / 5 = 18 / 5 = 3.6 ms NPP: (13 + 0 + 12 + 7 + 4) / 5 = 36 / 5 = 7.2 ms RR: (0 + 9 + 5 + 10 + 8) / 5 = 32 / 5 = 6.4 ms

2. Average Turnaround Time

Average Turnaround Time = (Sum of Turnaround Times) / 5

FCFS: (2 + 7 + 8 + 11 + 14) / 5 = 42 / 5 = 8.4 ms SJF: (3 + 15 + 1 + 9 + 5) / 5 = 33 / 5 = 6.6 ms NPP: (15 + 5 + 13 + 11 + 7) / 5 = 51 / 5 = 10.2 ms RR: (2 + 14 + 6 + 14 + 11) / 5 = 47 / 5 = 9.4 ms

Final Answers

(III-3) [5 points] Answer: NPP (Non-Preemptive Priority) (Average waiting time = 7.2 ms, which is the highest/worst among all four).

(III-4) [5 points] Answer: SJF (Shortest Job First) (Average turnaround time = 6.6 ms, which is the lowest/best among all four).

When RMS fail: RMS can fail when CPU utilization exceeds its bound, which approaches 69%, so deadlines are not guaranteed.

Why EDF can help: EDF is theoretically optimal and can schedule processes with up to 100% CPU 

utilization, allowing deadlines to be met when RMS cannot.

When RMS fails: RMS can fail when total CPU utilization exceeds the RMS utilization bound N(21/N−1)N(2^{1/N}-1), which approaches 69.3% as NN increases. Thus, RMS may miss deadlines even when the total utilization is below 100%.

Why EDF can help: EDF can schedule a feasible task set as long as total CPU utilization is ≤ 100%. Therefore, EDF can successfully schedule some task sets with utilization above the RMS bound that RMS cannot.

more:

When RMS fail: RMS can fail when CPU utilization exceeds the RMS utilization bound, N(21/N−1)N(2^{1/N}-1). A task set may therefore miss deadlines even though the total CPU utilization is below 100%.

Why EDF can help: EDF has a higher schedulability bound and can schedule any feasible periodic task set when total CPU utilization is ≤100%\le 100\%, so it can meet deadlines for task sets that RMS cannot.

Mutual Exclusion: Only one process can be in the critical section at a time.

Progress: If no process is in the critical section, a process that wants to enter cannot be postponed indefinitely.

Bounded Waiting: There is a limit on how many times other processes can enter before a waiting process gets its turn.

• Mutual Exclusion: Only one process/thread can be inside the critical section at a time.

• Progress: If no process is in the critical section, a process that wants to enter should not be postponed indefinitely.

• Bounded Waiting: A process waiting to enter the critical section must have a limit on how many times other processes can enter before it gets its turn. Prevents starvation.

Atomic operation: An operation that is non-interruptible and completes as one indivisible operation.
Example: Test-and-Set, a hardware-supported atomic instruction that returns the original value and sets the value to TRUE.

Definition: An atomic operation is an operation that executes completely or not at all, without being interrupted or observed halfway through, so other processes/threads cannot interfere with it.

Example hardware-supported instruction:

Test-and-Set instruction:

• executed atomically (by hardware instruction support)

• returns the original value of passed parameter

• set the new value of passes parameter to “TRUE”

Compare_swap instruction:

• Executed atomically (by hardware instruction support)

• Returns the original value of passed parameter “value”

• Set the variable “value” the value of the passed parameter “new_value” but only if “value” == “expected” that is, the swap takes place only under this condition

atomic = non-interruptable

Explanation: Each philosopher needs two forks to eat, but each fork is shared with a neighboring philosopher. If all philosophers pick up one fork at the same time and wait for the other, a deadlock can occur.

A solution: Allow at most 4 philosophers to try to pick up forks at once, preventing all 5 from holding one fork and waiting forever, preventing deadlock

Blank = list

typedef struct {

int value;

struct process *list;

} semaphore;

• <

• block()

• <=

• wakeup(P)

wait(semaphore *S) {

S->value--;

if (S->value < 0) {

add this process to S->list;

block();

}

}

signal(semaphore *S) {

S->value++;

if (S->value <= 0) {

remove a process P from S->list;

wakeup(P);

}

}

Condition	Deadlock?	Example Graph
No cycle in the graph	No deadlock	P1 → R1 → P1 would actually be a cycle, so use: P1 → R1
Cycle + each resource has only one instance	Yes, deadlock	P1 → R1 → P2 → R2 → P1
Cycle + at least one resource has multiple instances	May or may not be a deadlock	P1 → R1 → P2 → R2 → P1, with R1 having 2 instances

What to memorize

1. No cycle → No deadlock

2. Cycle + single instance per resource → Deadlock

3. Cycle + multiple instances → Cannot determine from cycle alone; may or may not be deadlock

For the example graphs, remember the notation:

• P → R = process requests resource

• R → P = resource is allocated to process

So the classic deadlock cycle is:

P1 → R1 → P2 → R2 → P1

Given Available = (0, 3, 2).

1. Is the system in a safe state?
   Yes
   Safe sequence: P3 → P1 → P2 → P4 → P0

2. Can a request from P4 (0, 0, 1) be granted?
   No
   After granting, the system would be unsafe.

3. Can a request from P1 (0, 3, 0) be granted?
   No
   P1's remaining Need = (1, 2, 3), so requesting 3 units of B exceeds its Need of 2.

4. Can a request from P3 (0, 1, 2) be granted?
   Yes
   The request is within P3's Need and Available, and the resulting state remains safe.

Final answers:
(1) Yes
(2) No
(3) No
(4) Yes