backup.tar

qnsim-ss.c010060000000620000062000000256240633246565500126260ustar00rljones00000400000021/******************************************************************************
*  Module:   qnsim-ss.c                                                       *
*                                                                             *
*  Author:   Rob Jones                                                        *
*                                                                             *
*  Purpose:  CSci 726 Discrete-Event Simulation: PROJECT #3                   *
*            Provides main simulation program for a general-purpose           *
*            STEADY-STATE SIMULATION of a queuing network consisting          *
*            of single server nodes.                                          *
*                                                                             *
*  Version:  5-02-97                                                          *
*                                                                             *
*  Note:     Even though this simulator is capable of simulating an           *
*            open or closed queuing network, the statistics are currently     *
*            applicable for an open network and are referrenced to node 0.    *
*            Also, the within-batch sample index (count) is counting the      *
*            number of departures from network.  If a closed network is       *
*            simulated without using a reference other than node 0, the       *
*            simulation will not terminate.                                   *
*                                                                             *
*******************************************************************************/

#include "qnet.h"
#include "queue.h"
#include "misc.h"

/* SIMULATION PARAMETERS: */

#define MAX_BATCHES      1000           /* maximum number of batches      */
#define BATCH_SIZE       1000           /* batch size (must be > 1)       */
#define INTERVAL_WIDTH   0.05           /* interval half width in percent */
#define LOC              0.95           /* level of confidence            */
#define INFINITY         1e300          /* a large number                 */

double *future_events;   /* future-events list */

void ProcessArrival(long i, double time)
/******************************************************************************
  Auxilary function used to service the arrival of a job to node 'i' at the
  current 'time' if the node is idle, otherwise the job is put into the queue.
  If the job is serviced, the job's departure is also scheduled.
*******************************************************************************/
{
  extern rv_func    *random_time;  /* sample function  */
  extern actvty     *status;       /* server status    */
  extern queue_type *queue;        /* service queue    */
  double job_time   = 0;           /* job service time */

  if (status[i] == IDLE) { /* if idle then service job */
    status[i] = BUSY;
    SelectStream(i);
    future_events[i] = time + random_time[i].func();
  } else { /* otherwise, add job to queue */

#ifdef SJF_QUEUE /* if SJF then sample/store service time */
    SelectStream(i);
    job_time = random_time[i].func(); 
#endif

    Insert(&queue[i],job_time);
  }
}

void ServiceJob(long i, double time)
/******************************************************************************
  Auxilary function used to service the next job in the queue of node 'i' at
  the current 'time' thereby scheduling the departure of the job.
*******************************************************************************/
{
  extern rv_func    *random_time;  /* sample function  */
  extern actvty     *status;       /* server status    */
  extern queue_type *queue;        /* service queue    */
  double job_time   = 0;           /* job service time */

  Remove(&queue[i],&job_time);

#ifdef SJF_QUEUE /* if SJF then service time is already stored */

  future_events[i] = time + job_time;

#else /* otherwise sample service-time function */

  SelectStream(i);
  future_events[i] = time + random_time[i].func();

#endif
  status[i] = BUSY;
}

