®PL168.¯

The following files accompany the article entitled "The Qsim
Simulation Toolkit," by Roy E. Kimbrell, Linda Correll, and Robert
Bass, BYTE July 1989, page 259.




==============================

          EG1.C

==============================


/* first example in the article */

#include <stdio.h>
#include "sim.h"
#include "sim_lib.h"
#include <float.h>

DEFINE_CREATE(customers);

DEFINE_QUEUE(q_loan_officer);
DEFINE_QUEUE(q_Biff);
QUEUE_STRUCT *q_array[]={&q_loan_officer_q,&q_Biff_q};
#define NUM_QUEUES	(sizeof(q_array)/sizeof(QUEUE_STRUCT *))

DEFINE_SERVICE(s_loan_officer);
DEFINE_SERVICE(s_Biff);
SERV_DATA *s_array[]={&s_loan_officer_s,&s_Biff_s};
#define NUM_SERVS	(sizeof(s_array)/sizeof(SERV_DATA *))

void decision_1(ENTITY *);
void decision_2(ENTITY *);
void term(ENTITY *);
void stop(void);

void main(int ac,char **av)
{
long runtime=0;
extern long strtol();
        if (ac > 1) runtime = strtol(av[1],0,0);
	SCHEDULE(customers,0,0);
	SCHEDULE(stop,0,(double)runtime);
	engine();
	}

CREATE(customers,now,0,expon(15.0),q_loan_officer)

QUEUE(q_loan_officer,s_loan_officer)
SERVICE(s_loan_officer,2,unfrm(20.0,30.0),decision_1)

void decision_1(ENTITY *entity)
{
	TRACE(decision_1);        /* debug code */
	PR_ENTITY(entity);        /* debug code */
	if (drand() < .6) term(entity);
	else q_Biff(entity);
	}

QUEUE(q_Biff,s_Biff)
SERVICE(s_Biff,1,normal(45.0,10.0),decision_2)

void decision_2(ENTITY *entity)
{
	TRACE(decision_2);       /* debug code */
	PR_ENTITY(entity);       /* debug code */
	if (drand()	< .85) term(entity);
	else q_loan_officer(entity);
	}

static systime_t total_time, max_time, min_time = FLT_MAX;
static unsigned count;

void term(ENTITY *entity)
{
systime_t tis;

	TRACE(term);             /* debug code */
	PR_ENTITY(entity);       /* debug code */
	count++;
	tis = now - entity->time;
	total_time += tis;
	if (max_time < tis) max_time = tis;
	if (min_time > tis) min_time = tis;
	free(entity);
	}

void stop(void)
{
int i;

	TRACE(stop);
	printf("Total time in system =   %10.4f, count = %d\n",
		total_time,count);
	printf("Average time in system = %10.4f\n",total_time/count);
	printf("Max time in system =     %10.4f\n",max_time);
	printf("Min time in system =     %10.4f\n",min_time);
	printf("\nSERVICES:  name|total|total busy|utilization|\n\
---------------|-----|----------|-----------|\n");
	for (i=0;i<NUM_SERVS;i++)
		printf("%15.s|%5.ld|%10.4f| %10.4f|\n",
			s_array[i]->name,
			s_array[i]->total,
			s_array[i]->total_busy,
			(s_array[i]->srvtime)
			       ? s_array[i]->total_busy/s_array[i]->srvtime
			       : 0
			);
	printf("\nQUEUES:    name|max_len|cur_len|total_wait|count|\
average_wait|\n\
---------------|-------|-------|----------|-----|------------|\n");
	for (i=0;i<NUM_QUEUES;i++)
		printf("%15.s|%7.d|%7.d|%10.4f|%5.d|  %10.4f|\n",
			q_array[i]->name,
			q_array[i]->max_len,
			q_array[i]->cur_len,
			q_array[i]->total_wait,
			q_array[i]->count,
			(q_array[i]->count)
				? q_array[i]->total_wait/q_array[i]->count
				: 0
			);
	exit(0);
	}



==============================

          ERLANG.C

==============================



#include <math.h>
#include "sim_lib.h"

double erlang(double u,unsigned k)
{
double r=1;
unsigned i;

	for (i=1; i<k; i++) r *= drand();
	return -u*log(r);
	}


==============================

          EXPON.C

==============================



#include <math.h>
#include "sim_lib.h"

double expon(double mean)
{
	return (-mean*log(drand()));
	}



==============================

          NORMAL.C

==============================


#include <math.h>
#include "sim_lib.h"

static flag=0;
static double norm2, oldu, olds;

double normal(double u,double s)
{
double r1, r2, a, b, w=2, norm1, t;

	if (flag & oldu == u & olds == s){
		flag = 0;
		return norm2;
		}
	while (w > 1){
		r1 = drand();
		r2 = drand();
		a = 2.0 * r1 - 1.0;
		b = 2.0 * r2 - 1.0;
		w = a*a + b*b;
		}
	t = sqrt(-2.0 * log(w)/w) * s;
	norm1 = a*t + u;
	norm2 = b*t + u;
	flag = 1;
	oldu = u; olds = s;
	return norm1;
	}


