TweetFollow Us on Twitter

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


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:  *) 
(* pp. 518-521.  *)
(* Written in SemperSoft Modula-2 v.1.1.2                *)
(* Allen Stenger May 1989   *)


FROM InOutIMPORT ReadCard,Write,
FROM Terminal    IMPORT WritePString;
FROM SimulationToolbox  IMPORT Duration,Requester,
FROM SimulationToolbox  IMPORT CreateNewThread,
FROM Distributions IMPORT ExponentialDistribution,

 WS=  8192; (* default work size *)

(* Note:  
 Times (Duration type) are in 0.01-minute units. *)
 = 2000;(* mean arrival time for 
 wash only *)
 = 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;
 DesiredService  = ( Wash, WashAndWax );
 WasherParams  = RECORD 
 (* for starting washer thread *)
 END; (* RECORD *)
 CarParams= RECORD 
 (* for starting car thread *)
 type : DesiredService;
 END; (* RECORD *)
 ServiceParams = RECORD 
 (* describes car wanting service *)
 Car    : CARDINAL;
 Service: DesiredService;
 END; (* RECORD *)
 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 );
 WriteCard( CurrentTime(),6 );
 Write(“ “);
 WriteCard( washer,3 );
 Write(“ “);
 IF type = Wash
 END; (* IF *)
 WriteCard( car,3 );
 WriteString(“) “);
 WriteString( s );
END LoggitWasher;

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

PROCEDURE SimulateWasher( parameterAddress : ADDRESS );
 wpp    : POINTER TO WasherParams;
 whoAmI : CARDINAL; (* number of this washer *)
 r :  Requester; (* who is being served *)
 sType  : POINTER TO ServiceParams; 
 service: DesiredService;
 car  : CARDINAL;
 wpp := parameterAddress;
 whoAmI := wpp^.WhoAmI;
 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 );
 cpp    : POINTER TO CarParams;
 whoAmI : CARDINAL; (* number of this car *)
 type : DesiredService;
 mean : Duration; (* mean inter-arrival time *)
 carDesc: ServiceParams;
 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 );
 cp:  CarParams;
 IF CurrentTime() < timeLimit
 cp.WhoAmI := latestCar[type];
 cp.type := type;
 CreateNewThread( SimulateCar,ADR(cp),WS);
 END; (* IF *)
END CreateNewCar;

PROCEDURE InitSimulation;
 i :  DesiredService; (* loop control *)
 n :  CARDINAL; (* loop control *)
 wp:  WasherParams;
 dur  : CARDINAL;
 WritePString(“How many washers are there?  “);
 ReadCard( numberOfWashers );
  “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,”);
 WriteString(“****** for a duration of “);
 WriteCard( timeLimit,6 );
 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;

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   *)


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

(* Exponential distribution of given mean.*)
PROCEDURE ExponentialDistribution( 

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   *)

FROM MathLib0    IMPORT ln;
FROM InsideMac   IMPORT Random;

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

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

