Page 31 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes initiated, the previous record will be output again; and (3) if input is completed before copying
is initiated, and this in turn completed before output is initiated, the next record will be output
instead. This is just for a single record of the output file. If we copy a file of 10,000 records, the
program can give of the order of 310;000 different results.

The actual sequence of operations in time will depend on the presence of other (unrelated)
computations and the (possibly time-dependent) scheduling policy of the installation. It is
therefore very unlikely that the programmer will ever observe the same result twice. The
only hope of locating the error is to study the program text. This can be very frustrating (if
not impossible) when it consists of thousands of lines and one has no clues about where
to look. Multiprogramming is an order of magnitude more hazardous than sequential
programming unless we ensure that the results of our computations are reproducible in
spite of errors. In the previous example, this can easily be checked at compile time. In the
correct version of Algorithm 1, the output and input processes operate on disjoint sets of
variables (g;t) and (f, s, eof). They are called disjoint or non-interacting processes. In the
erroneous version of the algorithm, the processes are not disjoint: the output process refers
to a variable t changed by the copying process; and the latter refers to a variable s changed
by the input process. This can be detected at compile time if the following rule is adopted:
a concurrent statement defines disjoint processes S1; S2; : : : ; Sn which can be executed
concurrently. This means that a variable vi changed by statement Si cannot be referenced
by another statement S (where j =6i). In other words, we insist that a variable subject to
i
change by a process must be strictly private to that process; but disjoint processes can refer
to shared variables not changed by any of them.

Throughout this paper, we tacitly assume that sequential statements and assertions made about
them only refer to variables which are accessible to the statements according to the rules of
disjointness and mutual exclusion. The latter rule will be defined in Section 3. Violations of
these rules must be detected at compile time and prevent execution. To enable a compiler to
check the disjointness of processes the language must have the following property—it must be
possible by simple inspection of a statement to distinguish between its constant and variable
parameters. We will not discuss the influence of this requirement on language design beyond
mentioning that it makes unrestricted use of pointers and side effects unacceptable. The rule of
disjointness is due to Hoare (1971). It makes the axiomatic property of a concurrent statement
S very simple: if each component statement Si terminates with a result Ri provided a predicate
Pi holds before its execution then the combined effect of S is the following:

“P” S “R”
where

P = P1 & P2 & …….. & Pn
R = R1 & R2 & ……. & Rn

As Hoare puts it: “Each S makes its contribution to the common goal.”
i
Mutual Exclusion: The usefulness of disjoint processes has its limits. We will now consider
interacting processes and concurrent processes which access shared variables. A shared variable
v of type T is declared as follows:
Var v: shared T

24 LOVELY PROFESSIONAL UNIVERSITY