Use of the Term “Process”

Some readers may be accustomed to using the word “process” to mean about what we mean by “domain”. {See, for example, Dennis and VanHorn, Programming Semantics for Multiprogrammed Computations, (_CACM) v.9, pp. 143-155 (March 1966).} In their view, a process becomes suspended waiting for a call to occur {domain becomes available}. When a call occurs, the process is restarted {domain becomes running}. When a process does a call, it becomes suspended until the call returns.

In Gnosis processes are indistinguishable. A domain either has a process {is running} or has no process {is not running}. When we say {(p1,gates)} that a process jumps from domain A to domain B, we mean that domain A leaves the running state, domain B enters the running state, and it is likely that the CPU {just freed by A} will be assigned to B immediately and efficiently. Thus the association between the processor and the process tends to last longer than the association of a domain with either a process or a processor.

Consider a mail metaphor for Gnosis. A message consists of some data (the order code and byte string) and some keys.

Keys are preaddressed envelopes to other objects. A start key is an infinite supply of identical envelopes in which messages may be sent. A resume key is an envelope that can be used just once.

A key owner cannot read the address on the envelope (only the postman can). Only the message is delivered to the addressee (not the containing envelope).

Jumps each specify a message and an envelope. A call specifies that a self-addressed envelope be included in the message and that no further processing be done until a reply (another message) is received in the provided envelope. A fork specifies that a message be sent without a return envelope (return key) being generated. Processing continues in this case. A return sends a message and awaits a message in a start style envelope.

The busy state {(p1,dsterm)} of a domain effectively provides an interlock mechanism that prevents two processes from being in a domain at the same time. For short public services, a start key can be widely distributed to a domain that designates the program and capabilities necessary to provide that service. While the program is running, the domain is busy. When the program is done it returns. If another program has called for the same service during this time, that service can now begin. This is much like what IBM calls “serially reusable”. It is especially useful for services that manipulate public data such as enqueuers and dequeuers. See (p3,bhmonitor) about using these ideas to implement Brinch Hansen’s monitors.

If the service is subject to delay and it is important to return to the callers on other than a first-in, first-out basis then a reentrant service is required. This may be provided by making a serially reusable (_front end) which creates a separate domain for the use of each process. In this manner there may be several domains each supporting a different process executing the same program. When the service is done the service program calls the space bank to dispose of all working space including its own domain. The return key provided to the space bank is to the original caller. The space bank returns to the return key.

The fact that the domain is left in the busy state by the CALL command allows these serially reusable programs to call other programs without allowing someone else in. The ability of the return key to get back into a busy domain completes this mechanism.

When a resume key is used, other return keys to that domain become empty keys. This fact relieves the programmer from anticipating the consequences of someone using the same resume key twice.

Most programming languages allow procedures to have local variables whose values persist between calls. In Algol 60 they are called “own”, in PL/I they are called static, in Fortran they are any variables that are not in common and are not parameters. (N.B. This usage is a violation of the FORTRAN 77 standard.) A gate may be made to have this type of storage merely by installing page nodes in the memory tree in the gate node. The above languages fail to provide more than one set of such variables per procedure. Imagine that a procedure has the job of making a terminal with case shift logic look to programs like a standard ASCII terminal. The procedure must remember the case shift between calls because the caller is not even aware of the concept of case shift. Simula 67 and Euclid provide for several sets of “own” type variables for one procedure with a different entry for each set. This can be accomplished in Gnosis by building different gate nodes with different memory trees with the same code sub-trees but different page keys.

Another less elegant and more efficient method is to use the same gate node but make different start keys with different data-byte values to distinguish the different callers. This scheme has the advantage that the different callers may require less than a node and a page each, but the disadvantage that a bug in the procedure encountered by one caller may ruin the service given to another caller.

Some applications require many terminals connected to the same or different programs that share data.

Systems such as VM/370 allow attachment of many terminals to one virtual machine. This approach suffers when the task that is working for terminal X needs the CPU for a while, during which time terminal Y needs a short service. The scheduler in the real CP cannot distinguish the two kinds of processing going on in that virtual machine. CP can and does give the virtual machine high priority when an activation character arrives at the virtual machine from terminal Y. The virtual machine also receives an interrupt which can be used to interrupt X’s service while Y’s service is done. What CP cannot know is when the short service is done so that the virtual machine can be rescheduled at the lower priority appropriate to X’s task. Another objection to this scheme is that the virtual machine must contain multiprogramming logic that duplicates much of the logic of the control program of the real machine.

Some operating systems might do this by assigning a job per terminal. This usually implies that any sharing of data is done only on disk. Multics can share in core but cannot share pointers, an almost indispensable programming technique.

Still another method assigns a virtual machine {or job} to each terminal and yet another machine to handling the shared data, with provisions for communicating between the central machine and subsidiary machines. It will still be true that some tasks on the central machine will be executed serially, unless that central machine has a complex sub-scheduler in it.

