Operating Systems: CPU Scheduling Concepts

Study Notes

Operating Systems 24CSC1031

Course taught by Wessam El-Behaidy, Associate Professor of Computer Science
Main reference: Operating System Concepts, Abraham Silberschatz, 10th Edition

CPU Scheduling

Scheduling is a fundamental operating system function.
Almost all computer resources are scheduled before use.
Multiprogramming loads several processes into memory simultaneously.
Processes transition through various states (running, waiting, ready, etc.) throughout their lifetime.
At any given time, only one process executes per CPU core.
A process scheduler (CPU scheduler) selects the next process for execution on a given core.
The ready queue holds all processes ready to execute in main memory.
The wait queue holds processes waiting for events.
Processes migrate among these queues as their state changes.
Process execution cycles consist of CPU bursts followed by I/O waits.
I/O-bound processes have many short CPU bursts.
CPU-bound processes have a few long CPU bursts.
The final CPU burst ends with a system request to terminate execution.
CPU scheduling decisions are crucial based on the distribution of CPU burst duration.

CPU-Scheduling Components

CPU scheduler (short-term scheduler) selects a process from the ready queue and allocates the CPU.
The dispatcher gives control of the CPU core to the selected process, involving context switching, switching to user mode, and jumping to the appropriate location in the user program.
Dispatch latency is the time it takes for the dispatcher to stop one process and start another.
The dispatcher should be as fast as possible.

CPU Scheduler Decisions

Scheduling decisions occur when a process switches from running to waiting, running to ready (e.g., interrupt), waiting to ready, or terminates.
In situations 1 & 4, a new process (if available in the ready queue) must be selected for execution.
The scheduling scheme can be either nonpreemptive or preemptive.

Nonpreemptive Scheduling

Processes keep the CPU until they release it, either by terminating or switching to the waiting state.

Preemptive Scheduling

In situations 2 & 3, the scheduling scheme is preemptive.
Virtually all modern operating systems use preemptive scheduling algorithms.
Preemptive scheduling can lead to race conditions when data is shared among multiple processes.

Scheduling Criteria

CPU utilization: Keep the CPU as busy as possible (Maximize)
Throughput: Number of processes completed per unit time (Maximize)
Turnaround time: Amount of time to execute a particular process (Minimize)
Waiting time: Time a process spends waiting in the ready queue (Minimize)
Response time: Time from request submission until the first response is produced (Minimize).

CPU Scheduling Algorithms

First-Come, First-Served (FCFS): The simplest algorithm, implemented as a FIFO queue, is nonpreemptive. A notable weakness is potentially long wait times for shorter processes behind longer-running ones, even the "convoy effect" if many I/O processes are competing with a long CPU process.
Shortest-Job-First (SJF): Associates each process with the length of its next CPU burst and schedules the process with the shortest burst. Nonpreemptive. Typically optimal for minimizing average wait. Can be difficult to know length of next CPU burst.
Shortest-Remaining-Time-First (SRT): Preemptive version of SJF.
Round Robin (RR): Preemptive scheduling method that allocates a small time slice (time quantum) to each process in the ready queue. If the process doesn't complete in the time slice, it's moved to the end of the ready queue and a new process takes control of the CPU. Context switching is critical in the function of RR, which impacts performance based on its time quantum setting.
Priority Scheduling: Each process has a priority number; the CPU is allocated to the process with the highest priority.
Can be either preemptive or non-preemptive.
Starvation can be a problem, so techniques like aging help.
Shortest-job-first (SJF) can be implemented with priority scheduling.
Priority scheduling with round robin combines the priority concept with round robin for fairness and reducing starvation risk.
Multilevel queue scheduling and multilevel feedback queue scheduling arrange processes with different priorities on queues of various levels.
Multilevel Queue Scheduling: The ready queue has multiple queues, each with a distinctive priority, and each queue has its own scheduling algorithm.
Multilevel Feedback Queue: Processes can move between queues, and scheduling algorithms need to determine when to promote/demote a process to/from queues.