See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/220800268

A Multiprocessor Operating System Simulator.

Conference Paper · January 1988

Source: DBLP

CITATIONS READS

11 191

2 authors, including:

Roy Campbell
University of Illinois Urbana-Champaign
636 PUBLICATIONS 18,257 CITATIONS

SEE PROFILE

All content following this page was uploaded by Roy Campbell on 01 September 2014.

The user has requested enhancement of the downloaded file.

Report No. UIUCDCS-R-88-1460 UILU-ENG--88-1766

TAPESTRY Pr/nc/pa//nves_iga£ors Roy Campbell

Technical Repo_ No. TTR8S-5 and Daniel Reed

A Multiprocessor Operating System Simulator

Gary M. Johnston
Roy H. Campbell

September 26, 1988

TAPESTRY

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN • URBAN.k, ILLINOIS 61801-298?
Contents

1 Introduction 1

2 Choices Overview 2
2.1 Why a Class Hierarchy? ............................. 3
2.2 The Choices Class Hierarchy ........................... 3
2.2.1 Processes and ProcessCont_iners .................... 4
2.2.2 Exceptions ................................. 5
2.2.3 Semaphores ................................ 5

3 Implementation 6

3.1 Microschedulin 8 .................................. 6

3.2 Class Hierarchies and Layering .......................... 7
3.3 Class CPU ..................................... 7
3.4 CPUTimer ..................................... 9
3.5 CPUManager Duties. .............................. 9
3.6 Processes and ProcessTasks ........................... 9
3.7 Exceptions ..................................... 11
3.8 Semaphores .................................... 11

4 Experience 12
4.1 Multiple Concurrent Producers and Consumers ................ 12
4.2 Real Memory Management ............................ 13
4.3 Virtual Memory Management .......................... 14

5 Conclusion 15

References 17
 A Multiprocessor Operating System Simulator*

Gary M. Johnston
Roy H. Campbell

September 26, 1988

Abstract

This paper describes a multiprocessor operating system simulator that was devel-
oped by the authors in the Fall semester of 1987. The sinmlator was built in response
to the need to provide students with an en_t in which to build and test operat-
Lug system concepts as part of the coursework of a third-year undergraduate operating
systems course.
Written in C++ [I], the simn]ator uses the co-routine style t_sk package [2] that
is distributed with the AT&T C ++ Translat_ to provide a hierarchy of classes that
represents a broad range of operating system software and hardware components. The
class hierarchy closely follows that of the Cho/c_ [3] family of operating systems for
loosely- and tightly-coupled nmltiprocessors. During an operating system course, these
classes are refined and specialized by students in homework assignments to facilitate
experimentation with different aspects of operating system design and policy decisions.
The current implementation runs on the IBM RT PC I under 4.3bsd UNIX. 2

1 Introduction

The principles of low-level operating system design have implications that are difllcult to
appreciate without the practical experience that is gained fzom programming multiprocessor
systems. However, it is dif_cult to provide university students with such a learning expe-
rience. Hardware resources are too expensive to allow each student single user access to a
multiprocessor workstation. Low level parallel processing systems software, as an instruc-
tional resource, is usually poorly organized and dimcult to understand. In addition, there is
1Rtle support for the debug_ug and testing of low-level systems programs on multiproces-
sors. This paper describes a multiprocessor operat/ng system simulator we have constructed

•This work was supported in part by NSF grant CCR-8-8-09479 and CISE-I-5-30035, by NASA grant
NSG1471, and by AT&T ISEP.
IRT PC is s trademstk of IBM.
2UNIX is a trademark of AT&T.
in C++to overcometheseproblems. The current implementation is usedin the department's
instructional laboratory, running on 30 IBM RT PCs which were donated to the university
by IBM Corporation.
The simulator is modeled on the Choices multiprocessor operating system family [3] [4]
[5]. It includes classes to model both the processes, schedulers, and exception handling
mechanisms of Choices and the processors, I/O devices, traps, interrupts, time_, and other
hardware components of a typical multiprocessor system like the Encore Multimax. s
The simulator was designed for a third year undergraduate course on operating systems
that is taught in the Department of Computer Science at the University of Illinois at Urbana-
Champaign. The goal of the course is to introduce students to the principles of operating
systems and to reinforce those principles with practical experiments and projects invoIving
the design of operating system mechanisms and policies.
Using the simulator, experimentation is conducted within the f_amework of the class hier-
archy and object-oriented programming mechanisms afforded by C++. Many of the practical
design exercises involve specializing an abstract class into a concrete class that implements
a particular policy or mechanism. Policy exercises include process scheduling, real memory
management, page replacement, and disk scheduling. Mechanism exercises include syn-
chronization primitives, I/O queues, paging mechanisms, exception handling schemes, and
message passing primitives.
The operating system course benefits from the use of C ++ in severs] Ways. The language
allows an efficient simulation of the operating system while providing a level of type checking
that aids debugging of student programs. Debugging and tracing aids are built into the base
classes of the simulator and help the students implement their designs. The class hierarchy
organizes the components of the simulation into similar algorithms and data structures. This
organization is a useful aid to the student that is learning the system. The class hierarchy
enables fafrly large simulations of an operating system to be built incrementally by the
students.
The remainder of this paper comdsts of four major sections. Section 2 describes the model
of the Choices operating system and class hierarchy supported by the simulator. Section 3
discusses the design and implementation of the simulator. Section 4 describes how the
simulator was used, including descriptions of some of the projects. Finally, we summarize
our experience with the simulator in section 5.

