Edsger W. Dijkstra, "Over seinpalen"

We consider a number of mutually “weakly coupled”, in themselves sequential processes. By the “weak coupling” I understand that they can take each other into account on certain points. For example, if a number of processes occasionally want to use one or the other facility that can only serve one process at a time, this means that the processes may have to wait for each other. If one process processes information that has to be supplied by another process, then it is also clear that the former may have to wait for the latter. i.e. the processes must be able to be synchronized to a certain extent with respect to each other.

A common memory has been introduced to enable the processes to exchange information about each other's progress. The elements of this memory are non-negative integers, which we call semaphores.

In the individual processes, the points that are important for mutual synchronization are marked, because it is indicated there that a certain operation must be carried out at certain semaphores when passing such a point. The individual processes here have the choice of two operations, the so-called V-operation and the so-called P-operation, which we will describe below.

In the following we assume that S1, S2, S3 etc. are names of accessible semaphores (not all semaphores need to be accessible in every process!); we will write the V and P operation as a procedure statement.

The V-operation relates to at least 1 semaphore, so for example “V(S1)” or “V(S1, S2, S3)”. If one of the individual processes performs the V-operation, the effect is that all semaphores specified at this time are increased by 1 in one indivisible act.

Note 1. The addition “in one indivisible act” is intended to express the following. Suppose that the value of the semaphore S1 = 3 and that then, for example, two of the (simultaneously operating!) processes want to execute the operation V(S1) “at the same time”. Due to the indivisibility of the operation, we may then imagine that these two V operations on the same semaphore are executed in succession in an otherwise irrelevant order, so that after completion S1 = 5 and not one of the increments, e.g. under table is hit.

Note 2. The V operation with more than 1 argument is not logically necessary, but it is elegant. In the statement “V(S1, S2)” a simultaneous raising of both semaphores is requested; if we replace this in one of the individual processes with “V(S1); V(S2)”, then we very explicitly ask for increments in a certain order. It might be a bit less fun to be forced to do this, if you prefer to raise a number of semaphores simultaneously in a “neutral” way.

Note 3. If the V-operation is included with more than 1 argument, then we will limit ourselves for the time being to the case that the semaphores specified with it are different.

In an individual process, the P operation marks the tentative passage of this point. The P-operation relates to 1 or more semaphores, so eg “P(S1)” or “P(S1, S2, S3)”. If the P-operation has been started in one of the individual processes, then an operation has started with it, which can only be ended at a moment when all semaphores assigned to it are positive. Termination of a P-operation implies that all semaphores specified therein are lowered by 1 and this termination also counts as one indivisible act. Also for the P-operation we limit ourselves to the case that the semaphores specified therein differ from each other.

Note 1. The P-operation with more than 1 argument is logically necessary.

Note 2. Many semaphores only take the values 0 and 1. In that case, the V operation acts as a “clear track section”; the P-operation, the tentative passing, can only be completed if the semaphore (or semaphores) involved is set to safe and passing then implies a setting to unsafe.

Example 1. If we have a class of machines (alias processes) Xi (i.e. X0, X1, X2, etc…) and each process has a critical section, critical in the sense that no two critical sections can be processed at the same time, then we can achieve this with a semaphore, say SX, which in this simple case will only be bivalent;

SX = 0 will mean: one of the machines Xi is working on its critical section

SX = 1 will mean: none of the machines Xi are working on their critical section.

The description of all processes is now the same:

  LXi: P(SX); TXi; V(SX); rest process Xi; goto LXi

If we started all processes Xi at their labeled point (i.e. “at the beginning of the line”) with the initial value SX = 2, we would have achieved that regardless of the size of the class of processes Xi and never more than two simultaneously working on their critical section. This is apparently a generalization of the mutual exclusion problem. (It is exactly the situation of, say, n tape decks on two channels.)

We draw attention to the fact that the formulation of the individual processes Xi is independent of the size of the class Xi, which is highly desirable given the dynamic variation of this size. The maximum allowable simultaneity for the critical sections also does not penetrate the formulation of the individual processes.

Example 2. Now we consider a group of machines Xi and a group of machines Yj, each with their critical section TXi resp. TYj. Execution of a critical section should exclude execution of all other critical sections, but we also require that the execution of a TX section and a TY section be alternating events.

We can achieve this with two bivalent semaphores, say SX and SY.

SX = 1 means that now it is the turn of a TX section.

SY = 1 means that now it is the turn of a TY section.

