RIA
laboria

laboratoire de recherche
en informatique
et automatique

An analysis of
some run-time errors
in an operating system

(version anglaise)

31 P

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° 49

(version anglaise)

juin 1974
AN ANALYSIS OF SOME RUN-TIME ERRORS
IN AN OPERATING SYSTEM

C. Kaiser*

S. Krakowiak**

Résumé. On s'intéresse dans cet article aux erreurs dans les programmes, et plus particulièrement dans les systèmes d'exploitation. Après avoir introduit quelques définitions touchant la génération et la propagation des erreurs, on analyse les symptômes et les causes de trois pannes survenues au cours du fonctionnement d'un système d'exploitation. Cette analyse sert de base à un essai de classification des erreurs dans les systèmes. En conclusion, on tente de tirer de cette expérience quelques enseignements pratiques.

*Abstract*. This paper deals with the subject of errors in programs, and more specifically in operating systems. Some definitions regarding error production and propagation are introduced. The symptoms and causes of three run-time errors which were observed in the last stages of the development of an operating system are analyzed. In conclusion, this analysis is used as a basis for a tentative classification of systems programming errors.

This material was first given in French in "Rapport Laboria n° 49" A revised version has been presented at the International Symposium on theoretical and practical aspects of operating systems, held at IRIA April 23-25,1974. This is an English transcription of the latter version.

<footnote>*IRIA (Laboria)</footnote>

<footnote>** Université de Grenoble I, Laboratoire d'Informatique (The work described in this paper was done while this author was associated with IRIA).</footnote>
AN ANALYSIS OF SOME RUN-TIME
ERRORS IN AN OPERATING SYSTEM

----:--:--:--:

# 1 - INTRODUCTION -

## 1.1 - Motivation for this study -

A substantial part of most programmers' activity is devoted to the tracking and correction of programming bugs. With regard to its practical importance, it does not seem that this subject has received the amount of attention it deserves. An increasing number of investigations are concerned with methods aiming to reduce the probability of occurrence of errors by a better structuring of programs and data. Debugging techniques are also a subject of current attention. Yet, it appears that the study of the forms, types, and causes of errors in programs has been somewhat neglected, and the list of references that we were able to collect on this subject is rather short (4, 10, 11). One reason for this situation may be the difficulty involved in going further than a more or less anecdotical description. another reason which makes a logical presentation difficult is that the domain of "incorrect solutions" to a problem is incomparably wider than the domain of correct solutions. Nevertheless, we found it worthwhile to analyze a number of "real life" errors, hoping to achieve a better understanding of the reasons for their occurrence. A further step would be the elaboration of methods tending to avoid making the same type of errors during the design and implementation of future systems.

The errors described in this paper were detected, along with many others, during the development of an operating system. Errors tend to have a special importance in this type of program, as they are very likely to be present and very difficult to locate. This is due to several causes: 1) Systems programs are usually large programs, 2) As they are designed and implemented by many people, documentation and communication become problems, 3) Systems programs involve parallel process execution, which gives rise to new classes of time-dependent errors, which are difficult to reproduce.
In the absence of a standard terminology for programming errors
our first attempt will be to propose some defintions.

## 1.2 - Terminology -

### 1.21 - Error production, manifestation and detection -

We shall first consider a single sequential process. The notion of an action will be taken as a primitive concept. An *action* is a phenomenon of finite duration, which takes place in a given universe (here called "the system"), whose states can be defined and observed before and after, but not during, the execution of an action. The intended purpose of an action is to change the state of the system. More precisely, the effect of an action *A* which changes the system's state from *S1* to *S2* may be specified [3] by an initial assertion $p_A(S1)$ and a final assertion $q_A(S2)$, which are boolean functions of the system state, such that, if $p_A(S1) = true$, then $q_A(S2) = true$. A *program* is the description of a set of actions in terms of some vocabulary, which includes the description of a fixed set of elementary actions and of certain sequencing rules which permit to combine actions. We shall assume that these sequencing rules do not allow parallel execution of elementary actions. The phenomenon which takes place when the program is executed, i.e. the execution of the sequence of elementary actions described by the program, is called a *sequential process* (we shall subsequently omit the term "sequential"). The execution of a process has a certain intended effect and, if its duration is finite, it may be considered itself as an action. By definition, an error is produced during the execution of a process if, after the execution of some action of this process, the final assertion corresponding to this action is *false*, while the initial assertion was *true*.

This definition is of little practical value, as most of the
assertions (let alone the program specifications !) are neither explicit
stated in the design stage of a program nor checked during program execu-
tion. Two consequences result: First, a considerable number of actions
may take place between the production of an error and its detection, i.e.
the discovery of the falsity of some final assertion. Second, an error
may go undetected, as long as it has no influence on any assertion which
is actually checked ; but a change in this situation, for instance after
a program modification, may unearth an error apparently uncorrelated with
the modification, and therefore very difficult to find.

