From: avg@uunet.uu.net (Vadim Antonov)
Newsgroups: comp.os.research
Subject: Re: Have we learned anything in the last 20 years?
Date: 13 Apr 92 00:17:38 GMT
Article-I.D.: darkstar.32797
Organization: Berkeley Software Design, Inc.
Originator: osr@ftp


Here is my $.02 (not dve kopeiki anymore) worth of oil to that flame;
basically it's what i learned experimenting with various approaches
to micro-kernels during the last seven years in my spare time.

I won't waste my (and your's) time discussing things like where to
schedule threads and put filesystem to; it's not very important with
hardware which is not completely brain-dead -- you'll have to have
a filesystem in OS anyway. The problem is that something is wrong with
the modern breed of operating systems as a whole -- i've got a STRONG
impression that all those new systems provide no NEW functionality
comparing with 15-20 years-old designs.

I'll try to express what i think without excessive math (not that it
exists :-) and will try to keep from philosophical speculations
ar far as possible.


So, FLAME MODE ON.

Let's start ab ovo.

Basically, there are five classes of machines:

0)	Discrete structures (exmaples: sets of sentences and
	production rules; schemes, texts of algorithms)

	Machines (let's call it in this way) of this class
	do not evolve in time. Turned off ICs and PCBs belongs
	to this class as well.

	The volume of information traffic between parts of such
	machins is obviously zero, though the notion of time is not
	completely useless concerning machines of this class --
	transcribing such a machine takes some time (something like
	O(length-of-text)).

1)	Deterministic digital computers (all flavors of them)

	These machines exist in discrete time and their parts
	interact with messages containing well-defined numbers
	of bits. It's the "modern" paradigm of a computing
	machine.

2)	Stohastic digital machines, analog machines and pseudo-analog
	circuitries (like lossy digital communication channels) with
	explicit structure (i.e. with parts which can be viewed as
	separate machines (modules, black boxes etc)).

	By their construction most modern electronic machines belong to
	this class. The most interesting feature is that you can't
	tell the exact amount of information carried by each elementary
	interaction, though the ways information go is clearly distinctive
	(PCBs are designed not to pass information between neighbour leads,
	aren't they? :-)

3)	Finally, the machines with no modular structure; i.e. each elementary
	part of such machine can (and do) interact with any other.

	Physical systems, to be brief. Humans and their tools belong
	to this class (though it's not proven that humans do not belong
	(at least partially) to the following class).

4)	Supernatural, transcendent, divine devices.

	Added mostly for fun :-) (to be able to appeal to deus ex machine).
	I can say nothing about features of these machines, can you?

The interesting property of those classes is their "symmetry" in
time/probability domain -- i.e. every machine of higher class can be
simulated with some precision (i.e. with some probability of actual
behaviour being in simulated margins) by some machine of lower class.
The higher precision the longer time will simulation take. (The notions
of "probability" and "precision" feels somewhat fuzzy concerning simulation
of machines of class 1 but i lack appropriate words). Vice versa,
for any machine of lower class there is a machine of higher class which
can with some probability behave like the machine of lower class during
some limited period of time.

Note that i do not do any difference between "physical" and "logical"
parts of these machines -- i think all readers agree that mathematical
objects and software are as real as hardware is.

While discussing of relationships of these classes is fun enough, let's
return to our rams (and roms :-). 

All modern operating systems are designed for machines of class 1 and
lack some sufficient architectural features to serve machines of class 2.

First of all, if we can't determine the amount of information passed
from one element of machine to another we can't create a system which
encapsulates that information into some kind of unified message and
tries to deliver it. In other words, an operating system of class 2
CAN NOT be a data carrier and SHOULD NOT know about the nature (digital,
analog, big-endgian or frequency-modulated) of information representations
used by modules to interact. If they interact they both know about it,
right?

Practically, it means that message-passing (and everything-is-file)
systems will never be able to incorporate class 2 interactions into
their basic sets of primitives. In the real life such interactions
are handled by specialized application-level software (trivial examples
are "operating systems" of telephone exchanges and robotic controlling
systems).

"So, what can such a system do if it can't meddle in information
exchange?" you could ask.  The answer is quite simple -- it can shape
the channels information is flowing by. In case of shared memory it's
flipping the page registers. In case of telephone conversations it's
toggling electronic switches.

Unfortunately, an operating system itself cannot incorporate knowledge
of all kinds of switching devices; so it should allow applications
to serve as "external" switch controllers.

The basic model of interactions in such system is passing pointers
or, better, accesses between producers and consumers of information.
Let's call the entities associated with the specific modules (entry-points
or pins or hooks or ports) simply -- objects. Accesses always point to
objects. Objects are nothing more than passive visible parts of modules.

