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.

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.

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.

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.

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

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

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)