Chapter 6: CPU Scheduling

CPU Scheduling

Process of determining which process or thread will use the CPU at any given time, based on the scheduling algorithm and current system state

CPU Scheduling Decisions

Occur when a process switches from running to waiting (nonpreemptive), running to ready (preemptive), waiting to ready (preemptive), or terminates (nonpreemptive)

Dispatcher

Transfers control of the CPU from one process to another

Scheduling Algorithms

First-Come First-Serve (FCFS): Non-preemptive scheduling algorithm where processes are executed in the order they arrive. It is simple and fair but can lead to the "convoy effect," where short processes wait behind long ones.

Shortest Job First (SJF): Non-preemptive scheduling algorithm that selects the process with the shortest burst time. It minimizes average waiting time but can cause starvation for longer processes.

Shortest Remaining Time First (SRTF): preemptive version of SJF where the process with the shortest remaining time is selected next. It improves response time for short processes but can lead to high context switching.

Round Robin (RR): Preemptive scheduling algorithm that assigns a fixed time slice (quantum) to each process in the ready queue. It is simple and fair but may lead to high context switching if the quantum is too small.

Priority Scheduling: Selects processes based on priority levels. It can be preemptive or non-preemptive. Higher-priority processes are executed before lower-priority ones, but it can lead to starvation for low-priority processes. This issue can be solved by aging, which means increasing the priority for “older” processes.

CPU Burst

Amount of time the process uses the processor before it is no longer ready

Length determined by exponential averaging