Scheduling metrics and algorithm

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):

  • 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.

PROCESSBURST TIME
P110
P210
P310

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
The GANTT chart above perfectly represents the waiting time for each process.

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.
ProcessBurst Time
P1100
P210
P310

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.
ProcessBurst Time
P1100
P210
P310

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
P1100
P210
P310

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
ProcessBurst Time
P15
P25
P35

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
ProcessBurst TimePriority
P1212
P231
P364
P423

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)

1 reply

Trackbacks

  1. Index of Operating System - Tech Access

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: