Previous Section
 < Free Open Study > 
Next Section


Case Study

Simulation

Problem Write a general-purpose simulation program that determines how long items (people, jobs, cars, ...) must wait in line before being served. The simulation must vary the number of servers and the time between arrivals of the items.

Discussion Before astronauts go up into space, they spend many hours in a spaceship simulator, a physical model of a space vehicle in which they can experience all the things that will happen to them in space. The spaceship simulator is a physical model of another object. A model can be thought of as a series of rules that describe the behavior of a real-world system. We change the rules and watch the effects of these changes on the behavior we are observing.

The technique that is used to make the model behave in the same way as the real object is called simulation. We can use similar techniques to build computer models of objects and events rather than physical models.

Let's look at a very useful type of simulation that uses queues as the basic data structure. In fact, the real-world system is called a queuing system. A queuing system consists of servers and queues of objects to be served. We deal with queuing systems frequently in our daily lives. When you stand in line to check out at the grocery store or to cash a check at the bank, you are dealing with a queuing system. When you submit a batch "job" (such as a compilation) on a mainframe computer, your job must wait in line until the CPU finishes the jobs scheduled ahead of it; the operating system is a queuing system. When you make a phone call to reserve an airline ticket and get a recording that says, "Thank you for calling Air Busters. Your call will be answered by the next available operator. Please wait."-you are dealing with a queuing system.

Please wait. Waiting is the critical element. The objective of a queuing system is to utilize the servers (the tellers, checkers, CPU, operators, and so on) as fully as possible, while keeping the wait time within a reasonable limit. These goals usually require a compromise between cost and customer satisfaction.

To put this situation on a personal level, start with this fact: No one likes to stand in line. If there were one checkout counter for each customer in a supermarket, the customers would be delighted. The supermarket, however, would not stay in business very long. Consequently, a compromise is made: The number of cashiers is kept within the limits set by the store's budget, and the average customer is not kept waiting too long.

How does a company determine the optimal compromise between the number of servers and the wait time? One way is by experience; the company tries out different numbers of servers and sees how things work out. This approach has two problems: It takes too long and it is too expensive. Another way of examining this problem is by using a computer simulation. To simulate a queuing system, we must know four things:

  1. The number of events and how they affect the system

  2. The number of servers

  3. The distribution of arrival times

  4. The expected service time

The simulation program uses these parameters to predict the average wait time. The interactions of these parameters constitute the rules of the model. By changing these parameters, we change the rules. The average wait times are then examined to identify a reasonable compromise.

Before we start designing a simulation program, let's walk through a simple simulation of a real-life example. Consider the case of a drive-in bank with one teller. How long does the average car have to wait? If business gets better and cars start to arrive more frequently, how would it affect the average wait time? When would the bank need to open a second drive-in window?

This problem has the characteristics of a queuing problem. We have a server (the teller) and objects being served (customers in cars), and we are interested in observing the average wait time.

The events in this system are the arrivals and the departures of customers. Suppose that the number of servers is 1, the average transaction takes 6 minutes, and a new customer arrives about every 5 minutes. Let's look at how we can solve this problem as a time-driven simulation. In a time-driven simulation, the program maintains a counter that represents a clock. To simulate the passing of a unit of time (a minute, for example), we increment the clock. We run the simulation for a predetermined amount of time-say, 100 minutes. (Of course, simulated time usually passes much more quickly than real time; 100 simulated minutes pass in a flash on the computer.)

From a software point of view, the simulation is a big loop that executes a set of rules for each value of the clock-from 1 to 100, in our example. Here are the rules that are processed in the loop body:

Rule 1.

If a customer arrives, he or she gets in line.

Rule 2.

If the teller is free and someone is waiting, the first customer in line leaves the line and advances to the teller's window. The service time is set to 6 minutes.

Rule 3.

If a customer is at the teller's window, the time remaining for that customer to be serviced is decremented.

Rule 4.

If there are customers in line, the additional minute that they have remained in the queue is recorded.

The output from the simulation is the average wait time. We calculate this value using the following formula:

