4.0 BASIC CONCEPTS

This section is devoted to a fairly detailed discussion of the mechanics of keys, gates, processes and accounts.

4.1 Keys

4.1.1 General

Briefly, a key is a word serving as the protected name of a system entity. Its possession provides the authorization to access that entity. The entities referenced by keys are usually memory pages, gates, events, or accounts. Keys are protected in the sense that they cannot be directly manipulated by programs; they can only be manipulated through a well defined set of system calls.

Keys provide a simplification to system design of great scope and power because:

  1. The monitor is no longer troubled with the burden of remembering which processes are allowed to do what. A process can access only those things for which it can present a key as a parameter of a system call.
  2. Naming and access control of many different entities are all handled with one mechanism. File directories, file index blocks, subsystems and independent programs are referenced by keys.
  3. As a special case of eliminating naming problems, keys eliminate the concept of input-output operations as explicit monitor facilities. All disc and RAD I/O will be done on a page basis; universal reference to a page of data by a key, regardless of its current physical location, allows the system to worry about the complete management of I/O devices. (As a passing note, unit record I/O, such as printers and tapes, will be handled by ad hoc programs that are-able to specify channel programs for their devices.)
  4. Since keys may be passed individually, by appropriate system calls, from one program or process to another they form a simple but effective mechanism for distributing privileges on a selective basis.

4.1.2 Keys and Key Pages

The monitor’s basic unit of data is a page. Two types of pages are recognized: key pages and data pages. A key page is used to hold up to 512 keys, each one word long. Key pages may be placed into a user’s virtual memory, but only with read access. In fact, whenever a key is used, it must be in a virtual space, as it is identified by its virtual core address.

A basic rule of the system is that keys can only be stored in key pages or in a special system pool called the key table. A user may build hierarchies of key pages at his own discretion; in fact, a user’s files and file directories would form such a structure. From these facts follows the conclusion that any key may be found either in the key table or in some tree structure rooted in the key table.

4.1.3 Key Types

There are many different types of keys serving different purposes. The following is a list of the major types.
4.1.3.1 Master Key
A master key is the most powerful form of reference to a page. If a process has a master key then no other reference to that page exists in the entire system. (There may, however, be duplicate keys to its key page.) The holder of a master key may read, write, or delete the page without concern for multiple usages. The usual contents of a master key will be the disc address of the page. Master keys avoid the overhead of other types below, and may not appear in circular chains.
4.1.3.2 Read and Write Keys
Read and write keys are created from master keys whenever multiple or restricted references to a page are needed. Such keys are indexes to the large key table where the master key is found along with ownership information for accounting purposes. Read keys restrict their possessor to read-only access.
4.1.3.3 Immediate Keys
Immediate keys are provided to allow pure data to be stored in key pages when convenient. Only 28 bits are possible, as four bits are reserved for key codes. Creation of immediate keys must, of course, be done with system calls.
4.1.3.4 Indirect Keys
Indirect keys contain the 17 bit address in the current virtual memory of the key to be used in its place. They are useful through saving a process the inconvenience of moving master keys or changing master keys to write keys, either of which require a write or master key to the key page involved.
4.1.3.5 Strong and Weak Keys
Once a key has been passed to another process the giver has lost all control over it. Once access to a file has been given to several people it is subsequently impossible to deny access to the file to just one of them. Strong and weak keys are key table indexes to read or write keys and come in sets. Deletion of a strong key renders the associated weak keys useless, but does not affect the real object. Hence, the usual practice for solving the above problem would be to pass out weak keys retaining their strong counterparts for control purposes.
4.1.3.6 Gate Key
Gate keys are, of course, the reference mechanisms for gates. Further discussion of them is postponed to the section on gates.
4.1.3.7 Template Keys
Template keys form the basis for a vital automatic mechanism to overcome problems of sharing pages. If a page is truly read-only, sharing between multiple users poses no particular problem. A shared read-write page however, poses severe usage problems. Usually interlock mechanisms must be set up and all users of the page must be aware of the possibility of other users.

Template keys provide an excellent compromise between these two extremes. A template page is initially shared among all users of it. It is not read-only and can be stored into by any program. When this occurs, however, a private copy of the page is created which replaces the shared copy for that user.