The programs for the machines are:

  LXi: P(SX); TXi; V(SY); process Xi; goto LXi

and

  LYj: P(SY); TYj; V(SX); process Yj; goto LYj

If the processes are all started “at the beginning of the line” then SX = 1 and SY = 0 or vice versa.

Example 3. Finally, we consider a class of machines Xi, which want to dump information units into a cyclic buffer with a capacity of N information units; furthermore a class of machines Yj, which want to process information units from this buffer.

Since filling the buffer implies administrative measures with “fill pointer” - and the same applies to emptying mutatis mutandis - we also require that filling can only be done by 1 machine Xi at a time and likewise that emptying can only be done by 1 machine Yj at a time.

We use four semaphores for this:

SX1 = number of free places in the buffer (initially = N)

SX = 0 if one of the machines is filling Xi, otherwise = 1

SY1 = number of filled places in the buffer (initially = 0)

SY2 = 0 if one of the machines Yj is emptying (otherwise = 1)

It will hold N - 1 < SX1 + SY1 < N.

The machines are now:

  LXi: P(SX1,SX2); fill next place of buffer; V(SY1,SX2); .....; goto LXi

  LYj: P(SY1,SY2); empty next buffer location; V(SX1,SY2); .....; goto LYj

We will now divide our cyclical processes into two groups. Those of one group are called “the concrete machines”, those of the other group are called “the abstract machines”.

The “concrete machines” are the transput devices. These are all (cyclical) processes that do their work autonomously with their own time awareness for a certain period of time. In this context, “autonomous” means independent of the control of the central computer. In addition to transport to and from the outside world (paper tape, printer, punch cards, etc.), this also includes transport between core memory on the one hand and drum or magnetic tape on the other. It is these processes that, once initiated by the X8, take place simultaneously with the working central computer.

The “abstract machines” are the mutually asynchronous programs. Since the central computer is de facto only working on 1 program at a time, we can say that at most one of the abstract machine is working at any given time. (It is possible that none of these programs will work: the central computer then “sits in the coordinator”. The coordinator is not considered one of the abstract machines.)

As long as semaphores are only selected by abstract machines, no special hardware provisions are required for this (except for deafness): any memory location can function as a programmed semaphore.

A semaphore, which is selected purely by the concrete machines (I leave it in the middle for a moment, whether there will be, it is quite conceivable) is a matter that takes place entirely outside the X8 and therefore does not need us at the moment. not to be interested.

However, a semaphore, which must be selectable by both a concrete and an abstract machine, requires our special attention. It is clear that this requires special hardware provisions and rigorous conventions.

In principle, each “hardware semaphore” is a (per installation) fixed memory location; the transput device can subtract 1 (external P operation) or add 1 (external V operation).

If the central computer needs to raise or lower these semaphores, this must be done using the additive off command. In this case, interference between the two additive operations (ie an internal and an external) is not possible.

A complication is that each hardware semaphore has a flip-flop associated with it that indicates whether the associated semaphore is positive. (For the necessity of this flip-flop, see later)

We can now distinguish two types of hardware semaphore (as a rule, each transput device has one of both types):

1. A starting order count. In this case, the central computer performs the V operation, and the transfer mechanism performs the P operation. The associated flip-flop in such a case is called an Acflop.
2. An interrupt count. In this case, the central computer performs the P operation and the transput device performs the V operation. The associated flip-flop in such a case is called an Inflop.

In each installation, the concrete machines are numbered. From the number it can then be deduced which memory locations are reserved for counting start orders and interrupts; the associated Acflop and Inflop can be reached by specifying the device number.

