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