IB Computer Science Topic A1.3.3: Comparison of Different Approaches to Scheduling Notes

Scheduling: Four Ways to Decide Which Process Gets the CPU Next

1. A single CPU core executes one process at a time, so when ten processes are ready to run, nine of them are waiting.
2. The scheduler decides which one of the ten runs, and for how long, and it makes that decision thousands of times a second.
3. The syllabus names four approaches, and the point of the topic is that none of them wins outright.

Four Metrics Decide Whether a Scheduler Is Doing Well

1. Throughput: the number of processes completed in a given period.
2. Turnaround time: the total time from a process arriving to it terminating.
3. Waiting time: the time a process spends sitting in the ready queue rather than executing.
4. CPU utilization: the percentage of time the CPU spends executing processes rather than idling.
5. A scheduler that improves one metric usually worsens another, which is why the comparison is always about the workload rather than the algorithm alone.

First-Come, First-Served: Simple, and Exposed to the Convoy Effect

1. Non-preemptive: once a process starts, it keeps the CPU until it finishes or blocks on input or output.
2. Simple: the ready queue is an ordinary queue, so the scheduler needs no priorities and no timer.
3. Predictable: a process is never overtaken, so its finish time can be worked out in advance.

Round Robin: Equal Time Slices, Paid For in Context Switches

1. Preemptive: a timer interrupts any process that is still running when its time quantum expires, and it rejoins the back of the queue.
2. Even-handed: every process reaches the CPU within one pass of the queue, so no process waits indefinitely.
3. Responsive: a newly arrived interactive process starts within one pass rather than after every earlier process has finished.
4. The time quantum is the length of one slice, and choosing it is the whole design decision.
   1. Too short a quantum means the CPU spends a large share of its time switching rather than executing.
   2. Too long a quantum means processes run to completion inside their slice, and round robin degenerates into first-come, first-served.

Multilevel Queue: Different Rules for Different Kinds of Process

1. Flexible: each queue can run its own algorithm, so interactive processes get round robin while long background jobs get first-come, first-served.
2. Targeted: a process is placed in a queue by its type, such as system, interactive or batch, rather than by a single number.
3. Complex: the designer must decide how many queues exist, what enters each one, and how CPU time is divided between the queues.
   1. If the lower queues are only served when the higher ones are empty, a background job can wait indefinitely.

Priority Scheduling: Important Work First, and the Starvation That Follows

1. Preemptive or non-preemptive: in the preemptive form a newly arrived high-priority process takes the CPU immediately, and in the non-preemptive form it waits for the current process to finish.
2. Effective for deadlines: work that must complete on time, such as an anti-lock braking calculation, is guaranteed the CPU ahead of everything else.
3. Exposed to starvation: a low-priority process can be overtaken indefinitely while higher-priority work keeps arriving.
4. Aging is the standard fix, raising a waiting process's priority the longer it has waited, so it eventually reaches the front.

One Set of Three Processes, Two Very Different Outcomes

1. Three processes arrive together, needing 24, 3 and 3 milliseconds of CPU time, and the queue order is P1, P2, P3.
2. Under first-come, first-served, P1 runs to completion first, so both short processes wait behind it.
3. Under round robin with a 4 millisecond quantum, P1 is interrupted after 4 milliseconds and the short processes finish early.

1. Round robin cuts the average wait by two thirds without finishing the whole workload any later, because the total CPU time needed is 30 milliseconds either way.
2. The long process pays for it, finishing at 30 milliseconds instead of 24.

Comparing the Four Approaches

1. All four share the same purpose, allocating CPU time so that the processor is kept busy, and all four are implemented by the operating system rather than by the processes themselves.
2. They differ in whether a running process can be interrupted, and in which metric they are willing to sacrifice.

Matching the Algorithm to the Workload

1. First-come, first-served suits batch work where the jobs are of similar length and no user is waiting for a response.
2. Round robin suits time-sharing and desktop systems, where several interactive processes must all feel responsive.
3. Multilevel queue suits general-purpose systems that must serve system tasks, interactive applications and background jobs at once.
4. Priority scheduling suits real-time systems, where a missed deadline is a failure rather than an inconvenience.
5. Scheduling under contention, including deadlock and the cost of context switching, is taken further at HL in A1.3.5.