2 Choices Overview

Choices-is a family of operating systems built using a class hierarchical object-oriented

approach to systems design and programming. A Choices operating system has been imple-
mented on an Encore Multimax and is being ported to an Intel iPSC/2' hypercube [6]. It
demonstrates that object-oriented design techniques are both appropriate and beneficial for

SMultimax is a tzademark of Encore Computer Corporation

4iPSC is a trademark of Intel Corporation.

2
 Choices Simulator Classes
Class Methods
Object
TProcess m

TTIdieProcess
TProcessContalner add remove -
TTCPU add remove interrupt trap
l"TFIFOQueue add reDIO_e --

TTProcessQueue add reT/_OUe --

TException raise await handle

TTInterruptException T T handle D

TTTResetException T T .handle
TTTTimerException T T handle
TTSoflwareException ra/se T handle m

TTTIdleException T T handle
TTTTerminateException T T hand_
TTTSemaphoreExceptlon T T handze
TSemaphore P V m

Table 1: Choices Simulstor Classes.

writing complete operating systems for multiprocessors and networks of multiprocessors.

2.1 Why a Class Hierarchy?

In Choices, the class hierarchy represents the major components of a family of operating
system designs. Classes represent the interfaces and implementations of processes, virtual
memory, context switching, exception handling, scheduling, and synchronization. They are
also used to provide a hardware/software interface by encapsulating ma_aine dependent
algorithms and data structures for the hardware entities such as the CPUs, MMUs, interval
timers, disks, and networks.
In our experience, an operating system designer may select, refine, and combine classes
from the c/ass hierarchy in order to build a custom operating system for a particular hardware
environment or a particular application. The resulting operating system is also more easily
modified or extended than one based on more =traditional" approa_2hes. The ease of module
substitution greatly _cilitates prototyping, a great benefit to practical operating systems
research and experimentation.
This section presents a brief overview of the Choices project and of the Choices class
hierarchy as implemented by the simulator. For more detail, see [3] [4] [5].

2.2 The Choices Class Hierarchy

 Legend

Symbol Meaning
method Definition of method.
method Redefinition of method.
T Subclass or inherited method.
- Undefined method.

Table 2: Class Table Legend.

The major classes of Choices as modeled by the simulator are shown in table 1. The table
is explained by the legend shown in table 2. Class Object is the root of the hierarchy. Sub-
classes are used to provide abstract interfaces and concrete implementations for operating
system mechanisms. They are used to encapsulate data, policies, and alternative implemen-
tations or versions. Subclasses of Object define the basic entities within an operating system.
Subclasses of these classes add and/or redefine methods in order to augment, specialize, or
provide concrete implementations of these classes.

2.2.1 Processes and ProcessContalners

Class Process provides the basic unit of execution within Choices. Process management in the
operating system is achieved by moving Processes between ProcessContainers. Subclasses
of ProcessContainers represent processors and schedulers.
An IdleProcess is associated with each simulated processor. It is executed only when
there are no other Processes available. Each IdleProcess periodically checks the scheduler
and signals the processor when it detects that there a_e Processes which could be executed.
Other Processes represent %ser-level" processes. The behavior is redefined by the sim-
ulation designer as necessary. Usually user-level Processes are designed to mimic some type
of program behavior in order to provide a "job load" for the simulation.
The CPU subclass of Pl_cessContainer represents processors. Adding a Process to a
CPU specifies that a particular process should be executed by a particular processor of the
multiprocessor system; that is, the Process is dispatched on the CPU. Removing a Process
from a CPU idles the processor, which represents preemption of the Process.
The ProcessContainer class defines methods to add 0 and remo_e 0 Processes. These
methods are specialized by the subclasses CPU, FIFOQueue, and ProcessQueue. An instance
of a CPU is active (the active component is the processor). However, a FIFOQueue and
ProcessQueue may contain many Processes although they are passive. The simulator itself
runs on a single UNIX process, and the classes of Choices it uses are specialized to emulate
a parallel processor. For example a CPU is implemented by tasks in order to emulate the
functions of a processor.
Facilities for scheduling and blocking Processes are provided by classes PIFOQueue and
ProcessQuene. A FIFOQuene acts as a simple afirst-in-first-out" queue of Processes, while
a ProcessQueue is associated with a times]ice quantum. When a Process is removed from a

4
ProcessQueue, the timeslice quantum field of the Process is set to the quantum associated
with the ProcessQueue. This field is used by the CPU to determine the maximum amount
of time the Process should be allowed to execute before being preempted. The quantum
associated with a ProcessQuene may be any value desired, supporting timeslicin 8. The
default quantum is a value which means "run-to-completion." These classes may be refined
by other subclasses in order to implement a wide range of policies. FIFOQueues can act
as queues of blocked Processes. Other subclasses of ProcessContainer can be defined and
substituted to provide whatever sorts of scheduling disciplines the system designer desires.

2.2.2 Exceptions

In Choices, most movement of Processes between ProcessContainers is done by Ezception

handlers. In addition, the only way in which an executing Process ca_ relinquish its CPU
is by the raising of an Exception. R_inqulshing the CPU may be a vohntaxy, synchronous
action performed by the Process (i.e., a "trap") or an involuntary, _synchronous action
caused by an external event (i.e., an "interrupt").
Class Exception itself is an abstract class in that no direct instances of class Exception
ever exist. Rather, it provides a base class from which subclasses may be derived in order
to provide specialized behavior. An Exception provides the methods handle(), ea/se0, and
await(). The raising of an Exception causes its handler to be invoked (with the possible
side-effect of unblockin 8 one or more Processes awaiting the Exception).
There are two abstract subclasses of Exception: IntereuptEzception and SoftwareEz-
ception, each of which is further subclassed. An InterruptException is associated with an
interrupt vector which, when delivered to a CPU, causes the associated InterruptException p
to be raised. Thus, InterruptExceptious occur asynchronously with the execution of Pro-
cesses. A SoftwsreException is not associated with an interrupt vector. Instead, it is raised
directly by an executing Process sad acts like & "trap."
InterruptException subclasses include Reaet.Ezception and TimerEzception. Each CPU
is associated with an instance of each of these. A ResetException provides the actious to be
taken when the CPU is "reset". The TimerException handles the expiration of the per-CPU
interval timer.
SoftwsreException subclasses include IdleEzception, 8emaphoreEzception, and Te_rnina-
teEzception. An IdleException is a softw_e event that signifies that Processes ate available
to the CPU for execution. An IdleException is raised by a CPU's IdleProcess when it de-
tects that the CPU's scheduler is non-empty. A TerminateException is raised- to remove
the Process from the CPU and delete it. A SemaphoreException is raised when a Process
attempts to acquire a semaphore which is unavailable. The SemaphoreException removes
the Process from the CPU and adds it to the' queue of Processes waiting for the semaphore.

2.2.$ Semaphores

A Semaphore is the basic synchronization primitive within the simulator. It defines the
faxnilisr P0 and V 0 operations [7] for acquiring and releasing the Semaphore.

5
8 Implementation

The simulator provides a class hierarchy from which simulated multiprocessor operating
systems can be designed and studied, followin 8 the Choices model as closely as possible.
This section discusses the implementation of the simulator under 4.3bad UNIX.

3.1 Microscheduling
Like Choices itself, the simulator is written in C ++. In order to provide the required simu-
lated concurrency, the simulator was written using the %oroutine-style task package" which
accompanies the AT&T C ++ Translator [2].
The task package provides user-level coroutine-style tasks, but does not provide for non-
voluntary relinquishing of the virtual processor. That is, an executing task doesnot block
unless it explicitly calls a task package procedure (for example, de/ay 0 or sleep()). While this
is very useful for system simulation, it is inadequate to emulate a multiprocessor program-
ruing environment realistically. A simulated user-level task executing an "infinite loop" will
prevent all the other simulated tasks from proceeding. This simple implementation of tasks
is inadequate to emulate interrupts or preemptive scheduling policies such as round-robin
time-slicing, multi-level feedback queues, or "shortest job first." In addition, we wanted to
simulate the nondeterminancy that must be dealt with by programs using or implementing
synchronization prim/fives and executing within a mnltiproceuor environment. Therefore,
the basic task package was augmented with a "microschednling" sub-system that time-slices
between executable tasks preemptively. Note that this involved only _ditiona to the task
package. The task package itself was not modified. D
The microschedufing mechamsm implements a time-sliced round-robin mechanism un-
derneath the basic task package. This mechanism gives each executable (i.e., non-blocked)
task a "microquantum" equal to one virtual clock tick. At the end of the microquantum, the
task is delayed for one clock tick, and the next executable task is dispatched. In this manner,
executable tasks are preemptively time-multiplexed on the underlying UNIX process.
The 4.3bed UNIX interval timer and signal mechanisms were used to implement the actual
preemption of tasks. At simulator initialization time, an interval timer is armed to deliver a
signal to the underlying UNIX process each time it expires. When the signal is received, the
signal handler executes in the context of the current task. The signal handler executes a call
to the task package to delay the current task by one virtual clock tick, thus relinquishing the
underlying UNIX process to execute another runnable task. If there are no more immediately
runnable tasks, the virtual clock is incremented (by the task system), allowing tasks which
had delayed themselves during the previous clock tick to become "ready" again. When a task
that had previously delayed itself via the signal handler becomes ready again, its invocation
of the signal handier returns, thus restoring that task's context to that which was in effect
when the signal was received. The task then continues execution at the point where it
was preempted. Thus, the microscheduling effectively implements a round-robin scheduling
policy underneath the existing task package.
 The basic task package requires no explicit shared resource access control internally
