Linux uses CFS, maintaining a Red-Black tree ordered by virtual runtime (vruntime). On Android (built on Linux), when a user touches the screen, the Android UI thread priority is dynamically boosted using Linux cgroups and `nice` values, ensuring buttery 120Hz touch response over background sync tasks.
Visual representation of control loops, memory layout, and execution flow for CPU Scheduling Algorithms & Dispatching.
Processes entering from New state or unblocking from I/O wait are placed into the Ready Queue.
The scheduler is invoked on 4 events: 1) Process switches from Running to Waiting, 2) Running to Ready (timer interrupt), 3) Waiting to Ready (I/O complete), 4) Process terminates. (Events 2 and 3 are preemptive).
The Dispatcher performs context switching, switches from User to Kernel Mode, and jumps to the proper location in the user program to restart execution.
Key metrics evaluated: Turnaround Time = Completion Time - Arrival Time; Waiting Time = Turnaround Time - Burst Time; Response Time = First CPU Run Time - Arrival Time.
| Feature / Dimension | Preemptive Scheduling (e.g., Round Robin, SRTF, MLFQ) | Non-Preemptive Scheduling (e.g., FCFS, Non-Preemptive SJF) |
|---|---|---|
| CPU Preemption | CPU can be forcibly seized from running process on timer interrupts or higher-priority arrival. | Once CPU is allocated, process holds it until it voluntary terminates or blocks on I/O. |
| System Responsiveness | High: Interactive user tasks get immediate time slices. | Low: A long running process can monopolize CPU (Convoy Effect). |
| Context Switch Overhead | Higher due to frequent timer-based context switches. | Minimal overhead: switches only on process completion or I/O block. |
| Data Race Risks | High: Requires robust kernel/user synchronization locks to protect shared state during preemption. | Low: Process completes its critical execution without interruption. |
Detailed answers, interviewer pro tips, key takeaway summaries, and code examples formulated for technical rounds.
✅ Correction: Turnaround Time is the total elapsed time from process arrival to final completion ($T_{turnaround} = T_{completion} - T_{arrival}$). Waiting Time is only the time spent sitting in the Ready Queue ($T_{wait} = T_{turnaround} - T_{burst}$).
✅ Correction: Standard Priority Scheduling suffers from severe starvation (indefinite blocking) if high-priority tasks continuously arrive. It requires Aging (gradually increasing the priority of waiting jobs) to guarantee progress.
The scheduler allocates CPU time among ready processes using preemptive or non-preemptive algorithms.