'k' M/M/1 tandem queue simulation

tandem.c

//******************************************************************************
//* 'k' M/M/1 tandem queue simulation 			                                   *
//******************************************************************************
//*  Notes:                                                                    *
//*----------------------------------------------------------------------------*
//*  Build: gcc -o tandem tandem.c 			                                       *
//*----------------------------------------------------------------------------*
//*  Execute: ./tandem  MAX_CUSTOMERS NUM_SERVERS(k) INTER_ARR_TIME1           *
//*  SERV_TIME1 PROBABILITY1 .. INTER_ARR_TIME(k) SERV_TIME(k) PROBABILITY(k)  *
//*----------------------------------------------------------------------------*
//*  Author: Anshuman Biswas                                                   *
//*  Email: [email protected]                                           *
//*----------------------------------------------------------------------------*
//*  Version: 1.0                                                              *
//******************************************************************************
//----- Include files ----------------------------------------------------------
#include <stdio.h>    			// Needed for printf()
#include <stdlib.h>   			// Needed for rand()
#include <math.h>				// Needed for log()

// #define MAX 50000      			         // Modify this to change the number of requests
#define RSEED 1234   			// Modify this to change seed of the random number generator function
#define CONST_PARAM 3

long int MAX;

//----- Link List -------------------------------------------------------------
// This link list will store the future events
typedef struct node {
  int callerID;
  int server;
  char event;
  char type;
  double time;
  struct node *next;
} node_t;

// This link list will store the attributes of the server
typedef struct Server {
  double arrTime;
  double serviceTime;
  double probability;
  double departureTime;
  int server;
  int busy;
  int departures;
  int exogenousArrivals;
  int systemArrivals;
  double throughputRate;
  double busyTime;
  double serverUtilization;
  double meanSystemTime;
  double meanQueueTime;
  double meanSystemNumber;
  double meanQueueNumber;
  node_t * queue;
  node_t * fel;
  struct Server *next;
} node_p;

//----- Function prototypes ----------------------------------------------------
double expntl(double x);        										                  // Generate exponential RV with mean x
void print_list_fel(node_t * head);											              // Print the future event list
int popEvent(node_t ** head);											                    // Remove the event at the front of the list
int popBuffer(node_p **temPar,double currentTime);								              // Remove the waiting event at the front of the buffer
void insertEvent(node_t ** head,int server,int callerID,char event,char type,double time);	// Insert an event at the appropriate time of occurence
void print_all(node_t * head,node_t * bhead,int n);						          // Print both the future event list as well as the buffer
void insertParam(node_p ** par,double arr,double serv,double pb,int n);           // Insert the parameters of a server
void print_list_param(node_p * head);                                 // Print the parameter list
int probLeaving(double p);

