Like humans, the operating system needs to plan its activities. These activities are the various processes that need to be executed by the OS. The OS needs to schedule all its processes properly to ensure that they get executed without any problems and in minimal time.
For these purpose, there are many scheduling algorithms like the First Come First Serve (FCFS) algorithm, Shortest Job First (SJF) algorithm ,etc. We will be discussing these algorithms in detail but before that we need to understand some terms.
- Arrival Time: The time at which the process arrives in the processor for execution.
- Waiting Time : The time for which a process has to wait before it starts executing. A process may have to wait if some other process is being executed (in a uniprocessor environment) or when the resources required by the process are not available, etc. It is calculated as :
Waiting time = Completion Time- Arrival Time- Service Time
3. Service Time/ Burst time : The time required by the process to complete its execution.
4. Turnaround Time : The interval between the time at which the process starts executing and the arrival time of the process. It is calculated using the formula:
Turnaround Time = Service Time + Waiting Time
Now, let us have a look at different scheduling algorithms :
First Come First Serve (Also called FCFS or FIFO or non-Preemptive) algorithm :
In this algorithm, the processes are executed in the order they enter the processor.
Consider the example,
Here, there are 5 processes A,B,C,D,E with their arrival time and service time.
From the given arrival times, we can see that process A is the first one to arrive at 0ms (milliseconds). So that process starts executing.
This is the execution queue. Process A starts executing at 0 and continues till 3 i.e. executes completely. Meanwhile, process B arrives at 2ms and is added to the waiting queue. Note: The value in the brackets ‘()’ denote the service time/burst time required by the process.
Next, process B is removed from the waiting queue and starts executing:
Process B executes till 9ms. Meanwhile processes C,D,E arrive and are added into the waiting queue.
C being first in the queue, starts executing next.
It executes for 4ms. No new process is added to the waiting queue. The next process to be executed is D.
D executes for 5ms from 13 through 18. After that E is the only process left to be executed. So, E executes next.
As you can see all the processes are successfully executed. Now let us calculate the waiting time and the turnaround time using the formulae mentioned above.
These are the results obtained:
So, this is the FCFS algorithm.
It is very simple.
- Favors CPU bound processes over I/O bound processes.
- If a longer process starts executing, the shorter processes have to wait for long which leads to the starvation of the shorter processes.
To overcome this disadvantage, we have the next algorithm.
Shortest Job First/ Shortest Process Next :
In this algorithm, the processes that require the least time for execution are executed first.
Let us first consider
Non-Preemptive Shortest Job First Algorithm :
Lets consider this example:
Process A is the first process to enter the processor. So it starts executing.
B is the only process in the queue now, so , it starts executing. As and when the processes arrive, they are added into the waiting queue.
Now, in the waiting queue, as we can see process E is the process that will require the least time for execution. Hence, process E starts executing.
C being the process requiring the least time starts executing next.
Finally, D starts executing
This is how SJF algorithm works.
Now, lets calculate the waiting and turnaround time.
- No bias for longer processes.
- Improved response time.
- Increased variability hence reduced predictability.
- Processing time of the process needs to be known.
- Possibility of starvation for longer processes.
This waiting and turnaround time can be further improved using the below method:
Preemptive Shortest Job First Algorithm (Shortest remaining time first):
In this method, while a process is executing, if a process requiring lesser service time enters, that process is executed first.
Consider the example:
A being the process to arrive first starts executing first.
Here, process B arrives at 2ms. Already executing process i.e. process A requires 1ms to complete and B needs 6ms which is greater. Hence, A continues execution.
Then B starts executing.
But at 4ms, C enters the queue. B requires 5ms to complete its execution whereas C requires 4ms. Hence, C starts executing and B is added to the queue.
While C was executing, D process entered the queue but since the time required for D to execute was greater than that of process C, processes were not switched.
Now all the processes are either executed or are in the queue. So now the process requiring minimum time for execution will be executed first. i.e. process E.
Now, the queue has process B and D both requiring 5ms. So any process can be executed next.
B entered the queue first hence, we will execute B first.
Now, D is the only process left. Hence, it will get executed next.
Ok, so let us now calculate the average waiting and turnaround time.
- Improved turnaround time and waiting time than preemptive SJF.
- No bias towards longer processes.
- Scheduler must have an estimate of processing time.
- Risk of starvation of longer processes.
- Elapsed service time must be recorded which increases overhead.
Now let us have a look at the next scheduling algorithm.
Round robin algorithm :
In this method, every process is executed for a specific interval or time quantum and after the interval is over the next process to arrive starts executing for the same amount of time.
Lets take an example.
Consider a time quantum of 4ms
A being the first process to arrive starts executing first.
Though the time quantum is of 4ms, A needs 3ms, 1ms less than the time quantum. Hence, it gets completely executed 1ms earlier.
Now since B is the next process, it starts executing.
It executes for 4ms and then the execution stops. The next process i.e. C starts executing and B is put back into the waiting queue.
C process executes for 4ms and executes completely. Meanwhile, process E enters the queue.
Next, process D starts executing.
Process D executes for 4ms whereas its required time was 5ms. Hence, it is added back into queue and the next process to be executed is process B which will execute for 2ms.
Next, process E will be executed for 2ms.
Now, the only process left in the queue is process D. Hence, it will get executed next for 1ms.
In this way, all processes are executed using the round robin method.
Now lets have a look at the average waiting time and turnaround time.
Effective approach in time sharing or transaction processing time.
- Relative treatment of processor bound and I/O bound processes can cause poor performance.
- Inefficient use of I/O devices.
- Increase in variance of response time.
Next, let us have a look at the Priority Scheduling algorithm.
Priority Scheduling Algorithm:
In this algorithm, every process has a specific priority and are executed according to the given priority.
- Non-Preemptive Priority Scheduling Algorithm:
In this algorithm, process of highest priority is completely executed first and then the process with the next highest priority is executed.
Lets take an example:
In the above example, we have 5 processes A,B,C,D,E
Processes A and B enter the processor first. Out of those two process , the process B has a higher priority and hence, process B will be executed first.
Meanwhile, the other processes are added into the waiting queue.
Now, after B completes its execution, the waiting queue is checked. Process D is the process in the waiting queue with highest priority. Hence, it is executed next.
Similarly, now from the queue, process E has the highest priority and is therefore executed.
Again, considering the priority, process C is executed….
followed by the process A.
Now, let us calculate the average waiting time and turnaround time.
The processes of higher priority get preference and are made to execute earlier.
The processes with lower priority may suffer starvation.
2. Preemptive Scheduling Algorithm:
In this algorithm, if a process with priority higher than that of the process being executed enters, the processor is preempted and that process starts executing.
Here at 0ms processes A and B enter the system. B being the process with highest priority starts executing first….
..but as process D enters the processor, since D has a higher priority, it starts executing next and B is added to the queue.
Now after D completes executing, (D gets completely executed as no other process with higher priority enters in between) B being the process with the highest priority starts executing next.
Next, the process E starts executing
Then, process C starts executing
And finally, process A starts executing
Now, let us calculate the average waiting time and turnaround time
The advantage of this algorithm is that the processes with higher priority do not have to wait, hence they are not starved.
Let us see the next algorithm
Highest Response Ratio Next Algorithm:
In this, for execution, we select the process that has the highest response ratio.
Response Ratio =( Waiting Time + Service Time ) / Service time
Let us understand this using an example:
Here, process A is the only process to enter the processor and hence it starts executing. Meanwhile, B enters the queue.
Now, since B is the only process to enter the queue, it starts executing next.
Now comes the trickier part.
There are three processes — C,D,E in the queue. How do we decide which one to select out of these?
Its very easy! We calculate the response ratio for each of them using the formula mentioned earlier.
As you can see, C has the highest response ratio. Hence it will be executed next.
Now we have to make a choice between process D and E. Let us calculate the response ratio for these processes.
Since E has the highest response ratio, it is executed next.
Now the only process left is D. Hence, it will be executed finally.
Let us now calculate the average waiting time and turnaround time for this example:
This is how processes are scheduled using Highest Response Ratio algorithm.
Here, the disadvantage is that extra calculation is required. Also the service time has to be known and the waiting time has to be tracked.
So, these are some of the scheduling algorithms in OS.
All of these can be compared and the one that best suits our requirement can be used.
Hope this helps you!
Have a nice day!!