Class Simulation

SIMULA and simulation

There is a widespread belief that SIMULA is a simulation language. This is the result of a misunderstanding which confuses the reason for the development of the language with its range of application. SIMULA was developed as a language with features which allowed certain kinds of simulation to be performed more easily on computers. These features were not then available in other languages. Some, like hierarchical types and virtual specification, are still almost unique to SIMULA.

Because it was developed with one application in mind, does not mean that it was not intended as a general purpose language. Its authors always aimed at a design with the widest range of use. The idea of a common base language, referred to earlier, was central to their purpose. The language called SIMULA is extremely powerful and has proved suited to many areas of programming. Its recent evolution has takem it further in this direction.

The area where SIMULA reveals the background of its designers is not in the language itself, but in the standard packages which it provides. We have seen SIMSET, which is useful in all sorts of programs. The other package builds on SIMSET to provide tools for discrete event simulation. This package is called SIMSET class SIMULATION.

It is not the purpose of this book to describe how discrete event simulation works. If you are unfamiliar with it, consult the bibliography for references. You should still be able to follow the examples in this chapter, since they are intended as demonstrative of the features of class SIMULATION, not of the underlying theory.

A simple example

Example 19.1 introduces the two most important features of class SIMULATION, the real procedure Time and Link class Process. These are combined to produce a very simple model of a man operating a machine.

Example 19.1: Simple simulation using Time and Process.

   SIMULATION
   begin
      integer Count;

      Process class Man(Mill); ref(Machine) Mill;
      begin
         while Time<400 do
         begin
            OutText("Loading starts");
            OutFix(Time,2,10);
            OutImage;   ! Report made;
            Count := Count + 1;   ! Keep a tally;
            Hold(5.0);
            Mill.Components := Mill.Components + 50;   ! Load up;
            Activate Mill;   ! Restart machine;
            while Mill.Components>0 do Hold(0.5);   ! Check regularly;
            Cancel(Mill);   ! Switch off;
            Hold(10.0);   ! Unloading takes longer;
            OutText("Unloading finishes");
            OutFix(Time,2,10);
            OutImage;   ! Report made;
         end--of--loop;
         Passivate
      end++of++Man;
      
      Process class Machine;
      begin
         integer Components;
         while True do
         begin
            OutText("Machine starts");
            OutFix(Time,2,10);
            OutImage;
            while Components>0 do
            begin
               Hold(2.0);   ! Machining time for one component;
               Components := Components - 1
            end..of..inner..loop;
            Passivate
         end--of--loop
      end++of++Machine;
      
      ref(Man) Worker;
      Worker :- new Man(new Machine);
      Activate Worker;
      OutText("Count = "); OutInt(Count,4); OutImage;
      Hold(800);
      OutText("Simulation ends"); OutImage
   end**of**simulation
Process class Man shows the actions of the man. He performs four basic actions. He loads the machine with a new supply of components. He starts the machine. He checks at regular intervals to see if the machine has finished. He unloads the machine when it is finished.

Each action involves two things. The first is some representation of what the action achieves, such as adding 50 to the attribute component of the machine that he is operating, to represent loading it. The second is some representation of the time taken for this. In the case of loading, this is a call of procedure Hold (5.0), where 5.0 is the time taken to complete the loading.

The starting of the machine involves specifying that the machine is to become active. Since we are dealing with coroutines this implies that the man will cease to be active at the same moment. The time element specifies that the activation is instantaneous. There are other scheduling possibilities when reactivating another Process, as we shall see.

The unloading involves resetting the Product attribute of the machine to zero. This also involves a Hold to represent time taken.

A third, optional element of the representation of an action is a report from the program. This can be made before or after an action, or both. Clearly the program would have no point if it did not report on what was happening.

An alternative to printing every time an action is performed is to keep a count of the number of times it is carried out. Other statistics can also be accumulated. In the program, the number of times the machine is loaded is counted and printed at the end.