Example :

Suppose that a supervisor call ( say Q) has the unspecified
side effet of clearing the register R5. This error will never be detected
if no attempt is made to reuse the old contents of R5 after a call of Q.Neither
will it be detected if the contents of R5 is consistently zero before Q is
called. But a change in the register allocation strategy (a new version of
an optimizing compiler !) may cause the error to appear.

These considerations lead us to introduce the following defini-
tions (see fig. 1) : we call *manifestation* of an error the first non-
verification of some initial assertion after the production of the
error. This is actually the first irreversible consequence of the error.
This definition assumes the existence of a single error ; we are not con-
sidering the case of error interference. Between its production and its
manifestation, the error will be called *latent* ; between its manifesta-
tion and its detection, it will be termed as *propagated*.

<table><caption>Fig. 1 : The phases of appearance of an error</caption>
  <tr>
    <td></td>
    <td>PRODUCTION</td>
  </tr>
  <tr>
    <td>latency time</td>
    <td>latent error</td>
  </tr>
  <tr>
    <td></td>
    <td>MANIFESTATION</td>
  </tr>
  <tr>
    <td>propagation time</td>
    <td>propagated error</td>
  </tr>
  <tr>
    <td></td>
    <td>DETECTION</td>
  </tr>
</table>

In our previous example, the error which consisted in the zeroing of R5
is latent between the return of Q and the first reading (if any) of the
old contents of Q5. Between this reading and its visible consequence
(if any) the error is propagated.
The possible existence of a latency time may be explained as follows: let A and B be two actions; let $p_A, q_A, p_B, q_B$ be the corresponding assertions. The validity of the construct A ; B relies on the relation $q_A \supset p_B$ ; however, the equivalence $q_A \equiv p_B$ is not required. Therefore, after an execution of A, the situation may be that $q_A = \underline{false}$ (an error was produced in A), and $p_B = \underline{true}$. In such case, the error will go through B undetected. Two remarks are now in order as regards the system's observability:

1) - The decomposition of a process into actions is, to a large extent, an arbitrary choice. In particular, a sequence of actions $A_1; A_2; ... ; A_k$ is itself an action A, with $p_A \equiv p_{A_1}$ and $q_A \equiv q_{A_k}$. As it depends on the action concept, the error concept is itself related to an observation level. Thus, in the example of the supervisor call, if the choice is to regard the action Q as atomic, error production takes place immediately after the execution of Q. But if one chooses a finer level of detail (for instance the execution of a machine instruction) one will be able to trace down, within the body of Q, the production and manifestation of the error.

2) - The definitions given above apply to the execution of a single sequential process. Their extension to the case of the parallel execution of several processes would be desirable, considering that operating systems usually involve parallel process execution. However, one must be very careful in the choice of the instants of observation, which should allow a precise definition of the state of the system with respect to all processes.

We shall now consider different error types.

## 1.22 - Incidents and crashes -

Let us consider the possible reaction to an error detection. The occurrence of a certain error at some point in the execution of a process may in some cases be expected, and, in particular, some further action may depend on this occurrence. Such an error will be called
an _incident_. Conversely, when an error is unexpected, which usually prevents the program from performing its intended effect, it will be called a _crash_.

If we want to keep the definition of an incident consistent with the previous definitions (1.21), we have to assume a second level of assertions, allowing us to describe the violations of the first-level assertions. This is actually the case in any well-designed operating system, where an error in a user's program (which appears to him as a crash) should be treated as a mere incident by the monitor, which must provide uninterrupted service to other users. Likewise, the monitor must try to cancel or to minimize the effects of a hardware malfunction. Thus, the programs in charge of incident handling are of vital importance in an operating system.

## 1.3 - Some definitions for the ESOPE system -

The errors described here were observed on the system ESOPE. We shall limit our account of this system to the notions which are necessary to understand what follows. A more complete description is given in [1].

### 1.31 - The hardware -

ESOPE runs on a CII 10070 (a French version of the XDS Sigma 7). This is a single-processor machine. A multiplexor channel allows several device controllers to operate in parallel with the CPU. This latter operates on the channel and controllers by means of I/O instructions such as *SIO*, *AIO*, *HIO*. The execution time of these instructions is unrelated to the time needed for the physical transfer of the information. Significant events related to this transfer are signalled to the CPU by means of an interrupt. A single interrupt level is used by all I/O devices, and an interrupt mask may be set by the CPU.

