CPU scheduling formulas

CPU scheduling. 9 formulas for GATE CS Operating Systems, each with when to use it. Each is explained in the topic notes.

All 9 CPU scheduling formulas

TURNAROUND TIME

TAT = CT - AT

Holds for every scheduling algorithm.

WAITING TIME

WT = TAT - BT

Valid when the process has a single CPU burst and does no I/O. With I/O bursts, WT = TAT − (total CPU time) − (total I/O time).

RESPONSE TIME

RT = (time of first dispatch) - AT

In a non-preemptive algorithm, RT equals WT when each process has a single CPU burst and does no I/O.

UTILISATION AND THROUGHPUT

CPU utilisation = \frac{time CPU is busy with processes}{total elapsed time}, Throughput = \frac{n}{total elapsed time}

Total elapsed time runs from time 0 to the last completion unless the question defines it otherwise. Idle gaps and context-switch time count as not busy.

HRRN RESPONSE RATIO

Response ratio = \frac{W + S}{S}

W = time the process has waited so far in the ready queue, S = its burst time. Recompute it at every instant the CPU becomes free.

EXPONENTIAL AVERAGING

τ_{n + 1} = α t_{n} + (1 - α) τ_{n}, 0 \leq α \leq 1

t_n = actual length of the nth CPU burst, tau_n = its predicted value, tau_1 = the given initial guess.

RR TURN BOUND

Gap between two turns of a process \leq (n - 1) q + n s \Rightarrow q \leq \frac{T - n s}{n - 1}

For n processes that all keep using full quanta, with a context switch of s ms between any two processes. The second form is the largest quantum for which every process gets the CPU again within T ms. With s = 0, the k-th process in a queue formed at time 0 first gets the CPU within (k − 1)q.

RR EFFICIENCY WITH SWITCH TIME

CPU efficiency = \frac{q}{q + s}

Valid when every process uses its full quantum q and each dispatch costs a context switch of s ms.

CPU UTILISATION WITH OVERHEADS

Utilisation = \frac{\sum CPU burst times}{\sum CPU burst times + switch time + idle time}

Use when context-switch time and idle gaps are given or can be read from the Gantt chart. The denominator is the total elapsed time.

Where this was asked: 2020 (1), 2022 (1), 2023 (1), 2024 (1), 2025 (2), 2026 (2). See the 8 previous-year questions on CPU scheduling. This shows what was asked, not what will be asked.

KEEP GOING

CPU scheduling: the notes and 8 solved previous-year questions