Scheduling Algorithms in Operating System

Scheduling Algorithms in Operating System:

Below is a list of some well known scheduling algorithms:

First Come First Served (FCFS) Scheduling - non-preemptive.
Shortest Job First (SJF) Scheduling - preemptive or non-preemptive.
Priority Scheduling - preemptive or non-preemptive.
Round Robin Scheduling - preemptive.

Each scheduling algorithm has its own criteria to choose the next job that will run on CPU. Since CPU scheduler needs to be fast, actual algorithms are typically not very complex.

Timelines

Scheduling is based on the information that is available at a given time. We need some way to represent the state of the system and any processes in it and how it changes over time. Gantt chart are used for this purpose. A Gantt chart is basically a glorified timeline that is used to depict the order of process execution graphically. Below is an outline of a Gantt chart:

Gantt chart

First process name

Second process name

More processes

1. First Come First Served Scheduling:

First Come First Served is the simplest CPU scheduling algorithm. It says that the process that enters first should get. FCFS algorithm is easy to understand. It is basically a queue like those we see in banks/ shops, etc.
A drawback of the FCFS algorithm is that the processes may have to wait for excessively long amounts of time.

Example 1

Suppose that there are three processes that arrive in the order shown below. They all arrive at time 0, but the system has decided to serve them in this order.

Process Name	Start time	Burst time
Process 1	0	24
Process 2	0	3
Process 3	0	3

If the processes are served in FCFS order i.e. process 1, then process 2, and finally process 3, then the Gantt chart would look like this:

Gantt Chart for FCFS Example 1

Process 1

Process 2

Process 3

Process 1 is dispatched first and runs for 24 time units (there is no preemption). Once process 1 has finished, process 2 is dispatched and runs for 3 time units. 24 time units have already elapsed, so process 2 starts at time 24. Once process 2 has finished at time 27, process 3 is dispatched. When process 3 has finished there have been 30 time units used (24 + 3 + 3).

The waiting time for a particular process can be measured by taking its finish time and subtracting the burst time and its arrival time.

The following table shows the waiting time for each process:

Process name	Arrival time	Burst time	Finish time	Waiting time
Process 1	0	24	24	0
Process 2	0	3	27	24
Process 3	0	3	30	27

Waiting time = Finish time - burst time - arrival time

The average waiting time for a whole set of processes can be calculated by adding all the individual waiting times and dividing by the number of processes. In the above example, the average waiting time is: (0 + 24 + 27) / 3 = 17.

Example 2

The waiting time is obviously dependent on the order in which the processes are served. Since it was mentioned that all three processes arrive at time 0, the system could have chosen to dispatch them in the following order:

Gantt chart for FCFS example 2

Process 2

Process 3

Process 1

The waiting times for the processes in example 2 are:

Process name	Arrival time	Burst time	Finish time	Waiting time
Process 1	0	24	30	6
Process 2	0	3	3	0
Process 3	0	3	6	3

The average waiting time for the 3 processes in example 2 is (6 + 0 + 3) /3 = 3.

There is a huge difference between the average waiting times in example 1 and example 2, even though the same three processes are being executed. Since FCFS is not preemptive, it is not a good scheduling algorithm for systems where response time is important (i.e. real time or time sharing systems).

2. Shortest Job First Scheduling:

Another way to schedule jobs is to pick the job that will take the least amount of time to complete. In FCFS scheduling, the average waiting time could be reduced by running the short jobs first. The SJF scheduling algorithm picks the shortest job in terms of burst size and places it on the CPU.

There are two possible schemes of this algorithm:

Non-preemptive - Once the CPU is given a process it cannot be. preempted until the current CPU burst finishes.
Preemptive - If a new process arrives with a shorter CPU burst than the remaining CPU burst of the currently executing process, then it replaces the currently executing process. It is also known as Shortest Remaining Time First.

Shortest Job First scheduling is provably optimal. It gives the minimum average waiting time for a given set of processes. If you run all the short jobs first, then each subsequent job has a relatively short waiting time. If you were to run-all the long jobs first, then every subsequent job would have a longer time to wait.

a. Non-Preemptive SJF Example:

In the following example there, are four processes.

Process name	Arrival time	Burst time
Process 1	0	7
Process 2	2	4
Process 3	4	2
Process 4	5	4

The arrival times in this example are important. Since there is only 1 process available at time 0 i.e. Process 1, it is by default the shortest process.
At time 2, process 2 arrives but process 1 is already running. There is no preemption, so even though process 2 is now the shortest it has to wait until process 1 finishes.
At time 4, process 3 arrives that is the shortest but process 1 has still not finished.
At time 5, process 4 arrives and process 3 is still the shortest. When process 1 finishes, then process 3 will run because it is the shortest.
When process 3 finishes, process 2 will run. It has the same length as 4, but arrived earlier so we will choose it.
Finally process 4 will run.

Gantt Chart for SJF Example 1

Process 1

Process 3

Process 2

Process 4

The waiting times for the processes in this example are:

Process name	Arrival time	Burst time	Finish time	Waiting time
Process 1	0	7	7	0
Process 2	2	4	13	7
Process 3	4	2	9	3
Process 4	5	4	17	8

The average waiting time is: (0 + 9 + 3 + 8) / 4 = 5

b. Preemptive SJF example:

In the following example there are again four processes. Note that process 3 now has a burst time of 1.

Process name	Arrival time	Burst time
Process 1	0	7
Process 2	2	4
Process 3	4	2
Process 4	5	4

The arrival times in this example are important. Since there is only 1 process available at time 0 i.e. Process 1, it is by default the shortest process.
At time 2, process 2 arrives, but process 1 is already running. However, there is preemption, so even though process 1 is already running, it is removed from the CPU and replaced with process 2.
At time 4, process 3 arrives that is now the shortest and it replaces process 2 on CPU.
At time 5, process 3 finishes and process 4 arrives. Process 2 is once again the shortest and it gains the CPU, running until time 7.
At time 7 process 4 is the shortest and runs until time 11.
Finally, process 1, which is the only process left, is now the shortest and finishes.

Gantt chart for SJF example 2

Process 1

Process 2

Process 3

Process 2

Process 4

Process 1

The waiting times for the processes in this example are:

Process name	Arrival time	Burst time	Finish time	Waiting time
Process 1	0	7	16	9
Process 2	2	4	7	1
Process 3	4	1	5	0
Process 4	5	4	11	2

The average waiting time is: (9 4-1 + 0 + 2) / 4 = 3

3. Priority Scheduling:

Another way to schedule jobs is to pick the job that has the highest priority. This requires that each process should have a priority associated with it. The priority is generally an integer with some well-defined range e.g. 1 to 10. The CPU is allocated to the process with the highest priority. In some systems, smaller numbers mean higher priority, in other systems larger numbers mean higher priority.

Priority scheduling can either be non-preemptive or preemptive. If there is preemption then a high priority job can remove a low priority job from the CPU and take over.

a. Non-Preemptive Example:

Process name	Burst time	Priority
Process 1	10	3
Process 2	1	1
Process 3	2	3
Process 4	1	4
Process 5	5	2

Assume that all processes arrived at time 0. First of all, Process 2 will get the CPU as it has the highest priority 1 and will finish. Then Process 5 will start execution. In non-preemptive priority scheduling, once a process gets the CPU, it will finish its work and then release the CPU.

Gantt chart for Non-preemptive Priority Scheduling:

Process 2

Process 5

Process 1

Process 3

Process 4

The average waiting time is: (1 + 6 + 16 + 18 + 19) / 5 = 8.2

b. Preemptive Example:

Process name	Arrival time	Burst time	Priority
Process 1	0	10	3
Process 2	2	1	1
Process 3	4	2	2
Process 4	6	1	4
Process 5	8	5	5

In the above example the execution takes place in the following sequence:

Process 1 arrives at time 0 and starts execution, as there is no other process.
At time 2, Process 2 arrives with higher priority, so Process 1 will be preempted and Process 2 will get the CPU and run to the completion using one unit of time at time 3.
At this point, there is again only one Process 1, which resumes and gets the CPU.
At time 4, Process 3 arrives with higher priority than Process 1 and gets the CPU and completes its execution.
At time 6, Process 4 arrives with priority 4. Now there are two processes i.e. Process 1 and Process 4. So, Process 1 continues using CPU.
At time 8, the last process arrives with a priority 5. Process 1 is still a high priority process, so it will run the completion.
As PI releases the CPU after completing its job, it will be assigned to P4, which will
execute completely.
In the end, P5 will get the CPU.

Gantt Chart for Preemptive Priority Scheduling

Process 1

Process 2

Process 1

Process 3

Process 1

Process 4

Process 5

Shortest Job First scheduling is also a form of priority scheduling. In the case of Shortest Job First scheduling, the priority is defined as the predicted next CPU burst.

One major problem with Priority based scheduling is that it may not be fair. Some low priority processes may not ever, get the chance to execute because higher priority processes keep stealing the CPU. One solution to this problem is to implement aging. The process of increasing the priority of a process as it gets older is known as aging.

4. Round Robin Scheduling:

Another way to schedule jobs is to assign a small amount of time to each process in which it executes. This small time unit is usually called the time quantum or time slice. The job is allocated to CPU for the time quantum. When the time quantum expires, the process is preempted from the CPU and replaced by the next process in the circular queue.

Example:

Process name	Burst time
Process 1	24
Process 2	3
Process 3	3

Gantt chart for Round-Robin Scheduling:

Process 1

Process 2

Process 3

Process 1

Process1

Process 1

Process1 gets the first 4 units of time. It requires another 20 units so it is preempted after the first time quantum. CPU is given to Process2 that does not require 4 units. It quits before its time quantum ends and CPU is given to Process3. Once each process has got one time quantum, CPU is given to Process1 for additional time quantum. Average turnaround time is 47/3 = 16.

Round Robin algorithm does not allocate CPU to any process for more than one time quantum in a row. If CPU burst exceeds time quantum, it is preempted and placed in the ready queue. That is why Round Robin is called preemptive scheduling algorithm.

The Round Robin scheduling algorithm will be similar to FCFS if the time quantum is very large. If the time quantum is larger than the largest CPU burst for all of the processes, then no process will be preempted. If the time quantum is made too small, then the context switch will take too much time. It is required when preempting one process from the CPU and replacing it with another.

5. Multi-Level Queue Scheduling:

The previous scheduling algorithms have treated different kinds of process in the same fashion. We typically make a distinction between foreground (interactive) processes and background (non-interactive) processes. Interactive processes generally require much faster response times than non-interactive processes. We can separate these two types of processes and schedule them separately. We probably want to schedule interactive processes more quickly than non-interactive ones.

We could split the ready queue into different sub-queues. One sub-queue is for each type of process that we have identified. An example of a 5 level queuing strategy (0 has highest priority, 4 has lowest) is shown below:

1. System processes
2. Interactive processes
3. Interactive editing processes
4. Batch processes
5. Student processes

When a process enters the system, it is automatically identified as a certain type of process and allocated to the correct queue. There is no way to change queues once a process has been allocated to a queue.

We have five queues in the above example. We must not only schedule individual jobs, but also the 5 queues themselves. There are two schemes to schedule the queues.

Fixed (Absolute) Priority

In this scheme, jobs are first serviced from queue 1. If there is no job in queue 1, then the jobs in queue 2 are serviced. Similarly, jobs in queue 3 are serviced only if there are no jobs in queues 1 or 2, and so on.

Time Slice

In this scheme, each queue gets a time slice i.e. the queues themselves are in a Round Robin queue. Jobs in each queue are executed for the specified amount of time. Then, the control is transferred to the next queue.

6. Multi-Level Feedback Queue Scheduling:

The main difference between a multi-level queuing strategy and a multi-level feedback queuing strategy is that jobs may move from one queue to another over time. It is possible to implement aging this way i.e. if a process stays in one queue too long, it moves up to the next higher priority queue.
The multi-level feedback queue strategy is defined by the following parameters:

Number of queues
Scheduling algorithm for each queue
Method used to determine when to upgrade a process
Method used to determine when to demote a process
Method to determine the queue a process will enter when that process needs service