Rich Mustakos has a B.S. in civil engineering from the Virginia Military Institute and currently works for MRJ, Inc. He has been an active programmer for 10 years and doing simulation modeling since 1983. You may reach him at 2404 Alsop Ct., Reston, VA 22091 or on CompuServ 76470,33.
I recently was faced with writing a simulation project that would work on a multitasking operating system. I had not programmed under this particular operating system in over six years and was unfamiliar with the tools and system calls. This project was also under a tight deadline.
Since I have been programming using Turbo C on MS-DOS systems, I decided the best approach would be to develop and debug the project on an MS-DOS system under Turbo C and port the code to the target system.
To exploit the target system's multitasking features, I needed to emulate the system calls under MS-DOS. Once I had acquired enough information about the target system, I put together a short specification for the emulator and then coded it.
After the emulator and the initial development of the project under MS-DOS, I ported the project to the target system (another long story in its own right). Once the port was running, I returned to the emulator and examined what I had written.
The emulator's major thrust was to provide co-routine "process" control and timing capabilities, and inter-"process" communications links that mirrored the target system's calls.
After examining the emulation software, I realized that the emulator very nearly constituted a discrete event simulation library. I then wrote a small requirements specification (see the sidebar "Requirements Specification") and developed a simulation library.
The Simulation Library
The simulation library consists of two header files and one code file. The first header file, CSIM. H (Listing 1) , is used by programmers in their simulations. It includes only those portions of the simulation library interface that must be visible to the programmer's project.The second header file, CSIMINT. H (Listing 2) includes all of the internals for the simulation library and should not be #included in the programmer's project. This header is #included in the library code files. It includes the prototypes for all routines that are visible to the programmer, the routines and variables that are used exclusively inside the simulation library, and all structures and variables that are not visible to the programmer's project.
Data Structures
The _simprocessT structure (Listing 2) holds all information pertaining to a process and connections between processes, including all pointers and general-purpose flag registers. Since the C specification does not ensure that all registers will be totally restored after a subroutine call, the entire register set must be stored, and then restored. The remaining fields next and prev are pointers to other simprocess structures; init records the process's level of initialization. proc_id is the process id number and is started sequentially from 1; kill_flag notifies the task handler that this process is marked to be stopped, and wait_flag notifies it that the process is waiting on a post; waitpost is a pointer to a post and keeps track of which post the process is waiting for (waitpost is NULL if the process is not waiting); start_time is the time of the process's next action in sim_system_time units. The _simprocessT structure also serves as the basis for a process stack.The _postT structure (Listing 2) is used for interprocess communications and to effect process synchronization. The structure contains pointers to other posts, its ID number, by which processes reference the post after it has been initialized, the post's name (which is used for initialization), a void pointer (value) that points to the memory to be passed in interprocess communications, and a pointer to an array of process pointers that keep track of all processes that are waiting for this post to be set.
Hidden Globals
The processlist instance is both the current process and task_handler's link into the list of processes. kbprocess links to the process that handles keyboard activity. totalprocs holds the number of processes that have been produced, or produced and stopped. old_vector stores the old value of the interrupt vector that is being used for context switching, and which will be restored if an orderly exit is made.Globals init, glbl_sp, glbl_ss, glbl_bp and glbl_fc are used during initialization to store current register information, and to pass the routine to be used by the process to the task handler. systimer points to the memory location of the system clock. postlist points into the circular list of posts, and generally points to the last post to be used. totalposts records the number of posts that have been created in the system up to this point; there is no way to delete posts.
Control Routines
The system control routines include install_handler, task_handler, sim_start, set_time_ratio and exit_processing (Listing 3) . The routine install_handler installs the task_handler and saves the old interrupt vector for exit_processing to reinstall. It also tests to see if the installation was successful, though it can be fooled. If the task_handler was already installed, the routine will return an error.The routine task_handler is the heart of the simulation system. It accomplishes context switching, context initialization and context destruction, checks for user input, updates system time, and determines which is the next process to gain control. Almost all of these functions are shaped by the method used for context switching, which uses the Turbo C concept of the interrupt routine type. Routines declared as interrupt type must be installed as interrupts, When the associated interrupt is invoked, all of the CPU registers will be saved on the stack (where the programmer can get to them and save them elsewhere if desired).
The task_handler is a type interrupt routine which, when called through an interrupt, places all available register values on the stack, where they are accessible as local variables. These variables are used to fill the appropriate fields in the _simprocessT structure when switching out of a context. The same stack variables are overwritten with values from a process _simprocessT fields for a particular process when a different context becomes "current."
In several areas, I have chosen to err of the side of caution, creating some potential redundancies. For example, each process context has its own stack area, located in memory directly above _simprocessT structure for that process. When each process is started, the following occurs: the stack and base pointer fields in the process's structure and actual registers are initialized to the top of its stack, the CS (code segment) and IP (instruction pointer) fields are set to point to the routine specified for this process, all the registers are transferred out of the structure to the stack and an interrupt return instruction is executed. Keeping copies in both the structure and on the stack and replacing those on the stack before the interrupt return may be unnecessary, but makes me feel safer.
Context Initialization
The task_handler routine will initialize a context if called while the global _sim_init_val equals 1. Three pre-conditions must be established before requesting a context initialization. First, glbl_fc should contain the address of the routine that will be run when this process starts running. Second, processlist should be set to the address of the _simprocessT structure that will contain information on this process. Finally, the stack pointer, stack segment and base pointer registers must point to the top of stack space for this process. After enforcing these conditions, the proper values are placed in the process's structure, the structure field init is set to 1, and the task_handler returns control to the calling routine (start_process). This portion of initialization generally occurs before the simulation starts, but these actions will still be performed even if a process is created after the simulation starts.The second part of initialization occurs once simulation has started. At this time, _sim_init_val is 0, and the structure field init is 1. These flags cause the task_handler to load the code segment and instruction pointer registers with values pulled out of the fields in the structure and the field init is set to 0. After the interrupt return has completed, the process starts executing as though it were called from another routine. At this point the process is up and running on its own.
stop_process is called when a process must be destroyed. This routine finds the _simprocessT structure for the process to be stopped and sets the field status.kill_flag to 1. After stop_process has changed the value of status.kill_flag for that process, the task_handler removes the offending process from the list of processes and frees its memory.
At each transfer of control, task_handler looks for the next process to be given control. It can decide in one of three ways. If a key has been pressed, task_handler automatically passes control to the keyboard routine (assuming one has been designated with start_kb_process). If there are no pending keystrokes and _sim_time_ratio is 0, task_handler will start the process with the lowest value of start_time and advances _sim_system_time to match start_time. If _sim_time_ratio is not 0, the difference between now and the last time update is multiplied by _sim_time_ratio and added to _sim_system_time. The process (if any) with a start_time less than or equal to _sim_system_time becomes the current process, and _sim_system_time is set to start_time. If no process has a start_time less than or equal to _sim_start_time, task_handler continues to loop through the list of processes while actual system time goes by, updating _sim_system_time at the rate of _sim_time_ratio until a processes start_time is reached.
The last system control routines are sim_start and exit_processing. sim_start starts the actual simulation processes by setting the global variable init to 0. An interrupt is then executed to start task_handler. The routine exit_processing cleans up after the simulation library and may additionally signal any errors on exit. To shut down the simulation system, the interrupt that was initially changed to hold the address of task_handler is returned to the value in old_vector. Finally, all the process and post memory structures are freed.
The process control routines are start_kb_process, start_process and stop_process. The major difference between the routines start_kb_process and start_process is that start_kb_process signals to task_handler that the process it is about to initialize is to be the designated keyboard handler. These routines ensure that the task_handler has been installed and allow it to perform the first level of initialization.
The start_kb_process and the start_process routines call getvect ( ) to determine if the task_handler has been installed. getvect( ) checks that the address of the selected interrupt is the same as the address of task_handler. If the returned address is not the same as task_handler, then install_handler is called to install task_handler.
When start_kb_process and start_process set up a process, they allocate memory equal to the size of a _simprocessT structure plus a stack (sized in paragraphs). The address of the structure is normalized as it would be in a huge memory model program. The stack segment is set to the normalized segment address of the structure, and the stack and base pointers are set to the normalized offset address of the structure, plus the size of the stack in bytes, establishing the stack space as a unique piece of memory for each process.
The code segment and instruction pointer fields of the _simprocessT structure for the current process are set to point to the beginning of the routine to be used by the process. Next, the new structure is spliced into the processlist. Finally, these routines save the current stack and base pointers in global variables, set the actual stack and base pointers to the newly-created stack, call task_handler to initialize the process structure, and clean up the stack and base pointers from global variables.
stop_process is one of the simpler routines since task_handler performs the majority of the operations required to kill a process. stop_process merely finds the correct _simprocessT structure and sets the status.kill_flag to 1.
The routines wait_until_time and wait_for_time directly control timing of processes. wait_until_time determines the interval between the current time and the desired start time. If the interval is negative, exit_processing is called with an appropriate number. If the interval is positive, then wait_until_time calls wait_for_time to request the delay. wait_for_time determines the time to wake the process, sets the process's start_time and then executes an interrupt to task_handler. task_handler waits until _sim_system_time is equal to the process's start time before returning control to the process.
Communications And Synchronization
The final set of routines are those that perform interprocess communications and synchronization: init_post, set_post, get_post and wait_post.init_post can produce a new post or verify the existence of an old post. When called, init_post checks all existing posts to determine if the incoming string argument names an existing post. If so, the ID for the matching post is returned to the calling process. If no post exists for that name, a new post with initial values set to NULL is linked into the list of posts. The new post's ID number is returned to the calling routine.
set_post is more complicated than init_post.set_post searches the list of posts for one with the proper ID. If the candidate post is currently set, a zero time wait is performed, allowing a simultaneous read of the old value to occur. If the value is still set, the routine returns the ID of the post to signal the error. Otherwise, the value address is set to the address supplied by the user.
If one or more processes are waiting for this post, the status.wait_flag field in the first waiting process structure is assigned 0, notifying task_handler that the process has started. Additionally, any processes found waiting on this post are placed into the NULL-terminated array of process pointers linked to the _postT structure.
get_post searches the list of posts for one with the appropriate ID. If the matching post's value field is NULL, get_post returns NULL, signifying that the post is not set. Otherwise, get_post returns the address stored in value.
wait_post functions much like get_post, but when wait_post encouters a NULL value field, it sets the process's status.wait_flag to 1, signaling task_handler to ignore this process. The post's address is placed in the process structure's waitpost field, and the address of the process is placed in the _postT's waiting array. wait_post then waits for the value field of the post to become something other than NULL. When this occurs, the post value is NULLed and returned to the calling program. The process status.wait_flag is then set to 0 and normal processing continues.
Using the Library
The library's programming interface consists of visible routines declared in CSIM.H.
int start_kb_process (void (*func)(void),int stacksize); int start_process (void (*func)(void), int stacksize);Both routines initialize a process to start the routine func, with a stack that is 16 times stacksize bytes of memory long. The routine start_kb_process also attaches keyboard input to the process. Both routines can be called before or during a simulation run and allow processes to be spawned during the simulation.
int set_time_ratio (float ratio);This routine sets the simulation running speed to allow a maximum of ratio seconds of simulation time to occur during each second of real time. If the ratio is zero, the simulation will progress as fast as it can. This process may be called anytime before or during a simulation; its effects are immediate.
void sim_start (void);This routine starts the simulation, passing control out of the calling routine to the task handler. This routine should be called only once to start the simulation and does not return control to the calling routine.
void exit_processing (int condition);This routine stops the simulation. exit_processing cleans up the interrupt table and deallocates all process memory. This routine prints the value of condition to provide some debug information to the programmer. This routine can only be called once, but can be called anywhere in a program.
void stop_process (int process_id);This routine stops the process identified by process_id. This routine should only be called after a simulation has started. You can also stop a process by sending it a signal that tells it to stop itself.
int wait_until_time (long unsigned starttime);To delay until a particular simulation time is reached, a process should put itself to "sleep" by calling this routine with the "wakeup" time, start_time, in seconds. Control is passed to task_handler and the simulation continues. Generally, control will return to this routine when CurrentTime is equal to start_time for this process. This routine should only be called after sim_start has been called.
int wait_for_time (float delaytime);To stop for a certain, predetermined time, a process should call this routine with the delay time in seconds. Control passes to task_handler and is returned to the calling routine after delaytime seconds of simulation time have elapsed. This routine should only be called after sim_start has been called.
int init_post (char *postname);This routine causes the system to check if a post with the name contained in postname exists. If the post does not exist, one is created and its ID is returned. If the post does exist, its ID is returned to the calling program. Control is always returned to the calling program with no change in simulation time. This routine may be called at any time.
int set_post (int post_id, void * pointer);After a post has been initialized, information can be passed to other processes by calling set_post. The arguments are the integer ID of the required post and a pointer to a memory buffer. When called, set_post surrenders control of the system for zero time, allowing simultaneous events to occur. This routine returns 0 if successful, the ID of the post if the post has already been set, and the negative ID if the post was not found. This routine should only be called after sim_start has been called.
void *get_post (int post_id);A process must call get_post to get information from a post identified as the argument post_id. If the post is not set, a NULL pointer is returned. If the post has been set, the pointer the post was set to is returned, and the post is reset. When this routine is called, control remains with the routine, and no simulation time passes. This routine should only be called after sim_start has been called.
void *wait_post (int post_id);This routine can be used both to pass information and to synchronize processes. The argument post_id identifies the post to be checked. If the post has been set, control is returned immediately to the calling process. If the post is not set, control does not return to the calling process until another process sets the post this process is waiting for. If there is no post with that ID, the routine returns a NULL to the calling routine, otherwise the routine returns the pointer in the value field of the post, and this field is then reset to NULL. This routine should only be called after sim_start has been called.
An Example
Discrete event simulation can simulate a single queue, multi-server teller system (see Listing 4) . The routine generator sends customers into the simulation and the three copies of the process teller then service and release them.Using these routines requires knowledge of their internal structure (to keep from doing things that are 'bad'). All processes start with a stack that does not come from MS-DOS. The process should never finish with a normal exit. If a process is to be exited, it must kill itself and then wait for some period of time to allow the task_handler to delete it from memory. The system does not know when a simulation is over, so programmers should include a process that shuts down the simulation:
void ender(void) { wait_for_time(8 _HOURS_); exit_processing(0); }This process allows the simulation to run for up to eight hours and then stops it. If this process is started as the keyboard process, it will be awakened when a key is pressed, calling exit_ processing which shuts down the simulation system. The routine generator initializes a post for passing information to the other processes. The generator process then spends the rest of the simulation looping through a section of code that introduces a customer into the simulation, calls set_post to notify the teller processes of the customer's arrival and waits up to four and a half minutes before restarting the loop.The teller process initializes the same post that the generator process initialized, giving the processes a way to communicate with each other. In particular, the teller processes will wait until they are notified that a customer has arrived by being sent the named signal "Customers". After initializing this post, the routine goes into an endless loop where it spends the rest of the simulation either waiting for notification that a customer has entered the simulation, or serving the customers, an operation that takes at least four minutes but no more than 10 minutes. Whenever this process is given the named signal, it checks to see if any customers are still in the queue. If there are customers, the process sends the named signal so that another teller process will see it and serve the next customer.
The only portion of this simulation that I have not shown is the actual creation of the processes and the start of the simulation. In this section we declare and initialize the global variables customers and tellers, and set the simulation time ratio to 1,000:1, completing our general initialization. To initialize our processes, a generator, three tellers processes and an ender process are started. I have set the size of the stacks for all the processes to 64 paragraphs of memory, or one Kb of stack space per process. (A good rule of thumb is that if things act strange, increase the stack space. I analyze all the routines that are called to come up with an approximate stack size, and then add another 0x20 or 0x30 paragraphs to that size. Since the processes all have the same stack size, I only check to see if the last one returns an error. If there is not enough room for one of the earlier processes, there will not be enough room to generate the ender process.) To actually start the simulation, call sim_start. Although I have a return after that point in main, note that control never returns from sim_start to main.
I have included another demo routine, grfcdemo.c (Listing 5) . grfcdemo.c shows the library's ability to be integrated into a graphics environment.
Further Discussion
Resource Control and Contention
Resources are another area of simulation. A resource is any item in limited supply that is required by one or more processes but cannot be used by more than one process at the same time.Ideally, a resource can be requested by multiple processes at the same time, and actually delivered to a particular process based on some prioritization scheme, either FIFO or FIFO by priority, or whatever scheme is appropriate.
A crude method of performing this scheme is to use set_post and wait_post inside another routine to allocate and deallocate resources from processes, and to use a global variable to track how many of the resources are available at any one time.
Swapping Processes Out of Memory
One of this system's limitations is that only as many processes may be active as can fit into memory. Having more active processes would be possible if the _simprocessT structure and the process stack could be transfered out of DOS memory, either onto disk or into expanded or extended memory. Swapping the structure out of MS-DOS memory risks corrupting the base and stack pointers and the stack segment pointer. This corruption would occur if the process were loaded into a different area of memory after a swap. This problem is not insurmountable, since the new register values could be calculated on the fly.
A Continuous Simulation Library
Continuous simulation is possible using this library. If each process sets its own step time and loops through updating itself and waiting for that amount of time, the same effect can be achieved as with true continuous modeling. An advantage of continuous simulation over continuous modeling is that each simulation process may set a different step time as required by the real-world process it is modeling, thereby reducing the overall CPU load while not degrading the resolution of the simulation.
Sidebar: Discrete Event Simultaion