LLL: choices (long)
Mon, 31 Oct 1994 20:38:26 +0800
It seems like there is a bit of a difference of opinion on what is
really being discussed with these things. This is only addressing
low level issues.
The following is a list of the kinds of questions I have seen asked,
or wonder about myself. After this list, I have my own opinions on
each issue (of course :-).
- VM -- What should it do? At what level should the VM code be?
Is one needed? Should it be RISC-like, stack based, something else?
- garbage collection -- Is it needed? If so, how can it be done
in a distributed system while maintaining an appropriate level of
system integrity/consistency? What kind of GC should be used?
Should it be global?
- message passing -- Who sends messages? How are they queued (if they
are at all)? What _is_ a message send, a procedure call, or something
more flexible? What is a message?
- hardware -- How should hardware be supported? What should a driver
in TUNES look like? How are interrupts handled? How is a task
switch started? What about paging, memory protection, disk access
etc. on heterogeneous platforms?
- security -- Where should things be checked? What level is the most
useful? Where is the line between performance degradation and
- persistance -- How much should be persistent? How should it be
done? Should a persistent object store replace the traditional
file system? If so, how can objects be saved onto tape or diskette
for backup? More importantly, how do you spell it?
Note that persistance + distribution + garbage collection becomes
very complex. The interactions of these things can be very subtle.
- distribution -- A workstation on a network is part of a distributed
system. I think it is very important to decide what kinds of things
and at what level things will be distributed. Should it be at the
level of individual objects such that an object reference might refer
to a local or a remote object? Should it be such that all object
references are local and special interface objects actually handle
the network connection to remote spaces? There are lots of
possibilities. What I mention here is just one end of a spectrum
of referential transparency.
- parallelism -- At what level should parallelism be supported? Should
it be at level of individual message sends as in Jecel's version of
Self? Should it be the opposite extreme and be at a process level
like Unix? Should the available processors be viewed as a pools of
executors for threads or should parallelism be handled on a processor
by processor basis?
- consistency -- Is it necessary that the state of the system be precisely
duplicated in the permanent store? If not, what kind of tolerance can
be allowed. Enforcing/assuring data consistency can bring in all kinds
of issues like blocking/waiting, access control, timeliness, data
duplication, caching behavior etc. What kind of consistency should
be addressed by the system? Data consistency, temporal consistency?
To help assure that everyone is thinking the same things I do when I
use the above terms, I have just sent the glossary from my final project
report to the list. I see that it has just shown up in my mail box,
so I will assume that everyone got it.
After introducing the above issues, it seems appropriate to give my
ideas about solutions/decisions regarding them.
- VM -- something quite RISC-like. I think that the bandwidth constraints
are less important than the ability to support multiple languages easily
and efficiently. I wouldn't put the VM in the kernel. I think that
superscalar processors will continue to have an advantage over VLIW
processors because they dynamically schedule execution. You can apply
all the tricks of VLIW compilation to a superscalar processor compiler,
but you will also gain this dynamic aspect. My money is on superscalar
and thus I have no problem with a simple RISC-like VM.
There are several tradeoffs here. If a RISC-like or generic stack-based
VM are chosen, then we have the possibility of using any one of a number
of high level languages to describe programs for low level code. However,
transfering such a program over a net will require a similar bandwidth
to transfering a native binary. If a high-level VM is used (e.g. like
that of Smalltalk), then the binaries get a lot smaller, but the VM
is larger and more complex, the process of locally compiling VM code
into local machine code is longer and the VM will not support all HLLs
equally well. One could write a C compiler for the Smalltalk VM, but
it would not be very efficient.
- garbage collection -- I think this is absolutely necessary and should
be implemented locally as part of a runtime, but not as part of the
kernel. There is a nice collection of papers at the University of
Texas at Austin by Paul Wilson. He also wrote a very nice overview
of single processor collection methods that is available for FTP there.
I am trying to track down a copy of a work by some people at the
Queen Mary College in London that is a survey of distributed GC
techniques. Francois-Rene may actually have better luck with this.
One of the authors is Elliot Miranda and the last I knew, he was at
the IRCAM in Paris doing LISP programming. Note that the persistent
object store must be collected as well and that this may involve
- message passing -- should be directly supported in the kernel a la QNX.
Distributed messaging should be handled as in QNX as well, let something
else deal with it. It should not be in the kernel. I have a Master's
thesis about message lookup techniques in dynamic languages that I am
going through. It is by Karel Driesen now at UC Santa Barbara.
- hardware -- the kernel is going to have to know about interrupts
and some form of tasking. However, it is possible to separate the
mechanism from the policy on this. QNX and Workplace/OS and Mach do
a fair job of allowing different kinds of user-level processes to do
task scheduling while the kernel takes care of actually performing the
task switches. I think that the Chorus solution of having the kernel
be net-aware is going to make the kernel to rigid and too large.
Disks can be supported without bloating the kernel too much. DOS machines
manage to boot without much in the way of ROM. Nothing more than a minimal
level of boot support should be in the kernel Perhaps it is not necessary
to support networking at such a low level. QNX gets a bit tricky here
by having the kernel capable of noting that a message is not destined
for a local task and sending it to a known user-level task that is
actually the handler for remote sends. It is a little more complex
than this, but not much. Chorus simply includes all this in the
kernel. I think that Workplace/OS and Mach 3.0 do the same as Chorus.
- security -- I am not too sure about this one. Ideally, individual
operations on objects could be controlled, but I think that this would
result in a terrible overhead on each message send. Any ideas?
If the basic operation in TUNES is a message send, then
placing security checks on each one could be prohibitive. Protecting
objects individually does not map well to all the currently used MMUs
I can think of. Typically, page sizes are 4kB and up. In most systems,
a page is the smallest unit of protection available from the hardware.
About the idea of allowing any access by an object if it has a direct
reference to another object. (I think Francois-Rene said this, but
I can't remember.) I don't think this is an effective solution. It
is very useful to be able to allow read-only access of some objects.
Adding wrapper objects that would intercept all accesses to
the wrapped object and only pass through the ones allowed has a hole.
Since I can have a direct reference to the wrapper object, I can access
and modify it. Thus, I could simply access the instance variable that
contained the direct reference to the wrapped object and I would be
able to circumvent the protection scheme. Be paranoid.
- persistence -- This is highly related to consistency (below). I
personally think that this is one of the points that will cause the
most contention. If you allow any given object to be persistent, then
you don't need to have an explicit filesystem. It would be nice to
be able to tell the system which objects are ephemeral/volatile and
which need to be saved for later. It is probably easier to develop
a system wherein the entire system image includes all objects and is
stored on disk. There is a fair body of work along these lines from
Smalltalk. A group at the U of Texas (Austin?) has developed the
Texas Persistent Store to allow C++ objects to gain persistency as
an attribute. While I would rather sell my grandmother for potato
chips than do a system the complexity of TUNES in C++, the ideas may be
interesting. One of the problems with a distributed persistent
system is how to handle remote references. If the system saves an
object with a remote reference when I shut it down, what happens
when it comes back up? How is that remote reference dealt with?
What if the remote system is not up?
- distribution -- I think that distribution should go along the lines
I described for task switching. It should not be an inherent part of
the kernel. It should be implemented by user level objects outside
the kernel. Note that complete location transparency requires that
very low level routines be able to send messages to local objects as
easily as remote ones. I think that QNX's solution of placing a hook
into the kernel will be enough support. Keep the kernel small and you
will have a chance at debugging it by hand.
- parallelism -- This is related to distribution. I think that systems
should be able to ignore how many processors there really are. Things
like load balancing should be part of high level system software, not
the kernel. Parallelism requires that there be some method of maintaining
consistency in system structures. See below.
- consistency -- This is the hardest point. There are a lot of people
doing PhD work on the topic of maintaining consistency in distributed
systems. A lot of questions arise like how to maintain a coherent view
of the system during shutdown if things are still active. Someone
mentioned the physics model of causality with light cones. The problem
with a distributed system is that the "speed" of information may change
dynamically and from place to place within the system universe due to
load and heterogenous networks. Thus, on each node/processor you will
have an expanding light/information cone, but there won't necessarily
be just one due to an event. If you want a precise control of
consistency, the overhead may stop the system from doing anything
Rebecca Callison did some very interesting work on consistency in
large real-time control systems like air traffic control networks in her
PhD thesis at the University of Washington. She should have finished
it in June, I think. If Chris Harris could find that stuff it might
be worth a look for other people. However, her object model would
be terribly restrictive for general systems. Nonetheless, she came
up with a very interesting way of handling uncertain data that is
applicable to distributed systems.
For those interested, the January (February?) BYTE has an overview of
QNX, Workplace/OS, Mach and a couple of other microkernel systems.
Jecel, which one is it? My memory is failing on this.
In short, I would like to see the smallest kernel possible that supports
message passing and task switching (but not scheduling). Everything
should be built on top of this by adding objects to handle specific
duties. Some objects can deal with the network and allow location
transparent message passing via the hook I talked about in the kernel.
Other objects can do things like handle the persistent object store
on disk. This will allow small discrete, self-contained units to be
written and tested. Note that the VM should be one of these add-on
Someone mentioned software engineering approaches to TUNES. I can't
remember who said it, but I think it was today. I agree 100%. Even
though the final system might actually use surprisingly little code,
an extremely clean, solid specification and design will make the rest
go much more smoothly. I have only had the pleasure of working on
one project where there was a very clean specification. The resultant
design was equally clean and the implementation was so fast it made
my head spin. Testing was easy because we had a clear idea of what
the system was supposed to do. At the time the constant documentation
writing and iterative spec and design processes seemed far too long
and hung up on detail. I have seen the error of my ways. Never again
will I stray from the path... :-)