The Structure of the "THE"-Multiprogramming System Edsger W.
One-line summary: By strictly layering the system into a hierarchy,
system design, implementation, and debugging are all simplified - software
engineering applied to systems engineering.
- Pearls of Dijkstra Wisdom:
- Love your machine, love your project, love your co-workers.
- Half-time implies progress at an eighth of the speed.
- Systems design is really hard (but not rocket science).
- Tools of the times:
- EL X8 machine, 32K 2.3 uS core memory, 512K, 40ms drum disk
- MULTICS was under development (THE 1967, Multics 1965)
- THE system hierarchy:
- Level 0 - Processor allocation:
- Multiplexing of CPU among society of sequential processes
- Observation that processes only care about correctness of progression
of states, and not the rate of progression (except for real-time system)
- Mutexes for "harmonious cooperation"
- Level 1 - Segment controller:
- There are "core pages" (in core memory) and "drum pages" (on the drum
- The abstract memory unit presented to upper levels in the hierarchy is
called the "segment" - many more segments than core pages exist, segments
fit inside a core/drum page.
- A segment controller maps segments into core pages, and does the
paging between core and drum pages.
- Observation that it doesn't matter if programs' code pages are
contiguous on drum, or even which drum page is used to back a core page.
- Level 2 - Message interpreter:
- Routes console input/output to and from the correct processes. Mutual
synchronization used to mutex the real console.
- Above level 2, every process thinks it has its own private console,
its own CPU, and doesn't care about physical memory since it deals with
- Level 3 - Communication units:
- Buffering of input streams, unbuffering of output streams (to I/O
devices, peripherals, etc.)
- Level 4 - User programs
- Level 5 - Operator (?)
- Debugging as part of the design process:
- Each level of hierarchy tested individually, starting with level 0 and
working way up
- Simplicity of each individual levels made exhaustive testing of all
possible system states possible. Each level's states are isolated - if
didn't do as hierarchy, number of states would explode as the product of
each components' states, rather than as addition of individual levels'
states. (I don't believe it - interaction between levels will
- Complex reasoning about processes' mutual synchronization was required.
- Mutex primitives:
- P,V sempahore operations
- If a semaphore value is nonpositive its absolute value equals the number
of processes booked on its waiting list.
- The P-operation represents the potential delay, the V-operation
represents removal of a barrier.
- Private semaphores - way for a process to force itself to block, and
rely on external process to determine that the process should go ahead an
proceed at a later date. Essentially condition variables.
- Proving the Harmonious Cooperation - processes generate finite number of
tasks (for lower-level processes), all processes return to their "homing
position" eventually, but only if there are no unaccepted tasks outstanding.
(Requires proving no deadlock. Hard.)
RelevanceStructured system design. Rigorous enforcement of layering,
with all of the benefits.
- Proofs of correctness are more hand-waving than proofs.
- Is a strict hierarchy always going to be found? Why can't there be peer