int main(int argc, char *argv[])
{
	int i,j=0,n=0,line=0,callerID=0,localCallerID,originalServer,departures=0,prob;
  char type;
	double prevTime = 0.0,newTime = 0.0,busyTime = 0.0,serviceTime=0.0,waitingTime = 0.0,residenceTime=0.0;
  double arr,serv,globalClock = 0.0;
  node_p * par = NULL;
  node_p * temPar = NULL;
  node_p * printPar = NULL;
  node_t * latestPar = NULL;
	
  if ( argc < 6 ) /* argc should be atleast 5 or more for correct execution */
  {
      /* We print argv[0] assuming it is the program name */
      printf( "usage: %s MAX_CUSTOMERS NUM_SERVERS(k) INTER_ARR_TIME1 SERV_TIME1 PROBABILITY1 .. INTER_ARR_TIME(k) SERV_TIME(k) PROBABILITY(k)\n", argv[0] );
      exit(-1);
  }
  else if (argc != (CONST_PARAM+atoi(argv[2])*3))
  {
      printf( "usage: %s MAX_CUSTOMERS NUM_SERVERS(k) INTER_ARR_TIME1 SERV_TIME1 PROBABILITY1 .. INTER_ARR_TIME(k) SERV_TIME(k) PROBABILITY(k)\n", argv[0] );
      printf( "There should be %d parameters for the program with %d servers.\n", (CONST_PARAM+atoi(argv[2])*3)-1,atoi(argv[2]) );
      printf( "You have inputted %d parameters.\n", argc-1 );
      exit(-1);
  }
  else
  {
      for(i = 3; i < argc; i++)
      {
          if(atof(argv[i]) < 0 && ((i-2)%3) != 0) // This is to check whether the service and arrival times are non zero
          {
              if((i%3) == 0)
                printf( "In server #%d, Inter arrival time must be greater than 0.\n",  (int)round((i-CONST_PARAM)/3)+1);
              else if(((i-1)%3) == 0)
                printf( "In server #%d, service time must be greater than 0.\n",  (int)round((i-CONST_PARAM)/3)+1);
              exit(-1);
          }
          else if((atof(argv[i]) < 0 || atof(argv[i]) > 1) && ((i-2)%3) == 0) // This is to check whether the probability is between 0 and 1
          {  
              printf( "In server #%d, the probability of leaving the system should be between 0 and 1.\n",  (int)round((i-CONST_PARAM+1)/3));
              exit(-1);
          }
          else if(((i-2)%3) == 0)
            insertParam(&par,atof(argv[i-2]),atof(argv[i-1]),atof(argv[i]),++j);
      }
  }
	MAX = atoi(argv[1]);
	// Assign a seed for the random number
	
  srand(RSEED);
  // temPar=par;
  // print_list_param(temPar);

  // Insert an initial arrival event to each server's FEL
  temPar=par;
  while(temPar!=NULL)
  {
    insertEvent(&temPar->fel,temPar->server,++callerID,'A','E',prevTime + expntl(temPar->arrTime));
    // Add to the exogenous arrival
    temPar->exogenousArrivals++;
    temPar=temPar->next;
  }
  
  // UNCOMMENT THIS TO VIEW THE FEL and the buffer  
  // printPar=par;
  // while(printPar!=NULL)
  // {
  //     print_all(printPar->fel,printPar->queue,printPar->server);   
  //     printPar=printPar->next;
  // }

	while(1) {
      temPar=par;
      while(temPar!=NULL)
      {
          if(temPar->fel)
          {
          	// Pickup the next event in the list
            	switch(temPar->fel->event){
        	        case 'A':
          	            prevTime = temPar->fel->time;
          	            localCallerID = temPar->fel->callerID;
                        originalServer = temPar->fel->server;
                        type = temPar->fel->type;
          	            popEvent(&temPar->fel);
          	            if(!temPar->busy) {
          	            	// Create a departure event in the FEL
          	            	serviceTime = expntl(temPar->serviceTime);
          		            newTime = prevTime+serviceTime;
          		            temPar->busyTime += serviceTime;
          		            temPar->meanSystemTime += serviceTime;
          		            insertEvent(&temPar->fel,originalServer,localCallerID,'D','X',newTime);
          		            temPar->busy = 1;	// Make the server busy
        		            }
            		        // Add to queue
            		        else 
            		        	 insertEvent(&temPar->queue,originalServer,localCallerID,'A',type,prevTime);

            		        // Create a new event
                        if(callerID < MAX && type == 'E')
                        {
            		            insertEvent(&temPar->fel,temPar->server,++callerID,'A','E',prevTime + expntl(temPar->arrTime));
                            // Add to the exogenous arrival
                            temPar->exogenousArrivals++;
                        }
        	    		     break;

          	    	case 'D':
                      prevTime = temPar->fel->time;
                      temPar->departureTime = prevTime;
                      localCallerID = temPar->fel->callerID;
                      originalServer = temPar->fel->server;
                      // Increase the departure in the system
                      temPar->departures++;
                      popEvent(&temPar->fel);
                      // This is the last server
                      if(temPar->next == NULL)
            	    		   departures++;
            	    		else{
                        // If (1-p) event occured
                        prob = probLeaving(temPar->probability);
                        // printf("%d: %lf\n", prob,temPar->probability);
                        if(prob == 1){
                            // Find the time to start
                            latestPar = temPar->next->fel;
                            while(latestPar->next != NULL)
                              latestPar = latestPar->next;
                            // Move the request to the next server
                            insertEvent(&temPar->next->fel,originalServer,localCallerID,'A','S',latestPar->time + expntl(temPar->next->arrTime));
                            // Add to the system arrival
                            temPar->next->systemArrivals++;
                          }
                          else
                            departures++;
        	            }
                      if(departures == MAX)
                            goto Result;
        	            if(temPar->queue!=NULL)
        	            	popBuffer(&temPar,prevTime);
        	            else
        	            	temPar->busy=0;
            	    		break;
          		}
          }
          // Catchup with the global time
          if(globalClock < prevTime || !(temPar->fel))
          {
            globalClock = prevTime;
            temPar=temPar->next;
          }
          // printPar=par;
          // while(printPar!=NULL)
          // {
          //     print_all(printPar->fel,printPar->queue,printPar->server);   
          //     printf("%lf:%lf:%lf:%lf\n",printPar->busyTime,printPar->meanQueueTime,printPar->meanSystemTime,globalClock);
          //     printPar=printPar->next;
          // }
          
      }

  }

	Result:
	// Output results
	printf("**************************************STATISTICS*******************************\n");
  printPar=par;
  while(printPar!=NULL)
  {
      if(printPar == par)
          arr = 1/printPar->arrTime;
      else
          arr = 1/(printPar->arrTime)+arr*(1-printPar->probability);
      serv = 1/printPar->serviceTime;
      printf("*   The arrival rate is :- %lf\n",arr);
      printf("*   The service rate is :- %lf\n",serv);
      if(arr > serv)
          printf("*   UNSTABLE:\n*    The queue in server %d is unstable since the arrival rate is greater than service rate!!\n",printPar->server);
      printPar=printPar->next;
  }
  
	printf("*                 Results from the Tandem Queue simulation                    * \n");
	printf("*******************************************************************************\n");
	printf("*  INPUTS:                                     \n");
	printf("*    Total simulated time        = %3.4f sec    \n", prevTime);
  printPar=par;
  while(printPar!=NULL)
  {
      printf("*  For Server:- %d                             \n", printPar->server);
      printf("*    Mean time between arrivals   = %lf sec      \n", printPar->arrTime);
      printf("*    Mean service time            = %lf sec      \n", printPar->serviceTime);
      printf("*    Probability P(%d)            = %lf sec      \n", printPar->server,printPar->probability);
      printPar=printPar->next;
  }
	printf("*******************************************************************************\n");
	printf("*  OUTPUTS:                                    \n");
	printf("*    Number of completions        = %u cust      \n", departures);
	printf("*    System Throughput rate       = %lf cust/sec \n", departures/prevTime);
  printPar=par;
  while(printPar!=NULL)
  {
      printf("*  For Server:- %d                             \n", printPar->server);
      printf("*    Number of server arrivals    = %d cust      \n", printPar->systemArrivals);
      printf("*    Number of exogenous arrivals = %d cust      \n", printPar->exogenousArrivals);
      printf("*    Number of departures         = %d cust      \n", printPar->departures);
      printf("*    Time of last departure       = %lf sec      \n", printPar->departureTime);
      printf("*    Busy Time                    = %lf sec      \n", printPar->busyTime);
    	printf("*    Server utilization           = %lf %%       \n", 100.0 * printPar->busyTime/printPar->departureTime);
      printf("*    Mean System time             = %lf sec      \n", printPar->meanSystemTime/printPar->departures);
    	printf("*    Mean queueing time           = %lf sec      \n", printPar->meanQueueTime/printPar->departures);
    	printf("*    Mean number in server        = %lf cust     \n", printPar->meanSystemTime/printPar->departureTime);
    	printf("*    Mean number in queue         = %lf cust     \n", printPar->meanQueueTime/printPar->departureTime);
      printf("*    Total system time            = %lf sec     \n", printPar->meanSystemTime);
      printf("*    Total queue time             = %lf sec     \n", printPar->meanQueueTime);
      printPar=printPar->next;
  }
	printf("*******************************************************************************\n");
	return 0;
}

