Scheduling algorithms are programs which allocate processing time of the CPU to processes according to some kind of logic.
In round robin scheduling, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority. It is simple, fair, easy to implement, and free of resource starvation, where programs do not gain access to the resources required for their processing, however means that high priority jobs have to wait in line and the largest job will take a lot of time to complete, and must be calibrated so that the CPU has a high efficiency, but also a high response time.
Multi-Level Feedback Queues
Multi-Level Feedback Queues consist of multiple FIFO queues, which processes can move between:
- A new process is inserted at the end (tail) of the top-level FIFO queue.
- At some stage the process reaches the head of the queue and is assigned the CPU.
- If the process is completed within the time quantum of the given queue, it leaves the
- If the process voluntarily relinquishes control of the CPU, it leaves the queuing
network, and when the process becomes ready again it is inserted at the tail of the same queue which it relinquished earlier.
- If the process uses all the quantum time, it is pre-empted and inserted at the end of the next lower level queue. This next lower level queue will have a time
quantum which is more than that of the previous higher level queue.
- This scheme will continue until the process completes or it reaches the base level queue.
- At the base level queue the processes circulate in round robin fashion until they complete and leave the system. Processes in the base level queue can also be scheduled
on a first come first served basis.
- Optionally, if a process blocks for I/O, it is 'promoted' one level, and placed at the end of the next-higher queue. This allows I/O bound processes to be favoured by the
scheduler and allows processes to 'escape' the base level queue. It allows processes to be allocated the right amount of time they require for completion, but takes more CPU overhead to move items between queues.
- Give preference to short jobs.
- Give preference to I/O bound processes.
- Separate processes into categories based on their need for the processor
First Come, First Served
The First Come, First Served algorithm is based on FIFO (first in, first out) queues, where jobs are executed on first come, first serve basis. It is easy to understand and implement, however it is non-preemptive, meaning programs must run until they finish, and has poor performance due to the long average wait time from processes at the back of the queue.
Shortest Job First
Shortest Job First is an algorithm which provides the best approach to minimising wait time in processes, and can be implemented in systems where the required CPU time is known in advance (i.e. batch systems). However, it is non-preemptive, meaning that processes must wait until they are done, and is impossible to implement in interactive systems, as the required CPU time is not known.
Shortest Remaining Time
Shortest remaining time is similar to shortest job first, but allows programs to be pre-empted, should a shorter job come along. This means that it is more useful in batch environments, as it can prioritise shorter tasks, which need to be given preference in this area. However, it is impossible to implement in interactive systems, as the required CPU time is not known.