Smalltalk80LanguageImplementation:Chapter 24

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.

class name	Resource
superclass	Object
instance variable names	pending resourceName
class variable names	ActiveSimulation
class methods	class initialization activeSimulation: existingSimulation ActiveSimulation ← existingSimulation instance creation named: resourceName ↑self new setName: resourceName
instance methods	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.

class name	ResourceProvider
superclass	Resource
instance variable names	amountAvailable
class methods	instance creation named: resourceName with: amount ↑self new setName: resourceName with: amount named: resourceName ↑self new setName: resourceName with: 0
instance methods	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.

class name	StaticResource
superclass	SimulationObject
instance variable names	amount resource priority
class methods	instance creation for: amount of: aResource withPriority: aNumber ↑self new setAmount: amount resource: aResource withPriority: aNumber
instance methods	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).

Consumable Resources

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

class name	NothingAtAll
superclass	Simulation
instance methods	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
12.153

At time 11.875, all but one jelly bean has been consumed. At time 12.153 Visitor number 7 stops the simulation.

Nonconsumable Resources

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.

class name	RentalAgency
superclass	Simulation
instance methods	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 name	CarRenter
superclass	EventMonitor
class variable names	CarCounter Hour
class methods	class initialization file: file super file: file CarCounter ← 0. Hour ← 60
instance methods	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 name	TruckRenter
superclass	EventMonitor
class variable names	TruckCounter Hour
class methods	class initialization file: file super file: file. TruckCounter ← 0 Hour ← 60 accessing setLabel TruckCounter ← TruckCounter + 1. label ← TruckCounter printString
instance methods	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.

class name	FileSystem
superclass	Simulation
instance variable names	statistics
instance methods	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.

class name	FileSystemReader
superclass	EventMonitor
instance methods	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
class name	FileSystemWriter
superclass	EventMonitor
instance methods	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.

Renewable Resources

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.

class name	CarDealer
superclass	Simulation
instance variable names	statistics
instance methods	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.

class name	CarBuyer
superclass	SimulationObject
instance variable names	entryTime
instance methods	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.

class name	CarDelivery
superclass	SimulationObject
instance methods	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
	55	0.0	197.168	78.5476
Entry	Number of Objects	Frequency
1-8	2	0.0363636	XX
8-15	3	0.0545454	XXX
15-22	2	0.0363636	XX
22-29	1	0.0181818	X
29-36	2	0.0363636	XX
36-43	1	0.0181818	X
43-50	0	0.0
50-57	1	0.0181818	X
57-64	2	0.0363636	XX
64-71	1	0.0181818	X
71-78	2	0.0363636	XX
78-85	2	0.0363636	XX
85-92	2	0.0363636	XX
92-99	0	0.0
99-106	0	0.0
106-113	1	0.0181818	X
113-120	3	0.0545454	XXX
120-127	2	0.0363636	XX
127-134	2	0.0363636	XX
134-141	2	0.0363636	XX
141-148	1	0.0181818	X
148-155	0	0.0
155-162	1	0.0181818	X
162-169	2	0.0363636	XX
169-176	2	0.0363636	XX
176-183	1	0.0181818	X
183-190	2	0.0363636	XX
190-197	2	0.0363636	XX
197-204	1	0.0181818	X
204-211	0	0.0
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.

class name	Ferry
superclass	SimulationObject
instance variable names	carsOnBoard currentSide
instance methods	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.

class name	IslandArrival
superclass	SimulationObject
instance methods	simulation control tasks self produce: 1 ofResource: 'Island'
class name	MainlandArrival
superclass	SimulationObject
instance methods	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.

class name	FerrySimulation
superclass	Simulation
instance methods	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.

class name	Ferry
superclass	SimulationObject
instance variable names	emptyTrips carsOnBoard currentSide trips totalCars emptyTrips
instance methods	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.

420.000	IslandArrival 1
420.000	MainlandArrival 1
425.290	MainlandArrival 2
429.380	MainlandArrival 3
430.830	IslandArrival 2
431.302	IslandArrival 3
434.209	IslandArrival 4
438.267	IslandArrival 5
440.864	IslandArrival 6
441.193	MainlandArrival 4
448.044	IslandArrival 7
448.827	IslandArrival 8
453.811	IslandArrival 9
458.804	MainlandArrival 5
467.860	IslandArrival 10
470.800	IslandArrival 11
473.957	MainlandArrival 6
475.508	IslandArrival 12

This continues until ...

1300.87	IslandArrival 169
1301.11	MainlandArrival 124
1301.19	IslandArrival 170
1306.75	IslandArrival 171
1309.30	IslandArrival 172
1315.24	MainlandArrival 125
1319.65	MainlandArrival 126
1321.80	MainlandArrival 127
1322.39	MainlandArrival 128
1328.45	IslandArrival 173
1328.99	IslandArrival 174
1329.77	MainlandArrival 129
1331.63	IslandArrival 175
1335.43	MainlandArrival 130
1338.93	IslandArrival 176
1342.46	MainlandArrival 131
1348.11	IslandArrival 177
1358.63	MainlandArrival 132
1359.10	IslandArrival 178
1360.79	MainlandArrival 133

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.