Process Scheduling

5.1 Introduction

We are aware that the Operating System as a whole is really one enormous scheduler. As such it is
responsible for sharing out the resources of the system such as memory, peripherals and processor
time. The part of the operating system that is known as the scheduler is the part that shares out the
processor time between all of the user programs, and it is that which we now discuss.

Each program in the system will, at any instant, be in exactly one of three different states, namely:

• running - currently running program

The first (running) is a special case of the second (runnable). We are assuming that we have a single
processor in our system, so when the operating system is running, no user program is running. As a
result, we ignore the running state beyond having recorded the identity of the program that was
running immediately before the operating system was entered (as a result of an interrupt, remember).
Programs in the blocked (non-runnable) state are those that are unable to run due to the fact that they
have, for example, requested some input or output operation from the system that has not yet
completed. In time, programs in this state will become runnable and once again eligible for selection
for running. The task of the scheduler is to select the next program to run from the list of runnable
programs. Let us examine a simple scheme that allows this.

5.2 A Simple Scheduler

As we have seen, the task of the scheduler is to select the next program to run from the list of
runnable programs. In order to do this, the scheduler must keep track of which programs are runnable
and which are not. We can imagine a table that holds information on each of the programs to tell us
whether that program is runnable or blocked, as shown below:
Program name R/B
PROGRAM A B
PROGRAM B R
PROGRAM C R
PROGRAM D B
: :
: :

When the scheduler is called to select the next program to run it simply scans the table looking for a
program marked as runnable (R) and selects it. When called again, the scheduler looks for another
(maybe the same) program marked as runnable and so on. If we can have any confidence in the fact
that the programs are listed in the table in some sort of priority order, then we can arrange for the
scheduler to start its scan at the top of the table. If however the programs are listed in the table in
essentially random order, then the scheduler should continue its scan from where it last selected a
program to run. In the former case, the scheduler is known as a priority scheduler and in the latter
case as a round-robin scheduler. Note that if all we need to store in the table is a flag to denote
whether the program is runnable or blocked, we could perhaps get away with storing this single bit of
information in a simple table indexed by program number. This number would in some way be derived
from the program name or from the order of arrival of programs. However, we will see later that this
kind of simple table may be unsuitable, so we will retain the idea of a table that includes identification
of the program. If we are to do that, we could perhaps envisage employing a linked-list to store the
information.

_________________________________________________________________________________________
Process Scheduling Page 5.1 Colin H C Machin
5.3 Priority Considerations
We have mentioned the idea of having confidence in the order of programs in the table being in some
way meaningful in terms of the program's importance relative to those around it. We must examine
the ideas of priority and see if we can build up a picture of how we might gain this confidence. One
simple way of establishing the priority of programs is to say that the longer a program has been in the
system, the higher its priority should be. (We may discover later that this is not necessarily a good
thing to do, though). We can have the table reflect this by always adding new programs at the bottom
of the table. As programs above a particular program complete and new programs are placed below
it, the one in question magically moves up the priority list. We may wish to use other methods for
establishing the priority of a program. For example, the source of a program (e.g. is it a student
running the program? is it the payroll program or is it merely one that is under development?) may
influence its priority. In this case, programs have an initial priority level that is essentially random - at
least as far as other programs in the system are concerned. So, when a program arrives in the system
it will, in general, have a priority less than some of the programs already in the system and a priority
greater than that of others. We must fit the new arrival into the table at the appropriate point, to reflect
its assigned priority. We could do this by storing the priority of the programs within the table, as shown
below:
Program name Priority R/B
PROGRAM A 3 B
PROGRAM B 5 R
PROGRAM C 6 R
PROGRAM D 8 B
: : :
: : :

If we now wish to add a new program, PROGRAM E, with a priority of 4, we would have to place this
after PROGRAM A, giving a new table structure as follows:
Program name Priority R/B
PROGRAM A 3 B
PROGRAM E 4 R
PROGRAM B 5 R
PROGRAM C 6 R
PROGRAM D 8 B
: : :
: : :

The fact that we may now wish to insert entries within this structure suggests that perhaps a simple
table may not be appropriate. We are almost certainly now forced into using a more complex data
structure, such as a linked-list.

We have seen here a situation in which the priority of a program is fixed upon its entry to the system
and we have assumed, perhaps, that the program retains this priority throughout its run - a fixed
priority scheme. There may be some merit in considering a situation in which the priority of a program
is allowed to change as the program runs. This scheme of variable priority had merit in times when
the operator was able to make better use of the system's resources by altering the priority of programs
to, for example, enable one to finish more quickly or another to move into the background for a while.
Nowadays, we allow the system to establish the priority of programs based upon some given criteria.
For example, it can be shown that it is desirable to give priority to programs that perform a lot of input
and/or output relative to processing whilst discriminating against programs with the opposite profile.
This is because if we keep programs that use a lot of processor time in reserve, they can always be
used to soak up any spare processor time that the system has available whilst other programs are
suspended awaiting the completion of input or output. Programs that consume large amounts of
processor time relative to the amount of input/output performed are known as compute-bound (or CPU
bound) programs, whilst those with the opposite profile are known as input/output (I/O)-bound
programs. Any scheme that adjusts the relative priorities of programs on this basis will be making
better use of the system's resources. The question immediately come to mind, "How can we assess
whether a program is computer bound or input/output bound?".

5.3.1 Long-Term Variable Priority Scheduling

One way of reassessing the priority of programs in the system is to apply what amounts to some kind
of scheduling formula to each program. This formula attempts to quantify the various characteristics of
the program's performance to date and to build up some measure of the program's new priority. Such
a formula may take into account a number of factors, including
_________________________________________________________________________________________
Process Scheduling Page 5.2 Colin H C Machin
 • the age of the program (how long it has been in the system)
• the amount of processor (CPU) time that it has consumed
• the number of units of input and output that it has had.

Each attribute is weighted and a composite result obtained. The weights may be positive or negative
and may be greater than or less than unity. The result indicates the program's absolute priority and in
doing so takes no account of the program's merits relative to others. In a scheme where a high
numerical result means that the program should be favoured, as score of 90 appears good. It is,
however, only good if the majority of other programs score below 90. The formula may be applied to
all programs (at once) at regular intervals - say every second or so. This may consume a substantial
amount of processor time for, perhaps, little benefit. We might be able to apply the formula only to
those programs whose status has in any way changed since the last time that the formula was applied
to programs in the system. This is likely to save time as those that have had no processor time or
performed no input or output will not have changed their absolute priority level. If we take this idea of
only considering programs whose status has changed since our last reassessment a stage further, we
see an alternative method emerging, namely that of reassessing a program's priority as it changes
status. This leads us to consider short-term variable priority scheduling.

5.3.2 Short-Term Variable Priority Scheduling

In this scheme we only consider the priority of programs that have changed status since we last looked
at program priority. In fact we look at the priority of programs as they change status. It might be
reasonable to suggest that whenever a program completes an input or output request it may be
considered as input/output bound at least until it proves otherwise. A program may be deemed
compute bound if it spends more than a certain amount of time processing without performing any
input or output.

_________________________________________________________________________________________
Process Scheduling Page 5.3 Colin H C Machin