3.0 SYSTEM OVERVIEW

The following sections describe the system from a fairly general point of view. The first section is concerned with the overall architecture; the second with the structure of the user program environment.

3.1 Basic Architecture

The system is organized as a series of concentric logical rings. Each ring provides a certain set of functions and has a set of interfaces to the next ring. The various rings can be loosely described as:

3.1.1 System Monitor

Handles coordination and scheduling of all system resources, such as the CPU, core memory, RADs, discs and remote terminals. Its interface consists of a set of system calls for manipulating entities called keys, which allow access to the various entities in the system. Keys will be extensively discussed in the later sections.

3.1.2 System Services

A collection of independent routines which perform basic service functions such as file management or utility services. In general, these services correspond to many of the functions performed-by the 940 Executive and Monitor. The unique feature is that all of these services can be written, debugged and operated entirely in user mode. In particular, none of the services provided by this level are absolutely necessary to do satisfactory programming. They merely provide a flexible means of packaging more sophisticated functions for general use. The interface mechanism for packaging these services is the gate, a concept which will be discussed later.

3.1.3 Language Processors

These processors serve generally the same purposes here as on the 940: a higher level language basis for doing further programming, debugging, or editing functions. Users at this level are generally programmers engaged in development work. System service routines are automatically invoked by language statements.

3.1.4 Program Products

User level software requiring little or no programming ability to operate effectively.

It should be mentioned that this specification is not at all concerned with the contents of the outer two rings; these rings constitute our principal products. The concern for a system design is to allow the greatest possible latitude to those designing and implementing these products.

This specification is also not concerned with the exact contents of the system service ring. This specification is concerned, however, with the forms of program interaction provided by these services. Essentially, this document specifies the concepts which are available and the limits of what can be done with them.

3.2 Basic Concepts

The facilities provided by the system monitor are those necessary to define and manipulate a number of basic structures. They are introduced and briefly defined here before proceeding to a discussion of the user program environment.

3.2.1 Key

A key is the protected name of a system entity whose possession by a program implies the authorization to access that entity. Keys are protected in the sense that they cannot be directly modified by a program even though they appear within its memory; they can only be manipulated through a well-defined set of system calls. A program has keys to each of its memory pages; conversely, a program may only access memory to which it has a key.

3.2.2 Gate

A gate is the entry point to an independent program unit completely external to those programs which may call it. The program associated with a gate occupies no space in the caller’s virtual memory. In general, the user is permitted no access of any kind to the gate program. Since a gate is completely secure from meddling, it may have privilege and capabilities that could not be given to the user; gates, if suitably programmed, can be trusted not to misuse their capabilities.

3.2.3 Process

A process corresponds to the usual system notion of an independently scheduled entity. User processes can create other processes and delete them, but the rigid hierarchical relationships used on the 940 are not maintained by the system. Processes do, however, bear close relationships to gates, as will be described later.

3.2.4 Account

An account is similar to a bank account in the sense that it is used as a source of funds to pay for the use of system resources. In particular, each running process must have an account attached to it; as a program runs charges are made to the account. If it runs out of funds, the program is stopped by the system. Accounts are also used for the direct control of processes. A system call may be used to stop the execution of all processes attached to a given account for debugging purposes, or whatever.

3.2.5 Event

An event is a system entity used to coordinate the execution of several processes. A process may cause an event to “happen” or request that it be blocked until another process makes an event “happen”.

3.3 Structure of the User Machine

We turn now to consider, from the assembly language programmer’s viewpoint, the features of the user’s machine. To start, we shall describe how certain basic functions are to be performed.

3.3.1 Memory Management

From the viewpoint of the low-level user and the monitor, all information known and immediately accessible is organized into the natural page size for the machine (2048 bytes for the Sigma 7). Each such page is identified by a key which is a word containing the home disc address of the page or a reference to a monitor-kept table containing the disc address. Keys are kept by the user to simultaneously enable him to specify which page he is referring to and to prove he has access to it.

Since keys are “protected” they may only be kept in privileged pages called key pages. A key page may appear in a user’s address space (and must in order to directly address it), but the user never has write access to it. Keys are required in order to do almost anything in the system so most programs will have at least one key page in their address space. System calls are used to move keys from page to page, so that the user may control the distribution of his keys.

One key page called the “space page” is naturally associated with every process and is used to describe the layout of its virtual memory. The first 256 words of the space page have a one to one correspondence with the available 256 slots for pages in the Sigma 7-virtual memory. The programmer arranges his memory by placing page keys in the appropriate slots in the space page. This in general requires that the space page itself be in the virtual memory of the program.

This facility is roughly the same as the relabeling facility available on the 940 with the exceptions that words instead of six bit bytes are used as page identifiers and that any page in the system to which a user has access may be referenced this way.

3.3.2 Input-Output and File Management

The key and virtual memory manipulation facilities provide a complete, but low-level, set of tools for handling all I/O functions for files. One merely places the desired pages in memory when and where needed. The system handles all the necessary decisions and activities relating to retrieving the pages from the disc and bringing them into memory and the RAD.

Note, in particular, that the structure of a file has not been specified. For this reason, a user is free to set up his file structure in any convenient way. In this context, key pages play the role of index blocks on the 940. Similarly, key pages also play the role of file directories, so that the user can maintain his own directory structure.

It is fairly clear, however, that much is to be gained from establishing certain standard ways of doing common I/O and file structure tasks. Standard file structures are needed to achieve reasonable economy in the programming of language processors and other programs which routinely do file manipulation. Certainly some machinery is needed to insulate the average user from all the flexibility and to insure normal interchangeability.

3.3.3 Packaging of System Services

A set of standard subroutines could certainly be written to perform many of the functions of a file management system. This might be a convenient way to solve some sorts of problems. It does mean, however, that each user has his own private copy of the routine and that it is completely accessible to him.

The situation can be somewhat more improved by making the package a collection of shared pages, but this requires that all users of the program agree on the virtual address of the program during execution. This works acceptably well on the 940, but the shared program cannot be protected from read access or copying. There is also no way to give such a shared program special privileges unless ordinary users are denied any access to them. (It should be noted that any program can be automatically relocatable and shared by dedicating two index registers to be used as base registers and making all internal references indexed. This technique will probably not find wide use, however.)

A more elaborate solution to the packaging problem is provided by gates. As described above, a gate is the entry point to a program completely external to the caller. Access to the gate is, as usual, represented by a gate key. Invocation of the gate program is caused by the monitor detecting a branching reference to a gate key. (How this will be encoded in the Sigma 7 instruction set has not been decided yet.) The monitor then proceeds to establish the gate program as a working process. The user may pass the gate program various parameters, including keys. In particular, a key to the program’s space page may be passed, which allows the gate program to perform any desired manipulation of the caller’s virtual memory. For example, the gate may perform multiple buffering for look ahead purposes, I/O list-directed input or output operations, or any other service function.

A further facility allows a user to specify the interpretation of the CAL instructions. A sixty-four word region of the space page is dedicated to receiving keys; one type of key causes control to be passed to a user routine in the current address space; a gate key causes the gate program to be executed when the CAL is called.

Gates provide a mechanism for creation of processes also. In general, a gate may be used in three ways: a program may jump through a gate creating a return gate to the calling program, it may jump through the gate with no provision for returning, or it may fork off a new process which begins execution of the gate program while the caller continues. As a further generalization, every process, when temporarily suspended, looks like a gate to the system.

Gates provide a very attractive solution to many problems:

  1. Since the gate key is the only handle the user has on the gate program, he never has direct access to the body of the gate, either read or write.
  2. Since the caller has no control over the actions of the gate program once he has transferred control to it, the gate may possess privileged capabilities, i.e., keys to privileged data pages. It can be counted or not to misuse them as the program was coded by a responsible Tymshare programmer.
  3. Since the gate program runs in its own address space it may be shared by multiple users without concern about the interference with their address space.
  4. The gate is really only an entry point; hence the caller cannot trick the gate program into performing a privileged function by entering at an unexpected location.
  5. A gate is typically destroyed when it is used, and restored when the gate program returns to the caller. Thus, the gate program cannot be tricked by using an old entry point unexpectedly.
  6. Gates can be used equally well for system calls or private functions. Thus a programmer may substitute his own gate routines to perform functions normally provided by the system.

