You can skip the intro if you've gone through the Part - 1
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 this 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
- Service Time/ Burst time: The time required by the process to complete its execution.
- 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
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 :
Let's 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 to 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 the SJF algorithm works.
Now, let's calculate the waiting and turnaround time.
Advantages :
No bias for longer processes.
Improved response time.
Disadvantages :
Increased variability hence reduced predictability.
The 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, the 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 processes 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.
Advantages :
Improved turnaround time and waiting time than preemptive SJF.
No bias towards longer processes.
Disadvantages :
The scheduler must have an estimate of processing time.
Risk of starvation of longer processes.
Elapsed service time must be recorded which increases overhead.
In the next part, we'll see the Round Robin Algorithm.
Hope this helps you!
Have a nice day!!
Top comments (0)