E.W.Dijkstra on multi process systems

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: lawrence@krubner.com

There was some moment, in the late 1960s and early 1970s, when the field of computer science hit a happy fluid moment. By that point, a large number of people had been working with computers for 20 years, so they knew what worked and what did not work, and yet nothing had been settled yet, no architectures dominated. And then, suddenly, computers became a monoculture with standard parts:

1.) a CPU

2.) random access memory

3.) a storage device such as a harddrive

I imagine there were a wealth of other possibilities that were stifled but which still might yield some interesting insights.


Storage allocation. In the classical von Neumann machine information is identified by the address of the memory location containing the information. When we started to think about the automatic control of secondary storage we were familiar with a system (viz. GIER ALGOL) in which all information was identified by its drum address (as in the classical von Neumann machine) and in which the function of the core memory was nothing more than to make the information “page wise” accessible.

We have followed another approach an as it turned out, to great advantage. In our terminology we made strict distinction between memory units (we called them “pages” and had “core pages” and “drum pages”) and corresponding information units (for lack of a better word we called them “segments”) a segment just fitting in a page. For segments we created a completely independent identification mechanism in which the number of possible segment identifiers is much larger than the total number of pages in primary and secondary store. The segment identifier gives fast access to a so-called “segment variable” in core whose value denotes whether the segment is still empty or not and if not empty, in which pages (or pages) it can be found.

As a consequence of this approach: if a segment of information, residing in a core page has to be dumped onto the drum in order to make the core page available for other use, there is no need to return the segment to the same drum page as it originally came from. In fact, this freedom is exploited: among the free drum pages the one with the minimum latency time is selected.

A next consequence is the total absence of a drum allocation problem: there is not the slightest reason why, say, a program should occupy consecutive drum pages. In a multiprogramming environment this is very convenient.

Processor Allocation We have given full recognition of the fact that in a single sequential process (such as performed by a sequential automaton) only the time succession of the various states has a logical meaning, but not the actual speed with which the sequential process is performed. Therefore we have arranged the whole system as a society of sequential processes, progressing with undefined speed ratios. To each user program, accepted by the system, corresponds a sequential process (buffering input stream in synchronism with the execution of the input commands), to each output peripheral corresponds a sequential process (unbuffering output streams in synchronism with the output commands); furthermore we have the “segment controller” associated with the drum and the “message interpreter” associated with the console keyboard.

This enabled us to design the whole system in terms of these abstract “sequential processes”. Their harmonious co-operation is regulated by means of explicit mutual synchronization statements. On the one hand, this explicit mutual synchronization is necessary, as we do not make any assumption about speed ratios, on the other hand this mutual synchronization is possible, because “delaying the progress of another process temporarily” can never be harmful to the interior logic of the process delayed. The fundamental consequence of this approach —viz. the explicit mutual synchronization— is that the harmonious co-operation of a set of such sequential processes can be established by discrete reasoning; as a further consequence the whole harmonious society of co-operating sequential processes is independent of the actual number of processors available to carry out these processes, provided the processors available can switch from process to process.