We now show how the central computer can adjust the associated flip-flop if necessary when a hardware semaphore is changed. (Adjustment of such a flip-flop due to modification by the transput equipment is not the concern of the central computer, but of the builders.

Let t be the integer representing the semaphore in core memory; the associated flip-flop is called Acflop. The transput device will accept another start command, if there is one and it is due. In the completion of the P operation on this semaphore it performs the action which can be described by

  if Acflop then begin t := t - 1; if t < 0 then Acflop := false

This P-operation, which must be considered as part of consuming the next start command, therefore has the possible consequence that the recording of subsequent start commands will no longer take place until further notice; this is if, due to depletion of the stock, Acflop is set to false.

Additional game rules are:

• that this action from the computer should be seen as an indivisible action - this creates its advantages - but then on the other hand the computer will not have the possibility to prohibit this action over a number of commands - and this creates its problems.
• that when t and Acflop are influenced by the computer, it is strictly forbidden if, however briefly, Acflop would falsely be true. At that moment, the transput device could immediately start working incorrectly.

If the central computer - to indicate that the next start information has been prepared - has to perform the V-operation on this semaphore, this was done by means of the following piece of program:

  t:= t + 1;
  if non Acflop then
     start if 0 < t
           then Acflop := true end

The justification for this piece of program is as follows. After the increment, Acflop is tested; if Acflop was true, then the count t was positive and it can only have become more positive due to the increment and any adjustment of Acflop is therefore up to the transput machine until further notice. But if we find the Acflop false, then the transput engine can no longer perform the P operation, so that t and Acflop are left untouched on that side and the central computer can carry out the test in peace.

Again we will designate the semaphore with t; we now call the associated flip-flop Inflop. Inflop indicates whether t is positive. The V operation performed by the transput machine can be described by:

  t := t + 1; if 0 < t then Inflop := true

viewed from the central computer, this is an indivisible, unstoppable act.

The completion of the P operation will only be executed by the central computer if Inflop is true; by the grace of deafness - where the value of Inflop has no effect, see later - the computer can afford to temporarily set Inflop to false.

The completion of the P operation by the computer now consists of the following piece of program:

  t := t - 1;
  in-flop := false;
  if 0 < t then
           in-flop := true

It is essential hereby assumed:

• that it can't hurt if Inflop is incorrectly false for a while
• that if transput machine and computer try “simultaneously” to execute the assignment “Inflop := true”, then Inflop will certainly be true afterwards.

The justification for this piece of program is now as follows. Every V-operation for the assignment “Inflop := false” from the above program is irrelevant, because then Inflop is set to false in any case. If during the assignment “inflop := false” the count t is positive, the computer will eventually execute the statement “inflop := true”. Interleaved operations V can only increase the count t and thus Inflop is correctly left behind. On the other hand, if during the assignment “Inflop := false” the count t is non-positive, we have to distinguish two cases. In the event that the count t does not become positive due to interleaved V-operations, then both the transput engine and the computer will leave the Inflop untouched and Inflop will rightly remain =false. If, on the other hand, the count becomes positive due to subordinated V-operations, then the assignment “Inflop := true” will in any case be executed by the transput machine at the moment of reversal (and possibly also, unnecessarily, by the computer, viz. if at the time of the test the count t is already positive). In the latter case, Inflop is therefore guaranteed to be correctly left on true.

Note. The readability of the Acflops and the two-sidedness of the convertibility of the Inflops have been introduced in the X8 especially to make these programs possible. This hardware is, in a sense, the extra price we have to pay for the impressibility of the autonomous operations on the semaphores.

In the following we will also represent Inflop true by = 1, and false by = 0.

As mentioned, the Inflops are numbered. In an installation with less than 27 Inflops, these can be read together as bits of the so-called (1st) Inflop word using a special communication command. (If there are more Inflops, a 2nd Inflop word will be introduced. Etc etc. I expect that a maximum of 26 bits will be used per Inflop word and that the sign bit of an Inflop word is always = 0 for standardization purposes.)

Note. I don't know what position the different Inflops occupy in the Inflop word: a decision might have to be made about this.

Each Inflop has a listen bit; this is also a flip-flop, which can be individually set in both directions by the X8. The listening bits can also be read via one (or if necessary more) so-called “listening word”. A listen bit occupies the same position in the listen word as the corresponding Inflop in the Inflop word.

Finally, there is a flip-flop that indicates whether the X8 is “deaf” or “hearing”. An operation takes place if

• the collation result of Inflop word(s) and listening word(s) does not contain zeros only
• and also the machine is hearing.

Note. The X8's deafening commands work “instantaneously”; it is therefore not possible for an interruption to take place after the command “deaf” (as was the case with the X1).

Memorandum: This should be checked before the restorative jump, which can effect the hearing → door transition; it must be inquired whether the hearing-making commands also work instantaneously.

The operation consists of:

• a special subroutine jump is executed (with a labda reserved for this purpose)
• in the execution of this subroutine jump, the normal increment of the command counter is suppressed and the machine is immediately deafened.

The interrupt jump directs the control to the “interrupt routine”; it starts by saving registry contents, etc. to ensure that the now interrupted program can be continued later as if nothing had happened. It will then have to analyze the Inflops to discover which external device had something to say, if necessary, and what, etc.

An important part of the coordinator is the interrupt routine. I expect that the interrupt routine will be so intertwined with the coordinator that separate treatment is hardly possible.

The coordinator waiting list contains all the programs in the machine, divided into two categories, the blocked ones and the executable ones.

Blocked program axes are program axes that cannot continue because they are waiting at a semaphore for the completion of an event necessary for their continuation.

Executable programs are programs that can continue were it not for the fact that the X8 can only help one of them. (I assume that the program executed by the X8 remains below the executable: the term “waiting list” is a bit odd, but let's put it that way. If the control really resides in the coordinator, then the term alright.)

The effect of the P-operation can be that a program is now blocked from the executable, the effect of a V-operation can be that a (other) program from the group of blocked ones is transferred to the executable. A program interrupted in action by an interrupt remains ranked below the executable!

We can also see it this way: if a P-operation is initiated in a program, then at that moment the program was in action, ie executable. Now there are two cases. Either the prevailing values of the affected semaphores do not constitute an obstacle, or they do. In the first case they are downgraded, the P operation is completed and the program remains executable. (Whether it stays in action is a whole other chapter!) In the second case, the program is removed from the group of executables. Thus, the group of blocked only contains all program axes that are stuck in an initiated but not completed P-operation.

The P-operations of the abstract machines are thus definitely not played as a permanent observation of the semaphores involved, on the contrary: the abstract machines, which are blocked, slumber. Now that the abstract machines, once blocked, are no longer sensitive to semaphores going positive, the coordinator must be sensitive to semaphores going positive. In other words. if 1 or more semaphores become positive, the coordinator has the duty to determine whether blocked people can be helped out of their blockade and if so, the coordinator must do this. (In the case of the V-operation with more than 1 argument, two abstract machines may therefore have to be transferred to the executable) Here lies a fairly strict duty for the coordinator: after all, it must be avoided that an abstract machine is blocked by a programmed semaphore, which has since become “unnoticed” positive. The abstract machine no longer looks, the semaphore no longer signals and everything is stuck!

It is for the above reasons that we will certainly not suffice with a simple additive output order for the V-operation, which has been described as an increment until now. The programmed V-operation becomes a call to a coordinator routine: it will increase the semaphores that have been passed on and also look at the consequences associated with this increase!

Here we now see the interweaving of the interrupt routine and the coordinator. The interrupt routine sec does not do much more than determine on which (hardware) semaphore the V-operation has been performed and this will also usually result in an abstract machine being unblocked.

The blocked program axes are located in the coordinator waiting list, specifying the semaphores to be lowered upon completion of the P operation.

I imagine that the waiting list will be arranged not as array, but linked via pointers. I assume that every abstract machine is assigned a number at creation - the lowest free number - and will keep this number throughout its existence. I also assume that under this number in the waiting list can be selected directly.

I wanted to link together all executable machines as a list, and I also wanted to make the starting link of a possibly non-empty blocked list at every non-positive semaphore.

Now, if one of the abstract machines wants to perform the P-operation, then the semaphores supplied are examined. If one of the semaphores is found to be non-positive, the other semaphores are no longer viewed at all, because this abstract machine is immediately attached to the blocked list of this semaphore. The remark is that before this semaphore is positive, the P-operation is in any case not eligible for completion.

If a V-operation is now performed on a semaphore, the coordinator can now check the possible consequences fairly quickly. If the blocked list was empty, then nothing was waiting for this V-operation and none of the blocked machines are eligible for unblockage. If the blocked list of this semaphore is not empty, then one examines an abstract machine in the list: if the other semaphores do not form an obstacle, then a P-operation can be completed and this abstract machine passes to the executable. If another semaphore does form an obstacle, then the abstract machine switches to the blocked list of that last semaphore. Repetatur, until either the semaphore is zero again (successful deblocking) or the list is empty (or both). It goes without saying that by completing the V-operation in such a way it is impossible that a positive semaphore with non-empty blocked list would remain.

Except for error and omission, as a result of a V operation, the coordinator should now be able to determine fairly quickly whether there are further consequences associated with this and, if so, which ones.

The listening bits fit perfectly in this scheme: the listening bit of a hardware semaphore is made = 1 if its blocked list is filled, otherwise = 0. After all: if the blocked list is empty, then initially nothing is waiting for this semaphore. What action shall we introduce then, if this semaphore becomes positive? For example, the listening bits emerge as a means of suppressing unnecessary interrupts. Whether this will have much effect remains to be seen, it could very well be that an interrupt is almost always awaited.

Translation: Serge Vakulenko - Campbell, California