The discussion questions are classified into several
categories as follows:
Performance
By holding to a "strict hierarchical" system does
Dijkstra eliminate the possibility of effective communication between the
system's logical peers?
As robust as the THE was, would people back in 1968 be
screaming "sacrilege" for wasting so much capacity by building the five
layers of the operating system?
Do you think that the amount of book-keeping, keeping
track on which process belongs to which task and what is its order in the
execution + which segment is where, could hinder the system's performance?
Do they have a scheduling algorithm for tasks?
Considering that speed of completion is not an important factor in their
design, what can we infer about tasks' completion times?
The idea of an OS with layered structure is so great,
but are there any drawbacks with the design?
The paper has totally ignored the performance issues
involved in a hierarchical structure. I wonder if there are too many levels
of abstraction, will there be a lot of overhead involved in communication
between the layers? Do you think whether we can combine some levels to make
it better? and if so, what levels do you suggest to combine?
The paper is phenomenal that it contains many concepts
which are fundamentals of the operating systems nowadays.(e.g. semaphores,
layered architecture, the concept of segmentation and segment variables as
basics of virtual memory). My question is a bit non-technical: Would a
similar paper be accepted (so many new concepts, but lacking most of the
formal proofs and performance details) if it were published in our time? Or
is it the general technical format of those days? Or is it because of the
name? (Dijkstra by that time had his most famous algorithm published) I
don’t intend to offend anyone (the committee that day or any other
scientist) by my last question...
Dijkstra claims that there is no reason for a program
to occupy consecutive drum pages, but doesn't this increase latency when
retrieving multiple pages?
What would be the performance overhead for the
strictly layered / hierarchical model being presented in this paper?
The author described their system as having a 5-level
hierarchy. This seems like a standard idea, but one point that strike me is
that the number of processor being irrelevant above level 0. Is that a
save/efficient decision? In order to create efficient applications, is it a
good idea to know the underlying hardware?
Synchronization
In this paper, the semaphore is presented for what I
presume is the first time (in the appendix, no less). What synchronization
primitives were used before this, if any?
When the paper talks about process allocation, it
mentions the processes are sequential, how do these sequential processes
achieve synchronization issues?
Under synchronization primitives in the Appendix, 0 is
considered a +ve value?
What is the purpose of a private semaphore?
Are the individual programs submitted to this machine
strictly single-threaded? It seems like each is treated as a sequential
process, and semaphore block *system* resources, rather than logical threads
within each program.
How does the Deadly Embrace avoided in such a system?
I am lost on that since there is no proof, can you elaborate on that?
When the semaphore is unlocked, how to specify which
process to remove from the waiting list? This may cause an unfair issue that
some processes may have to wait an unexpected long time.
How does THE avoid deadlocks? Lack of circular waits?
How do they prove this?
State-Of-the-Art
Was there a different and more accepted method of
structuring operating systems before this paper was presented? How long did
it take before the foundational ideas presented here were incorporated into
the 'mainstream' and accepted by industry?
Is this bottom-up layered approach still used in the
design and implementation of modern OS kernels?
What OSes in use apply this idea in their designs?
Would you map the system hierarchy described in the
paper to that of a modern system? I would like to see any differences
between two hierarchies.
This paper is very old but it presents some ideas that
seem like common sense (ie. layered system hierarchy). Is this a basis for
most modern operating systems or have we gone a different way? More
specifically, do we use a similar 5 layer model or a variant of it (or
something completely different)?
I think the author considers the main contribution
here to be a system that is bug free. Modern systems are much more complex
and are probably a lot deeper that this one. Do you think this kind of
build then test technique is feasible on a modern system?
Harmonious Cooperation
The first step of proving the Harmonious Cooperation
(in the appendix), it is mentioned that processes can only generate tasks
for processes at lower levels. In modern Operating Systems, could that be
translated to: "Processes can only create work for other processes via the
facilities provided by lower layers in the kernel"?
Isn't the insistence that processes only generate
tasks for processes at lower levels of the hierarchy too restrictive?
Stage 1 of proof of harmonious cooperation: Does this
imply that a process (in the modern sense) can not start another process (in
the modern sense), but must be started by an entity in a higher level of the
hierarchy?
Would you explain the first stage of the harmonious
cooperation? I don’t understand the proof. A single initial task cannot give
rise to an infinite number of task generations.
Miscellaneous
How does this paper address its requirement for "a
reduction of turn-around time for programs of short duration"?
What lead them to this architecture of layers? Was it
because of the extremely constrained resources (i.e. part-time availability
of the members) that lead to this approach?
Did you find the phrase "art of reasoning" a bit
archaic? The language used in the paper just has a totally different feel
from more recent papers.
Is this the first introduction of extended virtual
memory addresses? That is, the pages (segments) of memory are now no longer
required to be paged in/out from the same drum location. This seems like a
major advancement and allows paging of memory > system memory in a highly
efficient manner.
When the author speaks about the objectives of the
multiprogramming system his team devised do you find that objective (4) is
rather limiting for a today's user? which groups of users would be affected
by the lack of capacity and/or processing power?
How do you think they keep track of where a segment is
once they put it back onto the drum in an arbitrary - minimum latency -
space?
They break each task into processes. How can they keep
track of which process belongs to which task? How small a process should be?
What is the significance of abstracting the real-time
clock at level-0 for the "segment" management processes on level-1? Why
would the "relevant states" exploded?
Not really a question so much as a comment, but does
the author's tone seems a bit too whimsical/arrogant? One of the more
interesting comments from the author is that, after commenting on his work
group currently having mostly people of half-time availability, he then goes
to lament about how poor production speed with '"half-time people" is...
The author states near the end that general testing
should be done via a completely white box fashion in order to suss out all
relevant test cases, yet recent (i.e last decade or so at the very least)
practice seems to lean towards black box testing. Is this mainly due to the
increasing complexity of programs making white box testing mostly not
viable, or is there some more sinister reasoning behind it?
It seems that THE only supports down-calls across its
layers. How are they implemented?
The pages (core and drum -> memory and disk page
frames?) and the segment (actual pages?) kind of model virtual memory? Or is
it more like just unifying disk and memory storage space?
Are the levels of the hierarchy now just 2?
Could you give an example and describe how this system
run this example, especially how the six levels work for the example?
Could you point out the advantages and disadvantages
of this system?
The paper says "These sequential processes are placed
at various hierarchical levels, in each of which one or more independent
abstractions have been implemented." Do its hierarchical levels seem to be
the kernel-user process hierarchical structure?
Does the strict abstraction of concepts from one layer
to another make debugging harder?
How do you think they managed to code the level 0 of
their system? punch cards, paper tapes?
Discussion Summary
The discussion was guided to address the main categories in
the questions asked. In general, the questions were in four main categories:
performance, state-of-the-art, synchronization, and proof of correctness. The
discussion addressed the point about performance Vs abstraction in more depth.
Some clarifications were given regard questions in the other categories. The
summary is organized into the four questions categories.
Performance
The question that was asked is: Does the layered
architecture of the OS have a huge performance drawback?
The layered architecture goal is to build abstractions that
are useful for clarity, ease of testing, and maintenance. These abstractions
impose some restriction that negatively affects performance. So we can say that
we beautiful abstractions that are not efficient. For example, Windows NT had a
layered-oriented structure in its first release but the performance was worse
than Windows 95. Then, they reduced the number of layers and put more
functionality in each layer to gain some performance back.
Another question is: With these abstractions how much time
would be before the users (programmers) hack around the inefficient
abstractions?
Layers are enforced by software. They are not supported by
hardware which make them optional. They are optional since programming
languages, such as C and assembly do not support these types of abstractions
leading to violations of these abstractions. The abstractions are considered
guidelines not realities. The abstractions look like the blue print of Linux but
the implementation uses various type of optimizations that violate these
abstractions.
Moreover, the layer abstraction is grouping functions and
data which are exactly the components of an object in an OO programming language
(so each layer represents a big object). It is arguable that this paper is the
beginning of a field that is trying to find the most useful abstraction. The
abstraction can be Layers, a microkernel, or a virtual machine.
State-Of-The-Art
Most operating systems consider layering as a guideline in
building there system. The idea of building OS using abstractions is useful
because it makes the system modular. However, the performance draw back made
layering useless in building commercial OS.
Synchronization
Synchronization was done through two types of semaphores:
Mutual exclusion semaphores
Private semaphore
Private semaphores are similar to signal and wait since we
a process locks itself and another process unlocks it. The notion of private is
slightly confusing; therefore, private semaphores proved useless and disappeared
from the synchronization literature.
Proof of Correctness
Dijkstra does not go into the proof details. He only
mentions the three steps which are proved in A. N. Habermann thesis. The proof
is trying to use formal methods in the verifying the OS correctness. The idea of
using formal methods to check the correctness of OS software fluctuates in a
cycle of interest. Currently it is a hot topic of research. A group in
Microsoft is creating tools to diagnose device drivers.