Thread ordering and concurrency

From Planimate Knowledge Base
Jump to navigation Jump to search

From the 2001 conference

Note some of the material is a bit out of date, in particular zero time events posted to the FEC are arranged in order of broadcasts, moves/unblocks, time resets, button clicks and all other events.

Hence a message dispatcher posting a broadcast within its message item thread will see that broadcast processed before the item leaves the dispatcher.

Rick, March 2004



A modeller with previous programming experience will recognise that designing and developing a model in Planimate requires a different approach than if the model were being written in C or Java. One of the most important distinctions between Planimate and these programming languages is the way that program code (the elements of the model) get executed.


Planimate models, being discrete event simulations, are inherently multi-threaded, maaning they can have a number of "simultaneous" activities under way at a given point in time. Every item sitting in a model is effectively a potential program thread. Understanding how these threads can be managed and coordinated is crucial when modelling complex systems.


First, it is important to make a distinction between the Planimate model and the Planimate Engine which executes it. While a Planimate model can be considered multi-threaded and can contain many concurrent activities from its point of view, the engine itself is not multithreaded. It only ever executes one model item thread at a time, based on its implementation and processing rules.


What we will review here is how the engine orders the events it will process, the circumstances under which it may choose another event (and thread) to process and techniques a modeller can use to manage the concurrency issues.


1. Events and their ordering


Events are the mechanism that Planimate uses to keep track of activity in a model, both current and activity required in the future. The primary mechanism that Planimate uses to sort events is time. Events are kept sorted in a list called the Future Events Chain (FEC) which stores and orders what is "to be done". The engine processes these events in order of increasing time.


For events at the same time, the ordering becomes more complex. In general, events at the same time are processed FIFO, in the order that they are generated/posted by activity in the model. However in some cases the engine posts events at the current time in LIFO order, particularly when the event is related to unblocking or interactive broadcasts. This is done to increase responsiveness in interactive models and make the animation of activity more logical and easier to follow.


When events are generated at the same time, no guarantee is given of the order they will be processed in. Hence, for example, a model can not depend on the order that items will leave a number of servers, even though they arrive at the servers at the same time, in a known order and the servers have the exact same service time. When activities must follow in a strict order, the techniques of thread management outlined here should be kept in mind.


Up to now modellers have forced ordering by using a one second delay in a flow to guarantee that an event will occur after all other events at the current time. This has been inelegant (it causes an artificial passing of time in the model) and with the latest techniques can now be avoided.


2. What constitutes a thread


An item flowing in a path in Planimate can be considered a thread of execution. A Planimate model run consists of a succession of these threads. These get initiated by an event, which could be, for example, a "delay complete" event posted by a multiserver to the FEC or due to the user clicking on a button. Many events (and hence threads) may occur at the same simulation time ("Zero time" activity) or they may be separated in time, requiring the simulation clock to advance before they can occur.


While a thread executes it may generate side effects which in turn will eventually initiate other threads to process them. For example changing an attribute value posts "check" events for any blocking switches with a condition based on that attribute. From the point of view of the model, these side effects all occur at the same simulation time. In reality, they occur in sequence. However, the exact sequence cannot be assumed.


Once Planimate starts processing a particular thread (eg: moving an item out from an entry), the engine will continue to process it until that thread completes - the item reaches a point of capacity - at which point the engine will either retrieve another event to process or return to a pause/ready state, waiting for further user interaction. Model code within the one thread is guaranteed to execute in strict order.


When processing a thread, Planimate is attempting to move an item from one point of capacity to another. As soon as the item reaches its next point of capacity, the movement of the item and hence the thread is complete and another thread may commence. Objects with capacity include any delay object such as multiservers and spatial links, as well as queues and assemblers.


It is important to bear this in mind when processing a broadcast. Any capacity object following a broadcast entry will mean the following objects may not be processed in that same thread. This will be examined in detail shortly.


4. Special cases when thread order is guaranteed


The order that events at the same time are processed cannot be guaranteed. However in some specific cases, the engine will cause a thread to follow on to another thread immediately in order to preserve continuity in the models execution.


An original item entering a message dispatcher immediately starts the message item thread. If the message item reaches an exit within its original thread, then the next thread will be the original item leaving the dispatcher. In this case, the process of sending a message can be treated as a single thread.


In the case where the message item does not enter an exit within its original thread, other events may be processed in between, even between when the message item eventually does enter its exit and the original item leaving the dispatcher. Note that the original design intention of the message dispatcher was to enable time to pass in this way, so it should not be considered a problem. Just do not depend on the exact ordering of these events.


A broadcast message dispatcher (a relatively new feature) immediately starts the broadcast item thread(s) and will release the original item after all the broadcast items have emerged and completed their initial thread. This "return" after a single thread for each broadcast entry guarantees sequence, as it does for the message dispatcher.


