Co-operating sequential processes
Citation for published version (APA):
Dijkstra, E. W. (1968). Co-operating sequential processes. In Programming languages : NATO Advanced Study
Institute : lectures given at a three weeks Summer School held in Villard-le-Lans, 1966 / ed. by F. Genuys (pp.
43-112). Academic Press Inc..

Document status and date:Published: 01/01/1968
Document Version:
Accepted manuscript including changes made at the peer-review stage
Please check the document version of this publication:• A submitted manuscript is the version of the article upon submission and before peer-review. There can beimportant differences between the submitted version and the official published version of record. Peopleinterested in the research are advised to contact the author for the final version of the publication, or visit the
DOI to the publisher's website.
• The final author version and the galley proof are versions of the publication after peer review.
• The final published version features the final layout of the paper including the volume, issue and page
numbers.
Link to publication

General rights
Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners
and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights.
• Users may download and print one copy of any publication from the public portal for the purpose of private study or research.
• You may not further distribute the material or use it for any profit-making activity or commercial gain
• You may freely distribute the URL identifying the publication in the public portal.
If the publication is distributed under the terms of Article 25fa of the Dutch Copyright Act, indicated by the “Taverne” license above, please
follow below link for the End User Agreement:
www.tue.nl/taverne

Take down policy
If you believe that this document breaches copyright please contact us at:
openaccess@tue.nl
providing details and we will investigate your claim.

Download date: 08. 10月. 2024

EWD123

Table of Contents.

Table of Contents.
Preface.
0. Introduction
1. On

t~e

0

Nature of Sequential Processes.

2. Loosely Connected Processes.

10

2.1 • A Simple Example.

11

2.2. The Generalized Mutual Exclusion Problem.

19

2.3. A Linguistic Interlude,22

3. The Mutual Exclusion Problem Revisited.

26

3.1 . Tf.e Need for a More Realistic Solution.

26

3.2. The Synchronizing Primitives.

28

3.3. The Synchronizing Primitives Applied to the
Mutual Exclusion Problem.
4.The General Semaphore.

30
31

4.1. Typical Uses of the General Semaphore.

31

4.2. The Superfluity of the General Semaphore,

4.3. The Bounded Buffer.

35
39

5. Cooperation via Status Variables.

40

5.1, An Example of a Priority Rule.

41

5.2. An Example of Conversations48

5.2.1. Improvements of the Previous Program.

61

5.2.2. Proving the Correctness.

68

6. The Problem of the Deadly Embrace.

73

6.1. The Banker's Algorithm,

75

6.2. The Banker's Algorithm Applied77

7. Concluding Remarks,

82

E~l~

F~eface.

The main purpose of this preface is to ~xplain the specification
Version'', a~pearing on the title page ~f these lecture notes.
They have bee~ prepared under ccnsiderable ti~e pressure, circumstances~nde~ which I was unable to ha~e my ~se of t~e Englisb language correctedby a ~ative, circumstances under which I was unable first to try out
different methods of presentation. As they stand, I hope that they willserve their two primary purposes: to give my students a guide as to what
I am telling and to give my Friends and Relations an idea of what I am
doing.
''Preli~inar

The future fate of this ~anuscript, that may prove to be a monographin statu nascendi, will greatly depend on their reactions to it. I am greatly
indebted, in advance, to any reader wro is so Kind as to take the trouble
to give ~is comments, either in the form of suggestions how the presentationor the material itself could be improved, or in the form of an appreciation.
From the latter comments I Wlll try to get an idea whether it is worth-while
to pursue this effort any furt~er ard to p=epare a publication fit fo~ andagreeable to a wide~ public,

Already at this stage I s~ould like to express my gratitude to many:
to wy collaborators C.Eron (in particular for his scrutinous screening of
the typed version), to A.N.Habermann, F.J.A.Hendriks, C.Ligtmans and P.A.
Voorhoeve for many stimulating and clarifying discussions on the subject
itself, to the Department of Mathematics of the Technological University,
Eindhoven, for the opportunity to spend my time on the problems dealt withand to lecture on their solutions and also -trivial as it may seem, thisis nevertheless vital!- for putting at my private disposal a type writerwith a character set in complete accordance with my personal wishes.

E.W.Dijkstra

Department of Mathematics
Technological University

P.O. Box 513
EINDHOVENThe Netherlands

E'w'D123 - 0

0, IntrodL.:ction.

These lectures are intended for all those that expect that

i~

their

future acti'lities they will become seriously involved in the problems thatarise in either the desig0 or the more advanced applications of digital
information processing equipment; they arethat arefurthe~i~tended

for all those

uat interested.

The applications I have in mind are those in which the activity of acomputer must include the proper reacting to a possibly great variety ofmessages that can be sent to it at unpredictable moments, a situation which~ccursin process control, traffic control, stock control, banking applica-

ti.~ns,automization of informati:Jn flow in large organizations, centralized

computer service and, finally, all information systems i1

whic~

a numbe~ ofcomputers are coupled to each other.

The desire to apply computers in the ways sketched above has often astrong economic motivation, but in these lectures the not unimportant question of efficiency will not be stressed too much. We shall occupy ourselvesmuch 1lore with the logical problems which arise, for example, when speed
ratios are unknown, cornrnuni::ation possibilities restricted etc. We intend
to do so in order to creat:e a clearer insigl-ot into t:re origin of the difficulties we shall meet and into the nature of our solutions. To decide
whether under given circumstances t~e application of our techniques is
economically attractive or not falls outside the scope of these lectures.

I regret that I cannot offer a fully worked out theory, complete withGreek letter formulae, so to speak. The only thing I can do under the present
circumstances is to offer a variety of problems, together with solutions.
And in discussing these, we can only hope to bring as much system into it
as we possibly can, to find which concepts are relevant, as we go along.
May everyone that follows me along this road enjoy the fascination of these
intriguing problems as much as I do!

EI.•JD1 23 - 1

1. 011 the Nature of Seauential Processes.

Our problem field proper is the cooperation between two or more sequential
processes. Before we can enter this field, however, we rave to know quite
clearly what we call ''a sequential process''·

To this~reliminary

questionthe present section is devoted.

I should like to start my elwcidation with the comparison of two machines
to do the same example job, the one a non-sequential machine, the other asequential one.

Let us assume that of each of fcur quantities, named ''a[1]'', ''a[2]'',''a[3]'' and ''a[4]'' respectively, the value is given. Our machine has to processthese values in such a way trat 1 as its reaction, it "tells" us, which of thefour quantities has the largest value. E.g. in the case:"a[1]~7,a[2] ~ 12,a[3] ~ 2,

a[4] ~ 9"the answer to be produced is "a[2]" (or only 11 2' 1 , giving the index value
pointing to the maximum element).

Note that the desired answer would become incompletely defined if theset of values were -in order- "7, 1 2, 2, 12" 1 for then there is no uniquelargest element and the answer ''a[2]" would have been as good (or as bad)as "a[ 4 ]". This is remedied by the further assumption, that of the four
values given, no two are equal.

Remark 1 •If the required answer would have been the maximum value

occuring among the given ones, then the last restriction would

~ave

been

superfluous, for then the answer corresponding to the value set "7 1 12, 2, 12"
would have been "12".

Remark 2 ..

Our restriction "Of the four values no two are equal'' isstill somewhat loosely formulated, for what do we mean by "equal"? In theprocesses to be constructed pairs of values will be compared with one anotherand what is really meant is, that every two values will be sufficiently
different, so that the comparator will unambiguously decide, which of thetwo is the largest one .. In other words, the difference between any two mustbe large compared with "the resolving power'' of our comparators.

E 1~JDi 23-

2

We shall first construct our non-sequential ~achine. When we assume
our given values to be represented by currents, we canconsisti~g

a comparator

imagi~eof a two-way switch, the position of wrich is schematicallycontrolled by the currents ir the coils of electromagnets as in Fig.1 andFig.2.

~

A

f~

