CPU Scheduling, Process Synchronization, and Concurrency Control

In modern multitasking operating systems, multiple processes demand CPU execution and shared system resources simultaneously. Effective CPU scheduling ensures minimal latency, maximum throughput, and fair execution across workloads, while robust process synchronization prevents data corruption when concurrent entities access shared state.

1. The Convoy Effect and Gantt Charts

When jobs line up in a First-Come, First-Served (FCFS) queue, process burst time disparity leads to severe performance degradation.

The Problem: Convoy Effect

If a long process (e.g., burst time = 10 minutes) arrives just before a short process (e.g., burst time = 1 minute), the short process is forced to wait behind the long job for 10 minutes. The CPU remains occupied by a single, resource-heavy task while smaller, interactive tasks accumulate waiting latency.

Core Mental Model: Gantt Charts

A Gantt chart is a horizontal timeline representation used to evaluate CPU scheduling efficiency. It maps the exact execution intervals, waiting times, and turnaround times of processes across system time units.

• Burst Time ($BT$): The actual time duration required by a process for CPU execution.
• Arrival Time ($AT$): The timestamp at which a process enters the Ready Queue.
• Waiting Time ($WT$): The total time a process spends waiting in the Ready Queue before completion.

2. Shortest Job First (SJF) vs. Shortest Remaining Time First (SRTF)

Shortest Job First (SJF) — Non-Preemptive

• Mechanism: The CPU is allocated to the process with the smallest burst time. Once assigned, the CPU cannot be taken away until execution completes.
• Limitation (Starvation): If small jobs arrive continuously, larger jobs never receive CPU time.
• Practical Constraint: Requires prior knowledge of CPU burst times, which cannot always be predicted accurately in general-purpose computing.

Shortest Remaining Time First (SRTF) — Preemptive SJF

• Mechanism: If a new process arrives with a remaining CPU burst time shorter than the currently executing process's remaining time, the running process is preempted.
• Context Switching Overhead: Preemption forces the operating system to save the state (registers, program counter, address space) of the running process and load the new process's state. High preemption rates lead to significant context-switching latency.

3. Round Robin (RR) Scheduling & Time Quantum Dynamics

Round Robin provides time-sharing across all processes by allocating a strict, fixed slice of execution time known as the Time Quantum ($q$).

Impact of Time Quantum ($q$) Size

• Extremely Large Quantum ($q \to \infty$): Round Robin degrades into First-Come, First-Served (FCFS). The process executes until completion or I/O blockage without preemption.
• Extremely Small Quantum ($q \to 0$): The CPU spends more time executing operating system context switches than running actual user instructions, causing throughput collapse.

Example Walkthrough ($q = 2\text{ units}$)

Given three processes arriving at $t=0$:

• $P_1$ ($BT = 4$), $P_2$ ($BT = 3$), $P_3$ ($BT = 1$)

1. $P_1$ executes from $0 \to 2$ (Remaining: 2).
2. $P_2$ executes from $2 \to 4$ (Remaining: 1).
3. $P_3$ executes from $4 \to 5$ (Completed).
4. $P_1$ executes from $5 \to 7$ (Completed).
5. $P_2$ executes from $7 \to 8$ (Completed).

4. Priority Scheduling and Starvation Mitigation

Each process is assigned an explicit integer priority level (e.g., Rank 1 = Highest Priority; Rank 100 = Lowest Priority).

The Starvation Problem

Low-priority processes can remain in the Ready Queue indefinitely if higher-priority processes arrive continuously.

Mitigation via Aging

Aging gradually increments the priority of waiting processes at regular time intervals. Over time, an aged low-priority task reaches the top priority tier and is guaranteed CPU access.

5. Advanced Queue Topologies: MLQ and MLFQ

Modern systems segregate workloads based on response requirements and resource footprints.

Multilevel Queue (MLQ)