What is happening?

The coroutines in the program are both subclasses of Process. This prefixing class contains a ref attribute which can link each Process object to an object of a class called EventNotice. When a Process object is scheduled it is linked to and EventNotice object and the EventNotice is placed in a list called the sequencing set.

Each EventNotice has a real attribute called EvTime. This is the time at which the associated Process coroutine is to be restarted. The list of EventNotices is in order of increasing time. The Process whose EventNotice has the lowest EvTime is the currently active Process and its EvTime is the current time, which is returned by real procedure Time.

Diagram 19.1 shows the sequence of events in our simple program as changes in the sequencing set. This list is shown as a simple SIMSET Set, but is not necessarily held in that form. A tree list is often used.

Figure 19.1: Starting and ending events in example 19.1.

a) Time 0.0. SIMULATION activates MAIN.

         Current
      ---------------
      I    MAIN     I
      I EvTime= 0.0 I
      ---------------

b) Time 0.0. MAIN activates Worker.

          Current
      ---------------     ---------------
      I    Worker   I --> I    MAIN     I
      I EvTime=0.0  I <-- I EvTime= 0.0 I
      ---------------     ---------------

c) Time 0.0. Worker holds for 5.0.

          Current
      ---------------     ---------------
      I    MAIN     I --> I    Worker   I
      I EvTime=0.0  I <-- I EvTime= 5.0 I
      ---------------     ---------------

d) Time 0.0. MAIN holds for 800.0.

          Current
      ---------------     ---------------
      I    Worker   I --> I    MAIN     I
      I EvTime= 5.0 I <-- I EvTime= 800 I
      ---------------     ---------------

e) Time 5.0. Mill holds for 2.0.

          Current
      ---------------     ---------------     ---------------
      I    Worker   I --> I    Mill     I --> I    MAIN     I
      I EvTime= 5.0 I <-- I EvTime= 7.0 I <-- I EvTime= 800 I
      ---------------     ---------------     ---------------

f) Time 5.0. Worker holds for 0.5.

          Current
      ---------------     ---------------     ---------------
      I    Worker   I --> I    Mill     I --> I    MAIN     I
      I EvTime= 5.5 I <-- I EvTime= 7.0 I <-- I EvTime= 800 I
      ---------------     ---------------     ---------------

g) After numerous events: Time >= 400.0. Worker passivates .

          Current
      ---------------
      I    MAIN     I
      I EvTime= 800 I
      ---------------

h) Time 800. MAIN terminates.
Note the effects of Hold, Cancel, Passivate and Activate.

Hold
adds the specified amount to the EvTime of the EventNotice for that Process. Since the list is EvTime ordered, the EventNotice is shifted to its new place in the list. This will result in the next EventNotice's Process becoming active if the new place is not still first in the list.

Activate
has the effect of moving the EventNotice of the specified Process to the head of the list. There are other forms of this statement which will move it to other places in the list.

Cancel
removes the EventNotice for the specified Process from the sequencing set. When Man uses Cancel he stops the machine referred to by Mill.

Passivate
cancels the current Process.

Link class Process

After an informal example, here is a more rigorous definition of class Process. Many of its internal attributes are inaccessible to programs, including the reference to its EventNotice. It may only be manipulated by the features described from here on.

All the visible attributes of Process are type procedures, giving information about the current state of the Process object. The possible state are:

Active
the Process is the first in the sequencing set.

Suspended
the Process is in the sequencing set, but is not the first in the list.

Passive
the Process is not in the sequencing set, but its actions have not reached the final @i(end) in its class body. It may be re-scheduled.

Terminated
the Process has passed through the final @i(end) of its class body. This automatically removes it from the sequencing set. It cannot be re- scheduled.

Idle
the Process is either Passive or Terminated, i.e. it is not in the sequencing set. This state does not define whether the Process may be re- scheduled.

State attributes

Boolean procedure Idle
returns True if the Process is not in the sequencing set. Otherwise it returns false. This corresponds to the state described in 5 above.