Given this output, the bank can see whether its customers have an unreasonable wait in a one-teller system. If so, the bank can repeat the simulation with two tellers.

We have described this example in terms of a single teller and a specific arrival rate and transaction time. In fact, we should vary these simulation parameters to see how the changes affect the average wait time. These values are read as inputs to the program.

Because so many different applications might use this program-modeling bank queues, phone call-waiting systems, CPU "job queues," a doctor's office waiting room, and so on-we will write our program as a generic time-driven queuing system simulator. That is, the same program can be used to simulate many different real-world systems. We refer to the bank tellers, phone operators, and so on, as servers and the objects to be serviced (customers, patients, and so on) as jobs. This program simulates a multiple-server/single-queue system. That is, the jobs waiting to be served are stored in a single queue. (In contrast, grocery stores are usually multiple-server/multiple-queue systems.) Figure 4.15 lists the specifications of this program.

Start Figure

Specification: Program Simulation

Function The program simulates a queuing system, using the following simulation parameters: length of simulation, average time between arrivals, number of servers, and average transaction time.

Input The simulation parameters are entered interactively and include:

  1. The length of the simulation

  2. The average transaction time

  3. The number of servers

  4. The distribution of arrival times (average time between job arrivals)

The program must prompt the user for each input, and each input (a positive integer) is entered on a separate line.

At the end of each simulation, the program asks whether another simulation is desired. If the user responds positively, the program prompts the user to input a new set of simulation parameters.

Output The outputs are printed both to the screen and to a report file. The screen output is the resulting average wait time for the current simulation, properly labeled. Following the execution of the last simulation, the program prints the following message to the screen:

"Simulation is complete. Summary in file Report.sim."

The output in the file Report.sim consists of the set of simulation parameters, the resulting average wait time, and the number of jobs that are still waiting when the simulation ends. The output for each set of parameters should be printed on a single line, producing a tabular listing. A header line should be written to the file at the beginning of the program to label the columns, and a trailer section should be written to the end of the file to describe the meaning of the columns in the table.

Processing Requirements

  1. The program must include processing to guard against range errors in the user's inputs. The maximum values allowed for each parameter must be described as constants, so that they can be "tuned" if necessary. Use the following initial values:

    Maximum servers

    10

    Maximum simulation length

    10000

    Maximum transaction length

    1000

    Maximum time between arrivals

    1000

    Maximum size of the queue

    100

  2. Real-number output should be specified to two decimal places.

  3. If a job arrives when the queue is full, the simulation should abort and send an error message to both the screen and the report file.

Assumptions

  1. No more than one job arrives per time unit.

  2. User inputs can be assumed to be numeric.

End Figure

Figure 4.15: Specification for simulation program

Object-Oriented Design In a computer simulation, each physical object in the real-world system can be represented as a class object. Actions in the real world are represented as functions that manipulate the data members of these objects. In Chapter 2, we noted that object-oriented design is ideal for simulation problems. An object-oriented design begins by looking for potential objects in the problem specification.

Brainstorming, Filtering, and Scenarios

From our discussion of simulation, we know that there must be three objects: jobs, servers, and waiting lines.

Which characteristics of a job must be recorded? That is, which data members are associated with job objects? We are interested in the average time that a job spends waiting to be served, so a job must have a timer that records the number of time units it waits. What operations must be performed on the job object? We must initialize the timer when a job arrives, and increment the timer for each clock cycle that the job remains in the queue. If each job had a different transaction time, we would have to record it as part of the job object. In this simulation, however, all jobs have the same transaction time. Thus the only information associated with a job is the time it waits in line.

What about a server? A server can be free or busy, so we need a data member that keeps track of whether the server is free or busy. The server must be able to change and report its status. We also need to determine when the job being served is completed. Therefore, we need a timer associated with each server that is set to the transaction time when a job arrives and is decremented at each clock cycle. When this timer reaches zero, the job has been completed and the server is free.

A review of the last two paragraphs reveals an object that is more fundamental than either a job or a server: Both objects need a timer object. The job object needs to initialize the timer to zero and increment it; the server object needs to initialize the timer to a nonzero value and decrement it. Here are the CRC cards for our three fundamental objects.