int main(void)
/******************************************************************************
  MAIN PROGRAM
*******************************************************************************/
{
  extern qnt        type;           /* either OPEN or CLOSED                  */
  extern int        num_nodes;      /* number of service nodes                */
  extern rv_func    *random_time;   /* service time random variate functions  */
  extern queue_type *queue;         /* queue for each service node            */
  extern actvty     *status;        /* status of each server: {IDLE,BUSY}     */
  int    node;                      /* service node index                     */
  double clock;                     /* current simulation time                */
  double prev_clock;                /* previous sim time                      */
  double init_clock;                /* time at start of batch                 */
  long   i, j;                      /* general-purpose indices                */
  long   batch;                     /* batch index                            */
  long   count;                     /* sample counter within a batch          */
  long   current, next;             /* service node indices                   */
  long   seed = 123456789;          /* random number seed                     */
  long   n;                         /* number of samples                      */
  double u = 1.0 - 0.5*(1.0 - LOC); /* interval parameter                     */ 
  double s, t, diff;                /* used to compute interval estimate      */
  long   num_arrivals       = 0;    /* counts # of external job arrivals      */
  long   num_jobs           = 0;    /* total number of jobs in system         */
  double arrival_rate;              /* average external arrival rate          */
  double area_number;               /* time-averaged number of jobs in system */
  double mean_num_jobs      = 0.0;  /* E[number of jobs in system]            */
  double sumsqr_num_jobs    = 0.0;  /* sum of squares to compute variance     */
  double w;                         /* confidence interval half width         */                
/*=============================*/
  long   jobs;
  long   num    = 0;
  long   events;
  double mean   = 0.0;
  double sumsqr = 0.0;
  double ww;
/*=============================*/
  
  /* initialize */

  Network();   /* get specification of queuing network  */
  Init();      /* initialize of network data structures */ 

  /* create future-event list */
  future_events = (double *)calloc(num_nodes,sizeof(double)); 
  if (future_events == NULL) {
    error(MEM_ERR);
  }

  PlantSeeds(seed);
  Initialize();       /* set the initial state of network */
  clock = 0.0;        

  /* schedule first events */
  if (type == OPEN) {
    SelectStream(0);
    future_events[0] = random_time[0].func(); 
  } else {
    future_events[0] = INFINITY; 
  }
  for (i = 1; i < num_nodes; i++) {         
    if (IsEmpty(&queue[i]) == FALSE) {
      num_jobs += Number(&queue[i]);
      ServiceJob(i,clock);
    } else {
      status[i]        = IDLE;
      future_events[i] = INFINITY;                    
    }
  }

  /* begin simulation */

  for (batch = 1; batch <= MAX_BATCHES; batch++) { 

    /* re-initialize the statistics only */
    init_clock  = clock;
    prev_clock  = clock;
    area_number = 0.0;
    count       = 0;

/*=====================================*/
    jobs   = 0;
    events = 0;
/*=====================================*/

    while (count < BATCH_SIZE) {

      /* get next (most imminent) event */
      current = 0; 
      for (j = 0; j < num_nodes; j++) {
        if (future_events[j] < future_events[current]) {
          current = j;
        }
      }
      clock = future_events[current]; /* advance the clock */

      /* if event was an outside arrival then schedule a new one */
      if (current == 0) {
        SelectStream(0);
        future_events[current] = clock + random_time[current].func();
        area_number += num_jobs*(clock - prev_clock);
        prev_clock   = clock;
        num_arrivals++; 
        num_jobs++;     /* one more job in system */
      } else { /* process the departure */    
        if (IsEmpty(&queue[current]) == FALSE) { 
          ServiceJob(current,clock); /* service next job in queue */
        } else {
          status[current] = IDLE;
          future_events[current] = INFINITY;
        }
      }
      /* place job in a destination service node */

      next = GetNextNode(current); 

      if (next == 0) { /* if departure from system then */
        area_number += num_jobs*(clock - prev_clock);
        prev_clock   = clock;
        count++;
        num_jobs--;           /* one less job in system */
      } else { 
        ProcessArrival(next,clock);
      }          
#ifdef METHOD1
    /* compute mean number of jobs in system */
    diff = num_jobs - mean_num_jobs;
    sumsqr_num_jobs += diff*diff*(batch - 1.0)/batch;
    mean_num_jobs   += diff/batch;
#endif
    } /*end while*/ 

#ifdef METHOD2
    /* compute mean number of jobs in system */
    diff = area_number/(clock-init_clock) - mean_num_jobs;
    sumsqr_num_jobs += diff*diff*(batch - 1.0)/batch;
    mean_num_jobs   += diff/batch;
#endif

    /* to reduce some overhead, check on how we're doing every 10 samples */
    if (batch % 10 == 0) {
      n = batch;                    /* the number of samples */
      t = idfStudent(n - 1,u);      /* critical value of t   */
      s = sqrt(sumsqr_num_jobs/n);  /* standard deviation    */
      w = t*s/sqrt(n - 1);          /* interval half width   */
      if (w/mean_num_jobs <= INTERVAL_WIDTH) {
        break; /* exit for loop when desired interval is achieved */
      }
    }

/*=================================================*/
#ifdef DEBUG
    printf("%ld \t",batch);
    printf("%f \t",area_number/(clock-init_clock));
    printf("%f \n",area_number/count);
#endif
/*=================================================*/

  }/* end for */
    
  /* print results */

#ifndef DEBUG
  /* 
  *  need to compute width if "for loop" was exited 
  *  because the maximum number of batched were reached                
  */
  if (batch > MAX_BATCHES) {  
    n = MAX_BATCHES;              /* the number of samples */
    t = idfStudent(n - 1,u);      /* critical value of t   */
    s = sqrt(sumsqr_num_jobs/n);  /* standard deviation    */
    w = t*s/sqrt(n - 1);
  }

  arrival_rate = num_arrivals/clock;

  printf("\nSteady-State Simulation\n");
  printf("  sample points......:  %ld\n",n);
  printf("  confidence level...:  %g%%\n",LOC*100.0);
  printf("  confidence interval:  +/- %g%%\n",INTERVAL_WIDTH*100.0);
  if (w/mean_num_jobs > INTERVAL_WIDTH) {
    printf("\nMeasures did not reach desired interval width.\n");
  }
  printf("\n");
  printf("Expected number of jobs in the system:  %.4f +/- %.4f\n",
          mean_num_jobs, w);
  printf("Expected wait time of a job..........:  %.4f +/- %.4f\n",
          mean_num_jobs/arrival_rate, w/arrival_rate);

#endif /* endif DEBUG */
  return(0);
}

