Multiprogramming and the X8, Part 2
EWD54 · 1962–1964 · PDF · source transcription · Source language: Dutch. Machine translation: needs review.
|
|
|||||||||||||||||||||||||||||||||
|
|
|
| Multiprogramming and the X8, installment 2. (Continuation of EWD51) |
X8 No. 18. |
2.4. Cumulation of start commands and feedback messages.
If the signal poles that control synchronization with the external equipment were at most two-valued, we would not have banished the rush situation sufficiently. The essential rush situation may indeed be banished, the "moral" rush situation remains. An example may illustrate this.
Suppose we have to execute a number of drum transfers in otherwise arbitrary order. For the first transfer you have no knowledge of the drum position and the machine will on average have to wait half a revolution; after completion of this transfer, however, you know precisely how the drum is positioned and it is very tempting to try to use this knowledge, i.e., to execute the transfers in such an order that the waiting times can be kept as short as possible.
If you now have an organization for drum transfers that can only take note of the next transfer - through the intermediary of a next start command then supplied via program - after the previous transfer has been successfully handled, then the desire to give that next start command in time breeds a "moral" rush situation: it is then indeed not necessary, but still highly desirable, that the "ready signal" of the previous transfer results in a swift reaction.
In the case of drum transfer, the autonomously executable action is determined by:
|
(a) |
starting address in core |
|
(b) |
starting address on drum (plus specification of which drum, since at most 1 drum transfers at a time) |
|
(c) |
length of the transfer |
|
(d) |
direction of the transfer |
The feedback consists of two bits:
|
(e) |
whether the transfer was successful - i.e., no parity error occurred |
|
(f) |
the feedback that the transfer - successful or failed, see (e) - is completed. |
Per start command, one now provides a number of consecutive words, in which in a fixed, not relevant here, encoding space is provided for the data (a) through (e); the item (f) is conveyed by raising a reserved signal pole for this purpose.
The control of the drum transfers must therefore keep track of this signal pole - and associated flip-flop - plus the location of the code information (a) through (e).
To avoid the moral rush situation, one now provides a number of such start spaces on a number of consecutive memory locations; if per start command for data a through e, for example, two words are needed and, for example, four start commands can be accumulated, then this start magazine costs us 8 consecutive memory locations. The drum transfer organization must now process these start spaces cyclically.
In this case there are two extra complications, the cyclic processing and the error reaction.
2.4.1. The cyclic execution.
The start commands are now in a cyclic buffer of known length. This start buffer is filled under control of a rotating fill pointer, which is a fully programmable matter.
Being refilled is indicated each time by
"V(startseinpaal trommeltransport)"
The autonomous drum transport empties the start buffer - processes the start commands - under control of a cyclically rotating "empty pointer", with which the computer has nothing to do, except that at the very beginning it must be in phase: the first executed start command must indeed be the first given one. From that moment, barring disasters, the empty pointer rotates neatly behind the fill pointer.
2.4.1.1. One solution is to clear this empty pointer as part of the process that starts the machine; the "tooth-brushing program" can clear the fill pointer and we start the two processes automatically in phase. Ideally this organization is fine, from a practical point of view it is not stylish, because in case of doubt you can never get the whole thing back in order "as sure as a house" except by turning the machine off and on.
2.4.1.2. This additional objection can be countered - albeit at the cost of an extra instruction - if the empty pointer can be cleared from the computer. If you include this clear instruction in the toothbrush program, then you can also, in the meantime, regain control of the whole thing in case of doubt through the computer under program control. Although it costs an extra instruction in the computer code, this solution is not unattractive for the time being.
2.4.1.3. We can agree that the empty pointer is located at a fixed place in memory, e.g., immediately preceding the start buffer. If this is the only place where the fill pointer is kept, then this would lead to quite a lot of memory contacts for autonomous transport per word. After all: 1 memory contact for the word itself, but before the corresponding physical address is known, a memory contact with the corresponding - possibly already incremented - start information must be made, but to make this possible, it is necessary that first another memory contact is made to obtain the current value of the empty pointer.
(My remark: is this about the empty pointer, about the fill pointer, or about both? Johan E. Mebius)
This is a bit too much; one can reduce the number of memory contacts per word transport from three to two by stipulating that we have indeed introduced a fixed memory location for the empty pointer, but also add a few flip-flops - in our case two - to the drum organization, in which upon each start command acceptance (i.e., the P-operation by the autonomous equipment) the incremented empty pointer from the fixed memory location is copied. This under the motto that during an entire block transport the value of the empty pointer is constant.
Remark: The total of 2 memory contacts per word transport was based on the assumption that start address on the cores and length would be stored together in one word. We will return to this briefly later at the end of 2.4.
2.4.2. The error response.It is of course very pleasant to be able to give a number of start commands "in advance", but let us be well aware that you generally only value the later transports if the preceding transports have been successful. Very clear is that in the event of a failure of a transport from drum to cores: if something goes wrong here in word transport - parity error - then you can perhaps try it again. If we now accumulate two transport commands, of which the first reads a section of drum, after which the next wants to write something else to those same drum locations, then it is apparently not the intention that that second transport takes place if the first has failed.
The question is therefore, how the autonomous transport reacts to a detected parity error, besides the fact that the failure is indicated in the start data (see point e, from 2.4.)
Attempts to protect the autonomous organization from further action by clearing the action flip-flop, possibly also setting the start semaphore to zero, have failed, because the analysis of 2.1. (in EWD51) collapsed as a result.
A healthier solution seems to be to introduce the drum organization with two states, indicated by an OK-bit (implemented on a flip-flop). As soon as a parity error is detected, the organization goes into the state non OK; if non OK, then no word transport takes place, each transport is immediately terminated with an error message. This applies both to the transport in which the parity error occurred and to the following transports that are still in the start magazine.
The start magazine is thus "symbolically" completed, thereby guaranteeing that the entire semaphore game proceeds undisturbed.
The question is, how then the transition from non OK to OK should be effected. For a moment we thought that this could be based on emptiness of the start magazine. The fact that the transport mechanism, to discover that emptiness, does not have sufficient contact with the start semaphore by means of the P-operation alone, should have made us suspicious. One realizes the unreliability of an automatic transition to the OK-state when a new start command is added to an almost empty magazine. If the P-operation takes place just before the V-operation, the semaphore in question can just become = 0, while this is not the case if the P-operation takes place just after the V-operation: suddenly the sequence "1 -> 0 -> 1" would have a different effect than the sequence "1 -> 2 -> 1". And this was not the intention: such an implicit termination of the non OK state makes safe handling impossible.
There are thus two obvious possibilities at first glance, to make the machine explicitly restore the OK-state.
2.4.2.1. This is the extension of the situation described in 2.4.1.2.: the same instruction, which clears the empty pointer and also restores the OK state. One can couple these two things, for the OK state must be restored at a moment when the start magazine is in any case empty; with filling one can then also start again at the beginning.
2.4.2.2. The other possibility is an extension of the situation as described in 2.4.1.3.. One can allow in the start magazine, besides transport commands in both directions, also "restore OK-state" commands. In the case that an error message is detected, the computer adds the command "restore OK-state" to the magazine and repeats the failed commands. The first solution adds a command to the code of the central computer, the second adds a command to the arsenal that the autonomous organization accepts from the start magazine. Besides from "extension considerations" I also have a pronounced preference for the last solution because the central computer can already take its measures here without the requirement of empty start magazine getting clogged up or the extra specification of how the autonomous transport organization reacts to the resets when something is still running. In this way we guarantee that the autonomous organization receives the information controlling it neatly sequentially delivered.
The functioning of the autonomous drum transport can be documented for the well-willing reader, under the assumption that the last solution is chosen, as follows.
Legend:
|
the quantity "CyclischeTellerstand" is located at a fixed place in memory; |
The boolean "PariteitInOrde" is global w.r.t. the undeclared procedure "VolgendWoordtransport" as well as the anonymous quantities that control track selection, transport direction and drum synchronization. The quantities declared below are on flip-flops.
begin
boolean OK, integer teller;
start:
P (Startseinpaal Trommeltransport);
teller :=
CyclischeTellerstand := mod (4, CyclischeTellerstand + 1);
if OKHerstel[teller] then OK := true
else
begin
if OK then
begin
SteltransportRichtingInOp (RichtingTransport[teller]);
StelSpoorSelectieInOp (BeginadresTrommel[teller]:1024);
WachtOpTrommelstand (mod (1024, BeginadresTrommel[teller]));
VolgendWoord:
if Lengte[teller] != 0 then
begin
VolgendWoordtransport (BeginadresKernen[teller]);
Lengte[teller] := Lengte[teller] - 1;
OK := PariteitInOrde;
if OK then
goto VolgendWoord
end
end;
Succesmelding[teller] := OK
end;
V (Ingreepsignaal Trommeltransport);
goto start
end
(NB: != means "not equal to" - JEM)
Later I hope to show by way of example the structure of the program that plays the aforementioned piece of equipment.
Note. In the start instruction for the drum we must find space in advance for:
Lengte: 12 bits;
BeginadresKernen: 18 bits;
BeginAdresTRommel: 19 bits;
(drum): 2 bits;
OKHerstel: 1 bit.
For the success message you don't need a new position and you could use the OKHerstel-bit. We thus arrive at a total of 52 bits, which can splendidly be accommodated in two words. A complication, however, is that the first two items (Lengte and BeginadresKernen - JEM) together require 30 bits. The 3 bits that you lack could be accommodated in the second word, by externally accepting them on 3 flip-flops, so that the number of memory contacts per word does not increase unnecessarily. (An X8-word consists of 27 bits - JEM)
3. The coordinator.
3.1. On the administration of a population.
In the coordinator, the administration must take place of e.g. which input and output devices are assigned to which programs, which programs have been halted as a result of which signal poles, etc., etc..
If the number of programs were e.g. at most 10, if the collection of signal poles were a fixed limited collection, then we would not be dealing with the problem posed in the following. I do not want, especially at the beginning of my explorations, to impose such a drastic restriction on myself and therefore seek an organization in which the number of programs, the number of signal poles that participate, can vary arbitrarily over time, but in such a way that all these entities do not lose their identity during their existence.
A straightforward method is to consecutively number all entities of a certain class in order of introduction. This method is practically unusable because
(a) after a while these numbers will become arbitrarily high;
(b) to the question of how one can obtain further information about entity no. such-and-such of a certain class, only a search system can provide an answer.
The solution that attracts me most at the moment is inspired by the hotel business: as soon as you enter the hotel, you are assigned a free room and for the duration of your visit your room number is your identification.
Additional facilities are that if my hotel is full, I can build another floor on top and, if the top floor is empty, I can dismantle it if necessary.
The consecutively numbered hotel rooms are mapped in memory to consecutive locations (or fixed formations thereof): dismantling the top floor thus means that memory is freed for other purposes. It could therefore make sense.
The tactic is now that each new guest gets the lowest-numbered free room. Programmatically this is simple: we remember the size of the hotel, for each room whether it is occupied or not, and finally the rank number of the lowest occupied room. When a new guest arrives, he immediately gets his room and we look for the next free room; when a guest leaves the hotel, his room is released and at the same time this room number is compared with the current lowest free room number, which is replaced if necessary. The search work is thus very simple, it is even questionable whether we actually need the abundant datum "lowest free room number". (If a lot of searching would have to be done, I would store the occupied-bits in words and make use of the normalize instruction to find the first free one; because of the "so many bits per word" this solution attracts me less.)
I know that the tactic "new guest gets lowest free room" does not minimize the time average of the effective hotel size: if at a moment when the hotel is very full, a long-stayer registers, then the vacancy rate can drop drastically before the long-stayer has made it to the top floor, I cannot start dismantling. I thought nevertheless that this tactic would help a lot at little cost, certainly sufficiently, because the hotel rooms I have in mind will not be terribly large.
The hotel analogy goes further: many hotels will host a number of regular guests - the hardware signal poles, the standard communication programs etc.; it is clear that the regular guests will get the lowest-numbered rooms, from the start forever.
I assume that the number of hotels that are directly managed by the coordinator is limited, known and constant. In addition to the two mentioned administrative data, we will also have to remember per hotel the location - i.e. the address of the zeroth room. I also think this is stored in a fixed location.
3.2. The waiting lists for abstract machines.
A word of warning upfront. I must erect a building whose contours are beginning to dawn on me. I have an idea of the kind of foundation on which this building will rest: what the foundation will have to bear precisely, I will only know when the superstructure is complete. In designing the superstructure, however, I must constantly ask myself whether a foundation can still be built for it. In other words, no one should expect at this stage a watertight argument in which something is now introduced with a hair-splitting reference to the necessity that will be elaborated 100 pages later: that 100th page, after all, has not yet been written!
The order in which I will initially try to describe the various "operating rooms" of this building is more or less arbitrary. Probably I always choose that component for which the least obscure task description and a possible construction are clearest to me at that moment. That readability sometimes has to suffer from the fact that I cannot say everything at once and occasionally my thoughts are more elaborated than I can describe at that moment, I unfortunately see as inevitable. That much for this apology.
If a concrete machine - a transput device - gets stuck in its P-operation, the coordinator does not need to take special note of it: after all, the concrete machine remains on the leash and as soon as the impediments are removed, the concrete machine begins to run autonomously.
With the abstract machine it is different: these are programs that have ceased their activity because they could not continue at that time. As soon as the impediments are gone, they must be awakened from their deep slumber. Investigating the consequences - keeping track of the changed situation - of a V-operation on one or more semaphores is a task that typically lies in the coordinator's path.
We consider all abstract machines that are participating at a given moment, i.e. all abstract machines that at a given moment have either explicitly ceased their activity - by a P-operation - or have been interrupted somewhere in their activity. These abstract machines together form the population of HAM, i.e. "Hotel for Abstract Machines", and are identified during their existence by the room number of the room assigned to them in HAM.
Note: According to this definition, the coordinator itself is not an abstract machine and therefore the coordinator is not included in HAM. This applies, note well, to the core of the coordinator, i.e. that part of the coordinator that will always be present in the cores as a central administrator. (How it gets there is such a nice "prille-begin problem" that we would be wise not to occupy ourselves with it for the time being. The prille-begin problem is, after all, isolated.) To keep the time average of core memory occupation by the coordinator not too large, we will normally have parts of the coordinator on the drum and only load them when they need to come into action. It could well be that we can organize this most elegantly by considering these outrunners of the coordinator as abstract machines, which will then indeed belong to the regular guests of HAM.
One of the regular guests of HAM will be the "Dummy Abstract Machine" c.n. DAM. The text reads:
"LDAM: P (SDAM); goto LDAM"
This and that implies that SDAM will be a regular guest of the semaphore hotel, about which more later.
The coordinator is now such that when no abstract machine can any longer be simulated, because they are all blocked by semaphores, the operation
"V (SDAM)"
is performed; DAM thereby gets a turn and switches itself off for the time being by the operation "P (SDAM)". Such a dummy machine is logically not necessary, it probably makes the whole reflections a bit simpler. We then do not need to take into account in our description that the coordinator might not find an abstract machine to delegate the computer to. In the case that the coordinator is always executed by deaf X8, for example, we can make the machine hearing in DAM, which could be quite convenient.
Note: It is not strictly necessary that the operation V (SDAM) is only performed when there is really nothing more to do. If it turns out that we make DAM a machine with minimal priority, then it could well be that DAM, for example, takes a turn every few seconds. Something like that could prevent a situation where you could assign two priorities to abstract machines, a static priority and an effective priority, where the effective priority, initially derived from the static, slowly grows if the abstract machine never gets a turn. This to avoid the danger of permanent neglect. If it turns out more elegant to let DAM hobble along quietly in this, then there is nothing against it at all.
Regarding the fact that there are some objections to giving the rooms of HAM a fixed size, we will skip over that for the time being.
(If we, as I am currently decidedly proposing, give the rooms of HAM a fixed size, then the question we are currently leaving unanswered is whether we should choose the rooms so large that "they will always be sufficient" - a risky decision! - or whether we should create an organization in which a guest must leave his excess baggage in successive rooms or a central depot. We are merely signaling the problem now.)
The guests in HAM fall apart into two separate categories: blocked machines and interrupted machines. During non-activity of the coordinator there is one machine that falls into neither category, namely the abstract machine that is in action at that moment.
If control ends up in the coordinator as a result of an interruption, the abstract machine that was in action comes into the group of interrupted machines.
If control is referred to the coordinator as a result of a P-operation, this happens with the specification of one or more semaphores. If one of these semaphores is non-positive, then the machine that was in action goes over to the group of the blocked; if all specified semaphores are positive, they are all decreased by 1 and the abstract machine that was in action is included in the class of interrupted machines.
The interrupted machines are thus the machines from which the coordinator can choose; the blocked machines are those of which the coordinator does not need to take notice as long as the associated semaphore has not become positive. This happens by means of the V-operation and when the V-operation is performed, the coordinator must therefore come into action.
If this is a V-operation on a hardware semaphore, performed by an autonomous device, this happens with an intervention as a side effect; if the V-operation, of course by program, is performed on a programmed semaphore, then this program does not do this by an addition of an outcommand but by a (sub)routine jump to the coordinator. The machine that is interrupted in the V-operation is included in HAM in the class of the interrupted, logically there are after all no objections to letting this machine continue working normally after completion of the V-operation.
To indicate the subdivision into classes, we will string chains: each room of HAM contains space for another room number. The abstract machines that are interrupted are arranged in some order or other.
Externally we note the number of the first interrupted abstract machine; in each room we note the room number of the next interrupted machine and in the room of the last in the row we note a marker recognizable as such.
(If it turns out that we often have to add a newcomer to the company at the end of the row and the row can acquire an appreciable length, it is advisable to note externally not only the number of the first but also the number of the last in the chain. If we often have to operate "at the back of the chain", you can make the chain traversable in two directions by noting in each room also the number of the predecessor. Adding and removing becomes more cumbersome that way; I did not think this "double switching" was necessary. Keeping track externally of the number of the last is something else, because that has side benefits: it makes the marker superfluous.)
Premise of this technique is that we secretly still introduce a maximum size of HAM, namely via the number of bits that we make available in each room for the number of the next room; because this number, however, only increases logarithmically, you can maintain a majorant without undue waste that is always safe.
Before we now discuss in more detail the chains in which the blocked machines are included, it is good to consider for a moment why we have actually introduced the idea of blocked machines. We could do without it. If a machine performs the P-operation, but this cannot be completed because of a non-positive semaphore, then you could include this abstract machine in the list of interrupted machines, provided that as "state of progress" a reference to the beginning of the P-operation is included. If this abstract machine ever gets a turn again, it will surely try the P-operation again with fresh courage.
This has two disadvantages. First, it is not inconceivable that the machine then spends a demonstrable part of its time sweetening the failure of P-operations; second, the prevention of permanent neglect must then be watertight, because otherwise the computer could spend all its time on failed P-operations, while a meaningful process would find no passage. The introduction of the class of blocked machines can thus be seen as a means both to improve efficiency by not even trying things that are apparently doomed to fail, and as a means to keep our hands free later in the strategy.
Let us now look at the blocked abstract machines, for the time being under the simplifying assumption that each P-operation in a blocked machine receives only 1 semaphore as argument.
If the active machine now encounters a P-operation, control is referred to the coordinator; if the semaphore is positive, the P-operation is completed and the machine is included in the class of interrupted machines; otherwise it is possibly one of the many machines that must wait until the semaphore in question becomes positive.
Now, when the V-operation is performed on a semaphore, to discover which abstract machines can possibly be transferred to the class of interrupted machines as a result, it should not be necessary to search through all rooms of HAM to see if perhaps a blocked machine was also waiting on this semaphore. We can again provide for this search process with a chain.
All signal poles are housed in the Hotel for Signal Poles HS and are identified by their room number in this hotel. In each HS-room, besides the value of the signal pole, it is noted whether there are already abstract machines waiting for this signal pole to become positive; if so, these abstract machines are linked together in a chain and the HS-room contains (at least) the HAM-room number of the first in the series.
Now, when the V-operation is performed on a certain signal pole, the consequences that must be attached to it are clear. If the signal pole was already positive, we simply need to add 1 to it; if it was initially = 0, then we must check whether there are already abstract machines waiting, if so, one of these machines can be detached from this chain and included in the chain of interrupted machines. The strategic issue arises here in the case where more than 1 abstract machine was waiting on the signal pole in question; in that case, a choice must indeed be made.
It becomes more complicated when we consider that there will also be programs that, via P-operations with more than 1 signal pole, hand over control to the coordinator, and 1 or more of the specified signal poles are non-positive at that moment. A possible solution is the following, under the assumption that the HAM-room of this machine is large enough to contain the HS-numbers of the signal poles supplied with the P-operation.
The abstract machine in question is included in the chain of the first non-positive signal pole found. When this signal pole later becomes positive through a V-operation and this program is selected as a possible candidate for deblocking, then first the list of signal poles specified in its HAM-room is tested. Only if all of them are positive can the P-operation be completed, otherwise the result is that the machine is included in another signal pole chain. The chain attached to the signal pole on which the V-operation was performed is thus 1 shorter; if it has not become empty, a link is chosen again. Etc. etc. until the chain is empty or the signal pole is again = 0.
It thus amounts to the fact that the candidate for deblocking is made to execute its P-operation again, the P-operation for which the signal poles are now specified in its HAM-room. (That one of the tests is redundant because at least 1 signal pole is known to be positive, let us leave that aside; suppressing this test will require more time than just executing it.)
We thus see here two times, two situations in which the signal poles of a P-operation must be examined. I would like to name them: "the offered P-operation" and "the suggested P-operation", suggested i.e. by the becoming positive of a first blocking signal pole. Because it is tempting to exploit their similarity, it is good to point out the difference: when the coordinator is done with the offered P-operation, he can proceed to the order of the day, when the coordinator is done with a suggested P-operation, then the coordinator (at least if the P-operation has led to a new blockage) must return to the suggesting signal pole!
Organizationally, there is still an open issue, namely whether a HAM-room for an abstract machine can indeed accommodate this list of HS-numbers. The Hotel for Signal Poles also has a maximum size, which is expressed in the number of bits we provide for an HS-room number. Since P-operations can receive arbitrarily many signal poles, I can never guarantee in advance that a HAM-room is large enough. The best solution probably distinguishes two types of P-operations, those with no more than, say, three signal poles - this is the vast majority - and the P-operation with more signal poles. If the first is processed as smoothly as possible and the second type can also be handled, then we have done the one and not neglected the other.
A possible solution for the P-operation with arbitrarily many signal poles is the following: in the HAM-room, one records not only the return address for the case of a successfully completed P-operation, but also the return address that refers to the beginning of the P-operation. The offered P-operation processes the signal poles without storing them in the HAM-room; the suggested P-operation can now be simulated by letting the abstract machine start again just before its P-operation. The coordinator then receives a P-operation offered, of which it must still be known that this represents an offered P-operation. I suggest this solution with hesitation for two reasons:
|
(a) |
trying to complete the P-operation in this way does cost quite some time; the consideration that P-operations with so many signal poles will not occur so often is somewhat nullified by the consideration that precisely with a P-operation with many signal poles the chance of failure is large. |
|
(b) |
this runs logically smoothly if the program in which the P-operation occurred was still present on the cores; if not, then this little game, especially because of the special state of the coordinator, who after all must remember that this is actually a simulated suggested P-operation, could well become problematic. |
An alternative solution is to give an abstract machine more HAM-rooms at its disposal; the first time an abstract machine comes to initiate a P-operation with such a long waiting list, you will have to take the extra trouble to reserve one or more extra HAM-rooms as "follow-up rooms". I do not believe it is wise to release these "follow-up rooms" again after this demanding P-operation: you might as well assume that this abstract machine now once offers such demanding P-operations and that we should therefore leave the reservation in HAM permanent, until the abstract machine is completely removed.
As for the strategy for transferring from blocked to interrupted, I think you are quite well off when you, upon blockage of an offered P-operation, place the abstract machine at the beginning of the chain of the blocking signal pole and then, upon the V-operation, try to deblock the abstract machine hanging on the signal pole in order from beginning to end. This is the cheapest version of "first come, first served." This does not exclude permanent neglect of a machine that has remained stuck in a P-operation with more than 1 signal pole, i.e. when other abstract machines are contending for these signal poles. Can we say "So be it" here and conclude that this machine is therefore incompatible with the rest?
transcribed by Johan E. Mebius
revised Thu, 29 Mar 2007