because there is no preemption. Provided that critical sections do not delay, they do not need
synchronization because, without preemption, races cannot occur. Once microscheduling has
been added, however, this is no longer the case. Within the Choices classes, mutual exclusion
primitives are used in order to ensure that critical sections are protected. In order to support
these primitives in the simulator, instances of two low-level task classes are distinguished by
the microscheduling mechanism and are not preempted, s Therefore, these classes' methods
do not need to use explicit mutual exclusion primRives.

3.2 Class Hierarchies and Layering

The simulator is organized into two major class hierarchies: the augmented task package
class hierarchy (includin 8 the microscheduling mechanism) and the Choices class hierarchy
itself.

The basic task package provides the abstraction of a task, which is the primitive unit of
execution within a task package application. This hierarchy has been augmented by creating
subclasses of the task class in order to provide more specialized behavior as needed by the
rest of the simulator. These classes are CPUManager, CPUTimer, and ProcessTo.sk. A
CPUManager and a CPUTimer are associated with each simulated CPU. The CPUManager
simulates the activity of the CPU. This includes interrupt vector processing, trap process-
ing, and exception handling actions. The CPUTimer simulates a per-CPU interval timer to
provide support for preemptive time-slicin 8 of shnulated Processes. A ProcessTask is asso-
ciated with each simulated Process. The CPUManaser associated with a CPU allows the
ProcessTask to execute (on behalf of the simulated Process) when _he Process is dispatched
on that CPU.

The Choices simulator class hierarchy provides the classes that form the basis for oper-
ating system simulations: Process, ProcessContainer, CPU, Exception (and its subclasses),
etc. Table 1 shows this hierarchy. Fly, are 1 shows the arrangement in terms of layers.

3.3 Class CPU

A CPU contains a number of objects in addition to its CPl)Manager and CPUTimer. Each
CPU has a current Process and an IdleProcess. The current Process is the Process currently
being executed by that CPU. Since a CPU is a ProcessContainer, the current Process of a
CPU references the Process which the CPU contains (if any). The IdleProcess is executed
only when the CPU is otherwise idle (e.g., when there are fewer Processes in the %ystem"
than there are CPUs6).
Next, a CPU contains a queue of pending interrupt vectors and a table that maps in-
terrupt vectors to InterrnptExceptions. Incoming interrupt vectors and SoftwareExceptions
are detected by the CPUManager which then executes the InterruptException handlers.

SThese elaues are CPUManager and CP_Timer, _ below.

enot including IdleProeesses, of course.

7
 User simulation.

Choices classes.

CPUMana_er
CPUTimer Microscheduling.
ProcessTask

Task package.

Figure 1: Conceptual Layering in the Choices Simulator.

Each CPU references a ProcessContainer that operates as the Uready queue', or scheduler.
When an executable Process is removed from the CPU, it is added to this scheduler. Also, a
Process is removed from this scheduler when the CPU requires one. For example, when an
executing Process' timeslice expires, it is removed from the CPU and added to this scheduler.
Then, another Process is removed from the scheduler and added to the CPU.
In this way, several CPUs may be associated with a pa_iculaz scheduler. There is no
reason why there can't be more thu one scheduler in the system, each associated with its
own set of CPUs. The simulation designer can change this association dynamically at any
time.
There are two groups of operations on a CPU: Uprivste" routines intended for use by
afriends_' (essentially CPUMansSers and Exception handlers) and ``public', routines intended
for use by the simulation writer.
The private routines include addO, and remove(), which are redefinitions of the super-
class ProcessContainer methods for adding/removing Processes to/from a ProcessContainer.
Adding a Process to a CPU is e_ectively a ``dispatch', of the Process, while removing a Pro-
cess from a CPU corresponds to a "preemption" of the Process.
Two other important private routines are ,emo_e Vec-_" 0 and getEzcept_n(,). These are
used by the CPUManager to remove an interrupt vector from the incoming vector queue,
and to map a vector to an InterruptException, respectively.
The public operations include the constructor and destructor, routines to get and set the
CPU's scheduler ProcessContainer, the interrupt 0 routine which is used to send an inter-
rupt to a CPU, the trap() method which is used when a SoftwareException is raised, and
the setEzception 0 routine which is used to associate an interrupt vector with an Interrupt-
Exception.
When a CPU is created it is empty, i.e., it contains no Process. The Exception table
(which maps interrupt vectors to InterruptExceptions) contains two default mappings: a
ResetException is associated with the ResetVector, and a TimerException is associated
with the TimerVector.

