Smalltalk80LanguageImplementation:Chapter 22

Chapter 21 Probability Distributions

Probability Distributions

A simulation is a representation of a system of objects in a real or fantasy world. The purpose of creating a computer simulation is to provide a framework in which to understand the simulated situation, for example, to understand the behavior of a waiting line, the workload of clerks, or the timeliness of service to customers. Certain kinds of simulations are referred to as "counter simulations." They represent situations for which there are places or counters in which clerks work. Customers arrive at a place in order to get service from a clerk. If a clerk is not available, the customer enters a waiting line. The first customer in the line is serviced by the next available clerk. Often a given simulation has several kinds of places and several customers, each with an agenda of places to visit. There are many examples of such situations: banks, car washes, barber shops, hospitals, cafeterias, airports, post offices, amusement parks, and factories. A computer simulation makes it possible to collect statistics about these situations, and to test out new ideas about their organization.

The objects that participate in a counter simulation operate more or less independently of one another. So, it is necessary to consider the problem of coordinating or synchronizing the activities of the various simulated objects. They typically coordinate their actions through the mechanism of message passing. Some objects, however, must synchronize their actions at certain critical moments; some objects can not proceed to carry out their desired actions without access to specific resources that may be unavailable at a given moment. The Smalltalk-80 system classes, Process, Semaphore, and SharedQueue, provide synchronization facilities for otherwise independent activities. To support a general description of counter simulations, mechanisms are needed for coordinating

• the use of fixed-size resources,
• the use of fluctuating resources, and
• the appearance of simultaneity in the actions of two objects.

Fixed resources can either be consumable or nonconsumable. For example, jelly beans are consumable, fixed resources of a candy store; books are non-consumable resources of a library. Fluctuating resources are typically referred to as renewable or producer/consumer synchronized. A store can model its supply of jelly beans as a fluctuating resource because the supply can be renewed. One can also imagine a resource that is both renewable and nonconsumable. Such a resource might be modeled in a simulation of car rentals: cars are renewable resources since new ones are manufactured and added to the available supply of cars to rent; the cars are also nonconsumable because a rented car is returned to the dealer for use by other customers. Actually, most nonconsumable resources are consumable, for example, library books eventually become too tattered for continued circulation; the rental cars eventually get junked. "Nonconsumable" means, minimally, that they are not consumed during the period of interest in the simulation.

When the actions of two objects in a simulation must be synchronized to give the appearance of carrying out a task together, the two objects are said to be in a server/client relationship. For example, a doctor needs the cooperation of the patient in order to carry out an examination. The server is a coordinated resource; it is a simulation object whose tasks can only be carried out when one or more clients request the resource.

An important aspect of simulations is that they model situations that change over time; customers enter and leave a bank; cars enter, get washed, get dried, and leave a car wash; airplanes land, unload passengers, load passengers, and take off from airports. It is often the case that these activities are time-related; at certain times or with certain intervals of time, events occur. Therefore, actions have to be synchronized with some notion of time. Often this notion of time is itself simulated.

There are a number of ways in which to represent the actions of simulated objects with respect to real or simulated time. In one approach, the clock runs in its usual manner. At each tick of the clock, all objects are given the opportunity to take any desired action. The clock acts as a synchronization device for the simulation, providing the opportunity to give the appearance of parallelism since the clock waits until all actions appropriate at the given time are completed. Often, no actions will take place at a given tick of the clock.

Alternatively, the clock can be moved forward according to the time at which the next action will take place. In this case, the system is driven by the next discrete action or event scheduled to occur. The implementation of a simulation using this approach depends on maintaining a queue of events, ordered with respect to simulated time. Each time an event is completed, the next one is taken from the queue and the clock is moved to the designated time.

The simulations presented in this chapter are based on this event-driven approach. They include simulations in which a collection of independent objects exist, each with a set of tasks to do (services or resources to obtain), and each needing to coordinate its activity's times with other objects in the simulated situation.

This chapter describes a framework in which such simulations can be developed. The class SimulationObject describes a general kind of object that might appear in a simulation, that is, one with a set of tasks to do. The message protocol of the class provides a framework in which the tasks are carried out. An instance of class Simulation maintains the simulated clock and the queue of events. The specification of the arrival of new objects into the system (objects such as customers) and the specification of resources (such as the clerks) are coordinated in this class.

The next chapter, Chapter 23, deals with ways to collect the data generated in running a simulation. Statistics gathering can be handled by providing a general mechanism in subclasses of class Simulation and/or class SimulationObject. Alternatively, each example simulation can provide its own mechanism for collecting information about its behavior.

Chapter 24 describes example simulations that make use of two kinds of synchronizations, shared use of fixed resources and shared use of fluctuating resources; Chapter 25 introduces additional support for coordination between two simulation objects--those wanting service and those providing service.

A Framework for Simulations

This section contains a description of the classes that provide the basic protocol for classes SimulationObject and Simulation. These classes are presented twice. First, a description of the protocol is given with an explanation of how to create a default example; second, an implementation of these classes is given.

Simulation Objects

