The Demos kernel is about as small as a kernel can get, and therefore serves as an interesting example! What is in the kernel, and how does this relate to servers such as the process manager?
Here is a simplified list of Demos kernel services:
make-link -- create a new link to a mailbox send -- send a message over a link to the mailbox of a process receive -- await a message in a box of this processGiven these services, what data structures must the kernel understand? The definiton of a process provides the first part of the answer to this question:
A Demos process:
Memory Segment Link Table
________________ __________
| | |__________|
| | | ___|
| | ___ ... |
| | |__________
| code | |__________|
| |
| stack | Mailboxes
| | __________
| heap | |__________|
| | | ___|
| | ___ ... |
| | |__________
| | |__________|
|________________| |__________|
It is worth remembering that the extremely simple memory model of
Demos, one memory segment per process, was forced on the developers
of the system by the crude protection mechanism of the Cray 1 computer.
Seymour Cray believed that anyone buying a supercomputer could afford
real memory, so the only protection mechanism provided by the hardware
was a simple base and bound register. Cray understood the MMU only as
a mechanism to support demand-paged virtual memory, and he did not
understand the utility of the MMU for providing access to a complex
structured address space, for example, with a mix of shared and private
segments.
So what is a link? In the abstract, a link merely names a mailbox. It would be possible, on a uniprocessor with a huge memory, to represent a link by a pointer directly to the mailbox that link referenced, but if processes have short lifetimes, this would lead to trouble. If a process terminates, all links to mailboxes of that process should become invalid. Therefore, we construct a link as follows:
A Demos Link
____________ ________________ ________
|____________|________________|________|
| Process ID | Mailbox Number | Rights |
On the original Demos system, the process ID was just an integer, and process
IDs were issued sequentially to processes as they were created. Later,
when Demos was ported to a multicomputer, the process ID field was subdivided
into a machine ID field and a process ID relative to that machine.
The mailbox number for a process is an integer, an index into the array of mailboxes maintained by the kernel on behalf of the process. The rights field contains bits that determine the rights of the process to manipulate this link. These rights included the right to reuse the link (single-use links would self-destruct on use), the right to forward the link (non-forwardable links could be received from a message, but they could not be sent onward -- this bit could be turned off as the link was put in the message), and the right to duplicate the link (for non-duplicatable, the attempt to copy the link or include it in a message destroys the original).
Recall that the link array for a process is a kernel data structure. The process cannot directly manipulate links, and it has no way of inspecting their representation. All it can do is refer to the links it wishes to manipulate by link number, just the way UNIX processes refer to open files by file number, an index into the kernel's array of that process's open files.
So what is a Demos mailbox? There are two practical implementations. One is a list of messages awaiting receipt:
Demos Mailbox List of messages
_____________ _________ _________
|____________o--->|________o--->|____X____|
| message | | message |
|_________| |_________|
The problem with the above implementation is that it requires the
kernel to maintain a pool of arbitrarily sized buffers to hold the
messages, and in Demos, there was no limit on the size of a message!
The advantage of the above approach is that it allows the process
that sent the message to continue asynchronously while the message
awaits delivery.
The second practical implementation uses a list of processes that have tried to send messages that have not yet been delivered:
Demos Mailbox List processes
_____________ _________ _________
|____________o--->|________o--->|____X____|
| process | | process |
|_________| |_________|
Here, when a process tries to send a message to a ready or running receiver,
it blocks and hangs itself
on the mailbox of the process to which the message will be delivered.
When that process attempts to receive the message, the data will be
copied directly from the sender to the receiver, without ever being packaged
in a buffer outside the sender's or receiver's data structures.
When a process tries to send a message to a receiver that is blocked awaiting a message in the indicated box, the data is copied into the receiver's data structures and the sender unblocks the receiver. This is the scheme that was used in Demos! It has the advantage that the kernel does not need to maintain any buffer pool.
From the above, we can infer the following kernel representation for each process:
One Demos Process
Every process has a process ID
_________
ID |_________|
All processes get linked into lists, either the
ready list or lists of processes blocked attempting
message delivery:
_________
next |_________| pointer to next process in list
We need to describe the process's resources:
_________
data |_________| pointer to data segment
dsize|_________| size of data segment
links|_________| pointer to link table
lsize|_________| size of link table
boxes|_________| pointer to mailbox table
bsize|_________| size of mailbox table
state|_________| running, blocked sending, blocked receiving, stopped
If the process is blocked trying to send a message,
or if it is blocked trying to receive a message,
we need to describe where to get or put the message
when sender and receiver finally meet:
_________
buff |_________| address of buffer in data segment
blen |_________| length of buffer in data segment
mlink|_________| index of link included in message
rlink|_________| index of return link of message
Of course, there must be a ready-list somewhere in the Demos kernel
in order to allow scheduling of ready processes, and there must be
a current-process pointer to allow the system to find the description
of the current process!
Exercise: The above data structure description suggests an array of mailboxes per process. This is a bad idea, in part because many processes, such as the file manager, will need to reserve one box per file in the file system. Box numbers are likely to be huge integers. This leads to an alternative idea. All processes blocked attempting to deliver messages to a particular process are linked into a single queue. When a process attempts to receive a message in boxe i (or in a set of boxes, i, j, k), it searches this list for anyone waiting to deliver to box i (or j or k). When a process tries to send a message to box i of a process that is blocked awaiting a message, it checks to see if i is in the set of box numbers that process is blocked awaiting messages in. What distinct issues must you deal with, and how would you change the data structures given above to accomodate this!
How does the Demos process manager, a server, interact with the kernel? The answer is fairly straightforward, once one detail is made clear. Obviously, the kernel runs with the memory protection mechanism turned off! It must be able to access any part of memory in order to copy messages from the address space of one process to another!
What is less obvious is that the process manager must also have access to all of memory. The process manager is just a normal Demos process, but it does the heap management! It is in charge of allocating a data segment for each process, it implements the peek and poke operations on the data segments, and it creates the process description data structure when a new process is created. Therefore, data, the pointer to the data segment for the process manager is zero, and dsize, the size of the process manager's data segment, is the maximum allowed physical address.
The process manager still runs as a normal user process, but it is able to inspect and modify all of memory, and specifically, it uses these privileges to allocate memory for process descriptions, initialize that memory and link it into the ready list whenever a client requests that a process be changed from the stopped state to the running state.
The process manager will maintain a table (or list) of active processes, most likely a hash table that relates process ID to process description record. When it creates a link used as a handle for manipulating a process, it uses the process ID as the mailbox number. Therefore, although user processes never see actual process IDs, they have a copy of the ID of every process they control, where this copy is hidden in the link that the process has as a handle.
This trick cleverly allows the kernel's mechanism for protecting the integrety of links to be used to prevent a process from requesting management services for any process it is not authorized to manage.