B( [c
Fig. 1.

X

~

X

x<y

~
B~

[

Fig.2.

y<x

When current y is larger than current x, the left electromagnet pulls
harder tl:an the right one a'ld tre s~itch switches to the left (Fig.1) andthe input A is connected to output B; if current x is the larger one, weshall get the situation (Fig.2) where the input A is connected to output C.

In our diagrams we shall omit the coils and shall represent such a
comparator by a small box
.~

~
B

C

only representing at the top side the input and at the bottom side the two
outputs. The currents to be lead through the coils are identified in tl;equestion written inside the box and the convention is, that the input will
be connected to the right hand side output when the answer to the questionis "Yes", to the left hand side output when the answer is "No".

a[2] < a[4-]2++Fig.3.

4++

EWD123- 3

Now we can construct our machine asindica~edin Fig.3. At the output

side we have drawn four indicator lamps, one of wrich will

lig~t

up to

indicate the answer.

ln Fig.4 we indicate the position of the switches when the value set"7, 12, 2, 9" is applied to it. In the boxes the positions of the switches

are indicated, wires not connected to the input are drawn blotted.

'---~'>;: I

\I

!_ __

I

--<

'' 1

''4
Fig.4.

We draw the readers attention to the fact that now only the positionsof the three switches that connect output 2 to the input) matter; the reader
is invited to convince himself that the position of the other three switches
is indeed immaterial.

It is also good to give a moment attention to see what happens in time
when our machine of Fig.3 is fed with four 11 value currents 11 • Obviously it
cannot be expected to give the correct answer before the four value currents
are going through the coils. But one cannot even expect it to indicate thecorrect answer as soon as the currents are applied, for the switches must
get into their correct position and this may take some time. In other words:
as soon as the currents are applied (simultaneously or the one after theother) we must wait a period of time -characteristic for the machine- andafter that the correct answer will be shown at the output side. What happensin this waiting time is immaterial, provided that it is long enough for all
the switches to find their final position. They may start switching simultaneously, the exact order in which they attain their final position isimmaterial and, therefore, we shall not pay any attention to it any more.

From the logical point of view the switching time can be regarded asa marker an the time axis: before it the input data have to be supplied,
after i t the answer is available.

EWD123- 4

In the use of our machine the progress of time is only reflected in
the obvious "before - after" relation, which tells us, that we cannot expect
an answer before the question has been properly put. This sequence relation
is sa obvious (and fundamental) that it cannot be regarded as a characteristic
property of our machine. And our machine is therefore called a "non-sequentialmachine" to distinguish it from the kind of equipment -or processes that canbe performed by it- to be described now.

Up till now we have interpreted the diagram of Fig.3 as the (schematic)
picture of a machine to be built in space. But we can interpret this same
diagram ir a very different manner if we place ourselves in the mind of theelectron entering at the top input and wondering where to go. First it
finds itself faced with the question whether "a[1] < a[2]" holds. Having
found the answer to this question, it can proceed. Depending on the previous
answer it will enter one of the two boxes 11 a[ 1] < a[3] 11 or "a[2] < a[3]",i.e. it will only know what to investigate next, after the first question
has been answered. Having found the answer to the question selected fromthe second line, it will know which question to ask from the third line andhaving found this last answer it will now know which bulb should start toglow. Instead of regarding the diagram of Fig.3 as that of a machine, theparts of which are spread out in space, we have regarded it as rules of
behaviour, to be followed in time.

With respect to our earlier interpretation two differences are highly
significant. In the first interpretation all six comparators started working
simultaneously, although finally only three switch positions matter. In thesecond interpretation only three comparisons are actually evaluated -thewondering electran asks itself three questions- but the price of this gainis that they have to be perfmrmed the one after the other, as the outcomeof the previous one decides what to ask next. In the second interpretation
three questions have to be asked in sequence, the one after the other. The
existence of such an order relation is the distinctive feature of the second
interpretation which in contrast to the first one is therefore called "asequential process". We should like to make two remarks.

Remark 3.

In actual fact, the three comparisons will each take afinite amount of time (switching time" t ''decision time" or, to use thejargon, "execution time") and as a result the total time taken w:i.ll at least

E';JD1 23 - 5

be equal to tre sun1 of these three execution times. 'We stress ance more,that for many i:lvestigations these executions can be regarded as orderedmarkers on a scaleless time axis and that it is only tr.e relative orderingthat matters from this (logical) point of view.

Remark 4.

As a small side line we note that the two interpretations(call them "simultaneous comparisons" and "sequential comparisons 11 ) are only
extremes. There is a way of, again, only performing three comparisons,in which two of them can be done independently from one another, i.e. simultaneously; the third one, however, can only be done, after the other two
have been completed. It can be represented with the aid of a box in which
two questions are put and which, as a result, has four possible exits, as
in Fig.5.

IIa[ 1 J < a[2] ?

~~I

I all ] < a[ 3] ? I Ia[
1-a[3 J < a[ 4 J '

'

I

YN

NY

I ] < a[4]

I

yy~

I

?lla[2]<a[3] ?lla[2] < aL 4] ?

I

I
2

3

4

Fig.5.
The total time taken will be at least the sum of the comparison execution
times. The process is of the firstki~din the sense that the first twocomparisons can be performed simultaneously, it is of sequential natureas the third comparison can only be selected from the second line when thefirst two have both been completed.

We return to our purely sequential interpretation. Knowing that the
diagram is meant for purely sequential interpretation we can take advantageof this circumstance make the description of the "rules of behaviour" morecompact. The idea is, that the two questions on the second line -only oneof which will be actually asked- are highly similar: the questions one thesame line only differ in the subscript value of the left operand of thecomparison. And we may ask ourselves: "Can we map the questions on the sameline of Fig .3 on a single question ?"This can be done, but it implies that the part that varies along aline -i.e. the subscript value in the left operand- must be regarded as a

E't!D123 - 6

parameter,t;~,etask of which is to determine whi2h of the questions mappedon each other is meant, when its turn to be executed has come. Obviously thevalue of this parameter must be defined by the past history of the process.

Such parameters, in which past history can be condensed far future useare called "variables". To indicate that a new value has to be assigned toit we cse the so-called assignment operator'':='' (read: ''becomes''), a kindof directed equality sign which defines the value of the left hand side interms of the value of the right hand side.

We hope that tr.e previous paragraph is sufficientfor the reader torecognize also in the diagram of Fig.6 a set of "rules of behaviour 11 • Ourvariable is called ''i''; if the reader wonders, why the first question, whichis invariably "a[1] < a[2] ?'' is not written that way, he is kindly requested
to

~ave

some patience.

Fig.6
'~hen

we have followed the rules of Fig .6 as intended from top tillbottom, the final value of i will identify the maximum value, viz. a[i].

The transition from the scheme of Fig.3 to the one of Fig.6 is a drasticchange, for the last "rules of behaviour" can only be interpreted sequentially.
And this is due to the introduction of the variable 11 i": having only a[ 1 ] ,
a[2],
11

a[3] and a(4] available as values to be compared, the questiona[i] < a[2] ?'' is meaningless, unless it is known for which value of "i"this comparison has to be made.

E'dD123 - 7

Remark5.

It is somewhat L...!nhappy that the jargon of the trade calls

the thing denoted by ''i'', a variable, because in normal mathematics, theconcept of a variable is a completely timeless concept. Time has nothing
to do with the "x" in the relation''sin(2 * x) = 2 * sin(x) * cos(x)'';
if such a variable ever denotes a value, it denotes ''any value''·

Each time, however, that a variable in a sequential

p~ocess

is used-such as "i" in "a[i]"- it denotes a very specific value, viz. the lastvalue assigned to it, and nothing else! As long as no new value is assigned
de~otes

to a variable, it

a constant value!

I am, however, only too hesitart to coin ~ew terms: firstly it would
make this monograph unintendedly pretentious, secondly I feel that the(fas~ionable~)coining of new terms often adds as much to the confusion in

one way as it removes in the other. I shall therefore stick to the term
"variable".

Remark 6.

One may well ask, what we are actually doing, when we

introduce a variable without specifying, for instance, a domain for it,
i.e. a set of values which is guaranteed to comprise all its future actual
values. 'We shall not pursue this any further here.

Now we are going to subject our scheme to a next transformation. In
Fig.3 we have "wrapped up 11 t~e lines, now we are going to wrap up the schemeof Fig.6 in the other direction, an operation to wich we are invited by therepetitive nature of it and which can be performed at the price of a nexttvariable, "j 11 say.

i:== 1 •'j :~ 1 .

'

Ij

--

4

?I

I

j :~ j + 1·'

a[i] < a[j]?

I i:~ jFig.7

The change is a dramatic one, for the fact that the original problem
was to iderctify the :-~;aximum value among four given values is r.o longer
reflected in the "topology" of the rules of behaviou:::: in Fig.7 we only
find the number "4" mentioned once. By introducing another variable, say"n", and replacing the "4" in Fig.7 by "n" we have suddenly the rules of
behaviour to identify the maximum occurring among then elements a[1 ],a[2], ••••••• , a[n] and this practically only for the price that before
application, the variable n must be put to its proper value.

I called the cGange a dramatic one, for now we have not only given
rules of behaviour which r.,:.Jst be interpreted sequentially -this was alreadythe case with Fig.6- but we have devised a single mechanism for identifying
the maximum value amor<g any number of given elements, whereas our original
non-sequential machine could only be built for a previously well-defined
number of elements. We have mapped our comparisons in time instead of inspace, and if we wish to compare the two methods, it is as if the sequentialmachine "extends itself" in terms of Fig.3 as the need arises. It is ourlast transition which displays the sequential processes in their fullglory.

The technical term for what we have called 11 rules of behaviour" is analgorithm or a program. (It is not customary to call it "a sequential program"
although this name would be fully correct.) Equipment able to follow suchrules, "to execute such a program" is called 11 a general purpose sequential
computer" or "computer" for short; what happens during such a program
execution is called "a sequential process".

There is a commonly accepted technique of writing algorithms without
the need of such pictures as we have used, v:..z. ALGOL 60 ("ALGOL" being
short for Algorithmic Language). For a detailed discussion of ALGOL 60
I must refer the reader to the existing literature. We shall use it in
future, whenever convenient for our purposes.

For the sake of illustration we shall describe the algorithm of Fig.7(but for "n" instead of 11 411 ) by a sequence of ALGOL statements:

"back: if j /: n t··en
j:::: j + 1;

begin

if

a[i] < a[jJ the~ i::::: J;goto backend"

The first two statements:

Then

co~es

11

i: =1 ; j: = 1" are -I hope- self-explanatory,''back:'', a so-called label,~sed

to identify this place in the

program. Then comes "if j /: n then", a so-called conditional clause. If thecondition expr2ssed by it is satisfied, t.'le fol2_owirg statement will be
perfo~med, otherwise it will be skipped. (Another example of it can be found

two lines l~we~.) When the extent ~f the program which may have to be skipped~rimarily

presents itself

as a sequence of more than one

puts the so-called statement brackets

11state~ent,then one

begin 11 and "end" around this sec;uence,

thereby making it into a single statement as far as its surroundings areconcerned. (This is entirely analogous to the effect of parentheses inalgebraic formulae, such as 11 a * (b +c)" where the parenthesis pair indicatesthat the whole expression contained within it is to be taken as factor.) The
last statement

11~back" means that the process should be continued at the

point thus labeled; it does exactly the same thing for us as the upwardleading line of Fig.7.

EWDI23 -I0

2. Loosely Connected Processes.

T~esubjectma-;:;-te~of this monograph is the cooperatior. between loosely

connected sequential processes and this section will be devoted to a thoroughdiscussion of a simple, but representative problem, in order to give thereader some feeling fortre problems in t~is area.

In the previous section we have described the nature of a single
sequential process, performing its sequence of actions autonomously, i.e.
independent of its surroundings as soon as it hes been started.

When two or more of such processes have to cooperate with each other,

they

~ust

be connected, i.e.

t~eymust be able to communicate wi~h each otrer

in order to exchange information. As we shall see below, the properties ofthese means of intercommunication play a vital role.

Furthermore, we have stipulated that the processes should be connected
loosely; by this we mean that apart from the (rare) moments of explicit
intercommunication, the individual processes themselves are to be regarded
as completely independent of each other. In particular we disallow any
assumption about the relative speeds of the different processes. (Such anassumption -say''orocesses geared to the same clock''- could be regarded as
implicit intercommunication.) This independence of speed ratios is in strict
accordance with our appreciation of the single sequential process: its only
essential feature is, that its elementary steps are performed in sequence.
If we prefer to observe the performance with a chronometer in our hand, we
may do so, but the process itself remains remarkably unaffected by thisobservation.

I warn the reader that my consistent refusal to make any assumptions
about the speed ratios will at first sight appear as a mean trick to makethings more difficult than they already are. I feel, however, fully justified in my refusal. Firstly, we may have to cope with situations in which,indeed, very little is kr.own about the speeds. For instance, part of thesystem r11ay be a manually operated input station, another part of the system
might be such, that it can be stopped externally for any period of time,thus reducing its speed temporarily to zero. Secondly -and this is much more

E1ND1 23 - 11

important- wnen we thi<k that we can relyu~oncertain speed ratios, weshall discover t'lat we have been "pouPd foolish and penr-y 'lllise 11 • True thatcertain mechanisms can be made simpler under the

restrictions. The verification, however,t~atass~mptionof speed ratio

such an assunption is always

justified, is in general extremely tricky and tr.e task to 'l1Bke, in a reliable
manner, a well behaved structure out of many interlinked components isseriously aggravated when such ''analogue intarferences" have to be taken
into account as well. (For one thing: it will make the proper working arather unstable equilibrium, sensitive to any change in the different
speeds, as may easily arise by replacement of a component by another -say,replacement of a line printer by a faster~ode!-or reprogramming of acertain portion.)

2.1. A Simple Example.

After these introductory remarks I shall discuss the first problem.

We consider two sequential processes, "process 1" and "process 2", which
for our purposes can be regarded as cyclic. lf"1 each cycle a so-called "critical section'' occurs, critical in the sense that the processes Mave to beconstructed in such a way, that at any moment at most one of the two is
engaged in its critical section. In order to effectuate t~is mutual exclusion
tr.e two processes have access to a number of common variables. We postulate,that inspecting the present value of such a common variable and assigning a
new value to such a common variable are to be regarded as indivisible, noninterfering actions. I.e. when the two processes assign a new value to thesame common variable "simultaneously", then the assignments are to be regarded
as done the one after the other, the final value of the variable will be oneof the two values assigned, but never a "mixture" of the two. Similarly, when
one process inspects the value of a common variable 11 simultaneously" withthe assignment to it by the other one, then the first process will findeither the old or the new value, but never a mixture.

For our purposes ALGOL 60 as it stands is not suited, as ALGOL 60
has been designed to describe one single sequential process. We therefore
propose the following extension to enable us to describe parallellism ofexecution. When a sequence of statements -separated by semicolons as usual

E'~JD1 23- 12

in ALGOL 60- is surrounded by the special statement bracket pair "parbeqin"a~d''parend 11 , this is to be interpreted as parallel execution of the con-stituent staterrents.

T~ewhole construction -:et us call i~ ''a parallel

compound''- can be regarded as a statement.

Initiatio~of a parallel compo~nd

implies simultaneous initiation of all its constituent statements, its
execution is completed after the completion of the execution of all its
constituent statements. E.g.:
11

begin

51; parbeqin

52; 53; 54

parend; 55

end''(in which 51 ,52, 53. 54 and 55 are used to indicate s-:atements) means thataf~er

the completion of 51, the statements 52, 53 ar,d 54 will be executedin parallel, and only when they are all finished, then the execution ofstatement 55 will be i,..,i tiated.

With the above conv<::ntions we can describe our first solutio'L:
11

begin

integer turn; turn:= 1·'

parbegin
process 1 : begin

L1: if

turn

~

2

then

gota L1;

critical section 1·'

turn:= 2;
remainder of cycle 1· goto L1'

end;process 2: begin

L2: i f

turn

~

1

then

goto L2;

critical section 2;
turn:= 1;
remainder of cycle 2; goto L2
endparendend"(Note for the inexperienced ALGOL 60 reader. After "begin" in the firstline we find the so-called declaration "integer turn 11 , thereby sticking to
the rule of ALGOL 60 that program text is not allowed to refer to variables
without having introduced them with the aid of a declaration. As tris
declaration occurs after the "begin" of the outermost statement bracket
pair it means that for the whole duration of the program a variable has
been introduced that will only take on integer values and to which theprogram text can refer by means of the name "turn 11 . )EI~JD1 23

Th~

- 13

two processes communicate with ~ach other via the common integer''turn'', the value of which indicates w~ich of the two processes is the firstto perform (or rather: to finish) its critical section. From the program it
is clear that after the first assignment, the only possible values of thevariable11

turn 11 are 1 and 2. The condition for process 2 to enter its

critical section is that it finds at some moment "turn /: 1", i.e. "tu:rn = 2 11 •But the only way in which the variable 11 turn' 1 can get this value is by theassignment ''turn:= 2" in process 1. As process 1 performs this assignment
only at the completion of its critical section, process 2 can only initiate
its critical section after the completion of critical section 1. And criticalsection 1 could indeed be initiated, because the initial condition "turn = 1"
implied "turn/. 2 11 , so that the potential wait cycle, labeled L1, wasinitially inactive. After the assignment "t:Jrn := 2" the roles of the twoprocesses are interchanged. (N.B. It is assumed that ~he orly references tothe variable "turn" are the ones explicitly shown in the program.)

Our solution, though correct, is, however, unnecessarily restrictive:
after the completion of critical section 1, the value of the variable "turn 11
becomes11

2 11 , and it must be =1 again, before the next entrance into criticalsection 1. As a result the only admissible succession of critical sections
is the strictly alternating one ''1 ,2,1 ,2,1 ,2,1 , ••••• '', in other words, thetwo processes are synchronized. In order to stress explicitly that this is
not the kind of solution we wanted, we impose the further condition "If oneof the processes is stopped well outside its critical section, this is notallowed to lead to potential blocking of the other process.". This makes
our previous solution unacceptable and we have to look for another.

Our second effort works with two integers ''c1" and 11 c2", wherec = 0 I 1

respectively will indicate that the corresponding process in inside I outside
its critical section respectively. We may try the following construction:

"beginintegerc1, c2;

c1 :::::: 1; c2:::::: 1;

parbeqin
process 1 : begin L1: if

c? ·-

0

then

qoto L1;

c1 :::::: 0;
critical section 1;
c1 :::::: 1;
remainder of cycle 1 ; go to L1
end;process 2: begin L2: if c1~

0 thengoto L2;

c2:= 0;critical section 2;
c2:::::: 1;
remainder of cycle 2; gota L2
end

par endend"

The first ass'ignments set both c 's ::::: 1, in accordance with the factthat the processes are started outside their critical sections. During theentire execution of critical section 1 the relation 11 c1 ::::: 0 11 holds and thefirst line of process 2 is effectively a wait 11 Wait as long as process 1 isin its critical section.''. The trial solution gives indeed same protection
against simultaneity of critical section execution, but is, alas, too simple,
because it is wrong. Let first process 1 find thatc2::::: 1; let process 2

inspect c1 immediately afterwards, then it will (still) findc1 ::::: 1. Bothprocesses, having found that the other is not in its critical section, willconclude that they can enter their own section safely!

We have been too optimistic, we must play a safer game. Let us invert,at the beginning of the parallel processes, the inspection of the "c" of theother and the setting of the own "c". We then get the construction:

Go'D123 - 15

11

beqin

c1, c2;integerc1 := 1 ; c2:= 1·'

earbeg:inprocess 1: begin A1: c1 := 0·'

L1: i f

c2

0

~

then

got a

L1 ;

critical section 1·'

c1 := 1 .

'rer:~air,derof cycle 1· go to A1'

end;
process 2: begin A2: c2::::: 0·'

L2: if

c1

~

0

then

goto

L2;

critical section 2;
c2:= 1;remainder of cycle 2; goto A2
end
parendend"

It is worth while to verify that this solution is at least completely
safe. Let us focus our attention an the moment that process 1 finds

c2 = 1and therefore decides to enter its critical section. /l.t this moment we canconclude1) that the relation '1c1 = 0 11 already holds and will continue to holduntil process 1 has completed the execution of its critical section,2) that, as"c2 = 1" holds, process 2 is well outside its criticalsection, which it cannot enter as long as"c1 = 0" holds, i.e. as longas process 1 is still engaged in its critical section.
Thus the mutual exclusion is indeed guaranteed.

But this solution, alas, must also be rejected: in its safety measures
it has been too drastic, for it contains the danger of definite mutual
blocking. When after the assignment 11 c1 := 0" but yet before the inspectionof c2 (both by process 1) process 2 performs the assignment ''c2:= 0", thenboth processes have arrived at label L1 or L2 respectively and both relations"c1 = 0" and "c2 = 0'1 hold, with the result that both processes will wait
upon each other until eternity. Therefore also this solution must be rejected.

It was CK to set CJne's own "c" before inspecting t'le "c:":~ftre other,but it was wrCJng to stick to one's owr c-setting and just ts wait. This is(somewhat) remedied in t~e following constructior:"beginirtegerc1, c2;

c1 :.-= 1; c2:= 1;
parbeqinr;:r:Jcess 1: begin L1: c1 :::::: 0;
if

c2 ::::: 0

then

begin

c1 := i; goto L1 end;

critical section 1;
c1 := 1;remainder of cycle 1; qcto L1
end;
prGcess 2: beqin L2: c2:= 0;
if c1 = 0
begin

then
c2:::::: 1; ~ L2 end;

critical section 2;
c2:= 1;remainder of cycle 2; goto L2
end

par endend 11This construction is as safe as the previous one and, when the assignments"c1 := 0" and "c2:::::: 0 11 are performed ''simultaneously" it will not necessarily
lead to mutual blocking ad infinitum, because both processes will reset theirown "c" back to 1 before restarting the entry rites, thereby enabling theother process to catch the opportunity. But our principles force us to rejectalso this solution, for the refusal to make any assumptions about the speed
ratio implies that we have to cater for all speeds, and the last solution
admits the speeds to be so carefully adjusted that the processes inspect
the other's ''c'' only in those periods of time that its value is= 0. To makeclear that we reject such solutions that only work
our next requirement:

11

wit~

some luck, we stateIf tf-,e two processes are about to enter their criticalsections, it must be impossible to devise for them such finite speeds, thatthe decision which one of the two is the first to enter its critical section
is postponed until eternity.''·E',;IU123 - 17

In passing we ~ate, that thei~just rejected is quite acceptable

sol~tioneveryday life. E.g., when two people are talking ave=t~eteleohone andthey are suddenly disconnected, as a rule both try to reestablish the connection. They bGth dial ar.d if' they get the signal ":\Ju~ber Engaged", ·they put
down the receiver and, if not already called, they try 1'some 11 seconds later.
Of course, this may coincide with the next effort of tre other party, but asa rulet~econnection is reestablished succesfully after very few trials.

In our mechanicalcirc~mstances,

however, we cannot accept this oattern of

behaviour: our parties might very well be

Quite a collection of trial

identical~

have been shown to be incorrect

sol~tionsand at some moment people that had played witr the problem started todo~btwhether it could be solved at all. To the Dutch mathematician Th.J.Dekker
the credit is due for the first correct

It is,

solu~ion.

of our pr9vious efforts: it uses the ''safe sluice

11

i~fact, a mixtureof our last constructions,

together with the integer "turn 11 of the first one, but only to resolve
the indeterminatenessw~enr.ei ther of tre

immediately succeeds .. The

tw::~initial value of ''turn'' could have been 2 as well ..
"begininteger c1, c2, turn;c1 := 1 ; c2 ::::: 1 ; turn::::: 1 ;parbegin
process 1: begin A1: cl ::::: 0;
L1: ifc2:::: 0

then

begin

if

turn

then

go to

L1

then

go to

81 ;

then

go to

L2;

then

go to

82;

c1 := 1;

81: if

turn

goto

2

A1

critical section 1;
turn:= 2; c1 == 1;
remainder of cycle 1; goto A1

process 2: ~ A2: c2:= 0;
L2: if=0

thenbegi,,

if

c1

turn

2

c2:= 1·,E2: if

go to
end;

turn

A2

E'ND:23- 18

critical section 2;
turn::::: 1; c2:= 1;

remainder of cyc~e 2; got::::J

A2

end

parendend"'We shall now pr.:Jve t"ie correctnes3 of this solu-,;ior.. Jur first obser-

vation is that each process only operates on its own ''c". As a result process

1 inspects "c2'' only while ''c1 = 0'', it will only enter its critical section
providea it finds "c2::: 1 11 ; for process 2 the analogous::~bserv:;:~tion

can bemade.

I: short, we recognize the safe sluice of our last constructions and thesolution is safe in the sense that the two processes can never be in theircritical sections simultaneously. The second part of the proof has to showthat in case of doubt the decision which of the two will be the first toenter cannot be postponed until eternity.

~Jaw

we should pay some attention

to the integer "turn'': we note that assignment to this variable only occurs
at the end -or, if you wish: as part- of critical sections and therefore wewe can regard t'le variable "turn" as a constant during this decision process.
Suppose that "turn = 1 ". Then process 1 can only cycle via L1, that is with
"c1 = 0" and only as long as it finds "c20". But if "turn = 1 11 thenprocess 2 can only cycle via B2, but this state implies ''c2 = 1'', so thatprocesscannot and is bound t:J enter its critical section. For ''turn = 2"

the mirrored reasoning applies. As third and final part of the proof we
observe that stopping, say, process 1 in "remainder of cycle 1" will not
restrict process 2: the relation

11

C1 = 1" will then hold and process 2 canenter its critical section gaily, quite independent of the current value of''turn". And this completes the proof of the correctness of Dekker's solution.
Those readers that fail to appreciate its ingenuity are kindly asked torealize, that for them I have prepared the ground by means of a carefully
selected set of rejected constructions.

2.2. The

Ge~eralized

Mutual Exclusion Problerr.

The probleT of 3ection 2.1
processes,

eac~

~as

a natural generalizatior: given

with a critical section, can we construct

t~em

in

~cyclic

s~c~

a way,

that at any moment at :nost one of them is engaged in its critical section?
We assume the same means of intercommunication available, i.e. a set ofcommonly accessible variables. Furthermore our solt..:tion has to satisfy thesame requirements, that stopping one process well outside its critical section
may in no way restrict the freedom of the others, and that if more than one
process is about to enter its critical section, it ~ust be impossible todevise for the:n such finite speeds, that the decision wrich ore of them ist~efirs: one to enter its critical section, can be postponed Gntil eternity.

In order to be able to describe the solution ir, ALGCL 60, we need theconcept of the array. In section 2.1 we had to introduce a 1'c 11 for each of
the two processes and we did so by declaring"integerc1, c2' 1 •Instead of enumerating the quantities, we can declare -under the assumptionthat "N" has a well defined positive value"integer

array c[ 1N]"which means, that at one stroke we have introduced N integers, accessible
under the names"c[subscript]",

where "subscript" might take the values 1, 2, •••••. , N.

The next new ALGOL 60 feature we shall use is the so-called "for clause 1' ,which we shall use in the following form:"for j := 1 step 1 until N do statement 5 11,

and whicl-, enables us to express repetition of "statement 5" quite conveniently.
In principle, the for clause implies that "statement 5" will be executed N
times, with "j" in succession = 1, = 2, •••... , = 1\J.

Ne have added "in( 1principle'', for via a go to statement as constituent part of statement S
and leading out of it, the repetition can be ended earlier.)-·:

Finally we need the logical operator that in this monograph is denotedby "and". ·we have met the conditional clause in the form:

''if condi~i~n then statement''
We shall new mee~:"if c~:mdition
meaningtha~

and condition 2 t~en statement ''stetement 5 will~n!y

be executed if ''cand~tion 1'' and ''condition

2" are both satisfied. \Once :nore we :::.hCJuld like t:J stress that this mon:Jgrao~
is ;nt an ALGOL bO progranr11ing marual:t~eabove -lo.:;se!- explanations :Jf

ALGOL 60 have only been introduced to meke this monograph as self-contained
as possible.)

With

t~e

notational aids just sketched we can describe our solution

for fixed N as follows.

The overall structure is:"beginintegerarray b, c[O;Nj;integer turn;for turn:= 0 ~ 1 until N do
begin b[ turn]:= 1 ; c[ turn J:=
turn:= 0;parbegin
process 1 : begin ..••.••••.•.......... end;
process 2: begin .......••.•....••••.. end;

pr::tcess N: begin ........•..•....•.•.. end
parendend"

The first declaration introduces two arrays withN + 1

elements each,the next declaration introduces a single iilteger "turn". In the following
f:::rr clause this variable "turn" is used to take on the successive valuesi, 2, 3, ••.... ,~J,

so that the two arrays a=e initialized wit~ all elements= 1. Then ''turn'' is set= 0 (i.e. none of the processes, numbered from 1
onwards, is privileged). After this theN processes are started simultaneously.

The N processes are all similar. The structure of the i-th process is
as follows (I< i < N) :"process i: begin

inteqer j;

Ai: c[ij:~ 0;

Li: if

tLr~

j i

tren

begin eLi]:= 1;b[ turc]

ifthen turn:.:::o l jgoto Lic[i]:~ 0;for j :~ I step I until N do

begin

if

c

f i and c[ j J

0 t~en~Li end;critical secticn i·'turn:= 0· c[i~:= 1; b[i]:~ 1 ;'remainder o~ cycle i; 9oto

~i

end"

Remark.

T~edescription of the N individual processes starts with s declaration''integer j''· According to the rules of ALGOL 60 this means trat each processintroduces its own, private integer "j" (a so-called 11 local quantity").

We leave the pr:J:Jf to the reader. It has to show again:
1) that at any momef"1t at most one of "'::he processes is engaged in its
critical section2) that the decision which of tre processes is the first to enter its
critical section cannot be postponed until eternity2) that stopping a process in its ''remainder of cycle'' has no effectupon the others.

Of these parts, the second one is tre most difficult one. (Hint: as soon
as one of the processes has

perfor~ed

the assignment ''turn:= i", no newprocesses can decide to assign their number to turn before a critical section
has been completed. Mind that two processes ·can decide "simultaneously'' toassign t~eir i-value to turn!)(Remark, that can be skipped at first r~ading.)
The program just described inspects the value of "b[turn]" where boththe array "b" and the integer "turn" are in common store. We have statedthat inspecting a single variable is an indivisible action and inspecting

''b[turn]'' can therefore ~nly mean: i~spect the value of ''turn'', and if t~is~appens to be= 5, well, ~hen inspect ''b[5]''· Or, ir ~ore explicit ALGOL:~precess

i: ~integer j, k;

k:= turn; if b[k] = 1 ther ....••..

"

implying that ty the time that ''b[k]'' is inspected, ''turn'' may already ~avea value different from the current one of ''k''·Without the stated limitations in communicating with the ccmmcn stare, apossible interpretation of "the val:Je of b[turr<] 11 would have been "tre valueof the element of the array b as inoicated by the current value of turn''·
In so-called uniorogramming -i.e. aon

q~ar~ities~ingleseouential process

operating

local to it- the two interoretations are equivalent. In

multiprogramming, where other active processes may access and change thesame conmon informatio0, the two interpre":at:.ons make a great differarce!
In particular for the reader with extensive experience in uniprcgramming
this remark has been inserted as ani~dicationof the subtleties of t~egames we are playing.

2.3. A Linguistic Interlude.
(This section may be skipped at first reading.)

In section 2.2. we described the cooperation of N processes; in theove::-all structure we used a vertical sequence of dots between the brackets''parbeqin" and "parend''. Tris is nothing but a loose formalism, suggesting
to the human reader how to compose in our notation a set of N cooperating
sequential processes, under the condition that the value of N has been fixed
beforehand. It is a suggestion for the construction of 3, 4 or 5071 cooperatingprocesses, it does not give a formal description of N such cooperating processes
in which N occurs as a parameter, i.e. it is not a description, valid for amy
value of N.

It is the purpose ::Jf this section to show that the concept of theso-called "recursive procedure" of ALGOL 60 caters for this. This concept
will be sketched briefly.

We have seen, how after "begin" declarations could occur in order tointrod~ceand t~ ~arne either single varibles (by enumeration of their names)or w~ole ordered sets of variables (viz. in the array declaration). Wit~
the so-called ''procedure declaration'' we can define and name a certain
action;sue~

anacti~nmay the~ be invoked by ~sing its name as a statement,

thereby supplying the parameters, to which the action should be applied.

As an illustration we ':.Onsider the fol:owing P..LGCL bO program:"begininteger a, b;
procedure square(u, v); integer u, v;
begin u:= v * v end;

' square(b, a \1 ; square (' a,L: square ( a, 3J;
'

b)'

end"

In the first line the integer named ''a'' and ''b'' are declared. The nextline declares the procedure named "square", operating on two parameters,
which are specified to be single integers (and not, say, complete arrays).
This line is called "the procedure heading 11 • The immediately following
statement -the so-called 11 procedure body"- describes by definition theaction named: in the third line -in which the bracket pair "begin •..• end"
is superfluous- it is told that the action of "square''i~

to assign to thefirst parameter the square of the value of the second one. Then, labeled "L",comes the first statement. Before its execution the values of both ''a'' and''b'' are undefined, after its execution''a = 9''. After the execution of thenext statement, the value of "b" is therefore = 81, after the execution of
the last statement, the value of ''a'' is =b561, the value of ''b'' is still= 81.

In the previous example the procedure mechanism was essentially introduced
as a means for abreviation, a means for avoiding to have to write down the"body" three times, although we could"begin~ave

done so quite easily:

integer a, b;

L: a:= 3 * 3;b:= a* a; a:= b * b

end".

When the body is much more complicated than in this example, a program
along the latter lines tends indeed to be much more lengthy.

EwD123 - 24

This technique of 11 substituting for the call the appropriate versionof the body'' is, however,~alonger possible asso~nas the procedure is a

so-called recursive one, i.e. may call itself. It is then, that the procedure

really enlarges the expressive power of the programming language.

A simple example might illustrate the recursive procedure.

T~egreatest

common divisor of two given natural numbers is1) if they ~ave the same value equal to this value2) if they have different values equal to the greatest common divisor of thesmallest of the two and their difference.
In other words, if the greatest common divisor is not t~ivial (first case)the problem is replaced by finding the greatest common divisor of two
smaller numbers.

(In the following program the insertion "value v, w;" can be skipped by thereader as being irrelevant for our present purposes; it indicates that forthe parameters listed the body is only interested in the numerical valueof the actual parameter, as supplied by the call.)"begininteger a;procedure GCD(u, v, w); value v, w; integer u, v, w;
begin

if v ::::: w then u:::::: v
else
begin

__

if v < w then GCD(u, v, w - v)
else GCD(u, v - w, w)

end·,

GCD(a, 12, 33)
end If(In this example the more elaborate form of the conditional statement
is used, viz.:''if condition then statement 1 else statement 2"·
meaning that if "condition" is satisfied,"statement 1" will be executed and11statement 2" will be skipped, and that if "condition" is not satisfied,"statement 1" will be skipped and "statement 2" will be executed.)

The reader is invited to follow the pattern of calls of GCD and tosee, how the variable "a'' becomes ::::: 3; he is also invited to convincehimself of the fact that the (dynamic) pattern of calls depends on theparameters supolied and that the substitution technique -replace call bybody- as applied in t0e previous example wculd lead to difficulties here.

We shall now write a program to perform a matrix * vector ~ultiplication
i:l which1) the order of the~ scalar* scalar products to be summed is indeedprescribed (the rows of the matrix will be scanned from left to right)2) the N rows of the matrix can be processed in parallel.