Consider simulating a car wash. Major components of a car wash are washing places, drying places, paying places, washers, dryers, cashiers, and vehicles of different sorts such as trucks and cars. We can classify these components according to behavior. Major classifications are: places, where workers are located and work is performed; workers, such as washers, dryers, and cashiers; and the vehicles that are the customers of the places. These classifications might be translated into three classes of Smalltalk objects: Place, Worker, and Customer. But each of these classes of objects is similar in that each describes objects that have tasks to do--a Customer requests service, a Worker gives service, and a Place provides resources. In particular, a Place provides a waiting queue for the times when there are more customers than its workers can handle. These similarities are modeled in the superclass SimulationObject, which describes objects that appear in a simulated situation; a SimulationObject is any object that can be given a sequence of tasks to do. Each object defines a main sequence of activity that is initiated when the object enters the simulation. For example, the activities of a car in a car wash are to request a washer, wait while being washed, request a dryer, wait while being dried, pay for the service, and leave.

Class SimulationObject specifies a general control sequence by which the object enters, carries out its tasks, and leaves the simulation. This sequence consists of sending the object the messages startUp, tasks, and finishUp. Initialization of descriptive variables is specified as the response to message initialize. These messages are invoked by the method associated with startUp. Response to the messages tasks and initialize are implemented by subclasses of SimulationObject.

initialization
initialize	Initialize instance variables, if any.
simulation control startUp	Initialize instance variables. Inform the simulation that the receiver is entering it, and then initiate the receiver's tasks.
tasks	Define the sequence of activities that the receiver must carry out.
finishUp	The receiver's tasks are completed. Inform the simulation.
SimulationObject instance protocol

There are several messages that any SimulationObject can use in order to describe its tasks. One is holdFor: aTimeDelay, where the argument aTimeDelay is some amount of simulated time for which the object delays further action. The idea of this delay is to create a period of time in which the object is presumably carrying out some activity.

We call the category of these messages, the modeler's task language to indicate that these are the messages sent to a SimulationObject as part of the implementation of the message tasks.

A simulation can contain simple or static resources, like "jelly beans," that can be acquired by a simulation object. Or a simulation can consist of coordinated resources, that is, simulation objects whose tasks must be synchronized with the tasks of other simulation objects. The task language includes messages for accessing each kind of resource, either to get or to give the resource.

There are 3 kinds of messages for static resources. There are 2 messages for getting an amount of the resource named resourceName. They are

acquire: amount ofResource: resourceName
acquire: amount ofResource: resourceName withPriority: priorityInteger

There is one for giving an amount of the resource named resourceName,

produce: amount ofResource: resourceName

and one for giving up an acquired static resource,

release: aStaticResource

There are also 3 kinds of messages for coordinated resources. The message for getting the resource named resourceName (here, the resource is a SimulationObject that models a kind of customer, and the asker is a server such as a clerk) is

acquireResource: resourceName

To produce the resource named resourceName (the asker is a customer), the message is

produceResource: resourceName

and to give up an acquired resource (which is a SimulationObject whose task events can now be resumed), the message is

resume: anEvent

When a SimulationObject makes a static resource request (acquire:ofResource: or request:), it can do so by stating the level of importance of the request. The number 0 represents the least important request, successively higher numbers represent successively higher levels of importance. The message acquire:ofResource: assumes a priority level of 0; acquire:ofResource:withPriority: specifies particular levels in its third argument.

Two queries check whether a static resource is in the simulation and how much of the resource is available. These are resourceAvailable: resourceName, which answers whether or not the simulation has a resource referred to by the String, resourceName; and inquireFor: amount ofResource: resourceName, which answers whether there is at least amount of the resource remaining.

When a SimulationObject is synchronizing its tasks with that of another SimulationObject, it might be useful to know whether such an object is available. Two additional inquiry messages support finding out whether a provider or requester of a coordinated task is available--numberOfProvidersOfResource: resourceName and numberOf-RequestersOfResource: resourceName.

In addition, a message to a SimulationObject can request that the Simulation it is in stop running. This is the message stopSimulation.

