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.

Good news received last week:

Dear Mr. Francisco Sant’Anna,

I am pleased to confirm that your paper “LuaGravity, a Reactive Language
Based on Implicit Invocation” has been accepted for presentation and
publication at SBLP 2009.

All papers went through a rigorous reviewing process by the program
committee. Out of 30 research papers and 3 tutorials submitted, 12
papers and 1 tutorial were accepted.

Please make sure that in the preparation of the final paper you
carefully address the reviewers’ comments. Additionally, at least one
author is required to register in the conference for your paper to
appear in the proceedings.

Congratulations again on having your paper accepted. We look forward to
seeing you in Gramado!

Reviewer’s comments already addressed and final version submitted! One reviewer in particular pointed several constructive observations, which we took very seriously in the final version.

Follows the abstract for the paper:

The reactive programming paradigm covers a wide range of applications, such as
games and multimedia systems.
Mainstream languages do not offer proper support for reactive programming,
lacking language-level primitives that focus on synchronism and interactions
within application parts.
We propose an imperative reactive language, called LuaGravity, based on
unconventional implicit invocation mechanisms.
LuaGravity allows dataflow programming, sequential imperative execution, and
deterministic use of shared-memory.
With this work, we intend to unite the essential features of reactive languages
while keeping a convenient imperative style of programming.

SBLP [1] is the main Brazilian congress on programming languages. This year it will be held in Gramado on August 18-21.

[1] http://sblp2009.ucpel.tche.br/