- Chapter 24 The Use of Resources in Event-Driven Simulations
The Use of Resources in Event-Driven Simulations
In the previous chapters, we introduced a framework in which to specify event-driven simulations and to gather statistics about such simulations. Without resources to contend for and use, the only real task that an object can perform in a simulation is to hold (wait) for some specified amount of simulated time. Two kinds of resources are illustrated in this chapter: fixed resources and fluctuating resources. These kinds of resources were introduced in Chapter 22; the example in that chapter of classes Simulation and SimulationObject defined a support for resources coordination that will be further described in this chapter.
A fixed resource can be consumable. The simulation with a consumable resource begins with a given quantity of some resource, say, jelly beans. As the simulation proceeds, objects acquire the resource, ultimately using up all that were originally available. New objects needing the resource either terminate without successfully completing their tasks, or are indefinitely delayed waiting for a resource that will never be provided. Alternatively, a fixed resource can be nonconsumable. The simulation begins with a given quantity of some nonconsumable resource, say, glass jars. As the simulation proceeds, objects acquire the resource. When an object no longer needs the resource, it is recycled. Objects needing the resource either obtain it immediately or are delayed until a recycled one becomes available.
A fluctuating resource models producer/consumer relationships. A simulation can begin with a given quantity of some resource, say cars. As the simulation proceeds, objects acquire the resource; when they no longer need the resource, they recycle it (such as in the used car market). New resources can be added (produced), increasing the supply of the resource. Objects needing the resource either obtain it immediately or must wait until a recycled one or a new one becomes available. A fluctuating resource for which additional quantities can be produced is called a renewable resource. The example of the car is an example of a resource that is both renewable and nonconsumable.
Implementing ResourceProvider and StaticResource
The modeler's language for specifying resources in a Simulation includes expressions of the form
self produce: amount of: resourceName
The response to this message is either to create an instance of class Resource with amount as its available quantity of resources, or to retrieve an existing Resource and increment its resources by amount. Instances of ResourceProvider are created by sending ResourceProvider the message named: aString or named: aString with: amount.
When a SimulationObject requests a resource (acquire: amount ofResource: resourceName), the currently active simulation (ActiveSimulation) is asked to provide the corresponding resource (provideResourceFor:). Presumably the resource exists in the simulation as a result of the initialization of the Simulation; the Simulation refers to a Set of instances of ResourceProvider and can enumerate this Set in order to find one whose name is resourceName.
Once the SimulationObject has access to a ResourceProvider it can
- ask how many resources it has available,
- ask its name,
- ask to acquire some amount (and with a particular access priority),
- ask to produce some amount.
When a SimulationObject asks to acquire some resources, this request is added to a queue of such requests, ordered with respect to priority and, within identical priority levels, on a first-come first-served basis. Each time a request is made or more resources are produced, the ResourceProvider checks to see if one or more of its pending requests can be satisfied.
Each request is stored as an instance of class DelayedEvent. DelayedEvent was described in Chapter 22. Each DelayedEvent refers to a condition. In the case of delayed tasks, the condition is the time at which the tasks should be resumed; in the case of resource requests, the condition is an instance of StaticResource which is a representation of the requested resource and desired amount. Whenever a request is made, the request is stored on the waiting queue, pending, and then an attempt is made to provide the resource.
Class ResourceProvider is a subclass of class Resource. Class ResourceCoordinator, to be presented in the next chapter, is also a subclass of Resource. Resource represents the resource in terms of its name and the queue of requests that must be satisfied. A class variable refers to the currently active simulation (ActiveSimulation) for access to the time and process reference counting.
|instance variable names||pending|
|class variable names||ActiveSimulation|
class initialization activeSimulation: existingSimulation ActiveSimulation ← existingSimulation instance creation named: resourceName ↑self new setName: resourceName
accessing addRequest: aDelayedEvent pending add: aDelayedEvent. self provideResources. ActiveSimulation stopProcess. aDelayedEvent pause. ActiveSimulation startProcess name ↑resourceName private provideResources ↑self setName: aString resourceName ← aString. pending ← SortedCollection new
Notice that the mechanism used for storing requests on the SortedCollection, pending, is similar to that used for storing delayed events on the eventQueue of a Simulation. That is, a process that was running is suspended so that the reference count for processes in the Simulation is decremented. At the point that the process continues again, the reference count is incremented. A Semaphore is used in order to synchronize pausing and resuming the simulation process.
Class ResourceProvider represents resources as simple quantifiable items that have no tasks to do and are, therefore, not created as actual SimulationObjects. Rather, a numerical count is kept of the number of the items. When a SimulationObject successfully acquires this kind of resource, the SimulationObject is given access to an instance of StaticResource. The last expression of the method in ResourceProvider associated with acquire:withPriority: creates and returns a StaticResource. Prior to evaluating this expression, a DelayedEvent is removed from the collection of pending requests and the amount requested decremented from the amount currently available.
|instance variable names||amountAvailable|
instance creation named: resourceName with: amount ↑self new setName: resourceName with: amount named: resourceName ↑self new setName: resourceName with: 0
accessing amountAvailable ↑amountAvailable task language acquire: amountNeeded withPriority: priorityNumber | anEvent | anEvent ← DelayedEvent onCondition: (StaticResource for: amountNeeded of: self withPriority: priorityNumber). self addRequest: anEvent. ↑anEvent condition produce: amount amountAvailable ← amountAvailable + amount. self provideResources private provideResources | anEvent | [pending isEmpty not and: [pending first condition amount < = amountAvailable]] whileTrue: [anEvent ← pending removeFirst. amountAvailable ← amountAvailable - anEvent condition amount. anEvent resume] setName: resourceName with: amount super setName: aString. amountAvailable ← amount
A StaticResource represents a SimulationObject with no tasks to do other than to hold quantities of items for some other SimulationObject.
|instance variable names||amount|
instance creation for: amount of: aResource withPriority: aNumber ↑self new setAmount: amount resource: aResource withPriority: aNumber
accessing amount ↑amount name ↑resource name priority ↑priority comparing < = aStaticResource ↑priority < = aStaticResource priority task language consume: aNumber amount ← (amount - aNumber) max: 0 release resource produce: amount. amount ← 0 private setAmount: aNumber resource: aResource withPriority: priorityNumber amount ← aNumber. resource ← aResource. priority ← priorityNumber
Since a SimulationObject can hold on to a reference to a StaticResource, the messages consume: and release are part of the task language of a SimulationObject. When a SimulationObject acquires a resource, it is presumably consuming that resource, until that resource is returned to the simulation. The amount of resource held in the StaticResource is returned to the simulation by sending the StaticResource the message release. (Typically, however, the SimulationObject sends itself the message release: aStaticResource so that a uniform style of sending messages to self is maintained in the method associated With the object's tasks. This uniformity simplifies the design of a method for tracing or monitoring the events of a simulation. Because all task messages are sent as messages to self and therefore to a SimulationObject, it is possible to create a subclass of SimulationObject (EventMonitor was the example we presented in Chapter 23) in which all task messages are intercepted in order to store a notation that the task is being done.
Using acquire:ofResource: and release:, the resource is treated as a nonconsumable resource. A mixture is possible. The SimulationObject can acquire some amount of a resource, say 10, consume 5, and return 5. The message consume: is used to remove resources from the simulation. Thus the example would be accomplished by sending a StaticResource, acquired with 10 resources, the message consume: 5, and then the message release (or sending release: aStaticResource to self).
A simple jelly bean example illustrates the idea of a consumable resource. Recall the simulation example, NothingAtAll, introduced in Chapter 22. Suppose that whenever a Visitor enters the simulation and looks around, it has a task to acquire 2 jelly beans, take 2 units of time eating the beans, and leave. The simulation is initialized with one resource consisting of 15 jelly beans. The definition of this version of NothingAtAll is
initialization defineResources self produce: 15 of: 'jelly beans' defineArrivalSchedule self scheduleArrivalOf: Visitor accordingTo: (Uniform from: 1 to: 3)
The Visitor's tasks are expressed in two messages to self found in its method for tasks.
tasks self acquire: 2 ofResource: 'jelly beans'. self holdFor: 2
An example execution of this simulation, in which only exits and entries are monitored, is
|0.0||Visitor 1 enters|
|2.0||Visitor 1 exits|
|2.03671||Visitor 2 enters|
|4.03671||Visitor 2 exits|
|4.34579||Visitor 3 enters|
|5.92712||Visitor 4 enters|
|6.34579||Visitor 3 exits|
|7.92712||Visitor 4 exits|
|8.46271||Visitor 5 enters|
|10.4627||Visitor 5 exits|
|10.5804||Visitor 6 enters|
|12.5804||Visitor 6 exits|
|12.7189||Visitor 7 enters|
|14.7189||Visitor 7 exits||last visitor to get jelly beans endless waiting from now on|
|15.0638||Visitor 8 enters|
|17.6466||Visitor 9 enters|
|19.8276||Visitor 10 enters|
After the seventh Visitor enters, there are no more jelly beans, so all the subsequent Visitors are endlessly delayed waiting for resources that will never be made available. Alternatively, the Visitor could check to see if any jelly beans remain available (inquireFor:ofResource:). If none remain, the Visitor can leave rather than getting caught in the queue. This corresponds to the following method for tasks.
tasks (self inquireFor: 2 ofResource: 'jelly beans') ifTrue: [self acquire: 2 ofResource: 'jelly beans' self holdFor: 2]
One additional refinement might be to inform the simulation that all resources are used up and that it is time to "close the store." This is done by sending the Visitor the message stopSimulation. If we were to send this message the first time a Visitor enters who can not acquire enough jelly beans, then it is possible that a Visitor who has entered the store will get locked in. We have to make certain that a Visitor who acquires the last jelly beans, closes the store upon exit; in this way, a later Visitor will not lock this last successful one into the store. This corresponds to the following method for tasks.
tasks | flag | (self inquireFor: 2 ofResource: 'jelly beans') ifTrue: [self acquire: 2 ofResource: 'jelly beans'. flag ← self inquireFor: 2 ofResource: 'jelly beans'. "Are there still 2 left so that the next Visitor can be served?" self holdFor: 2. flag ifFalse: [self stopSimulation]]
Here is another example execution of the simulation NothingAtAll, in which only exits and entries are monitored.
|0.0||Visitor 1 enters|
|2.0||Visitor 1 exits|
|2.26004||Visitor 2 enters|
|4.26004||Visitor 2 exits|
|4.83762||Visitor 3 enters|
|6.34491||Visitor 4 enters|
|6.83762||Visitor 3 exits|
|8.34491||Visitor 4 exits|
|8.51764||Visitor 5 enters|
|9.9006||Visitor 6 enters|
|10.5176||Visitor 5 exits|
|11.9006||Visitor 6 exits|
|12.6973||Visitor 7 enters||last successful requestor|
|14.0023||Visitor 8 enters||nothing available for this Visitor|
|14.0023||Visitor 8 exits|
|14.6973||Visitor 7 exits||last successful requestor closes shop on exit|
The EventMonitor class described in the previous chapter also monitors the use of resources. So, a trace of NothingAtAll would include the times at which jelly beans were requested and obtained.
|0.0||Visitor 1 enters|
|0.0||Visitor 1 requests 2 of jelly beans|
|0.0||Visitor 1 obtained 2 of jelly beans|
|0.0||Visitor 1 holds for 2|
|1.40527||Visitor 2 enters|
|1.40527||Visitor 2 requests 2 of jelly beans|
|1.40527||Visitor 2 obtained 2 of jelly beans|
|1.40527||Visitor 2 holds for 2|
|2.0||Visitor 1 exits|
|2.56522||Visitor 3 enters|
|2.56522||Visitor 3 requests 2 of jelly beans|
|2.56522||Visitor 3 obtained 2 of jelly beans|
|2.56522||Visitor 3 holds for 2|
|3.40527||Visitor 2 exits|
|4.56522||Visitor 3 exits|
|5.3884||Visitor 4 enters|
|5.3884||Visitor 4 requests 2 of jelly beans|
|5.3884||Visitor 4 obtained 2 of jelly beans|
|5.3884||Visitor 4 holds for 2|
|6.69794||Visitor 5 enters|
|6.69794||Visitor 5 requests 2 of jelly beans|
|6.69794||Visitor 5 obtained 2 of jelly beans|
|6.69794||Visitor 5 holds for 2|
|7.3884||Visitor 4 exits|
|7.72174||Visitor 6 enters|
|7.72174||Visitor 6 requests 2 of jelly beans|
|7.72174||Visitor 6 obtained 2 of jelly beans|
|7.72174||Visitor 6 holds for 2|
|8.69794||Visitor 5 exits|
|9.72174||Visitor 6 exits|
|10.153||Visitor 7 enters|
|10.153||Visitor 7 requests 2 of jelly beans|
|10.153||Visitor 7 obtained 2 of jelly beans|
|10.153||Visitor 7 holds for 2|
|11.875||Visitor 8 enters|
|11.875||Visitor 8 exits|
At time 11.875, all but one jelly bean has been consumed. At time 12.153 Visitor number 7 stops the simulation.
A car rental simulation serves to illustrate the use of a nonconsumable resource. The example simulation is a short-term car rental agency that opens up with 15 cars and 3 trucks available. Renters of cars arrive with a mean rate of one every 30 minutes, and those requiring trucks one every 120 minutes. The first car renter arrives when the shop opens, and the first truck renter arrives 10 minutes later. Classes CarRenter and TruckRenter represent these simulation objects.
RentalAgency is specified as a subclass of Simulation. It implements the two initialization messages, defineArrivalSchedule and defineResources.
initialization defineArrivalSchedule self scheduleArrivalOf: CarRenter accordingTo: (Exponential mean: 30). self scheduleArrivalOf: TruckRenter accordingTo: (Exponential mean: 120) startingAt: 10 defineResources self produce: 15 of: 'car' self produce: 3 of: 'truck'
The tasks for CarRenter and TruckRenter are similar. First acquire a car or truck; if none are available, wait. Once the vehicle is obtained, use it. A CarRenter keeps the car between 4 and 8 hours (uniformly distributed); a TruckRenter keeps the truck between 1 and 4 hours (uniformly distributed). These usage times are indicated by having the renter hold for the appropriate amount of time before returning the vehicle (i.e., releasing the resource).
In order to monitor the two kinds of SimulationObject, and to have labels that separately identify each kind, the implementations of CarRenter and TruckRenter duplicate the labeling technique demonstrated earlier for class Visitor.
|class variable names||CarCounter|
class initialization file: file super file: file CarCounter ← 0. Hour ← 60
accessing setLabel CarCounter ← CarCounter + 1. label ← CarCounter printString simulation control tasks | car | car ← self acquire: 1 ofResource: 'car'. self holdFor: (Uniform from: 4*Hour to: 8*Hour) next. self release: car
|class variable names||TruckCounter|
class initialization file: file super file: file. TruckCounter ← 0 Hour ← 60 accessing setLabel TruckCounter ← TruckCounter + 1. label ← TruckCounter printString
simulation control tasks | truck | truck ← self acquire: 1 ofResource: 'truck'. self holdFor: (Uniform from: Hour to: 4*Hour) next. self release: truck
The rental agency simulation is run by invoking
aFile ← Disk file: 'rental.events'. CarRenter file: aFile. TruckRenter file: aFile. anAgency ← RentalAgency new startUp. [anAgency time < 600] whileTrue: [anAgency proceed]
The trace on file rental.events after 10 hours (600 minutes) shows the following sequence of events.
|0||CarRenter 1 enters|
|0||CarRenter 1 requests 1 of Car|
|0||CarRenter 1 obtained 1 of Car|
|0||CarRenter 1 holds for 460.426|
|10||TruckRenter 1 enters|
|10||TruckRenter 1 requests 1 of Truck|
|10||TruckRenter 1 obtained 1 of Truck|
|10||TruckRenter 1 holds for 87.2159|
|26.2079||CarRenter 2 enters|
|26.2079||CarRenter 2 requests 1 of Car|
|26.2079||CarRenter 2 obtained 1 of Car|
|26.2079||CarRenter 2 holds for 318.966|
|27.4147||CarRenter 3 enters|
|27.4147||CarRenter 3 requests 1 of Car|
|27.4147||CarRenter 3 obtained 1 of Car|
|27.4147||CarRenter 3 holds for 244.867|
|51.5614||CarRenter 4 enters|
|51.5614||CarRenter 4 requests 1 of Car|
|51.5614||CarRenter 4 obtained 1 of Car|
|51.5614||CarRenter 4 holds for 276.647|
|78.0957||CarRenter 5 enters|
|78.0957||CarRenter 5 requests 1 Of Car|
|78.0957||CarRenter 5 obtained 1 of Car|
|78.0957||CarRenter 5 holds for 333.212|
|93.121||CarRenter 6 enters|
|93.121||CarRenter 6 requests 1 of Car|
|93.121||CarRenter 6 obtained 1 of Car|
|93.121||CarRenter 6 holds for 359.718|
|97.2159||TruckRenter 1 releases 1 of Truck|
|97.2159||TruckRenter 1 exits|
|99.0265||CarRenter 7 enters|
|99.0265||CarRenter 7 requests 1 of Car|
|99.0265||CarRenter 7 obtained 1 of Car|
|99.0265||CarRenter 7 holds for 417.572|
|106.649||CarRenter 8 enters|
|106.649||CarRenter 8 requests 1 of Car|
|106.649||CarRenter 8 obtained 1 of Car|
|106.649||CarRenter 8 holds for 294.43|
|107.175||CarRenter 9 enters|
|107.175||CarRenter 9 requests 1 of Car|
|107.175||CarRenter 9 obtained 1 of Car|
|107.175||CarRenter 9 holds for 314.198|
|121.138||CarRenter 10 enters|
|121.138||CarRenter 10 requests 1 of Car|
|121.138||CarRenter 10 obtained 1 of Car|
|121.138||CarRenter 10 holds for 467.032|
|127.018||TruckRenter 2 enters|
|127.018||TruckRenter 2 requests 1 of Truck|
|127.018||TruckRenter 2 obtained 1 of Truck|
|127.018||TruckRenter 2 holds for 74.5047|
|145.513||CarRenter 11 enters|
|145.513||CarRenter 11 requests 1 of Car|
|145.513||CarRenter 11 obtained 1 of Car|
|145.513||CarRenter 11 holds for 243.776|
|166.214||CarRenter 12 enters|
|166.214||CarRenter 12 requests 1 of Car|
|166.214||CarRenter 12 obtained 1 of Car|
|166.214||CarRenter 12 holds for 429.247|
|172.253||CarRenter 13 enters|
|172.253||CarRenter 13 requests 1 of Car|
|172.253||CarRenter 13 obtained 1 of Car|
|172.253||CarRenter 13 holds for 370.909|
|191.438||TruckRenter 3 enters|
|191.438||TruckRenter 3 requests 1 of Truck|
|191.438||TruckRenter 3 obtained 1 of Truck|
|191.438||TruckRenter 3 holds for 225.127|
|201.523||TruckRenter 2 releases 1 of Truck|
|201.523||TruckRenter 2 exits|
|220.102||CarRenter 14 enters|
|220.102||CarRenter 14 requests 1 of Car|
|220.102||CarRenter 14 obtained 1 of Car|
|220.102||CarRenter 14 holds for 334.684|
|252.055||CarRenter 15 enters|
|252.055||CarRenter 15 requests 1 of Car|
|252.055||CarRenter 15 obtained 1 of Car|
|252.055||CarRenter 15 holds for 408.358|
|269.964||CarRenter 16 enters|
|269.964||CarRenter 16 requests 1 of Car|
|272.282||CarRenter 3 releases 1 of Car|
|272.282||CarRenter 3 exits|
|272.282||CarRenter 16 obtained 1 of Car|
|272.282||CarRenter 16 holds for 281.349|
|292.375||CarRenter 17 enters|
|292.375||CarRenter 17 requests 1 of Car|
|328.208||CarRenter 4 releases 1 of Car|
|328.208||CarRenter 4 exits|
|328.208||CarRenter 17 obtained 1 of Car|
|328.208||CarRenter 17 holds for 270.062|
|345.174||CarRenter 2 releases 1 of Car|
|345.174||CarRenter 2 exits|
|350.53||CarRenter 18 enters|
|350.53||CarRenter 18 requests 1 of Car|
|350.53||CarRenter 18 obtained 1 of Car|
|350.53||CarRenter 18 holds for 297.154|
|354.126||CarRenter 19 enters|
|354.126||CarRenter 19 requests 1 of Car|
|358.269||TruckRenter 4 enters|
|358.269||TruckRenter 4 requests 1 of Truck|
|358.269||TruckRenter 4 obtained 1 of Truck|
|358.269||TruckRenter 4 holds for 173.648|
|367.88||TruckRenter 5 enters|
|367.88||TruckRenter 5 requests 1 of Truck|
|367.88||TruckRenter 5 obtained 1 of Truck|
|367.88||TruckRenter 5 holds for 175.972|
|389.289||CarRenter 11 releases 1 of Car|
|389.289||CarRenter 11 exits|
|389.289||CarRenter 19 obtained 1 of Car|
|389.289||CarRenter 19 holds for 379.017|
|401.079||CarRenter 8 releases 1 of Car|
|401.079||CarRenter 8 exits|
|402.224||CarRenter 20 enters|
|402.224||CarRenter 20 requests 1 of Car|
|402.224||CarRenter 20 obtained 1 of Car|
|402.224||CarRenter 20 holds for 341.188|
|410.431||TruckRenter 6 enters|
|410.431||TruckRenter 6 requests 1 of Truck|
|411.307||CarRenter 5 releases 1 of Car|
|411.307||CarRenter 5 exits|
|416.566||TruckRenter 3 releases 1 of Truck|
|416.566||TruckRenter 3 exits|
|416.566||TruckRenter 6 obtained 1 of Truck|
|416.566||TruckRenter 6 holds for 119.076|
|421.373||CarRenter 9 releases 1 of Car|
|421.373||CarRenter 9 exits|
|422.802||CarRenter 21 enters|
|422.802||CarRenter 21 requests 1 of Car|
|422.802||CarRenter 21 obtained 1 of Car|
|422.802||CarRenter 21 holds for 241.915|
|452.839||CarRenter 6 releases 1 of Car|
|452.839||CarRenter 6 exits|
|460.426||CarRenter 1 releases 1 of Car|
|460.426||CarRenter 1 exits|
|512.263||CarRenter 22 enters|
|512.263||CarRenter 22 requests 1 of Car|
|512.263||CarRenter 22 obtained 1 of Car|
|512.263||CarRenter 22 holds for 277.035|
|516.598||CarRenter 7 releases 1 of Car|
|516.598||CarRenter 7 exits|
|531.917||TruckRenter 4 releases 1 of Truck|
|531.917||TruckRenter 4 exits|
|535.642||TruckRenter 6 releases 1 of Truck|
|535.642||TruckRenter 6 exits|
|543.162||CarRenter 13 releases 1 of Car|
|543.162||CarRenter 13 exits|
|543.852||TruckRenter 5 releases 1 of Truck|
|543.852||TruckRenter 5 exits|
|553.631||CarRenter 16 releases 1 of Car|
|553.631||CarRenter 16 exits|
|554.786||CarRenter 14 releases 1 of Car|
|554.786||CarRenter 14 exits|
|574.617||CarRenter 23 enters|
|574.617||CarRenter 23 requests 1 of Car|
|574.617||CarRenter 23 obtained 1 of Car|
|574.617||CarRenter 23 holds for 436.783|
|588.171||CarRenter 10 releases 1 of Car|
|588.171||CarRenter 10 exits|
|591.51||CarRenter 24 enters|
|591.51||CarRenter 24 requests 1 of Car|
|591.51||CarRenter 24 obtained 1 of Car|
|591.51||CarRenter 24 holds for 430.067|
|595.461||CarRenter 12 releases 1 of Car|
|595.461||CarRenter 12 exits|
|598.27||CarRenter 17 releases 1 of Car|
|598.27||CarRenter 17 exits|
|599.876||CarRenter 25 enters|
|599.876||CarRenter 25 requests 1 of Car|
|599.876||CarRenter 25 obtained 1 of Car|
|599.876||CarRenter 25 holds for 472.042|
|642.188||TruckRenter 7 enters|
|642.188||TruckRenter 7 requests 1 of Truck|
|642.188||TruckRenter 7 obtained 1 of Truck|
|642.188||TruckRenter 7 holds for 190.586|
A snapshot of the simulation shows that, at time 642.188, the following events are queued in anAgency and the following resources are available.
Resource (car) no pending requests; 6 available Resource (truck) no pending requests; 2 available Event Queue CarRenter for creation and start up TruckRenter for creation and start up 9 CarRenters holding 1 TruckRenter holding
Note that a nonconsumable resource differs from the description of a consumable resource only in the SimulationObject's sending the message release: in order to recycle acquired resources.
Example of a File System
The car rental is an open simulation in which objects (car renters and truck renters) arrive, do their tasks, and leave again. A closed simulation is one in which the same objects remain in the simulation for the duration of the simulation run. The next example is of a file system; it was adopted from a book by Graham Birtwistle that presents a Simulabased system named Demos [A System for Discrete Event Modelling on Simula, Graham M. Birtwistle, MacMillan, London, England, 1979]. The purpose of Demos is to support teaching about the kinds of eventdriven simulations discussed in this chapter. The book is a thorough introduction to this class of simulations and to their implementation in Simula. There are many useful examples, each of which could be implemented in the context of the Smalltalk-80 simulation framework provided in this and in the previous chapter. We use variations of a Demos file system, a car ferry, and an information system example for illustration in this chapter so that, after seeing how we approach the Smalltalk-80 implementations, the interested reader can try out more of Birtwistle's examples.
In the example file system, "writer" processes update a file, and "reader" processes read it. Any number of readers may access the file at the same time, but writers must have sole access to the file. Moreover, writers have priority over readers. The individual sequencing of events is shown in the programs below. The example illustrates the use of priority queueing for resources as well as another approach to collecting statistics. In this case, the statistics gathered is a tally of the number of reads and the number of writes.
Suppose there are three system file readers and two file writers, and only three (nonconsumable) file resources. The initialization method specifies a statistics dictionary with two zero-valued entries, reads and writes. The simulation is to run for 25 simulated units of time; it schedules itself to receive the message finishUp at time 25.
Note in the implementation of defineArrivalSchedule that the FileSystemReaders and FileSystemWriters are given attributes so that they can be identified in the event traces.
|instance variable names||statistics|
initialize-release initialize super initialize. statistics ← Dictionary new: 2. statistics at: #reads put: 0. statistics at: #writes put: 0 defineArrivalSchedule self scheduleArrivalOf: (FileSystemReader new label: 'first') at: 0.0. self scheduleArrivalOf: (FileSystemWriter new label: 'first') at: 0.0. self scheduleArrivalOf: (FileSystemReader new label: 'second') at: 0.0. self scheduleArrivalOf: (FileSystemWriter new label: 'second') at: 1.0. self scheduleArrivalOf: (FileSystemReader new label: 'third') at: 2.0. self schedule: [self finishUp] at: 25 defineResources self produce: 3 of: 'File' statistics statisticsAt: aKey changeBy: anInteger statistics at: aKey put: (statistics at: aKey) + anInteger printStatisticsOn: aStream statistics printOn: aStream
The FileSystemReader repeatedly carries out a sequence of five tasks: acquire one File resource, hold for an amount of time appropriate to reading the file, release the resource, update the tally of read statistics, and then hold for an amount of time appropriate to using the information read from the file. FileSystemWriters acquire three file resources, hold in order to write on the file, release the resources, and update the write statistics. The priority of a FileSystemReader is set to 1; the priority of a FileSystemWriter is 2. In this way, the nonconsumable ResourceProvider" File" will give attention to FileSystemWriters before FileSystemReaders.
In order to obtain a trace of the events, the two simulation objects are created as subclasses of EventMonitor. Since each has a single label that will serve to identify it, only the response to printOn: aStream is reimplemented.
accessing label: aString label ← aString simulation control tasks | file | "The repeated sequence of tasks is as follows" [true] whileTrue: [file ← self acquire: 1 ofResource: 'File' withPriority: 1. self holdFor: 2.0. self release: file. ActiveSimulation statisticsAt: #reads changeBy: 1. self holdFor: 5.0 ] printing printOn: aStream aStream nextPutAll: label. aStream space. self class name printOn: aStream
accessing label: aString label ← aString simulation control tasks | file | "The repeated sequence of tasks is as follows" [true] whileTrue: ["Gather information" self holdFor: 5.0. file ← self acquire: 3 ofResource: 'File' withPriority: 2. self holdFor: 3.0. self release: file. ActiveSimulation statisticsAt: #writes changeBy: 1] printing printOn: aStream aStream nextPutAll: label. aStream space. self class name printOn: aStream
The five simulation objects carry out their tasks, until the simulation stops itself at time 25. In specifying the tasks of a SimulationObject, the modeler has available all the control structures of the Smalltalk-80 language. A trace of the events shows how FileSystemReaders are held up because of the higher priority and larger resource needs of the FileSystemWriters. For example, the first and second FileSystemReaders are held up at time 7.0; the third at time 9.0; and all until time 11.0, the time at which no FileSystemWriter requires resources.
|0.0||first FileSystemReader enters|
|0.0||first FileSystemReader requests 1 of File|
|0.0||first FileSystemReader obtained 1 of File|
|0.0||first FileSystemReader holds for 2.0|
|0.0||first FileSystemWriter enters|
|0.0||first FileSystemWriter holds for 5.0|
|0.0||second FileSystemReader enters|
|0.0||second FileSystemReader requests 1 of File|
|0.0||second FileSystemReader obtained 1 of File|
|0.0||second FileSystemReader holds for 2.0|
|1.0||second FileSystemWriter enters|
|1.0||second FileSystemWriter holds for 5.0|
|2.0||second FileSystemReader releases 1 of File|
|2.0||second FileSystemReader holds for 5.0|
|2.0||first FileSystemReader releases 1 of File|
|2.0||first FileSystemReader holds for 5.0|
|2.0||third FileSystemReader enters|
|2.0||third FileSystemReader requests 1 of File|
|2.0||third FileSystemReader obtained 1 of File|
|2.0||third FileSystemReader holds for 2.0|
|4.0||third FileSystemReader releases 1 of File|
|4.0||third FileSystemReader holds for 5.0|
|5.0||first FileSystemWriter requests 3 of File|
|5.0||first FileSystemWriter obtained 3 of File|
|5.0||first FileSystemWriter holds for 3.0|
|6.0||second FileSystemWriter requests 3 of File|
|7.0||first FileSystemReader requests 1 of File|
|7.0||second FileSystemReader requests 1 of File|
|8.0||first FileSystemWriter releases 3 of File|
|8.0||first FileSystemWriter holds for 5.0|
|8.0||second FileSystemWriter obtained 3 of File|
|8.0||second FileSystemWriter holds for 3.0|
|9.0||third FileSystemReader requests 1 of File|
|11.0||second FileSystemWriter releases 3 of File|
|11.0||second FileSystemWriter holds for 5.0|
|11.0||first FileSystemReader obtained 1 of File|
|11.0||first FileSystemReader holds for 2.0|
|11.0||second FileSystemReader obtained 1 of File|
|11.0||second FileSystemReader holds for 2.0|
|11.0||third FileSystemReader obtained 1 of File|
|11.0||third FileSystemReader holds for 2.0|
|13.0||third FileSystemReader releases 1 of File|
|13.0||third FileSystemReader holds for 5.0|
|13.0||second FileSystemReader releases 1 of File|
|13.0||second FileSystemReader holds for 5.0|
|13.0||first FileSystemReader releases 1 of File|
|13.0||first FileSystemReader holds for 5.0|
|13.0||first FileSystemWriter requests 3 of File|
|13.0||first FileSystemWriter obtained 3 of File|
|13.0||first FileSystemWriter holds for 3.0|
|16.0||first FileSystemWriter releases 3 of File|
|16.0||first FileSystemWriter holds for 5.0|
|16.0||second FileSystemWriter requests 3 of File|
|16.0||second FileSystemWriter obtained 3 of File|
|16.0||second FileSystemWriter holds for 3.0|
|18.0||first FileSystemReader requests 1 of File|
|18.0||second FileSystemReader requests 1 of File|
|18.0||third FileSystemReader requests 1 of File|
|19.0||second FileSystemWriter releases 3 of File|
|19.0||second FileSystemWriter holds for 5.0|
|19.0||first FileSystemReader obtained 1 of File|
|19.0||first FileSystemReader holds for 2.0|
|19.0||second FileSystemReader obtained 1 of File|
|19.0||second FileSystemReader holds for 2.0|
|19.0||third FileSystemReader obtained 1 of File|
|19.0||third FileSystemReader holds for 2.0|
|21.0||third FileSystemReader releases 1 of File|
|21.0||third FileSystemReader holds for 5.0|
|21.0||second FileSystemReader releases 1 of File|
|21.0||second FileSystemReader holds for 5.0|
|21.0||first FileSystemReader releases 1 of File|
|21.0||first FileSystemReader holds for 5.0|
|21.0||first FileSystemWriter requests 3 of File|
|21.0||first FileSystemWriter obtained 3 of File|
|21.0||first FileSystemWriter holds for 3.0|
|24.0||first FileSystemWriter releases 3 of File|
|24.0||first FileSystemWriter holds for 5.0|
|24.0||second FileSystemWriter requests 3 of File|
|24.0||second FileSystemWriter obtained 3 of File|
|24.0||second FileSystemWriter holds for 3.0|
At this point, the current time is 25 and the statistics gathered is printed by sending the FileSystem the message printStatisticsOn: aStream where the Stream is, for example, a FileStream. The result is
reads 9 writes 5
Note that if the FileSystemReaders were not held up by lack of resources and lower priority, there would have been 12 reads during this timeframe.
In simulations involving producer/consumer synchronizations, simulation objects acting as producers make resources available to other objects acting as consumers. The simulation starts out with some fixed amount of resource, perhaps 0. Producer objects increase the available resources, consumer objects decrease them. This type of resource differs from a nonconsumable resource in that there is no limit to the amounts of resource that can be made available. Such resources are called renewable resources. Note that the limit in the nonconsumable case is enforced indirectly by the SimulationObject's returning resources through the StaticResource.
A simulation of a car dealership provides a simple example of a renewable resource. Suppose a customer comes in to buy a car every two to six days. The car dealer starts out with 12 cars on the lot; when these are sold, orders must wait until new cars are delivered. Ten to twelve new cars are shipped to the dealer every 90 days. We assume that all the cars are the same and that every customer is willing to wait so that no sales are lost if a car is not immediately available. The car dealer is interested in giving good service, but he is also unwilling to keep too large an inventory. By examining the average length of the queue of waiting customers, the dealer can modify his quarterly order of cars in order to minimize customer dissatisfaction and still maintain a small inventory of new cars.
Statistics on the amount of time that car buyers have to wait to get a car are kept by the simulation. The method used is the same as the method demonstrated in Chapter 23 for collecting information on Visitors to a Museum; a Histogram is maintained by the CarDealer. Each CarBuyer remembers its entry time; when it exists the simulation, the length of time the CarBuyer spent in the simulation is logged in the Histogram. This length of time is equivalent to the amount of time the CarBuyer had to wait to get a car because the CarBuyer's only task is to acquire a car.
|instance variable names||statistics|
initialize-release initialize super initialize. statistics ← Histogram from: 1 to: 365 by: 7 defineArrivalSchedule self scheduleArrivalOf: CarBuyer accordingTo: (Uniform from: 2 to: 6) startingAt: 1.0 self scheduleArrivalOf: (CarDelivery new) at: 90.0 "only one delivery is scheduled; the instance of CarDelivery will reschedule itself as the last of its tasks" defineResources self produce: 12 of: 'Car' accessing exit: aSimulationObject super exit: aSimulationObject. "A CarDelivery could be exiting--ignore it" (aSimulationObject isKindOf: CarBuyer ifTrue: [statistics store: currentTime -- aSimulationObject entryTime] printStatistics: aStream statistics printStatisticsOn: aStream
All the CarBuyer wants to do is get a car; the CarBuyer only waits if a car is not immediately available.
|instance variable names||entryTime|
accessing entryTime ↑entryTime simulation control initialize super initialize. entryTime ← ActiveSimulation time tasks self acquire: 1 ofResource: 'Car'
The CarDelivery produces 10 to 12 new cars. After producing the new cars, the CarDeliveryobject schedules itself to return in 90 days. An alternative implementation would have the CarDelivery hold for 90 days and then repeat its task.
simulation control tasks "Get access to the Car resource and produce 10, 11, or 12 new cars" self produce: ((SampleSpace data: #(10 11 12)) next) ofResource: 'Car'. "Schedule a new delivery in 90 days" ActiveSimulation scheduleArrivalOf: self at: ActiveSimulation time + 90
The statistics give us the number of buyers, minimum, maximum, and average wait times for the buyers, and the number of buyers within each wait-time interval. No one waited longer than 204 days. 91 car buyers came to the dealer; 12 did not have to wait because the dealer had cars already. Of the 43 that waited and were served, they waited on the average of 78.5 days.
At time 360.0 the statistics indicates the following information.
|Number of Objects||Minimum Value||Maximum Value||Average Value|
|Entry||Number of Objects||Frequency|
|Pending Requests 36 buyers waiting for a car|
From the above information, we can estimate that the number of cars delivered could safely be increased, even doubled, to meet the consumer demand.
Example of a Ferry Service
This next example is like one in the Birtwistle book. The example is of a ferry shuttling between an island and the mainland, carrying cars back and forth. The ferry starts service at 7:00 a.m. (420 minutes into the day) and stops at 10:45 p.m. (1365 minutes into the day) once it has reached one of its docking locations. The ferry has a capacity of only six cars.
The ferry's task is to load no more than six of the waiting cars and then to cross over the waterway. The crossing takes about eight minutes with a standard deviation of 0.5 minutes. The activity of crossing from one side to the other continues until the time is 1365 minutes. The FerrySimulation described next simulates one day's ferry service. Note in the definition of Ferry the use of the Smalltalk-80 whileFalse: control structure to repetitively send the Ferry from one side to another; also note the use of messages to split up the task description into parts load, holdFor: (cross over), unload, and changeSide.
|instance variable names||carsOnBoard|
simulation control initialize super initialize. carsOnBoard ← 0. currentSide ← 'Mainland' tasks "Initialize the count of loaded cars and then keep loading until at most 6 are on board. Stop loading if no more cars are waiting at the dock." [ActiveSimulation time > 1365.0] whileFalse: [carsOnBoard ← 0. self load. self holdFor: (Normal mean: 8 deviation: 0.5) next. self unload. self changeSide] load "It takes 0.5 minutes to load each car. Only try to acquire a resource, a car from this side's dock, if it is there. The conditional for the repetition checks remaining resources and only continues if a car is waiting." [carsOnBoard < 6 and: [self inquirefor: 1 of: currentSide]] whileTrue: [self acquire: 1 ofResource: currentSide. self holdFor: 0.5. carsOnBoard ← carsOnBoard + 1] changeSide currentSide ← currentSide = 'Mainland' ifTrue: ['Island'] ifFalse: ['Mainland'] unload "It takes 0.5 minutes to unload each car." self holdFor: carsOnBoard*0.5.
We will need two SimulationObjects in order to simulate the cars arriving at the dock of the Mainland or at the Island, that is, to produce a car at these locations.
simulation control tasks self produce: 1 ofResource: 'Island'
simulation control tasks self produce: 1 ofResource: 'Mainland'
The ferry simulation has two kinds of Resources, one for the mainland and one for the island, in which to queue the arriving cars. When these resources are first created, i.e., the day begins, there are three cars already waiting at the mainland dock and no cars waiting at the island dock. The arrival schedule says that cars arrive with a mean rate of 0.15 every minute.
initialization defineArrivalSchedule self scheduleArrivalOf: MainlandArrival accordingTo: (Exponential parameter: 0.15) startingAt: 420.0. self scheduleArrivalOf: IslandArrival accordingTo: (Exponential parameter: 0.15) startingAt: 420.0. self scheduleArrivalOf: Ferry new at: 420.0 defineResources self produce: 3 of: 'Mainland' self produce: 0 of: 'Island'
There is some data that the simulation should collect while it is accumulating. First, the Ferry should count the total number of trips it takes, the total cars it carries, and the number of trips it takes carrying no cars. This data is obtained by adding three instance variables (trips, totalCars, and emptyTrips) in the definition of class Ferry and modifying three methods.
|instance variable names||emptyTrips|
initialize super initialize. carsOnBoard ← 0. currentSide ← 'Mainland' trips ← 0. totalCars ← 0. emptyTrips ← 0 load "Keep a running tally of the cars carried" [carsOnBoard < 6 and: [self inquireFor: 1 ofResource: currentSide]] whileTrue: [self acquire: 1 ofResource: currentSide. self holdFor: 0.5. carsOnBoard ← carsOnBoard + 1. totalCars ← totalCars + 1] tasks "Check for an empty trip and keep a tally of trips" [ActiveSimulation time > 1365.0] whileFalse: [carsOnBoard ← 0. self load. carsOnBoard = 0 ifTrue: [emptyTrips ← emptyTrips + 1]. self holdFor: (Normal mean: 8 deviation: 0.5) next. self unload. self changeSide. trips ← trips + 1]
In addition, we would like to know the maximum size of the number of Mainland and Island arrivals, that is, the maximum queue waiting for the Ferry. The FerrySimulation can determine this information by adding two instance variables, maxMainland and maxIsland; each time the message produce: amount of: resourceName is sent to the simulation and a resource amount is increased, the corresponding variable can be reset to the maximum of its current value and that of the resource.
The trace we provide shows the beginning and the ending sequence of events. The arrival of cars at the Island and the Mainland is listed separately from the repetitive tasks of the Ferry.
This continues until ...
The Ferry starts at the Mainland where there were three cars waiting; no cars are at the Island. Immediately a car arrives at each place.
|420,0||Ferry 1 enters||load at Mainland: there are now 4 cars waiting at Mainland and 1 car waiting at Island|
|420.0||Ferry 1 obtained 1 of Mainland, holds for 0.5|
|420.5||Ferry 1 obtained 1 of Mainland, holds for 0.5|
|421.0||Ferry 1 obtained 1 of Mainland, holds for 0.5|
|421.5||Ferry 1 obtained 1 of Mainland, holds for 0.5||cross over|
|422.0||Ferry 1 holds for 8.56369||unload 4 cars at Island: there are now 2 cars waiting at Mainland and 1 car waiting at Island|
|430.564||Ferry 1 holds for 2.0||load at Island: there are now 2 cars at Mainland and 3 cars at Island|
|432.564||Ferry 1 obtained 1 of Island, holds for 0.5|
|433.064||Ferry 1 obtained 1 of Island, holds for 0.5|
|433.564||Ferry 1 obtained 1 of Island, holds for 0.5||cross over|
|434.064||Ferry 1 holds for 8.55344||unload 3 cars at Mainland: there are now 3 cars waiting at Mainland and 3 cars waiting at Island|
|442.617||Ferry 1 holds for 1.5||load at Mainland: there is now 3 cars waiting at Mainland and 0 cars waiting at Island|
|444.117||Ferry 1 obtained 1 of Mainland, holds for 0.5|
|444.617||Ferry 1 obtained 1 of Mainland, holds for 0.5|
|445.117||Ferry 1 obtained 1 of Mainland, holds for 0.5||cross over|
|445.617||Ferry 1 holds for 8.98081||unload 3 cars at Island: there are now 0 cars waiting at Mainland and 6 cars waiting at Island|
|454.598||Ferry 1 holds for 1.5||load at Island: there are now 0 cars waiting at Mainland and 6 cars waiting at Island|
|456.098||Ferry 1 obtained 1 of Island, holds for 0.5|
|456.598||Ferry 1 obtained 1 of Island, holds for 0.5|
|457.098||Ferry 1 obtained 1 of Island, holds for 0.5|
|457.598||Ferry 1 obtained 1 of Island, holds for 0.5|
|458.098||Ferry 1 obtained 1 of Island, holds for 0.5|
|458.598||Ferry 1 obtained 1 of Island, holds for 0.5||cross over|
|459.098||Ferry 1 holds for 7.96448||unload 6 cars at Mainland: there is now 1 car waiting at Mainland and 0 cars waiting at Island|
|467.062||Ferry 1 holds for 3.0||load at Mainland: there is now 1 car waiting at Mainland and 1 car waiting at Island|
|470.062||Ferry 1 obtained 1 of Mainland, holds for 0.5||continues until load at Island|
|1299.52||Ferry 1 obtained 1 of Island, holds for 0.5|
|1300.02||Ferry 1 obtained 1 of Island, holds for 0.5||cross over|
|1300.52||Ferry 1 holds for 7.23914||unload 2 cars at Mainland|
|1307.76||Ferry 1 holds for 1.0||load at Mainland: there is now 1 car waiting at Mainland and 3 cars waiting at Island|
|1308.76||Ferry 1 obtained 1 of Mainland, holds for 0.5||cross over|
|1309.26||Ferry 1 holds for 7.78433||load at Island: there are now 2 cars waiting at Mainland and 4 cars waiting at Island|
|1317.54||Ferry 1 obtained 1 of Island, holds for 0.5|
|1318.04||Ferry 1 obtained 1 of Island, holds for 0.5|
|1318.54||Ferry 1 obtained 1 of Island, holds for 0.5|
|1319.04||Ferry 1 obtained 1 of Island, holds for 0.5||cross over|
|1319.54||Ferry 1 holds for 8.51123||unload 4 cars at Mainland: there are now 3 cars waiting at Mainland and 0 cars waiting at Island|
|1328.05||Ferry 1 holds for 2.0||load at Mainland: there are now 5 cars waiting at Mainland and 2 cars waiting at Island|
|1330.05||Ferry 1 obtained 1 of Mainland, holds for 0.5|
|1330.55||Ferry 1 obtained 1 of Mainland, holds for 0.5|
|1331.05||Ferry 1 obtained 1 of Mainland, holds for 0.5|
|1331.55||Ferry 1 obtained 1 of Mainland, holds for 0.5|
|1332.05||Ferry 1 obtained 1 of Mainland, holds for 0.5||cross over|
|1332.55||Ferry 1 holds for 8.17247||unload 5 cars at Island: there is now 1 car waiting at Mainland and 4 cars waiting at Island|
|1340.72||Ferry 1 holds for 2.5||load at Island: there are now 2 cars waiting at Mainland and 4 cars waiting at Island|
|1343.22||Ferry 1 obtained 1 of Island, holds for 0.5|
|1343.72||Ferry 1 obtained 1 of Island, holds for 0.5|
|1344.22||Ferry 1 obtained 1 of Island, holds for 0.5|
|1344.72||Ferry 1 obtained 1 of Island, holds for 0.5||cross over|
|1345.22||Ferry 1 holds for 7.75318||unload at Mainland: there are 2 cars waiting at Mainland and 1 car waiting at Island|
|1352.98||Ferry 1 holds for 2.0||load at Mainland: there are 2 cars waiting at Mainland and 1 car waiting at Island|
|1354.98||Ferry 1 obtained 1 of Mainland, holds for 0.5|
|1355.48||Ferry 1 obtained 1 of Mainland, holds for 0.5||cross over|
|1355.98||Ferry 1 holds for 8.54321||unload 2 cars at Island: there are 2 cars waiting at Mainland and 2 cars waiting at Island|
|1364.52||Ferry 1 holds for 1.0||quitting time|
|1365.52||Ferry 1 exits|
The data collected shows that the Ferry took 79 trips, carrying a total of 310 cars (an average of 3.9 cars per trip). None of the trips was done with an empty load. The Mainland waiting line had a maximum of 7 cars while the Island had a maximum of 18. At the time that the Ferry closed, two cars were left at each location.