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

iMazing 2.1.8 - Complete iOS device mana...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
Civilization VI 1.0.2 - Next iteration o...
Sid Meier’s Civilization VI is the next entry in the popular Civilization franchise. Originally created by legendary game designer Sid Meier, Civilization is a strategy game in which you attempt to... Read more
TurboTax 2016 - Manage your 2016 U.S. ta...
TurboTax guides you through your tax return step by step, does all the calculations, and checks your return for errors and overlooked deductions. It lets you file your return electronically to get... Read more
Microsoft Office 2016 15.30 - Popular pr...
Microsoft Office 2016 - Unmistakably Office, designed for Mac. The new versions of Word, Excel, PowerPoint, Outlook and OneNote provide the best of both worlds for Mac users - the familiar Office... Read more
FotoMagico 5.3 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
Acorn 5.6.1 - Bitmap image editor.
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Dash 3.4.3 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
Microsoft Remote Desktop 8.0.37 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
Macs Fan Control - Monitor and c...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
MacFamilyTree 8.1.3 - Create and explore...
MacFamilyTree gives genealogy a facelift: modern, interactive, convenient and fast. Explore your family tree and your family history in a way generations of chroniclers before you would have loved.... Read more

Stickman Surfer rides in with the tide t...
Stickson is back and this time he's taken up yet another extreme sport - surfing. Stickman Surfer is out this Thursday on both iOS and Android, so if you've been following the other Stickman adventures, you might be interested in picking this one... | Read more »
Z-Exemplar (Games)
Z-Exemplar 1.4 Device: iOS Universal Category: Games Price: $3.99, Version: 1.4 (iTunes) Description: | Read more »
5 dastardly difficult roguelikes like th...
Edmund McMillen's popular roguelike creation The Binding of Isaac: Rebirth has finally crawled onto mobile devices. It's a grotesque dual-stick shooter that tosses you into an endless, procedurally generated basement as you, the pitiable Isaac,... | Read more »
Last week on PocketGamer
Welcome to a weekly feature looking back on the past seven days of coverage on our sister website, PocketGamer. It’s taken a while for 2017 to really get going, at least when it comes to the world of portable gaming. Thank goodness, then, for... | Read more »
ROME: Total War - Barbarian Invasion set...
To the delight of mobile strategy fans, Feral Interactive released ROME: Total War just a few months ago. Now the game's expansion, Barbarian Invasion is marching onto iPads as a standalone release. [Read more] | Read more »
Yuri (Games)
Yuri 1.0 Device: iOS iPhone Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: It's night. Yuri opens his eyes. He wakes up in a strange forest.The small, courageous explorer rides on his bed on casters in this... | Read more »
Space schmup Xenoraid launches on the Ap...
10Tons Xenoraid is out today on the App Store, bringing some high-speed space action to your mobile gadgets just in time for the weekend. The company's last premium title, another sci-fi game titled Neon Chrome, did quite well for itself, so... | Read more »
Star Wars: Force Arena Beginner's G...
Star Wars: Force Arena joined the populous ranks of Star Wars games on mobile today. It's a two-lane MOBA starring many familiar faces from George Lucas's famed sci-fi franchise. As with most games of this nature, Force Arena can be a little obtuse... | Read more »
Mysterium: The Board Game (Games)
Mysterium: The Board Game 1.0 Device: iOS Universal Category: Games Price: $6.99, Version: 1.0 (iTunes) Description: The official adaptation of the famous board game Mysterium! | Read more »
Sonny (Games)
Sonny 1.0.4 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.4 (iTunes) Description: Reimagined for iOS, cult-hit RPG Sonny brings challenging turn-based combat that requires strategy and mastery of each new skill to... | Read more »

Price Scanner via

Laptop Market – Flight To Quality? – The ‘Boo...
Preliminary quarterly PC shipments data released by Gartner Inc. last week reveal an interesting disparity between sales performance of major name PC vendors as opposed to that of less well-known... Read more
IBM and Bell Transform Canadian Enterprise Mo...
IBM and Bell Canada have announced they are joining forces to offer IBM MobileFirst for iOS market-ready enterprise applications for iPad, iPhone or Apple Watch. Bell, Canada’s largest communications... Read more
Otter Products is Closing… For a Day of Givin...
On Thursday, Feb. 9, Otter Products is closing doors to open hearts. In partnership with the OtterCares Foundation, the company is pausing operations for a day so all employees can volunteer with... Read more
15-inch 2.2GHz Retina MacBook Pro on sale for...
Amazon has 2015 15″ 2.2GHz Retina MacBook Pros (MJLQ2LL/A) available for $1799.99 including free shipping. Apple charges $1999 for this model, so Amazon’s price is represents a $200 savings. Read more
Back in stock: Apple refurbished 13-inch Reti...
Apple has Certified Refurbished 2015 13″ Retina MacBook Pros available for up to $360 off original MSRP, starting at $1099. An Apple one-year warranty is included with each model, and shipping is... Read more
CalcTape for macOS 1.2 Adding Machine App for...
schoettler Software has announced CalcTape 1.2, an update to their desktop calculator for macOS. When it comes to adding long columns of numbers, doing complex calculations or playing around with... Read more
New MacBooks And MacBook Pros WIth Kaby Lake...
Digitimes’ Joseph Tsai cites a Chinese-language Economic Daily News (EDN) report that unnamed market watchers are predicting Apple MacBook shipments to grow 10 percent in 2017, and projecting 15... Read more
New 2016 13-inch MacBook Pros on sale for up...
B&H Photo has the new 2016 13″ MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.9GHz/512GB Touch Bar MacBook Pro... Read more
New 15-inch Touch Bar MacBook Pros in stock a...
B&H Photo has the new 2016 15″ Apple Touch Bar MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
Opera Announces Neon Concept Browser For Mac
Opera is inviting users to get a glimpse of what Opera for computers could become with its Opera Neon browser concept. Each Opera Neon feature is described as “an alternate reality” for the Opera... Read more

Jobs Board

*Apple* Retail - Multiple Positions (Multi-L...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* & PC Desktop Support Technician...
Apple & PC Desktop Support Technician job in Stamford, CT We have immediate job openings for several Desktop Support Technicians with one of our most well-known Read more
*Apple* macOS Systems Integration Administra...
…most exceptional support available in the industry. SCI is seeking an Junior Apple macOS systems integration administrator that will be responsible for providing Read more
*Apple* Premier Retailer - Service Technicia...
DescriptionSimply Mac is the largest premier retailer for Apple products and solutions. At Simply Mac we are all Apple , all the time. Same products. Same prices. Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.