Domain states and kinds of invocations

In KeyKOS, key invocation plays the traditional role of subroutine call, and the message plays the role of parameters. Don’t imagine a stack, however. The traditional calling mechanism sends the address of data in order to communicate requirements to the subroutine. In KeyKOS, the message commonly includes keys that serve the same purpose — to indicate which objects are to be operated upon by the server.

A domain is always in one of only three states: running, available, and waiting. The picture below is a state diagram for a domain. Arrows are state transitions, not keys.

Running domains will execute instructions, barring page faults, insufficient CPUs, and a few other temporary obstacles. CPUs are multiplexed among the running domains. Available or waiting domains do not execute instructions.

There are two kinds of gate keys: start keys and resume keys. A start key can deliver a message only when the domain it designates is available. If a running domain tries to invoke a start key to a domain that is not available, the running domain is queued along with other domains invoking start keys to the unavailable domain. They will run again when the designated domain becomes available. A resume key is created as a result of the CALL instruction and is described below.

A program invokes a key by executing one of three invocation instructions, thereby selecting one of three ways to invoke the key: FORK, CALL, or RETURN.

A FORK invocation leaves the invoking domain in the running state.

A CALL leaves the invoking domain in the waiting state and automatically generates within the message, as the last key, a resume key to the invoking domain. The invoking domain remains in the waiting state until the resume key is invoked, whereupon the domain returns to the running state. Resume keys exist only to waiting domains, and as a resume key is invoked, all resume keys to the designated domain disappear and are everywhere efficiently replaced by null keys, q.v.

A RETURN invocation leaves the invoking domain in the available state. If there are domains that were queued by the unavailability of the RETURNing domain, one is promptly run.

The state of the domain is determined solely by the type of invocation, and not by the key being invoked.

Summary of gate invocations

Two kinds of gate keys:

Start key
Queues invoker until the designated domain is available.
Resume key
Automatically created by CALL invocation — exists only to waiting domains.
Three ways to invoke a key:

Leaves invoking domain running.
Leaves invoking domain waiting and includes in the message a resume key to invoker.
Leaves invoking domain available. Dequeues domains on the queue of the domain which performed the RETURN.
The invoking domain’s program specifies:

The invoked domain’s program (or initialization) has specified:

Invoking keys that are not gate keys

Keys that are not gate keys are primary keys, and the response to their invocation is performed by the microkernel. When a primary key is CALLed, usually the microkernel immediately returns a message to the invoker (depending on the nature of the invoked key) in such a way that the invoker cannot determine from the behavior of the key that it is not a start key. Most invocations of primary keys are CALLs. In this case the microkernel needs to “return to” the last key parameter. If the invocation is not a CALL and the last key parameter is a resume key then the message produced by the microkernel will be delivered to the domain designated by the resume key. Otherwise the message is lost.

CALLing a start key

This style of invocation, together with a matching RETURN invocation of the resume key, plays the role of the classic subroutine linkage and is the primary method of putting software together in KeyKOS. (Domains may share read-write storage for communication, but seldom do.)

CALLing a start key provides access to a serially reusable resource implemented by a domain’s program. Thus the microkernel need not allocate stack frames or cope with storage exhaustion. Most domains have state between invocations. This state is relevant to some context. Other contexts may have their own domains obeying the same program but with another state. The domain thus embodies the Smalltalk-style object. Domains obeying the same program implement objects of the same type. Such objects differ only in their state, not in their transition rules. However, KeyKOS objects exist at the system level, not the language level, and are much larger than Smalltalk objects (which average about 50 bytes).

The queuing of invokers of a start key to an unavailable domain provides a convenient and efficient queuing mechanism for the domain representing a serially reusable resource. Some services, such as a compiler, have no state between invocations and should be reentrant. In such cases the start key leads to a domain that creates another domain that obeys the compiler for one compilation and then destroys itself. Several compilations may thus proceed at once.

Co-routines — or CALLing a resume key

If domain X CALLs a resume key to domain Y the situations of the two domains are thereby reversed:

This action constitutes a co-routine linkage and has the traditional attributes of co-routines. This is the method typically used by a domain to deliver a sequence of values to another domain, especially when the values are produced or consumed as they are transmitted.

The co-routine relationship is frequently established as follows: X wishes to deliver a sequence of values to Y to whom X holds a start key. X CALLs Y’s start key sending an order in the parameter word foretelling a sequence of values. Y now holds a resume key to X and CALLs it for the first value of the sequence. X now holds a resume key to Y and passes the first value by CALLing the resume key. (Note that the unavailability of Y prevents other users of Y from interfering with Y’s state until Y is finished receiving the entire value sequence.)

This proceeds until X or Y indicates that it wishes to terminate the relationship, whereupon Y RETURNs to X’s resume key, making Y available for new transactions.

Functions of the domain

The following functional areas are frequently provided separately in other systems but are bundled in the KeyKOS domain:

I do not claim that this is a superior packaging of functions, except in the context of other KeyKOS design decisions.