Boolean procedure Terminated
returns the value true if the Process has reached its final end. This corresponds to the state described as Terminated above.
There is no simple way of discovering whether or not a Process is passive. The procedures Idle and Terminated must be used in combination, as follows
         passive is equivalent to Idle and not Terminated.

Other attributes

Long real procedure EvTime
will return the simulated time at which this Process is currently scheduled to become active. If this Process is currently Active, EvTime has the same value as the current simulated time. If this process is Idle, calling EvTime will cause a runtime error.

ref(Process) procedure NextEv
returns a pointer to the next Process in the sequencing set. If there is no such Process or if that process is Idle, it returns none.

Scheduling Processes

When a process is created, using new, it enters the passive state, calling Detach. It will not begin the actions defined by the programmer in the sub- class or -classes of Process, until it is scheduled and becomes active, i.e. is placed in the sequencing set and reaches the head of it.

The activate statement

It is not possible to write class SIMULATION in SIMULA, because, as a prefixing class, it cheats. It contains an extra form of statement which is not allowed in SIMULA programs not prefixed by SIMULATION. When we, as ordinary users of SIMULA, write classes for use as prefixes in this way we are not able to invent new language features in this way. We can only build on what is already there.

This special statement is called an activation statement. It can only be used in SIMULA blocks or classes prefixed by class SIMULATION. Its task is to set the event time of a Process and insert it into the sequencing set, known as scheduling the Process.

Simple activate

The activate statement has a number of forms. We have already used the simplest in example 19.1.
      activate Mill
This form makes the specified Process object the currently active one. This means giving it an event time equal to the currently simulated time and placing it in the sequencing set in front of the currently active Process.

Note that the previously current process remains in the sequencing set, with its event time unchanged and one behind the newly activated Process.

Activate before and after

A second form specifies a position in the sequencing set relative to an object in the set. Two specifiers are provided, before and after. Their use is shown below.
      activate Mill6 before Lathe2
will place Process object Mill6 in front of Lathe2 in the sequencing set. Lathe2 may be anywhere in the sequencing set. Mill6 will be given the same event time as Lathe2.
      activate Mill6 after Lathe2
will place Process object Mill6 behind Lathe2 in the sequencing set, giving it the same event time.

In either case, if Lathe2 happened not to be in the sequencing set, nothing would be done to Mill6.

Activate with a delay

A third form allows a Process object to be activated a specified time after the current simulated time. Its simple form is shown by
      activate Mill6 delay 6.5
which will give Mill6 an event time equal to the current simulated time plus 6.5. it is then added to the sequencing set at the appropriate place. If one or more Process objects are already present in the sequencing set with the same event time, the newly scheduled one will be placed after them.

If it is wished to place a newly scheduled Process object in front of any which are already in the sequnecing set with the same event time, an additional keyword specifier is used, as in

      activate Mill6 delay 6.5 prior

Activate at

Finally it is possible to specify an event time absolutely rather than relative the current simulated time. This has the same variants as when delay is used.
      activate Mill6 at 10.2
The statement above gives Mill6 an event time of 10.2 and adds it to the sequencing set. If other Process objects are already present with the same event time, it is added behind them. To force it to be inserted in front of any such objects, the final version of the activate statement must be used, as in the example below.
      activate Mill6 at 10.2 prior

Reactivate

activate statements have no effect if the Process is not already a passive member of the sequencing set. If you wish to schedule an object regardless of whether it is active, passive or suspended, you must use a reactivate statement. (Attempts to schedule terminated objects will cause runtime errors to be reported.)

The reactivate statement has exactly the same forms as the activate statement, with the keyword activate replaced by the keyword reactivate. Equivalent statements to those used above are

       reactivate Mill6;
       reactivate Mill6 before Lathe2;
       reactivate Mill6 after Lathe2;
       reactivate Mill6 delay 6.5;
       reactivate Mill6 delay 6.5 prior;
       reactivate Mill6 at 10.2;
       reactivate Mill6 at 10.2 prior;

