CPU Scheduling Strategies and Multiprogramming Mechanics

CPU scheduling is the core mechanism that allows modern operating systems to achieve multiprogramming and interactive execution. By dynamically allocating the central processing unit across various processes and threads, the OS balances resource utilization, maximizes throughput, and minimizes user-perceived delays.

1. Context Switching and Pure Overhead

A process moves through standard lifecycle states: New, Ready, Running, Waiting, and Terminated. When the CPU finishes executing or pauses execution of one process to service another, the operating system executes a Context Switch.

The Mechanism of State Preservation

Every process is governed by a Process Control Block (PCB) that stores its execution context:

1. Saving State: The OS captures the current snapshot of Process 1 ($P_1$)—including the program counter, processor registers, memory management information, and file state—and persists it into $PCB_1$.
2. Restoring State: The OS locates $PCB_2$, reads the latest preserved state, loads its register values and program counter into hardware registers, and begins executing Process 2 ($P_2$).
3. Pure Overhead: During context switching, the CPU performs strictly administrative chores. It executes no user code. This spent time is known as pure overhead. A higher frequency of context switches increases overhead and decreases effective CPU throughput.

2. Threads: The Light-Weight Execution Units

A Thread is the smallest schedulable unit of CPU execution within an operating system. A single process can host multiple threads (often referred to as Lightweight Processes or LWPs).

• Shared Resources: Threads residing within the same process share the text (code) segment, data segment (global variables, heap allocations), and OS resources (such as open file handles).
• Private Resources: To maintain independent execution, each thread preserves its own:
  • Unique Thread ID (TID)
  • Dedicated Program Counter (PC)
  • Architectural Register State
  • Independent Call Stack (local variables and stack frames)

3. Structural Comparison: Processes vs. Threads

Processes provide isolation and robust execution barriers, whereas threads provide speed and shared memory.

4. Thread Implementation Architectures & Models

Threads are implemented via two primary execution spaces:

• User-Level Threads (ULT): Managed by user-space runtime libraries without kernel awareness. Thread switching does not require CPU privilege-mode transitions, making operations extremely fast. However, if one ULT issues a blocking system call (e.g., synchronous I/O), the entire host process and all peer threads block.
• Kernel-Level Threads (KLT): Managed directly by the OS kernel. The kernel independently schedules each thread, enabling genuine multicore parallelism. Modern platforms (Linux, modern Windows) natively rely on kernel-level threading.

Multithreading Mapping Models

Many-to-One                 One-to-One                 Many-to-Many
 [ULT] [ULT] [ULT]         [ULT]   [ULT]            [ULT] [ULT] [ULT] [ULT]
   \     |     /             |       |                 \    \   /    /
    v    v    v              v       v                  v    v v    v
     [  KLT  ]             [KLT]   [KLT]               [ KLT ] [ KLT ]

1. Many-to-One:
   • Multiple user threads map to a single kernel thread.
   • Limitation: No true parallelism on multicore systems; a single blocking system call suspends all threads.
2. One-to-One:
   • Every individual user thread maps to a dedicated kernel thread.
   • Advantage: Native concurrency across multiple CPU cores; blocking calls do not impede peer threads. Adopted by Linux (NPTL) and Windows.
3. Many-to-Many:
   • Multiplexes many user threads over an equal or smaller number of kernel threads, allowing the developer to spawn arbitrary threads while the OS schedules them across available execution contexts.

Practical Benefits of Multithreading

• Responsiveness: User interfaces remain active on the primary thread while heavy jobs (e.g., network downloads, file parsing) run on background worker threads.
• Resource Sharing: Memory and open resources are shared natively without relying on complex IPC pipelines.
• Economy: Thread creation and context switching use significantly fewer CPU cycles than standard process forks.
• Scalability: Threads natively spread across modern multi-socket and multicore hardware architectures.

5. CPU Scheduling Queues and Schedulers

Processes transition through specific operating system queues throughout their lifecycle:

• Job Queue: Stores all processes present in the system, including those residing in secondary storage.
• Ready Queue: Holds processes resident in main memory (RAM) that are ready and waiting for CPU allocation.
• Device (I/O) Queue: Holds processes waiting for access to specific input/output devices (e.g., hard drives, network cards, printers).

The Three Operational Schedulers

1. Long-Term Scheduler (Job Scheduler):
   • Controls the Degree of Multiprogramming (the total number of processes residing simultaneously in memory).
   • Operates infrequently (intervals of seconds to minutes).
   • Regulates a balanced mix of I/O-bound and CPU-bound jobs.
