Smalltalk80LanguageImplementation:Chapter 23

Chapter 23 Statistics Gathering in Event-Driven Simulations

Statistics Gathering in Event-Driven Simulations

A framework for specifying event-driven simulations was presented in the previous chapter. This framework did not include methods for gathering statistics about a simulation as it is running. Statistics might consist of the amount of time each simulation object spends in the simulation (and, therefore, how well the model supports carrying out the kinds of tasks specified by the objects); information about the length of the queues such as the maximum, minimum and average lengths and amount of time spent in each queue; and information about the utilization of the simulation's resources.

There are a number of ways to add statistics gathering to class Simulation or class SimulationObject. In this chapter, we provide four examples of statistics gathering: duration statistics, throughput histograms, event tallying, and event monitoring. Each of these examples involves creating a subclass of Simulation or SimulationObject in order to provide a dictionary in which data can be stored or a file into which data can be written, and, in that subclass, modifying the appropriate methods in order to store the appropriate data.

Duration Statistics

For the first example of statistics gathering, we create a general subclass of Simulation that simply stores the time an object enters and exits the simulation. The times are kept in a special record whose fields are the time at which the object entered the simulation (entranceTime) and the length of time the object spent in the simulation (duration). Records are described as follows.

class name	SimulationObjectRecord
superclass	Object
instance variable names	entranceTime duration
instance methods	accessing entrance: currentTime entranceTime ← currentTime exit: currentTime duration ← entranceTime - currentTime entrance ↑entranceTime exit ↑entranceTime + duration duration ↑duration printing printOn: aStream entranceTime printOn: aStream. aStream tab. duration printOn: aStream

An example subclass of Simulation which uses SimulationObjectRecords for gathering statistics is StatisticsWithSimulation. It is defined as follows.

class name	StatisticsWithSimulation
superclass	Simulation
instance variable names	statistics
instance methods	initialization initialize super initialize. statistics ← Dictionary new simulation scheduling enter: anObject statistics at: anObject put: (SimulationObjectRecord new entrance: currentTime) exit: anObject (statistics at: anObject) exit: currentTime statistics printStatisticsOn: aStream | stat | aStream cr. aStream nextPutAll: 'Object'. aStream tab. aStream nextPutAll: 'Entrance Time'. aStream tab. aStream nextPutAll: 'Duration'. aStream cr. "Sort with respect to the time the object entered the simulation. Because the keys as well as the values are needed, it is necessary to first obtain the set of associations and then sort them." stat ← SortedCollection sortBlock: [ :i :j | i value entrance < = j value entrance]. statistics associationsDo: [ :each | stat add: each]. stat do: [ :anAssociation | aStream cr. anAssociation key printOn: aStream. aStream tab. anAssociation value printOn: aStream "The value is a SimulationObjectRecord which prints the entrance time and duration"]

Suppose we created NothingAtAll as a subclass of StatisticsWithSimulation. In this example, NothingAtAll schedules two simulation objects: one that does nothing (a DoNothing), arriving according to a uniform distribution from 3 to 5 units of time starting at 0; and one that looks around for 5 units of simulated time (a Visitor), arriving according to a uniform distribution from 5 to 10 units of time starting at 1. Whenever one of these objects enters the simulation, an entry is put in the statistics dictionary. The key is the object itself; the equals (=) test is the default (= =), so each object is a unique key. The value is an instance of SimulationObjectRecord with entrance data initialized. When the object exits, the record associated with it is retrieved and a message is sent to it in order to set the exit data.

class name	DoNothing
superclass	SimulationObject
instance methods	no new methods
class name	Visitor
superclass	SimulationObject
instance methods	simulation control tasks self holdFor: 5
class name	NothingAtAll
superclass	StatisticsWithSimulation
instance methods	initialization defineArrivalSchedule self scheduleArrivalOf: DoNothing accordingTo: (Uniform from: 3 to: 5). self scheduleArrivalOf: Visitor accordingTo: (Uniform from: 5 to: 10) startingAt: 1

Whenever we halt the simulation, we can send the message printStatisticsOn: aFile (where aFile is a kind of FileStream). The result might look like:

Object	Entrance Time	Duration
a DoNothing	0.0	0.0
a Visitor	1.0	5.0
a DoNothing	4.58728	0.0
a Visitor	6.71938	5.0
a DoNothing	9.3493	0.0
a DoNothing	13.9047	0.0
a Visitor	16.7068	5.0
a DoNothing	17.1963	0.0
a DoNothing	21.7292	0.0
a Visitor	23.2563	5.0
a DoNothing	25.6805	0.0
a DoNothing	29.3202	0.0
a Visitor	32.1147	5.0
a DoNothing	32.686	0.0
a DoNothing	36.698	0.0
a DoNothing	41.1135	0.0
a Visitor	41.1614	5.0
a DoNothing	44.3258	0.0
a Visitor	48.4145	5.0
a DoNothing	48.492	0.0
a DoNothing	51.7833	0.0
a Visitor	53.5166	5.0
a DoNothing	56.4262	0.0
a DoNothing	60.5357	0.0
a Visitor	63.4532	5.0
a DoNothing	64.8572	0.0
a DoNothing	68.7634	0.0
a Visitor	68.921	5.0
a DoNothing	72.4788	0.0
a DoNothing	75.8567	0.0

Throughput Histograms

A common statistic gathered in simulations is the throughput of objects, that is, how many objects pass through the simulation in some amount of time; this is proportional to how much time each object spends in the simulation. Gathering such statistics involves keeping track of the number of objects that spend time within predetermined intervals of time. Reporting the results involves displaying the number of objects, the minimum time, maximum time, and the number of objects whose times fall within each specified interval. Such statistics are especially useful in simulations involving resources in order to determine whether or not there are sufficient resources to handle requests-if objects have to wait a long time to get a resource, then they must spend more time in the simulation.

In order to support the gathering of throughput statistics, we provide class Histogram. Histograms maintain a tally of values within prespecified ranges. For example, we might tally the number of times various values fall between 1 and 5, 5 and 10, 10 and 20, 20 and 25, 25 and 30, 30 and 35, 35 and 40, and 40 and 45. That is, we divide the interval 5 to 45 into bins of size 5 and keep a running count of the number of times a value is stored into each bin.

Class Histogram is created by specifying the lower bound, the upper bound, and the bin size. To obtain a Histogram for the above example, evaluate

Histogram from: 5 to: 45 by: 5

