From: David Coleman (dcoleman_at_cs.washington.edu)
Date: Wed Jan 07 2004 - 08:49:52 PST
The Structure of the “THE”-Multiprogramming System by Edsger Dijkstra is
a fairly high-level description of the system along with some brief
discussions of how it was developed and some lessons learned. The paper
starts out with an overall introduction which describes the goals of the
project, the guiding design principles, and closes with the thought that
the individuals designing and building the system need to be pretty
smart and well-trained to make it successful. The hardware is described
(surprisingly powerful), a progress report is given (in which perfection
is claimed!), and the description of the system follows.
The Storage Allocation section was very interesting and seems to
describe an early implementation of virtual memory. An unfortunate lack
of detail prevents this section from being more useful. I would have
liked to have known what prompted them to explore alternatives to the
classical Von Neumann machine. Also, was special hardware necessary to
support this implementation? Was this really a description of virtual
memory and was it the original invention of it?
The Processor Allocation section makes a statement that I disagree with
in light that processes are used to control hardware: “… only the time
succession of the various states has a logical meaning, but not the
actual speed with which the sequential process is performed.” It would
seem that data loss is possible without a certain concern for processing
speed in certain cases. I suspect that those situations were implicitly
designed-for simply because they knew it wouldn’t work any other way.
The System Hierarchy section describes another significant contribution.
In short, it is a layered system in which each layer is responsible for
a certain class of hardware. Each layer knows only the hardware it is
managing; it knows nothing about the hardware being handled below it, in
effect abstracting it. Possibly this was aided by their guiding design
principle #2: Select a machine with sound characteristics and then
forget about the hardware (paraphrase).
The discussion of verification of the system hinged on 2 key points:
complete testing is impossible so intelligent white-box testing and
proof of correctness of the design was necessary. I’d also argue that
more ad-hoc, pseudo-random, real-world testing is necessary because it
invariably exposes timing holes and unexpected cases. Given the overall
simplicity of the system they developed, their verification methods
might not be sufficient for larger, more fully featured systems.
The discussion of synchronization in the appendix was interesting
although I didn’t understand the necessity or use of private semaphores.
Overall I felt the lack of detail hurt this paper. I find myself asking
questions like: “How did they come up with that?”, “Why did they take
that or a different approach?”, “How did they actually implement it?”,
or “How would I implement it?” and I generally wasn’t able to answer any
of them simply due to lack of information. However, the concepts of
virtual memory and layered, abstracted hardware were too significant to
complain much about the paper.
This archive was generated by hypermail 2.1.6 : Wed Jan 07 2004 - 08:50:19 PST