This capability provides for several interesting effects: first, subsystems do not have to initialize their context pages upon first entry. They can be initialized once during generation and made template pages. Each time user dependent data is stored, a page private to that user is created. Second, a partially shared file is possible. If two users start with a common file and make small changes to it, the changed parts become private and the unchanged parts remain shared.

4.1.4 Operations on Keys

Since the ability to access a page or a gate depends on having a key, the mechanisms for passing, creating and retaining keys bear some discussion. There are two types of key passing: moving and copying. Moving implies the former holder has no access any longer; copying implies that both holders have access. Copying of master keys is not allowed; if a copy operation is attempted, the master key is turned into a write key and the copy completed.

As mentioned above, keys can only be kept in key pages or in the key table to which programs do not have direct access. In the most general situation, keys are passed between two programs in key pages. But since a key page is passed by passing a key to it, there must be a mechanism to allow the passage of single keys. This is provided through a device called a key stack which each process maintains with a stack pointer double word at locations 16 and 17. Whenever a gate call is made, the contents of the key stack are transferred to the key stack of the gate program.

Each user needs some type of mechanism to serve as the long term holder of his keys. This is essentially the function of the file directory structure. The file system is a group of routines which get and put keys between the file directories and operating programs on the basis of symbolic names. It is perfectly satisfactory, however, to keep keys in raw form within “dump” files and completely bypass the normal file system for certain types of operations.

Certain types of keys can be manufactured at will by a user program. An immediate key can be created and inserted into any blank slot in a key page. Similarly an indirect key can be created by specific request. Possession of a read or write key allows a user to create a strong key and an associated set of weak keys. Gate keys are created by a special process whose description is postponed to a more detailed discussion of gates. Events are created upon demand and their keys may be copied without restriction.

Possession of master and write keys gives the possessor the authority to delete the object of the key, which causes the space occupied by the object to be reclaimed by the system. Any other keys to the same object are unaffected but useless. A user may delete any of his keys at will. Only the deletion of a master key causes immediate reclamation of space, however. As a low-level maintenance procedure, pages with no outstanding keys to them must be identified and deleted by the system. This can be done by scanning all key pages in the system and cross checking then with the key table. It would be a simple matter to do this as part of the disc bit map building procedure.

4.2 Accounting and Control

4.2.1 General

Two trends in the role of accounting information are of importance in system designs. First, many variations in charging and pricing mechanisms are to be expected. The point for system design is not to decide which scheme is most appropriate at any given time, but to provide data collection mechanisms for all feasible charging systems and for the analysis of alternatives. Second, individual user control of computation resources used becomes difficult in complex systems. If users are submitting batch jobs or running several processes simultaneously, the user needs a mechanism for preventing runaway programs from accumulating large charges. Both of these functions are provided for in a mechanism called the account.

4.2.2 Accounts

An account is a logical entity which authorizes a process to consume system resources and records the amounts utilized. An account contains the following items:
1. Current Balance
The amount of money a process may spend before it is trapped; the balance field is continuously decremented as charges accumulate.
2. Usages
A vector of the amounts of a pre-defined set of resources the process has used since it began execution under this account.
3. Links
Keys to superior and inferior accounts in the users’ account hierarchy.
4. Control Field
A set of controls which may be used to suspend the execution of any process dependent on this account for debugging purposes, system checkpoints, or whatever.

4.2.3 Account Types and Usage

In general, an account will be part of a hierarchy of accounts, each level in the hierarchy created to achieve some distribution of control. Each customer contractual entity will have a master account which is under the control of the account supervisor of the company. The balance of funds in this account serves primarily as a credit limit and can be adjusted by the Tymshare Sales organization.

The account supervisor can create subsidiary accounts, transfer funds into them and pass keys to them to other users. If a user wishes to limit the amount of exposure he has to a given program, or for a given time-sharing session, he can create a sub account, transfer funds into it and connect himself to it for charging purposes. If the sub account runs dry, a program trap will occur; at this point, execution may be terminated or more funds may be transferred and execution resumed. A sub account may be deleted, in which case the funds contained in it are transferred back into the higher level account.

