Semester 3Operating SystemsProcess Management
Process scheduling
There is a physical limit how many processes can be executed concurrently. So the scheduler decides which processes to run, for how long, when to stop. Core goal is to maximize the CPU utilization while keeping the system responsive.
Types of schedulers
- Long-Term Scheduler (Job Scheduler): Decides which programs on disk get loaded into main memory (RAM). Controls the degree of multiprogramming (how many processes run concurrently).
- Short-Term Scheduler (CPU Scheduler): Executes extremely fast (milliseconds) to select which process in the Ready Queue gets CPU execution time next.
- Medium-Term Scheduler (Swapper): Removes processes temporarily from RAM to disk (swapping out) when memory gets congested, and loads them back later (swapping in).
Preemptive vs. Non-Preemptive Scheduling
- Non-Preemptive: Once a process gets the CPU, it holds it until it voluntarily finishes or pauses for I/O.
- Preemptive: The OS can forcefully pause a running process (via timer interrupts) and hand the CPU to a higher-priority or newly waiting process.
The Core Mechanisms: Context Switching
When the scheduler switches execution from Process A to Process B:
Info
To switch context CPU takes pure clock cycles without doing ANY useful work to the user. An Efficient scheduler should also minimize context unnecessary switching.
Common CPU Scheduling Algorithms
| Algorithm | Type | How It Works | Key Advantage | Disadvantage |
|---|---|---|---|---|
| FCFS (First-Come, First-Served) | Non-Preemptive | Tasks execute strictly in order of arrival. | Simple to implement (FIFO queue). | Short processes get stuck behind massive ones. |
| SJF (Shortest Job First) | Non-Preemptive / Preemptive | Picks the process with the shortest CPU burst time next. | Optimal for minimizing average wait time. | Impossible to predict exact burst times in practice; can cause starvation for long jobs. |
| Round Robin (RR) | Preemptive | Gives each process a fixed time quantum (e.g., 10-50ms) before rotating to the next. | Excellent for interactive/time-sharing systems. | High context-switching overhead if time slice is too small. |
| Priority Scheduling | Preemptive / Non-Preemptive | Runs tasks according to allocated priority numbers. | Critical system processes execute first. | Starvation: Low priority processes may never run. (Solved via Aging—gradually raising a process's priority over time). |
| Multilevel Feedback Queue (MLFQ) | Preemptive | Uses multiple queues with different priorities; tasks move down as they consume CPU, or up if I/O bound. | Adapts dynamically to task behavior without needing burst estimates. | Complex setup (requires tuning queue limits and age intervals). |
Key Performance Metrics
Operating systems evaluate scheduling performance using specific targets:
- CPU Utilization: Percentage of time the CPU is actively performing work (Goal: Maximize).
- Throughput: Number of processes completed per unit of time (Goal: Maximize).
- Turnaround Time: Total time from process submission to its completion (Goal: Minimize).
- Waiting Time: Total time a process spends waiting in the ready queue (Goal: Minimize).
- Response Time: Time elapsed between process submission and its first execution response (Goal: Minimize).