An item entering an empty queue or dispatcher which is not blocked will immediately move through it.


A multiserver with a constant zero delay (default for a new multiserver) will post a completion event with LIFO priority meaning that the next event processed will be the item leaving the multiserver. However if the incoming item thread is from a broadcast entry, the system will complete sending any other broadcast items before the multiserver event gets processed. Getting the broadcast sent takes priority over processing events from the FEC.


A splitter will immediately move out all the items split from the incoming item, unless it becomes blocked.


Immediate messages (sent from within a routine) have special impact on thread order and are discussed later.


5. Coordinating Threads


The tradidional Planimate mechanism for synchronising two threads of activity is using a blocking switch and an attribute to create a gate. One item can then open the gate (by setting the attribute non zero) and the blocked item will then be able to flow and immediately close the gate behind it.


Messages provide a more structured mechanism for thread management. When a message is sent from a dispatcher, the original item will wait at the dispatcher until the message item enters an exit, at which point the original item will be ready for release. Any number of threads and simulation delay can occur in between, the item in the dispatcher will always wait until the message item enters an exit.


Messages provide a one to one signalling mechanism - one destination thread is activated for the incoming item thread. Sometimes a one to many operation is required, for example sending out a "clear" command to various parts of the model. In this case broadcasts are used.


Up until now there has not been a mechanism for knowing when all broadcasts have been received and processed. Modellers had to use a delay to force the event ordering. A recent enhancement to the dispatcher enables it to provide this capability without a delay.


When a broadcast is sent from a dispatcher, the original item waits at the dispatcher until every receiving broadcast entry has processed its broadcast event thread. Hence it combines the guarantee of order of a Message with the one to many characteristic of a Broadcast. Unlike a message however, the guarantee is only that the item(s) have left their respective broadcast entries and processed their initial thread. Hence any critical activity must occur immediately after the broadcast entry.


6. How to ensure a broadcast completes before continuing on a thread


If a certain activity (eg: a "Clear" broadcast) must occur before some subsequent code gets executed, several steps need to be taken to ensure there will be no problem with the ordering.

  • Send the broadcast via a dispatcher. That way, the item only leaves the dispatcher once all
    the broadcasts have been sent.
  • Ensure the critical code follows immediately after the broadcast entries, with no intervening
    capacity. If only Change Objects, Guides, Switches and Portals are used, there will be
    no capacity.
  • If graphical iteration is required (not iteration in a routine) then ensure there is only
    one switch in any given closed loop, the switch is set to "assume no blocking". Many change
    objects and guides are OK.


IF multiple switches occur in the one loop, the engine will only be able to iterate for a few
hundred iterations before complaining about an endless loop. Placing a zero delay multiserver
in the loop will fix this error but then mean the original item will leave the dispatcher
before the loop completes (this was mentioned earlier and is due to the fact that sending the
broadcast takes higher priority than processing events from the FEC where the multiserver posts
its event). In these cases, it may be better to use iteration in a routine since routines
always execute within one thread.


7. Other techniques for managing threads


In complex systems where many tests and operations have to be performed at regular intervals, it
may be desirable to minimise the number of threads in order that the system is easier to debug and understand. Having many items carrying out tasks which could be carried out by one item does not gain much speed but does make the system more complex. By using a single co-ordinating item in a master "loop" (which may delegate activities using messages) many concurrency issues disappear since there is only one active thread.


Minimise the number of "capacity" objects in flows. This prevents the thread being broken up. A zero delay is not required between every pair of change objects, especially if the "Only During Move" option is on. As previously mentioned, loops with a single switch in them do not require capacity objects within the loop, no matter how long the loop.


If possible, use dispatchers to co-ordinate and synchronise activities, in preference to attributes and gate switches.


Immediate messages may also be used to make "calls" to other threads. These are discussed below.


8. Immediate Messages


Immediate messages are messages initiated from a routine. They are unique in that they can be sent in the middle of a thread. This means the thread of the message item actually suspends the thread of the original item (which is waiting at the change object sending the immediate message). The moment the message item reaches an exit, the original item's thread continues on.


This recursive nature is the reason why a message item initiated from an immediate message cannot be delayed for any reason - a delay is impossible in the middle of a thread. However the recursive nature of immediate messages makes them very powerful in implementing complex search and lookahead systems. This is amplified by the fact that the immediate message mechanism can be active during Planimates lookahead stage - enabling a modeller to "patch in" to the lookahead process.


The combination of the thread-within-a-thread nature of immediate messages and the Planimate lookahead mechanism can lead to some very unexpected side effects. Modellers are advised to use immediate messages with extreme care. In particular, having the original and message routines marked "only during move" and avoiding modifying portal attributes and tables by the message item is strongly recommended. This will prevent the side effect issues and enable the immediate message to be used as a kind of "function call" which guarantees completion and order.





idkbase note 207