Operating Systems Practice Exam — Free

LRU evicts the page whose most recent use is furthest in the past. Track the frames with the least recently used page on the left; a hit moves that page to the most-recent end.

That is 9 faults: the three compulsory loads plus six replacements. Only the second reference to page 1 is a hit; every later reference arrives just after its page was evicted, which is the worst pattern for LRU.

Option C (8) is the tempting answer because it is the FIFO count for the same string: FIFO keeps page 3 (loaded second) long enough to score a hit on the sixth reference, so FIFO beats LRU here, a reminder that LRU is not always better. Option B (6) is the optimal (Belady) count, the lower bound that no online policy can beat on this string. Option A (5) is merely the number of distinct pages, which would be the fault count only if the process had enough frames to hold all of them.

9 page faults (option D).

Shortest remaining time first always runs the ready process with the least remaining CPU time, re-evaluating whenever a new process arrives.

• $t = 0$: only P1 is present; it runs (7 remaining).
• $t = 1$: P2 arrives with 4, less than P1's remaining 6, so P2 preempts P1.
• $t = 2$: P3 arrives with 1, less than P2's remaining 3, so P3 runs and finishes at $t = 3$.
• $t = 3$: P4 arrives with 2. Ready: P1 (6), P2 (3), P4 (2). P4 runs and finishes at $t = 5$.
• $t = 5$: P2 (3 remaining) runs and finishes at $t = 8$.
• $t = 8$: P1 (6 remaining) runs and finishes at $t = 14$.

The CPU is never idle, and the last completion at 14 ms equals the sum of all bursts ($7+4+1+2 = 14$), which checks the timeline.

Waiting time is turnaround minus burst, where turnaround is completion minus arrival:

• P1: $14-0-7 = 7$ ms
• P2: $8-1-4 = 3$ ms
• P3: $3-2-1 = 0$ ms
• P4: $5-3-2 = 0$ ms

Average waiting time $= (7+3+0+0)/4 = 2.5$ ms. For comparison, first-come first-served would run P1, P2, P3, P4 back to back with waiting times 0, 6, 9 and 9 ms, an average of 6 ms, which illustrates why SRTF minimizes average waiting time when burst lengths are known.

Completion times: P1 = 14 ms, P2 = 8 ms, P3 = 3 ms, P4 = 5 ms; average waiting time = 2.5 ms.

(a) Available = total instances minus the column sums of Allocation: (6, 5, 6) − (4, 4, 4) = (2, 1, 2). Need = Maximum − Allocation:

(b) Safety algorithm: start with Work = (2, 1, 2), repeatedly pick an unfinished process whose Need fits within Work, let it finish, and add its Allocation back. P0 needs 2 of B but only 1 is free, so skip it. P1 fits: Work = (2, 1, 2) + (2, 1, 0) = (4, 2, 2). P2 fits: Work = (5, 4, 3). P3 fits: Work = (5, 5, 5). P0 now fits: Work = (6, 5, 6). All four finish, so the state is safe; one safe sequence is P1, P2, P3, P0 (P1, P0, P2, P3 also works).

(c) P2's request (1, 0, 1) is within its Need (1, 1, 2) and within Available (2, 1, 2), so pretend to grant it: Available = (1, 1, 1), P2's Allocation = (2, 2, 2), Need = (0, 1, 1). Safety: P2 fits, Work = (3, 3, 3); P1 fits, Work = (5, 4, 3); P0 fits, Work = (6, 4, 4); P3 fits, Work = (6, 5, 6). The new state is safe, so the request is granted immediately.

(d) P0's request (1, 0, 1) is also within its Need (2, 2, 1) and within Available. Pretend to grant it: Available = (1, 1, 1), P0's Allocation = (2, 0, 2), Need = (1, 2, 0). Safety: P0 needs 2 of B, P1 needs 2 of A, and P2 and P3 each need 2 of C, but only one instance of each type is free. No process can finish, so the state would be unsafe: the request is denied and P0 is blocked until resources are released. The system is not deadlocked now; the banker refuses because it could no longer guarantee every maximum claim.

(a) Available = (2, 1, 2); Need rows (2, 2, 1), (2, 0, 1), (1, 1, 2), (1, 1, 2). (b) Safe, e.g. P1, P2, P3, P0. (c) Grant: the resulting state is safe. (d) Deny: the resulting state is unsafe.