(1.~here

we do not wish to impose the restriction of purely integer values,

we have used to declarator 11 real 11 instead of the declarator 11 inteqer 11 ; furthermore we \--·ave introduced an array with two subscipts in a, we hope,obvious manner.)

It is assumed that, upon entry of this block of program, the integers"~"

and "N" have positive values.

"begin~ array matrix[ 1N, 1real array vector[1M];

real array product[ 1 : N];procedure rowmult(k); value k; integer k;
begin

if k > 0 thenparbegin
begin real s; integer j;s:o: 0;for j ::= 1 step 1 until M dos:o: s + matrix[k,product[ k] := send;rowmult(k - 1)

parendrowmult(N);end"j] * vector[j];E'WD123 - 26

3. The Mutual Exclusion Problem Revisited.
We return to the problem of mutual exclusion in time of critical sectior.<:;,,~sintroduced in

sectio~2.1 and generalized in section 2.2. This section

deals with a more efficient tecl-nique for solving- this problem; only after

having done so, we have adequate means for the description of examples, withwhich I hope to convince the reader cf the rathe:·~undamental

importanceof ti-e mutual exclusion problem. In other wcras, I must appeal to the patier;ceof the wondering reader (suffering, as I am, from the sequential nature ofhuman communication!)

3.1. The Need for a More Realistic Solution.

The solution given in

sec~ion

2.2 is interesting in as far as it showsthat the restricted means of communication provided are, from a theoreticalpoint of view, sufficient to solve the problem. From other paints of view,which are just as dear to my heart, it is hopelessly inadequate.

To start with, it gives rise to a rather c~mbersome description of theindividual processes, in which it is all but transpcrent that the overallbehaviour is in accordance with the conceptually so simple requirement oftre mutual exclusion. In other words, in some way or another this solution
is a tremendous mystification. Let us try to isolate in our minds in which
respect this so2.ution represents indeed a mystification, for this investigatiorcould give the clue .~to improvement.

Let us take the period af time during which one of the processes is in
its critical section. We all know, that during that period, no other processes
can enter their critical section and that, if they want to do so, they have to
wait until the current critical section execution has been completed. For theremainder of that period hardly any activity is required from them: they haveto wait anyllow, and as far as we are concerned 11 they could go to sleep 11 •Our solution does nat reflect this at all: we keep the processes busy
setting and inspecting common variables all the time, as if no price has tobe paid for this activity. But i f our implementation -i.e. the ways in whichor the means by which these processes are carried out- is such, that "sleeping"EWD123 - 27

is a less expensive activity than this busy way of waiting, then we are
fully justified (now also from an economic point of view) to call oursolution misleading.

In present day computers, there are at least two ways in which thisactive way of waiting can be very expensive. Let me sketch them briefly.
These computers have two distinct parts, usually called "the processor'' and"the store". The processor is the active part, in which the arithmetic andlogical operations are performed, it is "active and small"; in the store,

which is "passive and large" resides at any moment the information, which
is not processed at that very moment but only kept there for future reference.
In the total computational process information is transported from store toprocessor as soon as it has to play an active role, the information in store
can be changed by transportation in the inverse direction4

Such a computer is a very flexible tool for the implementation ofsequential processes. Even a computer with only one single processor canbe used to implement a number of concurrent sequential processes. Froma macroscopic point of view it will seem, as though all these processes
are carried out simultaneously, a more closer inspection will reveal,
however, that at any "microscopic" moment the processor helps along only
one single program, and the overall picture only results, because atwell chosen moments the processor will switch over from one process toanother. In such an implementation the different processes share the sameprocessor and activity of one of the processes (i.e4 a non-zero speed) will
imply a zero speed for the others and it is then undesirable, that precious
processor time is consumed by processes, which cannot go on anyhow4

Apart from processor sharing, the store sharing could make the unnecessary
activity of a waiting process undesirable. Let us assume that inspection ofor assignment to a "common variable 11 implies the access to an information
unit -a so-called "word"- in a ferrite core store. Access to a word in acore store takes a finite time and for technical reasons only one word canbe accessed at a time4 When mo~e than one active process may wish access towords of the same core store, the usual arrangement is that in the case of
immanent coincidence, the storage access requests from the different active
processes are granted according to a built in priority rule: the lower
priority process is automatically held up4 (The literature refers to thisEWD123 - 28

situation when it describes "a communication channel stealing a memory
cycle from the processor.) The result is that frequent inspection ofcommon variables may slow downH~eprocess, the local quantities of which

are stored in the same core store.

3.2. The Synchronizing Primitives.

The origin of the complications, which lead to such intricate solutions
as the one described in section 2.2 is the fact that the indivisible accesses
to common variables are always "one-way information traffic": an individual
process can either assign a new value or inspect a current value. Such an
inspection itself, however, leaves no trace fort~eother processes and theconsequence is that, when a process want to react to the current value of acommon variable, its value may be changed by the other processes between
the moment of its inspection and the following effectuation of the reaction
to it. In other words: the previous set of communication facilities must be
regarded as inadequate for the problem at hand and we should look for better
adapted alternatives.

Such an alternative is given by introducinga) among the common variables special purpose integers, which we shall call"semaphores".
b) among the repertoire of actions, from which the individual processes haveto be constructed, two new primitives, which we call the

11

P-operation 11

and the "V-operation" respectively. The latter operations always operate
upon a semaphore and represent the only way in which the concurrent processes
may access the semaphores.

The semaphores are essentially non-negative integers; when only used
to solve the mutual exclusion problem, the range of their values will evenbe restricted to "0" and "1 ". It is the merit of the Dutch physicist andcomputer designer Drs.C.S.Scholten to have demonstrated a considerable fieldof applicability for semaphores that can also take on larger values. When
there is a need for distinction, we shall talk about ''binary semaphores" and"general semaphores" respectively. The definition of the P- and V-operation

EWD123- 29

that I shall give ~ow, is insensitive to tr.is distiction.

Definition.

The V-operatian is an operation with one argument, which must

be the identification of a semaphore. (If "51 11 and "52 11 denote semaphores,

we can write "V(S1)" and "V(S2) 11 . ) Its function is to increase the value of
its argument semaphore by 1; this increase is to be regarded as an indivisible
operation.

Note, that this last sentence makes11

V(51 )" inequivalent to

11

51 ::::.:- 51 + 1''.

For suppose, that two processes A and B both contain the statement "V(51)"and that both should like to perform this statement at a moment when, say,11

51 = 6". Excluding interference with 51 from other processes, A and B will

perform their V-operations in an unspecified order -at least: outside ourcontrol- and after the completion of the second V-operation the final valueof 51 will be ~ 8. If 51 had not been a semaphore but just an ordinary common
integer, and if processes A and E had contained the statement ''51:~ 51 + 1''
instead of the V-operation on 51, then the following could happen. Process
A evaluates "51 + 1" and computes "7"; before effecting, however, the assignmentof this new value, process B has reached the same stage and also evaluates
11

51 + 1 ", computing "7 11 • Thereafter both processes assign the value ''7" to51 and one of the desired increases has been lost. The requirement of the"indivisible operation" is meant to exclude this occurrence, when the Voperation is used.

Definition. The P-operation is an operation with one argument, which must
be the identification of a semaphore. (If "51" and "52" denote semaphores,
we can write "P(51 )" and "P(S2) 11 . ) Its function is to decrease the value of
its argument semaphore by 1 as soon as the resulting value would be nonnegative. The completion of the P-operation -i.e. the decision that this is
the appropriate moment to effectuate the decrease and the subsequent decrease
itself- is to be regarded as an indivisible operation.

It is the P-operation, which represents the potential delay, viz. whena process initiates a P-operation on a semaphore, that at that moment is= 0, in that case this P-operation cannot be completed until another process
has performed a V-operation on the same semaphore and has given it the value
11

1 11 • At that moment, more than one process may have initiated a P-operation

E'tJD1 23· - 30on that very same semaphore. The clause that completion of a P-ooeration isan indivisible action means that wf--en the semaphore :,as got the value "1 '',only one of t~e initiated P-operations on it is allowed to be completed.
INhich one, again, is left unspecified, i.e. at least outside our control.

At the present stage of our discussions we shall take the implementabilityof the P-and v-operations for granted.

3.3. The Synchronizing Primitives Applied to the Mutual Exclusion Problem.
The solution of the N processes, each with a critical section, theexecutions of which nust exclude one another in time (see section 2.2) is
now trivial. It can be done with the aid of a single binary semaphore, say"free". The value of "free" equals the number of processes allowed to enter
their critical section now, or:free

1" means: none of the processes is engaged in its critical section"free0" means: one of the processes is engaged in its critical section.

11

The overall structure of the solution becomes:"begininteger free; free:= 1;

parbegin
process 1: begin ••••••••.•••••• end;
process 2: begin ••••••.•••••.. -~;process N: begi.,, .............. end;
parendend"
with the i-th process of the form:"process i: begin
Li: P(free); critical section i; V(free);remainder of cycle i; goto Liend"

4. The General Semaphore.

4.1. Typical Uses of the General Semaphore.

We consider two processes, whic'l are called the 11 producer 11 and the11

consumer 11 respectively. The producer is a cyclic process and each time itgoes through its cycle it produces a certain portion of information, thathas to be processed by the consumer. The consumer is also a cyclic process
and each time it goes through its cycle, it can process the next portion of
information, as has been produced by the producer. A si~ple example is given
by a computing process, producing as "portions of ir,formation 11 punched cards
images to be punched out by a card punch, w'rich plays the role of tre
consumer.

The producer - consumer relation implies a one-way communication channel
between the two processes, along which the portions of information can betransmitted. We assume the two processes to be connected for this purpose
via a buffer with unbounded capacity, i.e. the portions produced need not
to be consumed immediately, but they may queue in the buffer. Tre fact thatno upper bound has been given for the capacity of the buffer makes thisexample slightly unrealistic, but this should not trouble us too mucr now.

(The origin of the name "buffer" becomes understandable as soon as we
investigate the ccnsequences of its absence, viz. when the producer can onlyoffer its next portion after the previous portion has been actually consumed.
In the computer - card punch example, we may assume that the card punch canpunch cards at a constant speed, say 4 cards per second. Let us assume, that
this output speed is well matched with the production speed, i.e. that thecomputer can perform the card image production process with the same average
speed. If the connection between computing process and card punch is unbuffered,then the couole will only work continuously at full speed when the card production process produces a card every quarter of a second. If, however, thenature of the computing process is such,tha~

after one or two seconds vigorous

computing it produces 4 to 8 card images in a single burst, then unbufferedconnection will result in a period of time, in which the punch will standidle (for lack of information), followed by a period in which the computing
process has to stand idle, because it cannot get rid of the next card image

E',JD123 - 32

before the preceding one has been actuallypu~ched.

Such irregularities in

production speed, however, can be smoothed out by a buffer of sufficient

size and that is, why suet~ a queuing device is called "a buffer".)In this section we shall not deal with the various techniques of implementing a buffer. It must be able to contain successive portions of infor~atian,

it must therefore be a suitable storage medium, accessible to both processes.
Furthermore, it must not only contain the portions themselves, it must also

represent their lineair ordering. (In the literature two well-known techniques
are described by "cyclic buffering" and "chaining" respectively.) When the
producer has prepared its next portion to be added to "':he buffer, "'e shallindicate this action simply by "add portion to buffer 11 , without going into
further details; similarly, the consumer will "take portion from buffer",
where it is understood that it will be the oldest portion, still in thebuffer. (Another name of a buffer is a "First- In-F irst-Dut-Memory.)

Omitting in the outermost block any declarations for the buffer, we
can now construct the two processes with the aid of a single general semaphore,
called "number of queuing portions".
"beginintegernumber of queuing portions;

number of queuing portions:= 0;parbegin
producer: begin
again 1: produce the next portion;
add portion to buffer;
V(number of queuing portions);
goto again 1
end;consumer: begin
again 2: P(number of queui~g portions);
take portion from buffer;process portion taken;

end

par endend' 1

E',JD123 - 33

The first lin= of the producer represents the coding of the process
which forms the next portion of information; it can be conceived -it has ameaning- quite {~dependent of the buffer for w~ich this portion is interded; when

it has been executed t~e next portion has been succesfully completed, thecompletion of its construction can no longer be dependent on other (unmentioned)
conditions. The second line of coding represents the actions, which define
the finishedportions as the next one in the buffer; after its execution

the new portion has been added completely to the buffer, apart from the factthat tre consumer does not know it yet. The V-operation finally confirms its

presence, i.e. signals it to the consumer. Note, that it is absolutely essential, that the V-operation is precede by the compl "'te addi tior, of tre portion.
About the structure of the consumer analogous remarks can be made.

Particularly in the case of buffer imple;nertation by mea:~s o-F chaining
it is not unusual that the operations ''add portion to buffer'' and ''takeportion from buffer" -operating as they are on the same clerical status
information of the buffer- could interfere with each other in a most undesirable fashion, unless we see to it, that they exclude each other in time.
This can be catered for by a binary semaphore, called "buffer manipulation",
the values of which mean:0either adding to or taking from the buffer is taki~g placeneither adding to nor taking from the buffer is taking place.
The program is as follows:EwD123- 34"begin integer number of queuing portions, buffer manipulation;

number of queuing

portions:~0;

buffer man-ipulation:= 1;
parbegin

producer: begin
again 1: oroduce next portion;P(buffer manipulation);
add portion to buffer;v( buffer manipulation);V(number of queuing oortions);
goto again 1
end;
co~ sumer:

begin

again 2: P(number of aueing portions);P(buffer manipulation);take portion from buffer;V(buffer manipulation);process portion taken;
goto again 2
endparendend"

The reader is requested to convince himself thata) the order of the two \/-operations in the producer is immaterialb) the order of the two P-operations in the consumer is essential.
Remark.

The presence of the binary semaphore "buffer manipulationn

has another consequence. We have given the program for one producer andone consumer, but now the extension to more producers and/or more consumers
is straightforward: the same semaphore sees to it that two or more additionsof·new portions will never get mixed up and the same applies to two or moretakings of a portion by different consumers. The reader is requested toverify that the order of the two V-operations in the producer is still
immaterial.

E'ND123 - 35

4.2. The Superfluity of the General Semaphore.

In this section we shall show the superfluity of the general semaphore
and wes~alldo so by rewriting the last program of the previous section,using binary semaphores only. (Intentionally I have written

and not

11

11

we shall show 11

we shall prove the superfluity". We do not have at our disposal

the mathematical apparatus that would be needed to give such a proof anddo not feel inclined to develop such mathematical apparatus now. NeverthelessI hope that my show will be convincing!) We shall first give a solution andpostpone the discussion till afterwards.
11

begin

integer numqueupor, buffer manipulation, consumer delay;
numqueupor:~0; buffer manipulation:= 1; consumer delay:= 0;

par beginproducer: begin
again 1: produce next portion;P(buffer manipulation);
add portion to buffer;numqueupor:= numqueupor + 1;
if numqueupor = 1 then V(consumer delay);V(buffer manipulation);goto again 1
end;consumer: begin
wait:

integer oldnumqueupor;P( consumer delay);

go on: P(buffer manipulation);take portion from buffer;numqueupor:= numqueupor - 1;
oldnumqueupor:= numquepor;V(buffer manipulation);process portion taken;
if oldnumqueupor = 0 thengoto wait else

goto go on

end

parendend"

Relevant in the dynamic behaviour of this program are the periods of time

E',•iD123 - 36

during whicr the buffer is empty. (As long as the buffer is not empty, t~econsumer can go on happily at its 'Tlaxirnum speed.) Suer, a period can only beinitiated by the consumer (by taking the last portion present from tf-le buffer),
it can only be terminated by the producer (by adding a portion to an empty
buffer). These two events can be detected unambiguously, thanks to thebinary semaphore 11 buffer manipulatian 11 , that guarantees the mutual exclusionnecessary for this detection. Each such pe::riod is accompanied by a P- and a\}-operation on the new binary semaphore "consumer delay 11 • Finally we draw
attention to the local variable "oldnumqueupor 11 of the consumer: its value
is set during the taking of the portion and fixes, whether it was thelast portion then present. (The more expert ALGOL readers will be aware that
we only need to store a single bit of information, viz. whether the decreaseof numqueupor resulted in a value~ 0; we could have used a local variableof type Boolean for this purpose.) When the consumer decides to go to"wait", i.e. finds "oldnumqueupor ~ 0 11 , at that moment "numqueupor 11 itself
could already be greater than zero again!

In the previous program the relevant occurrence was the period withempty buffer. One can remark that emptiness is, in itself, rather irrelevant:it only matters, when the consumer should like to take a next portion, whichis still absent. We shall program this version as well. In its dynamic
behaviour we may expect less P- and V-operations on "consumer delay", viz.
not when the buffer has been empty for a short while, but is filled again
in time to make delay of the consumer unnecessary. Again we shall first
give the program and then its discussion.

EliD1 23 - 37

"begininteger numqueupor, buffer manipulation, consumer delay;
nu~queupor:=0; buffer manipulation:= 1; consumer delay:= O;parbegin

producer: ~again 1: produce next portion;P(buffer manipulation);
add portion to buffer;numqueupor:= numqueupor + 1;
i f numqueupor = 0 thenbegin

V(buffer manipulation);v( consumer delay) end
else

V(buffer manipulation);goto again 1
end;consumer: begin

again 2: P(buffer manipulation);numqueupor:= numqueupor - 1;
if numqueupor = - 1 thenbegin

V(buffer manipulation);P(consumer delay);P(buffer manipulation) end;

take portion from buffer;V(buffer manipulation);process portion taken;
gota again 2
endparendendn

Again, the semaphore "buffer manipulation'' caters for the mutual
exclusion of critical sections. The last six lines of the producer could
have been formulated as follows:11

if numqueupor = 0 then v(consumer delay);V(buffer manipulation); goto again 1 n

n.1n123 - 38

In not doing so I

~avefollowed a personal taste, viz. to avoid P- andV-operations within critical sections; a personal taste to wf-·icr thereader should not pay tao~uchattention.

The range of possible values of ''numqueupar'' has been extended withthe value "-1'', meaning (outside critical section execution) ''the buffer
is not only empty, but its emptyness has already been detected by the
consumer, which has decided to wait". This fact can be detected by the
producer when, after the addition of one, "numqueupor = 0" holds.

Note how, in the case of "nurnqueupor = - 1 ", the critical section of
the consumer is dynamically broken into two parts: this is most essential,
far ot~erwise the producer would never get the opportunity to add the
portion tr,at is already so much wan ted by the consumer.

(The program just described is known as "The Sleeping Barber". There isa barbershop with a separate waiting room. The waiting room has an entry
and next to it an exit to the room with the barber's chair, entry andexit sharing the same sliding door which always closes one of them; furthermore
the entry is so small that only one customer can enter it at a time, thus
fixing their order of entry. The mutual exclusions are thus guaranteed.

-~

Barber's Chair+~------i~l

Waiting room.

When the barber has finished a haircut, he opens the door to thewaiting room and inspects it. If the waiting room is not empty, he invites
the next customer, otherwise he goes to sleep in one of the chairs in thewaiting room. The complementary behaviour of the customers is as follows:when they find zero or more customers in the waiting room, they just wait
their turn, when they find, however, the Sleeping Barber -"numqueupor = - 1 "they wake him up.)

EI".'D123 - 39

The two programs given present a strong hint ~o theconcl~sionthat

the general semaphore is, indeed, superfluous. Nevertheless we shaal not
try to abolish the general semaphore: the one-sided synchronisationr~striction

expressible by it is a very common one and comparison of thesolutions with and without general semaphore shows convincingly that its~ouldbe regarded as an adequate tool.

4.3. The Bounded Buffer.

I shall g~ve a last simple example to illustrate the use of thegeneral semaphore. In section 4.1 we have studied a producer and a consumer
coupled via a buffer with unbounded capacity. This is a typically one-sided
restriction: the producer can be arbitrarily far ahead of the consumer, on
the other hand the consumer can never be ahaed of the producer. The relation
becomes symmetric, if the two are coupled via a buffer of finite size, say
N portions. We give the program without any further discussion; we ask thereader to convince himself of the complete symmetry. ("The consumer produces
and the producer consumes empty positions in the buffer".) The value N,
as the buffer, is supposed to be defined in the surrounding universe into
which the following program should be embedded.

"begin integer number of queuing portions, number of empty positions,buffer manipulation;
number of queuing portions:= 0;
number of empty positions:= N;buffer manipulation:= 1;
parbegin
producer: begin
again 1: produce next portion;
P(number of empty positions);P(buffer manipulation);
add portion to buffer;V(buffer manipulation);V(number of queuing portions); go to again 1 end;
consumer: begin
again 2: P(number of queuing portions);P(buffer manipulation);take portion from buffer;V(buffer manipulation);V(number of empty positions);
process portion taken; goto again 2 end
par endend"

5. Cooperation via Status Variables.
In sections 4.1 and 4.3 we have illustrated the use of the general
semaphore. It proved an adequate tool, be it as implementation of a rather
trivial form of interaction. The rules for the consumer are very simple: if
there is something in the buffer, consume it. They are of the same simplicity
as the behaviour rules of the wage earner who spends all his money as soon
as he has been paid and is broke until the next pay day,In other words: when a group of cooperating sequential processes haveto be constructed and the overall behaviour of these processes combined
has to satisfy more elaborate requirements -the community, formed by them,has, as a whole, to be well-behaved in some sense- we can only expect tobe able to do so, if the individual processes themselves and the ways inwhich they can interact will get more refined. We can no longer expect
a ready made solution as the general semaphore to do the job. In general,
we need the flexibility as can be expressed in a program for a general
purpose computer.

We now have the raw material, we can define the individual processes,
they can communicate with each other via the common variables and finally
we have the synchronizing primitives. How we can compose from it what wemight want is, however, by no means obvious. We must now train ourselves to
use the tools, we must develop a style of programming, a style of "parallel
programmirrg 11 I might say.

In advance I should like to stress two points.

We shall be faced with a great amount of freedom. Interaction may
imply decisions bearing upon more than one process and it is not always
obvious, which of the processes should do it. If we cannot find a guiding
priciple (e.g. efficiency considerations), then we must have the courage
to impose some rule in the name of clarity.

Secondly, if we are interested in systems that really work, we shouldbe able to convince ourselves and anybody else who takes the trouble todoubt, of the correctness of our constructions. In uniprogramming one isE'ND123 - 41

already faced with the task of program verification -a task, the difficultyof which is often underestimated- but there one can hope to debug by testingof the actual program.

In our case the system will often have to work

under irreproducible circumstances and from field tests we can hardly expect

any serious help. The duty of verification should concern us right from thestart.

We shall attack a more complicated example in the hope that this will
give usso~eof the experience which might be used as guiding principle.

5.1. An Example of a Priority Rule.

In section 4.3 we have used the general semaphore to couple a producer
and a consumer via a bounded buffer. The solution given there is extendable
to more producers and/or more consumers; it is applicable when the11

portion"is at the same time a convenient unit of information, i.e. when we can regard
the different portions as all being of the same size.

In the present problem we consider producers that offer portions ofdifferent sizes; we assume the size of these portions to be expressed in
portions units. The consumers, again, will process the successive portions
from the buffer and will, therefore, have to be able to process portions,the size of which is not given a priori. A maximum portion size, however,will be known.

The size of the portions is given in information-.units, we assume alsothat the maximum capacity of the buffer is given in information units: thequestion whether the buffer will be able to accomodate the next portion
will therefore depend on the size of the portion offered. The requirement,
that

11

adding a portion to" and "taking a portion from the buffer" are stillconceivable operations implies that the size of the buffer is not lessthan the maximum portion size.

We have a bounded buffer and therefore a producer may have to wait

before it can offer a portion. With fixed size portions this could only
occur when the buffer was full to the brim, now it can happen, because
free space in the buffer, although present, is insufficient for tr.e portion
concerned.

Furthermore, when we have more than one producer and one of them is
waiting, then the other ones may go on and reach the state that they wish
to offer a portion. Such a portion from a next producer may also be toolarge or it may be smaller and it may fit in the available free space ofthe buffer.

Somewhat arbitrarily, we impose on our solution the requirement,that the producer wishing to offer the larger oortion gets priority overthe producer wishing to offer the smaller portion to the buffer. (Whentwo or more producers are offering portions that happer~ to be of 'the same
size, we just don't care.)

When a producer has to wait, because the buffer cannot accomodate
its portion, no other producers can therefore add their portions until
further notice: they cannot when the new portion is larger (for then it
will also not fit), they may not when the r~ew portion is smaller, for thenthey have a lower priority and must leave the buffer for the earlier request.

Suppose at a moment a completely filled buffer and three producers,
waiting to offer portions of 1, 2 and 3 units respectively. When a consumer
now consumes a five-unit portion, the priority rule implies that the producers with the 2-unit portion and the 3-unit portion respectively will get
the opportunity to go on and not the one offering the 1-unit portion. It is
not meant to imply, that then the 3-unit portion will actually be offered
before the 2-unit portion!

We shall now try to introduce so-called "status variables 11 for thedifferent components of the system, with the aid of which we can characterize
the state of the system at any moment. let us try.

E'ND123 - 43

For each producer we introduce a variable named ''desire''; this variable
will denote the number of buffer

units needed for the portion it could not

add to the buffer. As this number is always positive, we can attach to"desire = 0" the meaning, that no request from this buffer is pendi'lg.

Furthermore we shall introduce for each producer a private binary "producer
semaphore".

For the buffer we introduce the binary semaphore "bufman'', which takes

care of the mutual exclusion of buffer manipulations in the widest sense(i.e. not only the adding to and taking from the buffer, but also inspection
and modification of the status variables concerned.)

Next we need a mechanism to signal the presence of a next portion to
the consumers. As soon as a next portion is in the buffer, it can be consumed
and as we do not care, which of the consumers takes it, we can ~ope, thata general semaphore "number of queuing portions" will do the job. (Note,that it counts portions queuing in the buffer and not number of filled
information units in the buffer.)

Freecoming buffer space must be signalled back to the producers, but
the possible consequences of free coming buffer space are more intricate andwe cannot expect that a general semaphore will be adequate. Tentatively we
introduce an integer status variable "number of free buffer units". Note,that this variable counts units and not portions.

Remark.

The value of "number of free buffer units" will at most be

equal to the size of the buffer diminished by the total size of the portions
counted in "number of queuing portions", but it may be less! I refer to theprogram given in section 4.3; there the sum"number of queuing portions + number of empty positions"is initially (and usually)= N, but it may be= N- 1, because the P-operation
on one of the semaphores always precedes the V-operation on the other. (Verify,that in the program of section 4.3 the sum can even be = N - 2 and that thisvalue can even be lower, when we have more producers and/or consumers.) Here
we may expect the same phenomenon: the semaphore 11 number of queuing portians 11

EWD123- 44

will count the portions actually and completely filled and still unnoticed

by the consumers, "number of free buffer units" will count the completely
free, unallocated units ir the buffer. But the units which have been reserved
for filling, which have been granted to a (waiting) producer, without alreadybeing filled, will not be counted in either of them.

Finally we introduce the integer "buffer blocking", the value of whichequals the number of quantities "desire 11 ? that are positive. Obviously,
this variable is superfluous; it has been introduced as a recognition of oneof our earlier remarks, that as soon as one of the desires is positive, nofurther additions to the buffer can be made, until further notice. At thesame time this variable may act as a warning to tre consumers, that sucha "further notice" is wanted.

We now propose the following program, written for N producers and M
consumers.

("N 11 ,

11

M11 ,

11

Buffer size" and all that concerns the buffer isassumed to be declared in the surroundings of this program.)"beginintegerarray desire, producer semaphore [ 1 : N];integernumber of queuing portions, number of free buffer units,
buffer blocking, bufman, loop;

for .loop:= 1 ~ 1 until N do
begin desire[ loop]::::::: 0; producer semaphore[ loop]:= 0 end;
number of queuing portions:= 0;
number of free buffer units:= Buffer size;
buffer blocking:= 0; bufman:= 1;
par beginproducer 1 :be~ in •••••••••••••••••••••••••~;

producer n: begin

integer portion size;

again n: produce next portion and set portior size;P( bufman);if buffer blocking

0 andnumber of free buffer units> portion sizethen

El<D123 - 45

number of free buffer units:~
number of free buffer units - portion size
else
begin buffer blockin:~ buffer blocking - 1;desire[ n J:~ portion size j v( bufman) j
P(producer semaphore[n]); P(bufman) end;
add portion to buffer; V(bufman);
V(number of queuing portions); qoto again n
end·
-.-'
producer N: begin ••••••••••••••••• end;
cof"lsumer 1: b;gin ................. end;
consumer m: begin

integer portion size, n, max, nmax;

again m: P(number of queuing portions); P(bwfman);take portion from buffer and set portion size;
number of free buffer units:=
number of free buffer units + portion size;
test:

if buffer blocking > 0 ~begin

max:::::: 0;
for n :::::::: 1 step 1 until N do
begin

if max < desire[ n] ~begin max:::::: desire[n]; nmax::::::: n end~;
if max~ number of free buffer units thenbegin number of free buffer units::::::
number of free buffer units - max;
desire[nmax]::::::: 0;
buffer blocking:= buffer blocking- 1;

V(producer semaphore[nmax]); goto testend;
V(bufman); process portion taken; goto again m
end·
-.-·
consumer M: begin ••••••••••••••••• end
par endend"

EWD123- 46

In the outermost block the common variables are declared and initialized;
I hope -and trust that thispa~tof the program presents no difficulties tothe reader that has followed me until here.

Let us first try to under5tand the behaviour of the producer. When it
wishes to add a new portion to the buffer, there are essentially two cases:
either it can do so directly, or not. It can add directly under the combined
condition:"buffer blocking ::::: 0 and numbei of fTee buffeT units::=:: portion size";

if so, it will decrease "number of free buffer Lmits" and -dynamicallyspeaking in the same critical section- it will add the portion to the buffer.
The two following V-operatians (the order of which is immaterial) close thecritical section and signal the presence of the next portion to the combined
consumers. If it cannot add directly, i.e. if (either)"buffer blocking > 0 £E. number of free buffer units< portion size"(or both), then the producer decides to wait, "to go to sleep", and delegatesto the combined consumers the task to wake it up again in due time. The fact

J

that it is waiting is coded by ''desire[ n > 0 11 , "buffer blocking" is increasedby 1 accordingly. After all clerical operations on the common variables havebeen ca1:1:ied out, the cTit.ical section is left \by "'V\bufman)") and the

producer initiates a P-operation on its private semaphore. When it has completed
this P-operation, it reenters the critical section, merges dynamically withthe first case and adds the portion to the buffer. (See also the consumer inthe second program of section 4.2, where we have already met the cutting
open of a critical section.) Note that in the case of waiting, the producer
has skipped tile dec:rease of ,.number of free buffer units". Note also, thatthe producer initiates the P-operation on its private semaphore at a moment,that the latter may already be= 1, i.e. this P-operation, again, is only
a potential delay.

Let us now inspect, whether the combined consumers fulfill the tasks
delegated to them. The p:resence of a next portion is co:rrectly signalled tothem via the general semaphore "number of queuing portions" and as the
P-operation on it occurs outside any critical section, there is no dangerof consumers not initiating it. After this P-operation, the consumer enters

E',ID1 23 - 4 7

its critical section, takes a portion and increases the number of freebuffer units. If ''buffer blocking= ou holds, the following compound statement

is skipped completely and the critical section is left immediately; this iscorrect, for "buffer blocking = 0 11 means that none of the quantities "desire"is positive, i.e. that none of the producers is waiting for the free space
just created in the buffer. If, however, it finds "buffer blocking > 0",it knows that at least one of the producers has gone to sleep and it will
inspect, whether one or more producers~ave

to be woken up. It looks forthe maximum value of ''desire''· If this is not too large, it decides, thatthe corresponding producer has to go on. This decision has three effects:a)the ''number of free buffer units'' is decreased by the number of units
desired. Thus we guarantee that the same free space in the buffer cannot be
granted to mare than one producer. Furthermore this decrease is in accordancewith the producer behaviour.

b)"desire" of the producer in question is set to zero; this is correct,
far its request has-now been granted; buffer blocking is decreased by 1
accordingly.

c)a V-operation on the producer semaphore concerned wakes the sleeping
producer.

After that, control of the consumer returns to "test" to inspect,
whether more sleeping producers should be woken up. The inspection process
can end in one of two ways: either there are no sleeping producers anymore("buffer blocking = 0) or there are still sleeping processes, but the freespace is insufficient to accommodate tre maximum desire. The final value of"buffer blocking" is correct in both cases. After the waking up of the
producers is done, the critical section is left.

5.2. An Example of Conversations.

In this section we shall discuss a more complicated example, in which
one of the cooperating processes is not a machine but a human being, the"operator".

The operator is connected with the processes via a so-called "semi-duplex
channel'' (say ''telex connection''). It is called a duplex channel because it
conveys information in either direction: the operator can use a keyboard totype in a message for the processes, the processes can use the teleprinterto type out ~message for the operator. It is called a semi-duplex channel,
because it can only transmit information in one direction at a time.

Let us now consider the requirements to the total construction. (I admit,that they are somewhat simplified. I hope, that they are sufficiently
complicated to pose to us a real problem, yet sufficiently simple as not
to drown the basic pattern of our solution in a host of inessential
details. The trees should not prevent us from seeing the forest!)

We have N identical processes (numbered from 1 through N) and essentiallythey can ask a single question, called "Q1", meaning "How shall 1 go on?", towhich the operator may give one of two possible answers, called "A1" and "A2".
We assume, that the operator must know, which of the processes is asking thequestion -as his answer might depend on this knowledge- and we therefore
specify, that the i-th process identifies itself when posing the question;
we indicate this by saying that it transmits the question 11 Q1(i)". In a sense
this is a consequence of the fact, that all N processes use the same communication channel.

A next consequence of this channel sharing between the different processes
is that no two processes can ask their question simultaneously: behind thescenes some form of mutual exclusion must see to this. If only Q1-questions
are mutually exclusive, the operator may meet the following situation: aquestion -say "Q1 (3)- is posed, but before he has decided how to answer it,a next question -say"Q1 (7)"- is put to him. Then the single answer "A1" isno longer sufficient, because now it is no longer clear, whether this answer
is intended for "process 7" or for "process 3"· This could be overcome byE'w'C123 - 49

adding to the answers the identification of the process concerned, say,''A1(i)'' and ''A2(i)'' with the appropriate val~e of i.

But this is only one way of doing it: an alternative solution is tomake the question, fallowed by its answer, together a critical occurence:
it relieves the operator from the task to identify the process and wetherefore select the latter arrangement. Sa we stick to the answers ''A1'' and"A2". We have two kinds of conversations "01(i), A1' 1 and "Q1(i), A2" and thenext conversation can only be initiated when the previous one has been
completed.

We shall now complicate the requirements threefold.

Firstly, the individual processes may wish to use the communication
channel for single-shot messages -"M(i)" say- which do not require anyanswer from the operator.

Secondly, we wish to give the operator the possibility to postpone ananswer. Of course, he can do so by just not answering, but this would havethe undesirable effect,that the communication channel remains blocked forthe other N - 1 processes. We introduce a next answer "A3", meaning: "Thechannel becomes free again, but the conversation wi~h the process concerned
remains unfinished." Obviously, the operator :nust have the opportunity toreopen the conversation again. He can do so via 11 A4(i) 11 or "A5(i)", where11

i 11 runs from 1 through N and identifies the process concerned, where "A4"

indicates that the process should continue in the same way as after 11 A1",
while 11 A5 11 prescribes the reaction as to "A2". Possible forms of conversation
are now:a)"Q1(i), A1"b)"Q1(i), A2"c)"01 (i)' A3""A4(i)"d)"Q1(i), A3""A5(i)"

