UNIVERSITY MATHEMATICAL LABORATORY, CAMBRIDGE

Cambridge Supervisor : Planning Document 6
A Proposed File Dictionary System:
I - External View

1. Introduction

The proposed file dictionary system is designed with three objectives in mind:

1. That there shall be on the disc as little information as possible which cannot be accessed via the file dictionaries.
2. That there should be a flexible system whereby users can have controlled access to files belonging to other users, and whereby a group of users working on the same project can have what amounts to a communal file.
3. That the facilities provided for manipulating files should as far as possible suffice also for the administration of the file dictionaries, with the minimum of special facilities.

2. General Structure of the Dictionary System

Associated with each user in a User's File Dictionary (UFD) which contains an entry for each of that user's files. This entry points to the head of the chain of elements on the disc comprising the file (or to some other backing store device). Additionally, there is a Main File Dictionary (MFD) which contains one entry per user, this entry pointing to that user's UFD. Thus access to a file is through a two-level hierarchy of dictionaries. It is not proposed that this hierarchy should be extended to greater depth: it seems that a fully flexible scheme can be obtained by a mechanism of cross links at the second level.

In this context devices such as the printer and the plotter also appear as users (see Planning Document No. 2).

3. File Mode and Status

Following Planning Document No. 2, a file can be either in character mode or binary mode. NO indication of the mode of a file is carried in the file dictionary. The status of a file indicates the restrictions on its use, and is indicated by a set of markers. A tentative list of status markers is given here: for each the underlined state is the "normal" status.

(a) Temporary/Permanent:

Temporary files are deleted when read: all items in the well are temporary files.

(b) Reading Status:

(c) Writing Status:

(d) Status Change:

(e) Linkable/Not linkable (see Section 6.2)

Also associated with the status markers are the read and write interlocks (see Section 6).

Obviously, not all of the possible combinations of status marks are useful, or even meaningful, and the coding will be chosen to take advantage of this.

4. Naming of Files

A file name consists of three parts, α, β, γ. α is the user's name, and is usually implicit. β and γ are entirely free. This provides a two-part name as in MAC, and is also compatible with the way documents are titled in the present Supervisor.

5. Basic Operations

All file operations are made up from these basic operations. For example, FILE can be regarded as CREATE, and a cycle of WRITE instructions: this does not preclude the use of short cuts for supervisor efficiency.

The administration of the dictionaries likewise uses these basic operations. The special features required for dictionary administration are:

1. the system is the "author" associated with the MFD. This has status: read and write by author only, status change forbidden.
2. the system is the "author" associated with each UFD. These have status: read free, write by author only, status change forbidden.

6. Sharing of files

Three mechanisms for sharing files are provided, common files, linked files and grouped files.

6.1 Common Files

Any file which has reading status "free" can be read by any user. This facility is particularly valuable for library files. In this context each sub-system or compiling system ranks as a user, and has a UFD, all the files having status free read, write forbidden, status change forbidden. Thus to get a particular item from the XTRAN library, the user asks for file XTRAN/α/β. In fact, if he is already in the XTRAN system the system itself may generate the prefix.

This mechanism also makes it possible for routines developed by individual users to be made readily available for experimental use without complicated system administration.

6.2 Linked Files

A linked file is one for which the UFD entry points not to an actual file, but to an entry in another UFD. (This entry may in turn point to another UFD, so that arbitrarily long non-circular chains may exist.) For such a linkage to be possible, it is necessary that the UFD entry pointed at should have the status "linkable". When a link is established, the status of the "new" file is generated from the combination of the specified status and the status of the file being linked, thus if a link is made to a file with write-status "author only" the UFD entry pointing to this is given status "write forbidden".

The mechanism by which links are set up requires consideration. The MAC system requires that the user whose file is being linked to must first authorize a link from a specified user, then that user must call for the link to be established.

Associated with a UFD entry which has one or more links pointing to it are two interlock counters, the read interlock and the write interlock. These are initially both zero. Whenever reading is requested by any of the users who have access to the file, the read interlock count is increased by 1, being decreased by 1 when the operation is completed. As long as the read-interlock is non-zero, an attempt to write to the file will cause the program making the attempt to be halted until the read interlock is zero. As soon as a request is entered to write to the file, the write interlock is set non zero, and in this state any program trying to access the file, whether for reading or writing, will be halted until the write interlock is restored to zero on the completion of the current writing operation. This implies that if two users request writing operations to the same file there is some uncertainty as to which will be done first: however, this is intrinsically a dangerous thing to be doing, and the added uncertainty does not seem important.

Files can only be deleted by their authors. A delete command must obviously be delayed until all outstanding requests for the file have been serviced, i.e. until the read and write interlocks are zero. It is necessary that any UFD entries linked to the file must also be deleted: this implies that the UFD entry must include a marker to say whether any links exist to this file, and that backwards pointers must be provided. These backward pointers could be kept separately, since their number varies. Alternatively, deletion might be forbidden as long as links exist to the file in question. Thus all the "secondary" users would have to delete the appropriate entry in their UFD before the "primary" user could delete the file. To implement this system, the UFD would have to include a link counter, incremented when a link is established, and decremented when a secondary reference is deleted.

6.3 Grouped UFD's

Linked files provide for 'casual' cross references between user's files. When a group of programmers are working on a common project e.g. a compiler, the number of links required may be large, and tedious to set up. For this situation the concept of grouped UFD's is introduced. If two or more users are associated in a group, then any user in the group may access any file listed in any UFD of the group, subject to the restrictions indicated by the status marks. This is achieved by linking each UFD to the other UFD's in the group: if on a reading request the required file is not found in the requesting user's UFD, the other UFD's in the group are searched. Any one UFD can be a member of more than one group.

The mechanism of grouping is as follows. Each UFD contains a number of group pointers - one for each group it belongs to. The pointer identifies the "next" member of the group: for a set of users UFD's associated in a group the pointers form a circular chain. If a requested file is not found in the requesting user's UFD (the primary UFD), the UFD's on the first chain are examined. If the complete circle of the chain is traversed without finding the wanted file, the next chain is examined, and so on.

Mechanisms for setting up a group need consideration. One scheme is as follows:

Each group includes one primary UFD, to be called the head. The basic operation of adding one user to the group requires first that that user request linkage to the group, and second that the group head establish the connection. This would resemble the MAC way of setting up linked files.

DWB
28 July 1965

Copyright © 1965 University of Cambridge Computer Laboratory. Distributed by permission. Thanks to Barry Landy, Roger Needham and David Hartley for giving permission to distribute these documents. Thanks to Barry Landy for lending me the paper document from which this was scanned. Any typographical errors probably arose in the course of OCR.

Previous Planning Document: 5. Views of possible hardware alterations associated with object program core space allocation and addressing, DFH, 2 July 1965
Next Planning Document: 7. Initial Planning of the Cambridge On-Line System, JCV, 9 November 1965
Return to Cambridge Supervisor Planning Documents
Return to CUCPS TITAN page
Return to CUCPS home page
Return to University of Cambridge home page