Scheduling metrics helps in measuring any scheduling algorithm. The two most important scheduling metrics are: Turnaround Time and the Response Time
- Turnaround Time:
The turnaround of a job is defined as the time at which the job completes minus the time at which the job arrived at the system - Response Time:
The response time is defined as the time when the job arrives in a system to the first time it is scheduled.
Scheduling Algorithm:
A few of the important scheduling algorithm is:
- First Come First Serve(FCFS)
- Shortest Job First(SJF)
- Shortest Time-to-Completion First(STCF)
- Round Robin
- Priority Scheduling
- Multi-Level
First Come First Serve(FCFS):
- This is the most basic algorithm and is also known as First In, First out(FIFO).
- The process which arrives first gets executed first that is the process that requests the CPU first, gets the CPU allocated first.
- It comes under a Non-Preemptive scheduling algorithm that is once scheduled cannot be yielded back until it completes or goes to waiting state seeking for I/O operation.
- It is easy to understand and implement using a queue data structure, where a new process enters through the tail of the queue, and the scheduler selects the process from the head of the queue.
Metric Measurement:
Consider the processes P1, P2, and P3 given in the below table, arrives for execution in the same order, with Arrival Time 0, and given Burst Time.
PROCESS | BURST TIME |
P1 | 10 |
P2 | 10 |
P3 | 10 |
Turnaround Time:
- Turnaround time for the process P1= 10(10 – 0)
- Turnaround time for the process P2= 20( 10 + 10 – 0)
- Turnaround time for the process P3= 30( 10 + 10 + 10)
- Thus Average Turnaround time is = (10 + 20 + 30)/ 3 = 20
Response Time:
- Response time for the process P1 = 0
- Response time for the process P2 = 10
- Response time for the process P3 = 20
- Thus Average Response time is = (0 +10 + 20)/ 3 = 10

Problem with FCFS Scheduling:
- It is Non-preemptive algorithm, which means the process priority does not matter, thus any process can monopolize the CPU.
- Resource utilization in parallel is not possible, which leads to Convoy Effect, and hence poor resource(CPU, I/O) utilization.
What is Convoy Effect?
- Convoy Effect is a situation where many processes, who need to use resources for a very short time are blocked by the process holding the resources for a long time.
- This essentially leads to poor utilization of resources and hence poor performance.
- It increases the turnaround as well as response time or waiting time.
Process | Burst Time |
P1 | 100 |
P2 | 10 |
P3 | 10 |
Metrics measurement:
Turnaround Time:
- Turnaround time for the process P1= 100
- Turnaround time for the process P2= 110
- Turnaround time for the process P3= 120
- Thus Average Turnaround time is = (100 + 110 + 120)/ 3 = 110
Response Time:
- Response time for the process P1 = 0
- Response time for the process P2 = 100
- Response time for the process P3 = 110
- Thus Average Response time is = (0 +100 + 110)/ 3 = 70

Shortest Job First(SJF):
- This algorithm runs the shortest job first, then the next shortest , and so on.
- Even this comes under non-preemptive scheduling algorithm.
Process | Burst Time |
P1 | 100 |
P2 | 10 |
P3 | 10 |

Metric Measurement:
- Turnaround time for the process P1= 120
- Turnaround time for the process P2= 10
- Turnaround time for the process P3= 20
- Thus Average Turnaround time is = (120 + 10 + 20)/ 3 = 50
Response Time:
- Response time for the process P1 = 20
- Response time for the process P2 = 0
- Response time for the process P3 = 10
- Thus Average Response time is = (20 + 0 + 10)/ 3 = 10
The above calculation is based on that each of the process arrives at same time at t =0
Let us assume that the process P1 arrives at t =0 and need to run for 100 seconds, whereas the process P2 ad P3 arrives at t =10 and need to run for 10 seconds.

