Operating System Structure

10.1 Introduction
A modern operating system is structured as a number of System Processes, each performing a very
specific task and all under the control of the Kernel of the operating system. We have already looked
at the individual functions of the operating system and each of these is likely to be represented by one
or more system processes.

10.2 What is a Process?

For our purposes, a process is the result of executing a set of program instructions with a given data
set. Processes that make up the operating system are independent of each other physically but
dependent upon one another logically. Physical independence implies that one process does not
know or need to know where some other process exists, it needs only assume that another process
does exist, this being the logical dependence.

10.2.1 Are there Implications of this Definition?

Firstly, since the process does not exist physically but is only the result of the execution of program
with a given data set, we should be able quite simply to arrange for a single set of instructions
(program) to support a number of processes when combined with different sets of data. Programs that
are to support more than one program must be re-entrant. The easiest way to think of re-entrant code
(program instructions and constants) is to think of it being read-only. Any item of data that needs to be
changed as the program runs must be the property of the process and therefore must reside in the
data space. The process-oriented data as well as belonging to the given process actually contributes
to the definition of the process. Below is shown two processes (A and B) based upon a single piece of
code:

Process A Code Process B

Data Data
A B

Within the operating system, most operations are of a cyclic nature. For example, when one transfer
request is satisfied, another will surely emerge. Obviously, though, one particular process is likely to
be only one in a long chain of processes required to perform a given total action and therefore reliant
upon the processes either side of it. Consider a disk transfer request de-queuer that we saw when
studying device drivers for example. It must be fed by a transfer queuer and relieved by an interrupt
service routine.

This calls for:

(i) a synchronisation scheme for the processes so that they run in some organised order

and (ii) a scheme for information interchange

_________________________________________________________________________________________
Operating System Structure Page 10.1 Colin H C Machin
10.3 Process Synchronisation and Information Interchange
Let us consider the classic ‘producer/consumer’ situation by means of a simple example. Imagine a
building site with two men involved in mixing concrete. One is supplying water, via a bucket, to the
other that is using that water to mix the concrete. The former individual is the producer (of water)
whilst the latter is the consumer. There is only one bucket and thus the consumer cannot function until
the producer has produced some water. Likewise, the producer cannot produce more water until the
consumer has consumed the previous consignment. If we take the water as the information that is to
be transferred then we see that the transfer medium (the bucket) becomes the determining factor for
synchronisation. It is only the individual with the bucket who can function. The situation arises
frequently in computing and particularly within the operating system, since the latter is merely a set of
co-operating processes.

In process terminology, the information is referred to as a message and the transfer medium is a
message buffer. We noted that one process does not synchronise with another by means of a direct
call. In our example, the producer does not call across the building site to the consumer that some
water is available. Instead he passes the water in the bucket to a foreman. The foreman then checks
to see if the consumer is waiting for water (a message) and if so passes the bucket across. Note that
in our case, the consumer will always be waiting since there is only one bucket in the system.

What actually prevents the producer continuing without a bucket available? Exactly how does the
required synchronisation take place?

10.3.1 Semaphores
The provision of two flag signals or semaphores will take care of synchronisation. One of these
signals we shall take to mean "there is an empty bucket available" and the other "there is a full bucket
available". We introduce two operations that work upon these semaphores. One says "is some
condition true? If so, let me proceed and mark the condition as false, otherwise make me wait until the
condition does become true". This is called a p-operation (p-op). The other operation says "declare
some condition as true and if anyone is waiting for this condition to become true, wake him up". This
is called a v-operation (v-op). We talk of performing p-operations and v-operations upon a given
semaphore, for example p (empty bucket) means "if there is an empty bucket let me continue (and use
it) and mark this as such, otherwise make me wait until a bucket becomes available". We may now
formalise the building site example:
Producer Consumer

p(empty bucket) p(full bucket)

fill the bucket empty the bucket

v(full bucket) v(empty bucket)

The completion of one process releases the other without any direct link between them. As soon as a
process is released from a p-op the effective lock that prevented the process from entering the so-
called critical section of code is closed begin the process. This prevents this (and any other) process
from entering the critical section until the lock is again released. Thus our processes can be
represented by closed loops. The idea of re-locking a semaphore when a process is allowed to pass
is important if we consider, for example, two producers but still only one message buffer (bucket).

