Task Synchronisation

Synchronisation 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:

The definition of synchronisation found on dictionary.com is:

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:

1. one-to-one – only two task synchronising
2. one-to-many
3. many-to-one
4. many-to-many

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

In the simplest case of synchronisation, we have two tasks (Task₁ and Task₂) that need to synchronise their execution.

We can now say that Task₁ and Task₂ have synchronized their threads of execution.

However, what should the behavior be if Task₁ arrives first? In terms of the dictionary definition of synchronisation, Task₁ should wait for Task₂. Unfortunately, with most RTOSs this is not the case and Task₁ will continue execution without blocking. This means we need to further refine our definition of synchronisation to include the concepts of:

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, which feels like a paradox, is the case where:

 

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₂ now reaches the synchronisation point (assuming Task₁ has already passed the synchronisation point)? Does Task₂ block and wait for Task₁, or does it see that Task₁ has already visited to SO and continue? Or to put it another way, is the notification of synchronisation to the synch object from Task₁ persistent or non-persistent?

In a non-persistent model, the fact that Task₁ has already passed the synchronisation point is not remembered, therefore Task₂ blocks until Task₁ 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.

The key to this model is that the fact that Task₁ has already signalled the SO (passed the synchronisation point) is remembered. When Task₂ 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₂ consumes the signal Task₁ has set (auto-reset) or does Task₁ clear the signal (manual-reset) at some later time.

In the consuming model, if Task₂ now arrives back at the SO and waits, it will block until again signalled by Task₁. In the manual-reset model, Task₂ will continue to pass the synchronisation point until Task₁ (or indeed Task₂) explicitly clears the signal (normally with a separate API call).

Finally, in the consuming model what happens if Task₁ signals the SO more than once before Task₂ 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₂ arrives (binary model). The alternative is that a count is kept of the number of signals set by Task₁. Each time Task₂ waits on the SO this count is decremented, and Task₂ will only block if the count is zero.

So we can classify RTOS synchronisation into the following:

In the next posting I shall be looking at synchronisation involving more than two tasks and then following that one by examining some actual RTOSs and their support for synchronisation.