Multiprogramming: Hotel Management


early 1963

Dijkstra generalized his multiprogramming problem by seeking symmetries, as I've explained in a previous post. Below, I examine how Dijkstra also drew an analogy with hotel management to further simplify his multiprogramming concerns (EWD 54).

The “coordinator” in X8's Multiprogramming System keeps track of which programs are suspended by semaphores, which peripheral devices are assigned to which programs, and so on. The coordinator is thus similar to a state official who administers people, Dijkstra noted. By limiting the population of semaphores, programs, and the like to a fixed number, say 10, Dijkstra continued, we could avoid a lot of administrative headaches. But accepting such constraints would also lead to a less general problem description. Therefore, Dijkstra concluded, we will take the administrative problem in its general form.

Dijkstra drew an analogy with hotel management. A guest of a hotel is for example a semaphore. Every new guest is assigned a free room by the hotel's management, the coordinator. The room's number serves as an identification number for the duration of the guest's stay. If the guest arrives when the hotel is full, the coordinator will build a new floor on top of the hotel and assign one of its rooms to the guest. The top floor will be removed once all its guests have left. The consecutively numbered hotel rooms correspond to consecutive blocks in X8's main memory. Tearing down the top floor of the hotel amounts to deallocating memory such that it can be used for other purposes. Furthermore, Dijkstra chose to assign the smallest free-room number to every new guest (— realizing full well that this design choice does not shrink the average size of the hotel's building).

An hotel can have regular customers, such as the hardware semaphores, the standard communication protocols, etc. These regular customers will be assigned to the lowest rooms, for they will enter the hotel at the very beginning and will never leave.

The coordinator manages multiple hotels: H1, H2, ...  Hn — with n a fixed number. One hotel houses the software semaphores. Another houses the abstract machines, and so on.

Hotel of Abstract Machines

Given an arbitrary moment in time, consider all abstract machines that are in a halting position. (These machines are halting due to a P operation or because of an interrupt.) These abstract machines, Dijkstra continued, are the guests of the “Hotel of Abstract Machines” (HAM).

The coordinator is not an abstract machine, nor is it then — according to the definition of HAM — a guest of HAM. Dijkstra insisted, however, to consider decoupling the coordinator into a core coordinator and several subcoordinators. The subcoordinators could then be treated as abstract machines and, hence, could be stored in the HAM. This design decision would thus lead to more uniformity.

In the same spirit, Dijkstra introduced the “Dummy Abstract Machine” (DAM), which executes the following code:

“LDAM: P(SDAM); goto LDAM”        — with label LDAM and semaphore SDAM.

The purpose of DAM can be explained as follows. When the coordinator does not have any abstract machine to wake up — because they all remain blocked by semaphores — it can execute a “V(SDAM)” instruction. This, in turn, will allow the DAM to execute the “P(SDAM)” instruction. Logically speaking, Dijkstra emphasized, a dummy abstract machine is not needed. But, it helps for the sake of generality: now we do not have to deal with the peculiar situation in which the coordinator has no abstract machine to wake up.

To conclude, Dijkstra was a man of generality and analogy.

As an aside: his writings also show how he progressively refined his thoughts while he wrote. At times he even explicitly apologized to the reader for not yet having a complete understanding of a particular concept — a concept that he introduced in order to carry through the analogy that led him.