Scheduling algorithms
How the system picks the process that gets the processor: first come, shortest first, round robin, priorities; computing waiting and turnaround times, and recognising starvation and a badly chosen quantum.
- 38 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- On the timeline
- The numbers
- Scenarios
A few cards from the deck
Preemption: what is it?
Show the answer
The system's right to take the processor away from a process that has not finished, in order to give it to another.
Without it, a process stuck in a loop keeps the processor for good. With it, the arrival of a shorter or higher-priority process (SRTF, preemptive priority) or the end of the quantum (round robin) triggers the switch.
Three processes: P1 (arrival 0, duration 5), P2 (arrival 1, duration 3), P3 (arrival 2, duration 1). With shortest remaining time first, which finishes first, and when?
- P3, at time 3
- P1, at time 5
- P2, at time 4
- P3, at time 6
Show the answer
P3, at time 3
P1 starts at 0. At 1, P2 (3) is shorter than P1's remainder (4): it takes the processor. At 2, P3 (1) is shorter than P2's remainder (2): it runs and ends at 3. Then P2 ends at 5 and P1 at 9.
In first come first served, a long process at the head makes all the short ones behind it wait: this is the … effect.
Show the answer
In first come first served, a long process at the head makes all the short ones behind it wait: this is the convoy effect.
With durations 24, 3 and 3 all arriving together in that order, the mean waiting time is 17; in the order 3, 3, 24 it falls to 3.
Quantum: what is it?
Show the answer
The maximum time a process holds the processor before going to the back of the queue, in round robin.
Too short and the processor spends its time switching processes; too long and round robin behaves like first come first served and response gets slow.