[OS Concepts] 05. CPU Scheduling Algorithms

CPU Scheduling Basic Concepts

CPU Burst and I/O Burst

Process execution consists of alternating CPU bursts and I/O bursts.

[Process Execution Cycle]

CPU Burst -> I/O Burst -> CPU Burst -> I/O Burst -> ...

  |-------|          |--------|          |--|
  CPU exec          I/O wait           CPU exec
  (compute)        (disk read)        (compute)

CPU-bound process: Long CPU bursts, few I/O bursts
I/O-bound process: Short CPU bursts, many I/O bursts

Preemptive vs Non-preemptive Scheduling

Non-preemptive: Execution continues until the process voluntarily releases the CPU
Preemptive: The OS can forcibly reclaim the CPU from a running process

There are four situations where CPU scheduling is needed.

Transition from running to waiting state (I/O request) - Non-preemptive
Transition from running to ready state (interrupt) - Preemptive
Transition from waiting to ready state (I/O completion) - Preemptive
Process termination - Non-preemptive

Dispatcher

The dispatcher is the module that actually hands the CPU to the process selected by the CPU scheduler.

Performs context switch
Switches to user mode
Jumps to the appropriate location in the program

Dispatch latency should be as short as possible.

Scheduling Criteria

Criterion	Description	Optimization
CPU Utilization	Ratio of time the CPU is working	Maximize
Throughput	Number of processes completed per unit time	Maximize
Turnaround Time	Time from submission to completion	Minimize
Waiting Time	Total time spent in the ready queue	Minimize
Response Time	Time from submission to first response	Minimize

Scheduling Algorithms

1. FCFS (First-Come, First-Served)

The simplest scheduling. The process that arrives first is executed first.

[FCFS Example]

Process  Arrival  CPU Burst
  P1        0         24
  P2        0          3
  P3        0          3

Execution order: P1 -> P2 -> P3

Gantt Chart:
|----P1----|--P2--|--P3--|
0         24    27     30

Waiting time: P1=0, P2=24, P3=27
Average waiting time: (0+24+27)/3 = 17

What if the order were P2, P3, P1?
|P2|P3|----P1----|
0  3  6         30

Waiting time: P1=6, P2=0, P3=3
Average waiting time: (6+0+3)/3 = 3  (huge difference!)

Convoy Effect: Short processes line up behind a long process. This is a typical disadvantage of FCFS.

2. SJF (Shortest-Job-First)

Executes the process with the shortest CPU burst first. Theoretically guarantees optimal average waiting time.

[SJF Example - Non-preemptive]

Process  Arrival  CPU Burst
  P1        0         6
  P2        2         8
  P3        4         7
  P4        5         3

Gantt Chart:
|--P1--|P4|---P3---|----P2----|
0      6  9      16         24

Waiting time: P1=0, P2=16, P3=5, P4=1
Average waiting time: (0+16+5+1)/4 = 5.5

[SRTF (Shortest Remaining Time First) - Preemptive SJF]

Process  Arrival  CPU Burst
  P1        0         6
  P2        2         8
  P3        4         7
  P4        5         3

Time 0: P1 starts (remaining: 6)
Time 2: P2 arrives (remaining: 8) -> P1 continues (remaining: 4)
Time 4: P3 arrives (remaining: 7) -> P1 continues (remaining: 2)
Time 5: P4 arrives (remaining: 3) -> P1 continues (remaining: 1)
Time 6: P1 completes -> P4 starts (remaining: 3)
Time 9: P4 completes -> P3 starts (remaining: 7)
Time 16: P3 completes -> P2 starts (remaining: 8)
Time 24: P2 completes

Gantt Chart:
|--P1--|P4|---P3---|----P2----|
0      6  9      16         24

The key problem with SJF is that the next CPU burst length cannot be known in advance. In practice, exponential averaging based on past bursts is used for prediction.

Next prediction = alpha * recent actual + (1 - alpha) * previous prediction

alpha = 0: Ignore recent value (use only previous prediction)
alpha = 1: Ignore previous prediction (use only recent actual)
Typically alpha = 0.5

3. Priority Scheduling

Assigns a priority to each process and executes the one with the highest priority first.

[Priority Scheduling Example] (lower number = higher priority)

Process  CPU Burst  Priority
  P1        10         3
  P2         1         1
  P3         2         4
  P4         1         5
  P5         5         2

Execution order: P2 -> P5 -> P1 -> P3 -> P4

Gantt Chart:
|P2|--P5--|----P1----|P3|P4|
0  1      6        16 18 19

Average waiting time: (6+0+16+18+1)/5 = 8.2

Starvation: Low-priority processes may never execute. This is solved with the aging technique, which gradually increases the priority of waiting processes over time.

4. Round Robin

Scheduling for time-sharing systems. Each process is given a fixed time quantum.

[Round Robin Example] (time quantum = 4)

Process  CPU Burst
  P1        24
  P2         3
  P3         3

Gantt Chart:
|P1|P2|P3|P1|P1|P1|P1|P1|
0  4  7 10 14 18 22 26 30

P1: Runs 4 units -> back of ready queue
P2: Runs 3 units (complete)
P3: Runs 3 units (complete)
P1: Remaining 20 units run in chunks of 4

Waiting time: P1=6, P2=4, P3=7
Average waiting time: (6+4+7)/3 = 5.67

The choice of time quantum (q) is important.