Another type of account called an indirect account exists for special situations. Essentially, it is a pointer to a higher account, although it has its own usage and balance information. The special feature is, that the indirect account does not actually have any funds in it; thus, the indicated “balance” in a group of indirect accounts may be larger than that of the master account. However, any changes made to the indirect account are also made to the master so that the master may run dry before any of the indirect accounts. The indirect account is primarily used when it would be undesirable to pre-allocate funds to a group of sub accounts. Indirect account usage causes some extra monitor overhead since all members of an indirect account chain must be kept in core when a process is running.

A detailed discussion of the use of accounts for controlling processes is postponed to the next section.

4.2.4 Rate Structure

In previous operating systems the collection of accounting information was not particularly difficult; periodic records of resource usage’s were written onto a file and processed later by completely external programs which achieved varying degrees of sophistication in coping with accounting details. In particular, problems of rate structure were not part of the system design. All the monitor had to do was record the usage of resources that were being charged for.

This simple approach cannot continue if dollar amounts are to be used for direct control of processes. In this case, the cost of a unit of each resource must be known at the time and place that resource is charged for. This raises the problem of specifying all the pertinent variables about how much each resource costs. In the past, these variables have been four-dimensional:

1. Resource Unit Structure
What resources are chargeable by the system and their standard unit costs. Since the resources charged for may vary between rate structures a standard set will be maintained and zero cost assigned to those not charged for; this will allow analysis of the effects of rate changes. The rate structure currently being used by a process will be found in a protected key in its space page.
2. User Scale Factors
To account for variation in charging rates between users, a marketing-assigned scale factor could be used when making charges against the user. This would provide a simple way of handling educational or volume discounts, or different rate levels for different levels of marketing support.
3. Software Scale Factors
Certain software packages or subsystems may carry discounts or premiums, depending on marketing policy. Again, a scale factor could be used for changing when software package rates vary.
4. Tine Period Scale Factors
The problem of giving customers reduced rates on off hours usage can be handled with a time-dependent scale factor. This, however, becomes quite complex when handling customer loads from multiple time zones on a single system. “Off-hours” no longer corresponds to specific times in a national operation.
A small number of basic rate structures with standard resource costs and these three scale parameters provide a flexible mechanism for setting rates but are not unduly burdensome on the system.

4.2.5 Collection of Accounting Data

Charges are made for individual resources, as they are incurred, to the responsible account. For example, the clock interrupt routine records the amount of CPU time used. A charge is made by adding the appropriate number of resource units to the usage vector entry in the account. The units are multiplied by the charging rate, scale factors and the total subtracted from the current balance. If the account in question is an indirect account, this process is repeated for each member of the indirect chain.

At specified times during the execution of a process, entries are made into the accounting file by calling the accounting demon through a system gate. The accounting demon is the only program that knows the structure of the accounting files, so that this function is kept out of the monitor. Accounting records will generally be made at log-in, log-out, process creation and deletion, transitions through those gates for which accounting records are desired and at periodic intervals to protect against crashes.

4.2.6 Proprietary Software

It is anticipated that Tymshare computers will serve as a medium for the use of software proprietary to one user by another in return for payment. It may be to the advantage of both parties, as well as Tymshare, to allow the system accounting to record the charges and perform the billing and payment functions.

To allow this function, a program will be able to withdraw funds from any account to which it has a key, causing a corresponding entry to be made in the accounting file. Among other advantages, this means that the account balances can be used to control the use of any software that makes use of system accounting, even if the charges are not being made on the basis of Tymshare resource units.

This makes it possible for a software vendor to charge a fixed price for a service routine. When the vendor’s routine is called it merely transfers the fixed fee from the caller’s account and then begins to run under one of the vendor’s own accounts.

4.3 Gates and Processes

4.3.1 Types of Gates