PROCEDURE ExponentialDistribution( 
 r :  REAL;
 r := - FLOAT(mean) * ln( UniformZeroToOne() );
 IF r > maxCard THEN r := maxCard END;
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;


 Duration = CARDINAL;(* in units of time as
 defined by the caller *)
(*  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 

(* 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*)


FROM InOutIMPORT CloseOutput,OpenOutput;
FROM InOutIMPORT Read,WriteCard,WriteLn,
FROM InsideMac IMPORTDefltStack,GetApplLimit,
FROM VolumeIV  IMPORTStackSpace;

 SimulationQueue = POINTER TO QueueBlock;

 currentTime:  Duration;
 (* current simulated time *)

 (*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 *)
 WSIndex= [1..15];
 WS=  ARRAY [1..4096] OF INTEGER;
 WSArea : WS;
 END; (* RECORD *)
 theWorks : ARRAY WSIndex OF WSDesc;
 (* chain of free blocks *)
 PROCEDURE AllocateWorkSpace( VAR wsp : ADDRESS; 
  worksize : CARDINAL );
 IF worksize # TSIZE(WS)
 WriteString(“>>>wrong size worksize”);
 ELSIF freeWS = 0 THEN
 WriteString(“>>> Out of workspaces “);
 WITH theWorks[freeWS] DO
 wsp := ADR(WSArea);
 freeWS := NextWS;
 END; (* WITH *)
 END; (* IF *)
 END AllocateWorkSpace;
 PROCEDURE DeallocateWorkSpace( wsp : ADDRESS; 
   worksize : CARDINAL );
 FOR i := MIN(WSIndex) TO MAX(WSIndex) DO
 WITH theWorks[i] DO
 IF ADR(WSArea) = wsp
 NextWS := freeWS;
 freeWS := i;
 END; (* IF *)
 END; (* WITH *)
 END; (* DO *)
 END DeallocateWorkSpace;
 (* 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;
 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.*)

 IMPORT Duration,Starter;
 IMPORT WriteString;
 IMPORT currentTime;
 IMPORT DeallocateWorkSpace;
 IMPORT PrintHalt;
 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 *)
 TCBRange = [1..20];
 (*  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.
 saveCurrent:  TCBPtr;
 PROCEDURE RequeueTCB( t : TCBPtr );
 thisTCB: TCBPtr;
 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;
 releasedTCB:  TCBPtr;
 WHILE haltList # NIL DO
 WITH haltList^ DO
 IF WorkSpace # NIL (* main is 
 special - no 
 workspace *)
 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 *)
 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 >= 
 (* >= 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 :=
 ELSIF saveCurrent^.HaltPending
 THEN (* put on halt queue - case 2 *)
 saveCurrent^.NextTCB := haltList;
 haltList := saveCurrent;
 ELSE (* put on ready list - case 3 *)
 END; (* IF *)
 (* new thread is now in control *)
 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 );
 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.  *)
 p : PROCESS; 
 startP : Starter;
 parms : ADDRESS;
 workspace : ADDRESS;
 worksize : CARDINAL );
 IF freeTCB = NIL
 WriteString(“>>>Out of TCBs”);
 t := freeTCB;
 freeTCB := freeTCB^.NextTCB;
 NextTCB := NIL;
 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. *)
 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 );
 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.  *)
 WITH currentTCB^ DO
 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 ); 
 lastTCB: TCB;
 IF qHdr = NIL
 THEN (* only item in queue *)
 qHdr := currentTCB;
 ELSE (* add after last element in queue *)
 lastTCB := qHdr;
 lastTCB := lastTCB^.NextTCB;
 END; (* WHILE *)
 lastTCB^.NextTCB := currentTCB;
 END; (* IF *)
 WITH currentTCB^ DO
 NextTCB := NIL;
 Parms := qParm; 
 SuspendPending := TRUE;
 END; (* WITH *)
 END QueueTCB;
 VAR qParm : ADDRESS; 
 VAR qHdr : TCBQHdr ); 
 t := qHdr;
 qHdr := qHdr^.NextTCB;
 qParm := t^.Parms;
 END DequeueTCB;
 i :  CARDINAL; (* loop control *)
 dummyProc: Starter; (* just used for main*)
 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 *)
 END Init;
 BEGIN (* TCBManager *)
 END TCBManager;
(* Miscellaneous outer-level routines*)
 ch:  CHAR;
 WriteString(“>>> Simulation halting at time “);
 WriteCard( currentTime,6 );
 WriteString(“>>> Simulation halting at time “);
 WriteCard( currentTime,6 );
 WriteString(“>>> Press any key to end “);
 Read( ch );
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;
 moreThanEnough  : LONGINT; (* excess over 
 default *)
 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 );
 newTCB : TCB;
 wsp    : ADDRESS;
 threadProcess : PROCESS;
 AllocateWorkSpace(wsp, worksize);
END CreateNewThread;
PROCEDURE Hold( howLong : Duration );
 HangHold( howLong );
END Hold;

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

END HaltThread;

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

(* Queueing routines *)

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

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

PROCEDURE PlaceOrder(   q : SimulationQueue; 
 parameterAddress : ADDRESS );
 s :  TCB; (* server which is activated 
 by this order *)
 trash  : ADDRESS;
 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 *)
END PlaceOrder;

PROCEDURE Serve( q: SimulationQueue; 
 VAR parameterAddress : ADDRESS; 
 VAR r : Requester );
 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 );
 AddToReadyQueue( r );
END Reactivate;

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


Community Search:
MacTech Search:

Software Updates via MacUpdate

Planet Diver guide - How to survive long...
Planet Diver is an endless arcade game about diving through planets while dodging lava, killing bats, and collecting Starstuff. Here are some tips to help you go the distance. [Read more] | Read more »
KORG iDS-10 (Music)
KORG iDS-10 1.0.0 Device: iOS iPhone Category: Music Price: $9.99, Version: 1.0.0 (iTunes) Description: ** Debut Discount: 50% OFF! Sale Price US$9.99 (Regular price US$19.99). Other all Korg apps are also 50% OFF until Dec 28! **... | Read more »
World of Tanks Generals guide - Tips and...
World of Tanks Generals is a brand new card game by the developer behind the World of Tanks shooter franchise. It plays like a cross between chess and your typical card game. You have to keep in consideration where you place your tanks on the board... | Read more »
TruckSimulation 16 guide: How to succeed...
Remember those strangely enjoyable truck missions in Grand Theft Auto V whereit was a disturbing amount of fun to deliver cargo? TruckSimulation 16 is reminiscent of that, and has you play the role of a truck driver who has to deliver various... | Read more »
The best GIF making apps
Animated GIFs have exploded in popularity recently which is likely thanks to a combination of Tumblr, our shorter attention spans, and the simple fact they’re a lot of fun. [Read more] | Read more »
The best remote desktop apps for iOS
We've been sifting through the App Store to find the best ways to do computer tasks on a tablet. That gave us a thought - what if we could just do computer tasks from our tablets? Here's a list of the best remote desktop apps to help you use your... | Read more »
Warhammer 40,000: Freeblade guide - How...
Warhammer 40,000: Freebladejust launched in the App Store and it lets you live your childhood dream of blowing up and slashing a bunch of enemies as a massive, hulking Space Marine. It's not easy being a Space Marine though - and particularly if... | Read more »
Gopogo guide - How to bounce like the be...
Nitrome just launched a new game and, as to be expected, it's a lot of addictive fun. It's called Gopogo, and it challenges you to hoparound a bunch of platforms, avoiding enemies and picking up shiny stuff. It's not easy though - just like the... | Read more »
Sago Mini Superhero (Education)
Sago Mini Superhero 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: KAPOW! Jack the rabbit bursts into the sky as the Sago Mini Superhero! Fly with Jack as he lifts impossible weights,... | Read more »
Star Wars: Galaxy of Heroes guide - How...
Star Wars: Galaxy of Heroes is all about collecting heroes, powering them up, and using them together to defeat your foes. It's pretty straightforward stuff for the most part, but increasing your characters' stats can be a bit confusing because it... | Read more »

