Implementation

This section shows how write the simulation described above. Program  declares the class Event which is used to keep track of the address of an area and the time at which it is to be freed. Therefore, there are two parts to an event, a VoidPtr and a Time.

  
Program: Event Class Definition

Since events will be put into a priority queue, the Event class is derived from the Association class which is defined in Section . An association is an ordered pair comprised of a key and a value. In the case of the Event class, the key is the time of the event and the value is address of the area to be free. The events in a priority queue are prioritized by their times.

The simulation program is embodied in the function StoragePoolTest defined in Program . This function takes two arguments, a reference to the storage pool to be tested and an integer which specifies the number of simulation cycles to execute.

  
Program: Simulation Procedure for Exercising a Storage Pool

The variables size and latency are UniformRVs. The class UniformRV is a random number generator defined in Section . This class provides a member function called Sample which is used to sample the random number generator. I.e., every time Sample is called, a different (random) result is returned. The random values are uniformly distributed on the interval which is specified in the constructor (lines 3-4).

The StoragePoolTest routine uses a LeftistHeap priority queue (see Section ) to keep track of scheduled events (line 5).

The body of the main loop directly implements the steps outlined above. First, any events scheduled for the current time step are withdrawn from the priority queue and the associated storage areas are released (lines 10-19).

Second, the random variable size is sampled to determine the size of area to allocate and the random variable latency is sampled to determine when the allocated area should be deleted. An area of the required size is acquired and an event is scheduled in priority queue that will cause the area to be freed after the appropriate amount of time as elapsed.

The StoragePoolTest function given in Program  was used by the author to create Figures , and . Figure  shows the condition of a SinglyLinkedPool after simulation cycles. Figure  shows the condition of a DoublyLinkedPool and Figure  shows the condition of a BuddyPool after exactly the same simulation cycles.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.