8
 In the implementation, the CPU itself is passive; it is the CPUManager and the CPU-
Timer which are the active entities, controllin 8 the activities of the CPU. These are discussed
next.

3.4 CPUTimer

A CPU's CPUTimer implements timed preemption of Processes. A CPUTimer is a task that

sends the TimerVector to the CPU when the time interval expires, unless the CPUTimer is
stopped first. If the CPUTimer is stopped before it expires, then the residual time can be
retrieved.
In general, when a Process that specifies a timeslice quantum is dispatched, the CPU-
Manager sets the CPUTimer to expire at the appropriate time. If the CPUTimer expires,
the TimerVector interrupt triggers the execution of the associated InterruptException's han-
dler (usually a TimerException). If the Process is preempted for some reason other than
CPUTimer expiration, the CPUTimer is stopped and the residual is read and stored in a
field of the Process for possible use by the scheduler.

3.5 CPUManager Duties

The CPUManager handles asynchronous events in the system like interrupts as well as traps,
and invokes the Exception handlers associated with them. The CPUManager is initially
Uasleep,n and the arrival of an interrupt or trap "wakes up n the CPUManager. When a
CPU's interrupt() method is called, the vector is enquened on the CPU and its CPUManager
is awakened. When a CPU's _rap 0 method is called, the SoftwareException is saved on the
CPU, the invoking Process is stopped, and the CPUManager is awakened. The general
control loop of the CPUManager is shown in figure 2.

3.6 Processes and ProcessTasks

Each Process is implemented by a Pn0ceu Ta_k which executes when the Process is dispatched
on a CPU. Each Process conta_ins a timeslice quantum and a residual, which is used for
preemptive timeslicing. The residual field is set by the CPU when the Process is preempted.
This information is intended for use by schedulers. In addition, each Process keeps run-time
statistics.
The ProcessTask associated with a Process is the entity which is actually executed. It is
ProcessTasks that are multiplexed on the underlying UNIX process by the microscheduling
mechanism. The task methods are used by a CPUManager to start and stop the execution of
a Process' ProcessTask. In order to provide low-level critical section protection, methods are
provided to disable and re-enable the preemption of a ProcessTask by the microscheduling
mechanism.
IdleProcess is the subclass of Process that is executed by a CPU when there are no other
Processes for it to run. There is one IdleProcess associated with each CPU. The IdleProcess

9
// • CPUMam_er's work is never done...

// W_Lt for s_4-te:L-E'u_t.

sleep();

// Stop and delete the CPUTiner, if there is one, saving the residual.
int residual = O;
_1_ ( cpu->t:Lnor ts ]lULL ) {
residue= cpu->t_er->etop();
delete cpu->ttnor;
cpu->timer = ]fULL;
}

// Handle and reset the. pendAn K trap (SoftwareKxception), if theze is one.

// Otherwise, atop the cuzzent Process, if there is one.
Process • cuzTentProceee = c1_->cuzTentProcess;
i._ ( cpu->trap l= lOLL )
SoftwareExcep_ion • trap : cpu->trap;
cpu->trap = IULL;
trap->handle( _ );
} else if ( ClL_reatP_ocese I= MULL ) {
cuzTentproceee-> st op() ;
}

/1 Handle any pending interrupts (InterruptExcaptions).

vhile ( ( int vector : cpu->renoveVector() ) J: loVector ) {
// Get the COZTelpond/= K Exception.
// Call the Exception handler.
InterraptExcaption * interrupt = cpu->getException( vector );
interrupt->handle( vector, cpu );
}

// Start the CUZTant P_ocess, if there is one.

