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.