Click To expand
Click To expand
Click To expand
class TimerType
{
public:
  TimerType();      // Class constructor.
  // Sets count to zero.
  void SetTimer(int value);
  // Sets count to value.
  void Increment();
  // Increments count.
  void Decrement();
  // Decrements count.
  int TimeIs() const;
  // Returns count.
private:
  int count;
};

class JobType
{
public:
  JobType(); // Class constructor
  void IncrementWaitTime();
  int WaitTimeIs();
  // Returns the value of waitTime.
private:
  TimerType waitTime;
};
enum StatusType {BUSY, FREE};
class ServerType
{
public:
  ServerType();     // Class constructor.
  // Initializes status to FREE.
  bool IsFree() const;
  // Returns true if status is FREE; false otherwise.
  void SetBusy();
  // Sets status to BUSY.
  void DecrementTimeRemaining();7
  // Decrements TimeRemaining.
  void SetTimeRemaining(int time);
  // Sets timeRemaining to time.
private:
  StatusType status;
  TimerType timeRemaining;
};

Now, we need to look back at the specification and identify other objects-the objects that contain our servers and jobs.

Container Objects

From the abstract perspective, we have a list of servers. Can we use either our Unsorted List ADT or our Sorted List ADT to hold the servers? Let's look at the operations that must be performed on the list of servers to answer this question. Reviewing the rules to be processed in the loop body, we see that we need an operation to determine whether a server is free and one to engage a free server, thereby changing its status flag (Rule 2). We also need an operation to decrement the timers of the busy servers. Both List ADTs allow us to iterate through the list items, but not to change them. Decrementing the timers and changing the status flags require access to the server objects themselves, not just to copies of the objects. We can make the items on the list pointers to our server objects, thereby gaining access to the objects themselves, or we can write a problem-dependent list ourselves. Let's write a specialized ServerList ADT.

Let's call the operation to engage a server EngageServer. How do we know which, if any, server is free? We need another operation GetFreeServerId to tell us which server is available or to indicate that no server is free. Finally, we need an operation to decrement the timers of all active servers to indicate that a clock unit has passed (Rule 3). We call this operation UpdateServers. The ADT can be described with the following specification:

At the abstract level, the jobs waiting in line to be processed can be described as a queue of jobs. Let's see whether we can use the Queue ADT discussed in this chapter. Rule 1 tells us that if a job arrives, it should be put in line; this is the Enqueue operation. Rule 2 suggests two queue operations: We need to know if a job is waiting in line (the IsEmpty operation), and we need to be able to remove the first job from the queue (the Dequeue operation). Finally, Rule 4 says that we must increment the wait timers of all jobs still in line to show the passing of a clock unit. This operation is not supported by the Queue ADT developed in this chapter, but we can certainly implement it using operations that are supported. Here is the specification for the client function UpdateQue:

With the addition of UpdateQueue, we can use the Queue ADT discussed in this chapter. Just to prove how committed we are to the idea of data encapsulation, we will not discuss the implementation of the ServerList ADT and UpdateQue until we finish designing the driver program for the simulation. We believe that the information in the specification tells us enough that we can use these modules without knowing anything more. In fact, we give these modules to another programmer to implement however she wishes, and we write the rest of our program without having the implementations in hand. When we finish our design, we get the implementations of these modules from our friend.

Driver Design Now we're ready to design the driver program, the code that allows these objects to interact. The specification tells us that the program must continue to run simulations and print results with different sets of parameters until the user is ready to quit. This requirement suggests a loop, each iteration of which invokes the ExecuteSimulation function. Before we can process the first simulation, we must do some initialization work-opening the report file and writing the report header. After we finish the last simulation, we must do some termination processing-writing the report trailer, for example. Here is the top level of the driver design:

Driver

Open reportFile for writing
Write title and headings to reportFile
do
    ExecuteSimulation
    Write to screen "Enter an S to stop or another letter to continue; press return."
    Read letter
    Set finished to (letter = "S" or "s")
while NOT finished
Write trailer to reportFile

