From: David Coleman (dcoleman_at_cs.washington.edu)
Date: Mon Jan 12 2004 - 13:42:22 PST
“Programming Semantics for Multiprogrammed Computations” by Jack Dennis
and Earl Van Horn is a description of a set of meta-instructions for
constructing a capability-based system along with a supervisor (which
can consist of both hardware and software) to execute these instructions
and maintain this system. The paper describes segments, the protection
system using capabilities, processes, computations, principals, and the
supervisor. Protected procedures and directories are also discussed.
Segments are the smallest unit of stored information and can contain
data or executable instructions. The default protection scheme uses
permission rather than exclusion and is implemented via capabilities.
Segment capabilities include access indicators (RWX) and also the
concept of ownership. A process contains all the state necessary to
continue to execute a sequence of instructions and is the smallest
entity that can be scheduled for execution. A computation is a list of
capabilities (a C-list or “sphere of protection”) and a list of
processes running in that sphere of protection. A principal is an
individual or entity to whom charges for resources used could be applied to.
The supervisor maintains the system and implements meta-instructions
which support the concepts listed above. The supervisor enforces
capability protection, allows new spheres of protection to be built,
allows for parallel programming (via the FORK, QUIT, JOIN, LOCK and
UNLOCK meta-instructions), and support for protected procedures.
The computation concept is an interesting one. It really creates a
task-focused system instead of a user- or process-centric model. There
is a one-to-one mapping between C-lists and computations. Each different
C-list is a different computation. However, a computation can consist of
multiple processes all running within the same C-list. So instead of a
process acquiring the rights necessary to contribute to a task, a
process is created in an environment with the rights necessary to
perform that task and only performance of that task (the computation) is
the goal of that environment.
Protected procedures are interesting in that they are both protected
from external procedures modifying their objects as well as they run in
a separate sphere of protection which prevents them from modifying the
callers objects. This allows access to objects from only a given set of
procedures without granting the rights to even read the objects to the
calling processes. Thus a caller can ask a database for the results of a
search without ever having the right to read the database’s data object.
Additionally, that database procedure cannot modify anything in the
caller’s environment that the caller didn’t specifically grant access to.
It seems that there would be some fairly significant performance
penalties for calling procedures given that the supervisor is involved
via the CALL meta-instruction. It isn’t clear if this only occurs at a
logical boundary (such as a module) or if it occurs for every procedure
call.
Directories allow the naming of objects. Directories contain a list of
names and associated capabilities. Interestingly, the capabilities in
directory entries can be for segments, protected entries, I/O
operations, or other directories. This allows for hierarchical directory
structures. Directories, through the use of the ACQUIRE
meta-instruction, allow for sharing of named objects between processes.
Objects are reference counted so by simply creating a directory entry
for an object, it can be forced to be retained. When the last reference
to an object is removed, the object is deleted. Objects can also be
explicitly deleted by their owners via the DELETE meta-instruction. It
isn’t clear what would happen in the case of a DELETE on an object with
a reference count greater than zero.
This paper presents some very interesting concepts: specifically
capability lists (spheres of protection), protected procedures, and
computations. I would be very interested to know the interaction between
Dennis and Van Horn and the creator(s) of Multics.
This archive was generated by hypermail 2.1.6 : Mon Jan 12 2004 - 13:41:45 PST