As far as process i is concerned a) iS equivalent with c) and b) is equivalent
with d).

The second requirement has a profound influence: without it -i.e. onlyE·~·D 123

11

- 50

A1tt and "A2" permissible answers- the process of incoming message interpre-

tation can always be subordinate to one of the N processes, viz. the one,that has put the question: this can wait for an answer and can act accordingly.
We do not know beforehand, however, when the message "A4(i)" or 11 A5(i)" comes
and we cannot delegate the interpretation of it to the i-th process, because
the discovery that this incoming message is concerned with the i-th process
is part of the message interpretation itself!

Thirdly, A4- and A5-messages must have priority over Q1- and M-messages,
i.e. while the communication channel is occupied (in a Q1- or M-message),processes might reach the state, that they want to use the channel, but also
the operator might come to this conclusion. As soon as the channel becomes
available, we wish, that the operator can use it and that it won 1 t be snatchedaway by one of the processes. This implies that the operator has a means to
express this desire -a rudimentary form of input- even if the channel
itself is engaged in output.

We assume thata) the operator can give externally a"V(incoming message)",which he can use to announce a message (A 1 , A2, A3, A4, or A5)b) can detect by the machines reaction, whether the message is accepted orignored.

Remark.

The situation is not unlike the school teacher shouting "Nowchildren, listen! 11 • If this is regarded as a normal message, it is nonsensical:
either the children are listening and it is therefore superfluous, or they are
not listening, and therefore they do not hear it. It is, in fact a kind of"meta-message", which only tells, that a normal message is coming and whichshould also penetrate i f the children are not listening (talking, for instance).