//******************************************************************************
//*  Function: Print both the future event list as well as the buffer		   *
//*    - Input:  	1) The pointer to the head of the link list                *
//*    -  			2) The pointer to the head of the buffer				   *
//*    - Output: void                                                          *
//******************************************************************************

void print_all(node_t * head,node_t * bhead,int n) {
	printf("*******************************************************************************\n");
  printf("Server-%d\n",n);
  printf("***************************\n");
	printf("FEL-");
	print_list_fel(head);
	printf("***************************\n");
	printf("BUFFER-");
	print_list_fel(bhead);
	printf("*******************************************************************************\n");
}

//******************************************************************************
//*  Function to generate exponentially distributed RVs using inverse method   *
//*    - Input:  x (mean value of distribution)                                *
//*    - Output: Returns with exponential RV                                   *
//******************************************************************************
double expntl(double x)
{
	double z;                     // Uniform random number from 0 to 1

	// Pull a uniform RV (0 < z < 1)
	do {
		z = ((double) rand() / RAND_MAX);
	}
	while ((z == 0) || (z == 1));

  // return -log(1.0 - (double) random() / (RAND_MAX + 1)) / x;


	return(-x * log(z));
}

//******************************************************************************
//*  Function: Print the future event list                                     *
//*    - Input:  1) The pointer to the head of the link list                   *
//*    - Output: void                                                          *
//******************************************************************************
void print_list_fel(node_t * head) {
    node_t * current = head;
    while (current != NULL) {
        printf("(%d,%d,%c,%c,%lf)", current->server,current->callerID,current->event,current->type,current->time);
        current = current->next;
        if(current != NULL)
        	printf("|");
    }
    printf("\n");
}