The operating state of the CPU is reflected in a Program Status Doubleword (PSD), which contains, along with other information, a supervisor/program mode indicator and a physical/virtual addressing indicator. Some instructions (e.g. I/O instructions, mode control, ...) may only be executed in supervisor mode. According to the state of the
addressing indicator, the current instruction may refer directly to a
location in the physical store (the address belongs to the *physical address space*) or to a virtual location (the address is part of a *virtual memory*). In this latter case, the mapping between virtual and physical
memory is defined by a hardwired table, the *memory map*, which is part
of the CPU. By changing the contents of the memory map, one may define
a new instance of the virtual memory, mapped onto the same physical space.
The mapping is *pagewise*: virtual memory *pages* are mapped on physical memory *frames*; the page size is 512 words and a virtual memory contains 256 pages.

## 1.32 - *The supervisor* -

Besides those objects defined by the hardware structure,
(pages, frames, virtual memory) the ESOPE system defines processes, sema-
phores, users, files and primitives.

A *process* is a sequence of instruction executions; any
activity in the system is part of a process. Process synchronisation is
achieved by means of common *semaphores*.

*Users* are defined as sets of cooperating processes. With each
user is associated a virtual memory and a *princeps process*, which acts
as the delegate of the supervisor among other processes of the user. The
princeps process of a user blocks the other processes of this user when
it is activated. All processes of a user are executed in program mode
and have access to their common virtual memory.

*Files* are sequences of information pages.

System *primitives* are programmed extensions of the operation
code of the machine, made accessible to users by means of supervisor
calls (*CAL* instruction). Primitives may operate on processes (create,
destroy), an semaphores (create, destroy, *P*, *V*), on files (create, des-
troy, open, close, name, couple a file page with a virtual memory page)
The *supervisor* includes the code of the system primitives,
a set of resident processes executed in the physical space, and the set
of princeps process of all users.

## 2 - AN ANALYSIS OF THREE CRASHES -

It seems worth noting that the crashes described in this paper occurred in the last stage of the system development. The main mechanisms for process synchronization and resource management were performing their functions correctly, and the system was used in an experimental environment. The mean time between crashes was roughly a few hours. Observation seems to show that the errors which remain at that stage of development, besides their low frequency, have a long propagation time. One reason for this is the ability of an operating system, beyond a certain degree of complexity, to continue to perform some or all of its functions after the production of an error. This robustness, which might be praised as an advantage in system utilization, contributes to the loss of the informations which would be needed to locate the error, if no special care has been taken to preserve such information.

A PASCAL-like language [13] will be used for the description of the algorithms.

### 2.1 - An unexpected form of deadlock -

Incorrect programming of I/O operations on the operator's teletype was the cause of this error.

### 2.11 - Error explanation -

Any incident in a monitor primitive executed in physical space produces an immediate reaction : an error message is printed on the operator's teletype, and the systems stops, awaiting operator's action. The printing of the error message cannot use interrupts since all interrupts are masked off during the execution of monitor primitives. The following scheme applies :
procedure primitive {this is the program of a system primitive}

begin

mask all interrupts;

...

if error detected then

begin

bastringue ("System error n° j"); {print the error message}

wait for operator's reaction

end;

...

clear interrupt mask

end;

If a line of text is being printed on the teletype, the procedure *bastringue* waits for the end of this line; then an order is issued for the printing of the error message. If the waiting time for either the end of the current printing or the end of the printing of the error message is too long, this is interpreted as a malfunction of the operator's teletype. In such a case, an ultimate attempt is made to attract the operator's attention by causing a whistling sound to be produced by the built-in loudspeaker of the CPU.

The following procedures are used :

function controller free : boolean; {device controller not used}

var n: integer, cc: boolean;

begin

controller free := false; n := 0;

repeat

TIO (cc); {hardware test; if controller is not used,
          cc := true}

controller free := cc;

n := n + 1

until (n > limit) V controller free

{limit correspond to the maximum time needed to print a line}

end;
`procedure whistle; {operates the loudspeaker of the CPU}`

`repeat forever`

`WD (65); {whistling order}`

`procedure bastringue (message : alfa);`

`begin`

`if- controller free then whistle; {wait}`

`SIO (message);`

`{order for printing}`

`if- controller free then whistle; {wait}`

`end`

Besides being used for error messages, the operator's teletype is used as a standard means of communication for the handling of user jobs and the controlling of I/O devices. The teletype operation is managed by a special process, called *servant*, which takes into account the parallel operation of the CPU and the device controller.

`var SIT : semaphore; {initial value : SIT = 0}`

`procedure servant; {this is the program of the servant process}`

`repeat forever`

`begin`

...

`SIO (message);`

`{order for message printing}`

`P(SIT);`

`{wait}`

...

`end;`

`interrupt procedure input-output; {this procedure is executed
after an I/O interrupt}`

`begin`

`AIO; {acknowledge interrupt and de-allocate controller}`

`V(SIT);`

`end;`

The solution given above is in fact incorrect. When the *servant* process blocks itself as a result of *P(SIT)*, the execution of another process, *p*, is resumed on the CPU. If an error occurs in a monitor primitive invoked by *p*, before a *V(SIT)* is performed by the I/O interrupt, then procedure *bastringue* is called while the system is in the
following state :