the       *
*            simulation will not terminate.                                   *
*               qnsim-ts.c010060000000620000062000000233110633246122600126040ustar00rljones00000400000021/******************************************************************************
*  Module:   qnsim-ts.c                                                       *
*                                                                             *
*  Author:   Rob Jones                                                        *
*                                                                             *
*  Purpose:  CSci 726 Discrete-Event Simulation: PROJECT #3                   *
*            Provides main simulation program for a general-purpose           *
*            TRANSIENT-STATE SIMULATION of a queuing network consisting       *
*            of single server nodes.                                          *
*                                                                             *
*  Version:  5-02-97                                                          *
*******************************************************************************/

#include "qnet.h"
#include "queue.h"
#include "misc.h"

/* SIMULATION PARAMETERS: */

#define MAX_REPLICATIONS    1000            /* max number of replications     */
#define MAX_EVENTS          100000          /* maximum events per replication */
#define LOC                 0.95            /* level of confidence            */
#define PREC                1.0e-2          /* for rounding data to 1/1000    */
#define INFINITY            1e300           /* a large number                 */

double *future_events;   /* future-events list */

void ProcessArrival(long i, double time)
/******************************************************************************
  Auxilary function used to service the arrival of a job to node 'i' at the
  current 'time' if the node is idle, otherwise the job is put into the queue. 
  If the job is serviced, the job's departure is also scheduled.
*******************************************************************************/
{
  extern rv_func    *random_time;  /* sample function  */
  extern actvty     *status;       /* server status    */
  extern queue_type *queue;        /* service queue    */
  double job_time   = 0;           /* job service time */

  if (status[i] == IDLE) { /* if idle then service job */
    status[i] = BUSY;
    SelectStream(i);
    future_events[i] = time + random_time[i].func();
  } else { /* otherwise, add job to queue */

#ifdef SJF_QUEUE /* if SJF then sample/store service time */
    SelectStream(i);
    job_time = random_time[i].func(); 
#endif

    Insert(&queue[i],job_time);
  }
}

void ServiceJob(long i, double time)
/******************************************************************************
  Auxilary function used to service the next job in the queue of node 'i' at 
  the current 'time' thereby scheduling the departure of the job.                  
*******************************************************************************/
{
  extern rv_func    *random_time;  /* sample function  */
  extern actvty     *status;       /* server status    */
  extern queue_type *queue;        /* service queue    */
  double job_time   = 0;           /* job service time */

  Remove(&queue[i],&job_time);

#ifdef SJF_QUEUE /* if SJF then service time is already stored */

  future_events[i] = time + job_time;

#else /* otherwise sample service-time function */

  SelectStream(i);
  future_events[i] = time + random_time[i].func();

#endif
  status[i] = BUSY;
}

