Problem 0: (0%) In this problem set we will be using the modem pool simulation from the Book, section 13.2.2. This is an example of an event-driven simulation, an extremely useful tool used in many applications. You should compile and run the code below, making sure you understand how it works. You should also read section 13.2 from the book.
Notice that this application uses the
priority_queue
container class from the STL. Take
particular notice of the member functions that are called.
Problem 1: (80%) You will implement your own
priority_queque class and change the program below to use your
new priority queue. You should give your new class the name
pqueue
. You should not change any of the code in
this program except for the line that says:
PQ eventSet; // Pending events
which you will change to:
pqueue<Event> eventSet; // Pending events
Notice that the pqueue will be a templated class. You should also
comment out the line:
typedef priority_queue<Event,vector<Event>,greater<Event> > PQ;
Basically, your pqueue should maintain the same API that the STL's priority_queue offers. This is the whole point of data abstraction: you should be able to reimplement the class and have the old programs compile and run perfectly with the new implementation.
Problem 2: (20%) Implement a sort() function for your pqueue which does internal sorting (chapter 20.5).
// ModemSim class interface: run a simulation // // CONSTRUCTION: with (a) three parameters: the number of // modems, the average connect time, and the // inter-arrival time. // // ******************PUBLIC OPERATIONS********************* // void runSim( ) --> Run a simulation #include <limits.h> #include <time.h> #include <stdlib.h> #include <math.h> #include <vector> #include <queue> #include <functional> #include<iostream> using namespace std; class Event { enum { DIAL_IN = 1, HANGUP = 2 }; public: Event( int name = 0, int tm = 0, int type = DIAL_IN ) : time( tm ), who( name ), what( type ) { } bool operator> ( const Event & rhs ) const { return time > rhs.time; } bool operator< ( const Event & rhs ) const { return time < rhs.time; } friend class ModemSim; private: int who; // the number of the user int time; // when the event will occur int what; // DIAL_IN or HANGUP }; typedef priority_queue<Event,vector<Event>,greater<Event> > PQ; class ModemSim { public: ModemSim( int modems, double avgLen, int callIntrvl ); // Add a call to eventSet at the current time, // and schedule one for delta in the future. void nextCall( int delta ); // Run the simulation void runSim( int stoppingTime = INT_MAX ); private: PQ eventSet; // Pending events // Basic parameters of the simulation int freeModems; // Number of modems unused const double avgCallLen; // Length of a call const int freqOfCalls; // Interval between calls int poisson( double expectedValue ); }; // Return random number according to Poisson distribution. int ModemSim::poisson( double expectedValue ) { double limit = -expectedValue; double sum = log( static_cast<double>(rand())/ static_cast<double>(RAND_MAX)); int count; for( count = 0; sum > limit; count++ ) sum += log(static_cast<double>(rand()) /static_cast<double>(RAND_MAX)); return count; } // Constructor for ModemSim. ModemSim::ModemSim( int modems, double avgLen, int callIntrvl ) : freeModems( modems ), avgCallLen( avgLen ), freqOfCalls( callIntrvl ) { nextCall( freqOfCalls ); // Schedule first call } // Place a new DIAL_IN event into the event queue. // Then advance the time when next DIAL_IN event will occur. // In practice, we would use a random number to set the time. void ModemSim::nextCall( int delta ) { static int nextCallTime = 0; static int userNum = 0; eventSet.push( Event( userNum++, nextCallTime ) ); nextCallTime += poisson(static_cast<double>(delta)); } // Run the simulation until stopping time occurs. // Print output as in Figure 14.4. void ModemSim::runSim( int stoppingTime ) { static Event e; int howLong; while( !eventSet.empty( ) ) { e = eventSet.top( ); eventSet.pop( ); if( e.time > stoppingTime ) break; if( e.what == Event::HANGUP ) // HANGUP { freeModems++; cout << "User " << e.who << " hangs up at time " << e.time << endl; } else // DIAL_IN { cout << "User " << e.who << " dials in at time " << e.time << " "; if( freeModems > 0 ) { freeModems--; howLong = poisson( avgCallLen ); cout << "and connects for " << howLong << " minutes" << endl; e.time += howLong; e.what = Event::HANGUP; eventSet.push( e ); cout << "Push(1) " << endl; } else cout << "but gets busy signal" << endl; nextCall( freqOfCalls ); } } } // Simple main to test ModemSim class. int main( ) { int numModems; int totalTime; double avgConnectTime; int dialInFrequency; cout << "Enter number of modems, length of simulation,\n" << " average connect time, how often calls occur: "; cin >> numModems >> totalTime >> avgConnectTime >> dialInFrequency; ModemSim s( numModems, avgConnectTime, dialInFrequency ); s.runSim( totalTime ); return 0; }