This chapter is from the book
This chapter is from the book
This chapter is from the book
The Rise of Science: 1963–1967
With a working ALGOL compiler, and thereby freed from the confines of the physical hardware, Dijkstra was able to experiment with all manner of computer science issues. One of those early issues was multiprogramming. Dijkstra captained a team of five other researchers at the Eindhoven University of Technology who embarked on a project to build a multiprogramming system named the THE23 Multiprogramming System.
Dijkstra described this system in a famous paper24 that he submitted to the Communications of the ACM in 1968. The structure of that system was unique at the time, and showed just how far Dijkstra had come from his ARRA days.
This system ran on the X8 computer, which was a much faster and more capable derivative of the X1. The X8 had a minimum of 16K 27-bit words, expandable to 256K. It had a 2.5 μs core memory cycle time, allowing it to execute hundreds of thousands of instructions per second. It had indirect addressing and hardware interrupts25 that included IO and a real-time clock. For the day, it was an ideal platform for experimenting with multiprocessing.
Science
The architecture of the THE system was quite modern. Dijkstra was very careful to separate it into black box layers. He did not want high-level layers knowing about the intricacies of the layers at lower levels.
At the lowest layer (Layer 0) was processor allocation—this layer decided which processor would be allocated to a particular process. Above this layer, the executing program had no idea which processor it was running on.
The next layer up (Layer 1) was memory control. The system had a primitive virtual memory capability. Pages in the core could be swapped to and from the drum. Above this layer, the program simply assumes that all program and data elements are accessible in memory.
The next level (Layer 2) controlled the system console.26 It was responsible for ensuring that individual processes could communicate with their users with the keyboard and printer. Above this level, each process simply assumed that it had undivided access to the console.
Layer 3 controlled IO and the buffering of IO devices. Above this level, user programs simply assumed that data going in and out of various devices was a continuous stream requiring no management.
Layer 4 was where user programs executed.
In the mid-1960s, the discipline required in order to design an operating system with a carefully layered structure was brand new. The idea of creating layers of abstraction that isolated high-level policy from low-level detail was revolutionary. This was computer science at its best.
Semaphores
As part of this development, the team faced the issue of concurrent update and race conditions. To address this, Dijkstra came up with the semaphore abstraction that we have all come to know and love.
A semaphore is simply an integer upon which two operations27 are allowed. The P operation blocks the calling process if the semaphore is less than or equal to zero; otherwise, it decrements the semaphore and continues. The V operation increments the semaphore, and if the result is positive, it simply continues on. Otherwise, one of the blocked processes is released before continuing on.
As part of his write-up on semaphores, Dijkstra invents the terms critical section and indivisible action. A critical section is any portion of the program that is manipulating a shared resource in a way that must not be interrupted by another. That is, it does not allow concurrent update. An indivisible action is an action that must fully complete before a hardware interrupt is allowed. In particular, the increment and decrement operations upon semaphores must be indivisible.
Of course, nowadays we programmers know these concepts well. They were taught to us in our earliest years of coding. But Dijkstra and his team had to derive these concepts from first principles and formalize them into the abstractions that we now take for granted.
Structure
Another radically scientific concept adopted by Dijkstra was the notion that programs were structures of sequential procedures. Each such procedure had a single entry and a single exit. All adjacent procedures viewed it as a black box. Such procedures could be sequential in that one executed after the other, or they could be iterative in that a procedure executed many times in a loop.
This black box structure of sequential and iterative procedures allowed Dijkstra’s team to test the individual procedures in isolation and to create reasoned proofs that the procedures were correct.
The testing enabled by this structured approach was so successful that he proudly asserted:
“The only errors that showed up during testing were trivial coding errors (occurring with a density of one error per 500 instructions), each of them located within 10 minutes [of] (classical) inspection by the machine and each of them correspondingly easy to remedy.”
Dijkstra was convinced that this kind of structured programming was an essential part of good system design and was responsible for the significant success of the THE system. To dissuade detractors who claimed that its success was due to its relatively small size, Dijkstra wrote:
“. . . I should like to venture the opinion that the larger the project, the more essential the structuring!”
Proof
And this is where things start to get a little strange. In his write-up of the THE system, Dijkstra makes a remarkable claim:
“. . . The resulting system is guaranteed to be flawless. When the system is delivered, we shall not live in the perpetual fear that a system derailment may still occur in an unlikely situation.”
Dijkstra made this claim because he believed that he and his team had proven, mathematically, that the system was correct. This is a view that Dijkstra would hold, promote, and evangelize for the rest of his career. It is also the source of what I consider to be his greatest mistake. In his view, programming was mathematics.
Indeed, in On the Reliability of Programs,28 Dijkstra asserts that “programming will become more and more an activity of mathematical nature.” And in this, Edsger Wybe Dijkstra was, in my view, dead wrong.
