The Synchronous Blog

A blog about reactive programming languages.

Archive for the ‘Concepts’ Category

The case for synchronous concurrency

with 4 comments

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.

Advertisements

Written by francisco

March 23, 2012 at 10:20 pm

LuaGravity in the Lua Workshop 2009 – Video available!

leave a comment »

Click here to watch the talk about LuaGravity presented in the Lua Workshop’09.

Written by francisco

November 24, 2009 at 1:06 am

Posted in Concepts, News

Tagged with , , ,

Concurrent Systems

leave a comment »

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

Written by francisco

November 19, 2009 at 5:56 pm

SBLP – Full Paper available

leave a comment »

Click here to get the PDF with the full paper presented at SBLP entitled “LuaGravity: a Reactive Language based on Implicit Invocation”.

Written by francisco

August 27, 2009 at 5:07 pm

About Determinism

with 2 comments

Current approaches for concurrent systems, such as multi-threading and message-passing are inherently non-deterministic, leading to unpredicted execution.

In multi-threaded systems, wherein memory is shared among threads, even if critical sections of code are protected, one is still subject to bugs due to non-determinism.

Suppose one writes the following code:

thread1 {
    ...     // do some processing
    lock {
        a = a + 2
    }
}
thread2 {
    ...     // do some processing
    lock {
        a = a * 2
    }
}

a = 1
start(thread1)
start(thread2)
wait(thread1, thread2)
print(a)

Depending on which thread assigns to `a` first, the value printed might be 6 or 4.
Moreover, each time the program is executed, the other result may be printed, as thread scheduling isn’t deterministic.

By using message-passing concurrency, non-determinism is also an issue.
In the code below, the value 6 or 4 might also be printed.

myChannel = new Channel()
cspA {
    ...     // do some processing
    send(myChannel, 4)
}
cspB {
    ...     // do some processing
    send(myChannel, 6)
}
cspC {
    ...     // do long processing
    a = receive(myChannel)
    a = receive(myChannel)
    print(a)
}

The characteristic that makes such systems non-deterministic is that each command in the language takes an unbounded time to execute.
As each thread or process run in asynchrony with each other, we (or the compiler) can’t predict where each thread will be at anytime, being impossible to detect simultaneous accesses to system resources.


Synchronous Concurrency, in the other hand, is deterministic.
Each command is conceptually instantaneous or takes exactly the time it says so.

For instance, in LuaGravity all commands but AWAIT are instantaneous:

_a = _a + 2           -- instantaneous
SPAWN(reactor)        -- instantaneous
AWAIT(reactor)        -- waits for `reactor` to finish
AWAIT(2)              -- waits 2 seconds

In the code below, we can predict simultaneous access to _a that would lead to non-deterministic behavior, and raise an error.

SPAWN(function()
    _a = _a + 2       -- line 2: simultaneous access to `_a` with line 8
end)
SPAWN(function()
    AWAIT(keyboard.press)
    _a = 10           -- deterministic access to `_a`
end)
_a = _a * 2           -- line 8: simultaneous access to `_a` with line 2

The execution of this program yields an error when the second simultaneous access to _a happens.
The prediction of simultaneous access could be even static (if LuGravity had a compiling phase), raising a compile-time error.

Written by francisco

January 6, 2009 at 5:04 pm

Imperative Reactivity

with 2 comments

The LINK reactivity primitive was already presented in this post.
LINK makes the use of event-driven paradigm easier, avoiding all the bureaucracy of events definition, posting and handling: they are all done implicitly.
However, in another post, we pointed out three issues in this paradigm: inversion of control, multi-core processors and listener life cycle.

This post deals with the first and more annoying limitation of event-driven programming: inversion of control.
Event-driven programming demands that its callbacks execute very fast as the event handling is serialized: while one event is being handled, others are not – only one callback executes at a time.
Callbacks are, therefore, logically instantaneous and can’t hold state. They commonly receive state (those void* parameters), decode it (to work like a state machine and know where it was left), update it and return.
The sequential execution paradigm is broken here, as control is now guided by the event queue (the environment).

LuaGravity supports reactivity inside its methods in some way like Esterel does.
The AWAIT primitive suspends the execution of a method and waits for another method (or timer) to happen.
For example, AWAIT(keyboard.ENTER.press) suspends the running method until ENTER is pressed.
AWAIT is like a LINK, but is broken when its condition happens and resumes (instead of calling) the suspended method.