- the interrupts are masked off

- the teletype controller is held up by the *servant* process.

There is no way out of this state because the controller may be released (by an *AIO* instruction) only if the interrupts are unmasked.

This error may be made more explicit if we attempt to interpret hardware operations in terms of semaphores :

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

Now we clearly have the usual form of deadlock, as the two
following actions are executed in parallel :

a) P mask) ; P (controller) by procedures *primitive* and *bastringue*

b) P controller) ; P (mask) by procedures *servant* and *input-output*

This error is immediately detected; its latency time and propagation
time are zero.
## 2.12 - Error correction -

The usual remedies to deadlock may be applied :

a) - Request resources in the same order -

This remedy cannot be used here. If the order `P controller)`;
`P mask)` is chosen, this amounts to reserving the operator's teletype before
any execution of a system primitive, which is unrealistic. The opposite
choice prevents the use of interrupts by the *servant* process and parallel
I/O on the operator's console.

b) - Preemption of one resource -

Either resource (i.e. interrupt mask or operator's teletype)
may be preempted, depending on which process one wants to favor.

Preempting the interrupt mask gives priority to the *servant* process :

procedure primitive, {a possible remedy to deadlock}
begin
  P mask);

if error then

begin
  V (mask);          {clear interrupt mask}
  bastringue ("System error n° j");
  P (mask);          {mask off interrupts}
  wait for operator's reaction;
...
end;

V (mask)
end
The drawback of this solution is that it allows the typing of a whole
series of messages if the process *servant* uses channel command chaining to
speed up the input-output. On our machine, the interrupt mask is unique for
all I/O devices, and thus other processes with greater priority may be
allowed to be executed. Thus the execution of *bastringue* is delayed and the
initial error is allowed to be propagated, which contributes to the loss of
the information on the state of the system at the time of the error
manifestation.

The solution finally chosen was the preemption of the device
controller by procedure *bastringue* :

procedure bastringue (message : alfa) ; {the implemented cure of deadlock
begin
  HIO ; {stop the current I/O and release controller}
  SIO (message) ;
  if controller free then whistle
end

The preemption takes place so quickly that even the printing of the
current message is interrupted.

2.13 - Comments -

a) - The use of two distinct synchronizing methods (interrupts and semaphores) has masked the programming error. In this specific case, as well as in the I/O subsystem, the hardware structure of the machine did not allow the use of a single mechanism as in the remainder of the system.

b) - The use of a single teletype for the operator communications has
introduced an unexpected link between two independent operating conditions
of the system.
## 2.2 - A disguised form of the goto --

### 2.21 - Error handling mechanism -

The mechanism described in 2.1 allowed the monitor to react to the detection of an error in one of its own processes. What is described now is the reaction to the occurrence of an incident in a user process. The operation of this error handling mechanism was the occasion of a series of crashes which we shall analyze in some detail, because they tend to illustrate some rather typical design errors.

An incident in a user process may appear while executing either a non-privileged machine instruction or a system primitive. The incident is detected in the first case by the hardwired trap mechanism, in and in the second case by a programmed check. In both cases, the effect of the incident is to call a unique error handling procedure, the effect of which depends on the calling process and on the final system state, but not on the path followed to reach this final state. This policy results in the following error handling procedure :

- if the incident occurs in the monitor, a message is sent to the operator (as described in 2.1),

- if the incident occurs in some process *p* of a user *u*, this process is forcibly blocked and enters the queue of a special semaphore *error(u)* ; the princeps process of user *u* takes control,

- if the incident occurs in the princeps process itself, then an error indicator is set and the process is not interrupted : the reaction to the incident should be determined by its procedure.

The error-handling procedure is as follows :
`procedure react to incident;`

`begin` {let p be the running process}

`if p ∈ monitor then`
bastringue ("System error n° j")

`else` {p ∈ user u}

`begin` {control to princeps process of user u}

`if p ≠ princeps (u) then`

`begin`
put p in the queue of semaphore error (u) ;
activate princeps (u)

`end`

`else`

`begin`
set error indicator ;
return {end of primitive or trap routine}

`end`

`end`

`end;`

This scheme is described in more detail in [6].

This error-handling method was the origin of several crashes which all
appeared as a progressive blocking of the user processes.

2.22 - Error manifestation and explanation -

1) ¤ First error. The above scheme does not take into account the
path followed by a process before the incident is detected. This proved
to be insufficient to treat incidents in the system primitives. These
primitives have two possible forms, imposed by data accessing considera-
tions. A simple primitive uses only resident data, and is execu-
ted with physical addressing. A complex primitive uses in addition some
monitor data accessible in the virtual memory of the calling user. The
call of such a primitive involves the execution of a reentrant procedure,
in slave mode, in the user's virtual memory ; access to shared monitor
data has to be protected by critical sections. A complex primitive may
call one or more simple primitives ; the converse is not true.

