Promptness, queueing, diskless etc. etc.

[William S. Frantz]

>Note, however, that if a server somehow contrived to let itself run on
>the user-provided meter, and the meter ran out, you were basically
>hosed.  There isn't an obvious way for the server to protect itself
>that I can see.
 
Charlie aluded to the concept of "prompt", a concept which deserves more
discussion.  Prompt is a bit like obscenity, I can't define it, but I
know it when I see it.  A working definition which applies to KeyKOS is
that nothing outside the computer, e.g. a user with a debugger, can
block this process forever.
 
Certain activities are inherently prompt.  e.g. Accessing a page.  (The
kernel will bring it in if it is on disk.  If it is invalid, the domain
keeper will be called (or a non-zero return code will be returned to
the key invocation).); Calling many kernel implemented keys.
 
Other services, like public factories, depended on meters.  They are
only as prompt as their meter, so there are different kinds of promptness.
 
In order to ensure promptness, the general philosophy was to have users
contract for services.  This contract could range from payment in advance
to I'll bill you later.  However, all of these contracts permitted the
server to use its own resources to provide the service while recovering
their costs through the service contract.  In some sense, from the user's
perspective, a server request is atomic.  Once issues, it can not be
stopped until the service has been provided.  (Already I am thinking of
ways to provide a user with a "Stop, I've lost interest" key. :-)
 
 
>The invocation semantics in KeyKOS include locking directly.  When two
>messages are sent to a domain, the domain receives one and the other waits.
> This seems like locking to me, and can be used to implement pretty much
>any other sequential synchronization construct.  Does KeyKOS specify
>fairness for domains waiting on a key invocation?
 
KeyKOS specifies that it will try for FIFO queueing.  There are a number
of cases where the kernel will not provide FIFO queueing.  They include:
after restart, when the invoker changes its mind, and certainal pathalogical
cases when the invoker is slow at re-issuing the invocation.
 
 
>An early version of KeyKOS specified something very similar to the
>"working sets" proposed by Jonathan. In addition to CPU time, meters
>metered out "core residency" for virtual memory. (There was also a third
>resource, I/O channel capacity.) We dropped the idea, partly because of
>the sort of problems Jonathan is trying to work out, but mostly because
>we were busy and didn't see much use for it.
 
Tymshare's VM system implemented such a scheme where it was a big 
competitive advantage over the VM-size*time charging of competing
systems.  We never used, but should have, "Tymshare cuts the cost 
of doing nothing!"
 
 
>Yes.  If you invoke the highest keeper first, it can daisy-chain the
>fault downward by accessing the faulting page in the child segment.
>You can't easily daisy chain in the other direction.  I suspect some
>argument of this sort may have influenced the decision.
 
KeyKOS gave you a choice through the "no call" bit.  The "no call" bit
was also the only way to avoid blocking on slow segment keepers.  If a
keeper set the "no call" bit, it would receive any faults generated
by pages below it in the tree.  I could, although I know of no actual
implementations, use a helper domain to access the same page thru a
segment without "no call" and cause a lower-level keeper to be invoked.
A segment keeper could always cause the domain keeper to be invoked.
 
 
>3. Once user data objects are not made up of atomic objects of
>homogeneous size, the design of a backing store manager grows
>difficult.
 
In the early days, e.g. Multics, designers accepted the complexity and
poor performance of variable size data objects (pages, file system
blocks, main memory protection zones) as a trade off for the savings
in real hardware.  As hardware has gotten cheaper, people have been
willing to spend it for simplicity, and particulary for performance.
 
 
>A simple possibility: architect the system overall to use a disk page
>size of 4k and the current node structure.  Let the actual protection
>of a mapped core page be the least protection of any of the subpage
>keys, and require that all necessary 4k component pages be available
>before mapping a larger page.  This would work, but I'm sure y'all
>will propose something better.
 
A quick question is why you want small pages?  A system with 64K pages
would be straight forward.  The most compelling reason for small pages
is storage efficency, particulary with UNIX files being used as they
are.  The case for large pages becomes more compelling as the speed of
processors increases in relation to the speed of paging devices.
 
One approach to mapping small pages into large slots would be to check
if the large frame had been written beyond the extent of the small 
page and invoke a segment keeper if it had.  (All addresses beyond the
page would read as zero.)  You might want to have the kernel provide
R/W access to such pages to only one domain at a time, so you would
be able to check when rescinding the R/W access and identify the domain
responsible for changing beyond the page should the segment keeper
decide to reflect the fault to the domain keeper.
 
 
>Once we resolve that, my next question will be how to implement a
>diskless KeyKOS system.  What new protocols, if any, is needed if we
>are going to adopt the view that pageout is to be handled by
>user-level code?  Tentatively, I think that if we can go diskless, we
>can distribute effectively.
 
Let me see.  In order to have a remote disk KeyKOS, we will need to
have the following pieces of software:  (BTW - I work with a diskless
KeyKOS system.  I doesn't remember anything between restarts.  Since it
is a communication controller, lack of memory is not a problem.)
 
  External Page Manager
  Network Interface
  
(I will assume only one external page manager.  "Multiple external
page managers are an excersize for the student.")
 
We must ensure that these pieces of software don't block themselves.
Perhaps the simplest technique would be to make all main storage
management external.  The page manager has a capability which allows
it to read/write any frame of main storage and to define what page ID
it contains.  It can also wait for a page fault.  A page fault sends
it a message giving the page ID of the faulted page and the type of
access desired.  It must determine which pages are necessary to perform
paging and ensure they are not swapped out.
 
These capabilities are sufficent to build LRU but, for performance
reasons, we might want to add an interface which allows the kernel
to perform the LRU logic.  Initialization is an excersize for the
student.

-----------------------------------------------------------------
Bill Frantz                   Periwinkle  --  Computer Consulting
(408)356-8506                 16345 Englewood Ave.
frantz@netcom.com             Los Gatos, CA 95032, USA