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