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

calibre 2.69.0 - Complete e-book library...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more
Evernote 6.9.1 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
jAlbum Pro 13.5 - Organize your digital...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. You can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly... Read more
jAlbum 13.5 - Create custom photo galler...
With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly, with pro results - Simply drag and drop photos into groups, choose a design... Read more
Google Chrome 53.0.2785.143 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more
Chromium 53.0.2785.143 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. Version 53.0.2785.143: [Security Fix] High CVE-2016-... Read more
QuickBooks 2015 R8 - Financi...
Save 20% on QuickBooks Pro for Mac today through this special discount link QuickBooks 2015 helps you manage your business easily and efficiently. Organize your finances all in one place, track... Read more
Sierra Cache Cleaner 11.0.1 - Clear cach...
Sierra Cache Cleaner is an award-winning general purpose tool for macOS X. SCC makes system maintenance simple with an easy point-and-click interface to many macOS X functions. Novice and expert... Read more
Default Folder X 5.0.7 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click on... Read more
Safari Technology Preview 10.1 - The new...
Safari Technology Preview contains the most recent additions and improvements to WebKit and the latest advances in Safari web technologies. And once installed, you will receive notifications of... Read more

Pumped BMX 3: Beginner tips and tricks
There’s a whole lot more to Pumped BMX 3 than meets the eye. Your goal is to perform a wide array of sweet flips and tricks, but that’s easier said than done. It takes well practiced timing and coordination, and the game doesn’t really explain that... | Read more »
Cybird’s latest release - BFB Champions...
Launched in the UK in early September, BFB Champions’ newest update is loaded with great new features, and looks set to outshine the original version by taking it out of soft launch and giving it a new lease of life. | Read more »
3 apps to boost your focus
As someone who works from home, my workspace is a minefield of distraction. Cats, tasty snacks, the wind blowing past my window, that cleaning that I suddenly can’t put off any longer. If I let distraction takes its course, I find that soon half... | Read more »
Pumped BMX 3 (Games)
Pumped BMX 3 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: The final instalment of the smash hit #1 rated BMX game is here! Following on from the insane success of Pumped BMX 2, Pumped 3... | Read more »
4 games like Burly Men at Sea to inspire...
Burly Men at Sea is out today and it looks a treat. It tells the tale of three Scandinavian fishermen who leave the humdrum of their daily lives to go exploring. It’s a beautiful folksy story that unfurls as you interact with the environment... | Read more »
3 reasons you need to play Kingdom: New...
Developed by a tag team of indie developers - Thomas "Noio" van den Berg and Marco "Licorice" Bancale - Kingdom is a vibrant medieval fantasy adventure that casts players as a king or queen who must expand their empire by exploring the vasts lands... | Read more »
JoyCity have launched a brand new King o...
Great news for all of you Game of Dice fans out there - JoyCity have just released a brand new limited edition pack with a really cool twist. The premise of Game of Dice is fairly straightforward, asking you to roll dice to navigate your way around... | Read more »
Burly Men at Sea (Games)
Burly Men at Sea 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Burly Men at Sea is a folktale about a trio of large, bearded fishermen who step away from the ordinary to seek adventure. | Read more »
3 tips for catching the gnarliest waves...
Like a wave breaking on the shore, Tidal Rider swept its way onto the App Store charts this week settling firmly in the top 10. It’s a one-touch high score-chaser in which you pull surfing stunts while dodging seagulls and collecting coins. The... | Read more »
The beginner's guide to destroying...
Age of Heroes: Conquest is 5th Planet Games’ all new turn-based multiplayer RPG, full of fantasy exploration, guild building, and treasure hunting. It’s pretty user-friendly as far as these games go, but when you really get down to it, you’ll find... | Read more »

Price Scanner via

CAZE Annouces New Zero 5 Case for Jet Black i...
Hong Kong basd CAZE has announced Zero 5 case for iPhone 7/ 7 Plus, one of the world’s thinnest clear hard cases, measuring just 0.5 millimeters. CAZE has been producing and improving the Zero 5... Read more
Nest Egg Inventory App for iOS Offers Conven...
Campbell, California based Winprogger LLC has announced the release and immediate availability of Nest Egg – Inventory 4.1.22, an important update to their easy-to-use, yet comprehensive inventory... Read more
Factor4, LLC Launches Apple iOS and Android G...
Factor4, LLC, which offers gift and loyalty services to the SMB marketplace, has released free mobile applications that enable merchants to process via all Apple and Android devices. The Apple and... Read more
15-inch Retina MacBook Pros on sale for $200...
B&H Photo has 15″ Retina Apple MacBook Pros on sale for $200 off MSRP. Shipping is free, and B&H charges NY tax only: - 15″ 2.2GHz Retina MacBook Pro: $1799 $200 off MSRP - 15″ 2.5GHz Retina... Read more
Apple refurbished iMacs available for up to $...
Apple has Certified Refurbished 2015 21″ & 27″ iMacs available for up to $350 off MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are available: - 21″ 3.... Read more
Check Apple prices on any device with the iTr...
MacPrices is proud to offer readers a free iOS app (iPhones, iPads, & iPod touch) and Android app (Google Play and Amazon App Store) called iTracx, which allows you to glance at today’s lowest... Read more
Apple price trackers, updated continuously
Scan our Apple Price Trackers for the latest information on sales, bundles, and availability on systems from Apple’s authorized internet/catalog resellers. We update the trackers continuously: - 15″... Read more
Apple refurbished 2016 13-inch MacBook Airs a...
Apple has Certified Refurbished 2016 13″ MacBook Airs available starting at $849. An Apple one-year warranty is included with each MacBook, and shipping is free: - 2016 13″ 1.6GHz/8GB/128GB MacBook... Read more
1.4GHz Mac mini on sale for $449, save $50
Adorama has the 1.4GHz Mac mini on sale for $50 off MSRP including free shipping plus NY & NJ sales tax only: - 1.4GHz Mac mini (Apple sku# MGEM2LL/A): $449 $50 off MSRP To purchase a mini at... Read more
Apple refurbished 2015 13-inch MacBook Airs a...
Apple has Certified Refurbished 2015 13″ MacBook Airs available starting at $759. An Apple one-year warranty is included with each MacBook, and shipping is free: - 2015 13″ 1.6GHz/4GB/128GB MacBook... Read more

Jobs Board

Systems Architecture Prototyping - *Apple*...
Changing the world is all in a day's work at Apple . If you love innovation, here's your chance to make a career of it. You'll work hard. But the job comes with more Read more
*Apple* Retail - Multiple Positions- Akron,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Hardware Design Validation Engineer - *Apple...
Changing the world is all in a day's work at Apple . If you love innovation, here's your chance to make a career of it. You'll work hard. But the job comes with more Read more
Systems Architecture Prototyping - *Apple*...
Changing the world is all in a day's work at Apple . If you love innovation, here's your chance to make a career of it. You'll work hard. But the job comes with more Read more
*Apple* Retail - Multiple Positions- South B...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.