3.3.4 Terminal Input-Output Functions

Terminal I/O facilities are provided by a special class of system gates loosely called the Terminal Demon. (A demon is a semiautonomous process charged with performing a specific function with only minimal interface with the rest of the system. Other demons will appear in later sections.) The Terminal Demon handles the interface with Tymnet allowing programs to perform the usual I/O functions with terminals.

Many of these functions are straightforward, but some of them, such as blocking for input and output and escape, bear more discussion. The essential element in handling these functions is the Event Demon, whose duty is to assist the scheduler in deciding when to run processes whose activation depends upon asynchronous events such as the arrival of a break character.

When a process wishes to block upon the completion of some event, it merely calls the Event Demon with a key to the indicated event. When another process (e.g., the Terminal Demon) wishes to notify the blocked process that its event has occurred, it calls the Event Demon with a key to the “happened” event. The Event Demon, which has a gate key to each of the blocked processes, merely forks off the blocked process and returns to the caller.

The workings of the Terminal Demon now becomes fairly simple. If a program requests input or has generated a great deal of output and must be blocked for a while, the Terminal Demon requests an event key to be created and calls the Event Demon to be blocked. When conditions are right, the Terminal Demon again calls the Event demon to “cause” the unblocking event. The process is restored to execution and continues on its way.

Escape is handled in a somewhat unique manner. To handle escape in the manner of the 940 requires a considerable amount of machinery within the system itself for controlling processes. The approach taken here is somewhat simpler for the system and provides more flexibility.

A simple mechanism added to the Terminal Demon will allow a very general escape facility. Specifically, two processes can be made to time-multiplex the same input channel. Each process may request the channel be assigned to it and may block for lack of input. Externally, the user may also control the destination of the input characters. In particular, escape is a character whose function it is to chance the switch on the input channel to activate the other process. The other process, if it has been given sufficient privileges, can stop the first process, examine it as it is running or whatever.

To some degree handling escape is a little more involved than it is on the 940; however, standard gates will exist as library routines for default situations.

3.3.5 Control Functions and Accounting

The structure described so far for creating and controlling processes is intentionally very flexible. Note in particular that a running process has no handle or name that can be used by another process; coordination may occur only through events and shared read-write pages. Also note that there is no rigid father-son hierarchical relationship between processes as on the 940. When a process is created, it is responsible only to its controller. We now proceed to consider the problems of control. Control problems are inevitably bound up with accounting since one is generally interested in controlling resource usage which are the same things the system charges for. For this reason control functions and accounting functions use a common vehicle — the account.

As described above, each running process is assigned an account which supplies the “fuel” to keep the process running. At the user’s discretion, he may create subaccounts to limit the amount of computation a process may do. The account may also be used as a switch to stop any processes which are dependent on it. A system call known as “global search” may be made to return a gate key to each process which is running under a given account. Given sufficient authorization in the form of keys, the controlling process can examine the state of the stopped process and eventually restart them by forking.

3.4 Monitor Structure

There is, of course, a great deal to say about the internal design of the monitor system and about the performance of the system in revenue terms. At this juncture, most of what can be said is highly speculative at best.

In the area of design, a great many questions cannot be answered without some actual experimentation and development of data on usage patterns. Consider, for example, the problem of deciding on the use of disc versus RAD for the placement of file data. What kinds of algorithms are best for deciding where a page should be? Perhaps the throughput gained by promoting files to RAD for working storage exceeds the cost of both the extra RAD space desired and the time spent in promoting unused data; perhaps not. We don’t know enough about how systems are used today, let alone how they will be used in a year or two.

For system designers these are pressing problems. The only acceptable answer is to provide a structure where the system answers change when conditions require it. If the costs of system change are high, the first answer is likely to be the last one. During development stages, questions of performance are not particularly important. Software projects are not held up because the system can only support ten users rather than forty. The important requirement is that the system be functionally complete, so that many people are not waiting for the debugging of a single critical feature. Or worse, using a partially debugged feature only to find its specifications changed to eliminate an exceptional problem. Again, the ability of a system to withstand change allows designers to focus on functional performance first and efficiency later, the order which makes most sense.