Previous Year Questions (PYQs)

Compilers (such as GCC or Clang) are user-level application programs and utility software, completely distinct from the OS kernel. Memory management (Q), CPU scheduling (R), and interrupt handling (S) are core responsibilities executed inside the OS kernel.

(I) Setting the hardware timer must be privileged so a rogue process cannot monopolize the CPU by disabling preemption. (II) Reading the time of day is a non-privileged operation (reading time harms nothing). (III) Clearing or modifying memory page tables would destroy virtual memory isolation and must be privileged. (IV) Disabling interrupts (`CLI`) prevents the OS scheduler from preempting the process and must be strictly privileged.

Threads of the same process share the Text (code) segment, Data/BSS segments (global and static variables), Heap, and open file descriptors. However, each thread must independently execute its own function call sequence and instructions; therefore, each thread maintains its own ==pink:private Stack== and ==pink:private CPU Register values (including Program Counter and Stack Pointer)==.

When an event or I/O for a blocked (waiting) process completes, the kernel moves it to the ==yellow:READY state==. The process can only enter the RUNNING state when chosen by the CPU dispatcher from the ready queue. Direct ==pink:Blocked → Running transition violates OS scheduling invariants==.

Threads of the same process share the same virtual address space and memory mappings. Therefore, the kernel does ==pink:NOT need to change page tables or reload the page table base register (CR3)==, and the TLB cache does not need to be invalidated. Registers (A), Program Counter (B), and Thread Control Block (TCB) state (D) are private to each thread and must be updated.

After 3 consecutive forks: ==yellow:Total processes = 2^3 = 8==. ==pink:New processes = 8 - 1 = 7== (the parent process was already existing, not newly created).

1. Construct the Gantt Chart: • At t = 0 ms: Only P1 is in the ready queue. P1 executes non-preemptively from t = 0 to t = 4 ms. Completion Time ==yellow:CT(P1) = 4 ms==. • At t = 4 ms: Both P2 (arrived at t = 2, BT = 3) and P3 (arrived at t = 4, BT = 1) are present in the ready queue. Under SJF, ==green:P3 is selected because BT(P3) = 1 < BT(P2) = 3==. • P3 executes from t = 4 to t = 5 ms. Completion Time ==yellow:CT(P3) = 5 ms==. • At t = 5 ms: Only P2 remains. P2 executes from t = 5 to t = 8 ms. Completion Time ==yellow:CT(P2) = 8 ms==. 2. Calculate Turnaround Time (TAT = CT - AT): • P1: 4 - 0 = ==purple:4 ms== • P2: 8 - 2 = ==purple:6 ms== • P3: 5 - 4 = ==purple:1 ms== 3. Calculate Average Turnaround Time: Average TAT = (4 + 6 + 1) / 3 = 11 / 3 = ==yellow:3.67 ms==.

Gantt Chart Execution with q = 2: 1. t=0 to 2: P1 executes (remaining BT = 3). During this time, P2 (at t=1) and P3 (at t=2) arrive. Ready queue: [P2, P3, P1]. 2. t=2 to 4: P2 executes (remaining BT = 1). Ready queue: [P3, P1, P2]. 3. t=4 to 5: P3 executes (BT=1, finishes at t=5). Ready queue: [P1, P2]. 4. t=5 to 7: P1 executes (remaining BT = 1). Ready queue: [P2, P1]. 5. t=7 to 8: P2 executes (finishes at t=8). Ready queue: [P1]. 6. t=8 to 9: P1 executes (finishes at t=9). Completion Times: P1: CT = 9, TAT = 9 - 0 = 9, WT = 9 - 5 = 4 ms. P2: CT = 8, TAT = 8 - 1 = 7, WT = 7 - 3 = 4 ms. P3: CT = 5, TAT = 5 - 2 = 3, WT = 3 - 1 = 0 ms. Total WT = 4 + 4 + 0 = 8 ms. Average WT = 8 / 3 = 2.67 ms.

Formula: Final S = Initial S - (Number of P operations) + (Number of V operations) Final S = 7 - 20 + 15 = 2. Since the final value S = 2 is strictly greater than or equal to 0, no processes are blocked in the waiting queue. (If S were negative, say -2, then 2 processes would be blocked. Here S = 2, so 0 are blocked).

1. Total Allocated: R1 = 1+1+2+0 = 4; R2 = 0+1+1+1 = 3. 2. Available = Total - Allocated = (6-4, 5-3) = (2, 2). 3. Need Matrix (Max - Alloc): P1: (3-1, 2-0) = (2, 2) P2: (1-1, 3-1) = (0, 2) P3: (3-2, 1-1) = (1, 0) P4: (2-0, 2-1) = (2, 1) 4. Testing safe sequences: P3 Need is (1, 0) <= Avail (2, 2). P3 runs! Releases Alloc (2, 1) -> New Avail = (2+2, 2+1) = (4, 3). Next P1 Need (2, 2) <= (4, 3). P1 runs! Releases (1, 0) -> New Avail = (5, 3). Next P2 Need (0, 2) <= (5, 3). P2 runs! Releases (1, 1) -> New Avail = (6, 4). Next P4 runs! All finish. Safe sequence: <P3, P1, P2, P4>.

Assuming sequential TLB lookup and two page-table memory accesses on a miss: hit = 20 + 100 = 120 ns; miss = 20 + 2(100) + 100 = 320 ns; EMAT = 0.80(120) + 0.20(320) = 160 ns. A different answer requires a different timing convention, which must be stated and sourced.

Belady's Anomaly is the phenomenon where increasing the number of allocated page frames results in an INCREASE in the total number of page faults. Mattson et al. (1970) proved that 'Stack Algorithms' (algorithms where the set of pages in memory for n frames is always a strict subset of pages in memory for n + 1 frames: M(n) ⊆ M(n + 1)) can NEVER suffer from Belady's anomaly. Both LRU and Optimal are stack algorithms and therefore never suffer from Belady's anomaly. FIFO, Second Chance, and Random do not satisfy the stack property and are susceptible to Belady's anomaly.

1. Given: t_m = 200 ns S = 10 ms = 10,000,000 ns p = 1 / 10,000 = 0.0001 2. Formula: EMAT = (1 - p) * t_m + p * S 3. Calculation: EMAT = (1 - 0.0001) * 200 + 0.0001 * 10,000,000 EMAT = 0.9999 * 200 + 1,000 = 199.98 + 1000 ≈ 1199.98 ns ≈ 1200 ns.

1. Block Size = 2 KB = 2048 bytes. 2. Pointers per block = 2048 / 4 = 512 pointers = 2^9. 3. Direct capacity = 10 * 2 KB = 20 KB. 4. Single indirect = 512 * 2 KB = 1024 KB = 1 MB. 5. Double indirect = 512 * 512 * 2 KB = 2^9 * 2^9 * 2^11 B = 2^29 B = 512 MB. Total capacity = 20 KB + 1 MB + 512 MB = 513.02 MB ≈ 513 MB.

1. Head starts at 53 moving right (towards higher cylinders). 2. Requests in right direction: 65, 67, 98, 122, 124, 183. 3. C-SCAN travels all the way to disk end (cylinder 199). Movement right = 199 - 53 = 146 cylinders. 4. C-SCAN jumps from 199 to 0 (return distance = 199 cylinders). 5. From 0, it services remaining requests moving right: 14, 37 (stops at 37). Movement from 0 to 37 = 37 cylinders. Total Head Movement = (199 - 53) + (199 - 0) + (37 - 0) = 146 + 199 + 37 = 382 cylinders.