In Gnosis we provide a process for each terminal. Different parts of the virtual memory of the process can be: private, shared among some sub community, or shared among all terminals associated with the application. Any degree of core sharing can be accommodated between processes that are viewed as distinct by the scheduler. Now process Y can have its short CPU service without being confused with process X.

In capability based operating systems, data and capabilities have similar roles. They have much in common but the distinction between them is vital. In common is that the user allocates storage for both in space that he is responsible for.

There are two ways that capability based systems have used to distinguish between data and capabilities:

In some systems the memory systems have extra bits in each “word” that discriminate between data and capabilities. We call this idea “tagged memory” here.

In other systems, such as Gnosis, data is kept in pages which hold no capabilities, and the capabilities are kept in special “segregated memory”. The program’s capabilities to this segregated memory indicates that capabilities are stored there.

Which is best?
The most immediate distinction that I know of is the nature of the effort required to allocate storage. Many records or structures will include capabilities. To build values of these types we must allocate memory.
With a tagged architecture one may allocate data and capabilities with the same flexibility as one mixes fixed and floating data in structures.

With segregated storage, as in Gnosis, one must adopt a mixed strategy:

For objects with little data one usually puts everything in capability space and codes the data part in data keys

For objects with enough data to justify a page, pages are used and keys to those pages are kept with the other capabilities that constitute the object.

Both of these schemes work in the normal case where the object is really wrapped up in a domain.

An important kind of record is the activation record or stack frame. In Gnosis domains serve as activation records.

Another distinction is whether the user knows the real size of the capability.
With the tagged architecture the size of the capability must be chosen very early. This is a painful choice. There is dissension as to whether 64 bits is enough.

With segregated storage this is not an issue. Only the kernel knows how big a capability is.

A problem with the tagged architecture is that it changes the nature of “storage” in a rather profound way.
Storage is itself an abstract data type implemented by rather sophisticated algorithms in modern machines and software systems. There are many parts of the hardware used to support this abstraction. The cache must be modified. Note that virtual memory implies swapping. This swapping is done on I/O devices that must now also hold the tags. The channels must be modified, perhaps, to copy the tags. Most likely the system is backed up on magnetic tape and so the format of data on mag tape must be changed, and perhaps the tape hardware. There are now two modes of tape format -- with and without tags.

Yet another problem is that commands such as MVC and MVCL are built around the abstraction of storage -- they copy it.

What should the hardware do when it encounters an MVC that tries to copy part of a capability. There is no simple answer to this.

Compilers that support data abstraction that exist now presumably have assumed that a value of one of these types can be copied by the machine commands in the manual, such as MVCL.

Should CLC and CLCL be defined to work on capabilities? The ability to compare capabilities should itself be a capability. What condition code does a CLCL return if it encounters a capability? Every answer that I can think of involves modification to the definition and microcode of each of these general storage oriented commands.

In word-oriented machines, there are likely macros, in programmer’s heads and perhaps in libraries, that copy storage. These routines will try to load capabilities into data registers. This cannot be allowed. {Unless we have tagged registers, but then the definition of the add command becomes more complex.} But how do you copy a structure which includes capabilities? Does a copy loop first test each word to see if it is a capability and use different commands depending on the result?

My conclusion here is that tagged architecture seems attractive because it gets a conceptual free ride on the storage abstraction. But when we examine the details, it burdens that abstraction -- witness the mess it makes of MVCL and copy loops.

Analogues to some of these problems occur with segregated storage, but at a much higher level where the complexity can be better handled.

I conclude that:

Tagged architectures pervade the hardware architecture.

The size of the capability cannot be hidden from the user.

The only advantage of tagged architecture is that allocation of storage for a record or structure that includes capabilities is simpler.

C.A.R. Hoare’s description of Brinch Hansen’s monitors is naturally and easily implemented with domains. A domain is directly used to implement a monitor.
Monitors: An Operating System Structuring Concept -- C.A.R. Hoare, Communications of the ACM Oct 1974, Vol 17, # 10, pp549-557

The busy bit ensures that only one process is in the domain. The various procedures that are included in a monitor are provided by different order codes or different databytes in the start key.

To provide the wait-function, one must put the return key in a queue and return to DK(0). To do the function of signal one retrieves the return key and finishes the service and then FORKS to that return key.

Waiting and signaling:

The function of the wait is performed by associating a queue of activation records for each declared condition. Here an activation record is composed of an return key and an instruction address. When a wait on a condition is executed the current PSW and the current instruction address is placed in the queue for that condition and a jump return to DK(0) is done.

When a signal for a condition is done an activation record from the queue for that condition is placed on another queue global to the domain. {Signals cannot restart the old process until the monitor is exited; else there would be two processes in the monitor.}

It is arranged that all return jumps {including the one mentioned above} return (_fork) to their resume keys and then restart a job on the global activation queue if any and jump return to DK(0) if there are none. {This can be optimized.}.

{arcane}The operating system on the PDP-10 provides for the reader of a file to continue to read an old version of a file while another program is creating a new version of the “same” file. See (p3,multi-version) about similar tricks in Gnosis.