FIT2100 Chap.6 CPU Scheduling and Performance
CPU Scheduling and Performance
CPU scheduling chooses among ready processes. The policy must first respect eligibility: a process cannot be selected before arrival or while blocked. Non-preemptive policies let a selected burst finish or block, while preemptive policies create additional decision points. FCFS, shortest-job variants, round robin, priority, lottery and fair-share policies serve different goals.
Calculations begin with a timeline.
Completion is read from the final segment. Turnaround equals completion minus arrival, and normalised turnaround divides by service. Throughput counts completions over time, while response asks how quickly a request first receives service. Policy quality depends on whether the system is batch, interactive, real time or shared among users.
What this chapter covers
- 01
Scheduling decision points
- 02
Preemptive and non-preemptive policies
- 03
FCFS
- 04
Shortest job policies
- 05
Round robin and quantum
- 06
Priority and fairness
- 07
Turnaround metrics
- 08
Response and throughput
Worked example · free
Compute an FCFS schedule
- +2Timeline: A runs 0 to 5, B runs 5 to 7, and C runs 7 to 10 because FCFS preserves ready-queue arrival order.
- +2Completion times are A = 5, B = 7 and C = 10, read from the end of each final execution segment.
- +2Turnaround values are 5 − 0 = 5, 7 − 1 = 6 and 10 − 4 = 6.
- +2Mean turnaround is (5 + 6 + 6) / 3 = 5.67 time units after final rounding.
Key terms
- Preemptive Scheduling
- A policy style that may interrupt a running process and assign the processor to another eligible process.
- FCFS
- A non-preemptive policy that serves ready processes in arrival order.
- Round Robin
- A preemptive policy that gives each ready process a time quantum before unfinished work returns to the queue.
- Turnaround Time
- Completion time minus arrival time for one process.
- Response Time
- The delay between a request or arrival and its first visible service.
- Throughput
- The number of jobs completed per unit of elapsed time.
CPU Scheduling and Performance FAQ
Which scheduling algorithm is best?
There is no universal winner. Batch systems value throughput and turnaround, interactive systems value response, and real-time systems care about deadlines. A recommendation must name the workload objective and discuss fairness or overhead.
Why does quantum length matter?
A short round-robin quantum can improve initial response but increases context-switch frequency. A long quantum reduces switching overhead but behaves more like FCFS. The useful balance depends on burst lengths and switch cost.
How is turnaround different from waiting?
Turnaround measures the full interval from arrival to completion and includes service time. Waiting measures time spent eligible but not executing. In a simple CPU-only model, waiting can be derived as turnaround minus service.
What causes the convoy effect?
Under FCFS, a long process at the front can delay many short processes behind it. The schedule may be easy to implement and fair by arrival order while producing poor mean turnaround for the queued work.
Assessment move
Always draw the timeline before filling a metric table. Mark arrivals and every preemption point, then verify that no process runs before eligibility. Keep exact turnaround and normalised values until the final requested rounding. Compare policies on one workload, then change the workload and notice how the recommendation changes.
During a demonstration, print queue order and decisions so the result can be defended rather than guessed from final completion output. Start every scheduling problem with an event line containing arrivals, completions, quantum expiries and any decision points authorised by the policy. Above each point, list only eligible processes and the information the scheduler is allowed to use.
Draw CPU segments next, then derive completion, turnaround, waiting and response rather than guessing metrics directly from the input table. Use the conservation check that executed segment lengths equal total service demand when switch overhead is excluded. Recalculate one workload under FCFS, shortest job, shortest remaining time and round robin, keeping the same tie rule.
Explain not just which mean is smaller but which jobs benefit, which wait longer and what starvation or overhead risk appears. Vary one arrival or service time to see whether the ranking changes. For round robin, test two quantum sizes and count switches as well as response. For priority scheduling, state whether priority is static, whether arrivals preempt and how ageing affects a long waiter.
In lab output, log simulation time, ready queue and the reason for each selection. A final completion list is insufficient because different faulty paths can produce similar averages; the decision trace is the evidence that the policy was implemented as specified.
Working through CPU Scheduling and Performance in FIT2100? Sia is AskSia’s AI Computer Science tutor — ask any FIT2100 CPU Scheduling and Performance question and get a clear, step-by-step explanation grounded in how FIT2100 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