Thus the procedure *react to incident* may be entered by one
of the following paths (figure 3).

1 : trap in a user process.

2 : incident in a simple primitive called by a user process.

3 : incident in a complex primitive called by a user process.

4 : incident in a simple primitive called by a complex primitive.

5 : trap in a complex primitive.

<figure><img src="image_2.png" /><figcaption>**Figure 3** : Paths leading to the procedure *react to incident*
(the arrows indicate the paths of control)</figcaption></figure>
This disregard of the path has catastrophic consequences when the error occurs in a complex primitive inside a critical section. The user process is blocked in this section and the princeps process cannot gain access to the shared data protected by this critical section. If the mutual exclusion applies only to the processes of a single user, this user only is in error; but if the critical section is a global one, the whole system eventually becomes blocked.

Another type of crash, due to an incorrect restoring of the program status word, occurred after an error in a complex primitive : the princeps process of user *u* may alter the instruction counter of the faulty process, while it is blocked, and then activate it by $V(\text{error}(u))$. Such operations are legal and are used for debugging, but they may result in reactivating the blocked process outside the complex primitive it was executing, with the capabilities which were given to it only for the execution of this primitive.

2) - Consequence of parallel process execution within a user. While it executes a reentrant procedure in virtual memory, a complex primitive may be interrupted. Since all processes of a user share a common virtual memory, they are not mutually protected. As a consequence, while a process executes a complex primitive, other processes of the same user may access monitor data coupled in the virtual memory. Since the protection hardware does not allow for distinct access rights to different processes in virtual memory, the following solution is used : no parallel process execution may take place within a given user *u* while one of its processes is executing a complex primitive. Processes of user *u* (other than calling process itself) are blocked by a semaphore *stop* (*u*) during the execution of the complex primitive and reactivated at the end of this primitive.

Two procedures are used :
procedure suspend parallelism (u : user) ;

begin {u is the calling user}

put all active processes of user u, except the calling process
in the queue of semaphore stop(u)

end ;

procedure restore parallelism (u : user) ;

begin {u is the calling user}

activate all processes blocked by stop(u)

end ;

The disregard of the path had some effects on this
scheme : when the interruptible phase of a complex primitive contains a
call to a simple primitive, an error in this latter causes the procedure
to be called and the princeps process to be activated (path nr 4 in
figure 3). But the other processes of the calling user u, which are bloc-
ked by stop(u) will remain blocked forever. The same situation occurs if
a process is trapped in the interruptible phase of a complex primitive.
The error may block only the processes of a single user ; but, again, if
the error occurs inside a global critical section, the whole system even-
tually comes to a halt.

3) - *Corrections of the first error.* In order to obviate the effects of this disguised form of *goto* (the procedure *react to incident* is called without return), the following modifications were made :

a) - enumerate the potential causes of error (trap for unexisting
address's, uncoupled page, ...) within a global critical section, and elimi-
nate such causes by a parameter check before critical section entry.

b) - include in the procedure *react to incident* a call of the procedure *restore parallelism*. This decision was motivated by the following piece of reasoning : if *react to incident* is called while parallelism is suspended, the situation before the complex call is restored ; if not, the action is empty.
4) - *Second error*. The procedure *react to incident* may have two reactions depending on whether the faulty process is a princeps process or not. The modifications mentioned above applied to both cases. This has no consequences as long as the princeps process of a user is in mutual exclusion with other processes of this user, which ensures the protection of monitor data. Because of this mutual exclusion, stopping and restoring parallel execution are empty actions when executed by a princeps process. When the input-output operations were implemented, there was a need for parallel processes (I/O handlers) having access to system catalogs. These processes received the same status as a princeps process. This resulted in the following error, in the case of two processes, *print1* and *print2*, in charge of the two printers on the site: process *print1* blocks *print2* by *suspend parallelism* at the entry of a complex primitive, and then causes an incident in the virtual part of this primitive. The handling of this incident activates *print2*, which may then enter the virtual part of the complex primitive. But *print1* is still engaged in this same section of the primitive since it was considered as a princeps by the procedure *react to incident*.

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

process states : — active, ... blocked

/// : region of "impossible parallelism" (no mutual exclusion to monitor data)

<caption>**Figure 4 :** Violation of an assertion after a system modification</caption>
This error may occur only if *print1* and *print2* call a complex primitive at very close intervals of time. Since the probability of such an occurrence is very small, the error went undetected for a long time.

One might point out that the initial error was to allow an incident to occur in a monitor process such as *print1*. Actually, the incident was due to an attempt to open a file already open, which in this case invoked the procedure *react to incident* and the restoration of parallel execution, while this attempt should have been regarded as illegal.

