EECE 352: PS 11

Due: Tuesday 23 November 1999

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;
}



Jose M. Vidal
Last modified: Thu Nov 11 13:55:32 EST 1999