# Design implementation of a time-sharing system: a critical appraisal

Claude Kaiser, Sacha Krakowiak

<figure><img src="image_1.png" /></figure>

## To cite this version:

Claude Kaiser, Sacha Krakowiak. Design implementation of a time-sharing system: a critical appraisal. [Research Report] IRIA-RR-050, IRIA. 1974, pp.19. hal-04715982

HAL Id: hal-04715982

https://inria.hal.science/hal-04715982v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Zuv: 02002 AR50

RIA
laboria

laboratoire de recherche
en informatique
et automatique

Design implementation
of a time-sharing system:
a critical appraisal

C.Kaiser,S.Krakowiak

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 50

Janvier 1974
DESIGN IMPLEMENTATION OF A TIME-SHARING SYSTEM :
A CRITICAL APPRAISAL

C. Kaiser, S. Krakowiak*

ABSTRACT :

The ESOPE multiaccess system has been designed and implemented
at IRIA as a research project, in an attempt to investigate the validity
of some operating systems concepts and to develop a design and implementation
methodology.

The purpose of this paper is to make a critical appraisal of the
project after one year's experience with the system. The main design decisions
are analyzed and criticized, as well as the implementation of the basic system
mechanisms.

RESUME :

Le système ESOPE a été étudié et réalisé à l'IRIA pour concrétiser
des recherches sur les systèmes d'exploitation à partage de ressource et à
accès direct. Il a permis de vérifier le bien fondé de certains concepts
et de mettre en avant une méthode de construction.

Dans cet article, nous effectuons une analyse critique de ce
projet après une année d'utilisation. Les principaux choix de conception sont
revus et critiqués, de même que la réalisation des mécanismes fondamentaux
du système.

<footnote>* Présente affiliation : Université de Grenoble-I, Laboratoire d'Informatique, BP 53, 38041 Grenoble-Cedex, FRANCE.</footnote>
The purpose of this paper is to present a critical appraisal
of the design and implementation of an experimental multiaccess system after
one year's experience with this system. The main design decisions are
analyzed and criticized, as well as the implementation of the basic
system mechanisms.

# 1. DESIGN OBJECTIVES AND FUNDAMENTAL CONCEPTS.

## 1.1 - *Design objectives.*

The primary objective of the ESOPE project was to get some insight
into the problems associated with the design and implementation of an
operating system. The external specifications have therefore been set up
with the concern of eliminating all that would result in a "purely quanti-
tative increase of the total amount of work to be done" [5]. The system,
which runs on a CII 10070 computer, provides three classes of service :

- a high priority job connected to mutually interactive terminals,

- a set of 24 conversational console jobs,

- a background job.

A more detailed description can be found in [1, 5, 7, 8].
The problems encountered during the design could be classified under
the following headings : concurrency, information management and naming,
resource allocation, protection and reliability. We tried to investigate
each class of problems by creating appropriate design concepts ; we then
had to solve the problem of implementing these abstract entities into
specific mechanisms on the available hardware.

Some attention was paid to the development of a design and implemen-
tation methodology. A favorable factor was the (rather untypical) fact
that the same team of five people has been involved in the project from the
first specifications throughout the coding and testing phases.
## 1.2. - *Basic concepts.*

The system relies upon a small number of basic concepts, each related to the specific problems listed above :

- Logical and physical concurrency is handled by describing all activities in terms of sequential *processes*. Process synchronization is achieved by means of semaphores.

- All information handling relies upon the use of *segments*.

- The resource allocation policy is designed to avoid thrashing by activating a process only if a sufficient share of core memory has been allocated to it. Therefore, there is a precedence order between memory and processor allocation, which also has the effect of avoiding deadlock on memory [4].

In order to provide a unique conceptual framework for the above notions, the concept of *user* was introduced. A user is defined as :

- a loosely connected collection of interacting processes (there is no explicit interaction between processes of different users),

- a single naming space (i.e. a means of accessing information contained in segments),

- an elementary competitor for the system resources (i.e., resources are allocated globally to users, not to individual processes).

As a result, the concept of user also provides a convenient framework for protection. The separation of processes between users raises the problem of interprocess (within a user) and inter-user communication. This will be considered later in this paper.
## 2. OVERALL STRUCTURE OF THE SYSTEM.

The user concept provides a first level of structuring : the system
can be regarded as a two-level user hierarchy, as represented in figure 1.

<figure><img src="image_3.png" /><figcaption>Fig. 1. The user hierarchy.</figcaption></figure>

