CPU Scheduling Algorithms

CPU scheduling algorithm deal with the problem of deciding which of the processes in the ready queue is to be allocated the CPU.

Six commonly used scheduling algorithms are :

1. First-Come First-Served Scheduling Algorithm (FCFS)

It is simplest and the most straight forward of all scheduling algorithms.
In this scheduling, the process that requests the CPU first is allocated the CPU first. Thus the name first come first served.
When CPU is free, it is allocated to the process at the head of ready queue. The running process is then removed from the queue.
FCFS scheduling algorithm is non-preemptive. Once the CPU is allocated to a process that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O.

SJF is also known as Shortest-Job-Next (SJN) algorithm and is faster than FCFS.
When the CPU is available, it is assigned to the process that has the smallest next CPU For this, SJF algorithm associates with each process, the length of its next CPU burst.
In SJF, the process with the least estimated execution time is selected from the ready queue for execution. burst.
If two processes have the same length of next CPU burst. FCFS scheduling algorithm used to break the tie.
SJF algorithm can be preemptive or non-preemptive.

In priority scheduling, a priority is associated with all processes.
Process are executed in sequence according to their priority.
The CPU time allocated to the process with highest priority.
If the priority of two or more processes are equal than the process that has been inserted first into the ready queue is selected for execution. In other words, FCFS scheduling is performed when two or more processes have same priority.
The priorities are implemented as a fixed range of numbers such as 0 to 7 or 0 to 4,095.
In some systems, the highest number represents the highest priority. In such cases, processes with priority 7, is executed first.
In other system, a low number indicates a high priority. In that case, a process with priority 0 is executed first.
Priorities can be defined in two ways : internally or externally.

Priority of a process can be defined by the user or an application or by the operating system itself.

Round robin scheduling is similar to FCFS but preemption in added to switch between processes.
In RR scheduling, processes are dispatched in FIFO but are given a small amount of CPU time. This small amount of time is known as time quantum or time slice A time quantum is generally from 10 to 100 milliseconds.
If a process does not complete before its time slice expires, the CPU is preempted and is given to the next waiting process in ready queue.
The preempted process in then placed at the tail of the ready queue.
If a process is completed before its time slice expires, the process itself releases the CPU. The scheduler then proceeds to the next process in ready queue.
Whenever any new process arrives in the system it is added at the tail of the ready queue.
Round-robin scheduling is effective in timesharing environments in which the system needs to guarantee reasonable response time for interactive users.
In this environment the preemption overhead is kept low by efficient context switching mechanisms and by providing adequate memory for the process to reside in main storage at the same time.

Round robin scheduling is always preemptive as no process is allocated the CPU for more than one time quantum in a row. If a process CPU burst exceeds one time quantum then that process is preempted and is put back at the tail of ready queue.

Multilevel Queue Scheduling classifies the processes according to their types. For example, a multilevel queue scheduling algorithm makes a common division between the interactive processes (foreground) and batch processes (background). These two processes have different response times, so they have different scheduling requirements. Also, the interactive process has higher priority than the batch process.
In this scheduling, ready queue is divided into various queues that are called subqueues. A subqueue is a distinct operational queue.
The processes are permanently assigned to subqueues, generally based on some property of the process such as memory size, priority or process type.
Each subqueue has its own scheduling algorithm. For example, interactive processes at the foreground may use round robin scheduling while batch jobs at the background may use the FCFS method.
In addition, there is a scheduling algorithm that works globally between the different subqueues. Usually this is a fixed priority preemptive scheduling. For example, the foreground queue may have absolute priority over the background queue.

However for scheduling between the queues different approach can be used different approaches are to use absolute priority or time slicing.

Multi-level feedback queue scheduling is an enhancement of multi level queue scheduling. In this scheme, processes can move between the different queues.
The various processes are separated in different queues on the basis of their CPU burst characteristics.
If a process consumes a lot of CPU time, it is placed into a lower priority queue. Thus I/0 bound and interactive processes are placed in the higher priority queue and CPU bound processes are in lower priority queue.
If a process waits too long in a lower priority queue it is moved higher priority queue Such an aging prevents starvation.
The top priority queue is given smallest CPU time quantum.
If the quantum expires before the process voluntarily relinquishes the CPU, the process is placed at the back of the next lower queue.
In many multi-level feedback schemes, the quantum given to the process an it moves to each lower level queue becomes larger.

The CPU time quantum given to the various queues usually change by the factor of 2 with each decreasing step in the priority of queue. For example, as shown in figure, process in first queue is given a time quantum of 8 milliseconds, If it does not finishes within this time, it is moved to the tail of next queue. In this queue each process is given quantum of 16 milliseconds.