Hi guys,i read it and didnt understand that much,im study C++ right now so if u could somehow help me would appreciate that so much. With some explanatory notes would be great!!

APPLICATION OFQUEUES: SIMULATION 3.5.1 Introduction Simulation is the use of one system to imitate the behavior of another system. simulation Simulations are often used when it would be too expensive or dangerous to exper- iment with the real system. There are physical simulations, such as wind tunnels used to experiment with designs for car bodies and flight simulators used to train airline pilots. Mathematical simulations are systems of equations used to describe some system, and computer simulations use the steps of a program to imitate the behavior of the system under study. In a computer simulation, the objects being studied are usually represented as data, often as data structures given by classes whose members describe the computer simulation properties of the objects. Actions being studied are represented as methods of the classes, and the rules describing these actions are translated into computer algorithms. By changing the values of the data or by modifying these algorithms, we can observe the changes in the computer simulation, and then we can draw worthwhile inferences concerning the behavior of the actual system. While one object in a system is involved in some action, other objects and actions will often need to be kept waiting. Hence queues are important data struc- tures for use in computer simulations. We shall study one of the most common and useful kinds of computer simulations, one that concentrates on queues as its basic data structure. These simulations imitate the behavior of systems (often, in fact, called queueing systems ) in which there are queues of objects waiting to be served by various processes. 3.5.2 Simulation of an Airport Asa specificexample,let usconsider a smallbut busy airport with only onerunway (see Figure 3.5). In each unit of time, one plane can land or one plane can take off, but not both. Planes arrive ready to land or to take off at random times, so at any given moment oftime, the runway may be idle or a plane may be landing or taking off, and there may be several planes waiting either to land or take off. In simulating the airport, it will be useful to create a class Plane whose objects represent individualplanes. This class willdefinitely need an initialization method class Plane and methods to represent takeoff and landing. Moreover, when we write the main program for thesimulation,theneed for other Plane methodswillbecomeapparent. We will also use a class Runway to hold information about the state and operation of the runway. This class will maintain members representing queues of planes waiting to land and take off. We shall need one other class in our simulation, a class Random to encapsulate class Random the random nature of plane arrivals and departures from the runway. We shall discuss this class in more detail in Section 3.5.3. In our main program, we use a single method, called poisson , from the class Random . This method uses a floating- 67 point parameter (representing an average outcome)and it returns an integer value. Although the returned value is random, it has the property that over the course of many repeated method calls, the average of the returned values will match our specified parameter. In our simulation, we shall be especially concerned with the amounts of time that planes need to wait in queues before taking off or landing. Therefore, the measurement oftime willbe ofutmost importance to our program. We shalldivide the time period of our simulation into units in such a way that just one plane can use the runway, either to land or take off, in any given unit of time. The precise details of how we handle the landing and takeoff queues will be dealt with when we program the Runway class. Similarly, the precise methods describing the operation of a Plane are not needed by our main program. 68 int main() // Airport simulation program / * Pre: The user must supply the number of time intervalsthe simulation isto run, the expected number of planes arriving, the expected number of planes departing per time interval, and the maximum allowed size for runway queues. Post: The program performs a random simulation of the airport, showing the status of the runway at each time interval, and prints out a summary of airport operation at the conclusion. Uses: ClassesRunway, Plane, Random and functionsrun_idle, initialize. * /

{ int end_time ; // time to run simulation int queue_limit ; // size of Runway queues int flight_number = 0 ; double arrival_rate , departure_rate ; initialize(end_time , queue_limit , arrival_rate , departure_rate) ; Random variable ; Runway small_airport(queue_limit) ; for ( int current_time = 0 ; current_time

3.5.3 Random Numbers

A key step in our simulation is to decide, at each time unit, how many new planes

become ready to land or take off. Although there are many ways in which these

decisions can be made, one of the most interesting and useful is to make a random

decision. When the program is run repeatedly with random decisions, the results

willdiffer from run to run,and with sufficient experimentation,the simulation may

display a range of behavior not unlike that of the actual system being studied. The

Random method poisson in the preceding main program returns a random number

of planes arriving ready to land or ready to take off in a particular time unit.

Appendix Bstudies numbers, called pseudorandom , for use in computer pro- pseudorandom number grams. Several different kinds of pseudorandom numbers are useful for different applications. For the airport simulation, we need one of the more sophisticated kinds, called Poisson random numbers. To introduce the idea, let us note that saying that an average family has 2.6 children does not mean that each family has 2 children and 0.6 of a third. Instead, it means that, averaged over many families, the mean number of children is 2.6. Hence, for five families with 4, 1, 0, 3, 5 children the mean number is 2.6. Similarly, if the number of planes arriving to land in ten time units is 2, 0, 0, 1, 4, 1, 0, 0, 0, 1, then the mean number of planes arriving in one unit is 0.9. Let us now start with a fixed number called the expected value v ofthe random expected value, Poisson distribution numbers. Then to say that a sequence of nonnegative integers satisfies a Poisson distribution with expected value v implies that,over long subsequences,the mean value of the integers in the sequence approaches v . Appendix B describes a C++ class that generates random integers according to a Poisson distribution with a given expected value, and this is just what we need for the airport simulation.

3.5.4 The Runway Class Specification The Runway class needs to maintain two queues of planes, which we shall call landing and takeoff , to hold waiting planes. It is better to keep a plane waiting on rules the ground than in the air, so a small airport allows a plane to take off only if there are no planes waiting to land. Hence, our Runway method activity , which controls access to the Runway , will first service the head of the Queue of planes waiting to land, and only if the landing Queue is empty will it allow a Plane to take off. One aim ofour simulation is to gather data about likely airport use. It is natural 69 to use the class Runway itselfto keep statistics such the number ofplanes processed, the average time spent waiting, and the number of planes (if any) refused service. These details are reflected in the various data members of the following Runway class definition.

enum Runway_activity { idle , land , takeoff } ; Runway definition class Runway { public: Runway( int limit) ; Error_code can_land( const Plane & current) ; Error_code can_depart( const Plane & current) ; Runway_activity activity( int time , Plane & moving) ; void shut_down( int time) const; private: Extended_queue landing ; Extended_queue takeoff ; int queue_limit ; int num_land_requests ; // number of planesasking to land int num_takeoff_requests ; // number of planesasking to take off int num_landings ; // number of planesthat have landed int num_takeoffs ; // number of planesthat have taken off int num_land_accepted ; // number of planesqueued to land int num_takeoff_accepted ; // number of planesqueued to take off int num_land_refused ; // number of landing planesrefused int num_takeoff_refused ; // number of departing planesrefused int land_wait ; // total time of planeswaiting to land int takeoff_wait ; // total time of planeswaiting to take off int idle_time ; // total time runway isidle } ; Note that the class Runway has two queues among its members. The implemen- tation reflects the has-a relationships in the statement that a runway has a landing queue and has a takeoff queue.

3.5.5 The Plane Class Specification The class Plane needs to maintain data about particular Plane objects. This data must include a flight number, a time of arrival at the airport system, and a Plane status as either arriving or departing. Since we do not wish a client to be able to changethisinformation,weshallkeep itin privatedata members. When wedeclare a Plane object in the main program, we shall wish to initialize these three pieces of information as the object is constructed. Hence we need a Plane class constructor that has three parameters. Other times,however,we shallwish to construct a Plane object without initializing this information, because either its values are irrelevant or will otherwise be determined. Hence we really need two constructors for the Plane class, one with three parameters and one with none.

The C++ language provides exactly the feature we need; it allows us to use the same identifier to name as many different functions as we like, even within single block of code, so long as no two of these functions have identically typed parameter lists. When the function is invoked, the C++ compiler can figure out which version ofthe function to use, by looking at the number ofactual parameters and their types. It simply determines which set of formal parameters match the actual parameters in number and types. When we use a single name for several different functions, we say that the name is overloaded . Inside the scope of the class Plane , we are able to overload the two plane constructors, because the first uses an empty parameter list, whereas the second uses a parameter list of three integer variables. From now on, class specifications will often contain two constructors, one with parameters for initializing data members, and one without parameters. Finally, the Plane class must contain the methods refuse , land , and fly that are explicitly used by the main program. We will also need each Plane to be able to communicate its time of arrival at the airport to the class Runway , so a final method called started is included with this purpose in mind. We can now give the specification for the class Plane . enum Plane_status { null , arriving , departing } ; Plane definition class Plane { public: Plane() ; Plane( int flt , int time , Plane_statusstatus) ; void refuse() const; void land( int time) const; void fly( int time) const; int started() const; private: int flt_num ; int clock_start ; Plane_statusstate ; }

3.5.6 Functions and Methods of the Simulation The actions of the functions and methods for doing the steps of the simulation are generally straightforward, so we proceed to write each in turn, with comments only as needed for clarity.

void initialize( int & end_time , int & queue_limit , double & arrival_rate , double & departure_rate) / * Pre: The user specifiesthe number of time unitsin the simulation, the maximal queue sizes permitted, and the expected arrival and departure rates for the airport. Post: The program printsinstructionsand initializesthe parametersend_time, queue_limit, arrival_rate, and departure_rate to the specified values. Uses: utility function user_says_yes * / { cout > queue_limit ; cout > end_time ; bool acceptable ; do { cout > arrival_rate ; cout > departure_rate ; if (arrival_rate 1 . 0) cerr

Runway :: Runway( int limit) / * Post: The Runway data membersare initialized to record no prior Runway use and to record the limit on queue sizes. * / { queue_limit = limit ; num_land_requests= num_takeoff_requests= 0 ; num_landings= num_takeoffs= 0 ; num_land_refused = num_takeoff_refused = 0 ; num_land_accepted = num_takeoff_accepted = 0 ; land_wait = takeoff_wait = idle_time = 0 ; }

3. Accepting a New Plane into a Runway Queue Error_code Runway :: can_land( const Plane & current) / * Post: If possible, the Plane current is added to the landing Queue; otherwise, an Error_code of overflow isreturned. The Runway statisticsare updated. Uses: class Extended_queue. * / { Error_code result ; if (landing . size()

4. Handling Runway Access Runway_activity Runway :: activity( int time , Plane & moving) / * Post: If the landing Queue hasentries, itsfront Plane iscopied to the parameter moving and a result land isreturned. Otherwise, if the takeoff Queue has entries, its front Plane is copied to the parameter moving and a result takeoff is returned. Otherwise, idle is returned. Runway statistics are updated. Uses: class Extended_queue. * /

{ Runway_activity in_progress ; if ( ! landing . empty()) { landing . retrieve(moving) ; land_wait += time moving . started() ; num_landings ++ ; in_progress= land ; landing . serve() ; } else if ( ! takeoff . empty()) { takeoff . retrieve(moving) ; takeoff_wait += time moving . started() ; num_takeoffs ++ ; in_progress= takeoff ; takeoff . serve() ; } else { idle_time ++ ; in_progress= idle ; } return in_progress ; } 5. Plane Initialization Plane :: Plane( int flt , int time , Plane_statusstatus) / * Post: The Plane data members flt_num, clock_start, and state are set to the valuesof the parametersflt, time and status, respectively. * / { flt_num = flt ; clock_start = time ; state = status ; cout

The second ofthese constructors performs a null initialization . In many programs it is not necessary to provide such a constructor for a class. However, in C++, if we ever declare an array of objects that do have a constructor, then the objects must have an explicit default constructor. A default constructor is a constructor without parameters (or with specified defaults for all parameters). Each Runway object contains queues ofplanes,and each ofthese queues is implemented using an array of planes. Hence, in our simulation, we really do need the null initialization operation.

6. Refusing a Plane

void Plane :: refuse() const / * Post: Processesa Plane wanting to use Runway, when the Queue isfull. * / { cout

9. Communicating a Planes Arrival Data int Plane :: started() const / * Post: Return the time that the Plane entered the airport system. * / { return clock_start ; } 10. Marking an Idle Time Unit void run_idle( int time) / * Post: The specified time isprinted with a message that the runway isidle. * / { cout

11. Finishing the Simulation

void Runway :: shut_down( int time) const / * Post: Runway usage statisticsare summarized and printed. * / { cout

cout

3 : Plane number 4 landed after 0 time unitsin the takeoff queue . Plane number 6 ready to land . Plane number 7 ready to land . Plane number 8 ready to take off . Plane number 9 ready to take off . 4 : Plane number 6 landed after 0 time unitsin the takeoff queue . Plane number 10 ready to land . Plane number 11 ready to take off . 5 : Plane number 7 landed after 1 time unit in the takeoff queue . Plane number 12 ready to land . 6 : Plane number 10 landed after 1 time unit in the takeoff queue . 7 : Plane number 12 landed after 1 time unit in the takeoff queue . Plane number 13 ready to land . Plane number 14 ready to take off .

Plane number 14 told to try to takeoff again later.

8 : Plane number 13 landed after 0 time unitsin the takeoff queue . 9 : Plane number 3 took off after 7 time unitsin the takeoff queue . 10 : Plane number 5 took off after 7 time unitsin the takeoff queue . 11 : Plane number 8 took off after 7 time unitsin the takeoff queue . Plane number 15 ready to take off . 12 : Plane number 9 took off after 8 time unitsin the takeoff queue . Plane number 16 ready to land . Plane number 17 ready to land . 13 : Plane number 16 landed after 0 time unitsin the takeoff queue . Plane number 18 ready to land . 14 : Plane number 17 landed after 1 time unit in the takeoff queue . 15 : Plane number 18 landed after 1 time unit in the takeoff queue . Plane number 19 ready to land . Plane number 20 ready to take off . 16 : Plane number 19 landed after 0 time unitsin the takeoff queue . 17 : Plane number 11 took off after 12 time unitsin the takeoff queue . 18 : Plane number 15 took off after 6 time unitsin the takeoff queue . 19 : Plane number 20 took off after 3 time unitsin the takeoff queue.

20 : Runway isidle

Eventually, after many more steps of the simulation, we get a statistical summary.

Simulation hasconcluded after 1000 time units .

Total number of planesprocessed 970 Total number of planesasking to land 484 Total number of planesasking to take off 486 Total number of planesaccepted for landing 484 Total number of planesaccepted for takeoff 423 Total number of planesrefused for landing 0 Total number of planesrefused for takeoff 63 Total number of planesthat landed 483 Total number of planesthat took off 422 Total number of planesleft in landing queue 1 Total number of planesleft in takeoff queue 1 Percentage of time runway idle 9 . 5 % Average wait in landing queue 0 . 36646 time units Average wait in takeoff queue 4 . 63744 time units Average observed rate of planeswanting to land 0 . 484 time units Average observed rate of planeswanting to take off 0 . 486 time units Notice that the last two statistics, giving the observed rates of planes asking for landing and departure permission, do match the expected values put in at the beginning of the run (within a reasonable range): This outcome should give us some confidence that the pseudo-random number algorithm of Appendix Breally does simulate an appropriate Poisson distribution.

P1. Combine all the functions and methods for the airport simulation into a com- plete program. Experiment with several sample runs ofthe airport simulation, adjusting the values for the expected numbers of planes ready to land and take off. Find approximate values for these expected numbers that are as large as possible subject to the condition that it is very unlikely that a plane must be refused service. What happens to these values if the maximum size of the queues is increased or decreased? P2. Modify the simulation to give the airport two runways, one always used for landingsand onealwaysused for takeoffs. Comparethetotalnumber ofplanes that can be served with the number for the one-runway airport. Does it more than double?

Section 3.5.Application of Queues: Simulation 97 4 Landing queuc Plane landing Runway Takeoff queue Figure 3.5. An airport Section 3.5.Application of Queues: Simulation 97 4 Landing queuc Plane landing Runway Takeoff queue Figure 3.5. An airport