⏱️ OS 03: Context Switching & CPU Scheduling

Targeted for: Juspay Elimination Round & Hackathon Part B System Architecture Discussions
Key Focus: Hardware-level context switch execution, the "Single-Core Music + Coding" problem, scheduling metrics, and end-to-end numerical derivations (SRTF, Round Robin, Priority).

⚡ 1. Context Switching: What Happens at the OS Level?

A Context Switch is the procedure by which the CPU stops executing one process/thread and resumes executing another, preserving state so execution can resume seamlessly.

Step-by-Step OS Execution Sequence

1. Triggering Event:
   • Hardware Timer Interrupt (Preemptive scheduling: time slice quantum expired).
   • I/O System Call (Voluntary yield: e.g., read() waiting for disk/socket).
   • Hardware Fault / Exception (Page fault, division by zero).
2. Privilege Elevation (Mode Switch):
   • CPU switches from User Mode (Ring 3) to Kernel Mode (Ring 0).
   • Hardware automatically pushes the user stack pointer (RSP), program counter (RIP), and flags (RFLAGS) onto the process's Kernel Stack.
3. State Preservation (Save Old State):
   • OS saves all remaining General Purpose Registers (RAX, RBX, RCX, RDX, RSI, RDI, R8–R15), segment registers, and Floating Point / SIMD registers (AVX/SSE) into the process's PCB / task_struct.
4. Virtual Memory Switch (Only for Inter-Process Switches):
   • Kernel loads the base address of Process B's page table into the CR3 Control Register.
   • Hardware Impact: Invalidates the TLB (Translation Lookaside Buffer) (unless tagged with Process-Context Identifiers - PCID).
5. State Restoration (Load New State):
   • Kernel loads Process B's saved register state from PCB_B.
   • Restores stack pointer to Process B's stack.
6. Return to User Mode:
   • Kernel executes the iret (interrupt return) / sysret instruction.
   • CPU switches back to Ring 3 and jumps to Process B's saved RIP.

💸 2. Direct vs Indirect Overhead of Context Switching

[!TIP] Thread Switch vs Process Switch: A thread context switch within the same process skips Step 4 (no CR3 reload, no TLB flush) and avoids complete cache invalidation because both threads access the same address space.

🎵 3. Juspay Classic: "Playing a Song while Coding on a Single-Core PC"

The Question Asked in Juspay Part B:

"How does a single-core CPU allow you to listen to uninterrupted music in Spotify while compiling code in VS Code simultaneously?"

The 4-Part Architectural Explanation:

1. Preemptive Time-Slicing (The Illusion of Concurrency):
   • A single CPU core can only execute one instruction stream at any instant.
   • The OS Timer Interrupt generates hardware ticks at a frequency of 100–1000 Hz (every 1 to 10 ms).
   • The OS Short-Term Scheduler rapidly switches execution between the music player process, the text editor process, and background OS daemons.
2. The Audio Buffer & Hardware DMA (Direct Memory Access):
   • Music playback does not require continuous CPU intervention.
   • When the Spotify process gets its 5ms CPU slice, it decodes MP3/AAC audio frames and fills a Circular Audio Ring Buffer in RAM (holding 100–500 ms of future audio).
   • The Audio Sound Card pulls samples directly from this buffer via DMA without consuming CPU cycles. As long as Spotify gets scheduled before the buffer drains, the audio stream never glitches or stutters.
3. Priority Scheduling (Interactive vs CPU-Bound):
   • Real-time/interactive audio threads receive higher dynamic priority than CPU-intensive compiler jobs.
   • When the audio buffer falls below a threshold, an interrupt wakes the audio thread, immediately preempting the code editor.
4. Human Perception Threshold:
   • Human visual and auditory persistence perceives anything below 50–100 milliseconds as perfectly continuous and simultaneous. Context switching at 5–10ms intervals is completely undetectable to human senses.

📊 4. CPU Scheduling Metrics & Terminologies

• Arrival Time ($AT$): Time when the process enters the Ready Queue.
• Burst Time ($BT$): Total CPU execution time required by the process.
• Completion Time ($CT$): Instant when the process finishes all execution.
• Turnaround Time ($TAT$): Total elapsed time from arrival to completion. $$\text{TAT} = CT - AT$$
• Waiting Time ($WT$): Total time the process spent sitting idle in the Ready Queue. $$\text{WT} = \text{TAT} - BT$$
• Response Time ($RT$): Time from arrival until the process is allocated the CPU for the very first time. $$\text{RT} = \text{Time of First CPU Execution} - AT$$

🧮 5. Scheduling Algorithms & Worked Numerical Calculations

Consider the following set of 4 processes:

Algorithm 1: First-Come, First-Served (FCFS) & The Convoy Effect

Policy: Non-preemptive. Allocates CPU strictly in order of arrival.

Gantt Chart:

Calculation Table:

• Average Turnaround Time: $\frac{8 + 11 + 19 + 23}{4} = \frac{61}{4} = \mathbf{15.25}$
• Average Waiting Time: $\frac{0 + 7 + 10 + 18}{4} = \frac{35}{4} = \mathbf{8.75}$
• The Convoy Effect: Short processes ($P_2$, $BT=4$) get trapped behind long CPU-bound processes ($P_1$), causing severe degradation in average waiting time and resource utilization.

Algorithm 2: Shortest Remaining Time First (SRTF - Preemptive SJF)

Policy: Whenever a new process arrives or current process finishes, select the process with the minimum remaining burst time.

Execution Timeline Traced:

• $t=0$: Only $P_1$ is present (Remaining: $P_1=8$). $P_1$ runs.
• $t=1$: $P_2$ arrives ($BT=4$). Remaining $P_1=7, P_2=4$. $P_2$ has smaller remaining time $\rightarrow$ Preempt $P_1$! $P_2$ runs.
• $t=2$: $P_3$ arrives ($BT=9$). Remaining $P_2=3, P_1=7, P_3=9$. $P_2$ continues.
• $t=3$: $P_4$ arrives ($BT=5$). Remaining $P_2=2, P_4=5, P_1=7, P_3=9$. $P_2$ continues.
• $t=5$: $P_2$ completes ($CT=5$). Available: $P_4(5), P_1(7), P_3(9)$. Min is $P_4$. $P_4$ runs.
• $t=10$: $P_4$ completes ($CT=10$). Available: $P_1(7), P_3(9)$. Min is $P_1$. $P_1$ runs.
• $t=17$: $P_1$ completes ($CT=17$). Only $P_3(9)$ remains. $P_3$ runs.
• $t=26$: $P_3$ completes ($CT=26$).

Gantt Chart:

Calculation Table:

• Average Turnaround Time: $\frac{17 + 4 + 24 + 7}{4} = \frac{52}{4} = \mathbf{13.00}$
• Average Waiting Time: $\frac{9 + 0 + 15 + 2}{4} = \frac{26}{4} = \mathbf{6.50}$
• Takeaway: SRTF gives the provably optimal minimal average waiting time, but is impossible to implement perfectly in general-purpose OS because future burst time cannot be known in advance (estimated via exponential smoothing $\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$).

Algorithm 3: Round Robin (RR, Time Quantum $q = 3$)

Policy: Preemptive. Each process gets at most $q=3$ units before being moved to the tail of the Ready Queue.

Ready Queue Trace:

• $t=0$: Queue: $[P_1]$ $\rightarrow$ $P_1$ runs for 3 (remaining: 5).
• At $t=1, 2, 3$: $P_2, P_3, P_4$ arrive.
• $t=3$: Queue: $[P_2, P_3, P_4, P_1]$ $\rightarrow$ $P_2$ runs for 3 (remaining: 1).
• $t=6$: Queue: $[P_3, P_4, P_1, P_2]$ $\rightarrow$ $P_3$ runs for 3 (remaining: 6).
• $t=9$: Queue: $[P_4, P_1, P_2, P_3]$ $\rightarrow$ $P_4$ runs for 3 (remaining: 2).
• $t=12$: Queue: $[P_1, P_2, P_3, P_4]$ $\rightarrow$ $P_1$ runs for 3 (remaining: 2).
• $t=15$: Queue: $[P_2, P_3, P_4, P_1]$ $\rightarrow$ $P_2$ runs for 1 ($P_2$ finishes at $t=16$).
• $t=16$: Queue: $[P_3, P_4, P_1]$ $\rightarrow$ $P_3$ runs for 3 (remaining: 3).
• $t=19$: Queue: $[P_4, P_1, P_3]$ $\rightarrow$ $P_4$ runs for 2 ($P_4$ finishes at $t=21$).
• $t=21$: Queue: $[P_1, P_3]$ $\rightarrow$ $P_1$ runs for 2 ($P_1$ finishes at $t=23$).
• $t=23$: Queue: $[P_3]$ $\rightarrow$ $P_3$ runs for 3 ($P_3$ finishes at $t=26$).

Gantt Chart:

Calculation Table:

• Average Turnaround Time: $\frac{23 + 15 + 24 + 18}{4} = \frac{80}{4} = \mathbf{20.00}$
• Average Waiting Time: $\frac{15 + 11 + 15 + 13}{4} = \frac{54}{4} = \mathbf{13.50}$

Trade-Off of Time Quantum $q$:

• If $q \to \infty$: Round Robin degenerates into FCFS.
• If $q \to 0$: Processor sharing occurs, but system collapses under 100% Context Switch Overhead.
• Standard Rule of Thumb: $q$ should be chosen such that 80% of CPU bursts are shorter than $q$ (typically 10–50 ms).

🌲 6. Modern OS Scheduling: Linux CFS (Completely Fair Scheduler)

Modern Linux replaces queue-based schedulers with CFS:

• Data Structure: A Red-Black Tree ordered by vruntime (virtual runtime).
• Core Principle: The task that has had the least CPU execution time (smallest vruntime, leftmost node in the RB-Tree) is chosen next ($O(1)$ lookup, $O(\log N)$ insert).
• Nice Values (-20 to +19): Modulates how fast vruntime grows for a process. Higher priority processes accumulate vruntime slowly, earning more physical CPU time.

💬 7. Verbatim Interview Scripts (Say This Out Loud)

Q: "What is the Convoy Effect and which scheduling algorithm suffers from it?"

Verbatim Answer:
"The Convoy Effect is a performance pathology occurring in non-preemptive FCFS (First-Come, First-Served) scheduling. It happens when a long, CPU-bound process acquires the CPU, forcing all subsequent short, I/O-bound processes to wait in the Ready Queue. Even though the short jobs require negligible CPU time to issue their next disk or network request, they are completely blocked, leading to poor CPU and device utilization and inflated average waiting times."

Q: "How does the OS solve starvation in Priority Scheduling?"

Verbatim Answer:
"Starvation (or indefinite blocking) occurs when a low-priority process sits in the ready queue indefinitely because higher-priority processes continuously arrive.

The OS resolves this using Aging. Aging is a technique that gradually increases the priority of processes waiting in the ready queue over time. For instance, the scheduler may increment a process's priority by 1 every minute it spends waiting. Eventually, even the lowest-priority task reaches the highest priority in the system and is guaranteed CPU execution."