Each user other than the monitor is equivalent to a distinct
subsystem, or a virtual machine. Thus the I/O subsystem, the real-time high-
priority subsystem and the background job subsystem are each represented by
a user, as well as each one of the conversational jobs.

We shall first describe the structure of a user when considered as a
virtual machine. This description applies to all users other than the monitor.

### 2.1.- *The user as a virtual machine.*

The user virtual machine consists of a virtual memory and a set of
primitive operations available to the processes.

### 2.11 - *Virtual memory.*

The virtual memory of a user is a one-level, linear, paged addressing
space. The segments, each of which is a single linear space, are also divided
into pages. Access to segments is achieved by setting up a one-to-one mapping,
or coupling, between segment pages and virtual memory pages.
Thus, at a given time, the virtual memory can be coupled to parts of different
segments. The coupling operation has the only effect of updating virtual
memory tables and does not generate any transfer of information. The available
information handling primitive operations allow to *create* and *destroy* a
segment and *couple* or *uncouple* segment pages. The use of the coupling
primitives is protected by means of *open* and *close* operations : only an open
segment may be coupled, with a specific access right.

## 2.12 - Process management.

There is a two-level hierarchy within the processes of a user. A
system-provided process, called the princeps process of the user, is at the
top level ; the other processes are at the second level. The available process-
handling primitives include semaphore creation and destruction, the P and V
synchronizing operations, and process creation and destruction. In order to
enforce inter-user protection, processes and semaphores within a user are desiga-
ted by names local to this user, which makes unwanted interference impossible.
However, each princeps process may access semaphores local to the monitor
(figure 2).

<figure><img src="image_4.png" /><figcaption>Fig. 2. Local and global semaphore names.</figcaption></figure>
## 2.13 - The princeps process.

Within a user, the princeps process is part of a "distributed monitor" with the following functions:

1) The princeps process of a user interprets the command language of the subsystem associated with the user. In particular, it controls the operation of the linking loader. This loader implements a procedure reentrancy between users (data are initialized from a common pattern), sets up a pagewise protection for program and data and performs a cross-reference optimization to increase the locality of the programs.

2) The princeps process is in charge of the standard error-handling and debugging operations. Thus it has the ability to interrupt all other processes of the user, by forcing them to perform a P operation on a special semaphore; this facility is used, for example, when responding to a system call from a teletype, which allows the user virtual machine to return to a standard state. The trap-handling routines are also managed by the princeps process, which takes control in the case of an error in a user-provided error-handling routine. Lastly, the princeps process may provide information on the internal states of the user processes and semaphores, for debugging purposes.

As a result, the princeps process is given special rights with respect to synchronizing operations, access to segments and data, and protection of its private information against other processes.

## 2.2 - System decomposition.

We shall now give a more detailed account of the system structure in terms of processes and data.

### 2.21 - Process structuring.

The structuring of processes results from the user hierarchy and from the internal structure of a user. The latter has been described above; a detailed account of the internal process structure of the monitor can be found in [3].
Some system activities are not representable in terms of processes: these are the basic mechanisms which implement the primitive operations accessible to the monitor and the other users. These primitives are coded by means of supervisor call routines (SVC). At this lowest level, we also find the interrupt handling routines which are essentially represented by V operations on some monitor processes. Thus, this lowest level, called the kernel level, simulates a semaphore machine, without interrupts, whose operation code includes the process manipulation and synchronizing primitives as well as the segment-handling operations. The resulting three-layer structure is shown in figure 3.

<figure><img src="image_5.png" /></figure>

Implementation
of the basic machine
'> kernel)

Interrupt, trap and SVC routines

<caption>Figure 3. Process structuring in the ESOPE system.</caption>
## 2.22 - *Data structuring*.

Information may be classified according to the access allowed :

1) - *Monitor private data.* They are resident in physical space and consist of descriptors of system objects : users, processes, semaphores memory pages, segments.

2) - *Data shared by monitor and other users.* Some of the data are common to the monitor and a single user ; others are common to the monitor and all users. In both cases, the data are contained in predefined virtual pages which are kept resident in fixed page frames. This simple technique insures an easy user-monitor communication. The association of a virtual page to a fixed physical location may be permanent or temporary. Access to these communication pages is restricted to the princeps process of a user.

3) - *Users' data.* These data, contained in segments, are made accessible by the coupling mechanism. A segment (e.g. a reentrant procedure) may be coupled to several virtual spaces at a given time.

## 2.23 - *Lifetime of the objects.*

The different objects of the system have different lifetimes :