If q is too large: Same as FCFS
If q is too small: Context switch overhead increases
Empirically, set so that 80% of CPU bursts complete within q

5. Multilevel Queue Scheduling

Separates the ready queue into multiple queues and applies different scheduling algorithms to each.

[Multilevel Queue Scheduling]

High Priority
+------------------------------------------+
| System Processes      | FCFS              |
+------------------------------------------+
| Interactive Processes | RR (q=8)          |
+------------------------------------------+
| Interactive Editing   | RR (q=16)         |
+------------------------------------------+
| Batch Processes       | FCFS              |
+------------------------------------------+
| Student Processes     | FCFS              |
+------------------------------------------+
Low Priority

Upper queues must be empty before lower queues execute (fixed priority)
Or time allocation between queues (e.g., 80% interactive, 20% batch)

6. Multilevel Feedback Queue

Processes can move between queues. The most flexible scheduling algorithm.

[Multilevel Feedback Queue]

Queue 0: RR (q=8)   <--- New processes enter here
  |
  | If not complete within q=8, move to Queue 1
  v
Queue 1: RR (q=16)
  |
  | If not complete within q=16, move to Queue 2
  v
Queue 2: FCFS

Operation example:
- Short CPU burst process: Completes in Queue 0 (fast response)
- CPU-bound process: Moves down Queue 0 -> Queue 1 -> Queue 2
- Process returning after I/O completion: Moves back up to Queue 0

Result: I/O-bound + interactive processes get high priority
        CPU-bound processes get long time allocation in lower queues

Thread Scheduling

PCS (Process-Contention Scope): Threads compete within the same process at user level
SCS (System-Contention Scope): All threads compete at system level

Linux and Windows use SCS. Only kernel threads are scheduled on the CPU.

Multiprocessor Scheduling

Approaches

Asymmetric Multiprocessing: One processor makes all scheduling decisions (simple but bottleneck)
Symmetric Multiprocessing (SMP): Each processor schedules independently (modern standard)

Processor Affinity

A process tends to stay on the processor it is currently running on because data is already in the cache.

Soft Affinity: Prefers to run on the same processor but not guaranteed
Hard Affinity: Guarantees execution on a specific set of processors

// Setting processor affinity in Linux
#define _GNU_SOURCE
#include <sched.h>

void set_cpu_affinity(int cpu_id) {
    cpu_set_t cpuset;
    CPU_ZERO(&cpuset);
    CPU_SET(cpu_id, &cpuset);

    // Bind current thread to a specific CPU
    sched_setaffinity(0, sizeof(cpuset), &cpuset);
}

Load Balancing

Distributes work evenly across all processors in an SMP system.

Push Migration: Periodically moves tasks from overloaded processors
Pull Migration: Idle processors pull tasks from busy processors

Linux CFS (Completely Fair Scheduler)

CFS, the default scheduler since Linux 2.6.23, distributes "fair" CPU time to each process.

Core Concept: Virtual Runtime (vruntime)

[CFS Operating Principle]

Tracks each process's vruntime
Runs the process with the smallest vruntime next

vruntime increase rate = actual runtime / weight (based on nice value)

Process with low nice value (high priority):
  -> Large weight -> vruntime increases slowly -> Scheduled more often

Process with high nice value (low priority):
  -> Small weight -> vruntime increases quickly -> Scheduled less often

Red-Black Tree

CFS uses a Red-Black tree to manage processes sorted by vruntime.

[CFS Red-Black Tree]

         Sorted by vruntime

              (P3: 50)
             /        \
        (P1: 30)    (P5: 70)
        /    \          \
   (P2: 20) (P4: 40)  (P6: 80)

Leftmost node (P2, vruntime=20) is the next to execute

Insert/Delete/Search: O(log N) guaranteed

// Selecting the next process to run in CFS (conceptual code)
struct task_struct *pick_next_task_fair(struct rq *rq) {
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct rb_node *left;

    // Select the leftmost node in the Red-Black tree
    // = process with the smallest vruntime
    left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left)
        return NULL;

    struct sched_entity *se = rb_entry(left,
                                        struct sched_entity,
                                        run_node);
    return container_of(se, struct task_struct, se);
}

Target Latency

CFS guarantees that all runnable processes execute at least once within the target latency.

Example: Target latency = 20ms, runnable processes = 4

With equal priority, each process gets 5ms
If there are too many processes, a minimum granularity is guaranteed

Algorithm Comparison Summary

[Scheduling Algorithm Comparison]

Algorithm        Preempt Starv  Advantage           Disadvantage
---------        ------- -----  ---------           ------------
FCFS             X       X      Simple              Convoy effect
SJF              X       O      Optimal wait time   Burst prediction hard
SRTF             O       O      Better than SJF     Burst prediction hard
Priority         Both    O      Flexible            Starvation (aging needed)
Round Robin      O       X      Fair, good response q selection critical
Multilevel Queue O       O      Differentiated svc  No inter-queue movement
MLF Queue        O       Poss.  Most flexible       Complex parameter tuning
CFS              O       X      Fair CPU allocation Complex implementation

Summary

CPU scheduling is the core of a multiprogramming OS. Various algorithms exist including FCFS, SJF, priority, and round robin, each offering different trade-offs between throughput, response time, and fairness. Linux's CFS uses a Red-Black tree and the virtual runtime concept to achieve efficient and fair scheduling.