discrete-event simulation package in c or c++?

Dave Jones djones at megatest.UUCP
Sun May 8 14:18:28 AEST 1988


I'll let you look at one I wrote.  Even though it's not very big,
it's a little tricky.  It took me a day and a half to
write it.  It's interesting to compare it to the "task" package that 
comes with the ATT C++.

[ I've never actually read anything about this subject, so I would 
be very happy to get some constructive hints for improvement. ]

DEMONSTRATION PURPOSES ONLY.  This is not a "software release". 

It runs under Sun3 OS.  I can't think of any reason why it would not 
work on any other system that has a standard C library, but then, 
that may only be because I haven't thought of it.  The tricky bit 
is to save and restore process-stacks and registers.  UNIX has 
alloca() and setjmp()/longjmp(). Just what the doctor ordered.

I didn't include the queue package Queue, or the priority-queue
package PQ, becuase they require more packages, etc., etc..,
and besides, this is only a demo, right?


#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#		"End of shell archive."
# Contents:  sim2_demo.c sim2.h sim2.c
# Wrapped by djones at goofy on Sat May  7 20:38:14 1988
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f sim2_demo.c -a "${1}" != "-c" ; then 
  echo shar: Will not over-write existing file \"sim2_demo.c\"
else
echo shar: Extracting \"sim2_demo.c\" \(2844 characters\)
sed "s/^X//" >sim2_demo.c <<'END_OF_sim2_demo.c'
Xstatic char
XRCSHeader[] = "$Header$";
Xstatic char
XCopyright[] = "Copyright (C) 1988 by Megatest Corporation All Rights Reserved";
Xstatic char
XTheAuthor[] = "Dave Jones   (djones at goofy)";
X#include "sim2.h"
X#include <stdio.h>
X
X/* Example user program for descrete event simulation. */
X
X/* Procedures "producer_proc" and "consumer_proc" run as
X** simulated processes. They communicate by means of a counting-
X** semaphores.  Semaphore "widget" signals the presence of 
X** widgets produced by producer.  Semaphore "need_widgets"
X** signals the consumer's readiness to accept widgets --
X** (the number of open slots in a widget-queue).
X**
X*/
X
XSimulation sim;
XSemaphore  got_widgets;
XSemaphore  need_widgets;
XProcess producer;
XProcess consumer;
X
Xmain()
X{
X  static void producer_proc(); 
X  static void consumer_proc(); 
X
X  /* Initialize the simulation. The initialization must be done
X  ** before each run.  As simulation cannot be restarted after it
X  ** returns.
X  */
X  PSim_init(&sim);
X
X  /* Schedule the two processes to run under the simulation.
X  ** (Processes may also be added by simulated process which are
X  ** running under the simulation.)
X  */
X  PSim_proc_sched(&sim, &producer, producer_proc);
X  PSim_proc_sched(&sim, &consumer, consumer_proc);
X
X  /* Initialize the semaphores which they will use to communicate. */
X  /* Producer has produced no widgets yet.  We will stipuate that
X  ** the consumer is ready only to accept one initially.
X  */
X  PSim_sema_init(&sim, &got_widgets, 0);
X  PSim_sema_init(&sim, &need_widgets,1);
X
X  /* Now run the simulation.  When a delay-event occurs which takes
X  ** the simulation beyond 55 ticks, the simulation will cease.
X  */
X  PSim_run(&sim, 55L);
X
X  printf("Producer was busy %d ticks.\n", producer.total_time);
X  printf("Consumer was busy %d ticks.\n", consumer.total_time);
X  printf("simulated time is %d.\n", sim.time);
X
X  exit(0);
X}
X
X
X
X
Xstatic int
Xproducer_proc(sim)
X    Simulation * sim;  /* pointer to simulation under which the
X		       ** process is running.  To get the process-
X		       ** record itself, use sim->active.
X		       */
X{
X  int i = 0;
X  while(1)
X    {
X      /* Simulate being busy 8 ticks building a widget. */
X      i++;
X      fprintf(stderr, "Producing %d at %d\n", i, sim->time);
X      PSim_delay(sim, 8);
X
X      /* widget is now ready. */
X      fprintf(stderr, "%d finished at %d\n", i, sim->time);
X      Psema_wait(&need_widgets);
X      Psema_signal(&got_widgets); 
X    }
X}
X
X
X
X
Xstatic int
Xconsumer_proc(sim)
X     Simulation * sim;
X{
X  int i=0;
X  while(1)
X    {
X      i++;
X      fprintf(stderr, "Consumer waits for %d at %d\n", i, sim->time);
X      Psema_wait(&got_widgets);
X
X      /* Simulate being busy 3 ticks consuming a widget. */
X      fprintf(stderr, "Consuming %d at %d\n", i, sim->time);
X      PSim_delay(sim, 3);
X      Psema_signal(&need_widgets);
X
X    }
X}
END_OF_sim2_demo.c
if test 2844 -ne `wc -c <sim2_demo.c`; then
    echo shar: \"sim2_demo.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f sim2.h -a "${1}" != "-c" ; then 
  echo shar: Will not over-write existing file \"sim2.h\"