==============================

          RLNORM.C

==============================


#include <math.h>
double normal(double,double);

double rlnorm(double u,double s)
{
double sigma, mu;

	sigma = log(s*s/(u*u) + 1.0);
	mu = log(u) - sigma/2;
	return exp(normal(mu,sqrt(sigma)));
	}




==============================

          SIM.C

==============================



/* sim.c -- simulation system code */

#include <stdio.h>
#include <stdlib.h>

#define DEF_SPACE
#include "sim.h"

void engine(void)
{
EVENT *event;

	for(;;){
		TRACE(engine);
		if (!(event = nextevent())) return;
		if (event->time > now) now = event->time;
		(*event->f)(event->entity);
		free(event);
		}
	}

EVENT *nextevent(void)
{
EVENT *top;
extern EVENT *sched;
extern systime_t now;

	TRACE(nextevent);
	if (top = sched) sched = sched->next;
	return top;
	}

ENTITY *create(systime_t time,double feature)
{
ENTITY *new;
extern id_t entity_id;

	TRACE(create);
	new = (ENTITY *)calloc(1,sizeof(ENTITY));
	new->id = entity_id++;
	new->time = time;
	new->feature[0] = feature;
	return new;
	}

void sdump(void)
{
EVENT *sp;
extern EVENT *sched;

	sp = sched;
	while (sp){
#ifdef DEBUG
		printf("\tevent=%x, time=%f, f=%s, next=%x, entity=%x\n",
			sp,sp->time,sp->fs,sp->next,sp->entity);
#else
		printf("\tevent=%x, time=%f, next=%x, entity=%x\n",
			sp,sp->time,sp->next,sp->entity);
#endif
		if (sp->entity)
			printf("\tevent->entity->id=%ld, time=%f, feature[0]=%d\n",
				sp->entity->id,sp->entity->time,sp->entity->feature[0]);
		printf("\n");
		sp = sp->next;
		}
	}

#ifdef DEBUG
void schedule(void (*f)(), char *fs, ENTITY *entity, systime_t time)
#else
void schedule(void (*f)(), ENTITY *entity, systime_t time)
#endif
{
EVENT *sp, *event, *temp, *prev;
extern EVENT *sched;

	TRACE(schedule);
	event = (EVENT *)calloc(1,sizeof(EVENT));
	event->time = time;
#ifdef DEBUG
	event->fs = fs;
#endif
	event->f = f;
	event->entity = entity;
	if (!sched){
		sched = event;
		SDUMP();
		return;
		}
	if (sched->time > time){
		temp = sched;
		sched = event;
		event->next = temp;
		SDUMP();
		return;
		}
	sp = sched;
	while (sp && time >= sp->time){
		prev = sp;
		sp = sp->next;
		}
	prev->next = event;
	event->next = sp;
	SDUMP();
	return;
	}

void qdump(QUEUE_STRUCT *q)
{
ENTITY * ep;

	printf("\t* qdump: max= %d, current = %d, min=%d *\n",
		q->max_len,q->cur_len,q->min_len);
	ep = q->top;
	while (ep){
		PR_ENTITY(ep);
		ep = ep->next;
		}
	printf("\t* end of dump *\n");
	}


ENTITY *topq(QUEUE_STRUCT *q)
{
	return q->top;
	}

void nq(q,entity)
	QUEUE_STRUCT * q;
	ENTITY * entity;
{
	entity->next = (ENTITY *)0;
	if (q->end){
		q->end->next = entity;
		q->end = entity;
		}
	else
		q->top = q->end = entity;
	q->count++;
	entity->qtime = now;
	q->cur_len++;
	if (q->max_len < q->cur_len) q->max_len = q->cur_len;
#ifdef DEBUG
	qdump(q);
#endif
	}

ENTITY *dq(QUEUE_STRUCT *q)
{
ENTITY * p;

	p = q->top;
	if (p) q->top = q->top->next;
	if (p == q->end) q->end = (ENTITY *)0;
	if (p){
		q->total_wait += now - p->qtime;
		q->cur_len--;
		if (q->min_len > q->cur_len) q->min_len = q->cur_len;
		}
#ifdef DEBUG
	qdump(q);
#endif
	return p;
	}



==============================

          SIM.H

==============================



/* sim.h -- simulation system definitions */

typedef long id_t;
typedef double systime_t;

struct entity {
	id_t id;
	systime_t time, qtime;
	double feature[1];
	struct entity * next;
	};

typedef struct entity ENTITY;

struct event{
	systime_t time;
#ifdef DEBUG
	char *fs;
#endif
	void (*f)();
	ENTITY *entity;
	struct event *next;
	};