1) - *Users.* Some users are created at system initialization (e.g. the I/O user). Others are created and destroyed dynamically : for instance, the user associated with a conversational job is created at login and destroyed at logout. When created, a user contains only one process, its princeps process.

2) - *Processes and semaphores.* Within a user, processes and semaphores can be created and destroyed dynamically. The princeps process, however, cannot be destroyed during the user's lifetime. The destruction of a user implies the destruction of all its processes and semaphores.
3) - *Segments*. Segments are created and destroyed dynamically. A segment created by a user may survive the user's destruction only if it has been given an external name.

### 3. IMPLEMENTATION PROBLEMS.

We shall now present the main problems which were encountered in the mapping on the available hardware of the functional structure described above.

#### 3.1. *Process and information handling primitives.*

The concepts of process management and information handling must receive a different treatment at each level of the system hierarchy. At the two higher levels, inter-user as well as monitor-user protection must be enforced; at the lowest level, where the primitives are implemented, the peculiarities of the context-switching and information accessing mechanisms provided by the hardware must be taken into account. This goal is achieved by the use of a unique basic data structure with a distinct access mechanism at each level of the hierarchy.

As regards process management, the unique data structure is the set of descriptors for all processes and semaphores existing in the system. Any process or semaphore has an internal name within this structure. The access mechanisms are described below:

1) - in the kernel, the implementation of the synchronizing primitives includes processor allocation. But one must be able to use these primitives in SVC, interrupt, and trap routines, which are also part of the kernel, and which make use of the automatic context switching provided by the hardware. To avoid conflicts between these two modes of processor allocation, the version of the synchronizing primitives which is used in the kernel does not perform the actual processor allocation, but only the updating of process queues, if the state of a process is changed as a result of the operation. The actual processor allocation is left to the SVC, interrupt or trap routine where the synchronizing primitive has been called.
Since the effect of interrupts is represented by semaphore operations, the only uninterruptible sequences could be, in principle restricted to the kernel. Unfortunately, it may happen, e.g. for the I/O subsystem [1], that an interrupt routine must access variables in mutual exclusion with another process. Therefore, for real time constraints, interrupts must be masked during very short steps of some monitor processes. Apart from this peculiar case, all process executions are interruptible.

2) - at the monitor level, a fixed number of monitor semaphores are used for the cooperation of monitor processes, for I/O request transmission by a mail-box mechanism and for user-monitor communications. The monitor semaphores are known by their internal name, and no user process, except the princeps, is allowed to operate on them.

3) - at the user level, processes and semaphores may be created and destroyed dynamically. They are only accessible by local names, and the mapping between local and internal names is the responsibility of the kernel. A primitive executed by a user process (other than the princeps) may only have a local name as a parameter.

### 3.12. Information handling primitives.

As regards information handling, the unique data structure is the set of descriptors of all segments existing in the system. The constraints imposed by the segment on memory management are indicated there, (sharable, non sharable, resident in core). Each user can deal with a set of local names that it can assign dynamically. The mapping of local names into segment descriptors is the monitor's responsibility. The list of the user's access rights to the named segment is associated with each local name.

### 3.2. Memory management.

Since the addressing structure of the CII10070 does not include a base register, procedures and data cannot be moved in virtual memory in a straightforward fashion. [10] Therefore they are kept in fixed virtual locations. This contributes to a restriction of the available space in the user virtual memory, introducing the need for an elementary overlay structure, handled by
the coupling mechanism.

The mapping from virtual pages to physical frames is performed at every memory reference by indexing a table in high speed memory. The modification of this table, which takes place at least at every processor switching is complicated by the absence, for every page entry, of a presence bit and a use bit. In order to simplify this table management, the virtual memory of every user was divided into two sets of contiguous pages : a swappable set and a holy set whose pages are kept resident in core. Normal users have an empty holy set and only a few special ones, like the I/O user or the graphic display user which have members in the two sets. Moreover, by permitting the creation and deletion of holy pages and allowing a variable boundary between the two sets, a great flexibility in the I/O device buffer management was obtained.

### 3.3 Protection.

As the design did not include a general protection mechanism, the usage of the hardware protection features was elaborated at each hierarchical level :

- Protection among users is enforced by the presence of disjoint virtual spaces. The monitor runs without memory map and is therefore hidden from all users. Conversely, memory frames containing user's pages receive specific locks which prevent the monitor processes from writing into them.

