Multiprogramming and the X8
EWD51 · 1962–1964 · PDF · source transcription · Source language: Dutch. Machine translation: needs review.
|
|
|||||||||||||||||||||||||||||||||
|
|
|
| Multiprogramming and the X8 | X8 Nr. 17. |
0. Introduction.
To begin with, we consider a number of "loosely coupled", mutually asynchronous, inherently sequential processes. Without loss of generality we can restrict ourselves to cyclic processes.
The loose coupling will consist in the fact that these processes can exchange information with each other, i.e. have access to some common memory. When these processes would like to use the same facility in turn, or when one process wants to consume information that must be produced by another process, certain synchronization requirements follow therefrom. We must ensure that the processes do not interfere with each other or, in the case of information exchange, do not get too far out of step with each other.
In the first part, it is left completely open by what hardware these distinguished processes are realized. The ultimate aim is, in connection with the given - and I must add: conceivable - reality, to have some of these cyclic processes executed by a specific piece of hardware, while the remaining processes will be provided by the central computer. In the first part this distinction is not important; important is, that a "cyclic process" can be a programmed conception and that the number of cyclic processes involved at any given moment can vary over time.
In 1. I will speak of "machine" instead of "cyclic process", to emphasize the fact that we should conceive of these processes as largely (or completely) autonomous. In the light of the previous, we should therefore not be surprised if a few machines are added or a few machines are annihilated. Later, as we come closer to the realization with limited hardware, we will distinguish between "concrete machines" - i.e. cyclic processes to which a specific piece of hardware corresponds such as a communication device - and "abstract machines", which are simulated together by the central computer. For this simulator-general I will reserve the word computer. This simulation raises, with a view to more efficient use of the total installation, strategy problems, which I currently emphatically distance myself from. Before I even want to look at the strategy problem, i.e. before I even want to think about how the computer could exploit its freedom, I first want to see its "unfreedom" formalized, I want to have a suitable formalism in which the logically necessary "interlocks" between the various machines can be formulated.
In 2. we will begin the analysis of the simulation by one computer of the collected abstract machines. Here we see very clearly that no assumptions may be made about the mutual speed ratios of the different machines: when one of the abstract machines is working, the others are idle (work infinitely slowly).
1. Semaphores
The mutual temporal restrictions are recorded in so-called "semaphores". A semaphore is an integer that is accessible to at least two different machines; the possibilities for each individual machine to communicate with the semaphores are however limited to two, the operations P and V.
1.1. The V operation ("Raise").
The V operation can relate to an arbitrary number of different semaphores, e.g. "V (S1, S2, S3)". When this operation occurs in one of the machines - in our example S1, S2, S3 must then be accessible semaphores for this machine - the effect is that all specified semaphores are increased by 1 in one indivisible action.
1.2. The P operation ("Try and lower").
The P operation can relate to an arbitrary number of semaphores, e.g. "P (S1, S2, S3)". When this operation occurs in one of the machines - in our example S1, S2 and S3 must then be accessible to this machine - an operation is started that can only be completed at a moment when all specified semaphores are positive. Completion of a P operation implies that all specified semaphores are decreased by 1 and this completion is regarded as one indivisible action. Also for the P operation we restrict ourselves to the case where the semaphores specified are different.
1.3. Some examples of the use of semaphores.
Note. Many semaphores only take the values 0 and 1. In that case the V operation serves as "section free"; the P operation - a tentative passage - can only be completed when the semaphore (or semaphores) is (are) safe and passage then implies setting to unsafe. The terminology is most clearly derived from railway practice - at least from my understanding thereof.
1.3.1. If we have a class of machines Xi (X0, X1, X2, ...) and in each machine a critical section TXi occurs, critical in the sense that no two critical sections may be under operation simultaneously, then we can achieve this with a semaphore, say SX, which in this simple case will be two-valued:
SX = 0 will mean: one of the machines is busy with its critical section.
SX = 1 will mean: none of the machines is busy with its critical section.
The description of all machines is identical:
"LXi: P(SX); TXi; V(SX); rest of process Xi; goto LXi".
If we were to start all machines at their labelled point ("at the beginning of the line") with the initial value SX = 2, then we would have realized that regardless of the size of the class of machines Xi, never more than two would be simultaneously busy with their critical sections. This is apparently a generalization of the problem of mutual exclusion. (It is exactly the situation of e.g. n tape decks on two channels.)
We draw attention to the fact that the formulation of the individual machines Xi is independent of the size of the class of machines Xi, which is highly desirable with a view to the dynamic variation of this size.
1.3.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 one of the critical sections should exclude execution of all other critical sections, but we also require that the execution of a TX-section and a TY-section are alternating events.
We can achieve this with two two-valued semaphores, say SX and SY.
SX = 1 means that now first a TX-section is due.
SY = 1 means that now first a TY-section is due.
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 machines are all started at the beginning of the line, SX = 1 and SY = 0 must hold or vice versa.
Note. Had we also had a group of machines Zk and the requirement been that the execution of a TX-section, a TY-section and a TZ-section should follow each other in that order, then the programs would have been:
"LXi: P(SX); TXi; V(SY); process Xi; goto LXi"
"LYj: P(SY); TYj; V(SZ); process Yj; goto LYj"
"LZk: P(SZ); TZk; V(SX); process Zk; goto LZk".
We draw attention to the fact that in this extension the text of the machines Xi has not changed.
1.3.3. Now we consider a class of machines Xi that want to load information units into a cyclic buffer with a capacity of N information units; for this we have a class of machines Yj that want to process information units from this buffer.
Because filling the buffer implies administrative measures with the "fill pointer" - and for emptying mutatis mutandis the same applies - we additionally require that filling can only be done by 1 machine Xi at a time and likewise emptying can only be done by one machine Yj at a time.
We introduce four semaphores for this:
SX1 = number of free places in the buffer (initially = N)
SX2 = 0 when one of the machines Xi is filling, otherwise 1
SY1 = number of filled places in the buffer (initially = 0)
SY2 = 0 when one of the machines Yj is emptying, otherwise 1.
The relation N - 1 <= SX1 + SY1 <= N will hold. The machines are now:
"LXi: P (SX1, SX2); fill next place of the buffer; V (SY1, SX2); process Xi; goto LXi"
"LYj: P (SY1, SY2); empty next place of the buffer; V (SX1, SY2); process Yj; goto LYj"
In the foregoing the difference between abstract and concrete machines has been completely left in the background, precisely to show that they are, from a certain macroscopic point of view, completely equivalent. We now do make this distinction to analyze what kind of hardware this could be realized with.
2. Distinction between abstract and concrete machines.
An abstract machine is some programmed sequential process, a concrete machine is a transput device. (Transput is input or output.)
We are of course especially interested in the semaphores that regulate the synchronization between the computer - i.e. the aggregate of abstract machines - and a transput machine on the other hand.
For every semaphore of this type a fixed memory location is reserved. This addition manifests itself in two ways: on the one hand in the way the transput device is connected, on the other hand in the program that provides the cooperation with this transput device. Both processes must have access to this common semaphore.
We now restrict ourselves to two types of semaphores, namely the semaphore on which the P operation is performed by the computer and the V operation by the transput machine and the semaphore where the opposite is the case.
The mapping of the semaphore in a memory location is very obvious: in general it is an integer that must be remembered.
If the semaphore is in memory, there are of course commands with which the computer can access the semaphore. Moreover, the transput machine - if autonomous - in any case already has autonomous access to memory. The basic mechanism for semaphore handling is thus completely present. A further advantage of a memory location is the obvious possibility of extending the number of transput machines (and associated semaphores). There is however 1 complication that we should consider: the value of a semaphore - more precisely: whether it is positive or not - should have a controlling influence. We cannot therefore simply store the semaphore in core and do nothing else. To all these semaphores a flip-flop is therefore added, which will be a derivative of the semaphore, namely = 1 if the semaphore is positive and otherwise = 0. (As long as we restrict ourselves to non-negative semaphores the only other possibility is = 0. Because we are dealing with hardware facilities we will not impose unnecessary restrictions and in our definitions we will always allow negative semaphores, i.e. we perform sign tests and not zero tests.)
Such an added flip-flop then solves the problem of how we can give a controlling influence to a semaphore in core, but it does confront us with the task of ensuring that when the semaphore in memory is changed, this flip-flop is adjusted to the new state if necessary.
For this there are two possibilities
(a) we promote the combination of semaphore change and flip-flop adjustment to the status of indivisible action.
(b) we proceed with the separate adjustment of the flip-flop to the new semaphore value so carefully that temporary discrepancy cannot cause any problems.
Where the transput device changes a semaphore we choose the first method, where the computer changes a semaphore we choose the second method. The first method is not difficult to realize for the transput machine, because the transput machine does have the possibility of claiming memory - at least with a higher priority than the computer. For the machine the first solution is less attractive, because the computer could already access the semaphores via normal commands. The automatic adjustment of the flip-flop would thus mean that an extra encoding would have to be added to the address bits; this is not very attractive if we consider that this number of semaphores increases as more equipment is connected. The method has therefore been chosen where the machine can operate on each of the individual added flip-flops with separate - moderately addressed - commands.
2.1. The P operation by the transput machine.
Let t be the integer in core memory that represents the semaphore, let T be the associated flip-flop, which is 1 if 0 < t. T then functions as "Action flip-flop" for the communication machine, which at a suitable moment in its cycle will execute:
"if T = 1 then begin t := t - 1; if t <= 0 then T := 0 end".
The P operation by the transput machine implies upon completion the acceptance of a start command. (I do not go into the waiting when T = 0, e.g. whether the device actually stands still or makes a dead stroke, because that is unimportant in this context. Essential is that when T = 0 the transput machine will leave the semaphore t and the flip-flop T untouched.)
This P operation - part of consuming the next start command - has as possible consequence that the acceptance of the next start command is further prevented via the assignment T := 0, namely when the supply is exhausted.
Additional rules are:
(a) that this action must be regarded from the computer's point of view as an indivisible action - this has its benefits - but that on the other hand the computer will not have the possibility of forbidding this action over a number of commands - and this creates its problems. The latter follows from the fact that the transput machine has absolute priority over the machine when making autonomous memory contact (in accordance with the fact that at this microscopic level essential emergency situations must be able to be allowed).
(b) that when influencing t and T by the computer it is strictly forbidden for T = 1 to hold, however briefly, incorrectly. At that moment the transput device could then be started incorrectly.
This means that the computer must not perform the V operation via the program
"t := t + 1; C := 0 < t;
if C then T := 1"
(Note. The algol programs with which we describe the action of the machine have as a side property that each line corresponds to 1 X8 command; this makes it clearer to see where the transput device can intervene between the commands. Note that the counting in t is performed with a (condition-setting) additive command; thereby the counting is at least an indivisible action and the counting operations of computer and transput machine cannot interfere with each other.)
If the above program is executed at a moment when T = 1, there is a chance that after the test on the sign of the new value of t and before the assignment T := 1 the transput device performs so many P operations that t is reduced to zero and in accordance therewith T := 0 is performed, after which the computer still executes T := 1 on the basis of an obsolete condition.
The way out of this misery is
"t := t + 1;
if T = 0 then
begin if 0 < t
then T := 1 end"
The justification of this piece of program is now as follows. First we test T; if T = 1, then 0 < t held; after the addition t has only increased and the possible adjustment of T now lies on the path of the transput machine. But if we find T = 0, then the transput machine can no longer perform the P operation, so t and T are left untouched from that side and the computer can calmly perform the test.
In the practice of the X8 it will be executed a little more complicated. Such an "Action flip-flop" as T will, in order not to load the communication line unnecessarily, not be located in the basic machine but in the transput machine in question. This makes the query "T = 0" a less attractive proposition. Therefore a copy of T is kept in memory, called ST.
The P action by the transput device is now:
"if T = 1 then begin t := t - 1; if t < 0 then ST := T := 0 end"
and the V action by the computer becomes
"t := t + 1;
if ST = 0 then
begin if 0 < t then
begin ST := 1;
T
:= 1
end
end"
where we must ensure that the assignment to ST is performed before the assignment to T.
To limit the number of memory contacts of the transput machine it is desirable to represent ST and t in the same word, but in such a way that the operation t := t + 1 does not change ST. This can be done e.g. by dividing the word as follows:
d[26] = ST, d[25]...d[0] = (2^25 - 1) + t
The test "t <= 0" then amounts to the test "d[25] = 0".
2.2. The V operation by the transput machine.
Again we will denote the semaphore by t and the associated flip-flop by T and T = 1 if 0 < t. The V command is now simply
"t := t + 1; if 0 < t then T := 1"
executed by the transput mechanism as an indivisible action that the computer cannot prevent.
The P operation will only be performed by the computer when T = 1; the computer can, by grace of deafness, however permit itself to temporarily set T = 0.
The completion of the P operation by the computer now consists of the following piece of program
"t := t - 1;
T := 0;
if 0 < t then
T := 1"
Essential assumptions here are
(a) that it does no harm if T is incorrectly = 0 for a while;
(b) that when transput machine and computer try "simultaneously" to perform the assignment "T := 1", then after completion "T = 1" will certainly hold.
To show that the above piece of program leaves the value T in accordance with t under all circumstances after completion, we do not need to assume that T was initially positive. (If we reverse the first two statements, I would have to assume that; a clearer insight into this kind of game is still very desirable!) We can optionally also use this program to give a so-called negative advance via "t := t - n".
The reasoning is as follows. Every V operation before the assignment T := 0 in the above little program does not matter, because afterwards T := 0 is executed in any case. If during the assignment T := 0 t is positive, then the computer will eventually execute the statement T := 1. Because of intervening V operations t can only have increased further and T will thus be left correctly. If during the assignment T := 0 t is non-positive, then we must distinguish two cases. If despite possible intervening V operations t remains non-positive, then both transput machine and computer will leave T untouched and T will thus be left correctly = 0.
If by intervening V operations t becomes positive, then in any case the transput machine at the moment of change will execute T := 1 (and possibly additionally also once by the computer, namely if t was already positive at the time of the test). In this last case T will thus be guaranteed to be left correctly = 1.
After this analysis of V resp. P operation by the computer I trust
(a) that the reader is convinced of the watertightness
(b) that the reader will not take it amiss of me that I have spun this out so extensively. On the contrary even.
If the P operation must be performed by the machine, then the associated flip-flop T is a so-called interrupt flip-flop. An interrupt flip-flop is located in the basic machine, can be set in both directions by the computer, can be set to 1 by the transput machine. (This in contrast to an action flip-flop, see 2.1.)
2.3. Hardware for interrupt control.
Interrupt flip-flops can (see 2.2.) be set individually in both directions.
To each interrupt flip-flop a listen bit is added. This is also implemented as a flip-flop; the listen bits can also be set individually in both directions by the computer.
Interrupt flip-flops, as well as listen bits can be read out word-wise via a communication command. (As long as there are fewer than 27 per type, we do this with one word for each type.) Corresponding flip-flops have the same position in these words.
Finally, there is a deaf-hearing bit in the computer, which also has the commands "make deaf" and "make hearing".
If the following two conditions are satisfied:
(a) the machine is hearing
(b) the collation result of interrupt word(s) and (corresponding) listen word(s) is ≠ 0
then an interrupt takes place, i.e.
instead
of normally fetching the next command, a subroutine jump is placed in
the command register, which is executed with suppression of the
incrementing of the command counter; also the machine is automatically
made deaf by this action.
Note. It would follow from this that an interrupt can only take place at a place in the program where the machine is hearing. If during the last command before the interrupt it has already been decided that this interrupt will take place, then it may be difficult to go back on this decision if the last command was just the "make deaf" command. The solution is to also save the "deaf-hearing" state when storing the link and to jump back "restoring" when continuing the interrupted program. With the X1 it has been found that "delayed action" of the commands "make deaf" and "make hearing" does not cause any difficulty provided this delay extends over only 1 command.
The little program for the counting down of T in 2.2. will be performed in deafness; hence T may freely have an incorrect value for a while.
The listen bits enable us to ignore interrupt flip-flops - possibly temporarily - when there is - as yet - no interest in them.
transcribed by Johan E. Mebius
revised Thu, 29 Mar 2007