CPU scheduling

The CPU scheduler picks one process from the ready queue whenever the CPU becomes free or a preemption happens. A schedule is judged by a few standard measures. Convention used in these notes: time is in milliseconds and the Gantt chart starts at time 0. When two processes tie on the selection key (equal burst in SJF, equal remaining time in SRTF, equal priority), the one that arrived earlier wins. If they also arrived at the same instant, the one with the smaller index wins. In a preemptive algorithm, the running process is preempted only by a process that is strictly better. In round robin, a process that arrives at the same instant a running process is preempted joins the queue first, ahead of the preempted process. Always follow the rule a question states over these defaults.

FCFS (first come, first served) serves processes in order of arrival. It is non-preemptive and simple, but one long process delays all the short ones behind it. This is the convoy effect.

Take three processes arriving together at time 0 in the order P1, P2, P3 with bursts 24, 3 and 3. FCFS gives waiting times 0, 24 and 27, so the average is 17. Running them in the order P2, P3, P1 gives 0, 3 and 6, an average of 3. The work is the same; only the order makes the average so much worse.

SJF (shortest job first, non-preemptive): whenever the CPU is free, choose the ready process with the smallest burst time. When all processes are available at the same time, SJF gives the minimum average waiting time of any schedule. With different arrival times this guarantee no longer holds for non-preemptive SJF. Its drawbacks: burst times must be known (or predicted) in advance, and a long process can starve if short ones keep arriving.

Priority scheduling: each process has a priority, and the CPU goes to the highest-priority ready process. Unless a question says otherwise, these notes take a smaller number to mean higher priority; always read the statement. In the non-preemptive form, a newly arrived higher-priority process waits for the running one to finish. Low-priority processes may starve. The cure is ageing, which gradually raises the priority of a process the longer it waits. SJF is priority scheduling where the priority is the inverse of the (predicted) next CPU burst.

HRRN (highest response ratio next) is non-preemptive. Whenever the CPU is free, it computes for every ready process the response ratio below and runs the process with the largest ratio. Short jobs get a high ratio quickly, and a long job's ratio grows the longer it waits, so HRRN favours short jobs without starving long ones.

Predicting the next CPU burst. SJF and SRTF need burst lengths that are not known in advance. The usual estimate is the exponential average of the measured bursts. With $\alpha =0$ the prediction never changes; with $\alpha =1$ it equals the last actual burst. Expanded, ${\tau }_{n+1}=\alpha t_n+(1-\alpha )\alpha t_{n-1}+\cdots +(1-\alpha {)}^{n-1}\alpha t_1+(1-\alpha {)}^n{\tau }_1$, so older bursts carry geometrically smaller weight.

SRTF (shortest remaining time first) is the preemptive form of SJF. Whenever a process arrives, compare its burst with the remaining time of the running process. If it is strictly smaller, the running process is preempted. For a given set of processes with known arrival and burst times, and ignoring context-switch overhead, SRTF gives the minimum average waiting time (and average turnaround time) of any scheduling algorithm. Long processes may starve.

Preemptive priority works the same way with priorities: a newly arrived process whose priority is strictly better than the running one takes the CPU. If the priorities are equal, the running process continues unless the question says otherwise. Without ageing, priorities do not change while processes wait, so decisions are needed only at arrivals and completions.

LJF (longest job first, non-preemptive) and LRTF (longest remaining time first, its preemptive form) are the mirror images of SJF and SRTF: they pick the largest burst or remaining time. Under LRTF the remaining times often become equal, so the tie rule a question states decides the Gantt chart. Apply it at every tie, including a tie with the running process.

Round robin (RR) is FCFS with preemption by a timer. The ready queue is a FIFO. The process at the head is dispatched for at most one time quantum $q$. If it needs more, it is preempted and goes to the back of the queue. If it finishes or blocks earlier, the next process starts at once. RR is designed for time-sharing: every process gets a turn within a bounded time, and there is no starvation.

Multilevel queue (MLQ): the ready queue is split into separate queues, for example system, interactive and batch processes. Each process is permanently assigned to one queue, and each queue has its own algorithm (say RR for interactive, FCFS for batch). The queues themselves are scheduled either by fixed priority or by time-slicing among queues (for instance 80% of CPU time to one queue and 20% to another). Under fixed priority, a lower queue runs only when all higher ones are empty, so starvation is possible.

Multilevel feedback queue (MLFQ) lets a process move between queues. A typical design: queue 0 is RR with a small quantum, queue 1 is RR with a larger quantum, and the last queue is FCFS. A new process enters queue 0 and is demoted to the next queue if it does not finish within its quantum. A process that waits too long in a low queue may be promoted, which is ageing. CPU-bound processes sink to the lower queues, and I/O-bound processes stay in the upper ones.

A context switch saves the state of one process and loads another. It is pure overhead: the CPU does no useful work during it. Default in these notes: when a switch time $s$ is given, add $s$ to the timeline each time the CPU moves from one process to a different one. Do not add it at time 0, at the end, or when the same process continues. Some questions also charge a switch at the start, at the end, or after an idle gap. When a question states its own rule, follow it. Idle time is time when no process is ready; the CPU waits until the next arrival or I/O completion.

A process alternates between CPU bursts and I/O bursts. An I/O-bound process has many short CPU bursts; a CPU-bound process has few long ones. Favouring short CPU bursts, as SJF, SRTF and MLFQ do, tends to keep the I/O devices busy while long CPU work fills the gaps, and improves response for interactive processes.

For a process with I/O bursts, time spent doing I/O is not waiting time. Build the timeline: after a CPU burst the process goes to its I/O for the stated time, then rejoins the ready queue as if it had just arrived. Unless the question says that processes share one I/O device and must queue for it, assume each process's I/O overlaps freely with the others. Count waiting time only while a process sits in the ready queue.