From: Richard Jackson (richja_at_expedia.com)
Date: Sun Jan 11 2004 - 22:03:17 PST
Dennis and Van Horn wrote this 1965 paper to describe the general
programming methods for a multiprogrammed computer system, or MCS. They
defined a MCS as a system that is concurrently running multiple
computations that are being controlled by one or more operators/users.
Although the paper is almost 40 years old, I found it interesting that
the introduction mentioned the American Airlines SABRE system as an
example of a MCS. SABRE is still widely used today, though one must
assume that much of the underlying system has been refined over the
years. Still, if the name has gone unchanged, what else is still circa
1965?
As an overview of the domain, the following five features of a MCS were
presented: 1) multiple processes are running via multiple users, 2) many
resources are shared, 3) computations will have widely differing
resource requirements(especially over time), 4) reference to
common/shared information happens often, 5) a MCS must have flexibility
for constant improvements and changing requirements. Of these, #3
presented a problem. The authors noted that only average load need be
considered when allocating system resources. They mention peak load,
but claim that the system does not need to be tailored to this load.
What will happen to the system if the peak load exceeds the available
resources? Are they safe in ignoring this case? Also, #5 seems
obvious, and I am not sure that they needed to mention it in this paper.
A major concept that is used throughout the paper is that of a "sphere
of protection." This term isn't specifically defined in the paper, but
I understood it as the permission and/or abilities of some process(or
computation). A related concept is "list of capabilities" or "C-list".
This is a conceptual(and perhaps real) data structure that is used by
various objects within the MCS to indicate the actions that are allowed
with respect to that object. This concept was especially important in
the discussion of directory hierarchies and naming, which was discussed
later in the paper.
Many meta-instructions(programming primitives) were introduced
throughout the paper. Some are familiar, like: fork(create a new
process), quit(end a process), create(create directories or
segments(files)), lock/unlock(method for serializing critical sections
of code), etc. Others were less familiar: acquire(add a capability to a
C-List), receive(preparation step for sharing retained objects(i.e.:
persistent segments/files)), etc. The paper describes each of these in
detail, and does serve as a very good reference for these concepts.
The authors discussed object naming in much detail. They presented the
discussion in an evolutionary format, first explaining the various
problems that existed, and offering solutions. By this method, they
built up to their final proposal, that of a directory-based hierarchical
object scheme. While it seemed unusual during their initial
descriptions(before they determined that a hierarchy was needed), their
end result seems similar to some modern systems. In this section, they
asserted that object names can never change, due to the various
references that may exist. While they presented an interesting argument
here, this restriction seems quite limiting.
There was also a less-detailed discussion of a few other topics:
1-Supervisor module - this is the controlling hardware/software for a
MCS. The main functions are scheduling of processes and accounting of
computation time.
2-Inferior spheres of protection - They presented this using a debugging
example, such that a process may want to launch an inferior
computation(a child process) with less access rights, such that the
inferior process can be debugged. They also gave a long list of
exception conditions that could occur.
3- Protected entry points - a method of arbitrarily restricting use of a
procedure, used to prevent a process from accidentally misusing another
procedure.
The major strengths of this paper are:
1) Extensive documentation about naming conventions, definitions of
terms, and conceptual organization of a MCS
2) Listing of various meta-instructions/primitives that are important in
a MCS
3) Good discussion of naming considerations, possible problems, and
solutions
4) Interesting insight about the motivation for parallelism: "to relax
constraints on the order in which parts of a computation are carried
out."
The weaknesses of this paper are:
1) Perhaps too much elaboration on various terminology, such as
Principals
2) Meta-instruction naming is confusing in some cases, such as: delete
vs. release vs. remove. However, the authors do explain the differences
for more clarity.
Overall, I found this paper to be a good conceptual overview of the
programming semantics and concepts for a MCS, which is exactly what the
authors intended. Though they cited references to three real systems,
most of the paper seemed to be based on theory rather than an actual
implementation.
This archive was generated by hypermail 2.1.6 : Sun Jan 11 2004 - 22:03:29 PST