Producer 1 Consumer Producer 2

p(empty bucket) p(full bucket) p(empty bucket)
fill the bucket use the water fill the bucket
v(full bucket) v(empty bucket) v(full bucket)

Ideally the message buffer needs to alternate between the two producers. We need to rely upon the
lowest level of scheduling to ensure fairness in this respect. Now consider the situation in which there
are two buckets - one nominally belonging to each of the producers. When one producer performs a
v-op on (full bucket) it wakes up the consumer. If, before the consumer has finished consuming this
bucket full, the second producer performs a v-op on (full bucket), the second v-op will have to be
queued. This idea will be extended as we add producers. All we need to do is to modify our
_________________________________________________________________________________________
Operating System Structure Page 10.2 Colin H C Machin
semaphore from a simple no go/go signal (binary semaphore) to a no go/there are n more ..
(whatever(s)) .. in a queue signal (counting semaphore).

A further extension is to allow a larger number of buckets than producers. Now these buckets do not
belong to the individual producers. Instead they belong to (are the property of) the foreman. We can
now allow the producer to produce up to some limit (equal to the number of buckets, ultimately),
placing the produced information into a message queue for the intended consumer. We may not allow
a large message queue length, instead we may impose a limit based upon some arbitrary maximum
length of queue for the given consumer. One important implication of this extension is that even in a
single producer to single consumer situation the build-up of a message queue can absorb differential
rates of operation. For example, if the producer produces at a regular rate and the consumer
consumes in bursts (as might well be the case in our building site analogy), the consumer may not be
held up for lack of information. Likewise, the producer may not be held up for lack of places to put the
information.

10.4 Operating System Structure

We now have all of the mechanisms that are required to appreciate the structure of the operating
system. The operation of the semaphores is passed to the Kernel of the operating system. This
essentially schedules the system processes that make up the bulk of the operating system based upon
their use of the semaphore and message passing systems. The system processes are scheduled on
a very simple fixed priority basis. All interrupts come into the Kernel and are sent to the process(es)
that will deal with the cause of the interrupt. Eventually the process(es) will run and the interrupt will
be serviced. The structure of the operating system may be viewed diagrammatically as follows (the
SVC handler deals with any system calls that may arise. An SVC is simply another name for a system
call here):

Disk
Driver
Memory
Manager
U
s Printer
e Driver
r
P User
r Program Kernel
o Scheduler
g Terminal
r Driver
a
m
s SVC
Handler Filing
System
Handler

Interrupts

Note that the user program scheduler is the only system process that interfaces directly with user
programs. It is the system process with the lowest priority and thus will be selected only when there is
no further activity required by the system processes. Of course, the user SVC (or system call) handler
offers an interface from the user programs to the operating system, but this link is indirect since the
program's execution of a system call will cause an interrupt.

Consider that a user program is running and that it has just executed an "open file" system call. The
Kernel receives the resulting interrupt. This reveals that the interrupt occurred as a result of the
execution of a system (or SVC) call. It formulates and sends a message to the SVC handler process
to inform it that a system call is suspected. Eventually this process runs and discovers that a “open
file” system call has been specified by the user program. It formulates and sends a message to the
Filing System to ask it to open the specified file and a message to the User Program Scheduler to ask
it to mark the requesting user program as blocked. Once the Filing System runs it formulates and
sends a message to the Disk Handler process to ask it to read in a directory block. When this runs, it
starts off the transfer from the disk and then declares to the Kernel that it cannot continue until the
_________________________________________________________________________________________
Operating System Structure Page 10.3 Colin H C Machin
transfer has completed (this will eventually be marked by an interrupt from the disk controller
hardware). The Disk Handler informs the Kernel that it cannot continue by specifying a WAIT
MESSAGE operation, as indeed do all of the processes that are relying upon a reply from some other
process. The Disk Handler may be woken up by either the interrupt that we are expecting or by a
further transfer request. In the former case, it would check the status of the transfer and then report
this back to the Filing System process by means of a message and so on back up the chain.
Eventually the User Program Scheduler will be asked to mark the user program as now runnable.
When no more system process activity is required, the User Program Scheduler will run and eventually
that user program will be selected and run to carry on with its operations.

_________________________________________________________________________________________
Operating System Structure Page 10.4 Colin H C Machin