// lots: The =--t Process we etaz_ here nlKht very gel1 not be
// the sane one ee stopped.
if ( clm->cu.z.ran1:Procese In IOLL ) {
// Determine how nmch tins the Process ei].l get:
// If the cuzwant Process is the sane u before,
// it gets the rest of its times]ice (i.e., the reeidnLl).
// 0thergiee, it gets whatever its scheduler specified.
int time = (cpu->cuzTan_Procese == cuzTan_Process) ?
resides1 :
c1_- >cuz_ant Proc es s->get qmm_-mn( ) ;

// Staz_ the CPOTiner, unless the Procese is harked "zun to conpletion."

if ( t4ue I= KunToConpletton )
cpu->timer = nee CPUTiner( cpu, time );

Figure 2: Simplified CPUManager control loop.

i0
continually checksthe schedulerProcessContainerof its CPU. When it detects that this
scheduler is not empty, it raises an IdleException which causes a Process to be removed
from the scheduler and added to the CPU, suspending the IdieProcess until such time as the
CPU becomes idle again.

3.7 Exceptions

The Exception subclasses are the major means by which Processes are moved between Pro-
cessContainers in a Choices system itself and in the simulator. Each Exception subclass
provides specialized handling. There axe two subclasses of Exception, InterruptException,
and SoftwareException. Instances of subclasses of InterruptException represent hardware
interrupts. When an interrupt is delivered to a CPU, it is mapped by the CPUManager to an
InterruptException whose handler is then ca/led. Subclasses of InterruptException include:

ResetException: Associated with the ResetVector. it adds the CPU's IdleProcess to the
CPU.

TimerException: Associated with the TimerVector which is sent when the CPU's CPU-
Timer expires. It removes the current Process from the CPU and adds it to the
scheduler ProcessContainer associated with the CPU. It then removes a Process from
the scheduler and adds it to the CPU.

A SoftwareException is raised as a direct result of the execution of a Process. Software-

Exceptions are not associated with interrupt vectors; the raise method is invoked directly.
SoftwareException subclasses include:

IdleException: Raised when a CPU's IdieProcess detects that the CPU's scheduler has
become non-empty. Its handler removes the IdleProcess from the CPU, and then
removes a Process from the scheduler and adds it to the CPU.

TerminateException: Raised when the current Process on the CPU is to be terminated.

It removes and deletes the _t Process from the CPU, and then removes a Process
from the scheduler and adds it to the CPU.

SemaphoreException: Raised by a Semaphore when a PO operation detects that the

requesting Process must block (i.e., the resource is not available). It removes the
current Process from the CPU and adds it to the ProcessContainer associated with
the Semaphore. It then removes a Process from the CPU's scheduler and adds it to
the CPU.

3.8 Semaphores
Each Semaphore contains a count and a FIFOQueue ProcessContainer which holds Pro-
cesses that have been blocked attemptin 8 to acquire the Semaphore. It also references a
SemaphoreException that is raised when a Process must block.

11
 The P0 operation decrements the count. If the count then indicates that the Process
must block, a SemaphoreException is raised. The SemaphoreException removes the Process
from the CPU and adds it to the queue of blocked Processses.
The V 0 operation increments the count. If there are blocked Processes, one is removed
from the queue and added to the scheduler.

4 Experience

The resultin 8 simulator has proven to be very realistic. Several of the race conditions that
occurred as buss in the development of the real Choices operatin8 system were also en-
countered by students as they developed their own operatin 8 system components within
the simulator. Durin 8 the course, the students developed semaphores, messages, supervisor
requests, scheduling policies, real storage management, virtual storage management, disk
storage management and scheduling for the multiprocessor environment. This section dis-
cusses some of these projects and how they were implemented within the environment of the
simulator.

4.1 Multiple Concurrent Producers and Consumers

The object of this exercise was to 8ire students experience in designing systems involving
producer/consumer relationships among Processes, including deadlock detection and recov-
ery.
Initially, class Pipe had to be implemented to support a _wo-ended stream of Messages.
Methods were required to perform blocking, non-blockins, and synchronous send operations
(send_blockO, sendO, and send.._O , respectively), as well as blocking and non-blocking
receive operations (receive_b/oc]_ 0 and receive0, respectively). Each Messase essentially
consists of a strin 8 of data bytes and an identifier specifyin 8 the ultimate destination Process.
In this exercise, Processes are connected by Pipes in a ring, as shown in figure 3. Each
Process executes a loop in which it repeatediy choses one of the send or receive operations
at random, and performs this operation on one of its two Pipes. For send operations,
destinations age chosen at random. For receive operatlons, if a Message is received on a Pipe
whose destination does not specify" the receivin 8 Process, it is forwarded on the other Pipe.
Since the Processes are arranged in ring, all Messages eventually reach their destinations
(unless they are lost or cancelled).
In this situation, deadlocks can and did occur. Students implemented a centralized dead-
lock detection and recovery mechanism which consisted of a central Pipe (7ongrol information
object and an additional deadlock control Process which would periodically examine the Con-
fro1 information, discovering and breaking deadlock situations. The Pipe class was modified
to support this. Each send and receive operation on a Pipe would report its updated state
to the Control object, where it could then be used by the deadlock control Process.

12
 JProcess P oco,,I
r
s

S
%%%
J %

!
I
I
I

IP,o e-I [Process

/
I
I
I

,%
%
%
%
,%
i S

[Proc ,s
Figure 3: A Ring of Processes Connected by Pipes.

4.2 Real Memory Management

This project involved the implementation of Choices-style real memory management. Two
major classes were implemented: Rea/MemoeyObject and ReaiMemoryManager.
A RealMemoryObject represents a "sesment', or contiguous range, of memory organized
in fixed-size pages. The operations supported are read 0 and write 0. Each operation spec-
ifies an o._set into the RealMemoryObject at which the transfer is to begin, a length (in
bytes), and a destination/source buffer address. Initial reads from unwritten RealMemory-
Object locations are read as zeros. The RealMemoryObject maintains a "dirty bit" for each
page which has been written. The constructor specifies the range of addresses which the
RealMemoryObject will represent.
The other major class required for this project was a RealMemoryManager. A RealMem-
oryManager represents the physical memory of the simulated machine, so only one instance
of this class is created. The RealMemoryManage_ allocates and deallocates RealMemory-
Objects as requested by user Processes. Operations are a//ocate 0 and deallocate().
The a//ocate 0 operation specifies a number of bytes, and returns a RealMemoryObject.
The RealMemoryManager must find an unallocated range of memory that is at least as large
as the request. It then creates a RealMemoryObject to manage the range and returns it.
The deallocate() operation specifies a RealMemoryObject to be deleted. The RealMem-
oryManager deletes the RealMemoryObject, thus freeing the range of memory for possible
allocation in future allocate() requests.
RealMemoryObject and RealMemoryManager provide simnlated system services, and are

13
not supposedto be directly accessible to the user Processes (although the simulator cannot
enforce this). Therefore, the students implemented a subclass of SoftwareException called
SVCEzception. This class provides a user program interface to the system. Mechanisms for
passing argmnents into the "kernel" and for passing results back to the invoking Process
were also implemented.
Simulated user Processes were created to randomly allocate and deallocate RealMemory-
Objects, and to read and write them randomly. Statistics about memory usage, fragmen-
tation, allocation routine times, etc. were collected. The allocation algorithms commonly
known as "first fit," "best fit," and Uworst fit" were implemented and analyzed.

4.3 Virtual Memory Management

This project extended the ideas from the previous project in order to provide students with
experience in the various aspects of virtual memory management.
The idea of a RealMemoryObject was expanded to represent a Process' virtual address
space. This is encompassed by class Memo_ObjectCache. A MemoryObjectCache msin-
taius the state of each page in the viztual address space it represents. In addition to the
"dirty bit" (which was maintained by the RealMemoryObject in the previous project), the
MemoryObjectCache must maintain a "referenced bit" sad a bit indicating whether or not
the page is resident. If the page is non-nmident, the location of the page in secondary stor-
age must be stored. A MemoryObjectCa_zhe supports the same read sad write operations as
described for a RealMemoryObject, except that pages may be moved to sad from secondary
storage.
When a MemoryObjectCache xhust read or write a page that is marked non-resident, that
page must t;rst be retrieved from secondm'y storage. To facilitate this, am instance of class
PageManage, manages the physical memory of the machine and is responsible for paging to
and from secondary storage. The PageManager implements the pageFault 0 method, which
is invoked by a MemoryObjectCache when a non-resident page needs to be brought in from
secondary storage. The PageManager fetches the specified page from secondary storage and
marks it as resident.
Secondary storage is implemented with an instance of class Di6kManager. The DiskMan-
ager responds to the messages readPage 0 and writePage 0.
Various page replacement algorithms were implemented sad studied. These included
"least recently used," "not recently used," _trst in, first out," and "random." In addition,
various disk scheduling strategies were used, including allist come, ftrst served," "linear (or
unidirectional) scan," and "c£reular (bidirectional) scan." Finally, the page access patterns
of the Processes were varied in order to simulate ditt'erent degrees of temporal sad spatial
locality.

14
5 Conclusion

In this paper, we have described the use of C ++ as a high-level language for describing the
system data structures and algorithms introduced in a university undergraduate/graduate
course in operating systems. The students used a simulator programmed in C++ that emu-
lated a system based on Choices, an experimental multiprocessor operating system that we
are building at the University of Illinois. Class projects and exercises were chosen to give
students practice at systems design and programming. These projects and exercises were
written in C ++ and refuted or replaced classes in the simulator.
Most of the students in the course had programmed in C in a previous course on systems
programming and maz_ine organization. The transition to C++ was orderly. The students
found the additional type checking in C ++ an aid; however, many of the diagnostic messages
from the compiler required the students to seek help from their teaching assistants. The
debugging and tracing aids built into the simulator were found to be very useful as the
standard UNIX debugger cannot give accurate diagnostic messages in terms of the names
used in C++ programs. This is because the current C++ compiler generates C code which
is then compiled by the C compiler. A native C++ compiler would solve many of these
problems.
C ++ was proved to be an etBcient programming language for the simulator. Quite large
simulations (both in terms of size and length) could be done on a workstation during the
period of time permitted each student in the laboratory.
The use of a class hierarchical object-oriented description of an operating system was
instrumental in helping the students understand Choices. The class hierarchies organized the
common algorithms and data structures of an operating system and allowed students to infer
the properties of the simulator classes from the more abstract classes presented during lecture.
Unlike previous operating system courses that we have taught, we were able to present
multiprocessor operating system material couched in the general principles of operating
system design. The more _traditional" single processor operating system algorithms and
data structures could be presented as degenerate cases of the multiprocessor ones.
Currently, a simulator is the only practical approach to providing a large class of students
(approximately sixty) with a hands-on environment for multiprocessor operating system
design. Many of the problems that are encountered in multiprocessor operating system
design m deadlocks, races, unnecessary mutual exclusion and interrupt disabling, etc. --
were pointed out in lecture and successfully diagnosed by students during their exercises
on the simulator. In this and many other respects, the simulator provided a remarkably
accurate emulation of real multiprocessor system software development. The accuracy of
that emulation requires better diagnostic and tracing tools than we implemented in the
simulator. We believe some form of graphical visualization of the system is needed in order
to provide students with a better understanding of the utilization of resources, bottlenecks,
and communication flows. However, we do not see this as a drawback to the approach.
Rather, it points out a lack of necessary human interfaces and tools for designing complex
software. Such software tools would not only be useful in education, but they would have

15
application in the customization of Choicesfor particular applications and hardware. We
plan to incorporate such tools in the future revisionsof the simulator.

16
References

[1] Bjarne Stroustrup, The C+÷ Programming Language, Addison-Wesley Publishing Com-
pany, Reading, Massachusetts, 1986.
[2] Bjarne Stroustrup & Jonathan E. Shopiro, "A Set of C++ Classes for Co-Routine Style
Programming," Proceedings of the USENIX C-t-+ Workshop (1987).

[3] Roy Campbell, Vincent Russo & Gary Johnston, "The Design of a Multiprocessor Oper-
ating System," Proceedings m¢ the USENIX C-/-+ Workshop (1987).
[4] Vincent Russo, Gary Johnston & Roy Campbell, "Process Management and Excep-
tion Handling in Multiprocessor Operating Systems Using Object-Oriented Design Tech-
niques," O O PSLA '88 Conference Proceedings (forthcoming).

[5] Roy H. Campbell, Gary M. Johnston & Vincent F. Russo, "Choices (Class Hierarchical
Open Interface for Custom Embedded Systems)," Operating Systems Review 21(July
1987), 9-17.
[6] Roy H. Campbell & Daniel A. Reed, "Tapestry: Unifyin 8 Shared and Distributed Memory
Parallel Systems," Department of Computer Science, University of ]lUnois at Urbana-
Champaign, Technical Report No. UIUCDCS-R-88-1449, Urbana, Illinois, 1988.

[7] Edsger W. Dijkstra, "The Structure of the THE-Multiprosramming System," Communi-

cations of the ACM 11 (May 1968), 341-346.

17
 i

BIBLIOGRAPHIC DATA 1. RepoctNo. 3. Reclpient's Accession No.

SH|eT UZUCDCS-R-88-!460
4. Title a_ Subcitle 5- Repntt Date
September 1988
A Multiprocessor Operating System Simulator
6.

7. A=h=(s) 8. Performing Organizacioa Relx.

Gary M. Johnston and Roy H. Campbell No. R-88-1460

9. PetfoemmsOr|aai_cioaNameandAd_ess 10. Project/Tuk/Vork Uak No.

Department of Computer Science
1304 W. Springfield Ave. I1. Com_mct/Gtant No.
240 Digltal Computer Lab gSF CCR8-8-09479
Urbana, IL 61801 _ISE 1-5-30035
gASA NSG 1471
l_Spou_ins _gMiz_ionNamesmlAd_ess
National Science Foundation NASA Langley Research Center kT&T IL SOFT. 1-5-37388

Washington, DC 20550 Hampton, VA 23665

1&
AT&T Information Systems
Lincroft r NJ 07738
1_ S_p_me_y Nntes

16. Abstracts
This paper describes a multlprocessor operating system slmulator that was developed
by the authors in the Fall semester of 1987. The simulator was built in response
to the need to provide students with an environment in which to build and test
operating system concepts as part of the coursework of a third-year undergraduate
operating systems course.
Written in C++, the simulator uses the co-routlne style task package that is
distributed with the AT&T C++ Translator to provide a hierarchy of classes that
represents a broad range of operating system software and hardware components. The
class hierarchy closely follows that of the Choices family of operating systems
for loosely and tightly coupled multiprocessors. During an operating system course,
these classes are refined and specialized by students in homework assignments to
facilitate experimentation with different aspects of operating system design and
policy decisions. The current implementation runs on the IBM RT PC under 4.3bsd UNIX.

17. Key VorclsudD_umem A_lysis. 17_De_ti_ms

computer science education, multiprocessors, operating systems, simulators, class

hierarchies, object-orlented design.

171). Identifiers/Open-Ended Terms

17c. COSATI Field/Group

18. Availability Scacemen¢ 19.. Security Class (This 21. No. of Pages
gepoct)
unlimited UMc L_ssI_I_D 21
20. Security Clsss (This 22. Price

Ps_TN_LASSIFIED
tJIl¢OIvlM*O¢ 4OIlS*P? I
IllONId NTIS-II 110"701

View publication stats