task language
initialize	Initialize instance variables, if any.
holdFor: aTimeDelay	Delay carrying out the receiver's next task until aTimeDelay amount of simulated time has passed.
acquire: amount ofResource: resourceName	Ask the simulation to provide a simple resource that is referred to by the String, resourceName. If one exists, ask it to give the receiver amount of resources. If one does not exist, notify the simulation user (programmer) that an error has occurred.
acquire: amount ofResource: resourceName withPriority: priorityNumber	Ask the simulation to provide a simple resource that is referred to by the String, resourceName. If one exists, ask it to give the receiver amount of resources, taking into account that the priority for acquiring the resource is to be set as priorityNumber. If one does not exist, notify the simulation user (programmer) that an error has occurred.
produce: amount ofResource: resourceName	Ask the simulation to provide a simple resource that is referred to by the String, resourceName. If one exists, add to it amount more of its resources. If one does not exist, create it.
release: aStaticResource	The receiver has been using the resource referred to by the argument, aStaticResource. It is no longer needed and can be recycled.
inquireFor: amount ofRecsource: resourceName	Answer whether or not the simulation has at least a quantity, amount, of a resource referred to by the String, resourceName.
resourceAvailable: resourceName	Answer whether or not the simulation has a resource referred to by the String, resourceName.
acquireResource: resourceName	Ask the simulation to provide a resource simulation object that is referred to by the String, resourceName. If one exists, ask it to give the receiver its services. If one does not exist, notify the simulation user (programmer) that an error has occurred.
produceResource: resourceName	Have the receiver act as a resource that is referred to by the String, resourceName. Wait for another SimulationObject that provides service to (acquires) this resource.
resume: anEvent	The receiver has been giving service to the resource referred to by the argument, anEvent. The service is completed so that the resource, a SimulationObject, can continue its tasks.
numberOfProvidersOfResource: resourceName	Answer the number of SimulationObjects waiting to coordinate its tasks by acting as the resource referred to by the String, resourceName.
numberOfRequestersOfResource: resourceName	Answer the number of SimulationObjects waiting to coordinate its tasks by acquiring the resource referred to by the String, resourceName.
stopSimulation	Tell the simulation in which the receiver is running to stop. All scheduled events are removed and nothing more can happen in the simulation.
SimulationObject instance protocol

The examples we present in subsequent chapters illustrate each message in the modeler's task language.

Simulations

The purpose of class Simulation is to manage the topology of simulation objects and to schedule actions to occur according to simulated time. Instances of class Simulation maintain a reference to a collection of SimulationObjects, to the current simulated time, and to a queue of events waiting to be invoked.

The unit of time appropriate to the simulation is saved in an instance variable and represented as a floating-point number. The unit might be milliseconds, minutes, days, etc. A simulation advances time by checking the queue to determine when the next event is scheduled to take place, and by setting its instance variable to the time associated with that next event. If the queue of events is empty, then the simulation terminates.

Simulation objects enter a simulation in response to one of several scheduling messages such as

scheduleArrivalOf: aSimulationObjectClass
    accordingTo: aProbabilityDistribution or
scheduleArrivalOf: aSimulationObject at: aTimeInteger.

These messages are sent to the simulation either at the time that the simulation is first initialized, in response to the message defineArrivalSchedule, or as part of the sequence of tasks that a SimulationObject carries out. The second argument of the first message, aProbabilityDistribution, is an instance of a probability distribution such as those defined in Chapter 21. In this chapter, we assume the availability of the definitions given in Chapter 21. The probability distribution defines the interval at which an instance of the first argument, aSimulationObjectClass, is to be created and sent the message startUp.

In addition, Simulation supports messages having to do with scheduling a particular sequence of actions. These are schedule: actionBlock at: timeInteger and schedule: actionBlock after: amountOfTime.

In order to define the resources in the simulation, the modeler can send the simulation one or more of two possible messages. Either

self produce: amount of: resourceName

where the second argument, resourceName, is a String that names a simple quantifiable resource available in the simulation; the first argument is the (additional) quantity of this resource to be made available. Or

self coordinate: resourceName

The argument, resourceName, is a String that names a resource that is to be provided by some objects in the simulation and requested by other objects. For example, the resource is car washing, the provider is a washer object and the requestor is a car object.

initialization
initialize	Initialize the receiver's instance variables.
modeler's initialization language
defineArrivalSchedule	Schedule simulation objects to enter the simulation at specified time intervals, typically based on probability distribution functions. This method is implemented by subclasses. It involves a sequence of messages to the receiver (i.e., to self) that are of the form schedule:at:, scheduleArrivalOf:at:, scheduleArrivalOf:accordingTo:, or scheduleArrivalOf:accordingTo:startingAt:. See the next category of messages for descriptions of these.
defineResources	Specify the resources that are initially entered into the simulation. These typically act as resources to be acquired. This method is implemented by subclasses and involves a sequence of messages to the receiver (i.e., to self) of the form produce: amount of: resourceName.
modeler's task language
produce: amount of: resourcename	An additional quantity of amount of a resource referred to by the String, resourceName, is to be part of the receiver. If the resource does not as yet exist in the receiver, add it; if it already exists, increase its available quantity.
coordinate: resourceName	Use of a resource referred to by the String, resourceName, is to be coordinated by the receiver.
schedule: actionBlock after: timeDelayInteger	Set up a program, actionBlock, that will be evaluated after a simulated amount of time, timeDelayInteger, passes.
schedule: actionBlock at: timeInteger	Schedule the sequence of actions (actionBlock) to occur at a particular simulated time, timeInteger.
scheduleArrivalOf: aSimulationObject at: timeInteger	Schedule the simulation object, aSimulationObject, to enter the simulation at a specified time, timeInteger.
scheduleArrivalOf: aSimulationObjectClass accordingTo: aProbabilityDistribution	Schedule simulation objects that are instances of aSimulationObjectClass to enter the simulation at specified time intervals, based on the probability distribution aProbabilityDistribution. The first such instance should be scheduled to enter now. See Chapter 21 for definitions of possible probability distributions.
scheduleArrivalOf: aSimulationObjectClass accordingTo: aProbabilityDistribution startingAt: timeInteger	Schedule simulation objects that are instances of aSimulationObjectClass to enter the simulation at specified time intervals, based on the probability distribution aProbabilityDistribution. The first such instance should be scheduled to enter at time timeInteger.
Simulation instance protocol

