From: Ian King (iking_at_killthewabbit.org)
Date: Tue Jan 06 2004 - 00:00:35 PST
In this paper, Dijkstra discusses the design of a system to allow execution of
multiple programs concurrently on a single computer system, as well as some of
the lessons learned in implementation and testing of the system. The system was
designed and implemented for a particular machine, which is described only at a
high level. The paper also offers arguments of the correctness of the system as
flowing from its design. This paper addresses design process in general as much
as it describes a single design.
The design of the system is hierarchical, foreshadowing such later work as
Comer's 'layered' design for XINU. The hierarchy is also a simple one, a
'tower' of elements with one example of each; for instance, although there are
multiple peripherals, the peripheral management populates a single level, and
all user processes are peers in their level. The advantage is the abstraction
of the details of lower functions - for instance, the memory management
("segment controller") makes it unnecessary for higher layers to know the
physical location of a given item of data. (While "the system does not cater
to" assembly language, this scheme would likely also allow programs to be
commonly based on a single start address, as is customary in modern virtual
memory based systems.) The plan implemented in THE was quite effective in
meeting its stated goals, and Dijkstra recounts anecdotes of this isolation (for
instance, being able to test an upper-level feature despite the loss of drum
storage, by limiting test scope to employ only that memory that could be held in
core). However, it is interesting that it appears there must be interaction
between the scheduler and the memory manager, to preclude what Dijkstra
descriptively calls 'page flutter'; this suggests that the 'purity' of the
levels is not absolute, as the memory manager (level 1) needs to somehow 'lock'
certain pages until the scheduler (level 0) approves of their release.
(Alternatively, the memory manager could monitor the progress of the scheduler,
but this seems even more problematic). Such compromises are not uncommon or
necessarily bad, but Dijkstra seems almost sneaky in his passing reference to
this one.
Dijkstra does not provide much detail of implementation, and even lower-level
details of design are lacking. For instance, there is no discussion of how
processes are selected for scheduling (presumably there is some system to
prevent process starvation, even if simple round-robin); he makes mention of
'rules' for scheduling, but never describes the rules or their implementation.
He is intent on educating the reader on the process of design and
implementation, with the actual execution left as an exercise for the student.
The focus is on structure, but also on process upon that structure.
The discussion of process is both fascinating and disturbing. One one hand,
Dijkstra makes several insighful observations about the design process and
importance of attention to detail here; this is clearly borne out by modern
practice. He states some basic principles regarding availability of developers'
time, and their effectiveness when randomized, later expounded upon by Brooks in
The Mythical Man-Month. His admission regarding the paucity of debugging
facilities is also noteworthy, and he exhorts programmers to write testable
code. However, I would argue he places too much faith in analysis of the design
as precluding the possibility of defects. His scheme of testing from the bottom
up, beginning with the lowest-level abstractions, is a good strategy; he then
states that the danger is that one does not anticipate all possible conditions
and states in testing, but apparently does not grant sufficient credence to his
own argument. For if one does not comprehensively address all potential states
(impossible though that may be), the argument for the system's 'correctness' and
'rigor' seems unsupported - it is an argument in which necessary premises may
well be missing. Then, too, his use of synchronizing primitives, while
potentially creating a system free of race conditions, does not seem to preclude
deadlocks, and he even describes a classic deadlock that is not avoided by
semaphores alone. (One could wish his reference to a proof would have been set
forth in more detail here.) Further, in modern practice it is recognized that
excessive use of synchronizing primitives can adversely impact performance, and
careful thought goes into their application. While Dijkstra's requirements did
not include 'optimum performance,' subsequent software developers would find
that criterion near the top of customers' wish lists.
All in all, THE is structurally a very interesting and in some ways prophetic
design, but as many designers have learned over the years, a great design is no
guarantee of a defect-free implementation, and correctness proofs have still not
replaced the need for rigorous testing.
This archive was generated by hypermail 2.1.6 : Tue Jan 06 2004 - 00:05:15 PST