>>The interesting thing about KeyKOS in this regard is that it is
>>schizophrenic. It supports the first model for relationships among
>>user-level programs, but the KeyKOS kernel itself, considered as a "server"
>>whose clients are all the user-level processes in the system, is designed
>>very strongly around the second model.
>
>The KeyKOS model allowed the designer a great deal of flexability about
>which of these two models would be used. They could even be combined.
>
>The standard way of passing resources was to pass a space bank and a meter.
>The space bank provided trusted pages and nodes. (Since there could be
>many space banks in a system, the a program could trust some and not
>trust others. Some banks might provide replicated pages while others
>did not. Or pages on unsecure devices etc.)
I stand corrected. This is exactly what I've been envisioning all along, except with the possible addition of priority inheritance which would allow servers to accept untrusted meters in some cases. My respect for KeyKOS is increasing. :-)
>>I conclude with some reluctance that there are really three categories
>>of page in the system we're discussing:
>
>Perhaps a fourth kind of page is a page under the control of a external
>manager (e.g. a network remote page), but which has local disk backing
>storage. The kernel can put it on the local disk when main storage
>pressure gets too high, but its manager can always get it back to
>return it through the network to its "real" home.
This is exactly the idea behind Mach's model, with paged-out pages getting "reallocated" to the default pager while being queued for page-out by the "real" external pager. It's a good idea, although Mach's implementation obviously had some glitches, such as local backing store not being reserved until page-out time.
>>I never suggested that kernel data be made available to untrusted code.
>>The point was that the mechanisms used to protect kernel data from
>>access by untrusted code, while still allowing untrusted code to transfer
>>and exchange kernel storage like a currency, is something often needed
>>by servers as well for their own internal state, and it would be better
>>if the same abstractions and implementations could serve both needs
>>in the overall system design.
>
>There are several ways to do this in the KeyKOS model. Perhaps the most
>generally useful technique is the "red segment". [...]
Although this strikes me as a bit of a kludge, I must admit it's quite novel! :-)
>>Similarly, you might object that the stopped thread may be holding locks in
>>the server and preventing other clients' threads from making progress; but
>>in fact this is just the classic unbounded priority inversion problem, and
>>any traditional priority inheritance scheme will solve the problem.>
>
>I assume you are saying that I, a client of the server, should give
>resources to some other flat-out-broke client so his thread can proceed
>and release locks so I can obtain them.
_Somebody_ has to in any case: if it's not another client of the server, then the server itself must provide those resources. Neither way is really "fair". Which is the lesser evil?
Basically, this is just the classic priority inversion problem that's been beaten to death in the real-time community. In summary, it's impossible to get perfect CPU resource allocation in the presence of thread synchronization dependencies; what _is_ possible is to set an upper bound on the amount of priority inversion ("CPU misallocation") by using priority inheritance in conjunction with a sensible server design.
For example, with priority inheritance you can design a server that guarantees to its clients that no client's request will be delayed longer than 'n' milliseconds due to lock contention. That 'n' milliseconds is the "maximum CPU misallocation" factor, which is always there whether the server is providing the misallocated CPU time or its other clients are.
I submit that, as long as this factor is small and bounded, it doesn't really matter exactly how the misallocation occurs; it's just one of those unavoidable factors that must be accounted for in the system design, similar to the unpredictable-but-bounded delays caused by the kernel "stretching" a process's CPU time quantum occasionally, or device interrupts that unfairly eat up time from arbitrary processes.
>>For the kernel to entrust privileged state to a user-mode device
>>driver that is part of the TCB is fine. I wasn't arguing against
>>that. In the example you give, the kernel can still make progress on
>>other tasks while the pageout is in progress.
>>
>>The question is whether it is "safe" for the kernel to *block* on such
>>a process. In my opinion this is unsound.
>The KeyKOS kernel did not block on I/O. There were no "kernel processes".
>Instead, it aranged for the process on whose behalf it was running, to
>sleep on the I/O operation. After the I/O completed, the process would
>re-issue its request (or not if someone with a domain key changed its
>mind), and the operation would be reconsidered from the start. This
>technique allows all kernel locks to be released and eliminates the need
>to re-validate memory addresses in the processes local storage (stack,
>registers, etc.) Charlie and I have been trying to get a paper published
>on this subject.
Isn't this just the standard continuation model for kernel structuring? The V kernel from Stanford works the same way, as well as a number of other microkernels I've read about.
BTW, if you're looking for something publishable, I'd suggest writing something about the way KeyKOS supports client-provided, server-trusted resources (space banks, factories, etc.) and about how those facilities are used throughout the user-level facilities in KeyKOS. I've run my ideas for this kind of resource allocation by a number of well-known OS researchers, and judging from the typical knee-jerk "that can't possibly work" reactions I usually get, it's definitely not yet a well-known or accepted idea. Having a good proof-of-concept paper I could point to would make my life a whole lot easier in convincing other people that this is a good direction for Mach to head in. :-) Include some good benchmarks and measurements on the performance, predictability, and isolation characteristics of the system, and it could easily get into the upcoming SOSP.
Bryan