Chapter 5: CPU Scheduling
1. Basic Concepts
CPU scheduling determines which process gets the CPU when multiple processes are
waiting.
Types of Scheduling
• Preemptive: CPU can be taken away from a running process.
• Non-preemptive: Running process keeps the CPU until it finishes or blocks.
CPU–I/O Burst Cycle
Processes alternate between:
• CPU bursts (computation)
• I/O bursts (waiting for I/O)
Scheduler Components
• Short-term scheduler (CPU scheduler): Chooses which ready process runs
next.
• Dispatcher: Gives control of CPU to the selected process (context switch).
2. Scheduling Criteria
Used to evaluate scheduling algorithms.
Key Criteria
1. CPU Utilization – Keep CPU as busy as possible.
2. Throughput – Number of processes completed per unit time.
3. Turnaround Time – Completion time – submission time.
4. Waiting Time – Time spent in ready queue.
5. Response Time – Time from request → first response (important for interactive
systems).
Goal
Maximize:
• CPU utilization
• Throughput
Minimize:
• Turnaround time
• Waiting time
• Response time
3. Scheduling Algorithms
1. First-Come First-Served (FCFS)
• Non-preemptive
• Simple, fair
• Convoy effect: Short jobs wait behind long jobs.
2. Shortest-Job-First (SJF)
• Can be preemptive (Shortest-Remaining-Time-First) or non-preemptive
• Minimizes average waiting time
• Requires predicting CPU burst → not always practical
3. Priority Scheduling
• Each process has a priority value
• Preemptive or non-preemptive
• Problem: starvation (low priority process waits forever)
• Solution: aging (increase priority over time)
4. Round Robin (RR)
• Preemptive with fixed time quantum
• Good for interactive systems
• Smaller quantum → better response but more context switches
5. Multilevel Queue Scheduling
• Multiple separate queues (foreground, background, system, etc.)
• No process moves between queues
• Each queue has its own scheduling algorithm
• Priority between queues is fixed
6. Multilevel Feedback Queue
• Processes can move between queues
• Prevents starvation
• Very flexible; widely used
4. Thread Scheduling
Thread scheduling depends on whether the system uses:
• User-level threads
• Kernel-level threads
Contention Scope
• Process Contention Scope (PCS): Compete with threads inside the same
process.
• System Contention Scope (SCS): All threads compete for CPU (kernel-level).
Many modern OSes (e.g., Linux) use only one-to-one kernel threads → scheduling done
by kernel.
5. Multi-Processor Scheduling
Modern systems have multiple CPUs or cores.
Issues
• Load balancing: Ensure all cores have work.
• Processor affinity: Processes prefer to run on the same CPU for cache
efficiency.
Approaches
1. Asymmetric multiprocessing (AMP): One CPU handles all scheduling.
2. Symmetric multiprocessing (SMP): Each CPU schedules independently
(common today).
6. Real-Time CPU Scheduling
Used in systems that require guaranteed response times.
Types
• Hard real-time: Deadlines must be met.
• Soft real-time: Best-effort, some deadlines may be missed.
Algorithms
• Rate Monotonic Scheduling (RMS): Fixed priority → shorter periods = higher
priority.
• Earliest Deadline First (EDF): Dynamic priority → earliest deadline gets CPU.
7. Operating System Examples
Windows
• Priority-based, preemptive scheduler
• Uses multilevel feedback queues
• Threads are schedulable entities
Linux (CFS – Completely Fair Scheduler)
• Proportional share scheduling
• Tries to ensure each process gets fair CPU time
• Uses a red-black tree structure
Solaris
• Uses priority-based scheduling
• Multiple classes: real-time, system, time-sharing, etc.
8. Algorithm Evaluation
Algorithms are compared using:
1. Deterministic Modeling
• Hand-crafted example to compute waiting/turnaround time.
2. Queueing Models
• Use mathematical distribution models (advanced).
3. Simulation
• Simulating scheduling with random or real workloads.
4. Implementation & Measurement
• Implement in OS and measure actual performance.