Notice that in the above scheduling messages, scheduleArrivalOf:at: takes a SimulationObject instance as its first argument, while scheduleArrivalOf:accordingTo: takes a SimulationObject class. These messages are used differently; the first one can be used by the SimulationObject itself to reschedule itself, while the second is used to initiate the arrival of SimulationObjects into the system.

The protocol for Simulation includes several accessing messages. One, the message includesResourceFor: resourceName, can be sent by a SimulationObject in order to determine whether or not a resource having a given name exists in the simulation.

accessing
includesResourceFor: resourceName	Answer if the receiver has a resource that is referred to by the String, resourceName. If such a resource does not exist, then report an error.
provideResourceFor: resourceName	Answer a resource that is referred to by the String, resourceName.
time	Answer the receiver's current time.
Simulation instance protocol

The simulation control framework is like that of class SimulationObject. Initialization is handled by creating the Simulation and sending it the message startUp. Simulation objects and the scheduling of new objects create events that are placed in the event queue. Once initialized, the Simulation is made to run by sending it the message proceed until there are no longer any events in the queue.

In the course of running the simulation, objects will enter and exit. As part of the protocol for scheduling a simulation object, the object informs its simulation that it is entering or exiting. The corresponding messages are enter: anObject and exit: anObject. In response to these messages, statistics might be collected about simulation objects upon their entrance and their exit to the simulation. Or a subclass might choose to deny an object entrance to the simulation; or a subclass might choose to reschedule an object rather than let it leave the simulation.

simulation control
startUP	Specify the initial simulation objects and the arrival schedule of new objects.
proceed	This is a single event execution. The first event in the queue, if any, is removed, time is updated to the time of the event, and the event is initiated.
finishUp	Release references to any remaining simulation objects.
enter: anObject	The argument, anObject, is informing the receiver that it is entering.
exit: anObject	The argument, anObject, is informing the receiver that it is exiting.
Simulation instance protocol

Of the above messages, the default responses in class Simulation are mostly to do nothing. In particular, the response to messages enter: and exit: are to do nothing. Messages defineArrivalSchedule and defineResources also do nothing. As a result, the message startUp accomplishes nothing. These messages provide the framework that subclasses are to use--a subclass is created that overrides these messages in order to add simulation-specific behavior.

A "Default" Example: NothingAtAll

Unlike many of the system class examples of earlier chapters, the superclasses Simulation and SimulationObject typically do not implement their basic messages as

self subclassResponsibility

By not doing so, instances of either of these classes can be successfully created. These instances can then be used as part of a basic or a "default" simulation that serves as a skeletal example. As we have seen, such simulation objects are scheduled to do nothing and consist of no events. Development of more substantive simulations can proceed by gradual refinement of these defaults. With a running, default example, the designer/programmer can incrementally modify and test the simulation, replacing the uninteresting instances of the superclasses with instances of appropriate subclasses. The example simulation NothingAtAll illustrates the idea of a "default" simulation.

Suppose we literally do nothing other than to declare the class NothingAtAll as a subclass of Simulation. A NothingAtAll has no initial resources since it does nothing in response to the message defineResources. And it has no simulation objects arriving at various intervals, because it does nothing in response to the message defineArrivalSchedule. Now we execute the following statement.

NothingAtAll new startUp proceed

The result is that an instance of NothingAtAll is created and sent the message startUp. It is a simulation with no resources and no objects scheduled, so the queue of events is empty. In response to the message proceed, the simulation determines that the queue is empty and does nothing.

As a modification of the description of NothingAtAll, we specify a response to the message defineArrivalSchedule. In it, the objects scheduled for arrival are instances of class DoNothing. DoNothing is created simply as a subclass of SimulationObject. A DoNothing has no tasks to carry out, so as soon as it enters the simulation, it leaves.

class name	DoNothing
superclass	SimulationObject
instance methods	no new methods
class name	NothingAtAll
superclass	Simulation
instance methods	initialization defineArrivalSchedule self scheduleArrivalOf: DoNothing accordingTo: (Uniform from: 1 to: 5)

This version of NothingAtAll might represent a series of visitors entering an empty room, looking around without taking time to do so, and leaving. The probability distribution, Uniform, in the example in this chapter is assumed to be the one specified in Chapter 21. According to the above specification, new instances of class DoNothing should arrive in the simulation every 1 to 5 units of simulated time starting at time 0. The following expressions, when evaluated, create the simulation, send it the message startUp, and then iteratively send it the message proceed.

aSimulation ← NothingAtAll new startUp.
[aSimulation proceed] whileTrue

sage startUp invokes the message defineArrivalSchedule which schedules instances of DoNothing. Each time the message proceed is sent to the simulation, a DoNothing enters or exits. Evaluation might result in the following sequence of events. The time of each event is shown on the left and a description of the event is shown on the right.

