accessing

### setLabel

TruckCounter ← TruckCounter + 1.

label ← TruckCounter printString

instance methods

simulation control

### tasks

| truck |

truck ← self acquire: 1 of Resource: '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.

<table><tr><td>0</td><td>CarRenter 1 enters</td></tr><tr><td>0</td><td>CarRenter 1 requests 1 of Car</td></tr><tr><td>0</td><td>CarRenter 1 obtained 1 of Car</td></tr><tr><td>0</td><td>CarRenter 1 holds for 460.426</td></tr><tr><td>10</td><td>TruckRenter 1 enters</td></tr><tr><td>10</td><td>TruckRenter 1 requests 1 of Truck</td></tr><tr><td>10</td><td>TruckRenter 1 obtained 1 of Truck</td></tr><tr><td>10</td><td>TruckRenter 1 holds for 87.2159</td></tr><tr><td>26.2079</td><td>CarRenter 2 enters</td></tr><tr><td>26.2079</td><td>CarRenter 2 requests 1 of Car</td></tr><tr><td>26.2079</td><td>CarRenter 2 obtained 1 of Car</td></tr><tr><td>26.2079</td><td>CarRenter 2 holds for 318.966</td></tr><tr><td>27.4147</td><td>CarRenter 3 enters</td></tr><tr><td>27.4147</td><td>CarRenter 3 requests 1 of Car</td></tr><tr><td>27.4147</td><td>CarRenter 3 obtained 1 of Car</td></tr><tr><td>27.4147</td><td>CarRenter 3 holds for 244.867</td></tr><tr><td>51.5614</td><td>CarRenter 4 enters</td></tr><tr><td>51.5614</td><td>CarRenter 4 requests 1 of Car</td></tr><tr><td>51.5614</td><td>CarRenter 4 obtained 1 of Car</td></tr><tr><td>51.5614</td><td>CarRenter 4 holds for 276.647</td></tr><tr><td>78.0957</td><td>CarRenter 5 enters</td></tr></table>
<table>
  <tr>
    <td>78.0957</td>
    <td>CarRenter 5 requests 1 of Car</td>
  </tr>
  <tr>
    <td>78.0957</td>
    <td>CarRenter 5 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>78.0957</td>
    <td>CarRenter 5 holds for 333.212</td>
  </tr>
  <tr>
    <td>93.121</td>
    <td>CarRenter 6 enters</td>
  </tr>
  <tr>
    <td>93.121</td>
    <td>CarRenter 6 requests 1 of Car</td>
  </tr>
  <tr>
    <td>93.121</td>
    <td>CarRenter 6 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>93.121</td>
    <td>CarRenter 6 holds for 359.718</td>
  </tr>
  <tr>
    <td>97.2159</td>
    <td>TruckRenter 1 releases 1 of Truck</td>
  </tr>
  <tr>
    <td>97.2159</td>
    <td>TruckRenter 1 exits</td>
  </tr>
  <tr>
    <td>99.0265</td>
    <td>CarRenter 7 enters</td>
  </tr>
  <tr>
    <td>99.0265</td>
    <td>CarRenter 7 requests 1 of Car</td>
  </tr>
  <tr>
    <td>99.0265</td>
    <td>CarRenter 7 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>99.0265</td>
    <td>CarRenter 7 holds for 417.572</td>
  </tr>
  <tr>
    <td>106.649</td>
    <td>CarRenter 8 enters</td>
  </tr>
  <tr>
    <td>106.649</td>
    <td>CarRenter 8 requests 1 of Car</td>
  </tr>
  <tr>
    <td>106.649</td>
    <td>CarRenter 8 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>106.649</td>
    <td>CarRenter 8 holds for 294.43</td>
  </tr>
  <tr>
    <td>107.175</td>
    <td>CarRenter 9 enters</td>
  </tr>
  <tr>
    <td>107.175</td>
    <td>CarRenter 9 requests 1 of Car</td>
  </tr>
  <tr>
    <td>107.175</td>
    <td>CarRenter 9 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>107.175</td>
    <td>CarRenter 9 holds for 314.198</td>
  </tr>
  <tr>
    <td>121.138</td>
    <td>CarRenter 10 enters</td>
  </tr>
  <tr>
    <td>121.138</td>
    <td>CarRenter 10 requests 1 of Car</td>
  </tr>
  <tr>
    <td>121.138</td>
    <td>CarRenter 10 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>121.138</td>
    <td>CarRenter 10 holds for 467.032</td>
  </tr>
  <tr>
    <td>127.018</td>
    <td>TruckRenter 2 enters</td>
  </tr>
  <tr>
    <td>127.018</td>
    <td>TruckRenter 2 requests 1 of Truck</td>
  </tr>
  <tr>
    <td>127.018</td>
    <td>TruckRenter 2 obtained 1 of Truck</td>
  </tr>
  <tr>
    <td>127.018</td>
    <td>TruckRenter 2 holds for 74.5047</td>
  </tr>
  <tr>
    <td>145.513</td>
    <td>CarRenter 11 enters</td>
  </tr>
  <tr>
    <td>145.513</td>
    <td>CarRenter 11 requests 1 of Car</td>
  </tr>
  <tr>
    <td>145.513</td>
    <td>CarRenter 11 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>145.513</td>
    <td>CarRenter 11 holds for 243.776</td>
  </tr>
  <tr>
    <td>166.214</td>
    <td>CarRenter 12 enters</td>
  </tr>
  <tr>
    <td>166.214</td>
    <td>CarRenter 12 requests 1 of Car</td>
  </tr>
  <tr>
    <td>166.214</td>
    <td>CarRenter 12 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>166.214</td>
    <td>CarRenter 12 holds for 429.247</td>
  </tr>
  <tr>
    <td>172.253</td>
    <td>CarRenter 13 enters</td>
  </tr>
  <tr>
    <td>172.253</td>
    <td>CarRenter 13 requests 1 of Car</td>
  </tr>
  <tr>
    <td>172.253</td>
    <td>CarRenter 13 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>172.253</td>
    <td>CarRenter 13 holds for 370.909</td>
  </tr>
  <tr>
    <td>191.438</td>
    <td>TruckRenter 3 enters</td>
  </tr>
  <tr>
    <td>191.438</td>
    <td>TruckRenter 3 requests 1 of Truck</td>
  </tr>
  <tr>
    <td>191.438</td>
    <td>TruckRenter 3 obtained 1 of Truck</td>
  </tr>
  <tr>
    <td>191.438</td>
    <td>TruckRenter 3 holds for 225.127</td>
  </tr>
</table>
<table>
  <tr>
    <td>201.523</td>
    <td>TruckRenter 2 releases 1 of Truck</td>
  </tr>
  <tr>
    <td>201.523</td>
    <td>TruckRenter 2 exits</td>
  </tr>
  <tr>
    <td>220.102</td>
    <td>CarRenter 14 enters</td>
  </tr>
  <tr>
    <td>220.102</td>
    <td>CarRenter 14 requests 1 of Car</td>
  </tr>
  <tr>
    <td>220.102</td>
    <td>CarRenter 14 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>220.102</td>
    <td>CarRenter 14 holds for 334.684</td>
  </tr>
  <tr>
    <td>252.055</td>
    <td>CarRenter 15 enters</td>
  </tr>
  <tr>
    <td>252.055</td>
    <td>CarRenter 15 requests 1 of Car</td>
  </tr>
  <tr>
    <td>252.055</td>
    <td>CarRenter 15 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>252.055</td>
    <td>CarRenter 15 holds for 408.358</td>
  </tr>
  <tr>
    <td>269.964</td>
    <td>CarRenter 16 enters</td>
  </tr>
  <tr>
    <td>269.964</td>
    <td>CarRenter 16 requests 1 of Car</td>
  </tr>
  <tr>
    <td>272.282</td>
    <td>CarRenter 3 releases 1 of Car</td>
  </tr>
  <tr>
    <td>272.282</td>
    <td>CarRenter 3 exits</td>
  </tr>
  <tr>
    <td>272.282</td>
    <td>CarRenter 16 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>272.282</td>
    <td>CarRenter 16 holds for 281.349</td>
  </tr>
  <tr>
    <td>292.375</td>
    <td>CarRenter 17 enters</td>
  </tr>
  <tr>
    <td>292.375</td>
    <td>CarRenter 17 requests 1 of Car</td>
  </tr>
  <tr>
    <td>328.208</td>
    <td>CarRenter 4 releases 1 of Car</td>
  </tr>
  <tr>
    <td>328.208</td>
    <td>CarRenter 4 exits</td>
  </tr>
  <tr>
    <td>328.208</td>
    <td>CarRenter 17 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>328.208</td>
    <td>CarRenter 17 holds for 270.062</td>
  </tr>
  <tr>
    <td>345.174</td>
    <td>CarRenter 2 releases 1 of Car</td>
  </tr>
  <tr>
    <td>345.174</td>
    <td>CarRenter 2 exits</td>
  </tr>
  <tr>
    <td>350.53</td>
    <td>CarRenter 18 enters</td>
  </tr>
  <tr>
    <td>350.53</td>
    <td>CarRenter 18 requests 1 of Car</td>
  </tr>
  <tr>
    <td>350.53</td>
    <td>CarRenter 18 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>350.53</td>
    <td>CarRenter 18 holds for 297.154</td>
  </tr>
  <tr>
    <td>354.126</td>
    <td>CarRenter 19 enters</td>
  </tr>
  <tr>
    <td>354.126</td>
    <td>CarRenter 19 requests 1 of Car</td>
  </tr>
  <tr>
    <td>358.269</td>
    <td>TruckRenter 4 enters</td>
  </tr>
  <tr>
    <td>358.269</td>
    <td>TruckRenter 4 requests 1 of Truck</td>
  </tr>
  <tr>
    <td>358.269</td>
    <td>TruckRenter 4 obtained 1 of Truck</td>
  </tr>
  <tr>
    <td>358.269</td>
    <td>TruckRenter 4 holds for 173.648</td>
  </tr>
  <tr>
    <td>367.88</td>
    <td>TruckRenter 5 enters</td>
  </tr>
  <tr>
    <td>367.88</td>
    <td>TruckRenter 5 requests 1 of Truck</td>
  </tr>
  <tr>
    <td>367.88</td>
    <td>TruckRenter 5 obtained 1 of Truck</td>
  </tr>
  <tr>
    <td>367.88</td>
    <td>TruckRenter 5 holds for 175.972</td>
  </tr>
  <tr>
    <td>389.289</td>
    <td>CarRenter 11 releases 1 of Car</td>
  </tr>
  <tr>
    <td>389.289</td>
    <td>CarRenter 11 exits</td>
  </tr>
  <tr>
    <td>389.289</td>
    <td>CarRenter 19 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>389.289</td>
    <td>CarRenter 19 holds for 379.017</td>
  </tr>
  <tr>
    <td>401.079</td>
    <td>CarRenter 8 releases 1 of Car</td>
  </tr>
  <tr>
    <td>401.079</td>
    <td>CarRenter 8 exits</td>
  </tr>
  <tr>
    <td>402.224</td>
    <td>CarRenter 20 enters</td>
  </tr>
</table>
<table>
  <tr>
    <td>402.224</td>
    <td>CarRenter 20 requests 1 of Car</td>
  </tr>
  <tr>
    <td>402.224</td>
    <td>CarRenter 20 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>402.224</td>
    <td>CarRenter 20 holds for 341.188</td>
  </tr>
  <tr>
    <td>410.431</td>
    <td>TruckRenter 6 enters</td>
  </tr>
  <tr>
    <td>410.431</td>
    <td>TruckRenter 6 requests 1 of Truck</td>
  </tr>
  <tr>
    <td>411.307</td>
    <td>CarRenter 5 releases 1 of Car</td>
  </tr>
  <tr>
    <td>411.307</td>
    <td>CarRenter 5 exits</td>
  </tr>
  <tr>
    <td>416.566</td>
    <td>TruckRenter 3 releases 1 of Truck</td>
  </tr>
  <tr>
    <td>416.566</td>
    <td>TruckRenter 3 exits</td>
  </tr>
  <tr>
    <td>416.566</td>
    <td>TruckRenter 6 obtained 1 of Truck</td>
  </tr>
  <tr>
    <td>416.566</td>
    <td>TruckRenter 6 holds for 119.076</td>
  </tr>
  <tr>
    <td>421.373</td>
    <td>CarRenter 9 releases 1 of Car</td>
  </tr>
  <tr>
    <td>421.373</td>
    <td>CarRenter 9 exits</td>
  </tr>
  <tr>
    <td>422.802</td>
    <td>CarRenter 21 enters</td>
  </tr>
  <tr>
    <td>422.802</td>
    <td>CarRenter 21 requests 1 of Car</td>
  </tr>
  <tr>
    <td>422.802</td>
    <td>CarRenter 21 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>422.802</td>
    <td>CarRenter 21 holds for 241.915</td>
  </tr>
  <tr>
    <td>452.839</td>
    <td>CarRenter 6 releases 1 of Car</td>
  </tr>
  <tr>
    <td>452.839</td>
    <td>CarRenter 6 exits</td>
  </tr>
  <tr>
    <td>460.426</td>
    <td>CarRenter 1 releases 1 of Car</td>
  </tr>
  <tr>
    <td>460.426</td>
    <td>CarRenter 1 exits</td>
  </tr>
  <tr>
    <td>512.263</td>
    <td>CarRenter 22 enters</td>
  </tr>
  <tr>
    <td>512.263</td>
    <td>CarRenter 22 requests 1 of Car</td>
  </tr>
  <tr>
    <td>512.263</td>
    <td>CarRenter 22 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>512.263</td>
    <td>CarRenter 22 holds for 277.035</td>
  </tr>
  <tr>
    <td>516.598</td>
    <td>CarRenter 7 releases 1 of Car</td>
  </tr>
  <tr>
    <td>516.598</td>
    <td>CarRenter 7 exits</td>
  </tr>
  <tr>
    <td>531.917</td>
    <td>TruckRenter 4 releases 1 of Truck</td>
  </tr>
  <tr>
    <td>531.917</td>
    <td>TruckRenter 4 exits</td>
  </tr>
  <tr>
    <td>535.642</td>
    <td>TruckRenter 6 releases 1 of Truck</td>
  </tr>
  <tr>
    <td>535.642</td>
    <td>TruckRenter 6 exits</td>
  </tr>
  <tr>
    <td>543.162</td>
    <td>CarRenter 13 releases 1 of Car</td>
  </tr>
  <tr>
    <td>543.162</td>
    <td>CarRenter 13 exits</td>
  </tr>
  <tr>
    <td>543.852</td>
    <td>TruckRenter 5 releases 1 of Truck</td>
  </tr>
  <tr>
    <td>543.852</td>
    <td>TruckRenter 5 exits</td>
  </tr>
  <tr>
    <td>553.631</td>
    <td>CarRenter 16 releases 1 of Car</td>
  </tr>
  <tr>
    <td>553.631</td>
    <td>CarRenter 16 exits</td>
  </tr>
  <tr>
    <td>554.786</td>
    <td>CarRenter 14 releases 1 of Car</td>
  </tr>
  <tr>
    <td>554.786</td>
    <td>CarRenter 14 exits</td>
  </tr>
  <tr>
    <td>574.617</td>
    <td>CarRenter 23 enters</td>
  </tr>
  <tr>
    <td>574.617</td>
    <td>CarRenter 23 requests 1 of Car</td>
  </tr>
  <tr>
    <td>574.617</td>
    <td>CarRenter 23 obtained 1 of Car</td>
  </tr>
  <tr>
    <td>574.617</td>
    <td>CarRenter 23 holds for 436.783</td>
  </tr>
  <tr>
    <td>588.171</td>
    <td>CarRenter 10 releases 1 of Car</td>
  </tr>
  <tr>
    <td>588.171</td>
    <td>CarRenter 10 exits</td>
  </tr>
</table>
<table><tr><td>591.51</td><td>CarRenter 24 enters</td></tr><tr><td>591.51</td><td>CarRenter 24 requests 1 of Car</td></tr><tr><td>591.51</td><td>CarRenter 24 obtained 1 of Car</td></tr><tr><td>591.51</td><td>CarRenter 24 holds for 430.067</td></tr><tr><td>595.461</td><td>CarRenter 12 releases 1 of Car</td></tr><tr><td>595.461</td><td>CarRenter 12 exits</td></tr><tr><td>598.27</td><td>CarRenter 17 releases 1 of Car</td></tr><tr><td>598.27</td><td>CarRenter 17 exits</td></tr><tr><td>599.876</td><td>CarRenter 25 enters</td></tr><tr><td>599.876</td><td>CarRenter 25 requests 1 of Car</td></tr><tr><td>599.876</td><td>CarRenter 25 obtained 1 of Car</td></tr><tr><td>599.876</td><td>CarRenter 25 holds for 472.042</td></tr><tr><td>642.188</td><td>TruckRenter 7 enters</td></tr><tr><td>642.188</td><td>TruckRenter 7 requests 1 of Truck</td></tr><tr><td>642.188</td><td>TruckRenter 7 obtained 1 of Truck</td></tr><tr><td>642.188</td><td>TruckRenter 7 holds for 190.586</td></tr></table>

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 event-driven 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.

<table><tr><td>class name</td><td>FileSystem</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance variable names</td><td>statistics</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>initialize-release</td><td></td></tr></table>

**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.

<table><tr><td>class name</td><td>FileSystemReader</td></tr><tr><td>superclass</td><td>EventMonitor</td></tr><tr><td>instance methods</td><td></td></tr></table>

accessing

**label: aString**

label ← aString

simulation control

**tasks**

| file |

"The repeated sequence of tasks is as follows"

[true]

while True:

[file ← self acquire: 1 of Resource: '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
<table><tr><td>class name</td><td>FileSystemWriter</td></tr><tr><td>superclass</td><td>EventMonitor</td></tr><tr><td>instance methods</td><td></td></tr></table>

accessing

label: aString

label ← aString

simulation control

tasks

| file |

"The repeated sequence of tasks is as follows"

[true]

while True:

[

self holdFor: 5.0.

file ← self acquire: 3 of Resource: '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 lan- guage. 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.

<table><tr><td>0.0</td><td>first FileSystemReader enters</td></tr><tr><td>0.0</td><td>first FileSystemReader requests 1 of File</td></tr><tr><td>0.0</td><td>first FileSystemReader obtained 1 of File</td></tr><tr><td>0.0</td><td>first FileSystemReader holds for 2.0</td></tr><tr><td>0.0</td><td>first FileSystemWriter enters</td></tr><tr><td>0.0</td><td>first FileSystemWriter holds for 5.0</td></tr><tr><td>0.0</td><td>second FileSystemReader enters</td></tr><tr><td>0.0</td><td>second FileSystemReader requests 1 of File</td></tr><tr><td>0.0</td><td>second FileSystemReader obtained 1 of File</td></tr><tr><td>0.0</td><td>second FileSystemReader holds for 2.0</td></tr></table>
<table>
  <tr>
    <td>1.0</td>
    <td>second FileSystemWriter enters</td>
  </tr>
  <tr>
    <td>1.0</td>
    <td>second FileSystemWriter holds for 5.0</td>
  </tr>
  <tr>
    <td>2.0</td>
    <td>second FileSystemReader releases 1 of File</td>
  </tr>
  <tr>
    <td>2.0</td>
    <td>second FileSystemReader holds for 5.0</td>
  </tr>
  <tr>
    <td>2.0</td>
    <td>first FileSystemReader releases 1 of File</td>
  </tr>
  <tr>
    <td>2.0</td>
    <td>first FileSystemReader holds for 5.0</td>
  </tr>
  <tr>
    <td>2.0</td>
    <td>third FileSystemReader enters</td>
  </tr>
  <tr>
    <td>2.0</td>
    <td>third FileSystemReader requests 1 of File</td>
  </tr>
  <tr>
    <td>2.0</td>
    <td>third FileSystemReader obtained 1 of File</td>
  </tr>
  <tr>
    <td>2.0</td>
    <td>third FileSystemReader holds for 2.0</td>
  </tr>
  <tr>
    <td>4.0</td>
    <td>third FileSystemReader releases 1 of File</td>
  </tr>
  <tr>
    <td>4.0</td>
    <td>third FileSystemReader holds for 5.0</td>
  </tr>
  <tr>
    <td>5.0</td>
    <td>first FileSystemWriter requests 3 of File</td>
  </tr>
  <tr>
    <td>5.0</td>
    <td>first FileSystemWriter obtained 3 of File</td>
  </tr>
  <tr>
    <td>5.0</td>
    <td>first FileSystemWriter holds for 3.0</td>
  </tr>
  <tr>
    <td>6.0</td>
    <td>second FileSystemWriter requests 3 of File</td>
  </tr>
  <tr>
    <td>7.0</td>
    <td>first FileSystemReader requests 1 of File</td>
  </tr>
  <tr>
    <td>7.0</td>
    <td>second FileSystemReader requests 1 of File</td>
  </tr>
  <tr>
    <td>8.0</td>
    <td>first FileSystemWriter releases 3 of File</td>
  </tr>
  <tr>
    <td>8.0</td>
    <td>first FileSystemWriter holds for 5.0</td>
  </tr>
  <tr>
    <td>8.0</td>
    <td>second FileSystemWriter obtained 3 of File</td>
  </tr>
  <tr>
    <td>8.0</td>
    <td>second FileSystemWriter holds for 3.0</td>
  </tr>
  <tr>
    <td>9.0</td>
    <td>third FileSystemReader requests 1 of File</td>
  </tr>
  <tr>
    <td>11.0</td>
    <td>second FileSystemWriter releases 3 of File</td>
  </tr>
  <tr>
    <td>11.0</td>
    <td>second FileSystemWriter holds for 5.0</td>
  </tr>
  <tr>
    <td>11.0</td>
    <td>first FileSystemReader obtained 1 of File</td>
  </tr>
  <tr>
    <td>11.0</td>
    <td>first FileSystemReader holds for 2.0</td>
  </tr>
  <tr>
    <td>11.0</td>
    <td>second FileSystemReader obtained 1 of File</td>
  </tr>
  <tr>
    <td>11.0</td>
    <td>second FileSystemReader holds for 2.0</td>
  </tr>
  <tr>
    <td>11.0</td>
    <td>third FileSystemReader obtained 1 of File</td>
  </tr>
  <tr>
    <td>11.0</td>
    <td>third FileSystemReader holds for 2.0</td>
  </tr>
  <tr>
    <td>13.0</td>
    <td>third FileSystemReader releases 1 of File</td>
  </tr>
  <tr>
    <td>13.0</td>
    <td>third FileSystemReader holds for 5.0</td>
  </tr>
  <tr>
    <td>13.0</td>
    <td>second FileSystemReader releases 1 of File</td>
  </tr>
  <tr>
    <td>13.0</td>
    <td>second FileSystemReader holds for 5.0</td>
  </tr>
  <tr>
    <td>13.0</td>
    <td>first FileSystemReader releases 1 of File</td>
  </tr>
  <tr>
    <td>13.0</td>
    <td>first FileSystemReader holds for 5.0</td>
  </tr>
  <tr>
    <td>13.0</td>
    <td>first FileSystemWriter requests 3 of File</td>
  </tr>
  <tr>
    <td>13.0</td>
    <td>first FileSystemWriter obtained 3 of File</td>
  </tr>
  <tr>
    <td>13.0</td>
    <td>first FileSystemWriter holds for 3.0</td>
  </tr>
  <tr>
    <td>16.0</td>
    <td>first FileSystemWriter releases 3 of File</td>
  </tr>
  <tr>
    <td>16.0</td>
    <td>first FileSystemWriter holds for 5.0</td>
  </tr>
  <tr>
    <td>16.0</td>
    <td>second FileSystemWriter requests 3 of File</td>
  </tr>
  <tr>
    <td>16.0</td>
    <td>second FileSystemWriter obtained 3 of File</td>
  </tr>
  <tr>
    <td>16.0</td>
    <td>second FileSystemWriter holds for 3.0</td>
  </tr>
</table>
<table><tr><td>18.0</td><td>first FileSystemReader requests 1 of File</td></tr><tr><td>18.0</td><td>second FileSystemReader requests 1 of File</td></tr><tr><td>18.0</td><td>third FileSystemReader requests 1 of File</td></tr><tr><td>19.0</td><td>second FileSystemWriter releases 3 of File</td></tr><tr><td>19.0</td><td>second FileSystemWriter holds for 5.0</td></tr><tr><td>19.0</td><td>first FileSystemReader obtained 1 of File</td></tr><tr><td>19.0</td><td>first FileSystemReader holds for 2.0</td></tr><tr><td>19.0</td><td>second FileSystemReader obtained 1 of File</td></tr><tr><td>19.0</td><td>second FileSystemReader holds for 2.0</td></tr><tr><td>19.0</td><td>third FileSystemReader obtained 1 of File</td></tr><tr><td>19.0</td><td>third FileSystemReader holds for 2.0</td></tr><tr><td>21.0</td><td>third FileSystemReader releases 1 of File</td></tr><tr><td>21.0</td><td>third FileSystemReader holds for 5.0</td></tr><tr><td>21.0</td><td>second FileSystemReader releases 1 of File</td></tr><tr><td>21.0</td><td>second FileSystemReader holds for 5.0</td></tr><tr><td>21.0</td><td>first FileSystemReader releases 1 of File</td></tr><tr><td>21.0</td><td>first FileSystemReader holds for 5.0</td></tr><tr><td>21.0</td><td>first FileSystemWriter requests 3 of File</td></tr><tr><td>21.0</td><td>first FileSystemWriter obtained 3 of File</td></tr><tr><td>21.0</td><td>first FileSystemWriter holds for 3.0</td></tr><tr><td>24.0</td><td>first FileSystemWriter releases 3 of File</td></tr><tr><td>24.0</td><td>first FileSystemWriter holds for 5.0</td></tr><tr><td>24.0</td><td>second FileSystemWriter requests 3 of File</td></tr><tr><td>24.0</td><td>second FileSystemWriter obtained 3 of File</td></tr><tr><td>24.0</td><td>second FileSystemWriter holds for 3.0</td></tr></table>

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, aindeStream. The result is

<table><tr><td>reads</td><td>9</td></tr><tr><td>writes</td><td>5</td></tr></table>

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.

<table><tr><td>class name</td><td>CarDealer</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance variable names</td><td>statistics</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>initialize-release</td><td></td></tr></table>

**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 CarDelivery object 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.

<table><thead><tr><th>Entry</th><th>Number of Objects</th><th>Minimum Value</th><th>Maximum Value</th><th>Average Value</th></tr></thead><tbody><tr><td>1-8</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>8-15</td><td>3</td><td>0.0545454</td><td>XXX</td><td></td></tr><tr><td>15-22</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>22-29</td><td>1</td><td>0.0181818</td><td>X</td><td></td></tr><tr><td>29-36</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>36-43</td><td>1</td><td>0.0181818</td><td>X</td><td></td></tr><tr><td>43-50</td><td>0</td><td>0.0</td><td></td><td></td></tr><tr><td>50-57</td><td>1</td><td>0.0181818</td><td>X</td><td></td></tr><tr><td>57-64</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>64-71</td><td>1</td><td>0.0181818</td><td>X</td><td></td></tr><tr><td>71-78</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>78-85</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>85-92</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>92-99</td><td>0</td><td>0.0</td><td></td><td></td></tr><tr><td>99-106</td><td>0</td><td>0.0</td><td></td><td></td></tr><tr><td>106-113</td><td>1</td><td>0.0181818</td><td>X</td><td></td></tr><tr><td>113-120</td><td>3</td><td>0.0545454</td><td>XXX</td><td></td></tr><tr><td>120-127</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>127-134</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>134-141</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>141-148</td><td>1</td><td>0.0181818</td><td>X</td><td></td></tr><tr><td>148-155</td><td>0</td><td>0.0</td><td></td><td></td></tr><tr><td>155-162</td><td>1</td><td>0.0181818</td><td>X</td><td></td></tr><tr><td>162-169</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>169-176</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>176-183</td><td>1</td><td>0.0181818</td><td>X</td><td></td></tr><tr><td>183-190</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>190-197</td><td>2</td><td>0.0363636</td><td>XX</td><td></td></tr><tr><td>197-204</td><td>1</td><td>0.0181818</td><td>X</td><td></td></tr><tr><td>204-211</td><td>0</td><td>0.0</td><td></td><td></td></tr></tbody></table>

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.

<table><tr><td>class name</td><td>Ferry</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance variable names</td><td>carsOnBoard<br>currentSide</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>simulation control</td><td></td></tr></table>

### 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.

<table><tr><td>class name</td><td>Ferry</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance variable names</td><td>emptyTrips<br/>carsOnBoard<br/>currentSide<br/>trips<br/>totalCars<br/>emptyTrips</td></tr></table>

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.

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

This continues until ...

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

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.

<table><tr><td>420.0</td><td>Ferry 1 enters<br>load at Mainland: there are now 4 cars waiting at Mainland and 1 car waiting at Island</td></tr><tr><td>420.0</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5</td></tr><tr><td>420.5</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5</td></tr><tr><td>421.0</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5</td></tr><tr><td>421.5</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5<br>cross over</td></tr><tr><td>422.0</td><td>Ferry 1 holds for 8.56369<br>unload 4 cars at Island: there are now 2 cars waiting at Mainland and 1 car waiting at Island</td></tr><tr><td>430.564</td><td>Ferry 1 holds for 2.0<br>load at Island: there are now 2 cars at Mainland and 3 cars at Island</td></tr><tr><td>432.564</td><td>Ferry 1 obtained 1 of Island, holds for 0.5</td></tr><tr><td>433.064</td><td>Ferry 1 obtained 1 of Island, holds for 0.5</td></tr><tr><td>433.564</td><td>Ferry 1 obtained 1 of Island, holds for 0.5<br>cross over</td></tr><tr><td>434.064</td><td>Ferry 1 holds for 8.55344<br>unload 3 cars at Mainland: there are now 3 cars waiting at Mainland and 3 cars waiting at Island</td></tr><tr><td>442.617</td><td>Ferry 1 holds for 1.5<br>load at Mainland: there are now 3 cars waiting at Mainland and 0 cars waiting at Island</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>444.117</td>
      <td>Ferry 1 obtained 1 of Mainland, holds for 0.5</td>
    </tr>
    <tr>
      <td>444.617</td>
      <td>Ferry 1 obtained 1 of Mainland, holds for 0.5</td>
    </tr>
    <tr>
      <td>445.117</td>
      <td>Ferry 1 obtained 1 of Mainland, holds for 0.5<br/>cross over</td>
    </tr>
    <tr>
      <td>445.617</td>
      <td>Ferry 1 holds for 8.98081<br/>unload 3 cars at Island: there are now 0 cars waiting<br/>at Mainland and 6 cars waiting at Island</td>
    </tr>
    <tr>
      <td>454.598</td>
      <td>Ferry 1 holds for 1.5<br/>load at Island: there are now 0 cars waiting at Main-<br/>land and 6 cars waiting at Island</td>
    </tr>
    <tr>
      <td>456.098</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5</td>
    </tr>
    <tr>
      <td>456.598</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5</td>
    </tr>
    <tr>
      <td>457.098</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5</td>
    </tr>
    <tr>
      <td>457.598</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5</td>
    </tr>
    <tr>
      <td>458.098</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5</td>
    </tr>
    <tr>
      <td>458.598</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5<br/>cross over</td>
    </tr>
    <tr>
      <td>459.098</td>
      <td>Ferry 1 holds for 7.96448<br/>unload 6 cars at Mainland: there is now 1 car waiting<br/>at Mainland and 0 cars waiting at Island</td>
    </tr>
    <tr>
      <td>467.062</td>
      <td>Ferry 1 holds for 3.0<br/>load at Mainland: there is now 1 car waiting at Main-<br/>land and 1 car waiting at Island</td>
    </tr>
    <tr>
      <td>470.062</td>
      <td>Ferry 1 obtained 1 of Mainland, holds for 0.5<br/>continues until<br/>load at Island</td>
    </tr>
    <tr>
      <td>1299.52</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5</td>
    </tr>
    <tr>
      <td>1300.02</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5<br/>cross over</td>
    </tr>
    <tr>
      <td>1300.52</td>
      <td>Ferry 1 holds for 7.23914<br/>unload 2 cars at Mainland</td>
    </tr>
    <tr>
      <td>1307.76</td>
      <td>Ferry 1 holds for 1.0<br/>load at Mainland: there is now 1 car waiting at Main-<br/>land and 3 cars waiting at Island</td>
    </tr>
    <tr>
      <td>1308.76</td>
      <td>Ferry 1 obtained 1 of Mainland, holds for 0.5<br/>cross over</td>
    </tr>
    <tr>
      <td>1309.26</td>
      <td>Ferry 1 holds for 7.78433<br/>load at Island: there are now 2 cars waiting at<br/>Mainland and 4 cars waiting at Island</td>
    </tr>
    <tr>
      <td>1317.54</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5</td>
    </tr>
    <tr>
      <td>1318.04</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5</td>
    </tr>
    <tr>
      <td>1318.54</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5</td>
    </tr>
    <tr>
      <td>1319.04</td>
      <td>Ferry 1 obtained 1 of Island, holds for 0.5<br/>cross over</td>
    </tr>
  </tbody>
</table>
<table><tr><td>1319.54</td><td>Ferry 1 holds for 8.51123<br/>unload 4 cars at Mainland: there are now 3 cars waiting at Mainland and 0 cars waiting at Island</td></tr><tr><td>1328.05</td><td>Ferry 1 holds for 2.0<br/>load at Mainland: there are now 5 cars waiting at Mainland and 2 cars waiting at Island</td></tr><tr><td>1330.05</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5</td></tr><tr><td>1330.55</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5</td></tr><tr><td>1331.05</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5</td></tr><tr><td>1331.55</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5</td></tr><tr><td>1332.05</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5<br/>cross over</td></tr><tr><td>1332.55</td><td>Ferry 1 holds for 8.17247<br/>unload 5 cars at Island: there is now 1 car waiting at Mainland and 4 cars waiting at Island</td></tr><tr><td>1340.72</td><td>Ferry 1 holds for 2.5<br/>load at Island: there are now 2 cars waiting at Mainland and 4 cars waiting at Island</td></tr><tr><td>1343.22</td><td>Ferry 1 obtained 1 of Island, holds for 0.5</td></tr><tr><td>1343.72</td><td>Ferry 1 obtained 1 of Island, holds for 0.5</td></tr><tr><td>1344.22</td><td>Ferry 1 obtained 1 of Island, holds for 0.5</td></tr><tr><td>1344.72</td><td>Ferry 1 obtained 1 of Island, holds for 0.5<br/>cross over</td></tr><tr><td>1345.22</td><td>Ferry 1 holds for 7.75318<br/>unload at Mainland: there are 2 cars waiting at Mainland and 1 car waiting at Island</td></tr><tr><td>1352.98</td><td>Ferry 1 holds for 2.0<br/>load at Mainland: there are 2 cars waiting at Mainland and 1 car waiting at Island</td></tr><tr><td>1354.98</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5</td></tr><tr><td>1355.48</td><td>Ferry 1 obtained 1 of Mainland, holds for 0.5<br/>cross over</td></tr><tr><td>1355.98</td><td>Ferry 1 holds for 8.54321<br/>unload 2 cars at Island: there are 2 cars waiting at Mainland and 2 cars waiting at Island</td></tr><tr><td>1364.52</td><td>Ferry 1 holds for 1.0<br/>quitting time</td></tr><tr><td>1365.52</td><td>Ferry 1 exits</td></tr></table>

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.
<figure><img src="image_268.png" /></figure>
<figure><img src="image_269.png" /></figure>

25

Coordinated Resources
for Event-Driven
Simulations

The Implementation of Class
ResourceCoordinator

Example: A Car Wash Simulation

Example: A Ferry Service for a Special Truck

Example: A Bank

Example: An Information System
The three kinds of simulation objects, consumable, nonconsumable, and renewable, coordinate access to quantifiable static resources. Coordination is also needed in order to synchronize the tasks of two or more simulation objects. For example, a car washer only carries out its tasks when a vehicle appears in the car wash; a bank teller gives service to a customer when the customer appears in the bank.

The mechanism for providing synchronization of tasks among two or more SimulationObjects is supported by class ResourceCoordinator. Class ResourceCoordinator is a concrete subclass of class Resource; class Resource was defined in Chapter 24. The purpose of this chapter is to describe the implementation of ResourceCoordinator and to give several examples using this synchronization technique.

## The Implementation of Class Resource-Coordinator

A ResourceCoordinator represents a SimulationObject whose tasks must be synchronized with the tasks of another SimulationObject. One of the objects is considered the resource or the "customer"; the other object acquires this resource in order to give it service and can, therefore, be thought of as a "server" or clerk. At any given time, customers may be waiting for a server or servers may be waiting for customers, or no one may be waiting. Only one queue has to be maintained; a variable of a ResourceCoordinator keeps track of whether that queue contains customers, servers, or is empty. The variable pending, inherited from the superclass Resource, refers to the queue; the variable wholsWaiting refers to the status of the queue.

Three inquiries can be made of a ResourceCoordinator, are there customers waiting? (customersWaiting), are there servers waiting? (serversWaiting), and how many are waiting? (queueLength). The message acquire comes from a SimulationObject acting as a server who wants to acquire a customer to serve. If a customer is waiting, then the SimulationObject can give it service (giveService); otherwise, the SimulationObject is added to the queue which is set to be a queue of servers waiting. The message producedBy: aCustomer comes from a SimulationObject acting as a customer who wants to be served. If a server is waiting, then the SimulationObject can get service (getServiceFor: aCustomerRequest); otherwise, the SimulationObject is added to the queue which is set to be a queue of customers waiting.

In all cases, the queue consists of instances of DelayedEvent. If the queue consists of customers, then the DelayedEvent condition is the SimulationObject waiting to get service. If the queue consists of servers, then the DelayedEvent condition is nil until a customer is acquired, at which point the condition is set to be the customer request (itself a
DelayedEvent that was stored when the customer request was first made). When the DelayedEvent is resumed, the condition is returned to the requestor; in this way, a server gains access to a customer request. Once the synchronized tasks are completed, the server can resume the customer's activities by resuming the request.

<table><tr><td>class name</td><td>ResourceCoordinator</td></tr><tr><td>superclass</td><td>Resource</td></tr><tr><td>instance variable names</td><td>wholsWaiting</td></tr><tr><td>instance methods</td><td></td></tr></table>

### accessing

**customersWaiting**

`↑wholsWaiting == #customer`

**serversWaiting**

`↑wholsWaiting == #server`

**queueLength**

`↑pending size`

### task language

**acquire**

```text
| anEvent |
self customersWaiting ifTrue: [↑self giveService].
anEvent ← DelayedEvent new.
wholsWaiting ← #server.
self addRequest: anEvent.

"At this point, the condition of anEvent has been set to the customer request.".
↑anEvent condition
```

**producedBy: aCustomer**

```text
| anEvent |
anEvent ← DelayedEvent onCondition: aCustomer.
self serversWaiting ifTrue: [↑selfFor: anEvent].
wholsWaiting ← #customer.
self addRequest: anEvent
```

### private

**getServiceFor: aCustomerRequest**

```text
| aServerRequest |
aServerRequest ← pending removeFirst.
pending empty ifTrue: [wholsWaiting ← #none].
aServerRequest condition: aCustomerRequest.
aServerRequest resume.
ActiveSimulation stopProcess.
aCustomerRequest pause.
ActiveSimulation startProcess
```
**giveService**

| aCustomerRequest |
|-------------------|
| aCustomerRequest ← pending removeFirst. |
| pending.isEmpty ifTrue: [wholsWaiting ← #none]. |
| ↑aCustomerRequest |

**setName: aString**

super
super Name: aString
wholsWaiting ← #none

Notice that when a server gives service to a customer, the customer re-
quest is suspended (pause) in which case the simulation process refer-
ence count must be decremented until the service task is resumed.

**Example:**
**A Car Wash**
**Simulation**

The example of a CarWash simulation consists of cars that arrive and ask to be washed or washed and waxed. Washers are available to do the washing and waxing; when there are no cars to service, the Washers are idle. The definition of the simulation CarWash follows. There is one resource coordinator for the various car customers. Cars arrive for washing about one every 20 minutes; cars arrive for washing and waxing about one every 30 minutes. The Washer arrives when the CarWash first starts and stays as long as the simulation proceeds.

<table>
   <tr>
    <td>
     class name
    </td>
    <td>
     CarWash
    </td>
   </tr>
   <tr>
    <td>
     superclass
    </td>
    <td>
     Simulation
    </td>
   </tr>
   <tr>
    <td colspan="2">
     instance methods
    </td>
   </tr>
   <tr>
    <td colspan="2">
     initialization
    </td>
   </tr>
  </table>

defineArrivalSchedule

self scheduleArrivalOf: Wash
accordingTo: (Exponential mean: 20).
self scheduleArrivalOf: WashAndWax
accordingTo: (Exponential mean: 30).
self scheduleArrivalOf: Washer new at: 0.0

defineResources

self coordinate: 'CarCustomer'

Each kind of car customer can report the service it requires. The Wash-
er tasks depend on the kind of service each car customer wants. First a
customer is obtained. Then it is given service (wash, wax, or both) and
then the customer's own activities are continued.

<table>
   <tr>
    <td>
     class name
    </td>
    <td>
     Washer
    </td>
   </tr>
   <tr>
    <td>
     superclass
    </td>
    <td>
     SimulationObject
    </td>
   </tr>
  </table>
instance methods

simulation control

## tasks

| carRequest |

[true] while True:

[carRequest ← self acquireResource: 'CarCustomer'.

(carRequest condition wants: 'wash')

if True: [self holdFor: (Uniform from: 12.0 to: 26.0) next].

(carRequest condition wants: 'wax')

if True: [self holdFor: (Uniform from: 8.0 to: 12.0) next].

self resume: carRequest]

The vehicles Wash and WashAndWax are defined next. Each contains an attribute which defines the kinds of service they require. The tasks of these vehicles are simply to ask for service and, after getting the service, to leave.

<table><tr><td>class name</td><td>Wash</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance variable names</td><td>service</td></tr><tr><td>instance methods</td><td></td></tr></table>

accessing

## wants: aService

aService includes: aService

simulation control

### initialize

super initialize.

service ← #('wash')

## tasks

self produceResource: 'CarCustomer'

<table><tr><td>class name</td><td>WashAndWax</td></tr><tr><td>superclass</td><td>Wash</td></tr><tr><td>instance methods</td><td></td></tr></table>

simulation control

### initialize

super initialize.

service ← #('wash', 'wax')

WashAndWax is defined as a subclass of Wash since the only difference between the two is setting the service attributes. The following trace was produced by making Wash a subclass of EventMonitor.

0 Wash 1 enters

0 Wash 1 wants to get service as CarCustomer
<table><tr><td>0</td><td>WashAndWax 1 enters</td></tr><tr><td>0</td><td>WashAndWax 1 wants to get service as CarCustomer</td></tr><tr><td>0</td><td>Washer 1 enters</td></tr><tr><td>0</td><td>Washer 1 wants to serve for CarCustomer</td></tr><tr><td>0</td><td>Washer 1 can serve Wash 1</td></tr><tr><td>0</td><td>Washer 1 holds for 14.2509</td></tr><tr><td>7.95236</td><td>WashAndWax 2 enters</td></tr><tr><td>7.95236</td><td>WashAndWax 2 wants to get service as CarCustomer</td></tr><tr><td>8.42388</td><td>Wash 2 enters</td></tr><tr><td>8.42388</td><td>Wash 2 wants to get service as CarCustomer</td></tr><tr><td>12.9404</td><td>Wash 3 enters</td></tr><tr><td>12.9404</td><td>Wash 3 wants to get service as CarCustomer</td></tr><tr><td>14.2509</td><td>Washer 1 resumes Wash 1</td></tr><tr><td>14.2509</td><td>Washer 1 wants to serve for CarCustomer</td></tr><tr><td>14.2509</td><td>Washer 1 can serve WashAndWax 1</td></tr><tr><td>14.2509</td><td>Washer 1 holds for 25.502 (wash part)</td></tr><tr><td>14.2509</td><td>Wash 1 exits</td></tr><tr><td>26.6023</td><td>WashAndWax 3 enters</td></tr><tr><td>26.6023</td><td>WashAndWax 3 wants to get service as CarCustomer</td></tr><tr><td>26.8851</td><td>Wash 4 enters</td></tr><tr><td>26.8851</td><td>Wash 4 wants to get service as CarCustomer</td></tr><tr><td>29.5632</td><td>Wash 5 enters</td></tr><tr><td>29.5632</td><td>Wash 5 wants to get service as CarCustomer</td></tr><tr><td>32.1979</td><td>Wash 6 enters</td></tr><tr><td>32.1979</td><td>Wash 6 wants to get service as CarCustomer</td></tr><tr><td>38.7616</td><td>Wash 7 enters</td></tr><tr><td>38.7616</td><td>Wash 7 wants to get service as CarCustomer</td></tr><tr><td>39.753</td><td>Washer 1 holds for 9.21527 (wax part)</td></tr><tr><td>43.5843</td><td>Wash 8 enters</td></tr><tr><td>43.5843</td><td>Wash 8 wants to get service as CarCustomer</td></tr><tr><td>48.9683</td><td>Washer 1 resumes WashAndWax 1</td></tr><tr><td>48.9683</td><td>Washer 1 wants to serve for CarCustomer</td></tr><tr><td>48.9683</td><td>Washer 1 can serve WashAndWax 2</td></tr><tr><td>48.9683</td><td>Washer 1 holds for 14.2757 (wash part)</td></tr><tr><td>48.9683</td><td>WashAndWax 1 exits</td></tr><tr><td>51.8478</td><td>WashAndWax 4 enters</td></tr><tr><td>51.8478</td><td>WashAndWax 4 wants to get service as CarCustomer</td></tr><tr><td>63.244</td><td>Washer 1 holds for 11.7717 (wax part)</td></tr><tr><td>68.9328</td><td>Wash 9 enters</td></tr><tr><td>68.9328</td><td>Wash 9 wants to get service as CarCustomer</td></tr><tr><td>70.6705</td><td>WashAndWax 5 enters</td></tr><tr><td>70.6705</td><td>WashAndWax 5 wants to get service as CarCustomer</td></tr><tr><td>75.0157</td><td>Washer 1 resumes WashAndWax 2</td></tr><tr><td>75.0157</td><td>Washer 1 wants to serve for CarCustomer</td></tr><tr><td>75.0157</td><td>Washer 1 can serve Wash 2</td></tr><tr><td>75.0157</td><td>Washer 1 holds for 18.6168</td></tr></table>
<table><tr><td>75.0157</td><td>WashAndWax 2 exits</td></tr><tr><td>78.0228</td><td>Wash 10 enters</td></tr><tr><td>78.0228</td><td>Wash 10 wants to get service as CarCustomer</td></tr><tr><td>78.2874</td><td>WashAndWax 6 enters</td></tr><tr><td>78.2874</td><td>WashAndWax 6 wants to get service as CarCustomer</td></tr></table>

At 78.2874, there are 12 customers waiting---8 are Wash and 4 are WashAndWax; 2 Wash and 2 WashAndWax have been served.

From this trace one can see that more Washers are needed to service the demand in this CarWash. It is also possible to collect specific data on the amount of time customers wait (using the duration statistics gathering technique and throughput histogram from the previous chapter) and the percentage of time a worker is busy or idle.

## Example: A Ferry Service for a Special Truck

The last example in Chapter 24 was of a ferry service in which a ferry crosses between an island and the mainland carrying cars. The cars were modeled as static resources that a ferry could acquire. The ferry's task was to load as many as six cars, cross over the water, unload the cars it carried, and repeat the process. The example was like one provided in the book on Demos by Graham Birtwistle. In that book, Birtwistle describes the ferry service as coordinating the ferry service with the travels of a truck. A truck goes from the mainland to the island in order to make deliveries, returns to the mainland to get more supplies, and then goes to the island again, etc. The ferry only crosses from one side to the other if it is carrying the truck. This version of the ferry simulation requires a coordination of SimulationObjects representing the ferry and the truck; each has its own tasks to do, but the truck can not do its tasks without the assistance of the ferry and the ferry has no tasks to do in the absence of a truck to carry.

Ferry service starts at 7:00 a.m. (420.0 minutes into the day) and ends at 7:00 p.m. (1140 minutes into the day).

<table><tr><td>class name</td><td>FerrySimulation</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>initialization</td><td></td></tr></table>

### defineArrivalSchedule

self scheduleArrivalOf: Truck new at: 420.0.

self scheduleArrivalOf: Ferry new at: 420.0.

### defineResources

self coordinate: 'TruckCrossing'
The Truck and the Ferry are defined in terms of producing and acquiring the resource 'TruckCrossing'.

<table><tr><td>class name</td><td>Ferry</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance methods</td><td></td></tr></table>

simulation control

**tasks**

| truckRequest |
[ActiveSimulation time > 1140.0] whileFalse:
    [truckRequest ← self acquireResource: 'TruckCrossing'.
    self load.
    self crossOver.
    self unload.
    self resume: truckRequest]

**load**

self holdFor: 5.0

**unload**

self holdFor: 3.0

**crossOver**

self holdFor: (Normal mean: 8 deviation: 0.5) next

The Truck delivers supplies on the island and picks up supplies on the mainland.

<table><tr><td>class name</td><td>Truck</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance methods</td><td></td></tr></table>

simulation control

**tasks**

[true]
whileTrue:
    [self produceResource: 'TruckCrossing'.
    self deliverSupplies.
    self produceResource: 'TruckCrossing'.
    self pickUpSupplies]

**deliverSupplies**

self holdFor: (Uniform from: 15 to: 30) next

**pickUpSupplies**

self holdFor: (Uniform from: 30 to: 45) next

There is no check in the definition of Truck or Ferry for a particular side, mainland or island, because we assume that both simulations objects start on the same side (the mainland) and their synchronization for crossing over guarantees that they stay on the same side. A trace of the events for running FerrySimulation is
Example: Ferry Service for a Special Truck

<table><tbody><tr><td></td><td>Start at the mainland</td></tr><tr><td>420.0</td><td>Ferry enters</td></tr><tr><td>420.0</td><td>Ferry wants to serve for TruckCrossing</td></tr><tr><td>420.0</td><td>Truck enters</td></tr><tr><td>420.0</td><td>Truck wants to get service as TruckCrossing</td></tr><tr><td>420.0</td><td>Ferry can serve Truck</td></tr><tr><td>420.0</td><td>Ferry load truck</td></tr><tr><td>420.0</td><td>Ferry holds for 5.0</td></tr><tr><td>425.0</td><td>Ferry cross over</td></tr><tr><td>425.0</td><td>Ferry holds for 7.84272</td></tr><tr><td></td><td>unload the truck at the island side</td></tr><tr><td>432.843</td><td>Ferry unload truck</td></tr><tr><td>432.843</td><td>Ferry holds for 3.0</td></tr><tr><td>435.843</td><td>Ferry resumes Truck</td></tr><tr><td>435.843</td><td>Ferry wants to serve for TruckCrossing</td></tr><tr><td>435.843</td><td>Truck deliver supplies</td></tr><tr><td>435.843</td><td>Truck holds for 21.1949</td></tr><tr><td>457.038</td><td>Truck wants to get service as TruckCrossing</td></tr><tr><td>457.038</td><td>Ferry can serve Truck</td></tr><tr><td>457.038</td><td>Ferry load truck</td></tr><tr><td>457.038</td><td>Ferry holds for 5.0</td></tr><tr><td></td><td>cross over back to the mainland</td></tr><tr><td>462.038</td><td>Ferry cross over</td></tr><tr><td>462.038</td><td>Ferry holds for 8.28948</td></tr><tr><td>470.327</td><td>Ferry unload truck</td></tr><tr><td>470.327</td><td>Ferry holds for 3.0</td></tr><tr><td>473.327</td><td>Ferry resumes Truck</td></tr><tr><td>473.327</td><td>Ferry wants to serve for TruckCrossing</td></tr><tr><td>473.327</td><td>Truck pick up supplies</td></tr><tr><td>473.327</td><td>Truck holds for 40.0344</td></tr><tr><td>513.361</td><td>Truck wants to get service as TruckCrossing</td></tr><tr><td>513.361</td><td>Ferry can serve Truck</td></tr><tr><td>513.361</td><td>Ferry load truck</td></tr><tr><td>513.361</td><td>Ferry holds for 5.0</td></tr><tr><td></td><td>back to the island</td></tr><tr><td>518.361</td><td>Ferry cross over</td></tr><tr><td>518.361</td><td>Ferry holds for 8.05166</td></tr><tr><td>526.413</td><td>Ferry unload truck</td></tr><tr><td>526.413</td><td>Ferry holds for 3.0</td></tr><tr><td>529.413</td><td>Ferry resumes Truck</td></tr><tr><td>529.413</td><td>Ferry wants to serve for TruckCrossing</td></tr><tr><td>529.413</td><td>Truck delivers supplies</td></tr><tr><td>529.413</td><td>Truck holds for 27.1916</td></tr><tr><td>556.605</td><td>Truck wants to get service as TruckCrossing</td></tr><tr><td>556.605</td><td>Ferry can serve Truck</td></tr><tr><td>556.605</td><td>Ferry load truck</td></tr></tbody></table>
<table><tr><td>556.605</td><td>Ferry holds for 5.0</td><td>back to mainland, etc.</td></tr><tr><td>561.605</td><td>Ferry cross over</td><td></td></tr><tr><td>561.605</td><td>Ferry holds for 7.53188</td><td></td></tr><tr><td>569.137</td><td>Ferry unload truck</td><td></td></tr><tr><td>569.137</td><td>Ferry holds for 3.0</td><td></td></tr><tr><td>572.136</td><td>Ferry resumes Truck</td><td></td></tr><tr><td>572.136</td><td>Ferry wants to serve for TruckCrossing</td><td></td></tr><tr><td>572.136</td><td>Truck pick up supplies</td><td></td></tr><tr><td>572.136</td><td>Truck holds for 36.8832</td><td></td></tr></table>

The ferry tasks do not guarantee that the resting place for the evening is the mainland side. This can be done by monitoring which side the ferry is on and then stopping only after returning to the mainland. Only the definition of Ferry must change since the Truck side is synchronized with it.

<table><tr><td>class name</td><td>Ferry</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance variable names</td><td>currentSide</td></tr><tr><td>instance methods</td><td></td></tr></table>

### simulation control

#### initialize

super initialize.
`currentSide` ← 'Mainland'

#### tasks

| truckRequest finished |
finished ← false
[finished] while False:
    [truckRequest ← self acquireResource: 'TruckCrossing'.
        self load.
        self crossOver.
        self unload.
        self resume: truckRequest.
    finished ←
    ActiveSimulation time > 1140.0 and: [currentSide = 'Mainland']]

#### load

self holdFor: 5.0

#### unload

self holdFor: 3.0

#### crossOver

self holdFor: (Normal mean: 8 deviation: 0.5) next.
`currentSide` ←
    `currentSide` = 'Mainland'
    if True: ['Island']
    if False: ['Mainland']
Suppose now that cars can arrive at the ferry ramp in order to be carried across. The ferry can carry as many as 4 cars in addition to the truck, but the ferry will not cross over unless there is a truck to carry. Then the definition of the simulation changes by the addition of cars arriving at the mainland or the island; we introduce cars in the same way we did in Chapter 24—as static resources.

<table><tr><td>class name</td><td>FerrySimulation</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>initialization</td><td></td></tr></table>

**defineArrivalSchedule**

self scheduleArrivalOf: Truck new at: 420.0.
self scheduleArrivalOf: Ferry new at: 420.0.
self scheduleArrivalOf: MainlandArrival
accordingTo: (Exponential parameter: 0.15)
startingAt: 420.0.
self scheduleArrivalOf: IslandArrival
accordingTo: (Exponential parameter: 0.15)
startingAt: 420.0

**defineResources**

self coordinate: 'TruckCrossing'.
self produce: 3 ofResource: 'Mainland'.
self produce: 0 ofResource: 'Island'

The definitions for MainlandArrival and IslandArrival are the same as those given in Chapter 24.

<table><tr><td>class name</td><td>MainlandArrival</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>simulation control</td><td></td></tr></table>

**tasks**

self produce: 1 ofResource: 'Mainland'

<table><tr><td>class name</td><td>IslandArrival</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>simulation control</td><td></td></tr></table>

**tasks**

self produce: 1 ofResource: 'Island'

The Ferry now must take into consideration loading and unloading any cars waiting at the ramp of the current side.
<table><tr><td>class name</td><td>Ferry</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance variable names</td><td>currentSide<br/>carsOnBoard</td></tr></table>

instance methods

simulation control

**initialize**

super initialize.
`currentSide` ← 'Mainland'.
`carsOnBoard` ← 0.

**tasks**

| truckRequest finished |
finished ← false.
[finished] whileFalse:
    [truckRequest ← self acquireResource: 'TruckCrossing'.
self load.
self crossOver.
self unload.
self resume: truckRequest.
finished ←
    ActiveSimulation time > 1140.0 and: [currentSide = 'Mainland']}

**load**

"load the truck first"
self holdFor: 5.0
"now load any cars that are waiting on the current side"
[carsOnBoard < 4
    and: [self inquireFor: 1 ofResource: currentSide]]
    whileTrue:
        [self acquire: 1 ofResource: currentSide.
self holdFor: 0.5.
carsOnBoard ← carsOnBoard + 1]

**unload**

"unload the cars and the truck"
self holdFor: (carsOnBoard * 0.5) + 3.0

**crossOver**

self holdFor: (Normal mean: 8 deviation: 0.5) next.
`currentSide` ←
    `currentSide` = 'Mainland'
    ifTrue: ['Island']
    ifFalse: ['Mainland']

## Example: A Bank

A bank teller only carries out tasks when a customer appears at the teller's window and asks for service. Since the teller's services are de-
pendent on the needs of the customer, the specification of the teller's tasks includes requests for information from the customer.

Suppose the bank assigns two bank tellers to work all day. The bank opens at 9:00 a.m. and closes at 3:00 p.m. Throughout the day, customers arrive every 10 minutes with a standard deviation of 5 minutes. At the noon lunch hour, the number of customers increases dramatically, averaging one every three minutes. Two additional bank tellers are added to handle the increased demand for service. When a regular bank teller is not serving a customer, the teller has desk work to do.

The arrival of customers and regular workers into the bank is scheduled in the response to the message `defineArrivalSchedule` to `BankSimulation`. The lunchtime increase is represented by a discrete probability distribution that is a sample space of twenty 3's, representing a total of the 60 minutes during which lunchtime customers appear. Mixed with the normal load of customers, this means that 20 or more customers appear in that busiest hour.

We define simulation objects `BankTeller`, `LunchtimeTeller`, `BankCustomer`, as well as the `BankSimulation`.

<table><tr><td>class name</td><td>BankSimulation</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>class variable names</td><td>Hour</td></tr><tr><td>instance methods</td><td></td></tr></table>

initialization

defineArrivalSchedule

self scheduleArrivalOf: BankCustomer
accordingTo: (Normal mean: 10 deviation: 5)
startingAt: 9*Hour.

self scheduleArrivalOf: (BankTeller name: 'first') at: 9*Hour

self scheduleArrivalOf: (BankTeller name: 'second') at: 9*Hour.

self scheduleArrivalOf: BankCustomer
accordingTo:
(SampleSpaceWithoutReplacement
data: ((1 to: 20) collect: [ :i | 3]))
startingAt: 12*Hour.

self schedule: [self hireMoreTellers] at: 12*Hour.

self schedule: [self finishUp] at: 15*Hour.

defineResources

self coordinate: 'TellerCustomer'

simulation control

hireMoreTellers

self schedule: [(LunchtimeTeller name: 'first') startUp] after: 0.0.

self schedule: [(LunchtimeTeller name: 'second') startUp] after: 0.0
The ResourceCoordinator is responsible for matching customers (takers of service) with bank tellers (givers of service). The bank customer's task is simple. After entering the bank, the customer gets the attention of a bank teller and asks for service. After obtaining service, the customer leaves. The amount of time the customer spends in the bank depends on how long the customer must wait for a teller and how long the teller takes giving service.

<table><tr><td>class name</td><td>BankCustomer</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>simulation control</td><td></td></tr></table>

### tasks

self.produceResource: 'TellerCustomer'

The bank teller's tasks depend on the needs of the customer. To keep this example simple, we will assume that a BankTeller does about the same work for each customer, taking between 2 and 15 minutes. Another alternative would be to give each BankCustomer a list of desired services as was done in the car wash example; the BankTeller would enumerate over the set, taking times appropriate to each kind of service. Whenever a customer is not available, the teller does other tasks. These tasks are small and take a short amount of time; however, the teller can not be interrupted. When one of these background desk tasks is completed, the teller checks to see if a customer has arrived and is waiting for service.

<table><tr><td>class name</td><td>BankTeller</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>simulation control</td><td></td></tr></table>

### tasks

| customerRequest |
[true] while True:
  [(self numberOfProvidersOfResource: 'TellerCustomer') > 0
    if True: [self counterWork]
    if False: [self deskWork]]

### counterWork

| customerRequest |
customerRequest ← self.acquireResource: 'TellerCustomer'.
self.holdFor: (Uniform from: 2 to: 15) next.
self resume: customerRequest

### deskWork

self.holdFor: (Uniform from: 1 to: 5) next

A LunchtimeTeller has to schedule itself to leave the bank after an hour.
This scheduling can be specified in the response to initialize. When it is time to leave, the LunchtimeTeller has to make certain that all its tasks are completed before leaving. Therefore, a signal (getDone) is set to true the first time the message finishUp is sent; this signal is checked each time the teller's counter work completes. The second time finishUp is sent, the signal is true and the teller can exit. The LunchtimeTeller, unlike the regular BankTeller, does not do any desk work when customers are not available.

<table><tr><td>class name</td><td>LunchtimeTeller</td></tr><tr><td>superclass</td><td>BankTeller</td></tr><tr><td>instance variable names</td><td>getDone</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>initialization</td><td></td></tr></table>

**initialize**

super initialize.
getDone ← false.

ActiveSimulation schedule: [self finishUp] after: 60

simulation control

**finishUp**

getDone

ifTrue: [super finishUp]

ifFalse: [getDone ← true]

**tasks**

[getDone] whileFalse: [self counterWork].

self finishUp

A partial trace of the events follows.

<table><tr><td>540</td><td>BankCustomer 1 enters</td></tr><tr><td>540</td><td>BankCustomer 1 wants to get service as TellerCustomer</td></tr><tr><td>540</td><td>BankTeller first enters</td></tr><tr><td>540</td><td>BankTeller first wants to serve for TellerCustomer</td></tr><tr><td>540</td><td>BankTeller first can serve BankCustomer 1</td></tr><tr><td>540</td><td>BankTeller first holds for 9.33214</td></tr><tr><td>540</td><td>BankTeller second enters</td></tr><tr><td>540</td><td>BankTeller second does desk work</td></tr><tr><td>540</td><td>BankTeller second holds for 3.33594</td></tr><tr><td>543.336</td><td>BankTeller second does desk work</td></tr><tr><td>543.336</td><td>BankTeller second holds for 2.96246</td></tr><tr><td>546.298</td><td>BankTeller second does desk work</td></tr><tr><td>546.298</td><td>BankTeller second holds for 3.56238</td></tr><tr><td>549.332</td><td>BankTeller first resumes BankCustomer 1</td></tr><tr><td>549.332</td><td>BankTeller first does desk work</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>549.332</td>
      <td>BankTeller first holds for 1.83978</td>
    </tr>
    <tr>
      <td>549.332</td>
      <td>BankCustomer 1 exits</td>
    </tr>
    <tr>
      <td>549.819</td>
      <td>BankCustomer 2 enters</td>
    </tr>
    <tr>
      <td>549.819</td>
      <td>BankCustomer 2 wants to get service as TellerCustomer</td>
    </tr>
    <tr>
      <td>549.861</td>
      <td>BankTeller second wants to serve for TellerCustomer</td>
    </tr>
    <tr>
      <td>549.861</td>
      <td>BankTeller second can serve BankCustomer 2</td>
    </tr>
    <tr>
      <td>549.861</td>
      <td>BankTeller second holds for 14.3192</td>
    </tr>
    <tr>
      <td>551.172</td>
      <td>BankTeller first does desk work</td>
    </tr>
    <tr>
      <td>551.172</td>
      <td>BankTeller first holds for 4.16901</td>
    </tr>
    <tr>
      <td>555.341</td>
      <td>BankTeller first does desk work</td>
    </tr>
    <tr>
      <td>555.341</td>
      <td>BankTeller first holds for 2.60681</td>
    </tr>
    <tr>
      <td>557.948</td>
      <td>BankTeller first does desk work</td>
    </tr>
    <tr>
      <td>557.948</td>
      <td>BankTeller first holds for 4.58929</td>
    </tr>
    <tr>
      <td>559.063</td>
      <td>BankCustomer 3 enters</td>
    </tr>
    <tr>
      <td>559.063</td>
      <td>BankCustomer 3 wants to get service as TellerCustomer</td>
    </tr>
    <tr>
      <td>562.537</td>
      <td>BankTeller first wants to serve for TellerCustomer</td>
    </tr>
    <tr>
      <td>562.537</td>
      <td>BankTeller first can serve BankCustomer 3</td>
    </tr>
    <tr>
      <td>562.537</td>
      <td>BankTeller first holds for 13.4452</td>
    </tr>
    <tr>
      <td>564.18</td>
      <td>BankTeller second resumes BankCustomer 2</td>
    </tr>
    <tr>
      <td>564.18</td>
      <td>BankTeller second does desk work</td>
    </tr>
    <tr>
      <td>564.18</td>
      <td>BankTeller second holds for 2.63007</td>
    </tr>
    <tr>
      <td>564.18</td>
      <td>BankCustomer 2 exits</td>
    </tr>
    <tr>
      <td>565.721</td>
      <td>BankCustomer 4 enters</td>
    </tr>
    <tr>
      <td>565.721</td>
      <td>BankCustomer 4 wants to get service as TellerCustomer</td>
    </tr>
    <tr>
      <td>566.81</td>
      <td>BankTeller second wants to serve for TellerCustomer</td>
    </tr>
    <tr>
      <td>566.81</td>
      <td>BankTeller second can serve BankCustomer 4</td>
    </tr>
    <tr>
      <td>566.81</td>
      <td>BankTeller second holds for 5.08139</td>
    </tr>
    <tr>
      <td>571.891</td>
      <td>BankTeller second resumes BankCustomer 4</td>
    </tr>
    <tr>
      <td>571.891</td>
      <td>BankTeller second does desk work</td>
    </tr>
    <tr>
      <td>571.891</td>
      <td>BankTeller second holds for 4.69818</td>
    </tr>
    <tr>
      <td>571.891</td>
      <td>BankCustomer 4 exits</td>
    </tr>
    <tr>
      <td>575.982</td>
      <td>BankTeller first resumes BankCustomer 3</td>
    </tr>
    <tr>
      <td>575.982</td>
      <td>BankTeller first does desk work</td>
    </tr>
    <tr>
      <td>575.982</td>
      <td>BankTeller first holds for 2.10718</td>
    </tr>
    <tr>
      <td>575.982</td>
      <td>BankCustomer 3 exits</td>
    </tr>
    <tr>
      <td>576.59</td>
      <td>BankTeller second does desk work</td>
    </tr>
    <tr>
      <td>576.59</td>
      <td>BankTeller second holds for 4.04327</td>
    </tr>
  </tbody>
</table>

... and so on until lunch hour when the extra help arrives;
at this point, 18 customers have entered; BankTeller first is
giving BankCustomer 18 service...
<table>
  <tbody>
    <tr>
      <td>720</td>
      <td>BankCustomer 19 enters</td>
    </tr>
    <tr>
      <td>720</td>
      <td>BankCustomer 19 wants to get service as TellerCustomer</td>
    </tr>
    <tr>
      <td>720</td>
      <td>LunchtimeTeller first enters</td>
    </tr>
    <tr>
      <td>720</td>
      <td>LunchtimeTeller first wants to serve for TellerCustomer</td>
    </tr>
    <tr>
      <td>720</td>
      <td>LunchtimeTeller first can serve BankCustomer 19</td>
    </tr>
    <tr>
      <td>720</td>
      <td>LunchtimeTeller first holds for 11.9505</td>
    </tr>
    <tr>
      <td>720</td>
      <td>LunchtimeTeller second enters</td>
    </tr>
    <tr>
      <td>720</td>
      <td>LunchtimeTeller second wants to serve for TellerCustomer</td>
    </tr>
    <tr>
      <td>721.109</td>
      <td>BankTeller second does desk work</td>
    </tr>
    <tr>
      <td>721.109</td>
      <td>BankTeller second holds for 2.09082</td>
    </tr>
    <tr>
      <td>721.663</td>
      <td>BankTeller first resumes BankCustomer 18</td>
    </tr>
    <tr>
      <td>721.663</td>
      <td>BankTeller first does desk work</td>
    </tr>
    <tr>
      <td>721.663</td>
      <td>BankTeller first holds for 3.43219</td>
    </tr>
    <tr>
      <td>721.663</td>
      <td>BankCustomer 18 exits</td>
    </tr>
    <tr>
      <td>722.085</td>
      <td>BankCustomer 20 enters</td>
    </tr>
    <tr>
      <td>722.085</td>
      <td>BankCustomer 20 wants to get service as TellerCustomer</td>
    </tr>
    <tr>
      <td>722.085</td>
      <td>LunchtimeTeller second can serve BankCustomer 20</td>
    </tr>
    <tr>
      <td>722.085</td>
      <td>LunchtimeTeller second holds for 9.51483</td>
    </tr>
    <tr>
      <td>723</td>
      <td>BankCustomer 21 enters</td>
    </tr>
    <tr>
      <td>723</td>
      <td>BankCustomer 21 wants to get service as TellerCustomer</td>
    </tr>
    <tr>
      <td>723.2</td>
      <td>BankTeller second wants to serve for TellerCustomer</td>
    </tr>
    <tr>
      <td>723.2</td>
      <td>BankTeller second can serve BankCustomer 21</td>
    </tr>
    <tr>
      <td>723.2</td>
      <td>BankTeller second holds for 9.66043</td>
    </tr>
    <tr>
      <td>725.095</td>
      <td>BankTeller first does desk work</td>
    </tr>
    <tr>
      <td>725.095</td>
      <td>BankTeller first holds for 4.97528</td>
    </tr>
    <tr>
      <td>726</td>
      <td>BankCustomer 22 enters</td>
    </tr>
    <tr>
      <td>726</td>
      <td>BankCustomer 22 wants to get service as TellerCustomer</td>
    </tr>
    <tr>
      <td>729</td>
      <td>BankCustomer 23 enters</td>
    </tr>
    <tr>
      <td>729</td>
      <td>BankCustomer 23 wants to get service as TellerCustomer</td>
    </tr>
    <tr>
      <td>730.071</td>
      <td>BankTeller first wants to serve for TellerCustomer</td>
    </tr>
    <tr>
      <td>730.071</td>
      <td>BankTeller first can serve BankCustomer 22</td>
    </tr>
    <tr>
      <td>730.071</td>
      <td>BankTeller first holds for 8.17746</td>
    </tr>
    <tr>
      <td>731.6</td>
      <td>LunchtimeTeller second resumes BankCustomer 20</td>
    </tr>
    <tr>
      <td>731.6</td>
      <td>LunchtimeTeller second wants to serve for TellerCustomer</td>
    </tr>
    <tr>
      <td>731.6</td>
      <td>LunchtimeTeller second can serve BankCustomer 23</td>
    </tr>
    <tr>
      <td>731.6</td>
      <td>LunchtimeTeller second holds for 6.27971</td>
    </tr>
    <tr>
      <td>731.6</td>
      <td>BankCustomer 20 exits</td>
    </tr>
  </tbody>
</table>
<table><tr><td>731.95</td><td>LunchtimeTeller first resumes BankCustomer 19</td></tr><tr><td>731.95</td><td>LunchtimeTeller first wants to serve for TellerCustomer</td></tr><tr><td>731.95</td><td>BankCustomer 19 exits</td></tr><tr><td>732</td><td>BankCustomer 24 enters</td></tr><tr><td>732</td><td>BankCustomer 24 wants to get service as TellerCustomer</td></tr><tr><td>732</td><td>LunchtimeTeller first can serve BankCustomer 24</td></tr><tr><td>732</td><td>LunchtimeTeller first holds for 9.52138</td></tr></table>

... BankCustomer 40 just left and lunch time is over; there are 3 other customers in the bank; as soon as they finish with their current customers, the LunchtimeTellers will leave...

<table><tr><td>780.0</td><td>BankCustomer 44 enters</td></tr><tr><td>780.0</td><td>BankCustomer 44 wants to get service as TellerCustomer</td></tr><tr><td>780.918</td><td>BankTeller first wants to serve for TellerCustomer</td></tr><tr><td>780.918</td><td>BankTeller first can serve BankCustomer 44</td></tr><tr><td>780.918</td><td>BankTeller first holds for 13.1566</td></tr><tr><td>781.968</td><td>BankCustomer 45 enters</td></tr><tr><td>781.968</td><td>BankCustomer 45 wants to get service as TellerCustomer</td></tr><tr><td>784.001</td><td>LunchtimeTeller second resumes BankCustomer 43</td></tr><tr><td>784.001</td><td>LunchtimeTeller second exits</td></tr><tr><td>784.001</td><td>BankCustomer 43 exits</td></tr><tr><td>787.879</td><td>LunchtimeTeller first resumes BankCustomer 42</td></tr><tr><td>787.879</td><td>LunchtimeTeller first exits</td></tr><tr><td>787.879</td><td>BankCustomer 42 exits</td></tr><tr><td>789.189</td><td>BankTeller second resumes BankCustomer 41</td></tr><tr><td>789.189</td><td>BankTeller second wants to serve for TellerCustomer</td></tr><tr><td>789.189</td><td>BankTeller second can serve BankCustomer 45</td></tr><tr><td>789.189</td><td>BankTeller second holds for 2.38364</td></tr><tr><td>789.189</td><td>BankCustomer 41 exits</td></tr><tr><td>791.572</td><td>BankTeller second resumes BankCustomer 45</td></tr><tr><td>791.572</td><td>BankTeller second does desk work</td></tr><tr><td>791.572</td><td>BankTeller second holds for 2.34467</td></tr><tr><td>791.572</td><td>BankCustomer 45 exits</td></tr><tr><td>793.917</td><td>BankTeller second does desk work</td></tr><tr><td>793.917</td><td>BankTeller second holds for 3.19897</td></tr></table>

and so on...

The data that would be collected here includes the busy/idle percentages of the tellers and the customers' average wait time.
## Example: An Information System

Our last example is also in the Birtwistle book and, according to Birtwistle, is a popular example for simulation systems such as GPSS. The example is an information system simulation that describes remote terminals at which users can arrive and make retrieval requests. A customer with a query arrives at one or the other of the terminals and queues, if necessary, to use it. The system scanner rotates from terminal to terminal seeing if a request is waiting and, if so, provides service. Service means that the scanner copies the query to a buffer unit capable of holding three queries simultaneously; if no buffer position is available, the copying process must wait until one becomes available. Once copying to the buffer succeeds, the system processes the query and places the answer in the buffer to return to the terminal without need for the scanner again.

Using the data provided by Birtwistle, we will model a system with six terminals. Customers arrive at terminals with an exponential mean time of 5 minutes. The buffers are modeled as static resources; the terminals are also static resources; while the terminal services are objects whose tasks are coordinated with the tasks of the queries.

<table><tr><td>class name</td><td>InformationSystem</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>initialization</td><td></td></tr></table>

### defineArrivalSchedule

```
"Schedule many queries and only one scanner"
self scheduleArrivalOf: Query
    accordingTo: (Exponential parameter: 5)
    startingAt: 0.0.
self scheduleArrivalOf: SystemScanner new at: 0.0
```

### defineResources

```
self produce: 3 ofResource: 'Buffer'.
0 to: 5 do:
    [ :n |
        self produce: 1 ofResource: 'Terminal', n printString.
        self coordinate: 'TerminalService', n printString]
```

In the above method, we use string concatenation to form the attribute names of six terminals as static resources and six terminal services as coordinated services; the names are `Terminal0`, `...`, `Terminal5` and `TerminalService0`, `...`, `TerminalService5`.

The ResourceCoordinators for terminal service for each of the six terminals are being handled differently here than in the bank and car wash simulation examples. At any time, the queues of customers or
servers will contain only one or no elements. During the simulation, a Query will enter a queue to wait for terminal service. A SystemScanner moves from coordinator to coordinator, round-robin fashion, to act as the giver of service if a Query is waiting.

The customer, a Query, must first access a terminal resource to get a reply. On accessing one of the six terminals, the customer keys in a request and awaits the reply. It takes between 0.3 and 0.5 minutes (uniformly distributed) to enter a query. Then terminal service is requested. The query now waits for the SystemScanner; when the SystemScanner notices the waiting query, it gives it the needed service. This means that the SystemScanner obtains a buffer slot for the query and copies the request into the buffer. It takes 0.0117 minutes to transfer a query to the buffer. Now the reply can be transferred to the terminal and read, the buffer can be freed up, and the terminal released. It takes between 0.05 and 0.10 (uniformly distributed) to process a query, and 0.0397 minutes to transfer the reply back to the terminal. Customers take between 0.6 and 0.8 minutes (uniformly distributed) to read a reply.

<table><tr><td>class name</td><td>Query</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance methods</td><td></td></tr></table>

scheduling

## tasks

| terminalNum | "pick a terminal" | terminalNum ← (SampleSpace data: #('0' '1' '2' '3' '4' '5')) next. | "get a terminal resource" | terminal ← self acquire: 1 of Resource: 'Terminal', terminalNum. | "got the terminal, now enter the query" | self holdFor: (Uniform from: 0.3 to: 0.5) next. | "act as a resource for a terminal service in order to process the query" | self produceResource: 'TerminalService', terminalNum. | "the query is now processed; now read the reply" | self holdFor: (Uniform from: 0.6 to: 0.8) next. | "and release the terminal" | self release: terminal |

The scanner's job is to rotate from terminal to terminal seeing if a request is pending and, if so, to wait to transfer a query into a buffer and then move on. Scanner rotation takes 0.0027 minutes and the same amount of time to test a terminal.

<table><tr><td>class name</td><td>SystemScanner</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance variable names</td><td>n</td></tr></table>
instance methods

simulation control

initialize

super initialize.

n → 5

tasks

| terminalServiceRequest buffer test |

[true]

while True:

[n → (n + 1) \ 6.

self holdFor: 0.0027.

test →

self numberOfProvidersOfResource:

'TerminalService', n printString.

self holdFor: 0.0027.

test = 0 if False:

[terminalServiceRequest →

self acquireResource: ('TerminalService', n printString).

buffer → self acquire: 1 of Resource: 'Buffer'.

"copy the request"

self holdFor: 0.0117.

"process the query"

self holdFor: (Uniform from: 0.05 to: 0.10) next.

"return the reply to the terminal"

self holdFor: 0.0397.

"done, release the resources"

self release: buffer.

self resume: terminalServiceRequest]]

The SystemScanner is not idle when no Query is waiting; it continually
moves from terminal to terminal checking for a Query. This movement
stops when a Query is found in order to provide service. When the ser-
vice is completed, the SystemScanner returns to circulating around,
looking for another Query.

Not much happens at first. The first Query enters but it holds for
0.360428 units of time in order to enter its query at Terminal1; mean-
while the SystemScanner moves around the terminals. A second Query
enters at 0.0472472 and requests Terminal3; a third enters at 0.130608
and requests Terminal4. At 0.360428, the first Query requests service at
Terminal1 which is given a short time later at time 0.367198. Between
this time and time 0.478235, the SystemScanner gives service by get-
ting a Buffer, copying the query to the Buffer, processing it, transfer-
ring the reply, and then releasing the Buffer and resuming the Query.
In the meantime, the second Query requested service, and a fourth Que-
ry entered at Terminal4. The SystemScanner then rotates to Terminal3 to
give service to the second Query waiting there.
Coordinated Resources for Event-Driven Simulations

<table><tr><td>0.0</td><td>Query 1 enters</td></tr><tr><td>0.0</td><td>Query 1 requests 1 of Terminal1</td></tr><tr><td>0.0</td><td>Query 1 obtained 1 of Terminal1</td></tr><tr><td>0.0</td><td>Query 1 holds for 0.360428</td></tr><tr><td>0.0</td><td>SystemScanner enters</td></tr><tr><td>0.0</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.0027</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.0054</td><td>SystemScanner holds for 0.0027</td></tr></table>

...etc...

<table><tr><td>0.0432</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.0459</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.0472472</td><td>Query 2 enters</td></tr><tr><td>0.0472472</td><td>Query 2 requests 1 of Terminal3</td></tr><tr><td>0.0472472</td><td>Query 2 obtained 1 of Terminal3</td></tr><tr><td>0.0472472</td><td>Query 2 holds for 0.363611</td></tr><tr><td>0.0486</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.0513</td><td>SystemScanner holds for 0.0027</td></tr></table>

...etc...

<table><tr><td>0.1269</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.1296</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.130608</td><td>Query 3 enters</td></tr><tr><td>0.130608</td><td>Query 3 requests 1 of Terminal4</td></tr><tr><td>0.130608</td><td>Query 3 obtained 1 of Terminal4</td></tr><tr><td>0.130608</td><td>Query 3 holds for 0.445785</td></tr><tr><td>0.1323</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.135</td><td>SystemScanner holds for 0.0027</td></tr></table>

...etc...

<table><tr><td>0.356398</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.359098</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.360428</td><td>Query 1 wants to get service as TerminalService1</td></tr><tr><td>0.361798</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.364498</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.367198</td><td>SystemScanner wants to give service as TerminalService1</td></tr><tr><td>0.367198</td><td>SystemScanner can serve as TerminalService1</td></tr><tr><td>0.367198</td><td>SystemScanner requests 1 of Buffer</td></tr><tr><td>0.367198</td><td>SystemScanner obtained 1 of Buffer</td></tr><tr><td>0.367198</td><td>SystemScanner holds for 0.0117</td></tr><tr><td>0.378898</td><td>SystemScanner holds for 0.0596374</td></tr></table>
<table><tr><td>0.410858</td><td>Query 2 wants to get service as TerminalService3</td></tr><tr><td>0.41396</td><td>Query 4 enters</td></tr><tr><td>0.41396</td><td>Query 4 requests 1 of Terminal4</td></tr><tr><td>0.438535</td><td>SystemScanner holds for 0.0397</td></tr><tr><td>0.478235</td><td>SystemScanner releases 1 of Buffer</td></tr><tr><td>0.478235</td><td>SystemScanner resumes Query 1</td></tr><tr><td>0.478235</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.478235</td><td>Query 1 got served as TerminalService1</td></tr><tr><td>0.478235</td><td>Query 1 holds for 0.740207</td></tr><tr><td>0.480935</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.483635</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.486335</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.489035</td><td>SystemScanner wants to give service as TerminalService3</td></tr><tr><td>0.489035</td><td>SystemScanner can serve as TerminalService3</td></tr><tr><td>0.489035</td><td>SystemScanner requests 1 of Buffer</td></tr><tr><td>0.489035</td><td>SystemScanner obtained 1 of Buffer</td></tr><tr><td>0.489035</td><td>SystemScanner holds for 0.0117</td></tr><tr><td>0.500735</td><td>SystemScanner holds for 0.0515655</td></tr><tr><td>0.552301</td><td>SystemScanner holds for 0.0397</td></tr><tr><td>0.576394</td><td>Query 3 wants to get service as TerminalService4</td></tr><tr><td>0.592001</td><td>SystemScanner releases 1 of Buffer</td></tr><tr><td>0.592001</td><td>SystemScanner resumes Query 2</td></tr><tr><td>0.592001</td><td>SystemScanner holds for 0.0027</td></tr><tr><td>0.592001</td><td>Query 2 got served as TerminalService3</td></tr><tr><td>0.592001</td><td>Query 2 holds for 0.655313</td></tr></table>

...etc...

For more examples to try, see the Birtwistle book.
<figure><img src="image_270.png" /></figure>
PART FOUR

The previous three parts of the book described the Smalltalk-80 system from the programmer's point of view. The five chapters in this part present the system from the implementer's point of view. Readers who are not interested in how the system is implemented may skip these chapters. Readers interested only in the flavor of the implementation can read Chapter 26 alone. Readers interested in the details of the implementation, including those actually implementing the system, will want to read the following four chapters as well.

<figure><img src="image_271.png" /></figure>
<figure><img src="image_272.png" /></figure>

26

# The Implementation

**The Compiler**

* Compiled Methods

* The Bytecodes

**The Interpreter**

* Contexts

* Block Contexts

* Messages

* Primitive Methods

**The Object Memory**

* The Hardware
Two major components of the Smalltalk-80 system can be distinguished: the *virtual image* and the *virtual machine*.

1. The *virtual image* consists of all of the objects in the system.

2. The *virtual machine* consists of the hardware devices and machine language (or microcode) routines that give dynamics to the objects in the virtual image.

The system implementer's task is to create a virtual machine. A virtual image can then be loaded into the virtual machine and the Smalltalk-80 system becomes the interactive entity described in earlier chapters.

The overview of the Smalltalk-80 implementation given in this chapter is organized in a top-down fashion, starting with the source methods written by programmers. These methods are translated by a *compiler* into sequences of eight-bit instructions called *bytecodes*. The compiler and bytecodes are the subject of this chapter's first section. The bytecodes produced by the compiler are instructions for an *interpreter*, which is described in the second section. Below the interpreter in the implementation is an *object memory* that stores the objects that make up the virtual image. The object memory is described in the third section of this chapter. At the bottom of any implementation is the *hardware*. The fourth and final section of this chapter discusses the hardware required to implement the interpreter and object memory. Chapters 27 - 30 give a detailed specification of the virtual machine's interpreter and object memory.

## The Compiler

Source methods written by programmers are represented in the Smalltalk-80 system as instances of *String*. The *Strings* contain sequences of characters that conform to the syntax introduced in the first part of this book. For example, the following source method might describe how instances of class *Rectangle* respond to the unary message *center*. The *center* message is used to find the Point equidistant from a Rectangle's four sides.

### center

torigin + corner / 2

Source methods are translated by the system's *compiler* into sequences of instructions for a stack-oriented interpreter. The instructions are
eight-bit numbers called *bytecodes*. For example, the bytecodes corresponding to the source method shown above are,

0, 1, 176, 119, 185, 124

Since a bytecode's value gives us little indication of its meaning to the interpreter, this chapter will accompany lists of bytecodes with comments about their functions. Any part of a bytecode's comment that depends on the context of the method in which it appears will be parenthesized. The unparenthesized part of the comment describes its general function. For example, the bytecode `0` always instructs the interpreter to push the value of the receiver's first instance variable on its stack. The fact that the variable is named `origin` depends on the fact that this method is used by `Rectangles`, so `origin` is parenthesized. The commented form of the bytecodes for `Rectangle` center is shown below.

### Rectangle center

0. push the value of the receiver's first instance variable (origin) onto the stack

1. push the value of the receiver's second instance variable (corner) onto the stack

176. send a binary message with the selector +

119. push the `SmallInteger 2` onto the stack

185. send a binary message with the selector /

124. return the object on top of the stack as the value of the message (center)

The stack mentioned in some of the bytecodes is used for several purposes. In this method, it is used to hold the receiver, arguments, and results of the two messages that are sent. The stack is also used as the source of the result to be returned from the center method. The stack is maintained by the interpreter and will be described in greater detail in the next section. A description of all the types of bytecodes will appear at the end of this section.

A programmer does not interact directly with the compiler. When a new source method is added to a class (`Rectangle` in this example), the class asks the compiler for an instance of `CompiledMethod` containing the bytecode translation of the source method. The class provides the compiler with some necessary information not given in the source method, including the names of the receiver's instance variables and the dictionaries containing accessible shared variables (global, class, and pool variables). The compiler translates the source text into a `CompiledMethod` and the class stores the method in its message dictionary. For example, the `CompiledMethod` shown above is stored in `Rectangle`'s message dictionary associated with the selector center.

Another example of the bytecodes compiled from a source method illustrates the use of a store bytecode. The message extent: to a `Rectangle`
changes the receiver's width and height to be equal to the x and y coordinates of the argument (a Point). The receiver's upper left corner (origin) is kept the same and the lower right corner (corner) is moved.

**extent: newExtent**

corner ← origin + newExtent

**Rectangle extent:**

0. push the value of the receiver's first instance variable (origin) onto the stack

16. push the argument (newExtent) onto the stack

176. send a binary message with the selector +

97. pop the top object off of the stack and store it in the receiver's second instance variable (corner)

120. return the receiver as the value of the message (extent):

The forms of source methods and compiled bytecodes are different in several respects. The variable names in a source method are converted into instructions to push objects on the stack, the selectors are converted into instructions to send messages, and the uparrow is converted into an instruction to return a result. The order of the corresponding components is also different in a source method and compiled bytecodes. Despite these differences in form, the source method and compiled bytecodes describe the same actions.

**Compiled Methods**

The compiler creates an instance of CompiledMethod to hold the bytecode translation of a source method. In addition to the bytecodes themselves, a CompiledMethod contains a set of objects called its *literal frame*. The literal frame contains any objects that could not be referred to directly by bytecodes. All of the objects in Rectangle center and *Rectangle extent* were referred to directly by bytecodes, so the CompiledMethods for these methods do not need literal frames. As an example of a CompiledMethod with a literal frame, consider the method for *Rectangle intersects*. The *intersects* message inquires whether one *Rectangle* (the receiver) overlaps another *Rectangle* (the argument).

**intersects: aRectangle**

↑(origin max: aRectangle origin) < (corner min: aRectangle corner)

The four message selectors, max:, origin, min:, and corner are not in the set that can be directly referenced by bytecodes. These selectors are included in the CompiledMethod's literal frame and the send bytecodes refer to the selectors by their position in the literal frame. A CompiledMethod's literal frame will be shown after its bytecodes.

**Rectangle intersects:**

0. push the value of the receiver's first instance variable (origin) onto the stack

16. push the argument (aRectangle)
**209** send a unary message with the selector in the second literal frame location (origin)

**224** send a single argument message with the selector in the first literal frame location (max:)

**1** push the value of the receiver's second instance variable (corner) onto the stack

**16** push the argument (aRectangle) onto the stack

**211** send a unary message with the selector in the fourth literal frame location (corner)

**226** send a single argument message with the selector in the third literal frame location (min:)

**178** send a binary message with the selector <

**124** return the object on top of the stack as the value of the message (intersects:)

literal frame

\#max:

\#origin

\#min:

\#corner

The categories of objects that can be referred to directly by bytecodes are:

* the receiver and arguments of the invoking message

* the values of the receiver's instance variables

* the values of any temporary variables required by the method

* seven special constants (true, false, nil, -1, 0, 1, and 2)

* 32 special message selectors

The 32 special message selectors are listed below.

<table><thead><tr><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>+</td><td>-</td><td>&lt;</td><td>&gt;</td></tr><tr><td>&lt;=</td><td>&gt;=</td><td>=</td><td>~=</td></tr><tr><td>*</td><td>/</td><td>\</td><td>@</td></tr><tr><td>bitShift:<br>(at:)<br>(nextPut:)<br>blockCopy:<br>(new)</td><td>\\<br>(at:put:)<br>(atEnd)<br>value<br>(new:)</td><td>bitAnd:<br>(size)<br>=<br>value:<br>(x)</td><td>bitOr:<br>(next)<br>class<br>(do:)<br>(y)</td></tr></tbody></table>

The selectors in parentheses may be replaced with other selectors by modifying the compiler and recompiling all methods in the system. The other selectors are built into the virtual machine.
Any objects referred to in a CompiledMethod's bytecodes that do not fall into one of the categories above must appear in its literal frame. The objects ordinarily contained in a literal frame are

* shared variables (global, class, and pool)

* most literal constants (numbers, characters, strings, arrays, and symbols)

* most message selectors (those that are not special)

Objects of these three types may be intermixed in the literal frame. If an object in the literal frame is referenced twice in the same method, it need only appear in the literal frame once. The two bytecodes that refer to the object will refer to the same location in the literal frame.

Two types of object that were referred to above, temporary variables and shared variables, have not been used in the example methods. The following example method for Rectangle merge: uses both types. The merge: message is used to find a Rectangle that includes the areas in both the receiver and the argument.

**merge: aRectangle**

| minPoint maxPoint |
minPoint ← origin min: aRectangle origin.
maxPoint ← corner max: aRectangle corner.
↑Rectangle origin: minPoint
corner: maxPoint

When a CompiledMethod uses temporary variables (maxPoint and minPoint in this example), the number required is specified in the first line of its printed form. When a CompiledMethod uses a shared variable (Rectangle in this example) an instance of Association is included in its literal frame. All CompiledMethods that refer to a particular shared variable's name include the same Association in their literal frames.

**Rectangle merge: requires 2 temporary variables**

0. push the value of the receiver's first instance variable (origin) onto the stack

16. push the contents of the first temporary frame location (the argument aRectangle) onto the stack

209. send a unary message with the selector in the second literal frame location (origin)

224. send the single argument message with the selector in the first literal frame location (min:)

105. pop the top object off of the stack and store in the second temporary frame location (minPoint)

1. push the value of the receiver's second instance variable (corner) onto the stack

16. push the contents of the first temporary frame location (the argument aRectangle) onto the stack
**211** send a unary message with the selector in the fourth literal frame location (corner)

**226** send a single argument message with the selector in the third literal frame location (max:)

**106** pop the top object off of the stack and store it in the third temporary frame location (maxPoint)

**69** push the value of the shared variable in the sixth literal frame location (Rectangle) onto the stack

**17** push the contents of the second temporary frame location (minPoint) onto the stack

**18** push the contents of the third temporary frame location (maxPoint) onto the stack

**244** send the two argument message with the selector in the fifth literal frame location (origin:corner:)

**124** return the object on top of the stack as the value of the message (merge:)

literal frame

#min:

#origin

#max:

#corner

#origin:corner:

Association: #Rectangle -> Rectangle

□ *Temporary Variables* Temporary variables are created for a particular execution of a CompiledMethod and cease to exist when the execution is complete. The CompiledMethod indicates to the interpreter how many temporary variables will be required. The arguments of the invoking message and the values of the temporary variables are stored together in the *temporary frame*. The arguments are stored first and the temporary variable values immediately after. They are accessed by the same type of bytecode (whose comments refer to a temporary frame location). Since merge: takes a single argument, its two temporary variables use the second and third locations in the temporary frame. The compiler enforces the fact that the values of the argument names cannot be changed by never issuing a store bytecode referring to the part of the temporary frame inhabited by the arguments.

□ *Shared Variables* Shared variables are found in dictionaries.

* *global variables* in a dictionary whose names can appear in any method

* *class variables* in a dictionary whose names can only appear in the methods of a single class and its subclasses

* *pool variables* in a dictionary whose names can appear in the methods of several classes
Shared variables are the individual associations that make up these dic-
tionaries. The system represents associations in general, and shared
variables in particular, with instances of Association. When the compil-
er encounters the name of a shared variable in a source method, the
Association with the same name is included in the CompiledMethod's
literal frame. The bytecodes that access shared variables indicate the
location of an Association in the literal frame. The actual value of the
variable is stored in an instance variable of the Association. In the
CompiledMethod for Rectangle merge: shown above, class Rectangle is
referenced by including the Association from the global dictionary
whose name is the symbol #Rectangle and whose value is the class
Rectangle.

The Bytecodes

The interpreter understands 256 bytecode instructions that fall into five
categories: pushes, stores, sends, returns, and jumps. This section gives
a general description of each type of bytecode without going into detail
about which bytecode represents which instruction. Chapter 28 de-
scribes the exact meaning of each bytecode. Since more than 256 in-
structions for the interpreter are needed, some of the bytecodes take
extensions. An extension is one or two bytes following the bytecode,
that further specify the instruction. An extension is not an instruction
on its own, it is only a part of an instruction.

☐ *Push Bytecodes* A push bytecode indicates the source of an object to be added to the top of the interpreter's stack. The sources include

* the receiver of the message that invoked the CompiledMethod

* the instance variables of the receiver

* the temporary frame (the arguments of the message and the temporary variables)

* the literal frame of the CompiledMethod

* the top of the stack (i.e., this bytecode duplicates the top of the stack)

Examples of most of the types of push bytecode have been included in
the examples. The bytecode that duplicates the top of the stack is used
to implement cascaded messages.

Two different types of push bytecode use the literal frame as their
source. One is used to push literal constants and the other to push the
value of shared variables. Literal constants are stored directly in the
literal frame, but the values of shared variables are stored in an Associ-
ation that is pointed to by the literal frame. The following example
method uses one shared variable and one literal constant.
### incrementIndex

`tIndex ← Index + 4`

### ExampleClass incrementIndex

**64** push the value of the shared variable in the first literal frame location (Index) onto the stack

**33** push the constant in the second literal frame location (4) onto the stack

**176** send a binary message with the selector +

**129,192** store the object on top of the stack in the shared variable in the first literal frame location (Index)

**124** return the object on top of the stack as the value of the message (incrementIndex)

### literal frame

Association: `#Index` → 260

4

### Store Bytecodes
The bytecodes compiled from an assignment expression end with a store bytecode. The bytecodes before the store bytecode compute the new value of a variable and leave it on top of the stack. A store bytecode indicates the variable whose value should be changed. The variables that can be changed are

* the instance variables of the receiver

* temporary variables

* shared variables

Some of the store bytecodes remove the object to be stored from the stack, and others leave the object on top of the stack, after storing it.

### Send Bytecodes
A send bytecode specifies the selector of a message to be sent and how many arguments it should have. The receiver and arguments of the message are taken off the interpreter's stack, the receiver from below the arguments. By the time the bytecode following the send is executed, the message's result will have replaced its receiver and arguments on the top of the stack. The details of sending messages and returning results is the subject of the next sections of this chapter. A set of 32 send bytecodes refer directly to the special selectors listed earlier. The other send bytecodes refer to their selectors in the literal frame.

### Return Bytecodes
When a return bytecode is encountered, the CompiledMethod in which it was found has been completely executed. Therefore a value is returned for the message that invoked that CompiledMethod. The value is usually found on top of the stack. Four special return bytecodes return the message receiver (self), true, false, and nil.
□ *Jump Bytecodes* Ordinarily, the interpreter executes the bytecodes sequentially in the order they appear in a `CompiledMethod`. The jump bytecodes indicate that the next bytecode to execute is not the one following the jump. There are two varieties of jump, *unconditional* and *conditional*. The unconditional jumps transfer control whenever they are encountered. The conditional jumps will only transfer control if the top of the stack is a specified value. Some of the conditional jumps transfer if the top object on the stack is true and others if it is false. The jump bytecodes are used to implement efficient control structures.

The control structures that are so optimized by the compiler are the conditional selection messages to Booleans (`ifTrue:`, `ifFalse:`, and `ifTrue:ifFalse:`), some of the logical operation messages to Booleans (`and:` and `or:`), and the conditional repetition messages to blocks (`whileTrue:` and `whileFalse:`). The jump bytecodes indicate the next bytecode to be executed relative to the position of the jump. In other words, they tell the interpreter how many bytecodes to skip. The following method for `Rectangle` includes `Point`: uses a conditional jump.

**includesPoint: aPoint**

`origin <= aPoint`

`ifTrue: [↑aPoint < corner]`

`ifFalse: [↑false]`

**Rectangle includesPoint:**

**0** push the value of the receiver's first instance variable (origin) onto the stack

**16** push the contents of the first temporary frame location (the argument aPoint) onto the stack

**180** send a binary message with the selector `<=`

**155** jump ahead 4 bytecodes if the object on top of the stack is false

**16** push the contents of the first temporary frame location (the argument aPoint) onto the stack

**1** push the value of the receiver's second instance variable (corner) onto the stack

**178** send a binary message with the selector `<`

**124** return the object on top of the stack as the value of the message (includesPoint:)

**122** return false as the value of the message (includesPoint:)

## The Interpreter

The Smalltalk-80 interpreter executes the bytecode instructions found in `CompiledMethods`. The interpreter uses five pieces of information and repeatedly performs a three-step cycle.
## The State of the Interpreter

1. The CompiledMethod whose bytecodes are being executed.

2. The location of the next bytecode to be executed in that CompiledMethod. This is the interpreter's *instruction pointer*.

3. The receiver and arguments of the message that invoked the CompiledMethod.

4. Any temporary variables needed by the CompiledMethod.

5. A stack.

The execution of most bytecodes involves the interpreter's stack. Push bytecodes tell where to find objects to add to the stack. Store bytecodes tell where to put objects found on the stack. Send bytecodes remove the receiver and arguments of messages from the stack. When the result of a message is computed, it is pushed onto the stack.

## The Cycle of the Interpreter

1. Fetch the bytecode from the CompiledMethod indicated by the instruction pointer.

2. Increment the instruction pointer.

3. Perform the function specified by the bytecode.

As an example of the interpreter's function, we will trace its execution of the CompiledMethod for Rectangle center. The state of the interpreter will be displayed after each of its cycles. The instruction pointer will be indicated by an arrow pointing at the next bytecode in the CompiledMethod to be executed.

<figure><img src="image_273.png" /></figure>

push the value of the receiver's first instance variable (origin) onto the stack

The receiver, arguments, temporary variables, and objects on the stack will be shown as normally printed (their responses to printString). For example, if a message is sent to a Rectangle, the receiver will be shown as

Receiver

100@100 corner: 200@200

At the start of execution, the stack is empty and the instruction pointer indicates the first bytecode in the CompiledMethod. This CompiledMethod does not require temporaries and the invoking message did not have arguments, so these two categories are also empty.
### Method for Rectangle center

<table><tr><td>0</td><td>push the value of the receiver's first instance variable (origin) onto the stack</td></tr><tr><td>1</td><td>push the value of the receiver's second instance variable (corner) onto the stack</td></tr><tr><td>176</td><td>send a binary message with the selector +</td></tr><tr><td>119</td><td>push the SmallInteger 2 onto the stack</td></tr><tr><td>185</td><td>send a binary message with the selector /</td></tr><tr><td>124</td><td>return the object on top of the stack as the value of the message (center)</td></tr></table>

**Receiver** 100@100 corner: 200@200

### Arguments

### Temporary Variables

### Stack

Following one cycle of the interpreter, the instruction pointer has been advanced and the value of the receiver's first instance variable has been copied onto the stack.

### Method for Rectangle center

<table><tr><td>0</td><td>push the value of the receiver's first instance variable (origin) onto the stack</td></tr><tr><td>1</td><td>push the value of the receiver's second instance variable (corner) onto the stack</td></tr><tr><td>176</td><td>send a binary message with the selector +</td></tr><tr><td>119</td><td>push the SmallInteger 2 onto the stack</td></tr><tr><td>185</td><td>send a binary message with the selector /</td></tr><tr><td>124</td><td>return the object on top of the stack as the value of the message (center)</td></tr></table>

**Receiver** 100@100 corner: 200@200

### Arguments

### Temporary Variables

**Stack** 100@100

The interpreter's second cycle has an effect similar to the first. The top of the stack is shown toward the bottom of the page. This corresponds to the commonly used convention that memory locations are shown with addresses increasing toward the bottom of the page.
### Method for Rectangle center

<table><tr><td>0</td><td>push the value of the receiver's first instance variable (origin) onto the stack</td></tr><tr><td>1</td><td>push the value of the receiver's second instance variable (corner) onto the stack</td></tr><tr><td>176</td><td>send a binary message with the selector +</td></tr><tr><td>119</td><td>push the SmallInteger 2 onto the stack</td></tr><tr><td>185</td><td>send a binary message with the selector /</td></tr><tr><td>124</td><td>return the object on top of the stack as the value of the message (center)</td></tr></table>

**Receiver** 100@100 corner: 200@200

### Arguments

### Temporary Variables

<table><tr><td>Stack</td><td>100@100<br>200@200</td></tr></table>

The interpreter's third cycle encounters a send bytecode. It removes two objects from the stack and uses them as the receiver and argument of a message with selector +. The procedure for sending the message will not be described in detail here. For the moment, it is only necessary to know that eventually the result of the + message will be pushed onto the stack. Sending messages will be described in later sections.

### Method for Rectangle center

<table><tr><td>0</td><td>push the value of the receiver's first instance variable (origin) onto the stack</td></tr><tr><td>1</td><td>push the value of the receiver's second instance variable (corner) onto the stack</td></tr><tr><td>176</td><td>send a binary message with the selector +</td></tr><tr><td>119</td><td>push the SmallInteger 2 onto the stack</td></tr><tr><td>185</td><td>send a binary message with the selector /</td></tr><tr><td>124</td><td>return the object on top of the stack as the value of the message (center)</td></tr></table>

**Receiver** 100@100 corner: 200@200

### Arguments

### Temporary Variables

**Stack** 300@300

The interpreter's next cycle pushes the constant 2 onto the stack.
### Method for Rectangle center

<table><tr><td>0</td><td>push the value of the receiver's first instance variable (origin) onto the stack</td></tr><tr><td>1</td><td>push the value of the receiver's second instance variable (corner) onto the stack</td></tr><tr><td>176</td><td>send a binary message with the selector +</td></tr><tr><td>119</td><td>push the SmallInteger 2 onto the stack</td></tr><tr><td>185</td><td>send a binary message with the selector /</td></tr><tr><td>124</td><td>return the object on top of the stack as the value of the message (center)</td></tr></table>

**Receiver** 100@100 corner: 200@200

**Arguments**

**Temporary Variables**

<table><tr><td>Stack</td><td>300@300</td></tr><tr><td></td><td>2</td></tr></table>

The interpreter's next cycle sends another message whose result replaces its receiver and arguments on the stack.

### Method for Rectangle center

<table><tr><td>0</td><td>push the value of the receiver's first instance variable (origin) onto the stack</td></tr><tr><td>1</td><td>push the value of the receiver's second instance variable (corner) onto the stack</td></tr><tr><td>176</td><td>send a binary message with the selector +</td></tr><tr><td>119</td><td>push the SmallInteger 2 onto the stack</td></tr><tr><td>185</td><td>send a binary message with the selector /</td></tr><tr><td>124</td><td>return the object on top of the stack as the value of the message (center)</td></tr></table>

**Receiver** 100@100 corner: 200@200

**Arguments**

**Temporary Variables**

<table><tr><td>Stack</td><td>150@150</td></tr></table>

The final bytecode returns a result to the center message. The result is found on the stack (150@150). It is clear by this point that a return bytecode must involve pushing the result onto another stack. The details of returning a value to a message will be described after the description of sending a message.

Push, store, and jump bytecodes require only small changes to the state of the interpreter. Objects may be moved to or from the stack, and the instruction pointer is always changed; but most of the state remains the same. Send and return bytecodes may require much larger changes to the interpreter's state. When a message is sent, all five parts of the in-
interpreter's state may have to be changed in order to execute a different CompiledMethod in response to this new message. The interpreter's old state must be remembered because the bytecodes after the send must be executed after the value of the message is returned.

The interpreter saves its state in objects called *contexts*. There will be many contexts in the system at any one time. The context that represents the current state of the interpreter is called the *active context*. When a send bytecode in the active context's CompiledMethod requires a new CompiledMethod to be executed, the active context becomes *suspended* and a new context is created and made active. The suspended context retains the state associated with the original CompiledMethod until that context becomes active again. A context must remember the context that it suspended so that the suspended context can be resumed when a result is returned. The suspended context is called the new context's *sender*.

The form used to show the interpreter's state in the last section will be used to show contexts as well. The active context will be indicated by the word Active in its top delimiter. Suspended contexts will say Suspended. For example, consider a context representing the execution of the CompiledMethod for Rectangle rightCenter with a receiver of 100@100 corner: 200@200. The source method for Rectangle rightCenter is

**rightCenter**

↑ self right @ self center y

The interpreter's state following execution of the first bytecode is shown below. The sender is some other context in the system.

**Active**

**Method for Rectangle rightCenter**

112 push the receiver (self) onto the stack

208 send a unary message with the selector in the first literal (right)

112 push the receiver (self) onto the stack

209 send the unary message with the selector in the second literal (center)

207 send the unary message with the selector y

187 send the unary message with the selector @

124 return the object on top of the stack as the value of the message (rightCenter)

**literal frame**

#right

#center

**Receiver** 100@100 corner: 200@200

**Arguments**

**Temporary Variables**

**Stack** 100@100 corner: 200@200

**Sender**

<figure><img src="image_274.png" /></figure>
After the next bytecode is executed, that context will be suspended. The object pushed by the first bytecode has been removed to be used as the receiver of a new context, which becomes active. The new active context is shown above the suspended context.

Active

Method for Rectangle right

1. push the value of the receiver's second instance variable (corner) onto the stack

206 send a unary message with the selector x

124 return the object on top of the stack as the value of the message (right)

Receiver 100@100 corner: 200@200

Arguments

Temporary Variables

Stack

Sender

<figure><img src="image_275.png" /></figure>

Suspended

Method for Rectangle rightCenter

112 push the receiver (self) onto the stack

208 send a unary message with the selector in the first literal (right)

112 push the receiver (self) onto the stack

209 send the unary message with the selector in the second literal (center)

207 send the unary message with the selector y

187 send the unary message with the selector @

124 return the object on top of the stack as the value of the message (rightCenter)

literal frame

#right

#center

Receiver 100@100 corner: 200@200

Arguments

Temporary Variables

Stack

Sender

<figure><img src="image_276.png" /></figure>
The next cycle of the interpreter advances the new context instead of
the previous one.

Active

Method for Rectangle right

1
push the value of the receiver's second instance variable (corner) onto the stack

206 send a unary message with the selector x

124 return the object on top of the stack as the value of the message (right)

Receiver 100@100 corner: 200@200

Arguments

Temporary Variables

Stack 200@200

Sender

<figure><img src="image_277.png" /></figure>

Suspended

Method for Rectangle rightCenter

112 push the receiver (self) onto the stack

208 send a unary message with the selector in the first literal (right)

112 push the receiver (self) onto the stack

209 send the unary message with the selector in the second literal (center)

207 send the unary message with the selector y

187 send the unary message with the selector @

124 return the object on top of the stack as the value of the message (rightCenter)

literal frame

#right

#center

Receiver 100@100 corner: 200@200

Arguments

Temporary Variables

Stack

Sender

<figure><img src="image_278.png" /></figure>

In the next cycle, another message is sent, perhaps creating another
context. Instead of following the response of this new message (x), we
will skip to the point that this context returns a value (to right). When
the result of x has been returned, the new context looks like this:

Active

Method for Rectangle right

1 push the value of the receiver's second instance variable (corner) onto the stack

206 send a unary message with the selector x

124 return the object on top of the stack as the value of the message (right)

Receiver

100 @ 100 corner: 200 @ 200

Arguments

Temporary Variables

Stack

200

Sender

<figure><img src="image_279.png" /></figure>

Suspended

Method for Rectangle rightCenter

112 push the receiver (self) onto the stack

208 send a unary message with the selector in the first literal (right)

112 push the receiver (self) onto the stack

209 send the unary message with the selector in the second literal (center)

207 send the unary message with the selector y

187 send the unary message with the selector @

124 return the object on top of the stack as the value of the message (rightCenter)

literal frame

\#right

\#center

Receiver

100 @ 100 corner: 200 @ 200

Arguments

Temporary Variables

Stack

Sender

<figure><img src="image_280.png" /></figure>

The next bytecode returns the value on the top of the active context's stack (200) as the value of the message that created the context (right). The active context's sender becomes the active context again and the returned value is pushed on its stack.
Active

Method for Rectangle rightCenter

112 push the receiver (self) onto the stack

208 send a unary message with the selector in the first literal (right)

<figure><img src="image_281.png" /></figure>

112 push the receiver (self) onto the stack

209 send the unary message with the selector in the second literal (center)

207 send the unary message with the selector y

187 send the unary message with the selector @

124 return the object on top of the stack as the value of the message (rightCenter)

literal frame

#right

#center

Receiver 100@100 corner: 200@200

Arguments

Temporary Variables

Stack 200

Sender

<figure><img src="image_282.png" /></figure>

Block Contexts

The contexts illustrated in the last section are represented in the system by instances of MethodContext. A MethodContext represents the execution of a CompiledMethod in response to a message. There is another type of context in the system, which is represented by instances of BlockContext. A BlockContext represents a block in a source method that is not part of an optimized control structure. The compilation of the optimized control structures was described in the earlier section on jump bytecodes. The bytecodes compiled from a nonoptimized control structure are illustrated by the following hypothetical method in Collection. This method returns a collection of the classes of the receiver's elements.

classes

↑self collect: [ :element | element class]

Collection classes requires 1 temporary variable

112 push the receiver (self) onto the stack

137 push the active context (thisContext) onto the stack

118 push the SmallInteger 1 onto the stack

200 send a single argument message with the selector blockCopy:

164,4 jump around the next 4 bytes

104 pop the top object off of the stack and store in the first temporary frame location (element)
**16** push the contents of the first temporary frame location (element) onto the stack

**199** send a unary message with the selector class

**125** return the object on top of the stack as the value of the block

**224** send a single argument message with the selector in the first literal frame location (collect:)

**124** return the object on top of the stack as the value of the message (classes)

literal frame

\#collect:

A new BlockContext is created by the `blockCopy:` message to the active context. The bytecode that pushes the active context was not described along with the rest of the push bytecodes since the function of contexts had not been described at that point. The argument to `blockCopy:` (1 in this example) indicates the number of block arguments the block requires. The BlockContext shares much of the state of the active context that creates it. The receiver, arguments, temporary variables, `CompiledMethod`, and sender are all the same. The BlockContext has its own instruction pointer and stack. Upon returning from the `blockCopy:` message, the newly created BlockContext is on the stack of the active context and the next instruction jumps around the bytecodes that describe the actions of the block. The active context gave the BlockContext an initial instruction pointer pointing to the bytecode after this jump. The compiler always uses an extended (two-byte) jump after a `blockCopy:` so that the BlockContext's initial instruction pointer is always two more than the active context's instruction pointer when it receives the `blockCopy:` message.

The method for `Collection` classes creates a `BlockContext`, but does not execute its bytecodes. When the collection receives the `collect:` message, it will repeatedly send value: messages to the BlockContext with the elements of the collection as arguments. A `BlockContext` responds to value: by becoming the active context, which causes its bytecodes to be executed by the interpreter. Before the `BlockContext` becomes active, the argument to value: is pushed onto the `BlockContext`'s stack. The first bytecode executed by the `BlockContext` stores this value in a temporary variable used for the block argument.

A `BlockContext` can return a value in two ways. After the bytecodes in the block have been executed, the final value on the stack is returned as the value of the message value or value:. The block can also return a value to the message that invoked the `CompiledMethod` that created the `BlockContext`. This is done with the regular return bytecodes. The hypothetical method for `Collection` `containsinstanceOf:` uses both types of return from a `BlockContext`.

`containsinstanceOf: aClass`

self do: [ :element | (element isKindOf: aClass) ifTrue: [↑true]].

↑false
**Collection containsInstanceOf:** requires 1 temporary variable

112 push the receiver (self) onto the stack

137 push the active context (thisContext) onto the stack

118 push the SmallInteger 1 onto the stack

200 send a single argument message with the selector blockCopy:

164,8 jump around the next 8 bytes

105 pop the top object off of the stack and store in the second temporary frame location (element)

17 push the contents of the second temporary frame location (element) onto the stack

16 push the contents of the first temporary frame location (aClass) onto the stack

224 send a single argument message with the selector in the first literal frame location (isKindOf:)

152 pop the top object off of the stack and jump around 1 byte if it is false

121 return true as the value of the message (containsInstanceOf:)

115 push nil onto the stack

125 return the object on top of the stack as the value of the block

203 send the single argument message with the selector do:

135 pop the top object off the stack

122 return false as the value of the message (containsInstanceOf:)

**literal frame**

#isKindOf:

**Messages**

When a send bytecode is encountered, the interpreter finds the CompiledMethod indicated by the message as follows.

1. Find the message receiver. The receiver is below the arguments on the stack. The number of arguments is indicated in the send bytecode.

2. Access a message dictionary. The original message dictionary is found in the receiver's class.

3. Look up the message selector in the message dictionary. The selector is indicated in the send bytecode.

4. If the selector is found, the associated CompiledMethod describes the response to the message.

5. If the selector is not found, a new message dictionary must be searched (returning to step 3). The new message dictionary will be found in the superclass of the last class whose message dictionary was searched. This cycle may be repeated several times, traveling up the superclass chain.

If the selector is not found in the receiver's class nor in any of its superclasses, an error is reported, and execution of the bytecodes following the send is suspended.
□ Superclass Sends A variation of the send bytecodes called super-sends uses a slightly different algorithm to find the CompiledMethod associated with a message. Everything is the same except for the second step, which specifies the original message dictionary to search. When a super-send is encountered, the following second step is substituted.

2. Access a message dictionary. The original message dictionary is found in the superclass of the class in which the currently executing CompiledMethod was found.

Super-send bytecodes are used when super is used as the receiver of a message in a source method. The bytecode used to push the receiver will be the same as if self had been used, but a super-send bytecode will be used to describe the selector.

As an example of the use of a super-send, imagine a subclass of Rectangle called ShadedRectangle that adds an instance variable named shade. A Rectangle might respond to the message shade: by producing a new ShadedRectangle. ShadedRectangle provides a new method for the message intersect, returning a ShadedRectangle instead of a Rectangle. This method must use super to access its own ability to actually compute the intersection.

**intersect: aRectangle**

1 (super intersect: aRectangle)

shade: shade

**ShadedRectangle intersect:**

112 push the receiver (self) onto the stack

16 push the contents of the first temporary frame location (the argument aRectangle) onto the stack

133,33 send to super a single argument message with the selector in the second literal frame location (intersect.)

2 push the value of the receiver's third instance variable (shade) onto the stack

224 send a single argument message with the selector in the first literal frame location (shade.)

124 return the object on top of the stack as the value of the message (intersect.)

**literal frame**

\#shade:

\#intersect:

Association: \#ShadedRectangle → ShadedRectangle

It is important to note that the initial class searched in response to a super-send will be the superclass of the receiver's class only if the CompiledMethod containing the super-send was originally found the re-
receiver's class. If the CompiledMethod was originally found in a super-class of the receiver's class, the search will start in that class's superclass. Since the interpreter's state does not include the class in which it found each CompiledMethod, that information is included in the CompiledMethod itself. Every CompiledMethod that includes a super-send bytecode refers to the class in whose message dictionary it is found. The last entry of the literal frame of those CompiledMethods contains an association referring to the class.

## Primitive Methods

The interpreter's actions after finding a CompiledMethod depend on whether or not the CompiledMethod indicates that a primitive method may be able to respond to the message. If no primitive method is indicated, a new MethodContext is created and made active as described in previous sections. If a primitive method is indicated in the CompiledMethod, the interpreter may be able to respond to the message without actually executing the bytecodes. For example, one of the primitive methods is associated with the `+` message to instances of `SmallInteger`.

**+ addend**

`<primitive: 1>`

`↑ super + addend`

**SmallInteger + associated with primitive #1**

**112** push the receiver (self) onto the stack

**16** push the contents of the first temporary frame location (the argument addend) onto the stack

**133,32** send to super a single argument message with the selector in the first literal frame location (`+`)

**124** return the object on top of the stack as the value of the message (`+`)

**literal frame**

`#+`

Even if a primitive method is indicated for a CompiledMethod, the interpreter may not be able to respond successfully. For example, the argument of the `+` message might not be another instance of `SmallInteger` or the sum might not be representable by a `SmallInteger`. If the interpreter cannot execute the primitive for some reason, the primitive is said to *fail*. When a primitive fails, the bytecodes in the CompiledMethod are executed as if the primitive method had not been indicated. The method for `SmallInteger +` indicates that the `+` method in the superclass (`Integer`) will be used if the primitive fails.

There are about a hundred primitive methods in the system that per-
form four types of operation. The exact function of all of the primitives
will be described in Chapter 29.

1. Arithmetic

2. Storage management

3. Control

4. Input-output

## The Object Memory

The object memory provides the interpreter with an interface to the objects that make up the Smalltalk-80 virtual image. Each object is associated with a unique identifier called its *object pointer*. The object memory and interpreter communicate about objects with object pointers. The size of object pointers determines the maximum number of objects a Smalltalk-80 system can contain. This number is not fixed by anything about the language, but the implementation described in this book uses 16-bit object pointers, allowing 65536 objects to be referenced. Implementation of the Smalltalk-80 system with larger object references will require changing certain parts of the virtual machine specification. It is not within the scope of this book to detail the relevant changes.

The object memory associates each object pointer with a set of other object pointers. Every object pointer is associated with the object pointer of a class. If an object has instance variables, its object pointer is also associated with the object pointers of their values. The individual instance variables are referred to by zero-relative integer indices. The value of an instance variable can be changed, but the class associated with an object cannot be changed. The object memory provides the following five fundamental functions to the interpreter.

1. *Access* the value of an object's *instance variable*. The object pointer of the instance and the index of the instance variable must be supplied. The object pointer of the instance variable's value is returned.

2. *Change* the value of an object's *instance variable*. The object pointer of the instance and the index of the instance variable must be supplied. The object pointer of the new value must also be supplied.

3. *Access* an object's *class*. The object pointer of the instance must be supplied. The object pointer of the instance's class is returned.

4. *Create* a new *object*. The object pointer of the new object's class
and the number of instance variables it should have must be supplied. The object pointer of the new instance is returned.

5. Find the number of instance variables an object has. The object's pointer must be supplied. The number of instance variables is returned.

There is no explicit function of the object memory to remove an object no longer being used because these objects are reclaimed automatically. An object is reclaimed when there are no object pointers to it from other objects. This reclamation can be accomplished either by reference counting or garbage collection.

There are two additional features of the object memory that provide efficient representation of numerical information. The first of these sets aside certain object pointers for instances of class `SmallInteger`. The second allows objects to contain integer values instead of object pointers.

□ *Representation of Small Integers* The instances of class `SmallInteger` represent the integers –16384 through 16383. Each of these instances is assigned a unique object pointer. These object pointers all have a 1 in the low-order bit position and the two's complement representation of their value in the high-order 15 bits. An instance of `SmallInteger` needs no instance storage since both its class and its value can be determined from its object pointer. Two additional functions are provided by the object memory to convert back and forth between `SmallInteger` object pointers and numerical values.

6. Find the numerical value represented by a `SmallInteger`. The object pointer of the `SmallInteger` must be supplied. The two's complement value is returned.

7. Find the `SmallInteger` representing a numerical value. The two's complement value must be supplied. A `SmallInteger` object pointer is returned.

This representation for `SmallIntegers` implies that there can be 32768 instances of the other classes in the system. It also implies that equality (`==`) and equivalence (`==`) will be the same for instances of `SmallInteger`. Integers outside the range –16384 through 16383 are represented by instances of class `LargePositiveInteger` or `LargeNegativeInteger`. There may be several instances representing the same value, so equality and equivalence are different.

□ *Collections of Integer Values* Another special representation is included for objects representing collections of integers. Instead of storing the object pointers of the `SmallIntegers` representing the contents of the
collection, the actual numerical values are stored. The values in these
special collections are constrained to be positive. There are two variet-
ies of collection, one limiting its values to be less than 256 and the oth-
er limiting its values to be less than 65536. The object memory provides
functions analogous to the first five listed in this section, but for objects
whose contents are numerical values instead of object pointers.

The distinction between objects that contain object pointers and
those that contain integer values is never visible to the Smalltalk-80
programmer. When one of these special numerical collections is
accessed by sending it a message, the object pointer of an object repre-
senting the value is returned. The nature of these special collections is
only evident in that they may refuse to store objects that do not repre-
sent integers within the proper range.

## The Hardware

The Smalltalk-80 implementation has been described as a virtual ma-
chine to avoid unnecessary hardware dependencies. It is naturally as-
sumed that the hardware will include a processor and more than
enough memory to store the virtual image and the machine language
routines simulating the interpreter and object memory. The current
size of the virtual image requires at least a half megabyte of memory.

The size of the processor and the organization of the memory are not
actually constrained by the virtual machine specification. Since object
pointers are 16 bits, the most convenient arrangement would be a
16-bit processor and a memory of 16-bit words. As with the processor
and memory of any system, the faster the better.

The other hardware requirements are imposed by the primitives that
the virtual image depends on. These input-output devices and clocks are
listed below.

1. A bitmap display. It is most convenient if the bitmap being displayed can be located in the object memory, although this is not absolutely necessary.

2. A pointing device.

3. Three buttons associated with the pointing device. It is most convenient if these are physically located on the device.

4. A keyboard, either decoded ASCII or undecoded ALTO.

5. A disk. The standard Smalltalk-80 virtual image contains only a skeleton disk system that must be tailored to the actual disk used.

6. A millisecond timer.

7. A real time clock with one second resolution.
27

# Specification of the Virtual Machine

Form of the Specification

Object Memory Interface

Objects Used by the Interpreter

Compiled Methods

Contexts

Classes

<figure><img src="image_283.png" /></figure>
Chapter 26 described the function of the Smalltalk virtual machine, which consists of an interpreter and an object memory. This chapter and the next three present a more formal specification of these two parts of the virtual machine. Most implementations of the virtual machine will be written in machine language or microcode. However, for specification purposes, these chapters will present an implementation of the virtual machine in Smalltalk itself. While this is a somewhat circular proposition, every attempt has been made to ensure that no details are hidden as a result.

This chapter consists of three sections. The first describes the conventions and terminology used in the formal specification. It also provides some warnings of possible confusion resulting from the form of this specification. The second section describes the object memory routines used by the interpreter. The implementation of these routines will be described in Chapter 30. The third section describes the three main types of object that the interpreter manipulates, methods, contexts, and classes. Chapter 28 describes the bytecode set and how it is interpreted; Chapter 29 describes the primitive routines.

## Form of the Specification

Two class descriptions named Interpreter and ObjectMemory make up the formal specification of the Smalltalk-80 virtual machine. The implementation of Interpreter will be presented in detail in this chapter and the following two; the implementation of ObjectMemory in Chapter 30.

A potential source of confusion in these chapters comes from the two Smalltalk systems involved in the descriptions, the system containing Interpreter and ObjectMemory and the system being interpreted. Interpreter and ObjectMemory have methods and instance variables and they also manipulate methods and instance variables in the system they interpret. To minimize the confusion, we will use a different set of terminology for each system. The methods of Interpreter and ObjectMemory will be called *routines*; the word *method* will be reserved for the methods being interpreted. Similarly, the instance variables of Interpreter and ObjectMemory will be called *registers*; the word *instance variable* will be reserved for the instance variables of objects in the system being interpreted.

The arguments of the routines and the contents of the registers of Interpreter and ObjectMemory will almost always be instances of Integer (SmallIntegers and LargePositiveIntegers). This can also be a source of confusion since there are Integers in the interpreted system. The Integers that are arguments to routines and contents of registers represent object pointers and numerical values of the interpreted system. Some of these will represent the object pointers or values of Integers in the interpreted system.
The interpreter routines in this specification will all be in the form of Smalltalk method definitions. For example

### `routineName: argumentName`

| temporaryVariable |
temporaryVariable - self anotherRoutine: argumentName.
temporaryVariable - 1

The routines in the specification will contain five types of expression.

1. *Calls on other routines of the interpreter.* Since both the invocation and definition of the routine are in Interpreter, they will appear as messages to self.

* `self headerOf: newMethod`

* `self storeInstructionPointerValue: value inContext: contextPointer`

2. *Calls on routines of the object memory.* An Interpreter uses the name memory to refer to its object memory, so these calls will appear as messages to memory.

* `memory fetchClassOf: newMethod`

* `memory storePointer: senderIndex ofObject: contextPointer withValue: activeContext`

3. *Arithmetic operations on object pointers and numerical values.* Arithmetic operations will be represented by standard Smalltalk arithmetic expressions, so they will appear as messages to the numbers themselves.

* `receiverValue + argumentValue`

* `selectorPointer bitShift: -1`

4. *Array accesses.* Certain tables maintained by the interpreter are represented in the formal specification by Arrays. Access to these will appear as `at:` and `at:put:` messages to the Arrays.

* `methodCache at: hash`

* `semaphoreList at: semaphoreIndex put: semaphorePointer`

5. *Conditional control structures.* The control structures of the virtual machine will be represented by standard Smalltalk conditional control structures. Conditional selections will appear as messages to Booleans. Conditional repetitions will appear as messages to blocks.
* `index < length ifTrue: [...]`

* `sizeFlag = 1 ifTrue: [...]`

* `ifFalse: [...]`

* `[currentClass ~= NilPointer] whileTrue: [...]`

The definition of Interpreter describes the function of the Smalltalk-80 bytecode interpreter; however, the form of a machine language implementation of the interpreter may be very different, particularly in the control structures it uses. The dispatch to the appropriate routine to execute a bytecode is an example of something a machine language interpreter might do differently. To find the right routine to execute, a machine language interpreter would probably do some kind of address arithmetic to calculate where to jump; whereas, as we will see, Interpreter does a series of conditionals and routine calls. In a machine language implementation, the routines that execute each bytecode would simply jump back to the beginning of the bytecode fetch routine when they were finished, instead of returning through the routine call structure.

Another difference between Interpreter and a machine language implementation is the degree of optimization of the code. For the sake of clarity, the routines specified in this chapter have not been optimized. For example, to perform a task, Interpreter may fetch a pointer from the object memory several times in different routines, when a more optimized interpreter might save the value in a register for later use. Many of the routines in the formal specification will not be subroutines in a machine language implementation, but will be written in-line instead.

## Object Memory Interface

Chapter 26 gave an informal description of the object memory. Since the routines of Interpreter need to interact with the object memory, we need its formal functional specification. This will be presented as the protocol specification of class ObjectMemory. Chapter 30 will describe one way to implement this protocol specification.

The object memory associates a 16-bit object pointer with

1. the object pointer of a class-describing object and

2. a set of 8- or 16-bit fields that contain object pointers or numerical values.

The interface to the object memory uses zero-relative integer indices to indicate an object's fields. Instances of Integer are used for both object pointers and field indices in the interface between the interpreter and object memory.
The protocol of ObjectMemory contains pairs of messages for fetching and storing object pointers or numerical values in an object's fields.

### object pointer access

**fetchPointer: fieldIndex ofObject: objectPointer**
Return the object pointer found in the field numbered fieldIndex of the object associated with objectPointer.

**storePointer: fieldIndex ofObject: objectPointer withValue: valuePointer**
Store the object pointer valuePointer in the field numbered fieldIndex of the object associated with objectPointer.

### word access

**fetchWord: fieldIndex ofObject: objectPointer**
Return the 16-bit numerical value found in the field numbered fieldIndex of the object associated with objectPointer.

**storeWord: fieldIndex ofObject: objectPointer withValue: valueWord**
Store the 16-bit numerical value valueWord in the field numbered fieldIndex of the object associated with objectPointer.

### byte access

**fetchByte: byteIndex ofObject: objectPointer**
Return the 8-bit numerical value found in the byte numbered byteIndex of the object associated with objectPointer.

**storeByte: byteIndex ofObject: objectPointer withValue: valueByte**
Store the 8-bit numerical value valueByte in the byte numbered byteIndex of the object associated with objectPointer.

Note that `fetchPointer:ofObject:` and `fetchWord:ofObject:` will probably be implemented in an identical fashion, since they both load a 16-bit quantity. However, the implementation of `storePointer:ofObject:` will be different from the implementation of `storeWord:ofObject:` since it will have to perform reference counting (see Chapter 30) if the object memory keeps dynamic reference counts. We have maintained a separate interface for `fetchPointer:ofObject:` and `fetchWord:ofObject:` for the sake of symmetry.

Even though most of the maintenance of reference counts can be done automatically in the `storePointer:ofObject:withValue:` routine, there are some points at which the interpreter routines must directly manipulate the reference counts. Therefore, the following two routines are included in the object memory interface. If an object memory uses only garbage collection to reclaim unreferenced objects, these routines are no-ops.

### reference counting

**increaseReferencesTo: objectPointer**
Add one to the reference count of the object whose object pointer is `objectPointer`.
decreaseReferencesTo: objectPointer

Subtract one from the reference count of the object whose object pointer is objectPointer.

Since every object contains the object pointer of its class description, that pointer could be considered the contents of one of the object's fields. Unlike other fields, however, an object's class may be fetched, but its value may not be changed. Given the special nature of this pointer, it was decided not to access it in the same way. Therefore, there is a special protocol for fetching an object's class.

class pointer access

fetchClassOf: objectPointer

Return the object pointer of the class-describing object for the object associated with objectPointer.

The length of an object might also be thought of as the contents of one of its fields. However, it is like the class field in that it may not be changed. There are two messages in the object memory protocol that ask for the number of words in an object and the number of bytes in an object. Note that we have not made a distinction between words and pointers in this case since we assume that they both fit in exactly one field.

length access

fetchWordLengthOf: objectPointer

Return the number of fields in the object associated with objectPointer.

fetchByteLengthOf: objectPointer

Return the number of byte fields in the object associated with objectPointer.

Another important service of the object memory is to create new objects. The object memory must be supplied with a class and a length and will respond with a new object pointer. Again, there are three versions for creating objects with pointers, words, or bytes.

object creation

instantiateClass: classPointer withPointers: instanceSize

Create a new instance of the class whose object pointer is classPointer with instanceSize fields that will contain pointers. Return the object pointer of the new object.

instantiateClass: classPointer withWords: instanceSize

Create a new instance of the class whose object pointer is classPointer with instanceSize fields that will contain 16-bit numerical values. Return the object pointer of the new object.

instantiateClass: classPointer withBytes: instanceByteSize

Create a new instance of the class whose object pointer is classPointer with room for instanceByteSize 8-bit numerical values. Return the object pointer of the new object.
Two routines of the object memory allow the instances of a class to be enumerated. These follow an arbitrary ordering of object pointers. Using the numerical order of the pointers themselves is reasonable.

### instance enumeration

<table><tr><td>initialInstanceOf: classPointer</td><td>Return the object pointer of the first instance of the class whose object pointer is classPointer in the defined ordering (e.g., the one with the smallest object pointer).</td></tr><tr><td>instanceAfter: objectPointer</td><td>Return the object pointer of the next instance of the same class as the object whose object pointer is objectPointer in the defined ordering (e.g., the one with the next larger object pointer).</td></tr></table>

Another routine of the object memory allows the object pointers of two objects to be interchanged.

### pointer swapping

<table><tr><td>swapPointersOf: firstPointer and: secondPointer</td><td>Make firstPointer refer to the object whose object pointer was secondPointer and make secondPointer refer to the object whose object pointer was firstPointer.</td></tr></table>

As described in Chapter 26, integers between -16384 and 16383 are encoded directly as object pointers with a 1 in the low-order bit position and the appropriate 2's complement value stored in the high-order 15 bits. These objects are instances of class SmallInteger. A SmallInteger's value, which would ordinarily be stored in a field, is actually determined from its object pointer. So instead of storing a value into a SmallInteger's field, the interpreter must request the object pointer of a SmallInteger with the desired value (using the `integerObjectOf:` routine). And instead of fetching the value from a field, it must request the value associated with the object pointer (using the `integerValueOf:` routine). There are also two routines that determine whether an object pointer refers to a SmallInteger (`isIntegerObject:`) and whether a value is in the right range to be represented as a SmallInteger (`isIntegerValue:`). The function of the `isIntegerObject:` routine can also be performed by requesting the class of the object and seeing if it is SmallInteger.

### integer access

<table><tr><td>integerValueOf: objectPointer</td><td>Return the value of the instance of SmallInteger whose pointer is objectPointer.</td></tr><tr><td>integerObjectOf: value</td><td>Return the object pointer for an instance of SmallInteger whose value is value.</td></tr><tr><td>isIntegerObject: objectPointer</td><td>Return true if objectPointer is an instance of SmallInteger, false if not.</td></tr><tr><td>isIntegerValue: value</td><td>Return true if value can be represented as an instance of SmallInteger, false if not.</td></tr></table>

The interpreter provides two special routines to access fields that contain SmallIntegers. The `fetchInteger/ofObject:` routine returns the value
of a SmallInteger whose pointer is stored in the specified field. The
check to make sure that the pointer is for a SmallInteger is made for
uses of this routine when non-SmallIntegers can be tolerated. The
primitiveFail routine will be described in the section on primitive rou-
tines.

fetchInteger: fieldIndex ofObject: objectPointer

| integerPointer |
integerPointer ← memory fetchPointer: fieldIndex
                 ofObject: objectPointer.

(memory isIntegerObject: integerPointer)
ifTrue: [^memory integerValueOf: integerPointer]
ifFalse: [^self primitiveFail]

The storeInteger:ofObject:withValue: routine stores the pointer of the SmallInteger with specified value in the specified field.

storeInteger: fieldIndex
          ofObject: objectPointer
          withValue: integerValue

| integerPointer |
(memory isIntegerValue: integerValue)
ifTrue: [integerPointer ← memory integerObjectOf: integerValue.
memory storePointer: fieldIndex
           ofObject: objectPointer
           withValue: integerPointer]
ifFalse: [^self primitiveFail]

The interpreter also provides a routine to perform a transfer of several
pointers from one object to another. It takes the number of pointers to
transfer, and the initial field index and object pointer of the source and
destination objects as arguments.

transfer: count
fromIndex: firstFrom
ofObject: fromOop
toIndex: firstTo
ofObject: toOop

| fromIndex toIndex lastFrom oop |
fromIndex ← firstFrom.
lastFrom ← firstFrom + count.
toIndex ← firstTo.

[fromIndex < lastFrom] whileTrue:
  [oop ← memory fetchPointer: fromIndex
     ofObject: fromOop.
     memory storePointer: toIndex
     ofObject: toOop
     withValue: oop:
memory storePointer: fromIndex
  ofObject: fromOop
  withValue: NilPointer.
fromIndex ← fromIndex + 1.
toIndex ← toIndex + 1]

The interpreter also provides routines to extract bit fields from numerical values. These routines refer to the high-order bit with index 0 and the low-order bit with index 15.

**extractBits: firstBitIndex to: lastBitIndex of: anInteger**

†(anInteger bitShift: lastBitIndex - 15)
bitAnd: (2 raisedTo: lastBitIndex - firstBitIndex + 1) - 1

**highByteOf: anInteger**

†self extractBits: 0 to: 7
of: anInteger

**lowByteOf: anInteger**

†self extractBits: 8 to: 15
of: anInteger

## Objects Used by the Interpreter

This section describes what might be called the data structures of the interpreter. Although they are objects, and therefore more than data structures, the interpreter treats these objects as data structures. The first two types of object correspond to data structures found in the interpreters for most languages. *Methods* correspond to programs, subroutines, or procedures. *Contexts* correspond to stack frames or activation records. The final structure described in this section, that of *classes*, is not used by the interpreter for most languages but only by the compiler. Classes correspond to aspects of the type declarations of some other languages. Because of the nature of *Smalltalk* messages, the classes must be used by the interpreter at runtime.

There are many constants included in the formal specification. They mostly represent object pointers of known objects or field indices for certain kinds of objects. Most of the constants will be named and a routine that initializes them will be included as a specification of their value. As an example, the following routines initialize the object pointers known to the interpreter.

**initializeSmallIntegers**

```
"SmallIntegers"
MinusOnePointer ← 65535.
ZeroPointer ← 1.
OnePointer ← 3.
TwoPointer ← 5
```
initializeGuaranteedPointers

"UndefinedObject and Booleans"
NilPointer ← 2.
FalsePointer ← 4.
TruePointer ← 6.
"Root"
SchedulerAssociationPointer ← 8.
"Classes"
ClassStringPointer ← 14.
ClassArrayPointer ← 16.
ClassMethodContextPointer ← 22.
ClassBlockContextPointer ← 24.
ClassPointPointer ← 26.
ClassLargePositiveIntegerPointer ← 28.
ClassMessagePointer ← 32.
ClassCharacterPointer ← 40.
"Selectors"
DoesNotUnderstandSelector ← 42.
CannotReturnSelector ← 44.
MustBeBooleanSelector ← 52.
"Tables"
SpecialSelectorPointer ← 48.
CharacterTablePointer ← 50

## Compiled Methods

The bytecodes executed by the interpreter are found in instances of CompiledMethod. The bytecodes are stored as 8-bit values, two to a word. In addition to the bytecodes, a CompiledMethod contains some object pointers. The first of these object pointers is called the *method header* and the rest of the object pointers make up the method's *literal frame*. Figure 27.1 shows the structure of a CompiledMethod and the following routine initializes the indices used to access fields of CompiledMethods.

<figure><img src="image_284.png" /><figcaption>Figure 27.1</figcaption></figure>
**initializeMethodIndices**

"Class CompiledMethod"
HeaderIndex ← 0.
LiteralStart ← 1

The header is a SmallInteger that encodes certain information about the
CompiledMethod.

**headerOf: methodPointer**

↑memory fetchPointer: HeaderIndex
ofObject: methodPointer

The literal frame contains pointers to objects referred to by the
bytecodes. These include the selectors of messages that the method
sends, and shared variables and constants to which the method refers.

**literal: offset ofMethod: methodPointer**

↑memory fetchPointer: offset + LiteralStart
ofObject: methodPointer

Following the header and literals of a method are the bytecodes. Methods are the only objects in the Smalltalk system that store both object pointers (in the header and literal frame) and numerical values (in the bytecodes). The form of the bytecodes will be discussed in the next chapter.

□ *Method Headers* Since the method header is a SmallInteger, its value will be encoded in its pointer. The high-order 15 bits of the pointer are available to encode information; the low-order bit must be a one to indicate that the pointer is for a SmallInteger. The header includes four bit fields that encode information about the CompiledMethod. Figure 27.2 shows the bit fields of a header.

<figure><img src="image_285.png" /><figcaption>Figure 27.2</figcaption></figure>

The temporary count indicates the number of temporary variables used
by the CompiledMethod. This includes the number of arguments.

**temporaryCountOf: methodPointer**

↑self extractBits: 3 to: 7
of: (self headerOf: methodPointer)

The large context flag indicates which of two sizes of MethodContext are
needed. The flag indicates whether the sum of the maximum stack
depth and the number of temporary variables needed is greater than twelve. The smaller MethodContexts have room for 12 and the larger have room for 32.

**largeContextFlagOf: methodPointer**

↑self extractBits: 8 to: 8
of: (self headerOf: methodPointer)

The literal count indicates the size of the MethodContext's literal frame. This, in turn, indicates where the MethodContext's bytecodes start.

**literalCountOf: methodPointer**

↑self literalCountOfHeader: (self headerOf: methodPointer)

**literalCountOfHeader: headerPointer**

↑self extractBits: 9 to: 14
of: headerPointer

The object pointer count indicates the total number of object pointers in a MethodContext, including the header and literal frame.

**objectPointerCountOf: methodPointer**

↑(self literalCountOf: methodPointer) + LiteralStart

The following routine returns the byte index of the first bytecode of a CompiledMethod.

**initialInstructionPointerOfMethod: methodPointer**

↑((self literalCountOf: methodPointer) + LiteralStart) * 2 + 1

The flag value is used to encode the number of arguments a CompiledMethod takes and whether or not it has an associated primitive routine.

**flagValueOf: methodPointer**

↑self extractBits: 0 to: 2
of: (self headerOf: methodPointer)

The eight possible flag values have the following meanings:

<table><thead><tr><td>flag value</td><td>meaning</td></tr></thead><tbody><tr><td>0-4</td><td>no primitive and 0 to 4 arguments</td></tr><tr><td>5</td><td>primitive return of self (0 arguments)</td></tr><tr><td>6</td><td>primitive return of an instance variable (0 arguments)</td></tr></tbody></table>
Since the majority of CompiledMethods have four or fewer arguments and do not have an associated primitive routine, the flag value is usually simply the number of arguments.

☐ **Special Primitive Methods** Smalltalk methods that only return the receiver of the message (self) produce CompiledMethods that have no literals or bytecodes, only a header with a flag value of 5. In similar fashion, Smalltalk methods that only return the value of one of the receiver's instance variables produce CompiledMethods that contain only headers with a flag value of 6. All other methods produce CompiledMethods with bytecodes. When the flag value is 6, the index of the instance variable to return is found in the header in the bit field ordinarily used to indicate the number of temporary variables used by the CompiledMethod. Figure 27.3 shows a CompiledMethod for a Smalltalk method that only returns a receiver instance variable.

<figure><img src="image_286.png" /></figure>

flag field

value index

<caption>Figure 27.3</caption>

The following routine returns the index of the field representing the instance variable to be returned in the case that the flag value is 6.

**fieldOf: methodPointer**

↑self extractBits: 3 to: 7

of: (self headerOf: methodPointer)

☐ **Method Header Extensions** If the flag value is 7, the next to last literal is a header extension, which is another SmallInteger. The header extension includes two bit fields that encode the argument count and primitive index of the CompiledMethod. Figure 27.4 shows the bit fields of a header extension.

<figure><img src="image_287.png" /></figure>

argument
count

primitive
index

<caption>Figure 27.4</caption>

The following routines are used to access a header extension and its bit fields.
**headerExtensionOf: methodPointer**

| literalCount |
literalCount ← self literalCountOf: methodPointer.
↑self literal: literalCount-2
ofMethod: methodPointer

**argumentCountOf: methodPointer**

| flagValue |
flagValue ← self flagValueOf: methodPointer.
flagValue < 5
ifTrue: [↑flagValue].
flagValue < 7
ifTrue: [↑0]
ifFalse: [↑self extractBits: 2 to: 6
of: (self headerExtensionOf: methodPointer)]

**primitivePEATOf: methodPointer**

| flagValue |
flagValue ← self flagValueOf: methodPointer.
flagValue=7
ifTrue: [↑self extractBits: 7 to: 14
of: (self headerExtensionOf: methodPointer)]
ifFalse: [↑0]

Any CompiledMethod that sends a superclass message (i.e., a message to
super) or contains a header extension, will have as its last literal an As-
sociation whose value is the class in whose message dictionary the
CompiledMethod is found. This is called the *method class* and is
accessed by the following routine.

**methodClassOf: methodPointer**

| literalCount association |
literalCount ← self literalCountOf: methodPointer.
association ← self literal: literalCount-1
ofMethod: methodPointer.
↑memory fetchPointer: ValueIndex
ofObject: association

An example of a CompiledMethod whose literal frame contained a
method class was given in the last chapter. The CompiledMethod for the
intersect: message to ShadedRectangle was shown in the section of the
last chapter called Messages.
<figure><img src="image_288.png" /></figure>

A BlockContext represents a block encountered in a CompiledMethod. A BlockContext refers to the MethodContext whose CompiledMethod contained the block it represents. This is called the BlockContext's *home*. Figure 27.6 shows a BlockContext and its home.

The indices used to access the fields of contexts are initialized by the following routine.

**initializeContextIndices**

```
"Class MethodContext"
SenderIndex ← 0.
InstructionPointerIndex ← 1.
StackPointerIndex ← 2.
MethodIndex ← 3.
ReceiverIndex ← 5.
TempFrameStart ← 6.
"Class BlockContext"
CallerIndex ← 0.
BlockArgumentCountIndex ← 3.
InitialPIndex ← 4.
HomeIndex ← 5
```

Both kinds of context have six fixed fields corresponding to six named instance variables. These fixed fields are followed by some indexable fields. The indexable fields are used to store the temporary frame (arguments and temporary variables) followed by the contents of the evaluation stack. The following routines are used to fetch and store the instruction pointer and stack pointer stored in a context.
<figure><img src="image_289.png" /><figcaption>Figure 27.6</figcaption></figure>

**instructionPointerOfContext: contextPointer**

↑self fetchInteger: InstructionPointerIndex

ofObject: contextPointer

**storeInstructionPointerValue: value inContext: contextPointer**

self storeInteger: InstructionPointerIndex

ofObject: contextPointer

withValue: value

**stackPointerOfContext: contextPointer**

↑self fetchInteger: StackPointerIndex

ofObject: contextPointer
**storeStackPointerValue: value inContext: contextPointer**

self storeInteger: StackPointerIndex
ofObject: contextPointer
withValue: value

A BlockContext stores the number of block arguments it expects in one of its fields.

**argumentCountOfBlock: blockPointer**

1self fetchInteger: BlockArgumentCountIndex
ofObject: blockPointer

The context that represents the CompiledMethod or block currently being executed is called the *active context*. The interpreter caches in its registers the contents of the parts of the active context it uses most often. These registers are:

**Context-related Registers of the Interpreter**

<table><tr><td>activeContext</td><td>This is the active context itself. It is either a MethodContext or a BlockContext.</td></tr><tr><td>homeContext</td><td>If the active context is a MethodContext, the home context is the same context. If the active context is a BlockContext, the home context is the contents of the home field of the active context. This will always be a MethodContext.</td></tr><tr><td>method</td><td>This is the CompiledMethod that contains the bytecodes the interpreter is executing.</td></tr><tr><td>receiver</td><td>This is the object that received the message that invoked the home context's method.</td></tr><tr><td>instructionPointer</td><td>This is the byte index of the next bytecode of the method to be executed.</td></tr><tr><td>stackPointer</td><td>This is the index of the field of the active context containing the top of the stack.</td></tr></table>

Whenever the active context changes (when a new CompiledMethod is invoked, when a CompiledMethod returns or when a process switch occurs), all of these registers must be updated using the following routine.

**fetchContextRegisters**

(self isBlockContext: activeContext)
    ifTrue: [homeContext ← memory fetchPointer: HomeIndex
             ofObject: activeContext]
    ifFalse: [homeContext ← activeContext].
receiver ← memory fetchPointer: ReceiverIndex
             ofObject: homeContext.
method ← memory fetchPointer: MethodIndex
             ofObject: homeContext.
instructionPointer ← (self instructionPointerOfContext: activeContext) - 1.
stackPointer ←
    (self stackPointerOfContext: activeContext) + TempFrameStart - 1
Note that the receiver and method are fetched from the homeContext and the instructionPointer and stackPointer are fetched from the activeContext. The interpreter tells the difference between MethodContexts and BlockContexts based on the fact that MethodContexts store the method pointer (an object pointer) and BlockContexts store the number of block arguments (an integer pointer) in the same field. If this location contains an integer pointer, the context is a BlockContext; otherwise, it is a MethodContext. The distinction could be made on the basis of the class of the context, but special provision would have to be made for subclasses of MethodContext and BlockContext.

**isBlockContext: contextPointer**

| methodOrArguments |
methodOrArguments ← memory fetchPointer: MethodIndex
ofObject: contextPointer.
↑memory isIntegerObject: methodOrArguments

Before a new context becomes the active context, the values of the instruction pointer and stack pointer must be stored into the active context with the following routine.

**storeContextRegisters**

self storeInstructionPointerValue: instructionPointer + 1
inContext: activeContext.
self storeStackPointerValue: stackPointer - TempFrameStart + 1
inContext: activeContext

The values of the other cached registers do not change so they do not need to be stored back into the context. The instruction pointer stored in a context is a one-relative index to the method's fields because subscripting in Smalltalk (i.e., the `at:` message) takes one-relative indices. The memory, however, uses zero-relative indices; so the `fetchContextRegisters` routine subtracts one to convert it to a memory index and the `storeContextRegisters` routine adds the one back in. The stack pointer stored in a context tells how far the top of the evaluation stack is beyond the fixed fields of the context (i.e., how far after the start of the temporary frame) because subscripting in Smalltalk takes fixed fields into account and fetches from the indexable fields after them. The memory, however, wants an index relative to the start of the object; so the `fetchContextRegisters` routine adds in the offset of the start of the temporary frame (a constant) and the `storeContextRegisters` routine subtracts the offset.

The following routines perform various operations on the stack of the active context.
**push: object**

stackPointer ← stackPointer + 1.
memory storePointer: stackPointer
  ofObject: activeContext
  withValue: object

**popStack**

| stackTop |
stackTop ← memory fetchPointer: stackPointer
  ofObject: activeContext.
stackPointer ← stackPointer - 1.
↑stackTop

**stackTop**

↑memory fetchPointer: stackPointer
  ofObject: activeContext

**stackValue: offset**

↑memory fetchPointer: stackPointer-offset
  ofObject: activeContext

**pop: number**

stackPointer ← stackPointer - number

**unPop: number**

stackPointer ← stackPointer + number

The active context register must count as a reference to the part of the object memory that deallocates unreferenced objects. If the object memory maintains dynamic reference counts, the routine to change active contexts must perform the appropriate reference counting.

**newActiveContext: aContext**

self storeContextRegisters.
memory decreaseReferencesTo: activeContext.
activeContext ← aContext.
memory increaseReferencesTo: activeContext.
self fetchContextRegisters

The following routines fetch fields of contexts needed by the interpreter infrequently enough that they are not cached in registers. The sender is the context to be returned to when a CompiledMethod returns a value (either because of a "↑" or at the end of the method). Since an explicit return from within a block should return from the CompiledMethod enclosing the block, the sender is fetched from the home context.

**sender**

↑memory fetchPointer: SenderIndex
  ofObject: homeContext

The caller is the context to be returned to when a BlockContext returns a value (at the end of the block).
**caller**

↑memory fetchPointer: SenderIndex

ofObject: activeContext

Since temporaries referenced in a block are the same as those referenced in the CompiledMethod enclosing the block, the temporaries are fetched from the home context.

**temporary: offset**

↑memory fetchPointer: offset + TempFrameStart

ofObject: homeContext

The following routine provides convenient access to the literals of the
currently executing CompiledMethod.

**literal: offset**

↑self literal: offset

ofMethod: method

The interpreter finds the appropriate CompiledMethod to execute in re-
sponse to a message by searching a *message dictionary*. The message
dictionary is found in the *class* of the message receiver or one of the
*superclasses* of that class. The structure of a class and its associated
message dictionary is shown in Figure 27.7. In addition to the message
dictionary and superclass the interpreter uses the class's *instance speci-
fication* to determine its instances' memory requirements. The other
fields of a class are used only by Smalltalk methods and ignored by the
interpreter. The following routine initializes the indices used to access
fields of classes and their message dictionaries.

<figure><img src="image_290.png" /><figcaption>Figure 27.7</figcaption></figure>
initializeClassIndices

"Class Class"
SuperclassIndex → 0.
MessageDictionaryIndex → 1.
InstanceSpecificationIndex → 2.
"Fields of a message dictionary"
MethodArrayIndex → 1.
SelectorStart → 2

The interpreter uses several registers to cache the state of the message lookup process.

Class-related Registers of the Interpreter

<table><tr><td>messageSelector</td><td>This is the selector of the message being sent. It is always a Symbol.</td></tr><tr><td>argumentCount</td><td>This is the number of arguments in the message currently being sent. It indicates where the message receiver can be found on the stack since it is below the arguments.</td></tr><tr><td>newMethod</td><td>This is the method associated with the messageSelector.</td></tr><tr><td>primitiveIndex</td><td>This is the index of a primitive routine associated with newMethod if one exists.</td></tr></table>

A message dictionary is an IdentityDictionary. IdentityDictionary is a subclass of Set with an additional Array containing values associated with the contents of the Set. The message selectors are stored in the indexed instance variables inherited from Set. The CompiledMethods are stored in an Array added by IdentityDictionary. A CompiledMethod has the same index in that Array that its selector has in the indexable variables of the dictionary object itself. The index at which to store the selector and CompiledMethod are computed by a hash function.

The selectors are instances of Symbol, so they may be tested for equality by testing their object pointers for equality. Since the object pointers of Symbols determine equality, the hash function may be a function of the object pointer. Since object pointers are allocated quasi-randomly, the object pointer itself is a reasonable hash function. The pointer shifted right one bit will produce a better hash function, since all object pointers other than SmallIntegers are even.

hash: objectPointer

1objectPointer bitShift: -1

The message selector lookup assumes that methods have been put into the dictionary using the same hashing function. The hashing algorithm reduces the original hash function modulo the number of indexable locations in the dictionary. This gives an index in the dictionary. To make the computation of the modulo reduction simple, message diction-
aries have an exact power of two fields. Therefore the modulo calculation can be performed by masking off an appropriate number of bits. If the selector is not found at the initial hash location, successive fields are examined until the selector is found or a `nil` is encountered. If a `nil` is encountered in the search, the selector is not in the dictionary. If the end of the dictionary is encountered while searching, the search wraps around and continues with the first field.

The following routine looks in a dictionary for a CompiledMethod associated with the Symbol in the `messageSelector` register. If it finds the Symbol, it stores the associated `CompiledMethod`'s pointer into the `newMethod` register, its primitive index into the `primitiveIndex` register and returns true. If the Symbol is not found in the dictionary, the routine returns false. Since finding a `nil` or an appropriate Symbol are the only exit conditions of the loop, the routine must check for a full dictionary (i.e., no `nils`). It does this by keeping track of whether it has wrapped around. If the search wraps around twice, the selector is not in the dictionary.

**lookupMethodInDictionary: dictionary**

| length index mask wrapAround nextSelector methodArray |
| :-------------------------------------------------------- |
| length ← memory fetchWordLengthOf: dictionary. |
| mask ← length-SelectorStart-1. |
| index ← (mask bitAnd: (self hash: messageSelector)) + SelectorStart. |
| wrapAround ← false. |
| [true] whileTrue: |
| > [nextSelector ← memory fetchPointer: index ofObject: dictionary. |
| > nextSelector= NilPointer ifTrue: [↑false]. |
| > nextSelector= messageSelector |
| > ifTrue: [methodArray ← memory fetchPointer: MethodArrayIndex ofObject: dictionary. |
| > newMethod ← memory fetchPointer: index-SelectorStart ofObject: methodArray. |
| > primitiveIndex ← self primitiveIndexOf: newMethod. |
| > [true]. |
| index ← index + 1. |
| index = length |
| ifTrue: [wrapAround ifTrue: [↑false]. |
| wrapAround ← true. |
| index ← SelectorStart]]

This routine is used in the following routine to find the method a class associates with a selector. If the selector is not found in the initial class's dictionary, it is looked up in the next class on the superclass chain. The search continues up the superclass chain until a method is found or the superclass chain is exhausted.
**lookupMethodInClass: class**

| currentClass dictionary |
*currentClass ← class.

(currentClass~ NilPointer) whileTrue:
    [dictionary ← memory fetchPointer: MessageDictionaryIndex
        ofObject: currentClass.
        (self lookupMethodInDictionary: dictionary)
        ifTrue: [↑true].
        currentClass ← self superclassOf: currentClass].
messageSelector = DoesNotUnderstandSelector
    ifTrue: [self error: 'Recursive not understood error encountered'].
self createActualMessage.
messageSelector ← DoesNotUnderstandSelector.
↑self lookupMethodInClass: class

**superclassOf: classPointer**

↑memory fetchPointer: SuperclassIndex
ofObject: classPointer

The interpreter needs to do something out of the ordinary when a message is sent to an object whose class and superclasses do not contain a CompiledMethod associated with the message selector. In keeping with the philosophy of Smalltalk, the interpreter sends a message. A CompiledMethod for this message is guaranteed to be found. The interpreter packages up the original message in an instance of class Message and then looks for a CompiledMethod associated with the selector doesNotUnderstand: The Message becomes the single argument for the doesNotUnderstand: message. The doesNotUnderstand: message is defined in Object with a CompiledMethod that notifies the user. This CompiledMethod can be overridden in a user-defined class to do something else. Because of this, the lookupMethodInClass: routine will always complete by storing a pointer to a CompiledMethod in the newMethod register.

**createActualMessage**

| argumentArray message |
*argumentArray ← memory instantiateClass: ClassArrayPointer
  withPointers: argumentCount.
message ← memory instantiateClass: ClassMessagePointer
  withPointers: self messageSize.
memory storePointer: MessageSelectorIndex
  ofObject: message
  withValue: messageSelector.
memory storePointer: MessageArgumentsIndex
  ofObject: message
  withValue: argumentArray.
self transfer: argumentCount
fromField: stackPointer - (argumentCount - 1)
ofObject: activeContext
toField: 0
ofObject: argumentArray.
self pop: argumentCount.
self push: message.
argumentCount ← 1

The following routine initializes the indices used to access fields of a
Message.

initializeMessageIndices

MessageSelectorIndex ← 0.
MessageArgumentsIndex ← 1.
MessageSize ← 2

The instance specification field of a class contains a SmallInteger pointer
that encodes the following four pieces of information:

1. Whether the instances' fields contain object pointers or numerical values

2. Whether the instances' fields are addressed in word or byte quantities

3. Whether the instances have indexable fields beyond their fixed fields

4. The number of fixed fields the instances have

Figure 27.8 shows how this information is encoded in the instance spec-
ification.

<figure><img src="image_291.png" /></figure>

The four pieces of information are not independent. If the instances'
fields contain object pointers, they will be addressed in word quantities.
If the instances' fields contain numerical values, they will have
indexable fields and no fixed fields.

instanceSpecificationOf: classPointer

↑memory fetchPointer: InstanceSpecificationIndex
ofObject: classPointer
**isPointers: classPointer**

| pointersFlag |
pointersFlag ← self extractBits: 0 to: 0
of: (self instanceSpecificationOf: classPointer).
↑pointersFlag = 1

**isWords: classPointer**

| wordsFlag |
wordsFlag ← self extractBits: 1 to: 1
of: (self instanceSpecificationOf: classPointer).
↑wordsFlag = 1

**isIndexable: classPointer**

| indexableFlag |
indexableFlag ← self extractBits: 2 to: 2
of: (self instanceSpecificationOf: classPointer).
↑indexableFlag = 1

**fixedFieldsOf: classPointer**

| self extractBits: 4 to: 14
of: (self instanceSpecificationOf: classPointer)

Note: the instance specification of CompiledMethod does not accurately reflect the structure of its instances since CompiledMethods are not homogeneous. The instance specification says that the instances do not contain pointers and are addressed by bytes. This is true of the bytecode section of a CompiledMethod only. The storage manager needs to know that CompiledMethods are special and actually contain some pointers. For all other classes, the instance specification is accurate.
28

# Formal Specification of the Interpreter

- Stack Bytecodes

- Jump Bytecodes

- Send Bytecodes

- Return Bytecodes

<figure><img src="image_292.png" /></figure>
The main loop of the Smalltalk-80 interpreter fetches bytecodes from a CompiledMethod sequentially and dispatches to routines that perform the operations the bytecodes indicate. The fetchByte routine fetches the byte indicated by the active context's instruction pointer and increments the instruction pointer.

**fetchByte**

| byte |
byte - memory fetchByte: instructionPointer
ofObject: method.
instructionPointer - instructionPointer + 1.
↑byte

Since process switches are only allowed between bytecodes, the first action in the interpreter's main loop is to call a routine that switches processes if necessary. The checkProcessSwitch routine will be described with the process scheduling primitive routines in the next chapter. After checking for a process switch, a bytecode is fetched (perhaps from a new process), and a dispatch is made to the appropriate routine.

**interpret**

[true] whileTrue: [self cycle]

**cycle**

self checkProcessSwitch.
currentBytecode - self fetchByte.
self dispatchOnThisBytecode

The table on page 595 lists the Smalltalk-80 bytecodes. The bytecodes are listed in ranges that have similar function. For example, the first range includes the bytecodes from 0 through 15 and its entry is shown below.

0-15 0000 iiii Push Receiver Variable # iiii

Each range of bytecodes is listed with a bit pattern and a comment about the function of the bytecodes. The bit pattern shows the binary representation of the bytecodes in the range. 0s and 1s are used in bit locations that have the same value for all bytecodes in the range. Since all numbers from 0 through 15 have four zeros in their high order bits, these bits are shown as 0000. Lower case letters are used in bit locations whose values vary within the range. The value of each letter can be either 0 or 1. The letters used in the pattern can be included in the comment to refer to the value of those bits in a specific bytecode in the range. The comment for the first range of bytecodes indicates that the low-order four bits of the bytecode specify the index of one of the receiver's variables to be pushed on the stack.

The variable bits in a bit pattern are also sometimes used as a zero-relative index into a list included in the comment. For example, the entry
120-123 011110ii Return (receiver, true, false, nil) [i] From Message

specifies that the bytecode 120 returns the receiver, bytecode 121 returns true, bytecode 122 returns false and bytecode 123 returns nil.

The entries for bytecodes that take extensions will include more than one bit pattern. For example,

131 10000011 Send Literal Selector #kkkk With jjj Arguments jjjkkkk

There are four basic types of bytecode.

* stack bytecodes move object pointers between the object memory and the active context's evaluation stack. These include both the push bytecodes and store bytecodes described in Chapter 26.

* jump bytecodes change the instruction pointer of the active context.

* send bytecodes invoke CompiledMethods or primitive routines.

* return bytecodes terminate the execution of CompiledMethods.

Not all of the bytecodes of one type are contiguous, so the main dispatch has seven branches each of which calls one of four routines (stackBytecode, jumpBytecode, sendBytecode, or returnBytecode). These four routines will be described in the next four subsections.

### dispatchOnThisBytecode

(currentBytecode between: 0 and: 119) ifTrue: [↑self stackBytecode].

(currentBytecode between: 120 and: 127) ifTrue: [↑self returnBytecode].

(currentBytecode between: 128 and: 130) ifTrue: [↑self stackBytecode].

(currentBytecode between: 131 and: 134) ifTrue: [↑self sendBytecode].

(currentBytecode between: 135 and: 137) ifTrue: [↑self stackBytecode].

(currentBytecode between: 144 and: 175) ifTrue: [↑self jumpBytecode].

(currentBytecode between: 176 and: 255) ifTrue: [↑self sendBytecode]

The bytecodes 176-191 refer to Arithmetic Messages. These are

+, -, <, >, <=, >=, =, ~=, *, /, \\, @, bitShift:, //, bitAnd:, bitOr:

The bytecodes 192-207 refer to Special Messages. These are

at:* , at:put:* , size* , next* , nextPut:* , atEnd* , == , class, blockCopy: , value, value: , do:* , new* , new:* , x* , y*

Selectors indicated with an asterisk (*) can be changed by compiler modification.