Act 2: Lying About Processing

Define Turnaround Time, Waiting Time, and Response Time.

Metrics:

• Turnaround Time: Total time elapsed from process arrival to complete execution ($t_{\text{end}} - t_{\text{arrival}}$).

• Waiting Time: Total time a process spends waiting in the ready queue ($t_{\text{turnaround}} - t_{\text{burst}}$).

• Response Time: Time elapsed from process arrival until it is dispatched to run for the first time.

Three processes arrive at $t=0$ in the order $P_1, P_2, P_3$ with burst times of 10, 2, and 4 seconds respectively.

• Calculate average Turnaround, Waiting, and Response times under First-Come, First-Served (FCFS).

• Calculate the same metrics under Round Robin (RR) with a quantum of 3 seconds.

• FCFS Scheduling:

  • Execution order: $P_1 (0 \to 10)$, $P_2 (10 \to 12)$, $P_3 (12 \to 16)$.

  • Turnaround: $P_1 = 10$, $P_2 = 12$, $P_3 = 16$. $\text{Average} = \frac{10+12+16}{3} = \frac{38}{3} = 12.67\text{s}$.

  • Waiting: $P_1 = 0$, $P_2 = 10$, $P_3 = 12$. $\text{Average} = \frac{0+10+12}{3} = \frac{22}{3} = 7.33\text{s}$.

  • Response: $P_1 = 0$, $P_2 = 10$, $P_3 = 12$. $\text{Average} = \frac{0+10+12}{3} = 7.33\text{s}$.

• Round Robin (Quantum = 3s):

  • Execution trace: $P_1(0 \to 3)$, $P_2(3 \to 5 \text{ finishes})$, $P_3(5 \to 8)$, $P_1(8 \to 11)$, $P_3(11 \to 12 \text{ finishes})$, $P_1(12 \to 16 \text{ finishes})$.

  • Turnaround: $P_1 = 16$, $P_2 = 5$, $P_3 = 12$. $\text{Average} = \frac{16+5+12}{3} = \frac{33}{3} = 11.00\text{s}$.

  • Waiting: $P_1 = 16 - 10 = 6$, $P_2 = 5 - 2 = 3$, $P_3 = 12 - 4 = 8$. $\text{Average} = \frac{6+3+8}{3} = \frac{17}{3} = 5.67\text{s}$.

  • Response: $P_1 = 0$, $P_2 = 3$, $P_3 = 5$. $\text{Average} = \frac{0+3+5}{3} = \frac{8}{3} = 2.67\text{s}$.

Compare Interrupts, Traps, and Faults in terms of synchronicity and where the Program Counter (PC) points.

• Interrupt: Asynchronous hardware event (e.g., timer, device I/O). PC points to the next instruction to be executed after handling.

• Trap: Synchronous software-generated event (e.g., system call). PC points to the next instruction.

• Fault: Synchronous error condition (e.g., page fault). PC points to the faulting instruction itself, enabling instruction restart after resolution.

Detail the two-step execution model of an Interrupt Handler (Top-Half vs. Bottom-Half).

Top-Half vs. Bottom-Half:

• Top-Half (Immediate): Runs with interrupts disabled/masked. Performs time-critical work (e.g., clearing hardware device flags, reading buffer state), cannot block, and schedules deferred work.

• Bottom-Half (Deferred): Runs with interrupts unmasked. Handles non-critical data processing (e.g., memory allocation, waking waiting processes) and can be interleaved with new hardware interrupts.

What is the role of a Process Control Block (PCB) during a preemptive context switch?

The PCB stores the entire execution context of a suspended process (saved general registers, PC, stack pointer, page table root pointer). Upon context switch, the kernel writes current CPU states to the old process's PCB and restores CPU states from the newly dispatched process's PCB

Differentiate between an Atomic Operation, a Spinlock, a Semaphore, and a Mutex.

• Atomic Operation: Indivisible CPU hardware-level instruction (e.g., Compare-And-Swap) guaranteed to execute completely without partial reads/writes or context switches.

• Spinlock: A mutual exclusion mechanism using busy-waiting (looping on an atomic operation). Efficient for extremely short locks, but wastes CPU cycles if held long.

• Semaphore: A integer counter $v$, process queue $Q$, and protecting lock $s$. Decrementing below 0 puts calling processes to sleep rather than spinning.

• Mutex: A binary semaphore with strict ownership tracking. Only the thread that acquired the lock can release it, allowing detection of incorrect unlocking behavior.

Explain the deadlock condition shown below and state the fundamental rule to prevent it:

$$\text{Thread 1: acquires Lock A } \to \text{ requests Lock B}$$

$$\text{Thread 2: acquires Lock B } \to \text{ requests Lock A}$$

• Cause: Circular dependency where Thread 1 holds Lock A waiting for Lock B, while Thread 2 holds Lock B waiting for Lock A.

• Rule to Prevent: Enforce a strict global lock ordering across all threads (e.g., always acquire Lock A before Lock B)

Contrast Livelock with Starvation.

• :Livelock: Active threads continually change state in response to each other (e.g., repeatedly using try_lock() and retrying) without making forward progress.

• Starvation: A thread is ready to run or acquire a resource, but is indefinitely bypassed because higher-priority threads continuously take precedence.