This priority rule may make the communication channel reserved for anannounced A4 - or A5 message. By the time that the operator gets the opportunity
to give it, the situation or his mood may have changed, and therefore wethe list of answers with

11

A6

11

exte~d-the dummy opening- which enables the operator

EWD123 - 51

to withhold, upon further consideration, the A4 or A5.

A final feature of the message interpreter is the applicability test.
The operator is a human being and we may be sure that he will make mistakes.
The states of the message interpreter are such that at any moment, not all
incoming messages are applicable; when a message has been rejected as nonapplicable, the interpreter should return to such a state that the operator
can now give the correct version.

Our attack will be along the following lines:
1)

Besides theN processes we introduce another process, called "message

interpreter"; this is done because it is difficult to make the interpretationof the messages "A4 11 , "A5 11 and

2)11

A6 11 subordinate to one of the N processes ..

Interpretation of a message always implies, besides the message itself,

a state of the interpretsr.(In the trivial case this is a constant state,
viz. the willingness to understand the message.) We have seen that not all
incoming messages are always acceptable, so our message interpreter will bein different states. We shall code them via the (common) state variable
11

comvar 11 • The private semaphore, which can delay the action of the message

interpreter, is the semaphore "incoming message", already mentioned.

3)

For the N processes we shall introduce an array "procsem" of private

semaphores and an array11

procvar 11 of state variables, through which thethe different processes can communicate with each other, with the message
interpreter and vice versa.

4)

Finally we introduce a single binary semaphore "mutex 11 whicb caters

for the mutual exclusion during inspection and/or modification of thecommon variables.

5)

We shall use the binary semaphore 11 mutex 11 only for the purpose justdescribed and never, say, will 11 mutex : : : : Qrt be used to code, that the channel
is occupied4 Such a convention would be a dead alley in the sense that thetechnique used would fall into pieces as soon as the N processes would have
two channels (and two operators) at their disposal. We aim to make thecritical sections, governed by 11 mutex 11 rather short and we won't shed a tearif same critical section is shorter than necessary.

Well, the above five points, articles of faith, I might say, are of somehelp and I hope that in viewof our previous experiences they seem a set of

reasonable principles. I do one part of my job if I present a solution alongthe lines just given and show that it is correct. I would do a better job
if I could show as well, how such a solution is found. Admittedly by trial
and error, but even so, we could try to make the then prevailing guiding
priciple (in mathematics usually called "The feeling of the genius")
somewhat more explicit. For we are still faced with problems:a)what structure should we give to the N + 1 processes?

b)what states should we introduce (i.e. how ~any possible values should

the state variables have and what should be their meanings)?

The problem (both in constructing and in presenting the solution) is,that the twopoin~sjust mentioned are interdependent. For the values ofthe state variables have only an unambiguous, describable meaning, when"mutex""' 1" holds, j.e. rone of the processes is inside a critical section,in which they are subject to change. In other words: the conditions underwhich tr.e meaning of ti-e state variotll" valt':::s should te a1=.r.l :..cable ison~yknown, when the programs are finished, but we can only make tre programs

if we know "'':hat inspections of and operations on tl-,e state variables areto be performed. In my experience one starts with a rough picture of bothprograms and state variables, one t~en starts to enumerate the different
states and then tries to build the programs. Then two different things
may happen: either one finds that one has irtroduced too many states or
one finds that -having overlooked a need for cutting a critical section
into parts- one has not introduced enough of them. One modifies the states
and then the program and with luck and care the design process converges.
Usually I found myself content with a working solution and I did not botherto minimize the number of states introduced.

In my experience it is easier to conceive first the states (being
statically interpretable) and then the programs. In conceiving the states
we have to bear three points in mind.

a)State variables should have a meaning when mutex is = 0; on the other

hand a process must leave the critical section before it starts to wait fora private semaphore. We must be very keen on all those points where a process
may have to wait for something more complicated than permission to complete"P(mutex)",

EWD123- 53b)

The combined statevariables specify the total state of the system.

Nevertheless it helps a great deal if we can regard some state variable as''belonging to that and that process''· If some aspect of the total stateincreases linearly with N, it is easier to conceive that part as equallydivided among the N processes.

c)

If a process decides to wait on account of a certain (partial) state,each process, that makes the system leave this partial state should inspect
whether on account of this change, some waiting process should go on. (Thisis only a generalization of the principle, already illustrated in The Sleeping
Barber.)

The first two points are mainly helpful in the conception of the different
states, the last one is an aid, to make the programs correct.

Let us now try to find a set of appropriate states. We starts with theelement

11

procvar[i]", describing the state of process i.

procvar[ i) = 0

This we call ''the homing position". It will indicate that none of thefollowing situations applies, that process i does not require any special
service from either the message interpreter or one of the other processes.

procvar[i) = 1"On account of non-availability of the communication channel, process
i has decided to wait on its private semaphore." This decision can be taken
independently in each process, it is therefore reasonable to represent itin the state of the process. Up t i l l now there is no obvious reason to
distinguish between waiting upon availability for a M-message and for a
Q1-question, so let us try to do it without this distinction.

procvar[ i] = 2"Question "01 (i) 11 has been answered by 11 A3", viz .. with respect toprocess i the operator has postponed his final decision." The fact of the
postponement must be represented because it can hold far an undefinitely
long period of time (observation a); it should be regarded as a state variable

E'dD123 -54of the process in question as it can hold in N-fold (observation b). Simultaneously, "procva:r[i] ::: 2" will act as applicability criterion for theoperator messages"A4[ i ]" and 11 A5[ i ]n.

procvar[i] = 3""Q1[i]" has been answered by "A1" or by 11 A3"--- "A4[i] 11 • 11

procvar[ i] = 4' 1 11Q1 [ i ]" has been answered by "A2" or by "A3 11 -

-

-

11

A5[ i ]"."First of all we remark, that it is of no concern to the individual
process, whether the operator has postponed his final answer or not. The
reader may wonder, however, that the answer given is coded in "procvar", while

only one answer is given at a time. The reason is that we do not know how
long it will take the individual process to react to this answer: before it
has done so, a next process may have received its final answer to the Q1question.

Let us now try to list the possible states of the communication
organisation. We introduce a single variable, called 11 comvar 11 to distinguishbetween these states. We have to bear in mind three different aspects
1)

availability of the communication possibility forM-messages, Q1-questions

and the spontaneous message of the operator.
2)

acceptability -more general: interpretability- of the incoming messages.

3)

operator priority for incoming messages.

In order not to complicate matters immediately too much, we shall startby ignoring the third point. Without operator priority we can see thefollowing states.

comvar = 0"The communication facility is idle", i.e. equally available for bothprocesses and operator. For the processes 11 comvar = 0" means that the communication facility is available, for the message interpreter it means thatan incoming message need not be ignored, but must be of type A4, A5 or A6.

comvar = 1"The communication facility is used for a M-message or a 0.1-question".

E1ND123 -In this period of time the value of "comvar" must be

55

1- 0, because tr:ecommunication facility is not available for the processes; for the message
interpreter it means, that incoming messages have to be ignored.

comvar = 2"The communication facility is rsserved far an A1-,A2- or A3-answer."

When the M-message has been finished, the communication facility becomes
available again, after a Q1-question, however, it must remain reserved. During
this period, characterized by

11

comvar = 2'1 , the message interpreter must

know to which process the operator answer applies. At the end of the answer,
the communication facility becomes again available.

Let us now take the third requirement into consideration. This will leadto a duplication of (certain) states. When

11

comvar == 0" holds, an incoming

message is accepted, when ncomvar = 1 11 , an incoming message must be ignored,
This occurence must be noted down, because at the end of this occupationof the communication facility, the operator must get his priority. We canintroduce a new state:

comvar = 3
11

As 11 comvar

1 11 with operator priority requested."

When the transition to 11 comvar = 3" occurred during a M-message, theoperator could get his opportunity immediately at the end of it; if, however,
the transition to 11 comvar = 3 11 took place during a Q1-question, the priority
can only be given to the operator after the answer to the Q1-question. Therefore,
also state 2 is duplicated:comvar = 4
11

As "comvar

2", with operator priority requested."

Finally we have the state:

comvar = 5"The communication facility is reserved for, or used upon instigation of
the operator," For the processes this means non-availability, for the message
interpreter the acceptability of the incoming messages of type A4, A5 and A6.

EIID123 - 56

Usually, these messages will be announced to the message interpreter while11

comvar 11 is :::=:: 0. If we do nat wish that the entire collection and interpre-

tation of these messages is done within the same critical section, the message
interpreter can break it open. It is then necessary, that "comvar'' isI 0. -de1

may try to use the same value 5 for this purpose: for the processes it justmeans non-availability, while the control of the message interpreter knows
very well, whether it is waiting for a spontaneous operator message (i.e.
11reserved for •• ") or interpreting such a message (i.e. "used upon instigationof..").
Before starting to try to make the program, we must bear in mind point
c: remembering that availability of the communication facility is the great(and only) bottleneck, we must see to it, that every process that ends acommunication facility occupation decides upon its future usage. This isln the processes at the end of the M-message (and not so much at the end of
the Q1-question, for then the communication facility remains reserved forthe answer) and in the message interpreter at the end of each message interpretation.

The proof of the pudding is the eating, let us try, whether we canmake the program. (In the program, the sequence of characters startingwith "comment" and up to and including the first semicolon are inserted
for explanatory purposes only. In ALGOL 60, such a comment is only admitted
only immediately after "begin" but I do not promise, to respect this(superfluous) restriction. The following program should be interpreted tobe embedded in a universe in which the operator, the communication facility
and the semaphore ''incoming message" -initially = o- are defined.

begin

integer mutex, comvar, asknum, loop;
comment The integer 11 asknum 11 is a state variable of the message
interpreter, primarily during interpretation of the answers A1, A2
and A3. It is a common variable, as its value is set by the asking
process.;
integerarray procvar, procsem [ 1N];

EIID123 - 57

for loop:::::: 1 step 1 until N ~begin procvar[ loop]::::: 0; procsem[ loop}= 0 end;

comvar:= 0; mwtex:= 1;

par beginprocess 1:

be~in •••••••••••••••••••• end;

process r;: begin integer i; comment The integer "i 11 is a local variable,

very much like "loop 11 . ;M message:P(mutex);
if comvar = 0 thenbegin comment When the communication facility is available,

it is taken.;comvar:= 1; V(mutex) end
else
begin comment Otherwise the process books itself as sleeping
and goes to sleep.;procvar[n]:= 1; V(mutex); P(procsem[n])comment At the completion of this P-operation,"procsem[n]" will again be

0, but comvar -still

untouched by this process- will be =1 or =3·; end;
send M message;comment Now the process has to analyse, whether the operator(first!) or one of the other processes should get the communication facility or not.; P(mutex);
if comvar :::: 3 then comvar:::::

5~

begin comment Otherwise 11 comvar == 1" will hold and process n
has to look whether one of the other processes is waiting.
Note that 11 procvar[n] -== 0" holds.;.f:g_£ i::::: 1 ~ 1 ~ N ..9E.
begin.if. procvar[i] = 1 thenbegin procvar[i]::::: 0; V(procsem[i]); goto ready

end
end;
comvar:= 0~

ready: V(mutex);

EWDI23- 58

Q1 Question: P(mutex);
if comvar ::::: 0 thenbegin comvar:~ 1; V(mutex) end
else

begin procvar[n]::::: 1; V(mutex); P(pracsem[n]) ~;comment This entry is identical to that of the M message.
Note that we are out of the critical section, neverthelessthis process will set

11

asknum". It can do so safely, for noother process, nor the message interpreter, will access
11

asknum 11 as long as

11

comvar :::: 1" holds.;

asknum::::: n; send question Q1(n);P(mutex);comment "camvar" will be = 1 or :::: 3.;

if comvar::::: 1 then comvar::::: 2 else comvar::::: 4;V(mutex); P(procsem[n]);comment After completion of this P-operation, procvar[n]will be ::::: 3 or = 4. This process can now inspect and resetits procvar, although we are outside a critical section.;
if procvar[n] ~ 3 then Reaction 1 else Reaction 2;
procvar[n]:= 0;comment This last assignment is superfluous.;

end·
-.-·
process N: begin •••••••••••••••••••• end;
message interpreter:
begin integer i;
wait: P(incoming message);P( mutex);
if comvar

1 ~ comvar:= 3;

if comvar

3 thenbegin comment The message interpreter ignores the incoming
message, but in due time the operator will get theopportunity.;V(mutex); go to wait ~;EWDI23 - 59

if comvar "" 2 £E_ comvar : : : 4 thenbegin comment Only A1t A2 and A3 are admissible. The interpretation of the message need not be done inside a
critical section;v( mutex);
interpretation of the message coming in;i f message=

A1 thenbegin procvar[asknum]:= 3; v(procsem[asknum]);
goto after correct answer end;

if message = A2 thenbegin procvar[=sknum]:= 4; v(procsem[asknum]);
goto after correct answer end;
if message = A3 thenbegin procvar[asknum]:::::: 2; goto after correct answer end;

comment The operator has given an erroneous answer
and should repeat the message; goto wait;
after correct answer:

P(mutex);

if comvar = 4 thenbegin comment The operator should now get his opportunity;

comvar:::::: 5; V(mutex); goto wait end;
perhaps comvar to zero: for i:= 1 step 1 until N do
begin if procvar[ i] = 1 ~begin procvar[i]:= 0; comvar:::::: 1;

V(procsem[i]); goto ready end
end;
comvar:= 0;

ready: V(mutex); goto wait
end;comment The cases

11

comvar = 0" and "comvar ~ 5 11

Messages A4, A5 and A6 are admissiblea;

if comvar = 0 then comvar:= 5;comment See Remark 1 after the programa;
V(mutex);interpretation of the message coming in;remain~P(mutex);
if message

begin i:::::::

A4Lproces5 number] then11

process number given in the message 11 ;if procvar[ i] = 2 thenbegin procvar[i]:~ 3; V(procsem[i]);goto perhaps comvar to zero end;
comment Otherwise process not waiting for postponed
answer.; go to wrong message
end;

if message

A5[process number] thenbegin i::::::: "process number given in the message";
if procvar[ i] = 2 thenbegin procvar[i]::::::: 4; V(procsem[i]);goto perhaps comvar to zero end;

comment Otherwise process not waiting for postponed
answer.; goto wrong message
end;
if message = A6 then got a perhaps comvar to zero;wrong message:comment"comvar = 511 holds, giving priority to the operator
to repeat his message.;V ( mutex) ; go to wait

end

parendend

Remark 1. If the operator, while "comvar = 0 11 or "comvar = 5 11
originally holds, gives an uninterpretable (or inappropriate) message, thecommunication facility will remain reserved for his next trial.

Remark 2. The final interpretation of the A4 and A5 messages isdone within the critical section, as their admissibility depends on the stateof the process concerned. If we have only one communication channel and one
operator, this precaution is rather superfluous.

EWD123 - b'

Remark

3. The for-loops in the program scan tre processes inorder, starting by process 1; by scanning them cyclically, starting at anarbitrary process (selected by means of a (pseudo) random number generator)
we could have made the solution moresy~metricalin theN~rocesses.

Remark 4. In this section we have first given a rather thoroughexploration of the possible states and then the program. The reader might
be interested to know that this is the true picture -"a life recording"of the birth of this solution. When I started to write this section, theproblem posed was for me as new as for the reader: the program given is
my first version, constructed on account of the considerations andexplorations given. I hope that this section may thus give a ~int as how
one may find such solutions.

5.2.1. Improvements of the Previous Program.

In section 5.2 we have given a first version of the program; thisversion has been included in the text, not because we are content with it,
but because its inclusion completes the picture of the birth of a solution.
Let us now try to embellish, in the name of greater conciseness, clarity and,may be, efficiency. Let us try to discover in what respects we have made amess of it.

Let us compare the information flows from a process to the message
interpreter and vice versa. In the one direction we have the common variable"asknum" to tell the message interpreter, which process is asking thequestion. The setting arid the inspection of "asknum'' can safely take placeoutside the critical sections, governed by "mutex", because at any momentat most one of the N + 1 processes will try to access "asknum". In the inverse
information flowt where the message interpreter has to signal back to thei-th process the nature of the final operator answer, this answer is codedin "procvar". This is mixing things up, as is showna) by the "procvar"-inspection (whether procvar is = 3 or4), which is