A little bit confusing, huh?
Hope the following example helps.
Let’s say we want an animation to change its direction following the sequence RIGHT, DOWN, LEFT and UP when the respective keys are pressed.
Without using the AWAIT primitive, we need to hold state between successive executions of animation.changeDirection:

-- WITHOUT AWAIT
LINK(RIGHT.press,  animation.changeDirection)
LINK(DOWN.press, animation.changeDirection)
LINK(LEFT.press,    animation.changeDirection)
LINK(UP.press,       animation.changeDirection)

function animation.changeDirection (key)
    if (obj.state == 'right') and (key == 'DOWN') then
        obj.state = 'down'
        obj.x = obj.x()                -- stay here
        obj.y = obj.y() + S(obj.speed) -- move down

    elseif (obj.state == 'down') and (key == 'LEFT') then
        obj.state = 'left'
        obj.x = obj.x() - S(obj.speed) -- move left
        obj.y = obj.y()                -- stay here

    elseif (obj.state == 'left') and (key == 'UP') then
        obj.state = 'up'
        obj.x = obj.x()                -- stay here
        obj.y = obj.y() - S(obj.speed) -- move up

    elseif (obj.state == 'up') and (key == 'RIGHT') then
        obj.state = 'right'
        obj.x = obj.x() + S(obj.speed) -- move right
        obj.y = obj.y()                -- stay here
    end
end

With the use of AWAIT, we code the animation sequentially:

-- WITH AWAIT
while true do
    AWAIT(RIGHT.press)
    obj.x = obj.x() + S(obj.speed)   -- move right
    obj.y = obj.y()                  -- stay here

    AWAIT(DOWN.press)  obj.x = obj.x() -- stay here
    obj.y = obj.y() + S(obj.speed)   -- move down

    AWAIT(LEFT.press)  obj.x = obj.x() - S(obj.speed) -- move left
    obj.y = obj.y()                  -- stay here

    AWAIT(UP.press)
    obj.x = obj.x()                  -- stay here
    obj.y = obj.y() - S(obj.speed)   -- move up
end

In the code above, obj.x() takes its current position, and S(obj.speed) animates the objects (position = integral of speed).
Much cleaner with AWAIT, isn’t?
See the result in the video below:

The full example code can be found here.

Written by francisco

October 7, 2008 at 8:31 pm

Reactivity in LuaGravity

with 3 comments

The reactivity in LuaGravity is achieved with implicit method invocation. So what?

Suppose we have the following class definition:

MyClass = class {
   function init (self, name)
       self._name = name
   end
   function ping (self)
       print('ping', self._name)
   end
   function pong (self)
       print('pong', self._name)
   end
}

That is, a simple class with a property name and two methods: ping and pong.

Now we create three objects and link some of their methods:

a = MyClass('a')
b = MyClass('b')
c = MyClass('c')

LINK(a.ping, b.pong)
LINK(b.pong, c.ping)
LINK(c.ping, a.pong)

Then, a simple call to a.ping yields in:

> a.ping()
ping    a
pong    b
ping    c
pong    a

That simple! A method is implicitly called in reaction to a call in another condition method.
Comparing to event-driven programming, there’s no need to define or post events, it’s all made implicitly. Much less verbosity.


The reactive variables of LuaGravity (shown here and here) override Lua’s default behavior for attribution.

So that

b = a
a = 2

Is equivalent to

LINK(a.update, b.update)
a.update(2)

Variables are, instead, special objects with an update method.

The parameter in a method call is propagated through its link chain as in a pipeline.
This way the value 2 is also passed to b.update.


A simple example of using LuaGravity in multimedia applications would go like this:

LINK(video1.start, video2.start)
LINK(video3.stop,  video4.start)

The first link makes video1 and video2 play in parallel, while the second link makes video3 and video4 play in sequence.

By overloading the operators + and * one could just write:

video1 + video2  -- play in parallel
video3 * video4  -- play in sequence

In LuaGravity, event definition is implicit, event posting is implicit and event linking may also be implicit (through operator overloading).

Given the amount of times the word implicit appears in this text, could LuaGravity be considered an implicit implicit invocation system?

Written by francisco

September 1, 2008 at 12:05 am