## Task Synchronisation

October 15th, 2009Synchronisation is an everyday event, both in the real-world and the computer program. For example meeting a friend for a coffee requires synchronisation, in that both parties need to arrive within a given timeframe to make the event worthwhile (sometimes referred to as a rendezvous – however this tends to have more romantic implications). Alternatively, receiving a PO via fax is a form of synchronisation. The company waiting on the PO will-not/cannot start working on the project until this event occurs. Finally, in an automated robot manufacturing system, the movement and work done by each robot must be synchronised with each other and in conjunction with the actual production line.

In the field of embedded systems’ software there are also many requirements for synchronisation with a program. In multi-tasking system using a RTOS examples are:

- Asynchronous device driver where we are dealing with slow devices. We don’t necessarily want tasks blocked waiting on the device.
- At system start-up, many RTOSs start tasks as active (ready to run). We may have an ordering dependency for execution (e.g. initialisation of global resources) where all tasks must wait for a given condition (the concept of a barrier which can be very important in multi-processor systems).
- Having a managed task abort notification, rather than deleting tasks (which can lead to resource issues). Similar in concept to the UNIX/Linux kill signal. Also used to manage task pools.

The definition of synchronisation found on dictionary.com is :

**synchronisation**

*noun*

- the relation that exists when things occur
**at the same time**; “the drug produces an increased synchrony of the brain waves” [syn: synchronism] [ant: asynchronism] - an adjustment that causes something to occur or recur
**in unison**[syn: synchronization] - coordinating by causing to indicate
**the same time**; “the synchronization of their watches was an important preliminary” [syn: synchronization]

So synchronisation is about making sure event happen at the same time (as in a common clock in communications systems) as opposed to asynchronous which means not happen at the same time. Unfortunately, as we shall see, most texts related to RTOS descriptions misuse/misunderstand this term.

It should be noted that synchronisation and mutual exclusion often get lumped together and confused. Mutual exclusion is about making sure thing don’t happen at the same time, whereas synchronisation is about making sure they do.

In regard to task synchronisation there four classes of interaction we need to address:

- one-to-one – only two task synchronising
- one-to-many
- many-to-one
- many-to-many

Initially we address the condition where only two tasks are synchronising.

ONE-TO-ONE : SINGLE CONDITION

In the simplest case of synchronisation, we have two tasks (Task

_{1}and Task_{2}) that need to synchronise their execution.- Task
_{2}runs until it reaches the synchronisation point as defined by an RTOS synchronisation object (*SO*), at which point it waits for Task_{1} - Task
_{1}now runs and reaches the synchronisation point, signals Task_{2}via the*SO*. Both tasks are now ready to run. - The higher priority task now continues execution and the lower priority task is made ready (If the tasks are of equal priority typically Task
_{1}will continue as this avoids a context switch).

We can now say that Task

_{1}and Task_{2}have synchronized their threads of execution.However, what should the behavior be if Task

_{1}arrives first? In terms of the dictionary definition of synchronisation, Task_{1}should wait for Task_{2}. Unfortunately, with most RTOSs this is not the case and Task_{1}will continue execution without blocking. This means we need to further refine our definition of synchronisation to include the concepts of:- Symmetric or Bilateral Synchronisation
- Asymmetric or Unilateral Synchronisation

BILATERAL SYNCHRONISATION

Bilateral synchronisation is the condition when whichever task arrives first it waits for the other one. This is often called the

*Rendezvous*(as support by the Ada programming language). Surprisingly this is rarely supported by the majority of RTOSs. One limitation of bilateral synchronisation is that it cannot be used for ISR-to-task synchronisation (as an ISRs must never block).UNILATERAL SYNCHRONISATION

Unilateral Synchronisation, which feels like a paradox, is the case where:

- if Task
_{2}arrives at the*SO*first it will wait for Task_{1}, and then synchronisation with Task_{1}when it arrives - if Task
_{1}arrives at the*SO*first it will not wait for Task_{2}, thus unilateral synchronisation.

When reading literature associated with RTOSs and synchronisation, this is the most commonly described model (e.g. Li, 2003).

This, however, brings us yet another dilemma; what happens when Task

_{2}now reaches the synchronisation point (assuming Task_{1}has already passed the synchronisation point)? Does Task_{2}block and wait for Task_{1}, or does it see that Task_{1}has already visited to*SO*and continue? Or to put it another way, is the notification of synchronisation to the synch object from Task_{1}persistent or non-persistent?NON-PERSISTENT UNILATERAL SYNCHRONISATION OBJECT

In a non-persistent model, the fact that Task

_{1}has already passed the synchronisation point is not remembered, therefore Task_{2}blocks until Task_{1}signals again . Due to how most RTOSs actually support unilateral synchronisation (discussed later), this, like bilateral synchronisation, is also an uncommon model. Interestingly, Win32 supports this model using a concept called a PulseEvent. If no tasks are waiting when the PulseEvent is called then the event is discarded.PERSISTENT UNILATERAL SYNCHRONISATION OBJECT

The key to this model is that the fact that Task

_{1}has already signalled the*SO*(passed the synchronisation point) is remembered. When Task_{2}arrives at the synchronisation point is doesn’t block, but continues (this particular use case is actually asynchronous event notification).However, we have yet another dichotomy; does Task

_{2}*consumes*the signal Task_{1}has set (auto-reset) or does Task_{1}*clear*the signal (manual-reset) at some later time.In the consuming model, if Task

_{2}now arrives back at the*SO*and waits, it will block until again signalled by Task_{1}. In the manual-reset model, Task_{2}will continue to pass the synchronisation point until Task_{1}(or indeed Task_{2}) explicitly clears the signal (normally with a separate API call).Finally, in the consuming model what happens if Task

_{1}signals the*SO*more than once before Task_{2}arrives at the synchronisation point, and therefore the original signal has not been consumed? One model is there is no effect, the signal remains set and is consumed when Task_{2}arrives (binary model). The alternative is that a count is kept of the number of signals set by Task_{1}. Each time Task_{2}waits on the*SO*this count is decremented, and Task_{2}will only block if the count is zero.So we can classify RTOS synchronisation into the following: