Question 10: Job Scheduling

10. A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero(the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?

 (A) This algorithm is equivalent to the first-come-first-serve algorithm.
 (B) This algorithm is equivalent to the round-robin algorithm.
 (C) This algorithm is equivalent to the shortest-job-first algorithm.
 (D) This algorithm is equivalent to the shortest-remaining-time-first algorithm.

Answer : (B)

Explanation:

Two important things to note.

1. Process Priority is proportional to waiting time.
2. Re-evaluation happens after every T time units.

 When all processes arrive at time zero, algorithm randomly picks one of the processes Pi because all processes have priority 0. Once Pi gets executed for T time unites, re-evaluation happens. Now, priority for Pi would be 0 and all other priority would be proportional to T ( I will just call the priority as T). Now, scheduler randomly picks one of the remaining processes other than Pi. Lets assume Pj. After another T, priority for Pi would be T and Pj would be T, and for rest of them it would be 2T. Now, scheduler picks up another remaining tasks.

Assuming all processing need sufficiently large amount of time, After N*T time units, all processes have waited for (N-1)*T time units and they become equal again -- and again, same Pi would be chosen. You could clearly see that, it is following a round robin aproach i.e., P1, P2, P3, ... , PN then back to P1, P2....

The algorithm no where considers the length of the job or the remaining time of the job. It also does not matter who came first as well. So, clearly answer is B.

Example Based Approach
Lets consider 4 jobs with running times of 7, 8, 6, 5 (you can assume any random numbers). Lets name them as P1, P2, P3 and P4 respectively. Lets assume T = 3.

First P1 gets chosen as everyone has same priority.
|P1|P1|P1|

After 3 sec, priorities would be
P1 = 0, P2 = 3, P3 = 3, P4 = 3.
So, P2 gets selected.
|P1|P1|P1|P2|P2|P2|

After 6 sec, priorities would be
P1 = 0, P2 = 3, P3 = 6, P4 = 6.
So, P2 gets selected.
|P1|P1|P1|P2|P2|P2|P3|P3|P3|


continuing this way... the execution timeline would be.
|P1|P1|P1|P2|P2|P2|P3|P3|P3|P4|P4|P4|P1|P1|P1|P2|P2|P2|P3|P3|P3|P4|P4|P1|P2|P2|

It can be clearly seen, it is round robin.

Does the length of the job mattered ?
You can clearly see that the P1 with neither the smallest was chosen before other jobs.

Does the remaining job time mattered ?
Same explanation as above. P1 with remaining time of 7 is chosen before P2 (with remaining time of 8) and P4(remaining time of 5). So, clearly remaining time did not matter.

Does the first come first serve mattered ?
We cant see that in this example. Lets try another example to emphasis the first come job did not matter.

Lets tweak the example in discussion. Assume P2,P3,P4 come after 1 sec.

After first epoch of T secs. Priorities would be.
P1 = 0, P2 = 2, P3 = 2, P4 = 2.

So, now P2 would be chosen even though P1 came first. This proves that, first come job has no advantage.

Concepts to Revise :
Job Scheduling

References :