5) - *Third error*. The eradication of errors in system primitives was still complicated by the following fact : a superficial analysis seemed to show that the semaphores *stop* and *error* were used in disjoint cases for a given user ; therefore it was decided to use a single semaphore per user for both functions. This resulted in a series of system crashes, which could eventually be explained as follows :

a) - an incident occurs during the execution of a process *q* of user *u*. Therefore *q* is blocked by *error(u)*.

b) - the princeps process of user *u* is activated. It executes a debugging program to find out the cause of the incident. This program involves a call for a complex primitive.

c) - at the exit of the virtual part of this primitive, all processes blocked by *error(u)* (including process *q*) are activated

d) - as *princeps(u)* is still active, a system assertion is now violated (i.e. mutual exclusion between *princeps(u)* and other processes of user *u*). An error is now latent.

e) - the chances for this error to become manifest are still small : a frequent consequence of the incident is the eventual destruction of *q* by *princeps(u)*. But if *q* calls a complex primitive, it may now cause an unexpected incident, since the system is in an "impossible" state. If such an incident occurs in a global critical section, a system crash follows.
## 2.23 - The error-handling mechanism criticized -

A somewhat idealized description of the algorithms has been given : it does not provide a complete picture of the complexity of the mechanisms and the difficulties encountered for tracing the errors. Nevertheless, our analysis has emphasized some potential sources of trouble :

1) **Unwanted change of environment.** By "environment of a process" we mean the set of all objects (variables, procedures, ...) to which this process may gain access at a given point of its execution, together with the corresponding access rights. In the simple case of a single process executing, for example, an ALGOL program, the environment is the set of objects designated by the identifiers known at a given step of the execution. Changes of environment occur at every entry or exit of a block or a procedure. Exit may be accomplished in the normal way (end of block or procedure) or by a *goto* statement. The dangers of this construct in sequential programs have been repeatedly pointed out since [2]. But in an operating system which involves a number of parallel processes, there are many ways for environment switching. Even if interrupts are replaced by semaphore operation, (following the suggestions in [12]), the effects of such devices as supervisor calls, traps, and instructions which modify "program status words" are quite similar to those of a *goto* statement and should be handled with the same care. These mechanisms are even more harmful in that they often appear to the programmer as innocuous procedure calls, or are even completely transparent (as is the case with traps). It would seem advisable for the systems programmer to limit himself to the use of constructs really equivalent to procedure calls, i.e. including a preservation and restoration of the initial environment.

2) **Incident handling.** It seems worth noting that the errors analyzed in 2.22 originated in the handling of some incident. This operation always involves an environment switching ; but the initial environment cannot be restored without care, since, by definition, the process is not able to continue in that environment.
In conclusion, one can find two design errors in the scheme described in 2.21: an overcentralization, resulting from an underestimation of environment switching problems, and a poor analysis of potential incident causes. The process of eliminating incident causes by enumeration proved to be inadequate (e.g. in the case of the "impossible" error). It would have been wiser to let each incident occur and then take appropriate action. Lastly, the situation was aggravated by unwanted connections between independent processes (by the suspension of parallel execution and the confusion between error and stop).

## 2.3 - A hardware failure -

The crash which will be analyzed now originated in the failure of a hardware protection mechanism. The error was more difficult to locate in that it was the first and only one which affected this hardware which we had trusted entirely until then. A further difficulty was the random propagation of the error over the users of the system.

### 2.31 - The page on demand mechanism -

To avoid system overload and thrashing, memory pages are allocated only to a subset ("current" users) of the users which request them; no memory is allocated to the rest of these users ("ready" users).

Ready users are selected to become current according to the number of available frames and to the estimated requests. No user may remain in the current state for an indefinite time: at the end of a maximum residence time, it transits back to the ready state and all its memory frames are returned to the common pool.

Page frames are allocated one by one on demand to current users. While a page requested by a user is transferred to memory, the user loses the CPU and is put in the "page wait" state; at the end of the transfer, the user is a candidate for the CPU and becomes "eligible"; the CPU is allocated to the eligible users in a round-robin fashion. The user to which the CPU is currently allocated is in the "running" state.
<figure><img src="image_4.png" /><figcaption>a) Resource requests</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>b) Substates of the current state</figcaption></figure>

**Figure 5 : Allocation states of a user.**

The monitor is in charge of the mapping between memory pages and frames ;
it also guarantees the mutual protection between users, which have no
direct knowledge of memory frames.