//******************************************************************************
//*  Function: Remove the event at the front of the list                       *
//*    - Input:  1) The pointer to the pointer of the head of the link list    *
//*    - Output: int: A bool type for whether the pop was successful or not	   *
//******************************************************************************
int popEvent(node_t ** head) {
    int retval = -1;
    node_t * next_node = NULL;

    if (*head == NULL) {
        return -1;
    }

    next_node = (*head)->next;
    retval = 1;
    free(*head);
    *head = next_node;
    return retval;
}

//******************************************************************************
//*  Function: Remove the waiting event at the front of the buffer             *
//*    - Input:  1) The pointer to the pointer of the head of the server       *
//*    - Input:  2) double: The current time in the simulation                 *
//*    - Output: void                                                          *
//******************************************************************************
int popBuffer(node_p **temPar,double currentTime) {
    double newTime,serviceTime,wt;
    int retval = -1;
    node_t * next_node = NULL;

    if ((*temPar)->queue == NULL) {
        return -1;
    }
    // printf("Current Time - %lf\n", currentTime);
    next_node = (*temPar)->queue->next;
    retval = 1;
    // Insert as a departure event
    serviceTime = expntl((*temPar)->serviceTime);
    // printf("serviceTime Time - %lf\n", serviceTime);
    newTime = currentTime+serviceTime;
    (*temPar)->busyTime += serviceTime;
    wt = (currentTime - (*temPar)->queue->time);
    wt = (wt > 0)? wt : 0;
    (*temPar)->meanQueueTime += wt;
    (*temPar)->meanSystemTime += (serviceTime+wt);
    // Write the data to file
    insertEvent(&((*temPar)->fel),(*temPar)->queue->server,(*temPar)->queue->callerID,'D','X',newTime);
    free((*temPar)->queue);
    (*temPar)->queue = next_node;
    return retval;
}