Price Scanner via

New MacBook Air 13-Inch and 15-Inch Coming At...
The Taipei, Taiwan based Chinese language Economic Daily News’s Xie Yili reports that major redesign of the MacBook Air, which currently dates back to October, 2010, is expected to be unveiled next... Read more
World’s First USB-C Adapter For MacBook Suppo...
Innergie, a brand of Delta Electronics, has announced its official release of the world’s first USB-C adapter supporting four DC output voltages, the PowerGear USB-C 45. This true Type C adapter... Read more
13-inch and 11-inch MacBook Airs on sale for...
B&H Photo has 13″ and 11″ MacBook Airs on sale for up to $120 off MSRP as part of their Holiday sale including free shipping plus NY sales tax only: - 11″ 1.6GHz/128GB MacBook Air: $819 $90 off... Read more
13-inch MacBook Pros on sale for up to $150 o...
Take up to $150 off MSRP on the price of a new 13″ MacBook Pro at B&H Photo today as part of their Holiday sale. Shipping is free, and B&H charges NY tax only. These prices are currently the... Read more
13-inch 128GB MacBook Air now on sale for $79...
Best Buy has just lowered their price on the 2015 13″ 1.6GHz/128GB MacBook Air to $799.99 on their online store for Cyber Monday. Choose free shipping or free local store pickup (if available). Sale... Read more
Best Buy lowers 13-inch MacBook Pro prices, n...
Best Buy has lowered prices on select 13″ MacBook Pros this afternoon. Now save up to $200 off MSRP for Cyber Monday on the following models. Choose free shipping or free local store pickup (if... Read more
Cyber Monday: Apple MacBooks on sale for up t...
Apple resellers have MacBook Pros, MacBook Airs, and MacBooks on sale for up to $250 off MSRP for Cyber Monday 2015. The following is a roundup of the lowest prices available for new models from any... Read more
Cyber Monday: Apple Watch on sale for up to $...
B&H Photo has the Apple Watch on sale for Cyber Monday for $50-$100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - Apple Watch Sport: $50 off - Apple Watch: $50-$100 off B... Read more
Cyber Monday: 15% off Apple products, and sto...
Use code CYBER15 on Cyber Monday only to take 15% on Apple products at Target, and store-wide. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-... Read more
iPad Air 2 And iPad mini Among Top Five Black...
Adobe has released its 2015 online shopping data for Black Friday and Thanksgiving Day. The five best selling electronic products on Black Friday were Samsung 4K TVs, Apple iPad Air 2, Microsoft Xbox... Read more

Jobs Board

iOS Passbook & *Apple* Pay Engineer - A...
# iOS Passbook & Apple Pay Engineer Job Number: 36237585 Santa Clara Valley, Califo ia, United States Posted: May. 27, 2015 Weekly Hours: 40.00 **Job Summary** The Read more
*Apple* New Products Tester Needed - Apple (...
…we therefore look forward to put out products to quality test for durability. Apple leads the digital music revolution with its iPods and iTunes online store, continues Read more
Software Engineer, *Apple* Watch - Apple (U...
# Software Engineer, Apple Watch Job Number: 33362459 Santa Clara Valley, Califo ia, United States Posted: Jul. 28, 2015 Weekly Hours: 40.00 **Job Summary** Join the Read more
SW Engineer - *Apple* Music - Apple (United...
# SW Engineer - Apple Music Job Number: 40899104 San Francisco, Califo ia, United States Posted: Aug. 18, 2015 Weekly Hours: 40.00 **Job Summary** Join the Android Read more
Sr Software Engineer *Apple* Pay - Apple (U...
# Sr Software Engineer Apple Pay Job Number: 44003019 Santa Clara Valley, Califo ia, United States Posted: Nov. 13, 2015 Weekly Hours: 40.00 **Job Summary** Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.