The main work of the program occurs in ExecuteSimulation. It must get the simulation parameters, run the simulation, and print the result to the screen and to the report file. Here is the design for this important module:

ExecuteSimulation

GetParameters (timeLimit, numServers, transactionTime, timeBetween)
Initialize simulation variables
while more time to run
    UpdateClock
    UpdateServers
    UpdateQue
    if JobArrives()
         waitQue.Enqueue(job)
    servers.GetFreeServerId(serverId, found)
    if (found AND !waitQue.IsEmpty())
         StartJob
Clean up wait queue
Calculate average wait time
PrintResults

This design gives an overall view of a simulation but leaves many questions unanswered. Clearly, more levels of the design are needed.

The GetParameters function gets all the parameters for this execution of the simulation. Because it returns so many different values, we decide to make it send back a single parameter, a struct that contains a data member for each simulation parameter.

struct ParametersType
{
   int timeLimit;
   int numServers;
   int transactionTime;
   int timeBetween;
};

GetParameters must prompt the user for each parameter value, read the response, check the response to make sure that it falls within the bounds listed in the program specifications, and-if the response is not valid-ask for another value. Clearly, this is a lot of work, and we do not want to become distracted right now. We really want to focus on the main processing of this program, the execution of the simulation using these parameters, so we decide to postpone the design and coding of this module until we've had a chance to test the simulation processing. But this module returns the simulation parameters. How can we postpone coding it? We code a stub to stand in its place. The stub simply assigns sample simulation parameters to the struct.

void GetParameters(ParametersType& parameters)
// Stub used for testing; sets simulation parameters.
{
  parameters.timeLimit = 100;
  parameters.transactionTime = 5;
  parameters.numServers = 2;
  parameters.timeBetween = 3;
}

We use this stub until we're convinced that our main simulation processing works; then we come back and code this module to get real values from the user. In this way, we code and test our program incrementally.

Our next job is to initialize the simulation variables. What are these variables? As we saw in reference to the bank-teller example, we must keep track of two values: (1) the total wait time for all jobs and (2) the number of jobs served. These values are used to calculate the average wait time. The last variable to initialize is the clock.

InitializeSimulationVariables

Set totalWait to 0
Set numJobs to 0
Set clock to 0

Now we come to activities in the while loop in ExecuteSimulation. Updating the clock means incrementing clock; UpdateServers and UpdateQue have already been specified and can be coded directly from the specifications. Our next activity inside the loop is to determine whether a new job has arrived. How do we know whether a job has arrived in this particular clock unit? The answer reflects two factors: the simulation parameter timeBetween (the average time between job arrivals) and luck.

Luck? We're writing a computer program that bases calculations on sheer luck? Well, not exactly. Let's express timeBetween another way-as the probability that a job arrives in any given clock unit. Probabilities range from 0.0 (no chance) to 1.0 (a sure thing). If on the average a new job arrives every five minutes, then the chance of a customer arriving in any given minute is 0.2 (1 chance in 5). Therefore, the probability of a new job arriving in this iteration of the loop body is 1.0 divided by timeBetween. Let's call this value arrivalProb. Now what about luck? In computer terms, luck can be represented via use of a random-number generator. We simulate the arrival of a customer by writing a function JobArrives, which generates a random number between 0.0 and 1.0 and applies the following rules:

  1. If the random number is between 0.0 and arrivalProb (inclusive), a job has arrived and JobArrives returns true.

  2. If the random number is greater than arrivalProb, no job arrived in this clock unit and JobArrives returns false.

Where do we get a random-number generator? You can find the formula in a statistics book and code it yourself. However, there is an even easier way. C++ compilers provide a random-number generator in the standard library-the rand function.

#include <cstdlib>
  
randomInt = rand();

rand returns a random integer in the range of 0 through RAND_MAX, a constant defined in <cstdlib>. (RAND_MAX is typically the same as INT_MAX.) To convert this number to a value between 0.0 and 1.0, cast it to a floating-point number and divide it by float (RAND_MAX):

float(rand())/float(RAND_MAX)

bool JobArrives

