Domain states and kinds of invocations

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.

FORK

Leaves invoking domain running.

CALL

Leaves invoking domain waiting and includes in the message a resume key to invoker.

RETURN

Leaves invoking domain available. Dequeues domains on the queue of the domain which performed the RETURN.

• which key held by the invoker is to be invoked;
• which data and keys are to be included in the message;
• which of the three kinds of invocation is to be performed;
• for CALLs and RETURNs, how to receive the message for the invocation that will next cause the domain to run.

• how the components of the message are to be accepted;
• where to start execution.

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:

• Before CALLing: X is running and holds a resume key to Y; Y is waiting.
• After CALLing: Y is running and holds a resume key to X; X is waiting.

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:

• Abstraction (information hiding)
• Instantiation
• Protection (calling some program with different authority)
• Exclusion and queuing
• Multi-programming

NEXT