• The Ready Queue is permanently partitioned into separate sub-queues (e.g., System, Interactive, Batch).
• Each sub-queue maintains its own dedicated scheduling algorithm.
• Processes remain fixed in their assigned queues for their entire lifecycle.

Multilevel Feedback Queue (MLFQ)

• Processes are dynamically moved between queues based on their runtime execution patterns.
• I/O-bound interactive tasks stay in high-priority short-quantum queues; CPU-bound jobs drop to lower-priority batch queues.
• Forms the architectural foundation for production kernels (such as the Linux Completely Fair Scheduler / priority mechanisms).

6. CPU Scheduling Algorithms Comparison

7. Process Synchronization & The Critical Section Problem

When multiple concurrent execution threads or processes access shared, mutable memory simultaneously, non-deterministic execution order creates data inconsistency (Race Condition).

Definitions

• Critical Section (CS): The section of code that reads, writes, or modifies shared resources (e.g., global variables, shared memory blocks , shared files).
• Race Condition: A software defect where the output of execution depends unpredictably on the exact sequence or timing of concurrent threads.

8. The Three Formal Requirements for Critical Section Solutions

To guarantee synchronized concurrency, any synchronization mechanism must satisfy three foundational criteria:

1. Mutual Exclusion: If process $P_i$ is executing in its critical section, no other process may execute in its critical section simultaneously.
2. Progress: If no process is executing in its critical section and some processes wish to enter, only those processes not executing in their remainder sections can participate in deciding who enters next. This selection cannot be postponed indefinitely.
3. Bounded Waiting: There must be an upper bound on the number of times other processes are allowed to enter their critical sections after a process has requested entry and before that request is granted, preventing process starvation.

9. Classical Software Solution: Peterson's Algorithm

Peterson’s Algorithm is a classical, dual-process software synchronization algorithm satisfying all three requirements for processes $P_i$ and $P_j$ ($i, j \in \{0, 1\}$).

Shared Variables

• boolean flag[2]: Initialized to {false, false}. flag[i] = true indicates process $P_i$ wants to enter the Critical Section.
• int turn: Indicates whose turn it is to enter the Critical Section.

Implementation Structure (Process $P_i$)

// Process P_i structure (where j is the other process: j = 1 - i)
do {
    // Entry Section
    flag[i] = true;              // Declare intention to enter
    turn = j;                    // Yield priority to the other process
    
    // Busy wait while other process wants to enter and has the turn
    while (flag[j] && turn == j);

    // CRITICAL SECTION (Access Shared Resource)
    // ...

    // Exit Section
    flag[i] = false;             // Relinquish access

    // REMAINDER SECTION
    // ...
} while (true);

Verification

• Mutual Exclusion: For both $P_0$ and $P_1$ to enter simultaneously, turn would need to be both $0$ and $1$ concurrently, which is physically impossible on a single variable assignment.
• Progress & Bounded Waiting: The turn variable resolves ties immediately, preventing mutual blocking (deadlock) and guaranteeing bounded entry attempts.

Summary and Key Takeaways

• Convoy Effect: First-Come, First-Served scheduling allows long compute-bound jobs to block short interactive jobs, driving up average wait time.
• SJF vs. SRTF: Non-preemptive Shortest Job First optimizes average wait times, while Shortest Remaining Time First preempts running processes when shorter jobs arrive.
• Time Quantum Balance: Round Robin performance depends directly on quantum size; large quanta degrade to FCFS, whereas tiny quanta trigger context-switch thrashing.
• Starvation Mitigation via Aging: Unbounded priority queue blocking is resolved by incrementally raising the priority of long-waiting tasks over time.
• Modern Queueing via MLFQ: Multilevel Feedback Queues dynamically categorize tasks across execution tiers based on runtime burst behavior.
• The Critical Section Triad: Every valid synchronization mechanism must strictly satisfy Mutual Exclusion, Progress, and Bounded Waiting.
• Peterson's Algorithm: Guarantees mutual exclusion and bounded entry for two concurrent processes using shared flag arrays and an explicit turn handover variable.