Gates are complex mechanisms which must serve several purposes which are similar in concert but not identical. To see the distinctions consider the following three types of gate usage:
1. Pure Gate
This is the unexecuted state of a sharable program. It has no storage within it that is unique to a particular user. When it begins execution it will either acquire new memory unique to the caller or copy certain of the template keys into user-dependent versions. The pure state is the normal existence for the reference copy of all shared programs. All potential users of the program have a key to the same pure gate.
2. Return Gate
This is the form in which a gate program may contain information unique to a single user. In particular, the gate is unique to the user even though the majority of its pages may be shared by all users. The term return gate is used to indicate that such a gate is a mechanism for returning to the gate program.
3. Re-entrant Gate
This form of gate is used jointly by all of its callers to manage a common resource. It has the restriction that its use must generally be interlocked and that the program must know that it is being used this way. Similar effects can often be achieved by a group of return gates which share a set of read-write pages, but this causes a proliferation of separate return gates. For economic reasons, re-entrant gates are often desirable. It is not completely clear at this time that user mode programs will be able to successfully operate as reentrant gates. Certain monitor routines such as the terminal demon and the event demon are examples of re-entrant gates.

4.3.2 The Space Page

Before proceeding to a detailed discussion of the mechanics of gates, it is necessary to present the concept of the space page. The space page is the control information required by the system and the program itself. This is a key page consisting of the following items:
1. Memory Control
A 256 word array which may hold keys to pages, thus defining an arrangement of virtual memory.
2. Fault Controls
A series of keys which define how the program wishes to interpret CALs, standard processor interrupts, hardware trap conditions, and specially defined system trap conditions. For each of these conditions there are essentially two options, the fault condition can be handled by the program itself through placing an immediate key pointing to an XPSD instruction; or it may specify an external gate to be executed by providing a normal gate key.
3. Privileged Controls
A group of keys which are manipulatable only by the monitor because of their privileged nature. These include several items concerned with accounting. Another special entry is the gate brand — a word designed to prevent multiple gate keys to the same space page from being created. Considerable confusion can be caused by two processes executing with the same context storage.

Recall that both gates and processes have space pages. A gate is, in fact, a latent process. Jumping through a gate can be viewed in either of two ways: as the metamorphosis of a single process or as the suspension of one process and the simultaneous creation of another. Indeed, the suspension of the first process is only an option; “forking” is accomplished by not suspending the calling process. As may be expected, there are a few restrictions on the similarity between gate calls and process creation, but these must be discussed after more details on gates have been presented.

Most processes will run with their space rage in their virtual memory, as the usual memory manipulation techniques require movement of keys in and out of the space page. There is an exception to this, however. If CALs or trap conditions are being used to interface a program with an external gate (which is perhaps acting as a simulator), a write key to the space page of the caller is delivered to the gate as a parameter. The called gate may then perform its desired manipulation on the caller’s memory. Note that the system is assuming that the process which initialized the space page has implicitly authorized the passing of the write key to the gate program, which seems to be reasonable.

Given that a gate is defined by its associated space page, it becomes fairly reasonable to relate the two entities. In particular, there exists a system call which takes a write key to a space page and a few other parameters and produces a gate key. If the indicated space page is already a gate, these gates can be rendered invalid and a new gate created. Thus, the write key to the space page is more powerful than a normal gate key. In particular, a process which holds the write key to the space page of another process can stop it by this operation.

Stopping a process by this mechanism is not usually the cleanest thing to do. In particular, if the process has jumped through another gate, then it is running as if it were a third process; the stopping of the second has merely prevented the third process from restarting the second again. Nothing really disastrous has happened to the system (the orphaned process is either annihilated by the system or allowed to commit suicide gracefully). The recommended approach is to use the account controls which stop cleanly all processes running under a given account. It may happen, however, that a process created by a gate call has begun executing under another account, in which case the creator has no control over it. In this case, termination by write key is all that can be done; in such cases it would be expected that the third process is prepared for the possibility and will do the right thing.

4.3.3 Mechanics of Gates

We can now turn to a detailed description of the operation of gate transitions. For the most part we shall ignore the re-entrant gate and concentrate on the pure and return types.

There are three types of gate calls, the jump, the jump-return, and the fork. The fork is essentially like the straight jump call with the exception that two processes exist while before there was only one. The distinction between the jump and the jump-return lies in the fact that the jump-return creates and passes to the called gate a gate which may be used to return control to the caller. Depending on the variety of return gate executed, the new return gate may either be placed on the key stack or in a designated memory location.