0.0	a DoNothing enters
0.0	a DoNothing exits
3.21	a DoNothing enters
3.21	a DoNothing exits
7.76	a DoNothing enters
7.76	a DoNothing exits

and so on.

We can now make the simulation more interesting by scheduling the

arrival of more kinds of simulation objects, ones that have tasks to do. We define Visitor to be a SimulationObject whose task is to enter the empty room and look around, taking between 4 and 10 simulated units to do so, that is, a random amount determined by evaluating the expression (Uniform from: 4 to: 10) next.

class name	Visitor
superclass	SimulationObject
instance methods	simulation control tasks self holdFor: (Uniform from: 4.0 to: 10.0) next

NothingAtAll is now defined as

class name	NothingAtAll
superclass	Simulation
instance methods	initialization defineArrivalSchedule self scheduleArrivalOf: DoNothing accordingTo: (Uniform from: 1 to: 5). self scheduleArrivalOf: Visitor accordingTo: (Uniform from: 4 to: 8) startingAt: 3

Two kinds of objects enter the simulation, one that takes no time to look around (a DoNothing) and one that visits a short while (a Visitor). Execution of

aSimulation ← NothingAtAll new startUp.
[aSimulation proceed] whileTrue

might result in the following sequence of events.

0.0	a DoNothing enters
0.0	a DoNothing exits
3.0	a Visitor enters
3.21	a DoNothing enters
3.21	a DoNothing exits
7.76	a DoNothing enters
7.76	a DoNothing exits
8.23	a (the first) Visitor exits after 5.23 seconds

and so on.

Implementation of the Simulation Classes

In order to trace the way in which the sequence of events occurs in the examples provided so far, it is necessary to show an implementation of the two classes. The implementations illustrate the control of multiple independent processes in the Smalltalk-80 system that were described in Chapter 15.

Class SimulationObject

Every SimulationObject created in the system needs access to the Simulation in which it is functioning. Such access is necessary, for example, in order to send messages that inform the simulation that an object is entering or exiting. In order to support such access, SimulationObject has a class variable, ActiveSimulation, that is initialized by each instance of Simulation when that instance is activated (that is, sent the message startUp). This approach assumes only one Simulation will be active at one time. It means that the tasks for any subclass of SimulationObject can send messages directly to its simulation, for example, to determine the current time. SimulationObject specifies no instance variables.

class name	Simulation Object
superclass	Object
class variable names	ActiveSimulation
class methods	class initialization activeSimulation: existingSimulation ActiveSimulation ← existingSimulation instance creation new ↑super new initialize

The simulation control framework, sometimes referred to as the "life cycle" of the object, involves the sequence startUp-tasks-finishUp. When the SimulationObject first arrives at the simulation, it is sent the message startUp. instance methods

simulation control
    initialize
        "Do nothing. Subclasses will initialize instance variables."
        ↑self
    startUp
        ActiveSimulation enter: self.
        "First tell the simulation that the receiver is beginning to do my tasks."
        self tasks.
        self finishUp
    tasks
        "Do nothing. Subclasses will schedule activies."
        ↑self
    finishUp
        "Tell the simulation that the receiver is done with its tasks."
        ActiveSimulation exit: self

The category task language consists of messages the modeler can use in specifying the SimulationObject's sequence of actions. The object might hold for an increment of simulated time (holdFor:). The object might try to acquire access to another simulation object that is playing the role of a resource (acquire:ofResource:). Or the object might determine whether a resource is available (resourceAvailable:).

task language
    holdFor: aTimeDelay
        ActiveSimulation delayFor: aTimeDelay
    acquire: amount ofResource: resourceName
        "Get the resource and then tell it to acquire amount of it. Answers an instance of StaticResource"
        ↑(ActiveSimulation provideResourceFor: resourceName)
            acquire: amount
            withPriority: 0
    acquire: amount ofResource: resourceName withPriority: priority
        ↑(ActiveSimulation provideResourceFor: resourceName)
            acquire: amount
            withPriority: priority
    produce: amount ofResource: resourceName
        ActiveSimulation produce: amount of: resourceName
    release: aStaticResource
        ↑aStaticResource release
    inquireFor: amount ofResource: resourceName
        ↑(ActiveSimulation provideResourceFor: resourceName)
            amountAvailable > = amount
    resourceAvailable: resourceName
        "Does the active simulation have a resource with this attribute available?"
        ↑ActiveSimulation includesResourceFor: resourceName
    acquireResource: resourceName
        ↑(ActiveSimulation provideResourceFor: resourceName)
            acquire
    produceResource: resourceName
        ↑(ActiveSimulation provideResourceFor: resourceName)
    resume: anEvent
        ↑anEvent resume
    numberOfProvidersOfResource: resourceName
        | resource |
        resource ← ActiveSimulation provideResourceFor: resourceName.
        resource serversWaiting
            ifTrue: [↑resource queueLength]
            ifFalse: [↑0]
    numberOfRequestersOfResource: resourceName
        | resource |
        resource ← ActiveSimulation provideResourceFor: resourceName.
        resource customersWaiting
            ifTrue: [↑resource queueLength]
            ifFalse: [↑0]
    stopSimulation
        ActiveSimulation finishUp