typedef struct event EVENT;

struct queue{
	char * name;
	ENTITY *top, *end;
	unsigned short max_len, cur_len, min_len, count;
	systime_t total_wait;
	};

typedef struct queue QUEUE_STRUCT;

struct serv_data{
	char * name;
	unsigned long total;
	double total_busy, srvtime;
	};

typedef struct serv_data SERV_DATA;

void sdump();
#ifdef DEBUG
void schedule(void(*)(),char *,ENTITY *,systime_t /* time */);
#else
void schedule(void(*)(),ENTITY *,systime_t /* time */);
#endif
void engine();
EVENT *nextevent();
ENTITY *create(systime_t /* time of creation */,double /* feature */);
ENTITY 	*topq(QUEUE_STRUCT * /* entity queue */),
		*dq(QUEUE_STRUCT * /* entity queue */);
void nq(QUEUE_STRUCT * /* entity queue */, ENTITY *);

#ifndef DEF_SPACE
extern double now; /* current time in system */
extern EVENT *sched;
extern id_t entity_id;
#else
double now; /* current time in system */
EVENT *sched;
id_t entity_id;
#endif

#ifdef DEBUG
#define TRACE(name)	printf("%f " #name "\n",now);
#define SDUMP()	sdump()
#define PR_ENTITY(entity) \
	if (entity) printf("\tentity: id=%ld, time=%f, feature=%f, next=%x\n",\
			entity->id,entity->time,entity->feature[0],entity->next);\
	else printf("\tentity=0\n");
#else
#define TRACE(name)
#define SDUMP()
#define PR_ENTITY(entity)
#endif

#ifdef DEBUG
#define SCHEDULE(name,entity,time)	\
	schedule(name,#name,(ENTITY *)(entity),(systime_t)(time));
#else
#define SCHEDULE(name,entity,time)	\
	schedule(name,(ENTITY *)(entity),(systime_t)(time));
#endif

#define DEFINE_CREATE(name)		\
	void name();

#define CREATE(name,create_time,feature,create_freq,service)	\
void name()\
{\
extern systime_t now;\
	TRACE(name);\
	service(create((systime_t)create_time,(double)feature));\
	SCHEDULE(name,0,now+create_freq);\
	}

#define DEFINE_SERVICE(name)		\
	systime_t name(ENTITY *);\
	SERV_DATA name##_s={#name};

#define SERVICE(name,nservers,delay,next)	\
double name(entity)\
	ENTITY *entity;\
{\
static systime_t srvtime[nservers], wait_time;\
extern systime_t now;\
unsigned short i;\
	TRACE(name);\
	PR_ENTITY(entity);\
	for (i=0;i<nservers;i++) if (srvtime[i] <= now) break;\
	if (i == nservers) return -1;\
	/* note: delay may be a function call */\
	wait_time = delay;\
	srvtime[i] = now + wait_time;\
	SCHEDULE(next,entity,srvtime[i]);\
	/* compute statistics -- \
        only total served and total busy time done for now */\
	name##_s.total++;\
	name##_s.total_busy += wait_time;\
	name##_s.srvtime=srvtime[i];\
	return srvtime[i];\
	}

#define DEFINE_QUEUE(name)		\
	void name(ENTITY *);\
	QUEUE_STRUCT name##_q={#name};

#define QUEUE(name,service)		\
void name(entity)\
	ENTITY *entity;\
{\
systime_t srvtime;\
ENTITY * top;\
	TRACE(name);\
	PR_ENTITY(entity);\
	if (entity) nq(&name##_q,entity);\
	if ((top = topq(&name##_q)) &&\
			(srvtime=service(top)) >= 0){\
		dq(&name##_q);\
		SCHEDULE(name,0,srvtime);\
		}\
	/* compute statistics */\
	}



==============================

          SIM_LIB.H

==============================



/*
			sim_lib.h

function definitions for the statistical simulation library

u - mean
s - standard deviation
k - number of samples
a, b - limits
mode - middle or peak of a triangular distribution

*/

double erlang(double u, unsigned k);
double expon(double u);
double normal(double u, double s);
double rlnorm(double u, double s);
double triag(double a, double mode, double b);
double unfrm(double a, double b);
double drand(void);


==============================

          TRIAG.C

==============================



#include <math.h>
#include "sim_lib.h"

double triag(double a,double mode,double b)
{
double r;

	r = drand();
	if (r <= (mode-a)/(b-a)) return a + sqrt((mode-a)*(b-a)*r);
	else return b - sqrt((b-mode)*(b-a)*(1-r));
	}


==============================

          UNFRM.C

==============================


#include <math.h>
#include <stdlib.h>
#include "sim_lib.h"

#define min(a,b)        (((a) < (b)) ? (a) : (b))

double unfrm(double a,double b)
{
	return (drand()*fabs(a-b)+min(a,b));
	}