Having an access to object module can intiate a transaction.
The elementary transactions consist of passing *accesses* between
two modules.

[you aren't expected to understand this (sic) :-) ]

Ok. Accesses can be used to share or obtain other accesses. Sounds like
a "thing for itself" (a term by a greatest teoretican of mass murdering, if
you don't know). Now, how the actual exchange of information tied to
that?

First, we'll need the notion of protocol (associated with an access).
Protocol P is a set of kinds of accesses (let's name them with the words
W[1]...W[n]) bundled with protocols of accesses they carry to and from:

P = { (W[1], to:{P[1], ..., P[i ]}, from:{P[1], ..., P[j ]}), ..., (W[n]...) }
                               1                        1

As you see, that notion is recursive by nature. Surely, in any hierarchy
of protocols should be at least one protocol with empty to:/from: sets
or with to:/from: sets containing the only the same protocol (there is
also a case of a cycle but i'll drop it for now, although it can be
interesting thing to discuss). Let's call such self-defined protocols 
"basic protocols".

Every basic protocol corresponds to some physical method of information
exchange. Other protocols may be reduced to basic protocols (surely,
nothing prevents non-basic protocols of having associated physical
methods).

As an example, let's look at the model covering "typical" digital
machines. The basic protocol for those machines is the protocol of
operating memory with three basic operations: 

PMEM = { ("read", to:{PMEM("write")}),
         ("write", to:{PMEM("read")}),
         ("part-of", from:{PMEM}, to:{PMEM("read")}) }

X."read"(M) copies contents of M to X,
X."write"(M) copies contents of X to M, and
Y <- X."part-of"(A) assigns to Y access to the part of X with bounds
read from memory object A.

Computers have a device called RAM which contains all the data (i
simplify, of course). Now if some module asks memory to read data
it actually gives memory accesses to both memory pieces and RAM
module KNOWS WHAT TO DO WITH THAT (not the operating system!).

Ok, there is another thing called ALU. It can be represented as a
piece of memory -- you put arguments to some locations and get results
from other locations (some real devices like Weitek math coprocessors
really work like that!). No new abstractions required providing that
ALU can send/receive bits to memory when required.

Finally, the controlling unit(s) are simple automatons which can
have a number of acccesses (let's call it contexts) and retrieve
data from memory (commands) and issue sequences of PMEM operations
to accesses they have.

Now, let's look how this scheme handles DMAs -- a usual pitfall for
"traditional" architectures. Quite simple -- if you need to read something
from disk to memory give the access to memory to the disk driver! The
driver transforms system protocol into device command and the device
will perform the physical data exchange.

The major feature of that approach is the possibility of automatic
reduction of protocols to basic ones invisibly to protocol's users.
For example, if we have an access with a memory protocol associated
with an object belonging to a file system and issue, say, "read" request
the file system can get the access to the destination memory we supplied,
pass it to the disk driver together with addressing information and
the driver will perform the actual copy.

In practice this scheme is a bit more complicated because not every
kind of memory can be made directly accessible to controlling units.
It means, that the memory subsystem should support "layered" memory
or "caches" but still it does not impact the basic set of the system's
primitives.

Surely, these primitives can handle things like accesses to telephone
sets as well as accesses to memory pieces :-)

I hope you noted that this scheme lacks the usual processes or
threads -- actually there are contexts associated with NON-PROGRAMMABLE
automatons (say, virtual processors) and pieces of memory. It works
equally well for single-threaded automatons, clusters of threads or
for fancy data-flow engines. There can be an (logially external to the
system) device producing new automatons; or alternatively we can
view it as a large set of already-existing units. Surprisingly, this
approach covers machines which can physically modify itself (i'd like
to see the machine inserting new PCBs into itself with a kind of a robotic
arm!)

I bet you're still asking what all that stuff has in common with the
practice. Ok. Such systems CAN BE BUILT. They can be made at least
as effective as traditional systems on traditional machines as well;
though there are no full-scale implementation is available right now
(it's the reason why i wrote virtually nothing about it). The only
published text is my (rather cryptic and written in terrible English)
article in ACM OS Review; it contains brief description of a working
model of such a system. I haven't pushed this work much furter since
that time 'cause i've to earn money (damn reality) by terminally boring
things like writing drivers for the brain-dead PC hardware.
Moreover, i'm not so naive to think that a lonely hacker with a
zero-funded project can develop some real system.

Guess what i think do we have learnt something during the last 20 years? :-)

Vadim Antonov