New keywords in activation and reactivation

The words activate, reactivate, delay, prior, at, before and after are all key words in blocks and classes prefixed by class SIMULATION. Using them elsewhere in a SIMULA program will result in a compiler reported error.

Other scheduling mechanisms

Activation explicitly places Process objects in the sequencing set, in accordance with the implicit or explicit scheduling cxriteria given. Identical effects can often be produced by different forms.

There are other scheduling mechanisms and scheduling support mechanisms, all in the form of procedures. These are not language extensions and do not introduce new keywords. Thus they could, in theory, be written in SIMULA.

None of the following procedures are attributes of Process and so they are all used without remote accessing.

ref(Process) procedure Current
returns a reference to the currently active Process. Since this contains the sequence of statements currently being executed, its EvTime attribute defines the current simulated time. In fact, all actions inside a class SIMULATION block can only occur when the object in which they are contained is Current or when they are in the main block.

long real procedure Time
returns the current simulated time, which equals Current.EvTime.

procedure Hold
has a single, long real parameter. It increases the event time at which the Process in which it is called by the amount of this parameter and moves it to the appropriate place in the sequencing set. If the new event time is greater than the event time of the second Process in the set,this second Process now becomes Current. Hold is used to specify the passage of time in a process which is being modelled as a Process object. This can corresponding to a period of activity or a period of waiting.

procedure Passivate
removes the Process object in which it is called from the sequencing set. This makes the object passive. It represents the start of an inactive, waiting period. Unlike Hold, it does not specify a duration for this period. The object may only be restarted by an Activate or Reactivate statement outside its own body, i.e. by the actions of another Process. This includes the main program block, as we shall see later.

procedure Wait
has a single ref(Head) parameter. The Process in which it is called is removed from the sequencing set, in the same way as by Passivate. The Process object is then added to the list represented by the Set whose Head is passed as the parameter to Wait. It is inserted at the end of this Set. This represents the Process joining a queue, where it waits, passively. When it reaches the front of this queue or is selected from it by some other criterion it may be rescheduled, but again, only from outside itself.

procedure Cancel
has a single ref(Process) parameter. It will remove the specified Proces object from the sequencing set and make it passive. It differs from Passivate and Wait, in that any Process object may be passivated by another, not just by itself. It represents a Process making a decision to halt another.

A further example of SIMULATION - a receptionist

Example 19.2 shows a more complex model, using some of the features described above. In particular it shows the use of Wait to represent queuing.

Example 19.2: An employment office queuing model.

   SIMULATION
   begin
   
      ref(Head) ReceptionistQ, InterviewQ1, InterviewQ2;
      integer I, Manual;
      
      Process class Interviewer(Title, MyQueue); text Title;
                                            ref(Head) MyQueue;
      begin
         ref(Link) Next;      
         inspect MyQueue do
            while True do ! Indefinite loop;
            begin
               if not Empty then
               begin
                  Hold(3.5); ! Interview time taken as 3.5 minutes;
                  Next :- First;
                  Next.Out;
                  activate Next after Current;
                  Hold(3.0);   ! 3 minutes to clear desk;
               end else
               begin
                  Hold(5.0);   ! Wait 5 minutes before checking queue again;
               end--of--one--sequence
            end++of++loop
            
      end==of==Interviewer;
      
      Process class JobHunter(SkillCategory); integer SkillCategory;
      begin
         OutText("Job hunter "); OutInt(SkillCategory,4);
         OutText(" joins receptionist queue at time "); OutFix(Time,4,8);
         OutImage;
         Wait(ReceptionistQ);
         OutText("Job hunter "); OutInt(SkillCategory,4);
         OutText(" joins interview queue"); OutImage;
         Hold(1.0);   ! 1 minute to join new queue;
         if SkillCategory=Manual then Wait(InterviewQ1)
                                 else Wait(InterviewQ2);
         OutText("Job hunter "); OutInt(SkillCategory,4);
         OutText(" leaves employment office"); OutImage
      end==of==JobHunter;

      Process class Receptionist;
      begin
         ref(Link) Customer;
         while True do
         begin
            if not ReceptionistQ.Empty then
            begin
               Hold(2.0);
               Customer :- ReceptionistQ.First;
               Customer.Out;
               activate Customer;
            end else Hold(1.0)
         end
      end==of==Receptionist;


      Manual := 1;
      ReceptionistQ :- new Head;
      InterviewQ1 :- new Head;
      InterviewQ2 :- new Head;
      activate new Receptionist;
      activate new Interviewer("Manual",InterviewQ1);
      activate new Interviewer("Skilled",InterviewQ2);
      for I := 1,2,2,1 do
      begin
         Activate new JobHunter(I);
         Hold(2.0)
      end;
      Hold(100)
   end**of**program