- Inside a virtual memory, code and data of a user can receive different access protection. However, it is not possible to fully protect the processes of a user from each others, since the number of available memory frame locks is too small. Then two classes of processes are considered, the princeps process and other processes. Only the princeps process is allowed to write into its own data and into monitor's data and to couple monitor segments to the virtual memory.

- As the processes of a user may use the same primitives as monitor processes, a dynamic check is performed at the time of any primitive call. Every possible agent of the hierarchy, i.e. process or user, is associated with an authorization list which defines at any moment the primitives it is allowed to call. Every primitive starts at a unique entry gate, where the authorizations are checked.
and, if needed, the agent receives further authorizations. For example, if the primitive uses data of monitor segments that have to be accessed in virtual memory, coupling authorization for this access is provided at this gate. Likewise, every primitive ends at an exit gate where the original authorization list is restored. These checking operations produce some overhead since they lead sometimes to switch control between resident and non resident monitor, i.e. between virtual and physical addressing spaces.

- The privileges of the monitor itself are limited as much as possible. Thus the distributed part of it, using virtual memories, runs in slave mode only.

### 3.4. *Implementation stages.*

We tried to keep the target structure of the system apparent all through implementation. To achieve this goal, the main processes of the system were implemented as early as possible, sometimes in a very simplified form. The construction was made in stages, and at each stage new functions were introduced and a running system constructed. Specific software measurements were used to fully debug the system and to enhance our knowledge of its behaviour.

The set of synchronizing primitives, a part of the kernel, was first built, allowing us to implement the skeleton of the monitor processes and, together with their princeps process, as many users as we had available terminals. Each user could then use very crude versions of a text editor and desk calculator. At this point, CPU time was the only resource to be dynamically allocated. Nevertheless, many problems of concurrency were present and could be debugged while the system was still small. The most helpful debugging devices used were: a program looping for a finite duration allowing us to increase the load of the system at the user level, and a cyclic buffer in which, at every process switching, were put the name, address and duration of the former active process.

The second stage concerned the allocation of physical memory. The virtual memory was used with fixed segment pages associated to it, i.e. without dynamic coupling. The main debugging tools added were a copy of the memory map, to cope with the absence of an instruction for reading the memory map itself, and a display of the state of the different queues (page queues, user queues ...).

Virtual memory management was the next implemented feature. It includes the coupling mechanism and the segment management. Virtual memory descriptors and segment descriptors were useful information to trace during system execution.
The different classes of users were then introduced : normal conversational user, high priority user, graphic console user, I/O user, batch user. This concluded the implementation of the princeps process. Therefore, every user was supplied with private interactive debugging commands.

Finally, the main software facilities, i.e. text editor, interpreters compilers and link editor, were integrated. The command allowing the princeps to stop, to examine and modify the other processes of the user turned out to be a very convenient debugging tool.

## 4. CRITICAL EVALUATION OF THE PROJECT.

The concepts and mechanisms presented above have been explored with a number of subsystems, including a PL/I interactive compiler, a graphic display subsystem and an interactive simulator which allows several on-line terminals within a single user. These two latter subsystems, in particular, provided many opportunities to appraise the use of process synchronization and segment management in the users' programs.

### 4.1. Concepts and mechanisms.

The notion of a user provided a good unifying concept for the separate notions of resource allocation, protection and virtual space. However, the implementation of a multiprocess user on a single-process oriented hardware had some harmful consequences : for instance, all processes of a user had to share the same virtual space, with the same protection, and the same SVC and trap mechanisms. For protection's sake, this sometimes led to inhibiting the parallelism of actions within a user during some SVC executions.

The introduction of a unique synchronizing primitive, and the interpretation of interrupts by V operations had a positive effect : very few concurrency errors occured and all of them were detected and corrected at an early stage. In addition to P and V, a new synchronizing primitive was introduced, which simulated a "memoryless event". It turned out that this primitive was not actually necessary and that it could lead to errors difficult to trace if used concurrently with V operations on the same semaphores.
No hierarchy (such as the usual tree-structuring) was introduced between segments. It appeared that a hierarchy was not generally needed, except for special applications, such as the graphic user, for which a special segment system was built on top of the basic one. Coupling was found useful, not only to extend the limited virtual memory, but also to make an efficient use of paging (e.g. page-wise organization of hash-tables). However, copying a segment to another segment involves the coupling of two page frames and an information transfer in core memory between these two pages. From an implementation point of view, coupling provided a unique mechanism for information transfer between memory levels.