//******************************************************************************
//*  Function: Insert an event at the appropriate time of occurence            *
//*    - Input:  1) The pointer to the pointer of the head of the link list    *
//*    - Input:  2) int: ID of the the caller                                  *
//*    - Input:  3) char: Symbol to signify the event                          *
//*    - Input:  4) double: The time the event will occur                      *
//*    - Output: void                                                          *
//******************************************************************************
void insertEvent(node_t ** head,int server,int callerID,char event,char type,double time)
{
  node_t * current = *head;
  node_t * newEvent = NULL;
  if(current == NULL) {
      newEvent=malloc(sizeof(node_t));
      newEvent->next = NULL;
      *head = newEvent;
      newEvent->time=time;
      newEvent->callerID = callerID;
      newEvent->event = event;
      newEvent->type = type;
      newEvent->server = server;
  }
  else {
    while(current != NULL) {
        // This is the case when the event needs to be inserted in after the last event
        if(current->time <= time && current->next == NULL) {
            // Create a new memory and re-assign the pointers
            newEvent=malloc(sizeof(node_t));
            newEvent->next = current->next;
            current->next=newEvent;
            newEvent->time=time;
            newEvent->callerID = callerID;
            newEvent->event = event;
            newEvent->type = type;
            newEvent->server = server;
            break;
        }
        // This is the case when the event needs to be inserted before the first event
        else if(current->time > time && current == *head) {
            // Create a new memory and re-assign the pointers
            newEvent=malloc(sizeof(node_t));
            newEvent->next = current;
            *head = newEvent;
            newEvent->time=time;
            newEvent->callerID = callerID;
            newEvent->event = event;
            newEvent->type = type;
            newEvent->server = server;
            break;
        }
        // This is the case when the event needs to be inserted in between two other events
        else if(current->time < time && current->next->time >= time) {
            // Create a new memory and re-assign the pointers
            newEvent=malloc(sizeof(node_t));
            newEvent->next = current->next;
            current->next=newEvent;
            newEvent->time=time;
            newEvent->callerID = callerID;
            newEvent->event = event;
            newEvent->type = type;
            newEvent->server = server;
            break;
        }

      // Proceed to the next event
      current = current->next;
    }
  }
}

//******************************************************************************
//*  Function: Print the parameter list                                        *
//*    - Input:  1) The pointer to the head of the link list                   *
//*    - Output: void                                                          *
//******************************************************************************
void print_list_param(node_p * head) {
    node_p * current = head;
    while (current != NULL) {
        printf("(%d,%lf,%lf,%lf)", current->server,current->arrTime,current->serviceTime,current->probability);
        current = current->next;
        if(current != NULL)
          printf("|");
    }
    printf("\n");
}

//******************************************************************************
//*  Function: Insert the parameters of a server                               *
//*    - Input:  1) The pointer to the head of the parameter link list         *
//*    - Input:  2) double: The mean arrival time to the server                *
//*    - Input:  3) double: The probability of leaving the system              *
//*    - Input:  4) double: The mean service time of the server                *
//*    - Output: void                                                          *
//******************************************************************************
void insertParam(node_p ** par,double arr,double serv,double pb,int n)
{
    node_p *end = *par;
    node_p *newParam = NULL;
    // If there are no servers added
    if(end == NULL)
    {
      newParam=malloc(sizeof(node_p));
      *par = newParam;
    }
    // For all other cases
    else
    {
      // Navigate to the end of the list
      while(end->next!=NULL) 
          end=end->next;
      newParam=malloc(sizeof(node_p));\
      end->next = newParam;
    }
    // Create the information for the node
    newParam->next = NULL;
    newParam->arrTime = arr;
    newParam->serviceTime = serv;
    newParam->probability = pb;
    newParam->server = n;
    newParam->queue = NULL;
    newParam->fel = NULL;
    newParam->busy = 0;
    newParam->departures = 0;
    newParam->exogenousArrivals = 0;
    newParam->systemArrivals = 0;
    newParam->throughputRate=0.0;
    newParam->busyTime=0.0;
    newParam->departureTime=0.0;
    newParam->serverUtilization=0.0;
    newParam->meanSystemTime=0.0;
    newParam->meanQueueTime=0.0;
    newParam->meanSystemNumber=0.0;
    newParam->meanQueueNumber=0.0;
}

//******************************************************************************
//*  Function: Generate whether the cusomer will leave the system              *
//*    - Input:  1) double: The probability of occurence of the event          *
//*    - Output: int: 1 if it will leave the system, 0 if it will continue     *
//******************************************************************************

int probLeaving(double p)
{
    return ((double)rand() / RAND_MAX) > p ? 1:0;
}