The model shows an employment office, with two interviewers and a shared receptionist. New arrivals looking for work must register with the receptionist and then wait in one of the queues (lines), according to their desired type of employment. When the job hunter has been interviewed, he leaves.

Job hunters, the receptionist and the two interviewers are all active participants and so are represented as Process sub-class objects. Each has appropriate attributes and actions, including reporting on their actions, defined in the body of their sub-class.

Arrivals are parameterised, allowing job hunters with different skills to be generated from the same basic class. These attributes will determine which interviewer they see.

The queues are represented by sets and arrivals join them by calling Wait with the Set appropriate to their skill or the initial queue for the receptionist as parameter. The receptionist and the two interviewers check the queue of arrivals waiting to see them and take the first member of the Set, if any, each time they have completed an interview. They then reschedule this Process, allowing it to move to the next stage in its job search.

The delays are all given as real constants in this example. To produce a more realistically random effect, random drawing procedures could be used to provide delay values, according to appropriately chosen distributions. Those provided in SIMULA are outlined briefly in chapter 20. Others are usually available from standard libraries on particular systems, such as the NAG library.

The Main Process

We have already implied that the block prefixed by class SIMULATION may be regarded as a Process, in that it can Hold, be the Current object etc. Indeed for symmetry it is often useful to be able to schedule the prefixed block in the same way as user defined Process objects. Within a block prefixed by SIMULATION, usually called the main block for the simulation model, all the actions of a Process object are legal.

To achieve this class SIMULATION includes a hidden declaration of a sub-class of Process, called Main_Program. This is used to create the main block's representative in the sequencing set. The body of this sub-class consists of a single statement, as shown below.

       Process class Main_Program;
       begin
          while True do Detach;
       end--of--Main_Program;
As the last of its initialisation actions, class SIMULATION creates a Main_Program object and schedules it for simulated time 0.0. This means that when the actions of the prefixed block commence, they follow a call of Detach inside this Main_Program object. This object is still at the front of the sequencing set and remains the currently active Process, but its Detach causes the statements in the prefixed block to be performed. Thus the currently active Process object uses the actions in the prefixed block as its own.

If Hold is called inside this block, it will act on the currently active Process object, i.e. the Main_Program object, rescheduling it for a later event time. This will cause the currently executing actions to leave the prefixed block's statements and enter those of the body of the new first in the sequencing set.

When the Main_Program object again reaches the front of the sequencing set and becomes active, it immediately calls Detach again. This takes it back to the prefixed block, at the instruction immediately following the one which caused the Main_Program object to be rescheduled, in this case Hold. Thus the Main_Program object again uses the actions of the prefixed block as its own and the effect of rescheduling it is seen to be equivalent to rescheduling the prefixed block.

This explains the method used to set the period of time covered by all or part of a simulation program. Both out examples so far contain a call on Hold in the main program block. This follows the setting up and starting of the other Process objects and puts the Main_Program object at the end of the sequencing set, with an event time equal to the desired length of time to be simulated. When this object reaches the front of the sequencing set it detaches back to the program block, allowing final reporting and termination of the program.