Set value to float (rand() )/ float(RAND_MAX)
return (value <= arrivalProb)

Finally, we come to the last activity in the ExecuteSimulation loop body: If a server is free and a job is waiting, start a job. What parameters does StartJob need? To engage the server, it must have the list of servers, the index of the free server, and the transaction time (from parameters). If a job starts, two other variables are changed: the number of jobs served (numJobs) and the total wait time of jobs served (totalWait).

StartJob(servers, waitQue, serverId, parameters, numJobs, totalWait)

waitQue.Dequeue(job)
Increment numJobs
Set totalWait to totalWait + job.WaitTimels()
servers.EngageServer(serverId, parameters.transactionTime)

When the loop terminates (after the clock hits the timeLimit), this version of the simulation is finished. Now we need to clean up the wait queue, calculate the average wait time, and print out the results.

CleanUp(waitQue, jobsLeftInQue)

Set jobsLeftInQue to 0
while NOT waitQue.IsEmpty()
    waitQue.Dequeue(job)
    Increment jobsLeftInQue

Finally, we are ready to calculate the average wait time-the information that we have been waiting for:

Set averageWait to totalWait / numJobs

What happens if no jobs were ever received? If the simulation was run for a short timeLimit with a relatively large timeBetween parameter, numJobs might be zero. Division by zero causes the program to crash at run time, so it is better to check for this condition explicitly:

if numJobs > 0
    Set averageWait to totalWait / numJobs
else
    Set averageWait to 0

All that is left in the ExecuteSimulation design is to print the results. We can generate the output that must be printed to the screen with a simple output statement. Printing the reportFile output, however, requires us to know how the columns in the table were set up. It reminds us that there are two other file output operations-one to print the report "header" (the title and column headings) and one to print the report "trailer" (text describing the meaning of the columns).

The work required to print the output with the title centered and the columns straight is not important to developing and testing the simulator. Like GetParameters, these print operations can be coded in the second development iteration. Our final program needs these operations, of course, but we don't need them now. Straight tabular output is irrelevant to testing whether the simulation works. As a consequence, we put the coding of these three operations on hold, and replace them for now with stubs:

void PrintResults(std::ofstream& reportFile,
  ParametersType parameters, float averageWait,
  int jobsLeftInQue)
{
  reportFile  << "Average wait time is "  << averageWait << std::end1;
}

void PrintReportHeader(std::ofstream& reportFile)
{
  reportFile  << "Starting Simulation"  << std::end1;
}

void PrintReportTrailer(std::ofstream& reportFile)
{
  reportFile  << "Ending Simulation"  << std::end1;
}

This step completes the design of the driver for our simulation (except for the input/output functions that we are postponing to the second development iteration).

As promised earlier, we developed the design for the driver of this program without ever knowing how the ServerList ADT and the UpdateQue function were implemented. Meanwhile, our friend has been busy developing these modules for us. Let's see what she came up with.

The Server ADT The list of servers is represented as a class with two data members: the number of servers (numServers) and an array of ServerType items. Recall that ServerType objects have a data member timeRemaining of type TimerType that indicates how much time is left on the current job and a data member status that contains either BUSY or FREE. Here is the definition for the class ServerList:

class ServerList
{
public:
  ServerList();     // Class constructor
  ~ServerList();    // Class destructor
  void GetFreeServerId(int& serverID, bool& found);
  void EngageServer(int serverId, int transactionTime);
  void UpdateServers();
  ServerList(int number);
private:
  int numServers;
  ServerType* servers;
);

The InitServers operation is implemented as the class constructor for the class ServerList. It sets numServers to the input parameter number and uses the new operator to allocate the array of servers. GetFreeServerId searches the array of timers for one that is free. If one is free, found is set to true and serverID is set to the index of its array slot; otherwise, found is false. EngageServer is the simplest of all: It merely sets the server's timer to transactionTime and its status to BUSY. Finally, the UpdateServers operation loops through the servers, decrementing the timers of the active servers and changing a server's status if the timer is zero.

