From: Richard Jackson (richja_at_expedia.com)
Date: Wed Jan 07 2004 - 15:50:13 PST
This 1967 paper by Edgar Dijkstra gives an overview of a
multiprogramming system called "THE". This system was developed in the
late 1960's by a team of 6 half-time people at Technological University
in Eindhoven, The Netherlands.
I found Dijkstra's introduction very interesting, as he laid out the key
design principles for the system. These principles are generic enough
that they could be applied to many other projects, and they are still
relevant today. They are summarized here:
1) Select a project that is very challenging and excludes most
superfluous features that only add cost
2) Choose a good platform, but don't tailor your design specifically to
that platform
3) Learn from past experiences, and do not repeat past mistakes
Finally, he made a very interesting comment about half-time engineers.
He claims that these people are less productive by a factor of four! To
some extent this is logical, but he seems convinced that the cost is
even higher than one might expect. This short aside by Dijkstra was one
of my favorite parts of the article.
Next, Dijkstra gave an overview of the target hardware platform and an
overview of the specific problems they were trying to solve(i.e.:
provide a system to run user programs at this University). He then went
into a short summary of the current status of the system, describing
some of the traditional challenges that hinder any development
effort(scope creep, high debugging costs). He also made some assertions
about the supposed correctness of his system, claiming that "logical
soundness can be proved a priori" and "system is guaranteed to be
flawless." While I tried to keep an open mind while reading the rest of
the paper, I definitely have major concerns about his optimism.
The core of the paper was devoted to an overview of the internals of the
system. An overview of storage is given, with some high-level notes
about optimizations that were utilized. Another similar section
describes the processor abstraction and ability to synchronize activity
between multiple concurrent processes. The most interesting portion of
this section talks about the hierarchy of the system. Dijkstra explains
that processors are controlled at level 0, segments at level 1, messages
at level 2, IO at level 3, user programs at level 4, and the operator at
level 5. The organization presented here is logical and seems to
support Dijkstra's theory of making the system "guaranteed to be
flawless" via a testable hierarchy. Going on, the author explains how
each level was exhaustively tested, and how all relevant states were
checked. Again, I question the thoroughness that is possible here, but
for a small system, I suppose that some chance of complete testing is
possible. Still, I do not consider Dijkstra's system to be small.
As an appendix, Dijkstra gives an overview of semaphores and explains
how their system used these primitives in two different ways(mutual
exclusion and private semaphores). This appendix is interesting,
though it does not seem critical to the focus of this paper. Many of
these concepts seem quite well-known, although at the time perhaps they
were not ubiquitous..
The major strengths of this paper are:
1) Good historical overview of an early computer operating system
2) Good(but very optimistic) philosophy about hierarchical design
techniques and testability benefits
3) Interesting viewpoints about software engineering issues(development
team, process issues)
4) Good support for a thorough testing methodology
The weaknesses of this paper are:
1) Limited technical details about the design
2) Strong assertions about system correctness without much supporting
detail
Overall, this paper was enjoyable to read. Dijkstra's writing style is
somewhat lighthearted, given the subject matter. I think the paper
would have been much better if he'd given more support for his various
controversial claims about system correctness.
This archive was generated by hypermail 2.1.6 : Wed Jan 07 2004 - 16:18:42 PST