2. Short-Term Scheduler (CPU Scheduler):
   • Selects which ready process from RAM receives immediate CPU execution.
   • Executes frequently (intervals of 10 to 100 milliseconds). Must run with high computational efficiency.
3. Medium-Term Scheduler (Swapper):
   • Removes running or waiting processes from primary memory to disk (swapping out) during memory pressure, restoring them later (swapping in) to stabilize system performance.

6. Core Scheduling Performance Metrics

The operating system evaluates CPU scheduling algorithms using five primary mathematical metrics:

• CPU Utilization: The percentage of time the processor is actively executing application or system code. Target: 40% (light load) to 90% (heavy load).
• Throughput: The total count of completed execution processes per designated unit of time. Target: Maximize.
• Turnaround Time ($TAT$): Total elapsed duration spanning the exact moment of process arrival to its final termination:

Target: Minimize.

• Waiting Time ($WT$): The cumulative aggregate of time a process spends waiting inside the Ready Queue:

Target: Minimize.

• Response Time ($RT$): The duration elapsed from original process arrival to the exact timestamp of its very first scheduled CPU execution response:

Target: Minimize.

7. Preemptive vs. Non-Preemptive Scheduling

Operating system scheduling logic falls into two distinct execution strategies:

1. Non-Preemptive Scheduling:
   • Once a process gains access to the CPU, it runs uninterrupted until it yields control willingly—either by issuing a blocking I/O request or by terminating.
   • Trade-off: Simpler to design and free of race conditions, but can lead to long wait times for small tasks.
2. Preemptive Scheduling:
   • The operating system can interrupt a currently running process using hardware timers, priority adjustments, or interrupts, safely moving it back to the Ready Queue.
   • Trade-off: Prevents CPU monopolization and improves real-time responsiveness, but incurs context-switching overhead and requires synchronization around shared data.

8. First-Come, First-Served (FCFS) and the Convoy Effect

First-Come, First-Served (FCFS) is the simplest non-preemptive scheduling algorithm. The CPU core is allocated strictly to processes in the chronological order of their arrival into the Ready Queue (managed internally via standard FIFO structures).

The Convoy Effect Walkthrough

A major limitation of FCFS is the Convoy Effect, where short processes are forced to wait behind a long, CPU-heavy process.

Consider three processes arriving simultaneously at $T=0$ in the order $P_1, P_2, P_3$:

• Burst Time for $P_1 = 24\text{ ms}$
• Burst Time for $P_2 = 3\text{ ms}$
• Burst Time for $P_3 = 3\text{ ms}$

Execution Timeline (Gantt Chart)

Performance Analysis

• Waiting Time for $P_1$: $0\text{ ms}$
• Waiting Time for $P_2$: $24\text{ ms}$
• Waiting Time for $P_3$: $27\text{ ms}$
• Average Waiting Time:

If the same processes had arrived in reverse order ($P_2, P_3, P_1$):

• Average Waiting Time:

Key Insight: In FCFS, when a long CPU-bound process holds the execution pipeline, all subsequent short or I/O-bound processes are blocked behind it. This degrades both average waiting times and peripheral device utilization.

Summary and Key Takeaways

• Context Switching: The mechanism of preserving a running process's state in its PCB and loading another's. It allows multiprogramming but introduces pure overhead, during which no user work executes.
• Process vs. Thread: Processes own isolated virtual memory maps and file handles; threads exist inside a process, sharing code, data, and heap while retaining their own stack and register set.
• Crash Isolation: Because threads share memory, an unhandled crash in one thread can terminate the entire process. Separate processes remain crash-isolated.
• Multithreading Models: Modern operating systems use the One-to-One model, mapping each user thread to a distinct kernel thread for genuine multicore execution.
• Queue Hierarchy: The OS manages processes using three primary queues: the Job Queue (disk), the Ready Queue (RAM), and the Device Queue (I/O).
• Scheduler Types: The Long-Term Scheduler controls the degree of multiprogramming, the Short-Term Scheduler handles rapid CPU allocations, and the Medium-Term Scheduler handles memory swapping.
• Performance Criteria: Scheduling algorithms aim to maximize CPU Utilization and Throughput, while minimizing Turnaround Time, Waiting Time, and Response Time.
• The Convoy Effect: In non-preemptive FCFS scheduling, short tasks queued behind long, compute-heavy jobs experience high waiting times, which lowers overall system efficiency.