Chapter 5: CPU Scheduling¶

Basic Concepts¶

CPU Scheduling is the process of deciding which process in the ready queue should be allocated to the CPU next.
The CPU Scheduler selects from among the processes in memory that are ready to execute and allocates the CPU to one of them.
CPU scheduling is necessary because:
- Multiple processes compete for CPU time.
- It helps maximize CPU utilization and system throughput.

Types of Scheduling:

Long-term (Job Scheduling) – selects which processes are admitted to the system.
Short-term (CPU Scheduling) – decides which process gets the CPU next.
Medium-term Scheduling – temporarily removes processes from memory (swapping).

Scheduling Events:

CPU scheduling decisions occur when a process:

Scheduling can be:

CPU Utilization: Keep the CPU as busy as possible.
Throughput: Number of processes completed per time unit.
Turnaround Time: Total time to execute a particular process.
Waiting Time: Time a process spends waiting in the ready queue.
Response Time: Time from request submission until the first response is produced.
Fairness: Ensuring all processes get a reasonable share of CPU time.

Goals of Scheduling:

First-Come, First-Served (FCFS): - Processes are scheduled in the order they arrive. - Non-preemptive. - Simple but can cause the convoy effect (long jobs delay shorter ones).
Shortest Job First (SJF): - Selects the process with the smallest CPU burst time. - Can be preemptive (Shortest Remaining Time First) or non-preemptive. - Optimal in minimizing average waiting time, but requires burst-time prediction.
Priority Scheduling: - Each process has a priority; the CPU is assigned to the highest-priority process. - Can be preemptive or non-preemptive. - May lead to starvation; use aging to prevent it.
Round Robin (RR): - Each process gets a small time quantum. - After the quantum expires, the process is preempted and moved to the end of the ready queue. - Ensures fairness; suitable for time-sharing systems. - Performance depends on the size of the time quantum.
Multilevel Queue Scheduling: - Ready queue is partitioned into multiple queues (e.g., foreground and background). - Each queue has its own scheduling algorithm. - Processes are permanently assigned to a queue.
Multilevel Feedback Queue: - Similar to multilevel queue, but allows processes to move between queues. - Used to dynamically adjust priorities.

Involves scheduling processes across multiple CPUs or cores.
Two main approaches:
- Asymmetric Multiprocessing: One processor handles scheduling and I/O; others execute user code.
- Symmetric Multiprocessing (SMP): Each processor is self-scheduling; processes are in a common ready queue.

Load Balancing:

Ensures that work is evenly distributed across all processors.
Can be achieved by: - Push Migration: A process periodically checks for imbalance and moves processes from busy CPUs. - Pull Migration: Idle CPUs pull processes from busy ones.

Processor Affinity:

Keeps a process on the same processor to improve cache performance.
Types: - Soft Affinity: Preference but not enforced. - Hard Affinity: Process bound to a specific processor.

Real-Time Scheduling:

**Comparison of CPU Scheduling Algorithms**¶
Algorithm	Preemptive	Type	Fairness	Complexity	Remarks
FCFS (First-Come, First-Served)	No	Non-preemptive	Low (convoy effect)	Simple	Long jobs delay short ones
SJF (Shortest Job First)	Optional	Both	Medium	Moderate	Optimal average waiting time
Priority Scheduling	Optional	Both	Low (can starve low)	Moderate	Use aging to prevent starvation
Round Robin (RR)	Yes	Preemptive	High	Simple	Depends on time quantum
Multilevel Queue	Both	Preemptive/Non	Medium	High	Separate queues by type
Multilevel Feedback Queue	Yes	Preemptive	High	Very High	Dynamic priority adjustment

CPU scheduling is key to system performance and responsiveness.
Algorithms differ in fairness, complexity, and efficiency.
In multiprocessor systems, additional factors like load balancing and processor affinity come into play.