Petrol

Implementation of a scheduling algorithm.

In this assignment, you will implement the well-known Shortest Remaining Processing Time (SRPT) scheduling algorithm.

The problem is as follows. You are given a computer (or a processor) which has unit speed, i.e., it can do 1 unit of work in 1 unit of time. The computer receives as input a sequence of jobs which may arrive over time. The goal of the scheduling algorithm is to specify which job to process at each time interval.

Each job j is specified by two quantities -- its processing time p(j) which denotes how much processing time is needed to finish this job, and release date r(j), which denotes the time at which the job arrives in the system, i.e., we can start processing this job only after time r(j). Thus each job is specified by a pair (p(j),r(j)). We shall assume that all the quantities p(j) and r(j) are integers.

Let us see an example. Suppose there are two jobs (10,0) and (2,3). One can construct several schedules : one such schedule is to process the first job from time 0 to time 10 (a total of 10 units), and then process the second one from time 11 to 13. Another schedule would be to do the first job from time 0 to time 3 for a total of 3 units. Now do the second job from time 3 to time5, and then finish the first job from time 5 to time 12.

Note that, as in the second schedule above, we may choose to "preempt" a job, i.e., stop processing it, and then process it again at some later point of time. The SRPT algorithm is a scheduling algorithm which tells us which job to schedule at each point of time. The algorithm states that each time unit, we should schedule the job which has the smallest "remaining processing time". The remaining processing time of a job is the amount of processing which still needs to be done on this job.

Let us see an