CPU Scheduling

This Galvin topic covers scheduling policies. You compute average waiting and turnaround times for FCFS, SJF, priority and Round Robin scheduling, analyse the effect of the time quantum, and understand priority inversion and adaptive multilevel feedback queues.

Relation 1 —

Write this relation with symbols exactly as in Operating System Concepts — Silberschatz, Galvin & Gagne before substituting numbers. Examiners award partial marks for a correct setup even when arithmetic slips.

Relation 2 —

Write this relation with symbols exactly as in Operating System Concepts — Silberschatz, Galvin & Gagne before substituting numbers. Examiners award partial marks for a correct setup even when arithmetic slips.

Relation 3 —

Write this relation with symbols exactly as in Operating System Concepts — Silberschatz, Galvin & Gagne before substituting numbers. Examiners award partial marks for a correct setup even when arithmetic slips.

The scheduler mediates competition for the CPU, and the right policy depends on the goal. FCFS is trivially fair but lets a long job delay everyone behind it (the convoy effect). Shortest-job-first provably minimises average waiting time, but it needs to know or estimate burst lengths and can starve long jobs. Round Robin gives each process a quantum in turn, bounding response time for interactive use — a tiny quantum means responsiveness but heavy context-switch overhead, a huge quantum degenerates toward FCFS. Priority scheduling can invert (a high-priority task waits on a low-priority one holding a lock), which priority inheritance fixes by temporarily boosting the holder.

State assumptions explicitly before using any relation for cpu scheduling — steady state, uniform properties, linear elastic material, ideal gas, incompressible flow, etc., as applicable.

Wrong assumptions invalidate the entire solution even when the formula is correct. In Operating Systems viva and GATE descriptive questions, listing valid assumptions often earns separate marks.

1. Read the question and list given data with SI units (common in Operating Systems papers).
2. Draw a neat labelled diagram where applicable — examiners in Indian universities award diagram marks even when arithmetic slips.
3. Identify which relation from this topic applies to cpu scheduling.
4. Use equation 1: .
5. Use equation 2: .
6. Substitute values, compute, and verify units and sign (direction).
7. State conclusion in one line — e.g. safe/unsafe, stable/unstable, feasible/infeasible.

CPU Scheduling appears in systems software and backend. In Indian it software curricula this topic is tested because it connects theory to process, memory, and file management.

GATE and semester exams often combine cpu scheduling with earlier units — revise prerequisites before attempting mixed problems.

Industry interview panels sometimes ask: "Where did you use cpu scheduling?" — answer with a lab, mini-project, or plant visit example if possible.

Students compute turnaround and waiting time inconsistently (turnaround = completion − arrival; waiting = turnaround − burst), forget arrival times in mixed problems, and pick a Round Robin quantum without weighing context-switch cost. Ignoring starvation risk in SJF and priority scheduling is common.

Before attempting cpu scheduling problems, confirm you can:

1. Preemptive: RR and priority; non-preemptive: FCFS and basic SJF
2. Priority inversion is solved by priority inheritance
3. Multilevel feedback queues adapt to process behaviour

Revise the solved examples in Operating System Concepts — Silberschatz, Galvin & Gagne and one previous-year GATE or university paper for this unit.