Simulation Programming Notes

Synchronization of processes

Lin Jensen, Bishop's University
Computer Science 301a, Simulation Techniques, Fall 1996

There is a large body of literature on parallelism in hardware and operating systems. Several different schemes for process synchronization exist. In simulation we are primarily interested in pseudo-parallelism using co-routines, but similar principles apply.

Simula class DEMOS includes objects for the following 4 typical patterns of synchronization.


Producer - Consumer synchronization

In this machine-oriented pattern, Producers produce things, which are then consumed by Consumers. The things could be messages, customers, computer chips, or automobiles crossing a bridge. The same process can of course be both consumer and producer. For example, a computer repair person consumes broken computers and produces working computers.

Consumers synchronize with producers by means of a queue, or "bin." Producers can produce if there is room in the bin. (They can always produce if the bin is unlimited.) Consumers can consume only when the bin is not empty. The simplest form of a bin is simply a counter of anonymous items. Often we want to use a fifo-queue of the desired items, such as customers with arrival times, busses with number of passengers, or messages with text.

Using our toolboxes, the unit QUEUE can be used to hold the desired items, or the unit QNETOBJ to hold TArecords.

SIMULA class DEMOS (Discrete-Event Modeling On SIMULA) provides, among other things, the type bin, of anonymous counters. Producers give units of production (integer parameter) to the bin, and Consumers take units. A bin is initialized with a name (string) as a standard feature of DEMOS objects, and an initial content, for example:

        HappyCustomers :- new bin ("Happies", 0)
DEMOS bins are unlimited. The function avail returns the current contents of a bin, this can be used to determine that a customer will be "lost", or even to delay the producer.

Limited-capacity resources -- Semaphores

By contrast, in material-oriented modeling, the material, or customers are the ones that possess life cycles. The machines, or servers, are regarded as passive resources, being acquired (or seized) by the material, and later released. The material is often held up due to the limited capacity of the resource.

If the resource has capacity of one, we call it a single server. This special case is probably easier to deal with.

For example, in GPSS a single server is modeled by a facility. A facility can be seized and released, preempted, and made unavailable (with several degrees of urgency). A check is made that the same transaction releases a facility was the one that seized it. By contrast, a resource with larger capacity is modeled as a storage, transactions can enter and leave it. New entries can be blocked, but that is all.

The concept of semaphore comes from operating systems. A semaphore is a special counter that allows only a certain number of processes to be within a critical section at one time. The critical section of a process is guarded by calls to wait and signal on the semaphore. Wait allows the process to pass, so long as the counter value is greater than 0. It then decrements the value. If not, the semaphore needs to hold up (block) the process, using a queue for this purpose. Signal increments the value, letting new processes pass their wait instruction. In simulation, we would typically use a semaphore to guard a section

This is totally adaquate for a single server, giving the semaphore an initial value of 1. It is also adaquate for a server of larger capacity, by initializing the semaphore value to the corresponding capacity, so long as each process is only requesting one service unit. If processes are going to request multiple units, there are complications. The primary problem is a semantic one: What should happen when a request can't be granted?

SIMULA class miniQNcontext, and our toolbox unit QnetObj provide (object) classes for Server, as well as Source and Sink. Recently QnetObj has been augmented with methods MakeUnavailable & MakeAvailable, and the corresponding test (function NotAvailable). This implements an orderly shutdown, allowing process(es) to finish services they have started, but not "allowing" new starts. (If it is desired to model equipment breakdown, it will be necessary to deal with processes that are "Sleeping" to simulate the time of service.) It is still up to the process encountering unavailability to do something, and more importantly, to be resumed (by somebody) when the server becomes available again. The report on a server now includes statistics on available time.

Putting it together

In GPSS, waiting is implicit.
Resources, combining semaphore and server, are provided in SIMULA class DEMOS (res) and our Pascal toolbox unit RESOURCE (aResource). A process can acquire and then release a resource, with implicit waiting. The toolbox RESOURCE also includes methods MakeUnavailable & MakeAvailable, and is currently restricted to acquiring a single unit of resource capacity, for the reasons outlined above.

Two methods of dealing with processes that want to acquire a resource that is unavailable, or becomes unavailable while waiting, are provided. Acquire is for stubborn processes that insist on waiting until it is again available. This would apply to a train that is waiting for a drawbridge to be lowered. AcquireIfAvailable is a function that returns TRUE if the resource has been acquired, and FALSE without (further) waiting if the resource is unavailable. This would apply to a person waiting in line, who will want to choose another line. The syntax of this option prompts you to consider what to do. (You have to obtain the function value of a Pascal function, unlike C.)


Condition queues

A resource cannot model all situations involving waiting. It may be the case that a process needs to acquire some combination of resources. Kreutzer gives the example of a shop in which the servers Manuel and Samantha must sometimes consult a single book, and thus customers may need to acquire both the server and the book.

SIMULA class DEMOS provides a powerful class condq at which processes wait upon arbitrary conditions. Each time the condq is signaled (by processes completing their services (critical sections), the conditions of the waiting processes are reevaluated to see which one(s) can proceed. There is the option to evaluate either the first waiting process, or all of them. It would be an interesting project to implement this scheme in Pascal. I believe it can be done by associating with each process a Boolean function.


Master-Slave synchronization

Sometimes both machines and material should posess life cycles. They can then synchronize their activities by message passing. the toolbox unit
MESSAGE provides message port objects to which processes can send messages (stamped with sender's address by the port), and receive messages (blocking until a message is available). A port combines a queue of messages with a semaphore controlling receiving processes. The messages can contain any desired information.

Often it is useful to consider one process to be dominant during the interaction of two (or more) processes. In the Master-Slave pattern, Master processes coopt "Slave" processes, carry them along for a while, and then release them to continue their independent life cycles. To do this using MESSAGE,

An example of this is the program Ferry.pas in which a ferryboat coopts cars waiting at the dock, and then resumes them after reaching the other side of the river.

SIMULA class DEMOS provides a class waitq for Master- Slave synchronization. Slaves wait, masters coopt, getting a pointer to the slave, later they schedule the slaves, setting them free.

GPSS, being material-oriented, has no such mechanism.


Last updated 17 November 1996

Up to top of this document
To Simulation toolboxes
Back to Survey of Simulation languages
Back to Simulation notes
Back to Lin Jensen's home page. Comments, etc, send to

ljensenn at ubishops.ca