A Simulation stores a Set of resources. In the case of static resources, instances of class ResourceProvider are stored; in the case of resources that consist of tasks coordinated among two or more simulation objects, instances of ResourceCoordinator are stored.

When a SimulationObject requests a static resource (acquire:ofResource:) and that request succeeds, then the SimulationObject is given an instance of class StaticResource. A StaticResource refers to the resource that created it and the quantity of the resource it represents. Given the methods shown for class SimulationObject, we can see that a resource responds to the message amountAvailable to return the currently available quantity of the resource that the SimulationObject might acquire. This message is sent in the method associated with inquireFor:ofResource:.

In the methods associated with SimulationObject messages acquire:ofResource: and acquire:ofResource:withPriority:, a ResourceProvider is obtained and sent the message acquire: amount withPriority: priorityNumber. The result of this message is an instance of class StaticResource. However, if the amount is not available, the process in which the request was made will be suspended until the necessary resources become available. A StaticResource is sent the message release in order to recycle the acquired resource.

When a SimulationObject requests a coordinated resource (acquireResource:), and that request succeeds, then the object co-opts another simulation object acting as the resource (the object in need of service) until some tasks (services) are completed. If such a resource is not available, the process in which the request was made will be suspended until the necessary resources become available. Instances of class ResourceCoordinator understand messages acquire in order to make the request to coordinate service tasks and producedBy: aSimulationObject in order to specify that the argument is to be co-opted by another object in order to synchronize activities. As indicated by the implementation of SimulationObject, a ResourceCoordinator can answer queries such as customersWaiting or serversWaiting to determine if resources (customers) or service givers (servers) are waiting to coordinate their activities, and queueLength to say how many are waiting.

Explanations of the implementations of classes ResourceProvider and ResourceCoordinator are provided in Chapters 24 and 25.

Class DelayedEvent

The implementation of a scheduling mechanism for class Simulation makes extensive use of the Smalltalk-80 processor scheduler classes presented in the chapter on multiple processes (Chapter 15). There are several problems that have to be solved in the design of class Simulation. First, how do we store an event that must be delayed for some increment of simulated time? Second, how do we make certain that all processes initiated at a particular time are completed before changing the clock? And third, in terms of the solutions to the first two problems, how do we implement the request to repeatedly schedule a sequence of actions, in particular, instantiation and initiation of a particular kind of SimulationObject?

In order to solve the first problem, the Simulationmaintains a queue of all the scheduled events. This queue is a SortedCollection whose elements are the events, sorted with respect to the simulated time in which they must be invoked. Each event on the queue is placed there within a package that is an instance of class DelayedEvent. At the time the package is created, the event is the system's active process. As such, it can be stored with its needed running context by creating a Semaphore. When the event is put on the queue, the DelayedEvent is sent the message pause which sends its Semaphore the message wait; when the event is taken off the queue, it is continued by sending it the message resume. The method associated with resume sends the DelayedEvent's Semaphore the message signal.

The protocol for instances of class DelayedEvent consists of five messages.

accessing
condition	Answer a condition under which the event should be sequenced.
condition: anObject	Set the argument, anObject, to be the condition under which the event should be sequenced.
scheduling
pause	Suspend the current active process, that is, the current event that is running.
resume	Resume the suspended process.
comparing
< = aDelayedEvent	Answer whether the receiver should be sequenced before the argument, aDelayedEvent.
DelayedEvent instance protocol

A DelayedEvent is created by sending the class the message new or onCondition: anObject. The implementation of class DelayedEvent is given next.

class name	DelayedEvent
superclass	Object
instance variable names	resumptionSemaphore resumptionCondition
class methods	instance creation new ↑super new initialize onCondition: anObject ↑super new setCondition: anObject
instance methods	accessing condition ↑resumptionCondition condition: anObject resumptionCondition ← anObject comparing < = aDelayedEvent resumptionCondition isNil ifTrue: [↑true] ifFalse: [↑resumptionCondition < = aDelayedEvent condition] scheduling pause resumptionSemaphore wait resume resumptionSemaphore signal. ↑resumptionCondition private initialize resumptionSemaphore ← Semaphore new setCondition: anObject self initialize. resumptionCondition ← anObject

According to the above specification, any object used as a resumption condition must respond to the message < =; SimulationObject is, in general, such a condition.

Class Simulation

Instances of class Simulation own four instance variables: a Set of objects that act as resources of the simulation (resources), a Number representing the current time (currentTime), a SortedCollection representing a queue of delayed events (eventQueue), and an Integer denoting the number of processes active at the current time (processCount).

Initialization of a Simulation sets the instance variables to initial values. When the instance is sent the scheduling message startUp, it sends itself the message activate which informs interested other classes which Simulation is now the active one.