int main(void)
/******************************************************************************
  MAIN PROGRAM
/******************************************************************************
*******************************************************************************/
{
  extern qnt        type;           /* either OPEN or CLOSED                  */
  extern int        num_nodes;      /* number of service nodes                */
  extern rv_func    *random_time;   /* service time random variate functions  */
  extern queue_type *queue;         /* queue for each service node            */
  extern actvty     *status;        /* status of each server: {IDLE,BUSY}     */
  int    node;                      /* service node index                     */
  double clock;                     /* current simulation time                */
  long   i, j;                      /* general-purpose indices                */
  long   index;                     /* replication index                      */
  long   current, next;             /* service node indices                   */
  long   seed = 123456789;          /* random number seed                     */
  long   n;                         /* number of samples                      */
  double u = 1.0 - 0.5*(1.0 - LOC); /* interval parameter                     */ 
  double s, t, diff;                /* used to compute interval estimate      */             
  long   num_arrivals       = 0;    /* counts # of external job arrivals      */
  long   num_departures     = 0;    /* counts # of external job departures    */
  long   num_jobs;                  /* total number of jobs in system         */
  double arrival_rate;              /* average external arrival rate          */
  double departure_rate;            /* average external departure rate        */
  double mean_arrivals      = 0.0;  /* mean # of arrivals until steady state  */
  double sumsqr_arrivals    = 0.0;  /* sum of squares to compute variance     */
  double w;                         /* confidence interval half width         */                
  
  /* initialize */

  Network();  /* get specification of queuing network  */
  Init();     /* initialize of network data structures */ 

  /* create future-event list */
  future_events = (double *)calloc(num_nodes,sizeof(double)); 
  if (future_events == NULL) {
    error(MEM_ERR);
  }

  /* begin simulation */

  for (index = 1; index <= MAX_REPLICATIONS; index++) {

    /* re-initialize the state and statistics for each replication */ 

    /* pick a different seed for each replication */
    SelectStream(0); GetSeed(&seed); PlantSeeds(seed);

    Initialize();          /* reset the initial state of network */

    clock           = 0.0;   
    num_arrivals    = 0;
    num_departures  = 0;
    arrival_rate    = 0.0; /* to get started, make arrival rate */
    departure_rate  = 1.0; /*   different from departure_rate   */

    /* schedule first events */
    if (type == OPEN) {
      SelectStream(0);
      future_events[0] = random_time[0].func();
    } else {
      future_events[0] = INFINITY;
    }
    num_jobs = 0;
    for (i = 1; i < num_nodes; i++) {
      if (IsEmpty(&queue[i]) == FALSE) {
        num_jobs += Number(&queue[i]);
        ServiceJob(i,clock);
      } else {
        status[i]        = IDLE;
        future_events[i] = INFINITY;
      }
    }
    /* 
    *  To estimate the number of external arrivals before the network
    *  reaches steady state, the stopping criteria "flow in = flow out" 
    *  will be used.  To do the comparison, the average arrival rate 
    *  and average departure rate are both rounded to 1/100 precision.  
    */
    while ((arrival_rate != departure_rate) && (num_arrivals < MAX_EVENTS)) {

      /* get next (most imminent) event */
      current = 0; 
      for (j = 0; j < num_nodes; j++) {
        if (future_events[j] < future_events[current]) {
          current = j;
        }
      }
      clock = future_events[current]; /* advance the clock */

      /* if event was an outside arrival then schedule a new one */
      if (current == 0) {
        SelectStream(0);
        future_events[current] = clock + random_time[current].func();
        num_arrivals++; 
        num_jobs++;     /* one more job in system */
      } else { /* process the departure */    
        if (IsEmpty(&queue[current]) == FALSE) { 
          ServiceJob(current,clock); /* service next job in queue */
        } else {
          status[current] = IDLE;
          future_events[current] = INFINITY;
        }
      }
      /* place job in a destination service node */

      next = GetNextNode(current); 

      if (next == 0) { /* if departure from system then */
        num_departures++;
        num_jobs--;           /* one less job in system */
      } else { 
        ProcessArrival(next,clock);
      }          

      /* compute/round arrival/departure rates */
      arrival_rate   = (double)num_arrivals/clock;
      arrival_rate   = (double)(((long)(arrival_rate/PREC + 0.5))*PREC);
      departure_rate = (double)num_departures/clock;
      departure_rate = (double)(((long)(departure_rate/PREC + 0.5))*PREC);

/*======================================================*/
#ifdef DEBUG
      printf("%ld \t %ld \t %f \t %f \t",
             num_arrivals,num_departures,arrival_rate,departure_rate);
      printf("[%ld:%ld:%ld:%ld:%ld]",
             Number(&queue[1]),
             Number(&queue[2]),
             Number(&queue[3]),
             Number(&queue[4]),
             Number(&queue[5]));
      printf("\t %ld",index);
      printf("\t %f",mean_arrivals);
      printf("\n");
#endif
/*======================================================*/

    } /*end while*/ 

    if (num_arrivals == MAX_EVENTS) {
      error("Maximum number of events was reached!\n");
      exit(1);
    }

    /* compute mean number of external arrivals until steady state */
    diff = num_arrivals - mean_arrivals;
    sumsqr_arrivals += diff*diff*(index - 1.0)/index;
    mean_arrivals   += diff/index;

  }/* end for */
    
  /* print results */

  n = index-1;                    /* the number of samples */
  t = idfStudent(n - 1,u);        /* critical value of t   */
  s = sqrt(sumsqr_arrivals/n);    /* standard deviation    */
  w = t*s/sqrt(n - 1);            /* interval half width   */

#ifndef DEBUG

  printf("\nTransient Simulation:\n\n");
  printf("Expected time to steady state:  %.4f +/- %.4f\n\n", 
          mean_arrivals,w);
#endif 
  return(0);
}