E'ND123- b2

suddenly allowed to take place outside a critical sectionb) by the superfluity of its being reset to zero.

The suggestion is to introduce a new"integer array operanswer[1 :N]"the elements of which will be used in a similar fashion as "asknum". (Anattractive consequence is that the number of possible values of 11 procvar"-the more fundamental quantity(see below)- does not increase any more, if
the number of possible answers to the question Q1 is increased .. )I should like to investigate whether w~ can achieve a greater clarity
by separating the common variables into two (or perhaps more?) distinctgroups, in order to reflect an observable hierarchy in the way in which they
are used. Let us try to order them in terms of "basicness 11 •The semaphore "incoming message" seems at first sight a fairly basic
one, being defined by the surrounding universe. This is, howevert an illusion:

withinthe parallel compound we should have programmed (as N + 2nd process)the operator himself, and the semaphore "incoming message" is the private
semaphore for the message interpreter just as ttprocsem[i]" is for the i-th
process.)

Thus the most basic quantity is the semaphore "mutex" taking care of themutual exclusion of the critical sections.

Then come the state variables "comvar" and "procvar" which are inspected
and can be modified within the critical sections.

The quantities just mentioned share the property that their values
must be set before entering the parallel compound. This property is also
shared by the semaphores "procsem" (and "incoming message", see above), if
we stick to the rules that parallel statements will access common-semaphores
via P- and V-operations exclusively.

(Without this restriction, request for the communication facility
by process n could start with:

E'wD123 - 63

"P(mutex);
if comvar ~ 0 thenbegin comvar:~ 1; V(mutex) end
else
begin procvar[n]:~ 1; procsem[n]:~ 0;V(mutex); P(procsem[n ]) end"

We reject this solution on the further observation, that the assignment"procsem[n]" is void, except for the first time that it is executed; theinitialization of procsem 1 s outside the parallel compound seems therefore
appropriate).

For the common variables, listed thus far I should like to reserve thename "status variables", to distinguish them from the remaining ones,"asknum" and "operanswer", which I should like to call !!transmission variables".

I call the latter "transmission variables" because, whenever one ofthe processes assigns a value to such a variable, the information just stored
is destinated for a well known ''receiving party". They are used to transmit
information between well-known parties.

Let us now turn our attention from the common variables towards the
programs. Within the programs we have learnt to distinguish the so-called"critical sections", for which the semaphore_ 11 mutex" caters for the mutual
exclusion. Besides these, we can distinguish regions, in which relevant
actions occur, such as:

in the i-th process:Region 1 : sending an M-message

Region 2: sending a Q1(i)-question
Region 3: reacting to operanswer[i] (this region is somewhat open~ended)

and in the message interpreter:
Region 4: ignoring incoming messages
Region 5: expecting A1, A2 or A3
Region 6: expecting A4(i), A5(i) or A6

EwD123- 64

We come now to the following picture. 1n the programs we have criticalsections, mutually excluded by the semaphore 11 mutex". The purpose of thecritical sections is to resolve any ambiguity in the inspection and modificationof the remaining state variables,
the purpose of more intricate

inspectio~~'sequencing

and modification performed forpatterns'~of the regions, sequencing

patterns, that make the unambiguous use of the transmission variables possible.
(If one process has to transmit information to another, it can now do 50
via a transmission variable, provided that the execution of the assigning

region is always followed by that of the inspecting region before that of thenext assigning region!)In the embellished version of the program we shall stick to the rulethat the true state variables will only be accessed in critical sections(if they are not semaphores) or via P- and V-operations (if they are semaphores), while the transmission variables will only be accessed in theregions. (In more complicated examples this rule might prove too rigid andduplication might be avoided by allowing transmission variables at least
to be inspected within the critical section. In this example, however,
we shall stick to it.)

The remaining

improvements are less fundamental.

progra~Coding goes more smoothly if we represent the fact of requested
operator priority not in additional values of 11 comvar" but in an additional
two-valued state variable:"Boolean operator priority"(Quantities of type 11 Boolean 11 can take on the two values denoted by 11 true"and "false 11

respe~tively,

viz. the same domain as 11 conditions" such as wehave met in the if-clause.)

Furthermore we shall introduce two procedures; they are declaredoutside the compound and therefore at the disposal of the different
constituents of the parallel compound.

We shall first give a short description of the new meanings of thevalues:_ of the state variables "procvar 11 and "comvar":

EWD123- 63

procvar[i]0

procvar[ i]homing position
waiting for availability of the communication facility
for M or Q1 (i)procvar[i]cornvar2

waiting for the answer "A4(i)" or "A5(i)".
homing position (communication facility free)0communication facility for M or Q1

comvarcomvar2

commun-ication facility for A1 , A2 or A3

comvar3

communication facility for A4, A5 or A6.

We give the program without comments and shall do it in twa stages:
first the program outside the parallel compound and then the constituentsof the parallel compound.

begin integer mutext comvar, asknum, loop;
Boolean operator priority;
integer array pracvar, procsem, operanswer[ 1 :N];procedure M or Q entry(u); value u; integer u;

begin P(mutex);
if comvar ~ 0 thenbegin comvar:= 1; V(mutex) end
else
begin procvar[u]:~ 1; V(mutex); P(pracsem[u]) end
end;
procedure select new camvar value;
begin integer i;
if operator priority thenbegin operator priority:= false; comvar:= 3 end
else
begin ..!£:. i ::::::: 1 step 1 until N do
begin if procvar[i] = 1 ~begin procvar[i]:= 0; camvar:= 1;
V(procsem[i]); goto ready end

comvar:::;:: 0;
ready: end
end;

for loop:= 1 ~ 1 ~ N ~begin procvar[loop]:~ 0; procsem[loop]:~ 0 end;
comvar:= 0; mutex:= 1; operator priority:= false;parbeqin
process 1: be9in •.•••.•••••••••••••. end;

process N • begin •••••••.•••••....••• end;
message interpreter:
begin •••••••••••••••••••• end
parendend

Here the n-th process will be of the form
process n:

be9in

M message:

M or Q entry(n);Region 1:

send M message;P(mutex); select new comvar value; V(mutex);

Q1 question:M or Q entry(n);Region 2:

asknum:~n;send Q1 (n);P(mutex); camvar:= 2; V(mutex); P(procsem[n]);Region 3:

if operanswer[n] ~then Reaction
else Reaction 2;

end

When the message interpreter decides to enter Region 6 it copies, before
doing so, the array 11 procvartt: if an answer A4(i) should be acceptable,
then "procvar[i] ~ 2" should already hold at the moment of announcement of
the answer ..

E1ND123 - t7

message interpreter:J;

begin integer i; integer array pvcopy[ 1: N
wait:

P(incoming message); P(mutex);
if comvar = 1 thenRegion 4:

begin operator priority:= true;

leave:V(mutex); goto wait end;
if comvar ~ 2 then goto Region 6;

Region5:

V(mutex); collect message;
if message ~ A1 and message ~ A2 and message /:. A3 then qoto wait;
i:= asknum;
if message

A1 then operanswer[i]:= 1 else

if message

A2 then operanswer[i]:= 2;P(mutex);

if message = A3 then procvar[i]:::::: 2 else
signal to i:V(procsem[i]);preleave:select new comvar value; goto leave;

Region 6:

if comvar = 0 ~ comvar:= 3;for i:= 1 step 1 until N ~ pvcopy[i]:= procvar[i];V(mutex); collect message;i f message

A6 ~ begin P(mutex); goto preleave end;i f message /:. A4(process number) and message /:. A5(process number) thengoto wait;
i:= ''process number given in the message'';
if pvcopy[i] /= 2 then goto wait;
operanswer[i]:= if message = A4 then 1 else 2;
P(mutex); procvar[i]:= 0; goto signal to iend

As an exercise we leave to the reader the version, where pending requests
for Q1-questions have priority over those for M-messages. As a next extension
we suggest a two console configuration with the additional restriction thatan A4- or A5-message is only acceptable via the console over which the conversation has been initiated. (Otherwise we have to exclude simultaneous, contradicting messages 1'A4(i)" and "A5(i)" via the two different consoles. The solution
without this restriction is left for the really fascinated reader.)EWD123 - 68

5.2.2. Proving the Correctness.

!'l this section title I have used the word "proving 11 in an informal way.

have not defined what formal conditions must be satisfied by a "legal
proof" and I do not intend to do so. When I can find a way to discuss the
program of section 5.2.1, by which I can convince myself -and hopefully
anybody else that takes the trouble to doubt!- of the correctness of theoverall performance of this aggregate of processes, I am content.

In the following "state picture 11 we make a diagram of al the states inwhich a process may fi,.,d itself "for any length of time 1' , i.e. outside
sections, critical to mutex. In arrows we describe the transitions taking
place within the critical sections; accompanying these arrows, we give themodifications of comvar or the conditions, under which the transition
from one state to another is made.

Calling the neutral region of a process before entry into a Region 1
or Region 2: ;1 Region 0", we can give the state picture
Region 0
procvar == 0
comvar /= 0

comvar 0 -- 1

comvar - 1
Region 1 or 2
procvar == 0
Leaving Region 1 can be pictured as:

I

Region 1' procvar

comvar 1 -3

1- 1

operatorpriority

pracvar
1-0

I

Region o, procvar

0J
all procvar /=. 00iLeaving Region 2, with t~e possibility of a delayeda~swer,can be pictured

as:Region 2, procvar

0-2

I waiting for answer, procvar

0 /

A3

A1, A2

comvar 2- 3, 1, 0

comvar 2- 3, 1, 0
jwaiting for answer, procvar
'

1

2

I

comvar 0,3 - 0,1

A4, A5\

Region 3, procvar = 0

Reaction to the answer

Region 0, procvar

0

We can try to do the same for the message inte.rpreter. Here we indicate
along the arrows the relevant occurrences, such as changes of a procvar
and the kind of message. We use "WIM" as abreviation for "Waiting forIncoming Message''·

EI-JD1 23 - 70

"mo~:::moo" I'

!

'

I

Region 0 -- 1 , 2

WIM

Region 1
Region 0-1

WIM· Region o-comvar = 1
no priority

comvar = 0
no priority

Region 1 ' 2

Imessaqe~sage,[ejectedrRegion 4

I
WIM
comvar = 1
priorityend of Regior 2

III

end of Region 2

'--

IN!M

comvar = 2
no priority

comvar = 2
priority

mes' age"'" sage

Region 5
comvar = 2
no priority

Region 5
comvar = 2
priority

Region 22, 3

I
I

'

wrong
message

I

A1 ,

A2,
A3,

WIM

~

I

wrong
message'"comvar = 3
no priority
message
Region 6
comvar = 3
no priority

I

wrong
messageA4, A5 (Region 2- 3, procvar 2- 0)
or A6

!

"

'WIM

A1, A2, A3Region 1
Region 0I

These schemes, of course, teach us nothing new, but they may be a
powerful aid iro the program inspection.

We verify first, that "comvar = 0" represents indeed the homing
position of the communication facility, i.e. available for either entrance
into Region 1 or Region 2 (by one of the processes) or entrance into
Region 6 (by the message interpreter, as result of an incoming message
for which it is waiting).

If comvar = 0 and one of the processes wants to enter Region 1 orRegion 2, or a message comes from the operator, Region 1, 2 or 6 is entered;furthermore this entrance is accompanied by either "comvar:= 1" or "comvar::::: 3"
and in this way care is taken of the mutual exclusion of the Regions 1 , 2
and 6.

The mutual exclusion implies that processes may fail to enter Region
1 or 2 immediately, or that an incoming message must be rejected, comingat an inacceptable moment. In the first case, the process sets "procvar::::: 1 ",in the second case (in Region 4) the message interpreter sets "operator
priority::::: true".

These assignments are only performed unde-r the condition "comvar ~ 0";
furthermore the assignment "comvar::::: 0 11 -only occurring in the procedure"select new comvar value 11 -is only performed provided "non operator priority

and all procvar /: 1". From these two observations and the initial values,
we can conclude:"comvar :::: 0 11 excludes "operator priority" as well as the occurrence of one
or more 11 procvar :::: 1 11 •As all ends of occupation of the communication facility (i.e. theend of Region 1, 5 and 6) call "select new comvar value" we have establisheda) that entrance into the Region 1 , 2 and 6 is only delayed when necessaryb) that such a delay is guaranteed to be resolved at the earliest opportunity.

The structure of the message interpreter shows clearly that

D>D 1 23 - 72

5 only if "comvar

2"b) it can only execute Region 5 if "comvar

2"a) it can execute Regionc) executior. of Region

5 is the only way to make comvar agai:1 f 2.

The only assignment "comvar:= 2 11 occurs at the end of Region 2. As

a result each Region 2 can only be followed by a Region

5 and, conversely,

each Region 5 must be preceded by a Region 2. This sequencing allows us
to use the transmission variable "asknum 11 , which is set in Region 2 andinspected in Region

5.

For the uses of the transmission variables "operanswer 11 an an2logous

analysis can be made. Region 2 will be followed by Regiof"l5 (see above);

if here the final answer (A1 or A2) is interpreted, operanswer[i] is set

before 11 V(procsem[i])", so that the transmission variablef-) asbeen setproperly before the process can (and will) enter Region 3, where its"operanswer" will be inspected. If in Region 5 the answer A3 is detected,
the message interpreter set for this process "procvar[i]::::: 2 11 , thus allowing
once in Region 6. the answer A4 or A5 for this process. Again

11

V(procsem[i])n

is only performed after the assignment to operanswer. Thus we have verified
thata) operanswer is only set once by the message interpreter after a request
in Region 2.
b) this operanswer will only be inspected in the following Region 3 after
the request to set it has been fulfilled (in Region 5 or Region 6).
This completes the soundness of the use of the transmission variables"aperanswer".

Inspection of the message interpreter (particularly the scheme of its
states) showsa) that a rejected message (Region 4) sooner or later is bound to giverise to Region 6b) that wrong messages are ignored, giving the operator the opportunity
to correct.

By the above analysis we hope to have created sufficient confidence

E'tJD123 - 73

in the correctness of our construction. The analysis followed the steps
already hinted at in section 5.2.1: after creation of the critical sections(with the aid of mutex), the latter are used to sequence Regions properly,
thanks to which sequencing the transmission variables can be used unambiguously.

6. The Problem of the Deadly Embrace.

In the introductory part of this section I shall draw attention to arather logical problem that arises in the cooperation between various
processes, when they have to share the same facilities. We have selected
this problem for various reasons. Firstly it is a straightforward extensionof the sound principle that no two persons can use a single compartment ofa revolving door simultaneously. Seondly, its solution, which I regard as
non-trivial and that will be given in section 6.1, gives us a nice example
of more subtle cooperation rules than we have met before. Thirdly. it gives
us the opportunity to illustrate (in section 6.2) a programming techniqueby which a further gain in clarity can be achieved.

Let me first give an example of the kind of sharing I have in mind.

As "processes" we might take 11 programs", describing some computational
process to be performed by a computer. Execution of such a computational
process takes time, during which information must be stored in the computer.
We restrict ourselves to thoses processes of which is known in advance1) the maximum demand on storage spaceand2) that the computational process will end, ·provided that storage spacerequested by the process will be put at the disposal of the computational
process. The ending of the computational process will imply that its demandon storage space will reduce to zero.

We assume that the available store has been subdivided into fixed size
"pages' 1 which, from the paint of view of the programs can be regarded as
equivalent.

The actual demand on storage space, needed by a process, may be a function

varying in time as the process proceeds -subject, of course, to the a priori
known upper bound. We assume that the individual processes request fromand return to "available store" in single page units. With 11 equivalence 11(see the last word of the previous paragraph) is meant that a process,requiring a new page only asks for "a new page 11 but never for a special one
or one out of a special group.

We now request that a process, once initiated, will get the opportunity-sooner or later- to complete its action and reject any organization inwhich it may happen that a process may have to be killed half way its
activity, thereby throwing away the computation time already invested init.

If the computer has to perform the different processes one after theother, the only condition that must be satisfied by a process is that its
maximum demand does not exceed the total storage capacity.

If, however, the computer can serve more than one process simultaneously,
one can adhere to the rule that one only admits programs as long as the sumof their maximum demands does not exceed the total storage capacity. Thisrule, safe though it is, is unnecessarily restrictive, for it means thateach process effectively occupies its maximum demand during the complete
time of its execution. When we consider the following table (in which weregard the processes asprocess

11

borrowing" pages from available store)

present loan

maximum demand

P1

00

40

P2

60

20

available store

100

further claim

40
40

+

60

40

(a total store of 100 pages is assumed), we have a situation in which isstill nothing wrong. If, however, both process request their next page andthey should bpth get it, we should get the following situation:
process

maximum demandpresent loar

further claim

P1

00

41

39

P2

60

_ _,2o.:1_ +39

available store

100

62

38

E'ND123 - 75

This is an unsafe situation, for both processes might want to realize
their full further claim before returning a single page to available store.
Soeach of them may first 11eed a further 39 pages, while there are only 38

available.

This situation, when one process can only continue provided tre otherone is killed first, is called 11 The Deadly Embrace 11 • The problem to be solved
is: how can we avoid the danger of the Deadly Embrace without being unnecessarily restrictive.

6.1. The Banker's Algorithm.

A banker has a finite capital expressed in florins. He is willing toaccept customers, that may borrow florins from him on the following conditions.
1.

The customer makes the loan for a transaction that will be completed

in a finite period of time.
2.

The customer must specify in advance his maximum "need" for florins

for this transaction.

3.

As long as the "loan" does not exceed the "need" stated in advance,

the customer can increase or decrease his loan florin wise.
4.

A customer may not complain, if he asks for an increase of thecurrent loan and receives from the banker the answer "If I gave you theflorin you ask for you would not exceed your stated need and therefore youare entitled to a next florin. At present, however, it is somewhat inconvenient
for me to pay you, but I promise to send you the florin in due time."

5. His guarantee that this moment will indeed arrive is founded on thebanker's cautiousness 2nd the fact that his co-customers are subjected tothe same condition as he: that as soon as a customer has got the florin heasked for he will proceed with his transactions at a non-zero speed, i.e.
within a finite period of time he will ask for a next florin or will return
a florin or will finish the transaction , which implies that his complete
loan has been returned (florin by florin).

The primary questions area) under which conditions can the banker make the contract with a newcustomer?

b) under which conditions can the banker pay a (next) florin to a requestingcustomer without running into the danger of the Deadly Embrace?

The answer to question a) is simple: :,e can accept any customer, whosestated need does not exceed the banker's capital.

b) we introduce the following terminology.

To answer question

The banker has a fixed "capital" at his disposal; each new customer
states in advance his maximum ''need" and for each customer will hold''need[i] ~ capital''(for all'.
ljo

The current situation for each customer is characterized by his "loan".
Eacr loan is initially= 0 and shall satisfy at any instant11

0 :::=: laan[i] :::=: need[i]"(for all i).

A useful quantity to be derived from this is the maximum further "claim",

given by"claim[i]need[i]- loan[i]"(for all i).

Finally the banker notes the amount in "cash", given by"cash
Obviously

capital - sum of the loan's".
"0 ~ cash < capital"

has to hold.

In order to decide, whether a requested florin can be paid to thecustomer, the banker essentially inspects the situation that would arise
if he had paid it. If this situation is "safe", then he pays the florin,
if the situation is not "safe", he has to say: "Sorry, but you have to wait.".

Inspection, whether a situation is safe amounts to inspection, whether
all customer transactions can be guaranteed to be able to finish. The algorithm
starts to investigate whether at least one customer has a claim not exceeding
cash. If so, this customer can complete his transactions and therefore thealgorithm investigates the remaining customers as if the first one had finishedand returned its complete loan. Safety of the situation means, that alltransactions can be finished, i.e. that the banker sees a way of getting all

E'ND123 - 77

f-ris money back.

If the customers are numbered from 1 through N, the routine inspecting
a situation can be written as follows:11

integer free money; Boolean safe; Boolean array finish daubtful[1 :N];
free money:= cash;L:

far i::::;

step

until N do finish doubtful[i]:= true;

for i::o::::~1~Ndobegin if finish doubtful[i] and claim[i) =::free money thenbegin finish doubtful[i]:= false;
free money:= free money + loan[i]; gato L

end
end;

if free money·capital~safe::::c: true else safe::::::: false''

The above routine inspects any situation. An improvement of the
Algorithm has been given by L .Zwanenburg, who takes into account that the

only situations to be investigated are those, where, starting from a safe
situation, a florin has been tentatively given to customer[j]. As soon as"finish doubtful[j ]:::::: false" can be executed the algorithm can decidedirectly on safety of the situation, for apparently this te~pted payment
was reversible! This short cut will be implemented in the program in thenext section.

6.2. The Banker's Algorithm Applied.
In this example, the florins are processes as well. (Each florin, say,
represents the use of a magnetic tape deck; the loan of a florin is then thepermission to use one of the tape decks.)

We assume, that the customers are numbered from 1 through N and that theflorins are numbered from 1 through M. Each customer has a variable "florin
number" in which, after each granting of a florin, it can find the number ofthe florin it has just borrowed; also each florin has a variable "customer
number" in which it can find by which customer it has been borrowed.

EWD123 - 78

Each customer has a state variable 11 cusvar", where "cusvar = 1 11 means"I am anxious to borrow.'' (otherwise
variable "flovar", where

1111cusvar = 0); each florin ~as a state

flovar = 1" means "I am anxious to get borrowed,

i.e. I am in cash.'' (otherwise "flovar = 0"). Each customer has a binary

semaphore "cussem", each florin has a binary semaphore 11 flosem 11 , which
will be used in the usual manner.

We assume that each florin is borrowed and returned upon customer indi-

cation, but that he cannot finish the loan of a florin immediately. After thecustomer has indicated that he has no further use for this florin, the florin
may not be instantaneously available

for a next use. It is, as if thecustomer can say to a borrowed florin "run home to the banker". The actual
loan will on·ly be ended after the florin has indeed returned into cash: of its
return into the banker's cash it will signal the customer from which it came
via a customer semaphore "florin returned". A P-operation on this semaphoreshould guard the customer for an inconscious overdraft. Before each florin
request the customer will perform a P-ope ration on its "florin returned"; theinitial value of ''florin returned" will be "= need".

We assume that the constant integers "N" and "M'' (=capital) and theconstant integer array "need" are declared and defined in the universe inwhich the following program is embedded.

The procedure "try to give to" is made into a Boolean procedure, thevalue of which indicates whether a delayed request for a florin has been
granted. In the florin program it is exploited that returning a florin may
at most give rise to a single delayed request now being granted. (If more than
one type of facility is shared under control of the banker, this will no longer
hold. Jumping out of the for loop

to the statement labeled ''leave" at theend of the florin program is then not permissible.)f1ND123 -79

begin integer array loan, claim, cussem, cusvar, florin number, florin
returned[ 1 : N],flosem, flovar, customer number[1:M];

integer mutex, cash, k;
Boolean procedure try to give to (j); value j; integer j;
begin if cusvar[j] = 1 thenbegin integer i, free money;
Boolean array finish doubtful[ 1 :N];

free money:= cash - 1;

claim[j]:= claim[j]- 1; loan[j]:= loan[j] + 1;

LO:

for i:::::::

until N do finish doubtful[i]:= true;

for i:=

until N do

begin if finish doubtful[i] and claim[i] :S" free money thenbegin i f i ,j j thenbegin finish doubtful[i]:= false;

free money:= free money + loan[i];goto LO
end
else
begin comment Here more sophisticated ways forselecting a free florin may be implemented;
i:= 0;
L1:

i:= i + 1; if flovar[i]florin number[j]:= i;customer number[i]:= j;cusvar[j]:= 0; flovar[i]:= 0:
cash:= cash - 1;
try to give to:= true;V(cussem[j]); V(flosem[i]); goto L2
end
end
end;

claim[j J:= claim[j] + 1; loan[j J:= loan[j] - 1
er'!d;

L2:

__

end•,

try to give to:= false;

E'"'D123 - 80

mutex:= 1; cash:= M;

for k:= 1 ~ 1 until N do

begin loan[k]:= 0; cussem[k]:= 0; cusvar[k]:= 0; clai~[k]:= need[k];florin returned[k]:= need[k]end;for k:= 1 step 1 until M !1£.

begin flosem[k]:= 0; flovar[k]:=end;parbeqin
be~ in •••• ••• ••••••••••••• end;

customer 1:

customer N: begin •••••••••••••••••••• end;

florin 1 :begin •••••••••••••••••••• end;

florin M:

begin •••••••••••••••••••• end

parendend

In customer ''n", the request for a new florin consists of the following

sequence of statements:"P( florin returned[ n ]) ;P(mutex);cusvar[n]:= 1; try to give to (n);V(mutex);
P(cussem[n])"after completion of the last statement "florin number[n]" gives the identityof the florin just borrowed, the customer has the opportunity to use it andthe duty to return it in due time to the banker.

EwD1 23 - 81

The structure of a florin is as follows:
florin m:

begin integer h;start:P(flosem[m]);"Now "customer number[m]" identifies the customer that has borrowed it.
The florin can serve that customer until it has finished the task
required from it during this loan. To return itself to the cosh, theflorin proceeds as follows:"

claim[ customer number[m]]:= claim[ customer number[m]] + 1;
loan[customer number[m]]:= loan[ customer number[m]] - 1;

flavar[m]:= 1; cash:= cash + 1;
V(florin returned[customer number[m]]);for h:= 1 ~ 1 until N do
begin i f try to give to(h) then gato leave end;

leave:V(mutex);
gota startend

Remark.

Roughly speaking a succesful loan can only take place when two

conditions are satisfied: the florin must be requested and the florin must
be available. In this program the mechanism of cusvar and cussem is also
used (by the customer), when the requested florin is immediately available,
likewise the mechanism of flovar and flosem is also used (by the florin)
if, after its return to cash, it can immediately be borrowed again by awaiting customer. This programming technique has been suggested by C.Ligtmans
and P.A.Voorhoeve, and I mention it because in the case of more intricate
rules of cooperation it has given rise to a simplification that proved to
be indispensable. The underlying cause of this increase in simplicity itthat the dynamic way tnrough the topological structure of the program nolonger distinguishes between an actual delay or not, just as in the caseof the P-operation itself.

EWDI23 - 82

7. Conludinq Remarks.

In the literature one sometimes finds a sharp distinction between"concurrent programming" -more than one central processor operating on thesame job- and "multiprogramming" -a single processor dividing its time

between different jobs-. I have always felt that this distinction was

rather artificial and therefore confusing. In both cases we have, macroscopically speaking, a number of sequential processes that have to cooperatewith each other and our discussions on this cooperation apply equally wellto "concurrent programming" as to ''multiprogramming" or any mixture of thetwo. What in concurrent programming is spread C'Jt in space (c.q. equipment)

is in multiprogramming spread out i~ time: the two present themselves as
different implementations of the same logical structure and I regard thedevelopment of a tool to describe and form such structures themselves, i.e.
independent of these implementational differences, as one of the major
contributions of the work from which this monograph has been born. As a
specific example of this unifying train of thought I should like to mention-for those that are only meekly interested in multiprocessors, multiprogramming and the like- the complete symmetry between a normal sequential computeron the one hand and its periferal gear on the other (as displayed, for instance,in Section 4.3: "The Bounded Bufferu).

Finally I should like to express, once more, my concern about thecorrectness of programs, because I am not too sure, whether all of it isduly reflected in what I have written.

If I suggest methods by which we could try to attain a greater security,then this is of course more psychology than, say, mathematics. I have thefeeling that for the Human Mind it is just terribly hard to think in terms
of processing evolving in time and that our greatest aid in controling themis by attaching meanings to the values of identified quantities. For instance,in the program sectionLO:"i:= 10;x:= sqrt(x); i:= i - 1;
if i > 0 then gato LO"

E\iD123 -83

we conclude tt-,at the operation "x::::::sqrt(x)" is repeated ten times, but I
have

t~e

impression trat we can do so by attaching to"i" the meaning of''the number of times that the operation "x:=sqrt(x)'' still has to be repeated". (I know that in discussing program verification, Dr .P .Naur has

i'ltroduced the term "the general snapshot"; in all probability we have herea trivial example of it.) But we should be aware of the fact that such atimeless meaning (a statement of fact or relation) is not permanently
correct: immediately after the execution of "x:=sqrt(x)" but before that of
the subsequent "i:= i - 1" the value oftimes that the operation

11"i" is "one more than the number ofx:= sqrt(x)" still has to be repeated". In otherwords: we have to specify a~ what stages of the process such a meaning isapplicable and, of course, it must be applicable in every situation where
we rely on this meaning in the reasoning that convinces us of the desired
overall performance of the program.

In purely sequential programming, as in the above example, the regionsof applicability of such meanings are usually closely connected with placesin the program text (if not, we have just a tricky and probably messy program).
In multiprogramming we have seen -in particular in Section 5.2.1- that it isa worth-while effort to create such regions of applicabili~y of meaning very
consciously. The recognition of the hierarchical difference between thepresence of a message and the message itself, here forced upon us, might givea clue even to clearer uniprogramming.

For example. if I am married to one out of ten wives, numbered fromthrough 10, this fact may be represented by the value of a variable "wifenumber 11 , associated with me. If I may also be single, it is a commonly used
programmer 1 s device to code the state of the bachelor as an eleventh value,say "wife number = 0 11 • The meaning of the value of this variable then becomes11

If my wife number is = 0, then I am single, otherwise it gives the numberof my wife~" The moral is that the introduction of a separate Boolean variable"married" might have been more honest.

We know that the von Neumann type machine derives its power and flexibility
from the fact that it treats all words in store on the same footing. It is
often insufficiently realized that, thereby, it gives the user the duty toE'wD123 - 84

impose structure wherever recognizable.

Sometimes it is. It~asoften been quoted as The Great Feature of the

von Neumann type machine that it can modify its own instructions, but mostmodern algorithmic translators, however, create an object program thatremains in its entire execution fase just as constant as the original
source text. Instead of chaotically modifying its awn instructions justbefore or after their execution, creation of instructions and execution ofthese instructions now occur in different sequenced regions: the translationfase and the execution fase. And this for the benefit of us all.

It is my firm belief that in each process of some complexity thevariables occurring in it admit analogous hierarchical orderings and that,when these hierarchies are clearly recognizable in the program text, thegain in clarity of the program and in

efficiency of the implementation

will be considerable. If this monograph gives any reader a clearer indicationof what kind of hierarchical ordering can be expected to be relevant, I
have reached one of my dearest goals. And may we not hope, that a confrontation with the intricacies of Multiprogramming gives us a clearer understanding of what Uniprogramming is all about?