Where a simulation consists of several phases, it is possible to use several Holds in the program block. Each represents a particular part of the period being simulated.

If Passivated were to be called instead of Hold in the program block, the Main_Program block would never be re-entered and the simulation would continue for as long as any Process object remained in the sequencing set. Such a simulation's duration would be hard to predict, possibly running indefinitely. Normally Hold is used to fix a limit to the duration.

Warning over the use of Detach and Resume

The Process objects in a SIMULATION program should only be scheduled by using the mechanisms described in this chapter. All of these procedures depend on the use of Detach and Resume internally to achieve the correct effects, as we have seen with Main_Program. The Process objects exist as co-routines.

If you attempt to Detach or Resume a Process object explicitly, the effects could be disastrous for the scheduling mechanisms of SIMULATION. Detach and Resume should never be used in SIMULATION programs.

Utility procedure Accum

SIMULATION provides one further procedure, which is designed to be used for collecting certain information over a period of time during a simulation program. If you are not a mathmetician you may skip this section. If you are the following formal description may be of interest.

The procedure Accum is used to accumulate the "system time integral" of a real variable, C. This is regarded as a step function of simulated time. Its integral is collected in real variable A. B is the time of the last update and D the current increment. Accum is given in full.

       procedure Accum (A,B,C,D); name A,B,C;
                                  long real A,B,C,D;
       begin
          A:=A + C * (Time - B);
          B:=Time;
          C:=C + D;
       end ** of ** Accum;

A final example

Example 19.3 is another simulation using the features outlined in this chapter. It shows a model of an office. Documents are written by writers who pass them to the typing pool. The documents are typed by typists who pass them to the photocopier. Copies are made and passed to the mail room.

Example 19.3: Simulation with two time periods.

   SIMULATION
   begin

      procedure Report;
      begin
         OutText("   *** Report ***"); OutImage;
         OutInt(Count,6); OutText(" documents printed, at time");
         OutFix(Time,2,8); OutImage
      end--of--Report;

      Process class Writer;
      begin
         ref(Typer) Typist;
         ref(Document) Doc;
         while True do
         begin
            Hold(8.0);
            Doc :- new Document;
            Typist :- TypingPool.First;
            Typist.Out;
            activate Typist
         end
      end--of--Writer;

      Process class Typer;
      begin
         Wait(TypingPool);
         while True do
         begin
            Hold(4.0);
            activate PhotoCopier;
            Wait(TypingPool);
         end
      end--of--Typer;

      Process class Copier;
      begin
         while True do
         begin
            Hold(1.0);
            Count := Count + 1;
            OutText("Document printed at ");
            OutFix(Time,2,10);
            OutImage;
            Passivate
         end
      end--of--Copier;

      class Document;;

      ref(Head) TypingPool;
      ref(Copier) PhotoCopier;
      integer I, Count;

      TypingPool :- new Head;
      for I := 1 step 1 until 10 do activate new Typer;
      PhotoCopier :- new Copier;
      activate new Writer delay 2.0;
      activate new Writer delay 4.5;
      Hold(100);
      Report;
      Hold(100);
      Report
   end++of++program
The model runs for 100 time units and then reports. It then restarts for a further 100 time units, reports and stops.

Note that the main program makes two holds in this time. It is often useful to create models which report at regular intervals, not just at the end. It may also be useful to change some factors at certain points. This may represent day and night, changes in weather, the seasons, rest breaks or many other alterations in the conditions under which the model is operating.

Summary

This chapter has outlined very briefly the working of the standard prefixing class, SIMSET class SIMULATION. It has not dealt with the theory of simulation.

The class Process has been explained.

The procedures for scheduling and enquiring about the state of the simulation have been explained.

The mechanism for scheduling the main program block has been outlined.