class name	Simulation
superclass	Object
instance variable names	resources currentTime eventQueue processCount
class methods	instance creation new ↑super new initialize
instance methods	initialization initialize resources ← Set new. currentTime ← 0.0. processCount ← 0. eventQueue ← SortedCollection new activate "This instance is now the active simulation. Inform class SimulationObject." SimulationObject activeSimulation: self. "Resource is the superclass for ResourceProvider and ResourceCoordinator" Resource activeSimulation: self

Initialization messages are also needed by the subclasses. The messages provided for the modeler to use in specifying arrival schedules and resource objects provides an interface to the process scheduling messages.

initialization
    defineArrivalSchedule
        "A subclass specifies the schedule by which simulation objects dynamically enter into the simulation."
        ↑self
    defineResources
        "A subclass specifies the simulation objects that are initially entered into the simulation."
        ↑self
task language
    produce: amount of: resourceName
        (self includesResourceFor: resourceName)
            ifTrue: [(self provideResourceFor: resourceName) produce: amount]
            ifFalse: [resources add: (ResourceProvider named: resourceName with: amount)]
    coordinate: resourceName
        (self includesResourceFor: resourceaName)
            ifFalse: [resources add: (ResourceCoordinator named: resourceName)]
    schedule: actionBlock after: timeDelay
        self schedule: actionBlock at: currentTime + timeDelay
    schedule: aBlock at: timeInteger
        "This is the mechanism for scheduling a single action"
        self newProcessFor:
            [self delayUntil: timeInteger.
                aBlock value]
    scheduleArrivalOf: aSimulationObject at: timeInteger
        self schedule: [aSimulationObject startUp] at: timeInteger
    scheduleArrivalOf: aSimulationObjectClass accordingTo: aProbabilityDistribution
        "This means start now"
        self scheduleArrivalOf: aSimulationObjectClass
            accordingTo: aProbabilityDistribution
            startingAt: currentTime
    scheduleArrivalOf: aSimulationObjectClass accordingTo: aProbabilityDistribution startingAt: timeInteger
        "Note that aClass is the class SimulationObject or one of its subclasses. The real work is done in the private message schedule:startingAt:andThenEvery:"
        self schedule: [aSimulationObjectClass new startUp]
            startingAt: timeInteger
            andThenEvery: aProbabilityDistribution

The scheduling messages of the task language implement a referencecounting solution to keeping track of initiated processes. This is the technique used to solve the second problem cited earlier, that is, how to make certain that all processes initiated for a particular time are carried out by the single Smalltalk-80 processor scheduler before a different process gets the opportunity to change the clock. Using reference counting, we guarantee that simulated time does not change unless the reference count is zero.

The key methods are the ones associated with schedule: aBlock at: timeInteger and schedule: aBlock startingAt: timeInteger andThenEvery: aProbabilityDistribution. This second message is a private one called by the method associated with scheduleArrivalOf: aSimulationOb]ectClass accordingTo: aProbabilityDistribution startingAt: timeInteger. It provides a general mechanism for scheduling repeated actions and therefore represents a solution to the third design problem mentioned earlier, how we implement the request to repeatedly schedule a sequence of actions.

The basic idea for the schedule: aBlock at: timeInteger is to create a process in which to delay the evaluation of the sequence of actions (aBlock) until the simulation reaches the appropriate simulated time (timeInteger). The delay is performed by the message delayUntil: delayedTime. The associated method creates a DelayedEvent to be added to the simulation's event queue. The process associated with this DelayedEvent is then suspended (by sending it the message pause). When this instance of DelayedEvent is the first in the queue, it will be removed and the time will be bumped to the stored (delayed) time. Then this instance of DelayedEvent will be sent the message resume which will cause the evaluation of the block; the action of this block is to schedule some simulation activity.

A process that was active is suspended when the DelayedEvent is signaled to wait. Therefore, the count of the number of processes must be decremented (stopProcess). When the DelayedEvent resumes, the process continues evaluation with the last expression in the method delayedUntil:; therefore at this time, the count of the number of processes must be incremented (startProcess).

scheduling
    delayUntil: aTime
        | delayEvent |
        delayEvent ← DelayedEvent onCondition: timeInteger.
        eventQueue add: delayEvent.
        self stopProcess.
        delayEvent pause.
        self startProcess
    delayFor: timeDelay
        self delayUntil: currentTime + timeDelay
    startProcess
        processCount ← processCount + 1
    stopProcess
        processCount ← processCount - 1

Reference counting of processes is also handled in the method associated with class Simulation's scheduling message newProcessFor: aBlock. It is implemented as follows.

newProcessFor: aBlock
    self startProcess.
    [aBlock value.
        self stopProcess] fork

The first expression increments the count of processes. The second expression is a block that is forked. When the Smalltalk processor scheduler evaluates this block, the simulation sequence of actions, aBlock, is evaluated. The :completion of evaluating aBlock signals the need to decrement the count of processes. In this way, a single sequence of actions is scheduled in the event queue of the Simulation and delayed until the correct simulated time. In summary, the reference count of processes increments whenever a new sequence of actions is initiated, decrements whenever a sequence completes, decrements whenever a DelayedEvent is created, and increments whenever the DelayedEvent is continued.

