Scheduling

What is scheduling?

• Deciding which tasks to process, for how long, and in what order is achieved through scheduling algorithms
• A CPU is responsible for processing tasks as fast as possible
• Different algorithms are used to prioritise and process tasks that need CPU time
• The algorithms have different uses, benefits and drawbacks

Scheduling categories

• Pre-emptive: allocates the CPU for time-limited slots
• Non-pre-emptive: allocates the CPU to tasks for unlimited time slots

Pre-emptive scheduling

• Allocates the CPU for a specific time quantum to a process
• Allows interruption of processes currently being handled
• It can result in low-priority processes being neglected if high-priority processes arrive frequently
• Example algorithms include Round Robin and Shortest Remaining Time First

Non-pre-emptive scheduling

• Once the CPU is allocated to a process, the process holds it until it completes its burst time or switches to a ‘waiting’ state
• A process cannot be interrupted unless it completes or its burst time is reached
• If a process with a long burst time is running, shorter processes will be neglected
• Example algorithms include First Come First Serve and Shortest Job First

Scheduling algorithms

Round robin (RR)

• Round Robin is a pre-emptive scheduling algorithm
• Equally distributing processor time amongst all processes
• Each process is given a time quantum to execute
• Processes that are ready to be worked on get queued
• If a process hasn’t been completed by the end of its time quantum, it will be moved to the back of the queue

Round robin scheduling algorithm

First-come-first-served (FCFS)

• FCFS is non-preemptive, prioritising processes that arrive at the queue first
• The process currently being worked on will block all other processes until it is complete
• All new tasks join the back of the queue

First-Come-First-Served scheduling algorithm

Multi-level feedback queue (MLFQ)

• MLFQ is a pre-emptive priority algorithm where shorter and more critical tasks are processed first
• Multiple queues are used so that tasks of equal size are grouped together
• All processes will join the highest priority queue but will trickle down to lower priority queues if they exceed the time quantum

Multi-Level Feedback Queue scheduling algorithm

Shortest job first (SJF)

• SJF is non-pre-emptive, where all processes are continuously sorted by burst time from shortest to longest
• When new processes arrive on the queue, they are prioritised based on their burst time in the next cycle
• Shorter jobs are placed at the front of the priority queue
• Longer jobs have lower priority, so they are placed at the back

Shortest job first scheduling algorithm

Shortest remaining time first (SRTF)

• SRTF is a pre-emptive version of SJF, where processes with the shortest remaining time are higher priority
• Time quantum is set, and if a task doesn’t complete in time, it will be re-queued for further processing
• Before the next cycle starts, all processes are inspected and ordered by the shortest remaining time to complete

Shortest remaining time first scheduling algorithm

Comparison and summary of scheduling algorithms

Algorithm	Benefits	Drawbacks
Round Robin	- All processes get a fair share of the CPU - Good for time-sharing systems Predictable, as every process gets equal time	- Choosing the right time quantum can be difficult - This can lead to a high turnaround time and waiting time for long processes
First Come, First Served	- Simple and easy to implement - Fair in the sense that processes are served in the order they arrive	- This can lead to poor performance if a long process arrives before shorter processes - High-priority tasks wait for their turn in the queue
Multi-Level Feedback Queues	- Smaller tasks are prioritised - Creates a prioritisation system where similar-sized tasks are queued together	- More complex than other algorithms - Setting the correct parameters (e.g., number of queues, ageing rules) can be complex
Shortest Job First	- Minimises waiting time - Efficient and fast for short processes	- Requires knowing the burst time of processes in advance - Long processes can starve if short processes keep arriving
Shortest Time Remaining	- Ideal for jobs that have shorter burst times - It is preemptive, so it can be aligned with CPU for best performance (time quantum)	- Like SJF, it requires knowing the burst time of processes in advance - High context switching overhead due to preemption

• The suitability of a scheduling algorithm largely depends on the specific scenario and the system requirements
• A drawback in one scenario may not be a drawback in another

Worked Example

A company makes anti-virus software. When running anti-virus software, an operating system uses a scheduling algorithm to allocate CPU time to the anti-virus software.

Explain why a First Come First Served scheduling algorithm would not be suitable in this situation.

[2]

How to answer this question:

• Think of the conditions that anti-virus software runs optimally
• Recall the way the FCFS algorithm works and its benefits and drawbacks
• Link how the optimal running of anti-virus is incompatible with FCFS scheduling

Answer:

Example answer that gets full marks: Anti-virus software is high-priority because it scans the operating system constantly, looking for threats. When a threat is detected, anti-virus will quarantine or eliminate them. To work effectively, anti-virus software needs high-priority access to CPU time.

Using FCFS could delay these critical tasks if many other processes are in the queue ahead of the anti-virus software. Other less crucial tasks could get CPU time before the anti-virus process, leading to potential security risks.

Acceptable answers you could have given instead:

The FCFS algorithm is unsuitable because essential antivirus processing would be placed at the back of the queue and wait for its turn. Lower-priority tasks would use valuable CPU time, meaning the system could be at risk.