Scheduling: Deciding Which Process Runs Next
A scheduler chooses from the ready processes, and every rule it could use favours something: throughput, response time, or fairness. Round robin, shortest job first and priority with ageing balance those goals differently.
What a learner can do afterwards
- Work out average waiting time for a job set under two different policies
- Show how a low-priority job can starve under strict priority, and explain an ageing scheme that prevents it
- Say which policy suits an interactive machine and which suits a batch one
1 · Read
Waiting time is time ready but not running. Here, all jobs arrive at time 0 on one CPU, each has one burst, and switch cost is ignored. For bursts 8, 6, 4, 2, first-come order gives waits of 0, 8, 14, 18: mean 10. Shortest-job-first (SJF) orders 2, 4, 6, 8 and gives waits of 0, 2, 6, 12: mean 5. Add waits and divide by four. Subtract the means to compare policies.
Round robin gives each ready job a time slice, then moves an unfinished job to the queue's back. A job that finishes early gives up its turn. Response time is time until its first run. For jobs arriving at time 0, total waiting time is completion time minus burst length. With initial queue A, B, C, bursts 5, 3, 1 and slice 2, the timeline below shows how to trace the turns.
For jobs all ready together on one CPU, with known burst lengths and no switch cost, non-preemptive shortest-job-first minimizes average waiting time. It runs each selected job to completion. Real schedulers often estimate the next burst; poor estimates can change the result.
An interactive system often wants ready jobs to receive regular short turns. Round robin can serve that goal when the queue and slice are not too large. A batch system may instead prioritize average waiting time. Shortest-job-first fits the known-burst model, but workload and fairness goals still matter.
Strict priority can leave a low-priority job ready forever if higher-priority work keeps arriving. This is starvation; burst length alone is not the cause. One ageing scheme promotes waiting jobs up bounded priority levels. With first-in, first-out (FIFO) order at the highest level and finite bursts, a job reaching that level eventually gets a turn.
Very short slices can cause many context switches. When switches cost time, that leaves less CPU time for useful work. Longer slices reduce this overhead but can delay other jobs' next turns. A slice choice balances switching cost against responsiveness.
Compare waiting and response separately. SJF's optimum needs stated assumptions; round robin shares turns, and suitable ageing rules prevent starvation.
Original lesson, questions and flashcards about CPU scheduling.
2 · Watch
En anglaisTake it off screen
Where it sits
Optional connections
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.