Generality was a permanent concern in the design of mechanisms; some of them, however, turned out not to be general enough. Dynamic creation of processes and semaphores should have been allowed to monitor processes as well as to user processes, in order to allow an easy bootstrapping of the system. The mailbox mechanism used for I/O request transmission should have been extended to all kinds of inter-user communications. The present set of access rights to segments, i.e. *read*, *write*, *execute*, *shared*, should have been extended to include *copy only*. This latter type of segment would have to be kept resident on drum for protection purpose.

## 4.2. Method of construction.

### 4.21. Implementation language.

A PL/360-like language was used for the implementation. The most notable differences with PL/360, apart from machine dependent features, were an inter-program communication facility (external variables) and an elementary macro system. The use of this language provided good program readability and made therefore easy program communication, modification and debugging. Some less desirable features of the language were detected with experience. Direct access to the general registers — of the machine was actually very seldom needed, but the lack of an automatic register management proved to be a burden on the programmer and a source of trivial coding errors. Another weakness of the language was the inability to describe elaborate data structures and to specify controlled accessed mechanisms.
## 4.22. *Some pragmatic aspects.*

Few programming and debugging aids were used during the implementation of the system. This decision was definitely a wrong one, as was shown by experience. The few run-time aids which were actually implemented (in particular the time-labelled process trace) proved to be of considerable value. Besides, having everyone's code hand-checked by another person improved programming style and allowed an early detection of many errors. As the system was an experimental one, intended to be run at a unique site, only casual attention was paid to the system generation problems. This was another mistake: the need of a systematic procedure for system generation and bootstrapping became clear when the system grew larger.

## 4.3. - CONCLUSIONS.

One learns from one's mistakes. We found out that, in the process of designing and implementing our system, we had violated a number of "rules of action". These rules may appear obvious; it turned out, however, that they are not always easily put into application. The following list could probably be extended:

- "independence rule" : do not introduce artificial links between logically independent objects. A violation of this rule is the association of the processes of a user to a single trap-handling procedure.

- "uniformity rule" : use a uniform mechanism to perform a uniform class of actions. This rule was obeyed for the transfer of information between main and secondary storage, but it was overlooked as regards the compatibility of I/O streams between terminals and segments.
- "opaqueness rule" ([9]): do not let people know too much about other people's modules. In too many instances, direct knowledge of data structures (especially shared data) was used instead of calling a standard access procedure. As a result, any modification in such structures resulted in many modifications being scattered throughout all accessing modules instead of a single change in the access procedure.

In most cases, it can be noticed that the design errors resulted from taking binding decisions at too early a stage of the design.

### ACKNOWLEDGEMENTS.

The authors are indebted to the other members of the ESOPE team, C. Bétourné, J. Ferrié and J. Mossière, and to G. Baudet and J. Boulenger for their important contributions.
REFERENCES

1. BAUDET, G., FERRIE, J., KAISER, C., MOSSIERE, J. Entrées-sorties dans un système à mémoire virtuelle, *Congrès AFCET, Grenoble (1972)*.

2. BETOURNE, C., BOULENGER, J., FERRIE, J., KAISER, C., KRAKOWIAK, S., MOSSIERE, J. Process Management and resource sharing in the multiaccess system ESOPE, *Comm. ACM* 13, 12 (1970) pp. 727-733.

3. BETOURNE, C., FERRIE, J., KAISER, C., KRAKOWIAK, S., MOSSIERE, J. System design and implementation using parallel processes, *Proc. I.F.I.P. Congress, Ljubljana (1971)*, TA-3, pp. 31-36.

4. BETOURNE, C., KRAKOWIAK, S. Simulation de l'allocation de ressources dans un système conversationnel à mémoire virtuelle paginée, *Congrès AFCET, Grenoble (1972)*.

5. DIJKSTRA, E.W. The structure of the THE multiprogramming system, *Comm. ACM* 11, 5 (1968), pp. 431-446.

6. FERRIE, J., MOSSIERE, J. ESOPE : gestion des processus et partage des ressources, *Cahier de l'IRIA N° 8 (1972)*.

7. KAISER, C. Conception et réalisation de systèmes à accès multiple : gestion du parallélisme. *Thèse de Doctorat ès Sciences, Paris (1973)*.

8. KRAKOWIAK, S. Conception et réalisation de systèmes à accès multiple : allocation de ressource, *Thèse de Doctorat ès Sciences, Paris (1973)*.

9. PARNAS, D.L. Information distribution aspects of design methodology. *Proceedings I.F.I.P. Congress, Ljubljana (1971)*.

10. WATSON, R.W. Time sharing systems design concepts, *Mc Graw-Hill (1970)*.