else
echo shar: Extracting \"sim2.h\" \(2472 characters\)
sed "s/^X//" >sim2.h <<'END_OF_sim2.h'
X/*
X** RCSHeader = $Header$
X** Copyright = Copyright (C) 1988 by Megatest Corporation All Rights Reserved
X** TheAuthor = Dave Jones   (djones at goofy)
X*/
X
X#ifndef C_SIM
X#define C_SIM
X
X#include "queue.h"
X#include "PQ.h"
X#include <setjmp.h>
X
Xtypedef struct process Process;
X
X/***************************************************/
X/****************** Simulation *********************/
X
Xtypedef struct
X{
X  /******* read only ********/
X  unsigned long time;      /* number of ticks which have transpired */
X  unsigned long stop_time; /* when to stop the simulation */
X  Process* active;         /* the active process */
X
X  /******  private  *********/ 
X  PQ busy;             /* priority queue of busy processes */
X  Bool quit;           /* true iff we should return from PSim_run to caller. */
X  Queue semaphores;    /* list of all semaphores in this simulation */
X
X  char* stack_bottom;  /* marks the division on the stack between
X		       ** that used by the scheduler, and that used
X		       ** by simulated processes.
X		       */
X
X}Simulation;
X
X
X/***************************************************/
X/******************  Semaphore *********************/
X
Xtypedef struct
X{
X  /***** private *****/
X  Simulation* sim;  /* The simulation for which the semaphore is valid */
X  Queue queue;      /* queue of waiting processes */
X  int signals;
X
X}Semaphore;
X
X
X
X/***************************************************/
X/******************  Process ***********************/
X
Xstruct process
X{
X  /* read-only */
X  unsigned long total_time;  /* read-only */
X  int return_value;          /* read-only after "process" returns */
X                             /* Returned by "start" procedure */
X                             /* If process never returned, will be zero. */
X
X  /* private   */
X  unsigned long busy_until;  /* Simulated time at which "process" will resume*/
X  int (*start)();            /* The procedure of the simulated process */
X  char* stack_save;          /* mallocked memory to save the stack */
X  char* stack_real;          /* pointer to the "real" stack of the process */
X  long  stack_size;          /* size of the above */
X  jmp_buf restart;           /* longjmp to this to restart the process */
X  jmp_buf suspend;           /* longjmp to this to suspend the process */
X
X};
X
Xextern Simulation* PSim_init();
Xextern unsigned long PSim_run();
Xextern void PSim_proc_init();
Xextern void PSim_sema_init();
Xextern void Psema_signal();
Xextern void Psema_wait();
X
X#endif C_SIM
END_OF_sim2.h
if test 2472 -ne `wc -c <sim2.h`; then
    echo shar: \"sim2.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f sim2.c -a "${1}" != "-c" ; then 
  echo shar: Will not over-write existing file \"sim2.c\"