The state of the virtual memory of a user *u* is represented
by a Virtual Page Table (VPT(*u*, *V*)). For every virtual page *V*, an entry
in this table contains the address of the associated page frame (FRAME (*V*)
and an access lock bit *I*(*V*) (*I*=0 : unlocked, *I*=1 = locked). When the CPU
is allocated to a user, the contents of its VPT is loaded in the memory
map and is used by the hardware address translation and protection mecha-
nism, which allows a given virtual page to be accessed in any page frame.
*I*(*V*) = 1 indicates that a virtual page *V* is not present in physical memory.
Any reference to that page triggers a trap which is interpreted as a page
fault.

Consider for instance an instruction such as *MTW*, *A* *B*. Its
effect may be described as :

type increment = -8 ... 7 ;

integer = -2^31 .. (2^31 - 1) ;

procedure MTW (A : increment; B : integer) ;

begin B := B + A end ;
If the page frame containing *B* is locked, the instruction is not executed (i.e. neither *B* nor the instruction counter are modified), and the executing process is trapped for page fault.

## 2.32 - Description of the failure -

After some modifications in the machine configuration at the IRIA site, a malfunction appeared in the *MTW* instruction (and this instruction only), which took the following form (figure 6). Let *V* be the virtual page containing the word *B*. If $I(V) = 1$ (*V* is locked), a page fault trap occurs and the instruction counter is not modified, as in the normal case, but the incrementing operation $B := B + A$ is nevertheless executed in the page frame which is currently associated to *V* in the memory map.

Then two cases may occur :

1) if page *V* is in central memory, there is no trap and the *MTW* instruction operates correctly

2) if page *V* is not in central memory, then the value of *FRAME(V)* is the address *Q* of some page frame, because there is no way to represent an undefined value in the memory map (256 distinct values for 256 frames). Therefore the contents of this frame *Q* is modified. (fig. 6 a). After the page fault trap, a frame *P* is allocated to the user, page *V* is loaded in this frame (*FRAME(V) = P*, *I(V) = 0*), and the execution of *MTW* modifies correctly the contents of *P* when executed. (fig. 6 b).
memory map

Physical memory

Memory map

Physical memory

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

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

a) - *Before* trap (abnormal effet)

b) - *After* trap (normal effet)

**Figure 6** : Faulty operation of the instruction MTW, 1B ($B = 512 * V + D$).

The frame *Q* which was incorrectly modified contains a virtual page, which may belong to a different user from the running user. The error remains latent until this user makes use of the modified information, if it ever does. The manifestation of the error may vary between two executions of the same program, since it may depend on the whole history of the system since it was started. Thus the fault was observed as a random error and remained undetected for a long time.
## 2.33 - Tracing the fault -

The error was finally located by taking advantage of a special case of operation of the core allocator. When a user leaves the current state, all its virtual pages are locked. If the user still needs CPU time, it enters the ready state queue. If it returns soon enough to the current state, some of its virtual pages may still be present in memory frames; when access is made to such a page, a page fault trap occurs, the ready frame is allocated to the user, and no information is transferred from the drum. This mode of allocation becomes systematic when a single user is present in the system and the available core store is large enough to hold all its program and data.

In this case, the error appears consistently in the running user's program, and $MTW, AB$ has the effect of $B := B + 2A$ instead of $B := B + A$. The operation $B := B + A$ is executed once at page fault time and once at allocation time. (with the notations of figure 6, frame *P* is identical to frame *Q*). Thus the failure was detected by a program (the loader) which worked correctly before the hardware modification; in this program, a counter *C* is initialized to zero and the instruction $MTW, 1C$ is executed *N* times; these *N* operations are scattered throughout all program execution, which allowed the user to run several times through the current-ready cycle. The final value of *C*, at the end of the program, was greater than the known value of *N*.

## 2.34 - Error correction -

To mark the absence of a page *V* it is unsafe to rely only on $I(V) = 1$; one should also give a "nil" value to *FRAME(V)*. Since this is not feasible, a similar effect may be obtained by using the address of a frame which is protected from writing by the lock-key mechanism. Then the error in the page fault handling would have been immediately detected, provided the lock-key mechanism was itself in working order.
# 3 - CONCLUSION : A TENTATIVE CLASSIFICATION OF OPERATING SYSTEM ERRORS -

We will attempt here to isolate and classify some of the more characteristic errors in operating systems. Such a classification is not intended to be complete . In the more general area of programming errors, some elements for a classification can be found in [1]. Our analysis allows us to classify system errors in two distinct classes : synchronization errors and environment errors.

## 3.1 - Synchronization errors

### 1) - Mutual exclusion errors.

Mutual exclusion constraints are a direct consequence of parallel execution of processes. Several types of error are related to mutual exclusion :

- nested critical sections : if the order of nesting is not always the same, deadlock may occur. This risk may be hidden by the multiplicity of mutual exclusion mechanisms within a system (interrupt masking, semaphores, test and set ...)

- multiple exits from critical sections : the mutual exclusion should be suspended at each exit. There is a risk of error if the multiplicity of exit points is hidden (procedure calls, traps ... within a critical section).

