// A simple simulation of an M/M/1 queue to determine server utilization.
//
// CS 525, Simulation, Spring 2005

#include <cassert>
#include <queue>
#include <deque>
#include <iostream>
#include <sys/types.h>
#include <unistd.h>
#include "rng.h"


// Simulation time units.

  typedef double ticks;


// The arrival and service distributions.

   static rng * arrival_rate, * service_time;


// The trigger action type.

   typedef void (* trigger_proc)();


// An event; the scheduling unit.

   struct event {

     // When this event should be triggered.

	ticks trigger_time;

     // What happens when this event gets triggered.

	trigger_proc trigger;

     // Create a new event with the given the absolute trigger time and
     // behavior.

	event(ticks tt, trigger_proc t)
	  : trigger_time(tt), trigger(t) { }

     // Return true iff this event is greater than the given event.

       bool operator > (const event & e) const {
	 return trigger_time > e.trigger_time;
	 }
     };


// The event queue.  Maintained in increasing trigger time; events with
// identical trigger times are pulled off the queue in an arbitrary order.

   static std::priority_queue<event, std::deque<event>, std::greater<event> >
     event_queue;


// The most recent time at which the server went from idle to busy.

   static ticks server_starts;

// The total time at which the server has been busy so far.

   static ticks server_busy_time;


// The current simulation time; it's equal to the trigger time of the most
// recently triggered event.

   static ticks current_time;


// The number of customers waiting for service, including the one being
// serviced (if any).

   static unsigned queue_length;


// Deja vu, c++ style.

   static void server_start();
   static void schedule(const event &);
   static void run();


static void 
client() {

  // A client arrives for service.

  static unsigned clients = 0;

  if (++clients < 1000) {
    if (1 == ++queue_length)
      schedule(event(current_time, server_start));
    schedule(event(current_time + arrival_rate->next(), client));
    }
  }


int 
main(int argc, char * argv[]) {

  if (argc != 3) {
    std::cerr << "Command format is \"" << argv[0] 
	      << " arrival-rate service-time\".\n";
    exit(1);
    }

  srand48(getpid());

  total_service_time = current_time = 0;
  arrival_rate = new exponential(atof(argv[1]));
  service_time = new exponential(atof(argv[2]));

  schedule(event(current_time, client));

  run();

  std::cout << total_service_time/current_time << "\n";

  delete arrival_rate;
  delete service_time;
  }

static void
run() {

  // Pull events off the event queue and trigger them; keep doing it until
  // there ain't no mo'.

  while (not event_queue.empty()) {
    const event e = event_queue.top();
    event_queue.pop();
    current_time = e.trigger_time;
    e.trigger();
    }
  }


static void 
schedule(const event & e) {

  // Schedule the given event.

  assert(e.trigger_time >= current_time);

  event_queue.push(e);
  }


static void
server_continue() {

  // Once the server has finished with one customer, look for another customer
  // or go to the idle state.

  assert(queue_length > 0);
  if (--queue_length > 0)
    schedule(event(current_time + service_time->next(), server_continue));
  else {
    server_busy_time += current_time - server_starts;
    std::cout << server_busy_time/current_time << "\n";
    }
  }


static void
server_start() {

  // A new customer wakes the idle server up.

  assert(queue_length > 0);

  server_starts = current_time;
  schedule(event(current_time + service_time->next(), server_continue));
  }


// $Log: mm1-utilization.cc,v $
// Revision 1.4  2005/04/05 01:57:22  rclayton
// Updated.
//
// Revision 1.3  2005/04/04 03:10:43  rclayton
// Print the server utilization samples.
//
// Revision 1.2  2005/03/27 01:46:41  rclayton
// Define ticks.
//