We have only one client function, UpdateQue, left to discuss. We need to cycle through the queue incrementing the timer for each job object. Because we do not have access to the items on the queue, we must dequeue one job at a time, increment the timer, and put the job back into the queue. How do we know that we have processed each job in the queue? Let's enqueue an extra dummy job with the timer set to a negative number. When this job is dequeued, we have incremented all timers in the queue.

The design is now finished. The completion of the program is left to you as a programming assignment.

Simulation Results We ran our version of the program, letting it execute four simulations. The average wait times printed to the screen are 3.21, 0.88, 7.03, and 0.52. How can that be? The program inputs are currently coming from the GetParameters stub, not from the tester. Each time ExecuteSimulation calls GetParameters, it returns the same parameters. So how can the simulation produce different results for each simulation? The random-number generator supplies a little "luck," just as in real life, a bank teller might be really busy one Thursday morning and bored the next.

Let's try using a bigger time limit. We change the timeLimit member in the GetParameters stub to 1,000 clock units, recompile, and run the program again. This time, the four executions of the simulation yield much more similar results: 2.01, 2.92, 2.27, and 4.40.

We start the program again, and let it run four more executions of the simulation with the same time limit. This time we get exactly the same results as the previous run! How can that be? Aren't the random numbers supposed to be random? Much theoretical work has gone into the development of algorithms to produce random numbers. Given a particular function to produce random numbers and the current result of the function, however, the next value is completely predictable-not random at all! Random-number generators use an initial seed value from which to start the sequence of random numbers. Because the function rand initializes this seed to the same value each time, each run of the program produces the same sequence of "random" numbers. Therefore the numbers from such a function are really pseudo-random. For simulation purposes, however, pseudo-random numbers are sufficient. If a simulation is run for a long enough period of time, the theory of random numbers says that the wait times converge no matter what kind of random-number generator you use. As we saw, with a larger timeLimit value, the results were more alike. Note that the C++ standard library does provide a function srand, which allows the user to specify an initial seed before the first call to rand. The prototype for srand is

void srand(unsigned int);

How do we know whether the program is working? The results seem more or less "reasonable," but how do we know they are correct? A good way to see what the program is doing is to trace its execution using debugging outputs. That is, we add output lines throughout the program-when we enqueue and dequeue, when we engage a server, and so on. Then we walk through the debug output, comparing what the program is doing to what we expect it to do.

Another way to test this program is to run it with different values of input parameters and to see whether the results change in predictable ways. To perform such a test, however, we need to code the real GetParameters routine.

Table 4.1 shows the output from the file Report.sim for a sample test of the program. (Blank lines have been deleted between some output lines to enhance readability.) We want to answer our original question about the drive-in bank. Is one teller enough? The test demonstrates cases where the transaction time is five minutes, new jobs arrive every three minutes, and the number of servers varies from one to four. We have run each set of parameters for 100, 500, 1,000, and 5,000 clock units (minutes in this case), respectively.

Table 4.1: Output from one run of simulation program

Simulation

Simulation Length

Number of Servers

Average Transaction

Time Between Arrivals

Average Wait

Jobs Left

100

1

5

3

18.0

14

500

1

5

3

106.65

58

1000

1

5

3

202.55

132

5000

1

5

3

1042.11

686

100

2

5

3

2.19

3

500

2

5

3

1.41

1

1000

2

5

3

3.89

0

5000

2

5

3

2.99

2

100

3

5

3

0.09

0

500

3

5

3

0.28

0

1000

3

5

3

0.28

1

5000

3

5

3

0.22

0

100

4

5

3

0.00

0

500

4

5

3

0.03

0

1000

4

5

3

0.01

0

5000

4

5

3

0.01

0

All times are expressed in clock units. Average wait time reflects the wait time of jobs served; it does not reflect the wait time of jobs that were not yet served. Jobs Left reflects the number of jobs that were waiting to be served when the simulation time limit was reached.

When testing most programs, we will have a test plan in which we calculate and record what the results should be with certain input data values. We run the test data and check the actual results against the predicted results. As you can see, testing programs involving a random-number generator is a much more complex endeavor because the results are not easily predicted.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)