The information that a process is inside a critical section should be part of the state vector of this process.

### 2) - Determinacy errors.

A synchronizing mechanism is non-determinate when its validity relies on some implicit or explicit hypothesis of the relative speed of execution of the processes involved. Correctness proofs are usually much harder to obtain for such a scheme. "Memoryless events" are non-determinate mechanisms; hence, they are potential courses of errors, and one should try to use determinate mechanisms instead. In that respect, replacing interrupts
by V operations [12] allows for a better understanding of their action. In the
example given in 2.2, the procedure *restore parallelism* introduced non-
determinacy in the synchronizing mechanism.

3.2 - *Environment errors*

Two types of relations between a process and its environment
are especially error prone : error handling and access to information.

1) - *Errors handling errors.*

Error handling specification should include the analysis of
the possible causes of error and the definition of the reactions to the
different error types. If this analysis skips a certain class of errors,
these errors will be detected only after some propagation time, and their
initial cause will be difficult to trace.

It seems logically advisable to handle an error in the
environment where it was produced, because :

a) the necessary information is available in this very environment

b) an environment switching (without return) may have disastrous consequences.

This type of solution is proposed in [8], assuming a hierachi-
cally structured system : any error is detected by a trap-like device and
reflected to the level where the trap was triggered (this level may itself
transmit the error upwards). In any case, one must consider that the hand-
ling of an error may temporarily extend the capability of the faulty
process. On should also be careful that the handling of an error does
not leave the system in an "impossible" state (i.e. a state that cannot
be reached according to the system specifications), which may be the
source of further errors. As a consequence, error analysis is an important
task in the specifications of a system, which should not be restricted to
"normal" cases.
## 2) - Information accessing errors.

A frequent error occurs when a process has access to unauthorized information, or if it has access to authorized information with an incorrect access right. This error may stem either from an incorrect environment specification or from a faulty check at execution time. Two points, which are often neglected seem to be worth mentioning :

a) When the lifetime of some object is shorter than that of accessing processes, care should be taken that access to the object becomes actually impossible at the end of its lifetime. If the addressing mechanism does not allow for the prevention of access to the memory location of a "dead" object, these locations should be given a "nil" contents. Neglect of this precaution is often justified by reasoning founded on "impossible" system states ; such reasoning may prove wrong when an error occurs or may become wrong if the system is modified.

b) For efficiency or security reasons, system information is usually highly redundant. Thus a given object may be reached by a number of different access paths. In such a case, it is advisable to define a standard access path ; if one does not, one has to prove in all cases (including errors) the equivalence of all access paths, and make sure that this equivalence is preserved by any modification of the system.
Acknowledgments

The authors wish to express their appreciation to the other members of the group which designed and implemented the ESOPE system : C. BETOURNE, J. FERRIE and J. MOSSIERE, for their important contribution to the present work.

REFERENCES

[1] - BETOURNE C., BOULENGER J., FERRIE J., KAISER C., KRAKOWIAK S., MOSSIERE J.
Process management and resource sharing in the multiaccess system ESOPE, CACM 13, 12 (1970)

[2] - DIJKSTRA E.W.
*Goto* statements considered harmful, letter to the Editor, CACM 11,3 (1968)

[3] - FLOYD R.W.
Assigning meanings to programs, Proc. Symp. Appl. Math., Amer. Math. Soc., Vol.19 (1967)

[4] - HENDERSON P., SNOWDON R.,
An experiment in structured programming, BIT 12, 1 (1972)

[5] - HOARE C.A.R.
Towards a theory of parallel programming, in *Operating Systems Techniques*, (Hoare & Perrott, editors), Academic Press (1972)

[6] - KAISER C.
Conception et réalisation de systèmes à accès multiples : gestion du parallélisme.
*Thèse d'Etat*, Paris (1973) (French)

[7] - NEEDHAM R.M.
Handling difficult faults in operating systems, Third ACM Symposium on Operating Systems Principles, Stanford (1971)

[8] - PARNAS D. L.
Response to detected errors in well-structured programs, Carnegie-Mellon University (1972)

[9] - PARNAS D. L.
A technique for software module specification with examples, CACM 15,5 (1972).

[10] - PYLE I.C., Mc LATCHIE R.C.F., CRANDAGE B.
A second-order bug with delayed effect, Software-Practice & Experience 1,3 (1972)

[11] - SCHWARTZ J.T.
An overview of bugs, in *Debugging techniques in large systems* (R. Rustin, editor), Prentice-Hall (1971)
[12] - WIRTH N.
On multiprogramming, machine coding, and computer organization,
CACM 12,9 (1969)

[13] - WIRTH N.
Systematic programming, an introduction,
Prentice Hall (1973)

[14] - WULF W., SHAW M.
Global variables considered harmful,
ACM SIGPLAN Notices (feb. 1973)