Metrics measurement:
Turnaround Time:
- Turnaround time for the process P1= 100
- Turnaround time for the process P2= 100(110 – 10)
- Turnaround time for the process P3= 110(120- 10)
- Thus Average Turnaround time is = (100 + 100 + 110)/ 3 = 110.33
Response Time:
- Response time for the process P1 = 0
- Response time for the process P2 = 100
- Response time for the process P3 = 110
- Thus Average Response time is = (0 +100 + 110)/ 3 = 70
Thus even this suffers from same Convoy Effects.
Shortest Time-to-Completion First(STCF)
- This is similar to Short Job First(SJF) but it’s preemptive in nature.
- SJF is a non-preemptive scheduling algorithm.
Process | Burst Time |
P1 | 100 |
P2 | 10 |
P3 | 10 |

Metrics measurement:
Turnaround Time:
- Turnaround time for the process P1= 120
- Turnaround time for the process P2= 10
- Turnaround time for the process P3= 20
- Thus Average Turnaround time is = (120 + 10 + 20)/ 3 = 50
Response Time:
- Response time for the process P1 = 0
- Response time for the process P2 = 0
- Response time for the process P3 = 10
- Thus Average Response time is = (0 + 0 + 10)/ 3 = 3.33
Round Robin Algorithm:
- In this scheduling algorithm, the process is not run till completion, rather a job runs for a time slice(known as time quantum or scheduling quantum or time slicing) and then switches to the next job in the run queue.
- Consider the time quantum to be 1 second
Process | Burst Time |
P1 | 5 |
P2 | 5 |
P3 | 5 |

Metrics measurement:
Turnaround Time:
- Turnaround time for the process P1= 13
- Turnaround time for the process P2= 14
- Turnaround time for the process P3= 15
- Thus Average Turnaround time is = (13+ 14 + 15)/ 3 = 14
Response Time:
- Response time for the process P1 = 0
- Response time for the process P2 = 1
- Response time for the process P3 = 2
- Thus Average Response time is = (0 + 1 + 2)/ 3 = 1
For same processes with same Burst time and with SJF algorithm, the response time would be ( 0 +5 +10) /3 = 5.
What should be length of time slice in RR algorithm?
- The length of time slice is critical in RR. The shorter it is, the better the performance of RR under the response time metric.
- However, making the time slice too short will affect the performance of the system as it increases the context switching overhead.
- And making it too long would decrease the responsiveness of the system.
- Thus RR algorithm is best for response time but at the same time turnaround time of 14 is awful and even worst the simple FIFO( 5 +10 +15 ) /3 = 10.
Priority Scheduling Algorithm:
- In this algorithm, the process is scheduled on the basis of priority.
- The process with the highest priority is scheduled first, then the second highest priority, and so on.
- If the priority happens to be the same, processes are executed on FCFS basis.
- This is again of types: Preemptive Priority Scheduling and Non-Preemptive Priority Scheduling.
- Example: All the processes arrives at the same time t =0
Process | Burst Time | Priority |
P1 | 21 | 2 |
P2 | 3 | 1 |
P3 | 6 | 4 |
P4 | 2 | 3 |

Metric Measurement:
Turnaround Time:
- Turnaround time for the process P1= 24
- Turnaround time for the process P2= 3
- Turnaround time for the process P3= 32
- Turnaround time for the process P4= 26
- Thus Average Turnaround time is = (24 + 3 + 32 + 26)/ 4 = 21.25
Response Time:
- Response time for the process P1 = 3
- Response time for the process P2 = 0
- Response time for the process P3 = 26
- Response time for the process P4 = 24
- Thus Average Response time is = (3 + 0 + 26 + 24 )/ 4 = 13.25
Problem with Priority Scheduling Algorithm:
The process with the lowest priority may be blocked indefinitely or starved in the case higher priority process always pitch in.
Solution- Aging Technique:
- To prevent starvation of any process, we can use the concept of aging where we keep on increasing the priority of low-priority processes based on their waiting time.
- For example, if we decide the aging factor to be 0.5 for each day of waiting, then if a process with priority 20(which is comparatively low priority) comes in the ready queue. After one day of waiting, its priority is increased to 19.5 and so on.
- By doing so, we can ensure that no process will have to wait for an indefinite time for getting CPU time for processing.
Categories: Operating system (OS)
Leave a Reply