The Synchronous Blog

The point of this post is to show that it is wrong to rely on timing issues in preemptive multithreading for activites that require a synchronized behavior. I compare the same program specification in three different implementations.

The example program is supposed to blink two leds with different frequencies (400ms and 1000ms) on an Arduino board. They must blink together every 2 seconds.

The first two implementations use different RTOSes with preemptive multithreading. The third implementation uses the synchronous language Céu.

(UPDATE) The complete source files can be found here.

The first implementation uses the ChibiOS RTOS. I omitted all code related to creating and starting the threads (which run with the same priority).

Follows the code and video for the implementation in ChibiOS:

static msg_t Thread1(void *arg) {
    while (TRUE) {
        digitalWrite(11, HIGH);
        chThdSleepMilliseconds(400);
        digitalWrite(11, LOW);
        chThdSleepMilliseconds(400);
    }
}
static msg_t Thread2(void *arg) {
    while (TRUE) {
        digitalWrite(12, HIGH);
        chThdSleepMilliseconds(1000);
        digitalWrite(12, LOW);
        chThdSleepMilliseconds(1000);
    }
}

You can see that around 1:00 the leds loose synchronism among them, and also with the metronome.

The second implementation uses the DuinOS RTOS. I also omitted all code related to creating and starting the threads (which run with the same priority).

In this example the leds were well synchronized, so I included another task that uses the serial port with a different frequency.

Follows the code and video for the implementation in DuinOS:

taskLoop (T1) {
    digitalWrite(11, HIGH);
    delay(400);
    digitalWrite(11, LOW);
    delay(400);
}

taskLoop (T2) {
    digitalWrite(12, HIGH);
    delay(1000);
    digitalWrite(12, LOW);
    delay(1000);
}

int c = 0;
taskLoop (T3) {
    delay(77);
    Serial.print(c++);
}

Since the beginning you can see that the leds loose synchronism among them, and also with the metronome.

The third implementation uses the synchronous language Céu.

In this example the leds were well synchronized, even with the third activity that uses the serial port.

Follows the code and video for the implementation in Céu:

par do
    loop do
        _digitalWrite(11, _HIGH);
        await 400ms;
        _digitalWrite(11, _LOW);
        await 400ms;
    end
with
    loop do
        _digitalWrite(12, _HIGH);
        await 1s;
        _digitalWrite(12, _LOW);
        await 1s;
    end
with
    int c = 0;
    loop do
        await 77ms;
        c = c + 1;
        _Serial.print(c);
    end
end

Conclusion:

The execution model of preemptive multithreading does not ensure implicit synchronization among threads.

There’s nothing wrong with the RTOSes and the example implementations: the behavior shown in the videos is perfectly valid.

The problem is that usually the very first examples for these systems use blinking leds (supposely synchronized) to show how easy is to write multithreaded code. This is not true!

Preemptive multithreading should not be used as is to write this kind of highly synchronized applications. Adding semaphores or other synchronization primitives to these codes won’t help alone, they require a single thread to handle timers that is responsible to dispatching others.

I used timers in the example, but any kind of high frequency input would also behave nondeterministically in multithreaded systems.

In synchronous languages like Céu, the execution model enforces that all activities are synchronized all the time.

Concurrency is one of those terms that everyone has an intuition about its definition until needs to write about it, realizing that the concept is too open to just use “concurrency”.

Follows the first phrase in Wikipedia’s entry for “Concurrency”:

In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other.

By using the words simultaneously and interacting, this definition captures (for me) the essence of concurrency.

One of the fundamental properties of concurrent systems is their execution model, that is, when should the concurrent computations (I’ll call them concurrent entities) in the system run, and what are the rules that an entity should obey while running.

• Asynchronous Concurrency

In asynchronous execution, entities are in charge of their own control flow and execute independently of each other. Hence, each entity has its own notion of time, not shared globally. The decision to synchronize with other parts of the system is also internal to each entity, and not enforced by the surrounding environment. Depending on the concurrency model in use, these entities are known as threads, actors, processes, tasks, etc.

• Synchronous Concurrency

In synchronous execution, the system flow is controlled by the environment, and internal entities must execute at its pace, in permanent synchrony. Time is now shared between entities and is represented as time steps or as a series of events, both triggered by the surrounding environment.

In my personal experience, when saying “concurrency” people assume asynchronous concurrency, excluding all synchronous reactive languages/systems.

For example, if I state that event-driven programming is a concurrency model, I’ll probably be inquired about this position.

However, if you agree with Wikipedia’s definition and thinks about an event-driven implemented game with hundreds of entities interacting, how can it not be considered “concurrent”?

In a paper from Gerard Berry [1], this “prejudice” is also commented:

Being somewhat unclassical compared to prevalent CSP or CCS based models, it took more time for the synchronous model to be accepted in the mainstream Computer Science community.

Execution model is just one property of concurrent systems. I did not discuss here communication, synchronization, parallelism, determinism…

Maybe it is time to build something like a “Taxonomy for Concurrency”, enumerating all recurrent properties found in concurrency models and languages. Does anyone know about an existing work in this direction?

[1] Gérard Berry, The foundations of Esterel, Proof, language, and interaction: essays in honour of Robin Milner, MIT Press, Cambridge, MA, 2000