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 (especially 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.

Background

Perhaps the majority of simulations today are written in FORTRAN. A number of specialized languages, designed especially 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 concurrently 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 especially 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 concurrently. 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 queue it in various places to simulate queueing of the thread itself. The routine DispatchFromQueue takes the role of an operating system scheduler in deciding which thread gets to run next.

I used two local modules to segregate parts of the code that I considered likely to change; this isolates these parts and (in theory) reduces the impact on the rest of the code of any changes in these parts. These two modules are the WorkSpaceManager (allocates and deallocates workspaces) and the TCBManager (does all operations on TCBs, so that other portions of the code are not sensitive to how the TCBs are structured or manipulated). Local modules are not as nice as regular modules, since they do not have DEFINITION and IMPLEMENTATION parts, and they cannot be separately compiled; but they do allow some logical separation of the code.

Miscellaneous notes. These are some additional observations on the design that did not fit in the narrative above.

1. Modula-2 does not allow co-routines to be called with parameters. Therefore parameters are passed indirectly through a user-defined parameter block, whose address is stored in the TCB. Normally the parameter block is defined as a local variable in the caller; the called routine pulls out the parameters from this block, and needs not worry about being preempted by the caller (who might later change the block) as long as the called routine does not suspend itself before retrieving all the parameters.

2. I have chosen to use singly-linked lists for queueing TCBs. Doubly-linked lists are more commonly used for this, and probably better. I just did not want the extra complication.

3. This implementation uses a fixed-size workspace (although the SimulationToolbox interface allows user-specified sizes). This was done to avoid potential problems in allocating stacks on the heap (described in the SemperSoft manual pp. 44-45). Again, this was done for simplicity and is not a fundamental design decision.

4. The routine EnsureEnoughStack is needed because the workspaces are allocated on the stack and take up much more space than the default stack allocation. The compiler is supposed to automatically expand the stack to compensate for this, but doesn’t. This doesn’t have much impact as long as the stack does not expand past HeapEnd (the last actually used address in the application heap), except in the case of the Mac II. The Color QuickDraw text-drawing routines use the stack as a work area, and carefully check that there is enough stack space to do their job. If there is not enough (as would be the case if this routine were omitted) they quietly skip processing. This causes unusual sights such as the Standard File dialog box with all blank text.

For Further Reading

The Process View of Simulation, W.R. Franta. North-Holland, 1977. The classic book on the process-oriented model. Like most classics, full of useful information, and difficult to understand. Based on SIMULA 67.

Smalltalk-80: The Language and its Implementation, Adele Goldberg and David Robson. Addison-Wesley, 1983. Part 3 is about simulations in Smalltalk. As usual, Smalltalk programs are difficult to categorize, but these simulations appear to lean more to the event-oriented model. The CarWash example is on pp. 518-521.

“PASSIM: a discrete-event simulation package for PASCAL,” Dean H. Uyeno and Willem Vaessen. Simulation, v. 35 n. 6 (December 1980), pp. 183-190. PASSIM is another simulation package for a general-purpose language, this time for Pascal. PASSIM uses the event-oriented model.

“MicroPASSIM: A modelling package for combined simulation using Turbo Pascal,” Claude C. Barnett. In: Modelling and Simulation on Microcomputers, R. Greer Lavery (ed.). Society for Computer Simulation, 1985, pp. 37-41. Describes a conversion of PASSIM for MS-DOS.

Sample Simulation Runs

Listed below are two runs of the simulation program. Each specified a run time of 80 minutes; the first uses one washer and the second uses three washers.

The average arrival rate of Wash cars is one every 20 minutes, while for WashAndWax cars it is one every 30 minutes. Each washer averages 19 minutes to wash a car, and 29 minutes to wash and wax a car. Thus if there were only one stream of cars, a single washer could barely keep up. In the simulation, there are two streams, so a single washer quickly falls behind, two washers can barely keep up, but three washers can handle the load.

In the first example, during 80 minutes there were 4 Wash and 4 WashAndWax cars arriving, of which 2 each were completed. In the second example, during 80 minutes there were 3 Wash and 2 WashAndWax cars, all of which were completed. The units of time are 0.01 minutes (so 8000 means 80.00 minutes).

****** Simulation run with   1 washers,
****** for a duration of   8000.
     0 Wash   1 Entering car wash entrance.
     0 Washer  1 (Wash  1) Washing car.
     0 WashAndWax   1 Entering car wash entrance.
   558 Wash   2 Entering car wash entrance.
   943 WashAndWax   2 Entering car wash entrance.
  1445 Washer  1 (Wash  1) Wash complete.
  1445 Washer  1 (Wash  1) Ready for next car.
  1445 Washer  1 (WashAndWax  1) Washing car.
  1445 Wash   1 Leaving car wash.
  1762 Wash   3 Entering car wash entrance.
  3141 Washer  1 (WashAndWax  1) Wash complete.
  3141 Washer  1 (WashAndWax  1) Waxing car.
  4157 Washer  1 (WashAndWax  1) Wax complete.
  4157 Washer  1 (WashAndWax  1) Ready for next car.
  4157 Washer  1 (Wash  2) Washing car.
  4157 WashAndWax   1 Leaving car wash.
  5529 WashAndWax   3 Entering car wash entrance.
  6316 Washer  1 (Wash  2) Wash complete.
  6316 Washer  1 (Wash  2) Ready for next car.
  6316 Washer  1 (WashAndWax  2) Washing car.
  6316 Wash   2 Leaving car wash.
  7457 Wash   4 Entering car wash entrance.
  7509 WashAndWax   4 Entering car wash entrance.
  7650 Washer  1 (WashAndWax  2) Wash complete.
  7650 Washer  1 (WashAndWax  2) Waxing car.

>>> Simulation halting at time   8070

****** Simulation run with   3 washers,
****** for a duration of   8000.
     0 Wash   1 Entering car wash entrance.
     0 Washer  1 (Wash  1) Washing car.
     0 WashAndWax   1 Entering car wash entrance.
     0 Washer  2 (WashAndWax  1) Washing car.
   558 Wash   2 Entering car wash entrance.
   558 Washer  3 (Wash  2) Washing car.
   943 WashAndWax   2 Entering car wash entrance.
  1445 Washer  1 (Wash  1) Wash complete.
  1445 Washer  1 (Wash  1) Ready for next car.
  1445 Washer  1 (WashAndWax  2) Washing car.
  1445 Wash   1 Leaving car wash.
  1967 Washer  2 (WashAndWax  1) Wash complete.
  1967 Washer  2 (WashAndWax  1) Waxing car.
  2254 Washer  3 (Wash  2) Wash complete.
  2254 Washer  3 (Wash  2) Ready for next car.
  2254 Wash   2 Leaving car wash.
  3041 Washer  2 (WashAndWax  1) Wax complete.
  3041 Washer  2 (WashAndWax  1) Ready for next car.
  3041 WashAndWax   1 Leaving car wash.
  3400 Washer  1 (WashAndWax  2) Wash complete.
  3400 Washer  1 (WashAndWax  2) Waxing car.
  3615 Wash   3 Entering car wash entrance.
  3615 Washer  3 (Wash  3) Washing car.
  4407 Washer  1 (WashAndWax  2) Wax complete.
  4407 Washer  1 (WashAndWax  2) Ready for next car.
  4407 WashAndWax   2 Leaving car wash.
  5845 Washer  3 (Wash  3) Wash complete.
  5845 Washer  3 (Wash  3) Ready for next car.
  5845 Wash   3 Leaving car wash.

>>> Simulation halting at time   8300

Source Listings

(****************************************************)
(* file:  CarWash.m*)
(* Car Wash simulation using SimulationToolbox.    *)
(* REFERENCE:  Goldberg and Robson, SMALLTALK-80:  *) 
(* THE LANGUAGE AND ITS IMPLEMENTATION,*) 
(* pp. 518-521.  *)
(* Written in SemperSoft Modula-2 v.1.1.2                *)
(* Allen Stenger May 1989   *)
(****************************************************)

MODULE CarWash;

FROM SYSTEM IMPORT ADDRESS,ADR;
FROM InOutIMPORT ReadCard,Write,
 WriteCard,WriteLn,
 WriteString;
FROM Terminal    IMPORT WritePString;
FROM SimulationToolbox  IMPORT Duration,Requester,
 SimulationQueue;
FROM SimulationToolbox  IMPORT CreateNewThread,
 CurrentTime,HaltThread,
 HaltSimulation,Hold,
 InitializeQueue,
 PlaceOrder,Reactivate,
 Serve;
FROM Distributions IMPORT ExponentialDistribution,
 UniformDistribution;

CONST
 WS=  8192; (* default work size *)

(* Note:  
 Times (Duration type) are in 0.01-minute units. *)
 
 WashArrivalMean 
 = 2000;(* mean arrival time for 
 wash only *)
 WashAndWaxArrivalMean  
 = 3000;(* mean arrival time for 
 wash and wax *)
 MinWashTime=  1200; (* min and max wash times *)
 MaxWashTime=  2600;
 MinWaxTime =  800;(* min and max wax times *)
 MaxWaxTime =  1200;
 
TYPE
 DesiredService  = ( Wash, WashAndWax );
 WasherParams  = RECORD 
 (* for starting washer thread *)
 WhoAmI : CARDINAL;
 END; (* RECORD *)
 CarParams= RECORD 
 (* for starting car thread *)
 WhoAmI : CARDINAL;
 type : DesiredService;
 END; (* RECORD *)
 ServiceParams = RECORD 
 (* describes car wanting service *)
 Car    : CARDINAL;
 Service: DesiredService;
 END; (* RECORD *)
VAR
 latestCar: ARRAY 
 DesiredService OF CARDINAL;
 (* numbers of last cars created *)

 CarWashEntrance : SimulationQueue;
 timeLimit: Duration; (* extent of 
 simulation *)
 numberOfWashers : CARDINAL; 
 (* number of servers *)  

PROCEDURE LoggitWasher( washer : CARDINAL;
 s : ARRAY OF CHAR; type : DesiredService; car : CARDINAL );
BEGIN
 WriteCard( CurrentTime(),6 );
 Write(“ “);
 WriteString(“Washer”); 
 WriteCard( washer,3 );
 Write(“ “);
 IF type = Wash
 THEN
 WriteString(“(Wash”);
 ELSE
 WriteString(“(WashAndWax”);
 END; (* IF *)
 WriteCard( car,3 );
 WriteString(“) “);
 WriteString( s );
 WriteLn;
END LoggitWasher;

PROCEDURE LoggitCar( car : CARDINAL; 
 s : ARRAY OF CHAR; type : DesiredService );
BEGIN
 WriteCard( CurrentTime(),6 );
 Write(“ “);
 IF type = Wash
 THEN
 WriteString(“Wash “);
 ELSE
 WriteString(“WashAndWax “);
 END; (* IF *)
 WriteCard( car,3 );
 Write(“ “);
 WriteString( s );
 WriteLn;
END LoggitCar;

PROCEDURE SimulateWasher( parameterAddress : ADDRESS );
VAR
 wpp    : POINTER TO WasherParams;
 whoAmI : CARDINAL; (* number of this washer *)
 r :  Requester; (* who is being served *)
 sType  : POINTER TO ServiceParams; 
 service: DesiredService;
 car  : CARDINAL;
BEGIN
 wpp := parameterAddress;
 whoAmI := wpp^.WhoAmI;
 LOOP
 Serve( CarWashEntrance, sType, r);
 WITH sType^ DO
 service := Service;
 car := Car;
 END; (* WITH *)
 
 (* wash car *)
 LoggitWasher( whoAmI,”Washing car.”,
 service,car );
 Hold( UniformDistribution( 
 MinWashTime, MaxWashTime 
 ) );
 LoggitWasher( whoAmI,”Wash complete.”, service,car );
 IF service = WashAndWax
 THEN (* also wax car *)
 LoggitWasher( whoAmI,”Waxing car.”, service,car );
 Hold( UniformDistribution( 
 MinWaxTime, MaxWaxTime ) );
 LoggitWasher( whoAmI,”Wax complete.”,
 service,car );
 END; (* IF *)
 
 Reactivate( r );
 LoggitWasher( whoAmI,”Ready for next car.”,
 service,car );
 END; (* LOOP *)
END SimulateWasher;

PROCEDURE CreateNewCar( type : DesiredService ); FORWARD;

PROCEDURE SimulateCar( parameterAddress : ADDRESS );
VAR
 cpp    : POINTER TO CarParams;
 whoAmI : CARDINAL; (* number of this car *)
 type : DesiredService;
 mean : Duration; (* mean inter-arrival time *)
 carDesc: ServiceParams;
BEGIN
 cpp := parameterAddress;
 type := cpp^.type;
 whoAmI := cpp^.WhoAmI;
 IF whoAmI = 1 
 THEN (* start running right away *)
 ELSE (* delay to simulate random arrival time *)
 CASE type OF
 Wash   : mean := WashArrivalMean |
 WashAndWax :  mean 
 := WashAndWaxArrivalMean;
 END; (* CASE *)
 Hold( ExponentialDistribution( mean ) );
 END; (* IF *)
 
 CreateNewCar( type ); (* create next car of this type *)
 
 LoggitCar( whoAmI,”Entering car wash entrance.”, type );
 WITH carDesc DO
 Service := type;
 Car := whoAmI;
 END; (* WITH *)
 (* queue up for service *)
 PlaceOrder( CarWashEntrance, ADR(carDesc) ); 
 LoggitCar( whoAmI,”Leaving car wash.”,type );
 
 HaltThread; (* service over, car disappears into sunset *)
END SimulateCar;

PROCEDURE CreateNewCar( type : DesiredService );
VAR
 cp:  CarParams;
BEGIN
 IF CurrentTime() < timeLimit
 THEN
 INC(latestCar[type]);
 cp.WhoAmI := latestCar[type];
 cp.type := type;
 CreateNewThread( SimulateCar,ADR(cp),WS);
 ELSE
 HaltSimulation;
 END; (* IF *)
END CreateNewCar;

PROCEDURE InitSimulation;
VAR
 i :  DesiredService; (* loop control *)
 n :  CARDINAL; (* loop control *)
 wp:  WasherParams;
 dur  : CARDINAL;
 
BEGIN
 WritePString(“How many washers are there?  “);
 ReadCard( numberOfWashers );
 WritePString(
  “How long should the simulation run (minutes) ? “);
 ReadCard( dur );
 timeLimit := dur * 100; 
 (* Duration is in 0.01-minute units *)
 WriteString(“****** Simulation run with “);
 WriteCard( numberOfWashers,3 );
 WriteString(“ washers,”);
 WriteLn;
 WriteString(“****** for a duration of “);
 WriteCard( timeLimit,6 );
 WriteString(“.”);
 WriteLn;
 
 FOR i := MIN(DesiredService) 
 TO MAX(DesiredService) DO
 latestCar[i] := 0;
 END; (* FOR *)
 InitializeQueue( CarWashEntrance );
 
 (* Create all washers *)
 FOR n := 1 TO numberOfWashers DO
 wp.WhoAmI := n;
 CreateNewThread( SimulateWasher,ADR(wp),WS );
 END; (* FOR *)
 
 (* Create one of each kind of car *);
 CreateNewCar( Wash );
 CreateNewCar( WashAndWax );
 
END InitSimulation;

BEGIN
 InitSimulation;
 HaltThread;
END CarWash.

(****************************************************)
(* file:  Distributions.d *)
(* This module provides commonly used random             *)
(* distributions.*)
(* Written in SemperSoft Modula-2 v.1.1.2                *)
(* Allen Stenger May 1989   *)
(****************************************************)

DEFINITION MODULE Distributions;

(* Uniform distribution in the range start..end.*)
PROCEDURE UniformDistribution( 
 start, end : CARDINAL ) : CARDINAL;

(* Exponential distribution of given mean.*)
PROCEDURE ExponentialDistribution( 
 mean : CARDINAL ) : CARDINAL;

END Distributions.

(****************************************************)
(* file:  Distributions.m *)
(* See definition module for documentation of            *)
(* functions.      *)
(* Written in SemperSoft Modula-2 v.1.1.2                *)
(* Allen Stenger May 1989   *)
(****************************************************)
IMPLEMENTATION MODULE Distributions;

FROM MathLib0    IMPORT ln;
FROM InsideMac   IMPORT Random;

PROCEDURE UniformZeroToOne() : REAL;
BEGIN
 RETURN( FLOAT(Random()) / 65534.0 + 0.5 )
END UniformZeroToOne;

PROCEDURE UniformDistribution( 
 start, end : CARDINAL ) : CARDINAL;
BEGIN
 RETURN( start 
 + TRUNC((FLOAT(end - start) + 1.0) 
 * UniformZeroToOne()) );
END UniformDistribution;

PROCEDURE ExponentialDistribution( 
 mean : CARDINAL ) : CARDINAL;
CONST
 maxCard= FLOAT(MAX(CARDINAL));
VAR
 r :  REAL;
BEGIN
 r := - FLOAT(mean) * ln( UniformZeroToOne() );
 IF r > maxCard THEN r := maxCard END;
 RETURN( TRUNC(r) ); 
END ExponentialDistribution;

END Distributions.

(****************************************************)
(* file:  SimulationToolbox.d *)
(*  This module defines a set of subroutines for         *) 
(* doing discrete event simulation, using a        *)
(* “process” viewpoint.   *)
(* Written in SemperSoft Modula-2 v.1.1.2                *)
(*  Allen StengerMay 1989 *)
(****************************************************)

DEFINITION MODULE SimulationToolbox;

FROM SYSTEM IMPORT ADDRESS;

TYPE
 Duration = CARDINAL;(* in units of time as
 defined by the caller *)
 Starter= PROCEDURE ( ADDRESS );
 SimulationQueue;
 Requester;
 
(*  CreateNewThread starts a new thread of execution in 
 the simulation, beginning execution at routine 
 starter, which is passed the address of a parameter 
 block so that it knows what to do.  The worksize is
 the size (in bytes) of the stack to be allocated for 
 this thread.  The calling thread is suspended and 
 the new thread beings execution.  (Note that the 
 calling thread will be resumed to complete its 
 execution for the current time before the time can 
 be advanced.)  Initial execution of the program is 
 also considered to be a thread. 
*)
PROCEDURE CreateNewThread(  starter : Starter; 
 parameterAddress : ADDRESS;
 worksize : CARDINAL );
 
(* Hold is called to simulate a delay (while work is 
 being simulated).  The calling thread is suspended
 until this much simulated time has passed.  The 
 order of execution of threads becoming active at 
 the same simulated time is not defined.  Hold(0) 
 is legal.
*)
PROCEDURE Hold( howLong : Duration );

(* HaltSimulation is called at the end of the 
 simulation run and causes all threads to exit.
*)
PROCEDURE HaltSimulation;

(* HaltThread is called by a thread to end its own 
 existence.*)
PROCEDURE HaltThread;

(* CurrentTime returns the current simulated time (time
 starts at 0).*)
PROCEDURE CurrentTime() : Duration;

(****************************************************)
(* Queueing routines *)
(****************************************************)

(* InitializeQueue is called to create and initialize 
 a queue.*)
PROCEDURE InitializeQueue( VAR q : SimulationQueue );

(* PlaceOrder is called to place the caller on a queue 
 for service.  The parameterAddress is the address of 
 a parameter block that will be interpreted by the 
 server to determine the type of service needed.The 
 caller is suspended until reactivated by the server, 
 usually at the end of service.  More than one caller
 may be queued; the order of service is FIFO.
*)
PROCEDURE PlaceOrder(   q : SimulationQueue; 
 parameterAddress : ADDRESS );

(* Serve is called by a server to obtain the next order 
 to serve.  The identity of the requester is returned 
 so that the server may resume the requester when 
 done.  If there are no orders, the caller is 
 suspended until an order arrives.  More than one 
 server may wait on the same queue; the order in 
 which orders are given to servers is FIFO.
*)
PROCEDURE Serve( q: SimulationQueue; 
 VAR parameterAddress : ADDRESS; 
 VAR r : Requester );

(* Reactivate is called by a server to resume execution 
 of the requester.  The requester becomes ready to 
 run at the current time.  The caller continues to 
 run until it gives up control.
*)
PROCEDURE Reactivate( r : Requester );

END SimulationToolbox.

(****************************************************)
(* file:  SimulationToolbox.m *)
(*  This is the implementation module - see the    *)
(* definition module for documentation on external *)
(* routines.*)
(* Written in SemperSoft Modula-2 v.1.1.2                *)
(*  Allen StengerJune 1989*)
(****************************************************)

IMPLEMENTATION MODULE SimulationToolbox;

FROM SYSTEM IMPORT ADDRESS,ADR,PROCESS,NEWPROCESS,
 LONG,TRANSFER,TSIZE;
FROM InOutIMPORT CloseOutput,OpenOutput;
FROM InOutIMPORT Read,WriteCard,WriteLn,
 WriteString;
FROM StorageIMPORT ALLOCATE;
FROM InsideMac IMPORTDefltStack,GetApplLimit,
 SetApplLimit;
FROM VolumeIV  IMPORTStackSpace;

TYPE
 SimulationQueue = POINTER TO QueueBlock;

VAR
 currentTime:  Duration;
 (* current simulated time *)

PROCEDURE PrintHalt; FORWARD;
 (************************************************)
 (*This local module encapsulates the  *)
 (*workspace allocation and deallocation.          *)
 (************************************************)
 MODULE WorkSpaceManager;
 IMPORT WriteString;
 IMPORT PrintHalt;
 EXPORT AllocateWorkSpace,DeallocateWorkSpace;
 
 (******* temporary implementation with all 
 fixed-size WS of 8192 bytes *)
 TYPE
 WSIndex= [1..15];
 WS=  ARRAY [1..4096] OF INTEGER;
 WSDesc = RECORD
 WSArea : WS;
 ThisWS,
 NextWS : CARDINAL;
 END; (* RECORD *)
 
 VAR
 theWorks : ARRAY WSIndex OF WSDesc;
 freeWS : CARDINAL;
 (* chain of free blocks *)
 
 PROCEDURE AllocateWorkSpace( VAR wsp : ADDRESS; 
  worksize : CARDINAL );
 BEGIN
 IF worksize # TSIZE(WS)
 THEN
 WriteString(“>>>wrong size worksize”);
 PrintHalt;
 ELSIF freeWS = 0 THEN
 WriteString(“>>> Out of workspaces “);
 PrintHalt;
 ELSE
 WITH theWorks[freeWS] DO
 wsp := ADR(WSArea);
 freeWS := NextWS;
 END; (* WITH *)
 END; (* IF *)
 END AllocateWorkSpace;
 
 PROCEDURE DeallocateWorkSpace( wsp : ADDRESS; 
   worksize : CARDINAL );
 VAR
 i :  CARDINAL;
 BEGIN
 FOR i := MIN(WSIndex) TO MAX(WSIndex) DO
 WITH theWorks[i] DO
 IF ADR(WSArea) = wsp
 THEN
 NextWS := freeWS;
 freeWS := i;
 END; (* IF *)
 END; (* WITH *)
 END; (* DO *)
 END DeallocateWorkSpace;
 
 PROCEDURE Init;
 VAR
 i :  CARDINAL;
 BEGIN
 (* Chain the workspaces together *)
 freeWS := MIN(WSIndex);
 FOR i := MIN(WSIndex) TO MAX(WSIndex) DO
 WITH theWorks[i] DO
 ThisWS := i;
 NextWS := i + 1;
 END; (* WITH *)
 END; (* FOR *)
 theWorks[MAX(WSIndex)].NextWS := 0;
 END Init;
 
 BEGIN
 Init;
 END WorkSpaceManager;
 
 (************************************************)
 (*This local module encapsulates the TCB          *)
 (*(Thread Control Block) and does most of the     *)
 (*work of the Toolbox.  References to TCBs        *)
 (*should pass the TCB (pointer) to this           *)
 (*package, and should notreference TCB            *)
 (*fields directly.*)
 (************************************************)

 MODULE TCBManager;
 IMPORT Duration,Starter;
 IMPORT WriteString;
 IMPORT currentTime;
 IMPORT DeallocateWorkSpace;
 IMPORT PrintHalt;
 EXPORT TCB,TCBQHdr,
 DispatchFromQueue,AddToReadyQueue,
 CreateNewTCB,HangHalt,HangHold,StartTCB,
 QueueTCB,DequeueTCB;
 
 TYPE
 TCBPtr = POINTER TO TCBType;
 TCBType= 
 RECORD
 NextTCB: TCBPtr;(* forward chain *)
 ThreadNumber: CARDINAL; (* seq. no. *)
 HaltPending:  BOOLEAN; 
 (* halt in progress *)
 SuspendPending : BOOLEAN; 
 (* suspend in progress*)
 ActTime: Duration; 
 (* when to activate *)
 State  : PROCESS; (* from TRANSFER *)
 StartProc: Starter; (* where to begin*)
 Parms  : ADDRESS; (* thread parms *)
 WorkSpace: ADDRESS; (* stack address *)
 WorkSize : CARDINAL; 
 (* stack size in bytes*)
 END; (* RECORD *)
 
 TCB    = TCBPtr;
 (* for export only - in this 
 module use TCBPtr *)
 TCBQHdr= TCBPtr;
 TCBRange = [1..20];
 
 VAR
 (*  TCB lists -- TCBs may also be queued on 
 SimulationQueue types *)
 currentTCB : TCBPtr; (* currently active TCB *)
 readyList: TCBPtr; (* waiting TCBs, 
 in ascending order of ActTime *)
 haltList : TCBPtr; (* TCBs awaiting halt *)
 freeTCB: TCBPtr; (* free list of 
 TCB blocks *)
 
 lastThreadNumber : CARDINAL; 
 (* latest 
 TCBPtr^.ThreadNumber *)
 TCBBlocks: ARRAY TCBRange OF TCBType; 
  (* TCB pool *)
 
 (*  Dispatch the next TCB from the ready list while 
 queueing the current TCB. *)
 PROCEDURE DispatchFromQueue;
 (*
 This is the “scheduler” for the simulation.  
 When it is called by a thread, in general that 
 thread will be suspended and another will begin 
 running.  More precisely, there are 5 
 possibilities for the calling thread:
 1.The thread will return after advancing 
 currentTime, without disturbing the 
 ready list.  (Only occurs if the current
 TCB has an earlier activation time that 
 any TCB on the list.)
 2.The thread is marked to terminate and 
 will dequeue the next TCB from the ready 
 list, place it as the current TCB, 
 advance currentTime, place itself on the
 halt queue, and suspend itself (by 
 TRANSFER to the new current TCB).
 3.Same as 2 except it places itself in 
 order on the ready list.
 4.The simulation halts because the current 
 thread is marked to suspend or terminate
 and there are no ready TCBs.
 5.Same as 2 except the current TCB has 
 already been placed on a SimulationQueue
 and will not be further touched, except
 to TRANSFER to the next TCB.
 
 When a new thread is selected to be the current 
 thread, there are two possibilities for it:
 A.It may begin execution at StartTCB (if 
 this is its first execution).
 B.It may begin execution immediately 
 following the TRANSFER (if it is 
 resuming execution).
 In case B the thread will check the halt queue 
 and release any TCBs on it, then will issue 
 RETURN, causing it to return to the call that 
 send it to the scheduler in the first place.  
 Thus for HOLD the thread has held for the 
 desired time and is now returning to the
 simulation code, and for suspensions execution 
 will resume at the point of suspension.
 *)
 
 VAR
 saveCurrent:  TCBPtr;
 
 PROCEDURE RequeueTCB( t : TCBPtr );
 VAR
 lastTCB,
 thisTCB: TCBPtr;
 BEGIN
 lastTCB := NIL;
 thisTCB := readyList;
 WHILE (thisTCB # NIL) 
 AND (t^.ActTime >= thisTCB^.ActTime) DO
 lastTCB := thisTCB;
 thisTCB := thisTCB^.NextTCB;
 END; (* WHILE *)
 t^.NextTCB := thisTCB;
 IF lastTCB = NIL
 THEN (* inserting at beginning *)
 readyList := t;
 ELSE (* inserting past beginning *)
 lastTCB^.NextTCB := t;
 END; (* IF *)
 END RequeueTCB;
 
 PROCEDURE ClearHaltQueue;
 VAR
 releasedTCB:  TCBPtr;
 BEGIN
 WHILE haltList # NIL DO
 WITH haltList^ DO
 IF WorkSpace # NIL (* main is 
 special - no 
 workspace *)
 THEN
 DeallocateWorkSpace( 
 WorkSpace,WorkSize);
 END; (* IF *)
 END; (* WITH *)
 releasedTCB := haltList;
 haltList := haltList^.NextTCB;
 releasedTCB^.NextTCB := freeTCB;
 freeTCB := releasedTCB;
 END; (* WHILE *)
 END ClearHaltQueue;
 
 BEGIN (* DispatchFromQueue *)
 IF readyList = NIL
 THEN (* no other active threads *)
 IF currentTCB^.SuspendPending 
 OR currentTCB^.HaltPending
 THEN (* case 4 *)
 PrintHalt;
 ELSE (* case 1 with empty ready list *)
 currentTime := currentTCB^.ActTime;
 (* just return *)
 END; (* IF *)
 ELSE (* other active threads - 
 see who gets to run *)
 IF   currentTCB^.SuspendPending
 OR currentTCB^.HaltPending 
 OR (currentTCB^.ActTime >= 
 readyList^.ActTime)
 (* >= ensures that list will be 
 shuffled if other TCBs have the 
 same activation time as currentTCB - 
 needed for CreateNewThread *)
 THEN (* new thread gets to run - 
 cases 5, 2 and 3 *)
 saveCurrent := currentTCB;
 currentTCB := readyList;
 readyList := readyList^.NextTCB;
 currentTime := currentTCB^.ActTime;
 
 IF saveCurrent^.SuspendPending
 THEN (* no queueing action required - 
 case 5 *)
 saveCurrent^.SuspendPending :=
 FALSE;
 ELSIF saveCurrent^.HaltPending
 THEN (* put on halt queue - case 2 *)
 saveCurrent^.NextTCB := haltList;
 haltList := saveCurrent;
 ELSE (* put on ready list - case 3 *)
 RequeueTCB(saveCurrent);
 END; (* IF *)
 
 (*****************************)
 TRANSFER(saveCurrent^.State,
 currentTCB^.State);
 (*****************************)
 
 (* new thread is now in control *)
 
 ClearHaltQueue;
 
 ELSE (* old thread continues - 
 case 1 with non-empty ready list*)
 currentTime := currentTCB^.ActTime;
 (* just return *)
 END; (* IF *)
 END; (* IF *)
 END DispatchFromQueue;
 
 (*Add a TCB to the beginning of the ready list *)
 PROCEDURE AddToReadyQueue( t : TCBPtr );
 BEGIN
 t^.ActTime := currentTime;
 t^.NextTCB := readyList;
 readyList := t;
 END AddToReadyQueue;
 
 (*Allocate a new TCB.  Note that only the pointer 
 is returned - the caller has no direct access 
 to TCBs but should go through this module.  The 
 workspace address and size are recorded in the 
 TCB for use when the TCB exits.  *)
 PROCEDURE CreateNewTCB ( VAR t : TCBPtr;
 p : PROCESS; 
 startP : Starter;
 parms : ADDRESS;
 workspace : ADDRESS;
 worksize : CARDINAL );
 BEGIN
 IF freeTCB = NIL
 THEN
 WriteString(“>>>Out of TCBs”);
 PrintHalt;
 ELSE
 t := freeTCB;
 freeTCB := freeTCB^.NextTCB;
 WITH t^ DO
 NextTCB := NIL;
 INC(lastThreadNumber);
 ThreadNumber := lastThreadNumber;
 HaltPending := FALSE;
 SuspendPending := FALSE;
 ActTime:= currentTime;
 State := p;
 StartProc := startP;
 Parms := parms;
 WorkSpace := workspace;
 WorkSize := worksize;
 END; (* WITH *)
 END; (* IF *)
 END CreateNewTCB;
 
 (*  Mark the current TCB to be halted.  It will 
 continue to run until DispatchFromQueue is 
 called next, at which point the TCB will be 
 placed on the halt queue. *)
 PROCEDURE HangHalt;
 BEGIN
 currentTCB^.HaltPending := TRUE;
 END HangHalt;
 
 (*Mark the current TCB to run again after a 
 specified Duration.  It will continue to run 
 until DispatchFrom Queue is called.  *)
 PROCEDURE HangHold ( howLong : Duration );
 BEGIN
 currentTCB^.ActTime := currentTime + howLong;
 END HangHold;
 
 (*  Begin execution of a new thread according to 
 starter in TCB.  This is activated as a result 
 of the TRANSFER in DispatchFromQueue the first 
 time the thread runs.  *)
 PROCEDURE StartTCB;
 BEGIN
 WITH currentTCB^ DO
 StartProc(Parms);
 END; (* WITH *)
 END StartTCB;
 
 (*   Add the current TCB to a user queue, or remove 
 a TCB from a user queue.  A parameter block 
 address is recorded, then returned when the TCB 
 is dequeued. *)
 
 PROCEDURE QueueTCB( qParm : ADDRESS; VAR qHdr : TCBQHdr ); 
 VAR
 lastTCB: TCB;
 BEGIN
 IF qHdr = NIL
 THEN (* only item in queue *)
 qHdr := currentTCB;
 ELSE (* add after last element in queue *)
 lastTCB := qHdr;
 WHILE lastTCB^.NextTCB # NIL DO
 lastTCB := lastTCB^.NextTCB;
 END; (* WHILE *)
 lastTCB^.NextTCB := currentTCB;
 END; (* IF *)
 WITH currentTCB^ DO
 NextTCB := NIL;
 Parms := qParm; 
 SuspendPending := TRUE;
 END; (* WITH *)
 END QueueTCB;
 
 PROCEDURE DequeueTCB(  VAR t : TCB; 
 VAR qParm : ADDRESS; 
 VAR qHdr : TCBQHdr ); 
 BEGIN
 t := qHdr;
 qHdr := qHdr^.NextTCB;
 qParm := t^.Parms;
 END DequeueTCB;
 
 
 PROCEDURE Init;
 VAR
 i :  CARDINAL; (* loop control *)
 dummyProc: Starter; (* just used for main*)
 BEGIN
 readyList := NIL;
 haltList := NIL;
 freeTCB := NIL;
 
 FOR i := MIN(TCBRange) TO MAX(TCBRange) DO
 TCBBlocks[i].NextTCB := freeTCB;
 freeTCB := ADR(TCBBlocks[i]);
 END; (* FOR *)
 
 lastThreadNumber := 0;
 
 (* initialize TCB for already-running main routine *)
 CreateNewTCB(currentTCB,PROCESS(0),
 dummyProc,ADDRESS(0),
 ADDRESS(0),0);
 
 END Init;
 
 BEGIN (* TCBManager *)
 Init;
 END TCBManager;
 
(****************************************************)
(* Miscellaneous outer-level routines*)
(****************************************************)
PROCEDURE PrintHalt;
VAR
 ch:  CHAR;
BEGIN
 WriteLn;
 WriteLn;
 WriteString(“>>> Simulation halting at time “);
 WriteCard( currentTime,6 );
 WriteLn;
 CloseOutput;
 
 WriteString(“>>> Simulation halting at time “);
 WriteCard( currentTime,6 );
 WriteLn;
 WriteString(“>>> Press any key to end “);
 Read( ch );
 HALT;
END PrintHalt;

(*  This routine expands the stack after the workspaces
 are allocated to ensure that the Color QuickDraw
 text-drawing routines have enough stack to run. *)
PROCEDURE EnsureEnoughStack;
VAR
 moreThanEnough  : LONGINT; (* excess over 
 default *)
BEGIN
 moreThanEnough := StackSpace() - DefltStack;
 IF moreThanEnough < 0
 THEN SetApplLimit( 
 GetApplLimit() + moreThanEnough );
 END; (* IF *)
END EnsureEnoughStack;

(****************************************************)
(* Externally visible routines - see definition          *)
(* module for documentation.*)
(****************************************************)
PROCEDURE CreateNewThread(  starter : Starter; 
 parameterAddress : ADDRESS;
 worksize : CARDINAL );
VAR
 newTCB : TCB;
 wsp    : ADDRESS;
 threadProcess : PROCESS;
BEGIN
 AllocateWorkSpace(wsp, worksize);
 NEWPROCESS(StartTCB,wsp,LONG(worksize),
 threadProcess);
 CreateNewTCB(newTCB,threadProcess,
 starter,parameterAddress,wsp,
 worksize);
 AddToReadyQueue(newTCB);
 DispatchFromQueue;
END CreateNewThread;
 
PROCEDURE Hold( howLong : Duration );
BEGIN
 HangHold( howLong );
 DispatchFromQueue;
END Hold;

PROCEDURE HaltSimulation;
BEGIN
 PrintHalt; (* A Quick and Dirty Production *)
END HaltSimulation;

PROCEDURE HaltThread;
BEGIN
 HangHalt;
 DispatchFromQueue;
END HaltThread;

PROCEDURE CurrentTime() : Duration;
BEGIN
 RETURN currentTime;
END CurrentTime;

(****************************************************)
(* Queueing routines *)
(****************************************************)

(* External definitions for queueing *)
TYPE
 QueueBlock =  RECORD
 Orders : TCBQHdr;
 (* waiters for service *)
 Servers: TCBQHdr; 
 (* providers of service *)
 END; (* RECORD *)
 Requester= TCB;

PROCEDURE InitializeQueue( VAR q : SimulationQueue );
BEGIN
 NEW( q );
 q^.Orders := NIL;
 q^.Servers := NIL;
END InitializeQueue;

PROCEDURE PlaceOrder(   q : SimulationQueue; 
 parameterAddress : ADDRESS );
VAR
 s :  TCB; (* server which is activated 
 by this order *)
 trash  : ADDRESS;
BEGIN
 QueueTCB( parameterAddress, q^.Orders );
 IF q^.Servers = NIL
 THEN (* have to wait *)
 ELSE (* activate server for this queue *)
 DequeueTCB( s, trash, q^.Servers );
 AddToReadyQueue( s );
 (* the server will run and dequeue this order *)
 END; (* IF *)
 DispatchFromQueue;
END PlaceOrder;

PROCEDURE Serve( q: SimulationQueue; 
 VAR parameterAddress : ADDRESS; 
 VAR r : Requester );
BEGIN
 IF q^.Orders = NIL
 THEN (* have to wait for order *)
 QueueTCB( NIL, q^.Servers );
 DispatchFromQueue; (* wait for order *)
 END; (* IF *)
 (*   either resume execution after order arrives, or
 continue without wait if order already 
 available *)
 DequeueTCB( r, parameterAddress, q^.Orders);
END Serve;

PROCEDURE Reactivate( r : Requester );
BEGIN
 AddToReadyQueue( r );
END Reactivate;

BEGIN (* SimulationToolbox *)
 currentTime := 0;
 EnsureEnoughStack;
 OpenOutput(“Enter file name for logging:”);
END SimulationToolbox.