Discrete Simulations
Volume Number: 6
Issue Number: 12
Column Tag: Modula-2 Mods
Discrete-Event Simulations 
By Allen Stenger, Gardena, CA
Discrete-Event Simulation in Modula-2
[Allen Stenger works on the F-15 radar software for Hughes Aircraft Co. His
technical interests are software reliability, computer architecture, and computer
languages. Programming the Macintosh has been his hobby for the past five years.]
Despite the recent popularity of the Macintosh (e specially the Mac II) for
engineering work, little has appeared on using it for simulation. This article presents
a simple package for doing discrete-event simulation, and an example program (the
CarWash simulation from the Smalltalk books) using this package.
Perhaps the majority of simulations today are written in FORTRAN. A number of
specialized languages, designed e specially for simulation, have also appeared, with
GPSS and SIMSCRIPT being perhaps the most popular. But the language of choice for
simulation work is an old one, SIMULA 67. Macintosh programmers will recognize
SIMULA as one of the ancestors of today’s object-oriented languages, but it was really
invented as an extension of ALGOL for simulation work. SIMULA is also an ancestor of
Modula-2, which inherited from it the process concept.
As far as I know, none of these specialized simulation languages is available on
the Macintosh.
Types of Simulations
Simulations are divided generally into two classes: continuous-event and
discrete- event. In a continuous-event simulation, simulated time advances regularly
by some fixed increment, and at each simulated time the simulation checks to see if
anything happens at that time. In a discrete-event simulation, time proceeds by leaps
and bounds rather than continuously or regularly. The only simulated times that
“exist” are those when something in the state of the simulated universe changes, and
all other times are skipped as being uninteresting. This leads to an implementation of
the simulation as a queue of event records, in time order. Each event record is
dequeued and interpreted to see what new events it causes, and what changes to the state
of the universe.
The obvious implementation of a discrete-event simulation (known as the
event-oriented model) requires the definition of all variables making up the state of
the universe, and a set of transition rules telling how and under what conditions the
state changes. This is fairly simple to implement (it is just a Finite-State Machine
interpreter), but can often be obscure since the simulation consists of a (potentially
very large) set of states and transformation rules.
A rival approach has arisen, known as the process-oriented model. In the
event-oriented model, the events are considered central, and the programmer must
supply any connections between events, even the obvious ones of some object
undergoing several operations in sequence as time advances. In the process-oriented
model, each object is carried along by a thread of execution of the program, with
multiple threads executing con currently if there are multiple objects. There is no
single place where the state of the universe is kept, but the universe is make up of
objects, each with its own state. Each object’s state is implicitly kept in the local
variables of its thread of execution (unlike the event-oriented model, where the state
must either be defined globally or saved and restored locally when execution suspends
and resumes). This approach is a good bit simpler for the programmer, since it
requires less bookkeeping and also intuitively ties the progress of each object to the
progress of one thread in the program. On the other hand, it requires a language which
supports concurrency, which is probably why it has not been as popular as the
event-oriented approach.
One of Modula-2’s advances over Pascal is built-in support for concurrency, and
we will take advantage of this to construct a process-oriented simulation. (Object
Pascal fans may wish to translate this program into that language, in order to
understand better the strengths of Modula-2. The case of multiple washers is
e specially instructive.)
Program Notes
The program is divided into three modules: SimulationToolbox, CarWash, and
Distributions. The SimulationToolbox module provides a set of general-purpose
simulation routines which (in theory) should be useful for implementing any
simulation. The CarWash module is the “application program,” and implements the
Smalltalk car wash example, using the SimulationToolbox. The Distributions module
provides random-number generators for uniform and exponential distributions; it
could have been combined with the SimulationToolbox.
Modula-2 allows the external interface to a module to be defined separately from
the implementation, and I took advantage of this in developing the SimulationToolbox.
After developing some general ideas on how the program would work, I first wrote the
DEFINITION MODULE for SimulationToolbox. I then wrote and compiled some sample
simulation programs using this module. After adjusting the definitions until I was
happy with the example programs, I finally wrote the IMPLEMENTATION MODULE for
SimulationToolbox. This method of development saves a lot of time which would
otherwise be spent implementing routines which later turn out to be the wrong ones!
(Note that in Modula-2, unlike Pascal, the definition and implementation parts are
separately compiled, allowing changes to be made to the implementation part without
recompiling all the modules that use that module.)
In the SimulationToolbox, each separate “thread of execution” is called a thread.
(In the car wash example, each car’s actions are a separate thread, and each washer’s
actions are a separate thread. The cars and the washers are the objects that make up
this universe.) The main program is assigned a thread when it begins running; and
any thread may create new, independent threads by using the CreateNewThread
procedure. All threads appear to run con currently. Threads are passed a procedure
with which to begin execution, and the address of a parameter block which will tell the
thread what to do. The format of the parameter block is arbitrary.
Threads may suspend themselves for a specified period of simulated time (e.g. to
simulate some work that they are doing), or may suspend themselves on a queue
waiting for service. Once a thread has completed its role in the simulation, it may exit
by calling HaltThread. Any thread may halt the entire simulation by calling
HaltSimulation.
Given this framework, the CarWash simulation is fairly straightforward. The
main program creates a thread for each washer, and the washers queue on
CarWashEntrance waiting for cars to appear. The main program also creates an
instance (thread) of each type of car (wash only, or wash and wax). When each car is
created, it delays for a random period to simulate random arrival times, then it
creates the next instance (thread) of that type of car, and queues itself on the
CarWashEntrance. (The first car of each type is special -- it does not delay, but
immediately queues itself. This is done to match the implementation in Goldberg and
Robson. The physical interpretation of this is that the first car of each type has just
arrived when the car wash opens.) Washers repeatedly dequeue cars from the
CarWashEntrance and simulate random amounts of time to wash and wax them. When a
car is done, its thread exits.
Now let’s look at the implementation of SimulationToolbox. Each thread is
implemented as a Modula-2 process. The process is the key feature of Modula-2 which
allows us to use the process-model, rather than the event-model, of simulation.
Processes, despite their name, are actually co-routines, and the TRANSFER operation
is actually a call from one co-routine to another. On the Macintosh, each process has
its own stack (called the workspace), and transferring to a process causes its stack to
become the active stack. Whenever control is returned to the calling process (again by
a TRANSFER), it resumes execution at the point it left off, and (since it has its own
stack) all of its variables are in the same state as when it gave up control.
This provides a kind of multi-tasking, which we use in SimulationToolbox to
simulate the parallel operation of threads. The multi-tasking is simpler than that
commonly found in operating systems, since there is no time-slicing or preemption
-- each process can stay in control as long as it wants, and gives up control by
activating the process of its choice.
The SimulationToolbox implements each thread as a process and a Thread Control
Block (TCB) which contains miscellaneous variables needed to control the thread and to