Besides data on the bins, a Histogram keeps track of minimum, maximum, and total values entered. An entry might not fit within the bounds of the interval; an additional variable is used to store all such entries (extraEntries). The bins are stored as elements of an array; the array size equals the number of bins (that is, upper bound lower bound // bin size). The message store: aValue is used to put values in the Histogram. The index of the array element to be incremented is 1 + (aValue - lower bound // bins size). Most of the methods shown support printing the collected information.

class name	Histogram
superclass	Object
instance variable names	tallyArray lowerBound upperBound step minValue maxValue totalValues extraEntries
class methods	class initialization from: lowerNum to: upperNum by: step ↑self new newLower: lowerNum upper: upperNum by: step
instance methods	accessing contains: aValue ↑lowerBound < = aValue and: [aValue < upperBound] store: aValue | index | minValue isNil ifTrue: [minValue ← maxValue ← aValue] ifFalse: [minValue ← minValue min: aValue. maxValue ← maxValue max: aValue]. totalValues ← totalValues + aValue. (self contains: aValue) ifTrue: [index ← (aValue - lowerBound // step) + 1. tallyArray at: index put: (tallyArray at: index) + 1] ifFalse: [extraEntries ← extraEntries + 1] printing printStatisticsOn: aStream | totalObjs pos | self firstHeader: aStream. aStream cr; tab. totalObjs ← extraEntries. "count the number of entries the throughput records know" tallyArray do: [ :each | totalObjs ← totalObjs + each]. totalObjs printOn: aStream. aStream tab. minValue printOn: aStream. aStream tab. maxValue printOn: aStream. aStream tab. (totalValues / totalObjs) asFloat printOn: aStream. aStream cr. self secondHeader: aStream. aStream cr. pos ← lowerBound. tallyArray do: [ :entry | pos printOn: aStream. aStream nextPut: $-. (pos ← pos + step) printOn: aStream. aStream tab. entry printOn: aStream. aStream tab. (entry / totalObjs) asFloat printOn: aStream. aStream tab. aStream nextPut: $| "print the X's" entry rounded timesRepeat: [aStream nextPut: $X]. aStream cr] firstHeader: aStream aStream cr; tab. aStream nextPutAll: 'Number of'. aStream tab. aStream nextPutAll: 'Minimum'. aStream tab. aStream nextPutAll: 'Maximum'. aStream tab. aStream nextPutAll: 'Average'. aStream cr; tab. aStream nextPutAll: 'Objects'. aStream tab. aStream nextPutAll: 'Value'. aStream tab. aStream nextPutAll: 'Value'. aStream tab. aStream nextPutAll: 'Value' secondHeader: aStream aStream cr; tab. aStream nextPutAll: 'Number of'. aStream cr. aStream nextPutAll: 'Entry'. aStream tab. aStream nextPutAll: 'Objects'. aStream tab. aStream nextPutAll: 'Frequency'. private newLower: lowerNum upper: upperNum by: stepAmount tallyArray ← Array new: (upperNum - lowerNum // stepAmount). tallyArray atAllPut: 0. lowerBound ← lowerNum. upperBound ← upperNum. step ← stepAmount. minValue ← maxValue ← nil. totalValues ← 0. extraEntries ← 0

A simulation of visitors to a museum serves as an example of the use of a Histogram. Museum is like NothingAtAll in that Visitors arrive and look around. The Visitors take a varying amount of time to look around, depending on their interest in the museum artifacts. We assume that this time is normally distributed with a mean of 20 and a standard deviation of 5. Visitors come to the museum throughout the day, one every 5 to 10 units of simulated time.

class name	Museum
superclass	Simulation
instance variable names	statistics
instance methods	initialization initialize super initialize. statistics ← Histogram from: 5 to: 45 by: 5 defineArrivalSchedule self scheduleArrivalOf: Visitor accordingTo: (Uniform from: 5 to: 10) scheduling exit: aSimulationObject super exit: aSimulationObject. statistics store: currentTime - aSimulationObject entryTime printStatisticsOn: aStream statistics printStatisticsOn: aStream

In order for class Museum to update the statistics, Visitors must keep track of when they entered the museum and be able to respond to an inquiry as to their time of entry.

class name	Visitor
superclass	SimulationObject
instance variable names	entryTime
instance methods	initialization initialize super initialize. entryTime ← ActiveSimulation time accessing entryTime ↑entryTime simulation control tasks self holdFor: (Normal mean: 20 deviation: 5) next

To create and run the simulation, we evaluate

aSimulation ← Museum new startUp.
[aSimulation time < 50] whileTrue: [aSimulation proceed]

When the Museum was created, a Histogram for statistics was created. Each time a Visitor left the Museum, data was stored in the Histogram. The data consists of the duration of the visit.

After running the simulation until time 50, we ask the Museum for a report.

aSimulation printStatisticsOn: (Disk file: 'museum.report')

The method associated with printStatisticsOn: sends the same message, printStatisticsOn:, to the Histogram, which prints the following information on the file museum.report.

Number of Objects	Minimum Value	Maximum Value	Average Value
64	10.0202	31.2791	20.152
Entry	Number of Objects	Frequency
5-10	0	0
10-15	14	0.21875	XXXXXXXXXXXXXX
15-20	16	0.25	XXXXXXXXXXXXXXXX
20-25	20	0.3125	XXXXXXXXXXXXXXXXXXXX
25-30	13	0.203125	XXXXXXXXXXXXX
30-35	1	0.015625	X
35-40	0	0
40-45	0	0

Tallying Events

As another example of tallying the events in a simulation, we present a commonly-used example of a simulation of Traffic. In this simulation, we tally the number of cars that enter an intersection, distinguishing those that drive straight through the intersection from those that turn left and those that turn right. By observation, we note that twice as many cars go straight as turn right or left, but twice as many turn left as right. A new car arrives at the intersection according to a uniform distribution every 0.5 to 2 units of time (self scheduleArrivalOf: Car accordingTo: (Uniform from: 0.5 to: 2)). We will run the simulation until simulated time exceeds 100.

class name	Traffic
superclass	Simulation
instance variable names	statistics
instance methods	initialization initialize super initialize. statistics ← Dictionary new: 3. statistics at: #straight put: 0. statistics at: #right put: 0. statistics at: #left put: 0 defineArrivalSchedule self scheduleArrivalOf: Car accordingTo: (Uniform from: 0.5 to: 2). self schedule: [self finishUp] at: 100 statistics update: key statistics at: key put: (statistics at: key) + 1 printStatisticsOn: aStream aStream cr. aStream nextPutAll: 'Car Direction Tally' statistics associationsDo: [ :assoc | aStream cr. assoc key printOn: aStream. aStream tab. assoc value printOn: aStream]

Note that in the method associated with defineArrivalSchedule, the action self finishUp is scheduled to occur at simulated time 100. This event will terminate the simulation as desired.

class name	Car
superclass	SimulationObject
instance methods	simulation control tasks "Sample, without replacement, the direction through the intersection that the car will travel." | sample | sample ← SampleSpace data: #(left left right straight straight straight straight straight straight) ActiveSimulation update: sample next

SampleSpace was a class we introduced in Chapter 21. Cars are scheduled to enter the simulation with the sole task of picking a direction to tell the simulation. After running the simulation, we ask the Traffic simulation to report the tallies by sending it the printStatisticsOn: message. A possible outcome of evaluating

aSimulation ← Traffic new startUp.
[aSimulation proceed] whileTrue.
aSimulation printStatisticsOn: (Disk file: 'traffic.data')

is the following information written on the file traffic.data.

Car Direction	Tally
straight	57
right	8
left	15

Event Monitoring

Another possible technique for gathering data from a simulation is to note the occurrence of each (major) event, including the entering and exiting of simulation objects. This is accomplished by creating a subclass of SimulationObject that we call EventMonitor. In this example, a class variable refers to a file onto which notations about their events can be stored. Each message that represents an event to be monitored must be overridden in the subclass to include the instructions for storing information on the file. The method in the superclass is still executed by distributing the message to the pseudo-variable super.

Basically, the notations consist of the time and identification of the receiver (a kind of SimulationObject), and an annotation such as "enters" or "requests" or "releases."

class name	EventMonitor
superclass	SimulationObject
class variable names	DataFile
class methods	class initialization file: aFile DataFile ← aFile
instance methods	scheduling startUp self timeStamp. DataFile nextPutAll: 'enters'. super startUp finishUp super finishUp. self timeStamp. DataFile nextPutAll: 'exits' task language holdFor: aTimeDelay self timeStamp. DataFile nextPutAll: 'holds for'. aTimeDelay printOn: DataFile. super holdFor: aTimeDelay acquire: amount ofResource: resourceName | aStaticResource | "Store fact that resource is being requested." self timeStamp. DataFile nextPutAll: 'requests'. amount printOn: DataFile. DataFile nextPutAll: 'of', resourceName. "Now try to get the resource." aStaticResource ← super acquire: amount ofResource: resourceName. "Returns here when resource is obtained; store the fact." self timeStamp. DataFile nextPutAll: 'obtained'. amount printOn: DataFile. DataFile nextPutAll: 'of ', resourceName. ↑aStaticResource acquire: amount ofResource: resourceName withPriority: priorityNumber | aStaticResource | "Store fact that resource is being requested" self timeStamp. DataFile nextPutAll: 'requests'. amount printOn: DataFile. DataFile nextPutAll: 'at priority'. priorityNumber printOn: DataFile. DataFile nextPutAll: 'of', resourceName. "Now try to get the resource." aStaticResource ← super acquire amount ofResource: resourceName withPriority: priorityNumber. "Returns here when resource is obtained; store the fact." self timeStamp. DataFile nextPutAll: "obtained'. amount printOn: DataFile. DataFile nextPutAll: 'of', resourceName. ↑aStaticResource produce: amount ofResource: resourceName self timeStamp. DataFile nextPutAll: 'produces' amount printOn: DataFile. DataFile nextPutAll: 'of', resourceName. super produce amount ofResource resourceName release: aStaticResource self timeStamp. DataFile nextPutAll: 'releases' aStaticResource amount printOn: DataFile. DataFile nextPutAll: 'of', aStaticResource name. super release: aStaticResource acquireResource: resourceName | anEvent | "Store fact that resource is being requested" self timeStamp. DataFile nextPutAll: 'wants to serve for'. DataFile nextPutAll: resourceName. "Now try to get the resource." anEvent ← super acquireResource resourceName. "Returns here when resource is obtained store the fact." self timeStamp. DataFile nextPutAll: 'can serve" anEvent condition printOn: DataFile. ↑anEvent produceResource: resourceName self timeStamp. DataFile nextPutAll: 'wants to get service as' DataFile nextPutAll: resourceName. super produce amount ofResource resourceName resume: anEvent self timeStamp. DataFile nextPutAll: 'resumes'. anEvent condition printOn: DataFile. super resume: anEvent private timeStamp DataFile cr. ActiveSimulation time printOn: DataFile. DataFile tab. self printOn: DataFile.

We can monitor the events of the NothingAtAll simulation consisting of arrivals of Visitors and default simulations (DoNothings). Except for creating Visitor and DoNothing as subclassses of EventMonitor rather than of SimulationObject, the class definitions are the same.

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

NothingAtAll is redefined so that the default simulation is an EventMonitor.

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

After executing

Visitor file: (Disk file: 'NothingAtAll.events').
    "This informs DoNothing too"
aSimulation ← NothingAtAll new startUp.
[aSimulation time < 25] whileTrue: [aSimulation proceed]

the file 'NothingAtAll.events' contains the following information

0.0	a DoNothing enters
0.0	a DoNothing exits
3.0	a Visitor enters
3.0	a Visitor holds for 7.5885
4.32703	a DoNothing enters
4.32703	a DoNothing exits
7.74896	a Visitor enters
7.74896	a Visitor holds for 4.14163
8.20233	a DoNothing enters
8.20233	a DoNothing exits
10.5885	a Visitor exits
11.8906	a Visitor exits
12.5153	a DoNothing enters
12.5153	a DoNothing exits
14.2642	a Visitor enters
14.2642	a Visitor holds for 4.51334
16.6951	a DoNothing enters
16.6951	a DoNothing exits
18.7776	a Visitor exits
19.8544	a Visitor enters
19.8544	a Visitor holds for 5.10907
20.5342	a DoNothing enters
20.5342	a DoNothing exits
23.464	a DoNothing enters
23.464	a DoNothing exits
24.9635	a Visitor exits

Distinctively labeling each arriving SimulationObject might improve the ability to follow the sequence of events. The goal is to have a trace for an execution of the NothingAtAll simulation look like the following.

0.0	DoNothing 1 enters
0.0	DoNothing 1 exits
3.0	Visitor 1 enters
3.0	Visitor 1 holds for 7.5885
4.32703	DoNothing 2 enters
4.32703	DoNothing 2 exits
7.74896	Visitor 2 enters
7.74896	Visitor 2 holds for 4.14163
8.20233	DoNothing 3 enters
8.20233	DoNothing 3 exits
10.5885	Visitor 1 exits
11.8906	Visitor 2 exits
12.5153	DoNothing 4 enters
12.5153	DoNothing 4 exits
14.2642	Visitor 3 enters
14.2642	Visitor 3 holds for 4.51334
16.6951	DoNothing 5 enters
16.6951	DoNothing 5 exits
18.7776	Visitor 3 exits
19.8544	Visitor 4 enters
19.8544	Visitor 4 holds for 5.10907
20.5342	DoNothing 6 enters
20.5342	DoNothing 6 exits
23.464	DoNothing 7 enters
23.464	DoNothing 7 exits
24.9635	Visitor 4 exits

Each subclass of EventMonitor must create its own sequence of labels. EventMonitor sets up a label framework in which the subclass can implement a way of distinguishing its instances. EventMonitor itself provides a model that the subclasses can duplicate; in this way, a default simulation using instances of EventMonitor can be used to produce the trace shown above. In addition to the scheduling, task language and private, messages shown in the earlier implementation of EventMonitor, the class description has the following messages.

class name	EventMonitor
superclass	SimulationObject
instance variable names	label
class variable names	DataFile Counter
class methods	class initialization file: aFile DataFile ← aFile. Counter ← 0
instance methods	initialization initialize super initialize. self setLabel accessing setLabel Counter ← Counter + 1. label ← Counter printString label ↑label printing printOn: aStream self class name printOn: aStream. aStream space. aStream nextPutAll: self label

Visitor, as a subclass of EventMonitor, has to have an independent class variable to act as the counter of its instances. The class description of Visitor is now

class name	Visitor
superclass	EventMonitor
class variable names	MyCounter
class methods	class initialization file: aFile super file: aFile. MyCounter ← 0
instance methods	accessing setLabel MyCounter ← MyCounter + 1. label ← MyCounter printString simulation control tasks self holdFor: (Uniform from: 4.0 to: 10.0) next

MyCounter is set to 0 when the instance is tom initialize; the method is found in class EventMonitor. Printing retrieves the label that Visitor redefines with respect to MyCounter. We let DoNothing use the class variable, Counter, of its superclass. Then the desired trace will be produced using these definitions.