LLL: choices (long)

[Kyle Hayes]

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 
  security?

- 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
  distributed information.  

- 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
  useful.  

  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
objects.

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... :-)

Best,
Kyle