A1.3.3 — Scheduling

Terms:

• Slice / Quantum: The fixed amount of CPU time allocated to a process per turn.
• Pre-emption: The ability to interrupt a running process and give CPU time to another.
• Fairness: Ensuring all processes get a fair share of CPU time.
• Starvation: When a process is perpetually denied CPU time because higher-priority processes keep running.
• Efficiency: Maximising CPU utilisation and minimising turnaround time and waiting time.

First-Come, First-Served (FCFS)

• Processes are served in the order they arrive.
• Non-pre-emptive — a process runs until it finishes.
• Problem: Convoy effect — short processes get stuck behind long ones, causing poor CPU utilisation and high response times.
• Best for: Simple environments where predictability matters more than responsiveness.

Round Robin

• Each process gets an equal time slice (quantum) in a cyclic order.
• Pre-emptive — after the quantum expires, the process goes to the back of the queue.
• Problem: If quantum is too short → excessive context switching. Too long → behaves like FCFS.
• Best for: Time-sharing systems, interactive applications.

Multilevel Queue Scheduling

• Splits the ready queue into several separate queues, each with its own scheduling algorithm.
• Processes are permanently assigned to a queue based on type (e.g. foreground vs background).
• Problem: Lower-priority queues may suffer starvation. More complex to manage.
• Best for: Systems with different types of processes needing different treatment.

Priority Scheduling

• Each process is assigned a priority. CPU always goes to the highest-priority process.
• Can be pre-emptive (new high-priority process immediately displaces current) or non-pre-emptive.
• Problem: Low-priority processes may starve. Ageing (gradually increasing waiting processes' priority) helps.
• Best for: Real-time systems where critical tasks must always run first.