The Nucleus of a Multiprogramming System

Per Brinch Hansen, The nucleus of a multiprogramming system.¹ ;pretty much the paper the started microkernels … but it’s not a microkernel itself

Abstract:

This paper describes the philosophy and structure of a multiprogramming system that can be extended with a hierarchy of operating systems to suit diverse requirements of program scheduling and resource allocation. The system nucleus simulates an environment in which program execution and input/output are handled uniformly as parallel, cooperating processes. A fundamental set of primitives allows the dynamic creationg and control ofa hierarchy of processes as well as the communication among them.

The purpose of the system nucleus is to implement these fundamental concepts: simulation of processes; communi- cation among processes; creation, control, and removal of processes.

§§ “precise meaning” to the process concept

• distinction between internal (~=program execution) and external processes (I/O).

§§ synchronization primitives and IPC

• semaphore alone does suffice (safety and efficiency)
• message buffering within system nucleus as basic means of IPC.
• system nucleus adminsters a common pool of message buffers and message queue for each process.
• IPC primitives:

  // note Fortran, in/out parameters; you have to guess :)
  send_message(receiver, message, buffer), // block/non-block (queued buffers)
  wait_message(sender, message, buffer),   // blocks
  send_answer(result, answer, buffer),     // non-block
  wait_answer(result, answer, buffer),     // blocks
  

send_message copies a message into the first available buffer within the pool and delivers it in the queue of a named receiver. The receiver is activated if it is waiting for a message. The sender continues after being informed of the identity of the message buffer.

wait_message delays the requesting process until a message arrives in its queue. When the process is allowed to proceed, it is supplied with the name of the sender, the contents of the message, and the identity of the message buffer. The buffer is removed from the queue and made ready to transmit an answer.

send_answer copies an answer into a buffer in which a message has been received and delivers it in the queue of the original sender. The sender of the message is activated if it is waiting for the answer. The answering process continues immediately

wait_answer delays the requesting process until an answer arrives in a given buffer. On arrival, the answer is copied into the process and the buffer is returned to the pool. The result specifies whether the answer is a response from another process or a dummy answer generated by the system nucleus in response to a message addressed to a nonexisting process.

• regard the selection of a buffer as the creation of an identification of a conversation

• the buffer (communication channel) is protected and exclusive to the pair.

• queued messages undisturbed on the removal of their sender processes. Nucleus returns buffers to pool when answered.

• (reverse: ) on removal of a process, systems check for unanswered messages sent to the process and return dummy answers to the sender.

• it’s always the client who pays for the resource (i.e. buffer) during IPC. server only needs to reply (reusing sender buffer) instead of allocating one of its own

§§ dynamic creation, control and removal of processes

difference to actual microkernel (I mean, l4re)?

• parent has full control over its (direct?) children (the mandated hierarchy doesn’t seem to be micro-kernel-ish)
• every process can talk to each other (same namespace?)
• address space isolation? paging?
• async IPC (vs. l4)
• not yet the “capability” concept
• global buffer pool, instead of UTCB