G53OPS - Operating Systems

This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)

Priority Scheduling

Shortest Job First is just a special case of priority scheduling. Of course, we can use a number of different measures as priority.

Another example of setting priorities based on the resources they have previously used is as follows.

Assume processes are allowed 100ms before the scheduler preempts it. If a process only used, say 2ms, then it is likely to be a job that is I/O bound and it is in our interest to allow this job to run as soon as it has completed I/O - in the hope that it will go away and do some more I/O; thus making effective use of the processor as well as the I/O devices.

If a job used all its 100ms we might want to give this job a lower priority, in the belief that we can get smaller jobs completed first before we allow the longer jobs to run.

One method of calculating priorities based on this reasoning is to use the formula

1 / (n / p)

Where
n, is the last CPU burst for that process
p, is the CPU time allowed for each process before it is preempted (100ms in our example)

Plugging in some real figures we can assign priorities as follows

Another way of assigning priorities is to set them externally. During the day interactive jobs may be given a high priority and batch jobs are only allowed to run when there are no interactive jobs. Another alternative is to allow users who pay more for their computer time to be given higher priority for their jobs.

One of the problems with priority scheduling is that some processes may never run. There may always be higher priority jobs that get assigned the CPU. This is known as indefinite blocking or starvation.

One solution to this problem is called aging. This means that the priority of jobs are gradually increased until even the lowest priority jobs will become the highest priority job in the system. This could be done, for example, by increasing the priority of a job after it has been in the system for a certain length of time.

 Last Updated : 23/01/2002