CPU Scheduling Criteria and Non-Preemptive Algorithms

1. Why Do We Need CPU Scheduling?

In a modern operating system, multiple processes (e.g., P1, P2, P3) reside in memory and compete for CPU execution time. Because a single CPU can execute only one instruction stream at a given instant, the operating system must rapidly switch execution between these processes in milliseconds.

The fundamental goal of CPU scheduling is to maximize system performance metrics—such as CPU utilization and throughput—while minimizing user-centric delays like waiting time and response time. Without an organized scheduling discipline, the CPU would sit idle or process jobs inefficiently, leading to poor multitasking responsiveness.

2. Core Mental Model: The Restaurant Kitchen Analogy

To understand CPU scheduling, imagine a high-end restaurant kitchen with a single head chef (the CPU).

The Customers / Orders: Various customer orders arrive at the counter representing Processes.
The Waiting Area (Ready Queue): Orders waiting to be prepared are placed in an ordered queue in the kitchen counter memory (RAM).
The Expediter (CPU Scheduler): The head chef or kitchen manager decides which dish to cook next based on specific rules (e.g., shortest prep time first, or first-ordered-first-cooked) to maximize meals served per hour and keep customer wait times low.

3. System Queues in Operating Systems

Before a process is executed by the CPU, it flows through distinct administrative queues managed by the operating system kernel:

Structure & Concept Flow

Job Pool (Hard Disk / Secondary Storage)

| (Long-Term Scheduler loads into RAM)

Ready Queue (Processes in RAM waiting for CPU allocation)

| (Short-Term Scheduler dispatches to CPU)

Running State / CPU Execution

+---> [I/O Request / Printer / Keyboard] ---> Device Queue (Blocked / Waiting for I/O)

Job Queue: Contains all processes present in the mass storage system (hard disk) awaiting admission into main memory.
Ready Queue: Contains all processes residing in main memory (RAM) that are completely ready and waiting to be assigned to the CPU core.
Device Queue: Contains processes that are temporarily suspended because they are waiting for an Input/Output (I/O) completion event (such as waiting for keyboard input or a printer spooler response).

4. The Three Primary Operating System Schedulers

The operating system utilizes distinct schedulers operating at different time intervals to manage the lifecycle of processes:

Scheduler Type	Common Name	Core Responsibility / Action	Frequency / Execution Speed
Long-Term Scheduler	Job Scheduler	Decides which programs are admitted from secondary storage into the RAM ready queue. Controls the Degree of Multiprogramming.	Infrequent (Seconds to Minutes)
Short-Term Scheduler	CPU Scheduler	Selects from among the processes that are ready in RAM and allocates the CPU to one of them.	Extremely Frequent (Milliseconds)
Medium-Term Scheduler	Swapper	Temporarily removes processes from RAM to secondary storage (swapping out) and re-introduces them later (swapping in) to manage memory overcommit.	Moderate (Variable based on memory load)

5. CPU Scheduling Criteria (Performance Metrics)

To evaluate how effective a scheduling algorithm is, computer scientists and system engineers measure five primary performance criteria:

CPU Utilization: The percentage of time that the CPU is actively working rather than sitting idle. We aim to maximize this metric, typically targeting between $40\%$ and $90\%$ utilization under heavy workloads.
Throughput: The total number of completed processes executed per unit of time (e.g., 50 processes per minute). Higher throughput indicates superior system efficiency.
Turnaround Time ( $TT$ ): The total elapsed time from the exact moment a process is submitted to the system until it is completely finished. It includes time spent waiting in memory, waiting in queues, executing on the CPU, and doing I/O.

\begin{aligned} \text{Turnaround Time} &= \text{Completion Time} - \text{Arrival Time} \end{aligned}

Waiting Time ( $WT$ ): The cumulative total amount of time a process spends waiting inside the ready queue while desiring CPU time. Non-preemptive algorithms are heavily judged by how much waiting time they impose on short processes.

\begin{aligned} \text{Waiting Time} &= \text{Turnaround Time} - \text{Burst Time} \end{aligned}

Response Time: The duration from the time a process is submitted until the first response is produced (especially critical for interactive GUI or terminal environments).

6. Classification of CPU Scheduling Algorithms

Scheduling algorithms are broadly categorized into two major paradigms based on how control is relinquished by the CPU:

Structure & Concept Flow

CPU Scheduling Algorithms

+-- Non-Preemptive Algorithms

| +-- First-Come, First-Served (FCFS)

| +-- Shortest Job First (SJF - Non-Preemptive)

| +-- Priority Scheduling (Non-Preemptive)

| +-- Highest Response Ratio Next (HRRN)

+-- Preemptive Algorithms

+-- Round Robin (RR)

+-- Shortest Remaining Time Next (SRTN)

+-- Priority Scheduling (Preemptive)

Non-Preemptive Scheduling: Once the CPU has been allocated to a process, the process keeps the CPU until it voluntarily releases it (either by terminating or by switching to an I/O waiting state). The OS cannot forcibly yank the CPU away.
Preemptive Scheduling: The operating system has the authority to forcibly interrupt a currently running process and allocate the CPU to another process (e.g., when a higher-priority process arrives or a time quantum expires).

7. Deep Dive: First-Come, First-Served (FCFS)

First-Come, First-Served (FCFS) is the simplest non-preemptive scheduling algorithm.

Mechanics: Processes are allocated the CPU strictly in the order in which they arrive in the ready queue. The process that arrives first gets executed first.
Implementation Analogy: A standard checkout line at a grocery store counter.

The Convoy Effect Problem

FCFS suffers from a major performance flaw known as the Convoy Effect.

The Problem: Short processes are forced to wait behind a single large, CPU-bound process that arrived just slightly ahead of them.
Real-World Impact: If a 1-minute task arrives immediately after a 10-minute task, the 1-minute task must wait for the entire 10-minute task to finish execution. This spikes the average waiting time and degrades interactive system responsiveness.

8. Visualizing Execution: Gantt Charts

A Gantt Chart is a specialized timeline bar graph used in operating systems to visually depict the exact sequence of process execution, CPU start times, completion times, and idle gaps.

Structure & Concept Flow

Time: 0 5 12 15

+-----+---------+---------------+

| P1 | P2 | P3 |

+-----+---------+---------------+

Process P1: Executes from time $0$ to time $5$ (Burst Time = $5$ ).
Process P2: Executes from time $5$ to time $12$ (Burst Time = $7$ ).
Process P3: Executes from time $12$ to time $15$ (Burst Time = $3$ ).

9. Introduction to Shortest Job First (SJF)

Building upon the limitations of FCFS, Shortest Job First (SJF) is another foundational non-preemptive algorithm designed to drastically reduce average waiting times.

Mechanics: Associates each process with the length of its next CPU burst. When the CPU is available, it is assigned to the process that has the smallest overall burst time. If two processes have identical burst times, FCFS tie-breaking is applied.
Advantage: Proven mathematically to provide the minimum possible average waiting time for a given set of processes.
Practical Challenge: It is often impossible to know exact future CPU burst lengths in advance, requiring systems to estimate burst durations using statistical approximations (such as exponential averaging).

Summary and Key Takeaways

CPU Scheduling Objective: Maximizes CPU utilization ( $40\text{--}90\%$ ) and system throughput while minimizing waiting time and response time.
System Queues: Processes flow through structured administrative zones including the Job Queue (disk), Ready Queue (RAM), and Device Queue (I/O).
Scheduler Hierarchy: The Long-Term Scheduler manages program loading and multiprogramming degree; the Short-Term Scheduler (CPU Scheduler) dispatches processes rapidly in milliseconds; the Medium-Term Scheduler handles memory swapping.
Core Performance Metrics: Evaluated via CPU Utilization, Throughput, Turnaround Time ( $TT$ ), Waiting Time ( $WT$ ), and Response Time.
Non-Preemptive vs. Preemptive: Non-preemptive algorithms allow a process to hold the CPU until completion or I/O block, whereas preemptive algorithms allow forcible interruption by the OS kernel.
FCFS Mechanics: First-Come, First-Served operates as a simple queue but suffers from the Convoy Effect, where quick jobs get delayed behind long-running tasks.
Gantt Chart Visualization: Graphical timelines are essential tools for mapping out scheduling start/end times and calculating exact performance metrics.
Shortest Job First (SJF): Prioritizes processes with the shortest burst time, achieving optimal minimum average waiting time at the cost of needing future burst time predictions.