e, otherwise the job is put into the queue. 
  If the job is serviced, the job's departure is also scheduled.
*******************************************************************************/
{
  extern rv_func    *random_time;  /* sample function  */
  extern actvty     *status;       /* server status    */
  qnet.c010060000000620000062000000146460633241466100120140ustar00rljones00000400000021/******************************************************************************
*  Module:   qnet.c                                                           *
*                                                                             *
*  Author:   Rob Jones                                                        *
*                                                                             *
*  Purpose:  CSci 726 Discrete-Event Simulation: PROJECT #3                   *
*            Provides the data structures and operations for the              *
*            construction and simulation of a general queuing network.        *
*                                                                             *
*  Version:  4-14-97                                                          *
*******************************************************************************/

#include "qnet.h"
#include "queue.h"
#include "misc.h"

/* GLOBAL DATA: */

qnt        type         = CLOSED;       /* assume closed network              */ 
int        num_nodes    = 0;            /* number of service nodes            */
queue_type *queue       = NULL;         /* no. jobs in each service queue     */
actvty     *status      = NULL;         /* status of each service node        */
double     **P          = NULL;         /* commulative prob matrix            */
rv_func    *random_time = NULL;         /* list of functions that return the  */
                                        /* arrival/service time for each node */
char Use_Error[] 
     = "Must first define the number of nodes with function \"Nodes\"\n";

void Init()
/******************************************************************************
  called by main program to initialize data structures
*******************************************************************************/
{
  int i, j;

  if (num_nodes > 0) {
    /* consistency check */
    if (type == OPEN && random_time[0].func == NULL) {
      error("Must specify an arrival-time function for open networks.");
    }
    for (i = 1; i <= num_nodes; i++) {
      if (random_time[i].func == NULL) {
        error("Must specify a service-time function for every service node.");
      }
    }
    /* compute cumulative probabilities across each row of P matrix */
    for (i = 0; i < num_nodes; i++) {
      for (j = 1; j < num_nodes; j++) {
        P[i][j] += P[i][j-1];
      }
    }
  } else { /* function Network was not used properly */
    error("Must specify queuing network with function \"Network\".\n");
  }
  
  
}

void Initialize()
{
  long i;

  /* empty out each queue */
  for (i = 1; i < num_nodes; i++) {
    FlushQueue(&queue[i]); 
  }
  /* re-initialize each queue */
  InitialState();
}

void Nodes(int n)
/******************************************************************************
  declares the number of service nodes and allocates/initializes 
  the required data structures 
*******************************************************************************/
{
  int i;

  /* constraint checks */
  if (n <= 0) {
    error("Must declare at least 1 service node.\n");
  }
  num_nodes = n + 1;  /* additional node for external I/O */
  /* 
  *  create probability matrix 
  */
  P = (double **)calloc(num_nodes,sizeof(double *)); /* allocate the rows    */
  if (P == NULL) {
    error(MEM_ERR);
  }
  for (i = 0; i < num_nodes; i++) {                  /* allocate the columns */
    P[i] = (double *)calloc(num_nodes,sizeof(double)); 
    if (P[i] == NULL) {
      error(MEM_ERR);
    }
  } 
  /* 
  *  create list of random variate functions to call to compute
  *  the arrival/service time of each node
  *  note: calloc initializes random_time[] to NULL
  */ 
  random_time = (rv_func *)calloc(num_nodes,sizeof(rv_func));
  if (random_time == NULL) {
    error(MEM_ERR);
  }
  /* 
  *  create list indicating the status of each service node 
  *  note: calloc initializes status[] to IDLE
  */
  status = (actvty *)calloc(num_nodes,sizeof(actvty));
  if (status == NULL) {
    error(MEM_ERR);
  }
  /* 
  *  create list of pointers to each service queue 
  */
  queue = (queue_type *)calloc(num_nodes,sizeof(queue_type));
  if (queue == NULL) {
    error(MEM_ERR);
  }
  /* initialize each queue */
  for (i = 1; i < num_nodes; i++) {
    CreateQueue(&queue[i]); 
  }
}

void Connect(int i, int j, double p)
/******************************************************************************
  user function that connects service node 'i' to node 'j' with probability 'p'
*******************************************************************************/
{
  if (P != NULL) {
    P[i][j] = p;
  } else {
    error(Use_Error);
  }
}

void Arrival(double (*func)())
/******************************************************************************
  user function that specifies the external inter-arrival time function 
*******************************************************************************/
{
  if (random_time != NULL) {
    type = OPEN;
    random_time[0].func = func;
  } else {
    error(Use_Error);
  }
} 

void Service(int i, double (*func)())
/******************************************************************************
  user function that assigns a service-time function to node 'i' 
*******************************************************************************/
{
  if (i <= 0) {
    error("Service node identifiers must be greater than zero.");
  } else if (random_time == NULL) {
    error(Use_Error);
  } else {
    random_time[i].func = func;
  }
}

void Initial(int i, long j)
/******************************************************************************
  user function that initializes service node 'i' with 'j' jobs
*******************************************************************************/
{
  double job_time = 0;  /* job service time */
  long   k;

  if (queue == NULL) {
    error(Use_Error);
  } else {

#ifdef SJF_QUEUE /* if SJF then sample/store service time */
    SelectStream(i);
    for (k = 0; k < j; j++) {
      job_time = random_time[i].func();
      Insert(&queue[i],job_time);
    }
#else /* otherwise, just store the number of jobs */
    Insert(&queue[i],j);
#endif
  }
}

int GetNextNode(int i)
/******************************************************************************
  returns the destination node that receives the output of service node 'i'
*******************************************************************************/
{
  int    j;
  double u;

  SelectStream(i);
  u = Random();
  j = 0;
  while (u > P[i][j]) {
    j++;
  }
  return(j);
}

qnet.h010060000000620000062000000017420633241471500120120ustar00rljones00000400000021/******************************************************************************
*  File: qnet.h                                                               *
*******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "rngs.h"     /* random number generation package        */ 
#include "rvgs.h"     /* functions for random variate generation */
#include "rvms.h"     

typedef enum {OPEN, CLOSED} qnt;
typedef enum {IDLE, BUSY} actvty;

typedef struct {double (*func)();} rv_func;
  
/* INTERNAL OPERATIONS: */

void Init();
int  GetNextNode(int i); 

/* USER OPERATIONS: */

void Network();                           
void Nodes(int num);                      
void Connect(int from, int to, double p); 
void Service(int i, double (*func)());    
void Arrival();                           
void Initialize();              
void InitialState();              
void Initial(int i, long j);              

OSED} qnt;
typedef enum {IDLE,queue.c010060000000620000062000000055340633241213600121600ustar00rljones00000400000021/******************************************************************************
*  Module:   queue.c                                                      *
*                                                                             *
*  Author:   Rob Jones                                                        *
*                                                                             *
*  Purpose:  CSci 726 Discrete-Event Simulation: PROJECT #3                   *
*            Provides the queue structure and operations for the simulator.   *
*                                                                             *
*  Version:  5-01-97                                                          *
*******************************************************************************/

#include <stdlib.h>
#include "queue.h"
#include "misc.h"

#ifdef SJF_QUEUE

list *free_nodes = NULL;


list *New()
{
  list *ptr;

  if (free_nodes == NULL) {
    ptr = (list *)malloc(sizeof(list));
    if (ptr == NULL) {
      error(MEM_ERR);
    }
  } else {
    ptr        = free_nodes;
    free_nodes = free_nodes->next;
  }
  ptr->item = (item_type)0;
  ptr->next = NULL;
  return(ptr);
}

void Free(list *ptr)
{
  ptr->next  = free_nodes;
  free_nodes = ptr;
}

void CreateQueue(queue_type *q)
{
  q->contents = NULL;
  q->number   = 0;
}

void DeleteQueue(queue_type *q)
{
  list *ptr, *nxt;

  ptr = First(q); 
  while (ptr != NULL) {
    nxt = Next(ptr);
    Free(ptr);
    ptr = nxt;
  }
  ptr = free_nodes; 
  while (ptr != NULL) {
    nxt = Next(ptr);
    Free(ptr);
    ptr = nxt;
  }
  q->contents = NULL;
  free_nodes  = NULL;
  q->number   = 0;
}

void FlushQueue(queue_type *q)
{
  list *ptr, *nxt;

  ptr = First(q);
  while (ptr != NULL) {
    nxt = Next(ptr);
    Free(ptr);
    ptr = nxt;
  }
  q->contents = NULL;
  q->number   = 0;
}

bool IsEmpty(queue_type *q)
{
  if (q->number == 0) {
    return(TRUE);
  } else {
    return(FALSE);
  }
}

long Number(queue_type *q)
{
  return(q->number);
}

void Insert(queue_type *q, item_type v)
{
  list *ptr, *nxt; 
  list *new_entry = New();

  new_entry->item = v;
  if (q->contents == NULL) { 
    q->contents = new_entry;
  } else if (v <= q->contents->item) { 
    new_entry->next = q->contents;
    q->contents     = new_entry;
  } else {
    for (ptr = q->contents; ptr != NULL; ptr = nxt) {
      nxt = ptr->next;
      if (nxt == NULL) {
        ptr->next = new_entry;
      } else if (v <= nxt->item) {
        new_entry->next = nxt;
        ptr->next       = new_entry;
        break;
      }
    }
  }
  q->number++;
}

void Remove(queue_type *q, item_type *v)
{
  list *ptr = q->contents;

  if (q->contents != NULL) {
    (*v) = q->contents->item;
    q->contents = q->contents->next;
    q->number--;
    Free(ptr);
  }
}

list *First(queue_type *q)
{
  return(q->contents);
}

list *Next(list *l)
{
  return(l->next);
}

#endif
queue.h010060000000620000062000000030700633241210100121460ustar00rljones00000400000021/******************************************************************************
*                                                                             *
*  queue.h                                                                    *
*                                                                             *
*  Version:  30-April-97                                                      *
*                                                                             *
*******************************************************************************/
#ifndef _queue_h
#define _queue_h

#include "misc.h"

typedef double item_type;

#ifdef SJF_QUEUE /* SHORTEST JOB FIRST QUEUE */

/* QUEUE DATA STRUCTURES */

struct lst;

typedef struct lst {
  item_type  item;
  struct lst *next;
} list;

typedef struct {
  list *contents;    
  long number;     
} queue_type;

/* SJF QUEUE OPERATIONS */

void CreateQueue(queue_type *);
void DeleteQueue(queue_type *);
void FlushQueue(queue_type *);
bool IsEmpty(queue_type *);
long Number(queue_type *);
void Insert(queue_type *, item_type);
void Remove(queue_type *, item_type *);
list *First(queue_type *);
list *Next(list *);

#else /* ASSUME SIMPLE FIFO AS DEFAULT */

/* QUEUE DATA STRUCTURE */

typedef long queue_type;

/* FIFI QUEUE OPERATIONS */

#define CreateQueue(q)   (*q) = 0
#define DeleteQueue(q)   (*q) = 0
#define FlushQueue(q)    (*q) = 0
#define IsEmpty(q)       (((*q) == 0) ? TRUE : FALSE)
#define Number(q)        (*q)
#define Insert(q,v)      ((*q)++)
#define Remove(q,v)      ((*q)--)

#endif

#endif /* _queue_h */

misc.c010060000000620000062000000015130633175672000117710ustar00rljones00000400000021/******************************************************************************
*                                                                             *
*  mics.c                                                                     *
*                                                                             *
*  Version:  30-April-97                                                      *
*                                                                             *
*******************************************************************************/

void error(const char message[])
/******************************************************************************
  prints error message and then exits program
*******************************************************************************/
{
  printf("%s",message);
  exit(0);
}


misc.h010060000000620000062000000016730633175671200120060ustar00rljones00000400000021/******************************************************************************
*                                                                             *
*  mics.c                                                                     *
*                                                                             *
*  Version:  30-April-97                                                      *
*                                                                             *
*******************************************************************************/

#ifndef _misc_h
#define _misc_h

typedef enum {FALSE = 0, TRUE = 1} bool;

#define max(x,y)   (((x) > (y)) ? (x) : (y))
#define min(x,y)   (((x) < (y)) ? (x) : (y))

/*
*  When fatal error occurs call function 'error'
*  with stnd messages...
*/
#define MEM_ERR    0
#define FIL_ERR    1
/*
*  or pass in your own,
*  error will then call exit(0).
*/
void error(char *);

#endif /* _misc_h */
example954.c010060000000620000062000000045410633241373300127320ustar00rljones00000400000021/******************************************************************************
*                                                                             *
*  File:  example954.c                                                        * 
*                                                                             *
*  Project #3 Example:                                                        *
*  Queuing netork description and stochastic specification                    *
*  for a 5 node network in example 9.5.4 of notes.                            *
*                                                                             *
*******************************************************************************/

#include "qnet.h"
#include "const.h"   /* constant model parameters */

#ifdef JACKSON
double service1()
{
  return(Exponential(1.0/nu1));
}
double service2()
{
  return(Exponential(1.0/nu2));
}
double service3()
{
  return(Exponential(1.0/nu3));
}
double service4()
{
  return(Exponential(1.0/nu4));
}
double service5()
{
  return(Exponential(1.0/nu5));
}
#else
double service1()
{
  return(Erlang(5,0.14));
}
double service2()
{
  return(Erlang(4,0.20));
}
double service3()
{
  return(Erlang(5,0.14));
}
double service4()
{
  return(Erlang(4,0.20));
}
double service5()
{
  return(Erlang(4,0.20));
}
#endif

double Expo()
{
  return(Exponential(1.0/lambda));
}


void Network()
/******************************************************************************
  define the queuing network here
*******************************************************************************/
{
  /* declare 5 service nodes */
  Nodes(5);

  /* specify the network connections */
  Connect(0,1,0.4);
  Connect(0,3,0.6);
  Connect(1,2,0.8);
  Connect(1,3,0.2);
  Connect(2,0,0.2);
  Connect(2,1,0.4);
  Connect(2,5,0.4);
  Connect(3,4,1.0);
  Connect(4,2,0.2);
  Connect(4,5,0.8);
  Connect(5,0,1.0);

  /* specify the external inter-arrival time */
  Arrival(Expo);

  /* specify the service times */
  Service(1,service1);
  Service(2,service2);
  Service(3,service3);
  Service(4,service4);
  Service(5,service5);
}

void InitialState()
/******************************************************************************
  define the initial state of the queuing network here
*******************************************************************************/
{
  /* network is initially empty */
}