Smalltalk80LanguageImplementation:Chapter 23

From 흡혈양파의 번역工房
Revision as of 15:43, 28 April 2014 by Onionmixer (talk | contribs) (SMALLTALK80 Chapter 23 Statistics Gathering in Event-Driven Simulations 페이지 추가)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
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
    extrance
        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 |
        minVatue isNil
            ifTrue: [minValue  maxValue  aValue]
            ifFalse: [minValue  minValue min: aValue.
                maxValue  maxValue max: aValue].
        totalValues  totalValues + aValue.
        (self contains: aValue)
            ifTrue: [index  (aValue - IowerBound // 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.
        maxVatue 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 nextPutAtl: '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 EvenMonitor
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
instace 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.


Notes