else
echo shar: Extracting \"sim2.c\" \(7323 characters\)
sed "s/^X//" >sim2.c <<'END_OF_sim2.c'
Xstatic char
XRCSHeader[] = "$Header$";
Xstatic char
XCopyright[] = "Copyright (C) 1988 by Megatest Corporation All Rights Reserved";
Xstatic char
XTheAuthor[] = "Dave Jones   (djones at goofy)";
X
X#include "sim2.h"
X#include <stdio.h>
X#include "heap.h"
X
X/******************************************************************
X**
X** Discrete event simulation package.   See sim2_demo.c.
X**
X*******************************************************************/
X
X
X
X/* This procedure is used by the priority-queue package PQ to 
X** order processes which are "busy" until some simulated time.
X** The first process not to be busy will be scheduled to run.
X*/
Xstatic
XBool process_precedes(proc1,proc2)
X  Process* proc1;
X  Process* proc2;
X{
X  return proc1->busy_until < proc2->busy_until;
X}
X
X
X
X
X
X
X/*****************************************************/
X/*        Initialize a simulation                    */
X/*****************************************************/
X
XSimulation*
XPSim_init(obj)
X  register Simulation* obj;
X{
X  obj->time = 0;   /* elapsed simulated time */
X
X  /* priority queue of busy processes */
X  PQ_init(&obj->busy, process_precedes );
X
X  /* keep up with semaphores, in order to clean up later. */
X  Queue_init(&obj->semaphores);
X
X  return obj;
X}
X
X
X
X
X/************************************************************************/
X/* Schedule a process to run in a simulation. (Call PSim_init() first.) */
X/************************************************************************/
X
Xvoid
XPSim_proc_sched(obj, proc, start )
X     Simulation* obj;
X     register  Process* proc;     
X     int (*start)();
X{
X  proc->total_time = 0L;
X  proc->start = start;
X  proc->stack_save = (char*)0;
X  proc->stack_size = 0;
X  proc->return_value = 0;
X
X  /* Schedule it as ready now. */
X  proc->busy_until = obj->time;
X  PQ_insert(&obj->busy, (Ptr)proc);
X
X}
X
X
X
X
X#define PSim_first(obj) ((Process*)(PQ_first(&((obj)->busy))))
X
X/***********************************************************************/
X/*       Delay the active process by some number of ticks.             */
X/***********************************************************************/
X
XPSim_delay(obj, ticks)
X  register Simulation* obj;
X  int ticks;
X{
X  register Process* proc = obj->active;
X
X  /* Update time until which the process will be busy, and
X  ** the total amount of time it will have been busy at
X  ** that time.
X  */
X  proc->total_time += ticks;
X  proc->busy_until = obj->time + ticks;
X
X  /* If the first queued process is ready before this one,
X  ** we must suspend the active process, and start a
X  ** queued one.  If not, just tick the clock.
X  */
X  if((PSim_first(obj)->busy_until < obj->active->busy_until)
X     || obj->active->busy_until >= obj->stop_time
X    )
X    {
X      /* schedule this process as "busy" */
X      PQ_insert(&(obj->busy), obj->active);
X      suspend_active_proc(obj);
X    }
X  else
X    obj->time = proc->busy_until;
X}
X
X
X
X
X/***********************************************************************/
X/*                   stop the simulation                               */
X/***********************************************************************/
X
XPSim_stop(obj)
X  Simulation* obj;
X{
X  obj->quit = 1;
X  suspend_active_proc(obj);
X}
X
X
Xextern char* alloca();
X
X/***********************************************************************/
X/* Run the simulation, stopping after some number of ticks, unless
X** all processes exit, or some process calls PSim_stop() first.
X*/
X/***********************************************************************/
X
X
Xunsigned long
XPSim_run(obj, ticks)
X  Simulation* obj;
X  unsigned long ticks;
X{
X  obj->stack_bottom = (char*)alloca(1);
X  obj->stop_time += ticks;
X
X  while(!obj->quit)
X    {
X      /* Get a busy process from the busy-queue */
X      obj->active = (Process*) PQ_pop(&obj->busy);
X
X      /* If all processes are finished, or are waiting on 
X      ** a semaphore, we are blocked, and must exit the simulation.
X      */
X      if(obj->active==0) goto end_simulation;
X
X      /* Update the time to the time of the active process */
X      obj->time = obj->active->busy_until;
X
X      if( obj->time >= obj->stop_time) goto end_simulation;
X
X      if(setjmp(obj->active->suspend) == 0)
X	{
X	  if(obj->active->stack_save == 0)
X	    {
X	      /* Process has not yet started. Call its start-procedure. */
X	      obj->active->return_value =
X		(*(obj->active->start))(obj);
X	    }
X	  else
X	    { /* Process has been suspended, and will now be restarted. */
X	      
X	      /* allocate the restarting process's stack. */
X	      alloca( obj->active->stack_size );
X	      
X	      /* restore it */
X	      bcopy(  obj->active->stack_save, obj->active->stack_real,
X		    obj->active->stack_size);
X	      sfree(obj->active->stack_save);
X	      obj->active->stack_save = 0;
X	      
X	      /* restart the process */
X	      longjmp(obj->active->restart, 1);
X	    }
X	}
X    }
X
X end_simulation:
X  cleanup(obj);
X  return obj->time;
X}
X
X
Xstatic
Xcleanup(obj)
X  Simulation* obj;
X{
X  PQ_clean(&(obj->busy));
X
X  /* Iterate through semaphores, cleaning them up. */
X  {
X    Semaphore* sema;
X    while( sema = (Semaphore*)Queue_pop(&obj->semaphores))
X      {
X	Process *proc;
X	while( proc = (Process*)Queue_pop(&sema->queue))
X	  if(proc->stack_save != (char*)0)
X	    sfree(proc->stack_save);
X
X	Queue_clean(&sema->queue);
X      }
X    Queue_clean(&obj->semaphores);
X  }
X}
X
X
X
X
X  
X/***********************************************************************/
X/*                     Initialize a semaphore                          */
X/***********************************************************************/
X
Xvoid
XPSim_sema_init(sim, sema, signals)
X     Simulation* sim;
X     Semaphore* sema;
X{
X  sema->signals = signals;
X  sema->sim = sim;
X  Queue_init(&sema->queue);
X  Queue_append(&sim->semaphores, sema);
X}
X
X
X/***********************************************************************/
X/*                      Wait on a semaphore                            */
X/***********************************************************************/
X
Xvoid
XPsema_wait(obj)
X     register Semaphore* obj;
X{
X  if( obj->signals-- > 0)
X    {/* don't suspend. */
X    }
X  else
X    { Queue_append(&obj->queue, (Ptr)obj->sim->active);
X      suspend_active_proc(obj->sim);
X    }
X}
X
X
X
X/***********************************************************************/
X/*                      signal a semaphore                             */
X/***********************************************************************/
X
Xvoid
XPsema_signal(obj)
X     register Semaphore* obj;
X{
X  if(++obj->signals <= 0 )
X    { Process* ready = (Process*)Queue_pop(&(obj->queue));
X      ready->busy_until = obj->sim->time;
X      PQ_insert(&obj->sim->busy, ready);
X    }
X}
X
X
X
X
X
X#define min(a,b)        ((a)<(b)?(a):(b))
X#define abs(a)          ((a)< 0?-(a):(a))
X
X/** suspend the active process **/
X
Xstatic 
Xsuspend_active_proc(obj)
X  register Simulation* obj;
X{
X  char* stack_top = alloca(1);
X  long size = abs(obj->stack_bottom - stack_top);
X  
X  obj->active->stack_save = (char*)smalloc(size);
X  obj->active->stack_real = min(stack_top, obj->stack_bottom);
X  obj->active->stack_size = size;
X
X  if(setjmp(obj->active->restart) == 0)
X    {       
X      /* copy the stack and return to the simulator. */
X      bcopy( obj->active->stack_real, obj->active->stack_save, size);
X      longjmp(obj->active->suspend, 1);
X    }
X}
END_OF_sim2.c
if test 7323 -ne `wc -c <sim2.c`; then
    echo shar: \"sim2.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of shell archive.
exit 0



More information about the Comp.lang.c mailing list