Three special objects

Domains, segments, and meters are three special primitive objects. By their nature these objects must be implemented in the microkernel. For each of these special objects there are infrequent exceptional states, encountered by the microkernel, whose disposition must be determined by code outside the microkernel. (In KeyKOS, by design, the policies to be implemented in these exceptional situations are left to domain code, as in [9].) In such cases the key in the object’s keeper slot is invoked with a message that includes information about the nature of the state, and the service key to the object. The key in the keeper slot is normally a start key to a domain obeying a program called a keeper. The keeper may use the service key to return the object to a state where the kernel’s rules for the special object are suitable again.

A keeper invocation is one which is triggered by some exceptional state of a domain, a segment, or a meter. This invocation is in the form of a CALL invocation, and is designed such that, after the exceptional states which triggered the event are rectified, control may be transferred to the domain whose action caused the circumstance (by a RETURN invocation of the resume key) without it being aware of the interruption of its execution.

In KeyKOS, the use of keeper invocations to summon aid is motivated by the intent to remove policy concerning the handling of such events from the microkernel. Fixed policies of this kind tend (in conventional systems) to inhibit the evolution of the system. By moving such policy to programs implemented in domain code, an attempt is made to provide an avenue for future evolution and growth of the system, as well as a mechanism to allow multiple policies to be simultaneously supported in a single system.

Domain service

The key from the domain’s keeper slot is called when the domain encounters difficulty in executing instructions. Program interrupts (beyond address translation faults) and Supervisor Calls (SVCs) cause the domain’s keeper to be called. The domain keeper may thus emulate environments provided by other operating systems, or provide debugging services.

The domain service key designates a domain. It provides authority to retrieve and replace parts of the state of the domain including the keys in the general and special slots. The domain service key provides complete access to the state of the computation within the domain, and authority to intervene therein.

The code that interprets the domain service key invocation is in the microkernel, in contrast to the code which interprets the domain start key invocation, which is the domain code. The domain code (obeyed by the domain) has no control over and is not involved in interpreting these domain service key invocations. The domain service key is used to initialize a domain and to intervene if the domain’s program should not behave as expected. Many domains hold their own domain service key. One order on a domain service key yields a start key to that domain. This order also takes a one byte value, the data byte. The start key includes this byte, which is delivered along with messages delivered via that start key.

Segment service

A segment has some specific size which is a power of sixteen. A segment is either a page or is compound. A compound segment comprises sixteen equal-size portions. To a compound segment there are both a segment key and a segment service key. Page keys and segment keys are memory keys (While a page is a segment, a page key is not a segment key. A page key is, however, a memory key). The memory key to a compound segment is a node key, fetch key, sense key (q.v.) or segment key designating the node that is the root of the segment.

The sixteen portions of a compound segment S are each represented by the key from one of sixteen component slots in S accessible via the segment service key to S. To the segment key holder the segment appears as the seamless concatenation of the sixteen portions. A fetch or store reference to a portion of S via the segment key to S has the effect of a fetch or store reference via the key from the corresponding component slot. These keys are typically memory keys to smaller segments. A fetch or store reference to a portion of a segment whose component slot key is not a memory key is invalid . Store references via read-only memory keys are also invalid. Invalid fetch or store references to segments cause invocations of the key from the segment’s keeper slot or lacking that, the referencing domain’s keeper slot. The referencing domain is left in the state just before the reference was made. The invocation message includes the address within the segment to which the reference occurred, a segment service key, and a resume key to the referencing domain.

If M is a memory key to a segment, then one may construct, given M, the following three types of segments:

A memory key to a page or segment may be used to define the address segment of a domain or it may be used to define a portion of another segment. The same memory key may be used in several contexts at once.

Meter service

Meters account for certain system resources including CPU time. To a meter there is a meter key and a meter service key. For a domain to run, its meter slot must hold a meter key to a valid superior meter.

Within a meter appear -

For a meter to be valid, its superior meter key slot must hold a meter key to a valid higher meter. There is a primitive meter which is always valid. There must be a chain of meters leading to the primitive meter. As a domain runs, the chain of meters rooted in the domain’s meter slot all record the resources used. The meter service key supports fetching from and storing to the various slots of the meter while the meter key provides (but limits) the resources the holder can consume. The meter key holder can build inferior meters.

A meter’s keeper slot key is called when a resource counter in the meter reaches zero. The message associated with the invocation includes a meter service key which may be used to replenish the counter if that is the plan. The message also includes a resume key to the waiting domain whose execution exhausted the meter. This key may be used to restart the waiting domain when appropriate. The meter keeper is in a position to perform scheduling over all the domains served by that meter, directly or indirectly.

Role of nodes in the special objects

Nodes are of very general use. They play much the same role of control blocks of some programming systems. Nodes assume a fundamental role in the definition of most other objects. The special objects (domains, segments, and meters) are actually composed of nodes. Their behavior is determined by code in the microkernel. It might be said that these extra behaviors of the node are merely alternate personalities of the node, inherent in the node itself. Segment keys, domain service keys, and meter keys designate nodes while limiting their holders to the corresponding special function. A segment service key or meter service key is merely a node key to the underlying node. We call them all service keys here merely to emphasize their parallel role. Similarly, the meter service key is the node key to the underlying node.

To build a segment or meter it suffices merely to place the appropriate keys in a new node, and request the segment key or meter key by an order on the node key. To limit the number of programs that know how domains are built from nodes, getting a domain service key takes a special key: the domain tool key q.v.. The domain service key is used to install the parts of a domain. Typically the domain service key is obtained from a domain creator, which is the only type of object holding the domain tool key.

The effects of invoking primitive keys are immediate. Invoking a node key to change the definition of a segment has immediate effects on all address spaces in which that segment occurs.

The reader may have noticed by now that some keys have other uses than invocation. In particular, memory keys are used in the address slots of domains and meter keys are used in the meter slots of domains.