scheduling

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)

• In A Level Computer Science, RR 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