The method for the private message schedule: aBlock startingAt: timelnteger andThenEvery: aProbabilityDistribution forks a process that repeatedly schedules actions. The algorithm consists of iterations of two messages,

self delayUntil: timeInteger.
self newProcessFor: aBlock

Repetition of the two messages delayUntil: and newProcessFor: depends on a probability distribution function. The number of repetitions equals the number of times the distribution can be sampled. The number that is sampled represents the next time that the sequence of actions (aBlock)

should be invoked. Elements of the distribution are enumerated by sending the distribution the message do:.

private
    schedule: ablock
            startingAt: timeInteger
            andThenEvery: aProbabilityDistribution
        self newProcessFor:
            ["This is the first time to do the action."
                self delayUntil: timeInteger.
                "Do the action."
                self newProcessFor: aBlock copy.
                aProbabilityDistribution
                    do: [ :nextTimeDelay |
                        "For each sample from the distribution, delay the amount sampled."
                        self delayFor: nextTimeDelay.
                        "then do the action"
                        self newProcessFor: aBlock copy]]

Simulation itself has a control framework similar to that of SimulationObject. The response to startUp is to make the simulation the currently active one and then to define the simulation objects and arrival schedule. The inner loop of scheduled activity is given as the response to the message proceed. Whenever the Simulation receives the message proceed, it checks the reference count of processes (by sending the message readyToContinue). If the reference count is not zero, then there are still processes active for the current simulated time. So, the system-wide processor, Processor, is asked to yield control and let these processes proceed. If the reference count is zero, then the event queue is checked. If it is not empty, the next event is removed from the event queue, time is changed, and the delayed process is resumed.

simulation control
    startUp
        self activate.
        self defineResources.
        self defineArrivalSchedule
    proceed
        | eventProcess |
        [self readyToContinue] whileFalse: [Processor yield].
        eventQueue isEmpty
            ifTrue: [↑self finishUp]
            ifFalse: [eventProcess ← eventQueue removeFirst.
                currentTime ← eventProcess time.
                eventProcess resume]
    finishUp
        "We need to empty out the event queue"
        eventQueue ← SortedCollection new.
        ↑false
    enter: anObject
        ↑self
    exit: anObject
        ↑self
private
    readyToContinue
        ↑processCount = 0

In addition to these various modeler's languages and simulation control messages, several accessing messages are provided in the protocol of Simulation.

accessing
    includesResourceFor: resourceName
        | test |
        test ← resources
            detect: [ :each | each name = resourceName]
            ifNone: [nil].
        ↑test notNil
    provideResourceFor: resourceName
        ↑resources detect: [ :each | each name = resourceName]
    time
        ↑currentTime

The implementations of Simulation and SimulationObject illustrate the use of messages fork to a BlockContext, yield to a ProcessorScheduler, and signal and wait to a Semaphore.

Tracing the Example NothingAtAll

We can now trace the execution of the first example of the simulation, NothingAtAll, in which DoNothings only were scheduled. After sending the message

NothingAtAll new

the instance variables of the new simulation consist of

resources = Set ()
currentTime = 0.0
processCount = 0
eventQueue = SortedCollection ()

We then send this simulation the message startUp, which invokes the message scheduleArrivalOf: DoNothing accordingTo: (Uniform from: 1 to: 5). This is identical to sending the simulation the message

schedule: [DoNothing new startUp]
startingAt: 0.0
andThenEvery: (Uniform from: 1 to: 5)

The response is to call on newProcessFor:.

Step 1. newProcessFor: increments the processCount (self startProcess) and then creates a new Process that evaluates the folloing block, which will be referred to as block A.

[self delayUntil: timeInteger.
    self newProcessFor: block copy.
    aProbabilityDistribution do:
        [ :nextTimeDelay |
            self delayFor: nextTimeDelay.
            self newProcessFor: block copy]

where the variable block is

[DoNothing new startUp]

which will be referred to as block B.

Step 2. When the process returns to the second expression of the method newProcessFor:, execution continues by evaluating block A. Its first expression decrements the process count and suspends an activity until time is 0.0 (i.e., create a DelayedEvent for the active simulation scheduler to tell the DoNothing to startUp at time 0.0; put it on the event queue).

resources = Set ()
currentTime = 0.0
processCount = 0
eventQueue = SortedCollection (a DelayedEvent 0.0)

Now we send the simulation the message proceed. The process count is 0 so readyToContinue returns true; the event queue is not empty so the first DelayedEvent is removed, time is set to 0.0, and the delayed process is resumed (this was the scheduler block A). The next action increments the process count and evaluates block B. This lets a DoNothing enter and do its task, which is nothing, so it leaves immediately. The new processFor: message decrements the process count to 0, gets a number from the probability distribution, delays for this number of time units, and schedules a new process for some time later. The sequence continues indefinitely, as long as the message proceed is re-sent to the simulation.

Other tasks will enter the event queue depending on the method associated with the message tasks in a subclass of SimulationObject. Thus if Visitor is scheduled in NothingAtAll, then the expresson self holdFor: someTime will enter an event on the queue, intermingled with events that schedule new arrivals of Visitors and DoNothings.