The key stack is an ad hoc vehicle for passing small numbers of keys across gate calls. Locations 16 and 17 decimal of the virtual memory of a process contains a stack pointer double word used to control a key stack. When a gate call is made, the contents of the key stack in the calling process are copied by the system into the called program’s key stack.

General registers are also handled in an ad hoc manner. There are instances when no general registers should be passed, as when restarting a suspended process. Can the other hand, general registers provide an efficient method for passing arguments. The proposed mechanism is as follows: the space page of each gate contains a bit mask indicating which, registers are to be passed across the gate. Since it is within the space page, the gate program can change the conventions when it wishes.

Multiple entry points are a very desirable feature of gates, as many complex packages will be built out of functions which need to share subroutines and context. A general, yet simple, scheme is the following: a bit mask is stored in the key table position corresponding to the gate key which describes which entry points are legal for a multi-entry gate. The key to a multi-entry gate may be used in two manners: if the key is referenced through an indirect key, an index field of the indirect key determines the entry point number; if the key is referenced directly, the contents of index register 7 determine the entry point number; in either event, the gate program begins execution with the entry point number in register 7 if the bit mask makes that entry point legal.

We are now ready to compare pure and return gates. The distinction between the two is quite simple - the space page of a pure gate is a template page; at the time of the first store into it, a private copy is made for the caller. Similarly, its context pages are either originally template pages or are acquired after the first call to the gate. If the pure gate was called by a jump-return, the called gate may also execute a jump-return to the caller, giving to the caller a return gate to be used in a subsequent call.

It should be noted that when a gate is executed, the key to it is removed from the callers virtual space to prevent multiple usages. In addition, any copies of the key held by the caller or any other process, are rendered useless. (This is only true for non-pure gates; since a pure gate generates private copies for each use, it is not rendered useless to others). However, the normal practice for a called gate is to deliver another return gate key when it returns to its caller. If a program repeatedly calls the “same” gate (i.e.; keeps using the new return gate), the actual structure involved is two co-routines rather than a strict subroutine hierarchy.

4.3.4 System Referee

The System Referee illustrates the flexibility of the system, architecture in solving a very fundamental problem. Many current systems protect a proprietary program from unauthorized use or thievery through various hardware and software limitations on access. The same does not hold true, however, for the user of the program; his data may be as proprietary to him as the program is to its author. In current systems, the user has no control over the actions of the program once initiated, even though it may be making copies of the user’s data in the program owner’s directory.

The problem of protection for the user is compounded by the fact that the owner of the program may have legitimate reasons for writing some sorts of data, such as accounting information or statistical summaries. The user of the program has no way of knowing what are legitimate functions and what are merely clever ways of encoding his proprietary data.

As a protection mechanism, an agent known as the System Referee may be invoked by a user to oversee execution of a program. This option is invoked by a parameter of a gate transition. The space page of the gate is flagged in the privileged area as being under the jurisdiction of the System Referee. All gate transitions made by the program are similarly flagged.

In operational terms, the flag causes the process to be suspended whenever it detects a non-master write key (or an indirect key pointing to one), in its space page. As part of the scheme, the user supplies a gate to the System Referee which will be called when the process is suspended. The user supplied procedure is given the data image (i.e., all the bits but not the status) of the key for examination. If the key is the member of an agreed upon set, the user program may restart the process; otherwise, it may abort it.

A short consideration of the mechanisms for information transmittal shows the above scheme is sufficient. A master key causes no difficulty because of its uniqueness. If the executing process holds the master key and is eventually deleted, no other access to that page exists. Read keys also present no problems, as the read key will not allow the process to write anywhere. Hence we need only consider non-master write keys. Now, the non-master write key must be put into the space page of some process within the jurisdiction of the System Referee in order to put data into it. Hence, detecting such keys on initial gate transition or during subsequent execution is sufficient.

There can be no limitation on the types of activity the process can perform once it has established the right to write in a page. Any write access can succeed in transmitting encoded user data. However, the user does have the option of allowing no external writing. To be workable, there must be some common agreement between the two parties. The important point is that the user can enforce the agreement himself by detecting violations of it.