Scheduling (OCR A Level Computer Science)
Revision Note
Written by: Callum Davies
Reviewed by: James Woodhouse
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
Preemptive: allocates the CPU for time-limited slots
Non-preemptive: allocates the CPU to tasks for unlimited time slots
Preemptive 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-Preemptive 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)
RR is a pre-emptive 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-preemptive, 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 preemptive 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 understand 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.
Last updated:
You've read 0 of your 5 free revision notes this week
Sign up now. It’s free!
Did this page help you?
