The Synchronous Blog

A blog about reactive programming languages.

Posts Tagged ‘threads

Dynamic Applications in Céu (2/2)

with 3 comments

This is the follow up to the previous post on creating dynamic applications in Céu.

As introduced there, organisms are the main abstraction mechanism in Céu, reconciling objects and lines of execution in a single construct. The example below, extracted from the previous post, creates two instances of a class that prints the “Hello World!” message every second:

  class HelloWorld with
     var int id;
  do
     every 1s do
         _printf("[%d] Hello world!\n",
                  this.id);
     end
  end

  var HelloWorld hello1, hello2;
  hello1.id = 1;
  hello2.id = 2;
  await FOREVER;
.

One thing that arises in the code is how the organisms hello1 and hello2 are declared as local variables, using the same syntax of a normal variable declaration (e.g. “var int x=0”). This implies that an organism follows the standard scoping rules of conventional imperative languages, i.e., its memory is reclaimed when its enclosing block goes out of scope. Additionally, all of its lines of execution are seamlessly killed.

Céu supports three different ways to manage the life cycle of organisms automatically: local variables, anonymous allocations, and named allocations.

Local variables

The simplest way to manage organisms is to declare them as local variables, as shown in the previous example. As in the example, the two organisms don’t go out of scope, let’s include an explicit block to declare hello2 so that it goes out of scope after 5 seconds:

  var HelloWorld hello1;
  hello1.id = 1;
  do
     var HelloWorld hello2;
     hello2.id = 2;
     await 5s;
  end
  await FOREVER;
.

The organism hello2 runs in parallel with the do-end construct and is active while the block is in scope. After 5 seconds, the block goes out of scope and kills hello2, also reclaiming all its memory. As an outcome, the message “[2] Hello world!” stops to show up in the video.

The order of execution between blocks and organisms is determined: code inside a block executes before the organisms declared inside it. This way, the do-end has priority over hello1 (they are both in the top-level block), while await 5 has priority over hello2 (they are both inside the do-end). The order the messages appear in the video is correct, hello2 always awakes before hello1. Also, hello2 is killed before printing for the 5th time, because the await 5s has higher priority and terminates the block before hello2 has the chance to execute for the last time.

Regarding memory usage, a local organism has an associated slot in the “stack” of its enclosing block, which is calculated at compile time. Blocks in sequence can share memory slots. Local organisms do not incur overhead for calls to malloc/free.

Anonymous allocations

True dynamic applications often need to create an arbitrary number of entities while the application is running. Céu supports a spawn command to dynamically create and execute  a new organism:

  do
      var int i = 1;
      every 1s do
          spawn HelloWorld with
              this.id = i;
          end;
          i = i + 1;
      end
  end
.

We now spawn a new organism every second passing a different id in the constructor (the code between with-end). We can see in the video that every second a new organism starts printing its message on the screen. Again, the printing order is deterministic and never changes.

Note that the spawned organisms are anonymous, because there’s no way to refer to them after they are created. Anonymous organisms are useful when the interaction with the block that creates them happens only in the constructor, as in the example above.

Note also the we use an enclosing do-end apparently with no purpose in the code. However, in order to also provide seamless memory reclamation for anonymous organisms, a spawn statement must be enclosed by a do-end that defines the scope of its instances. This way, when the do-end block goes out of scope, all organisms are reclaimed in the same way local organisms are.

In the next example, we surround the previous code with a par/or that restarts the outer loop after 5 seconds:

  loop do
      par/or do
          await 5s;
      with
          do
              var int i = 1;
              every 1s do
                  spawn HelloWorld with
                      this.id = i;
                  end;
                  i = i + 1;
              end
          end
      end
  end
.

Now, after creating new instances during 5 seconds, the par/or terminates the do-end scope and all organisms are killed. The loop makes this pattern to execute continuously.

An anonymous organism can also be safely reclaimed when its body terminates, given that no one can refer and access its fields.

Named allocations

The most flexible way to deal with dynamic organisms is through the new statement, which not only spawns a new organism but also returns a reference to it:

  do
      var HelloWorld* hello = new HelloWorld;
      hello:id = 1;
      ... // some more code
  end
.

In the example, the returned reference is assigned to the variable hello, which is of type HelloWorld* (a pointer to the class). The organism can be manipulated through the colon operator (:), which is equivalent to the arrow operator in C (->).

A named organism is automatically reclaimed when the block holding the pointer it was first assigned goes out of scope. In the example, when the do-end block in which the hello pointer is declared goes out of scope, the referred instance is reclaimed.

For safety reasons, Céu does not allow a pointer to “escape” to an outer block. Without this precaution, a reference could last longer than the organism it points, yielding a dangling pointer in the program. In the following example, both the assignment to outer and the call to _cfunc are refused, given that their scope are broader the that of variable hello:

  var HelloWorld* outer;
  do
      var HelloWorld* hello = new HelloWorld;
      hello:id = 1;
      outer = hello;          // this assignment is refused at compile time
      _cfunc(hello);          // this call is refused at compile time
      ... // some more code
  end
.

In order to compile this code, we need to include finalizers to properly handle the organism going out of scope:

  var HelloWorld* outer;
  do
      var HelloWorld* hello = new HelloWorld;
      hello:id = 1;

      finalize
          outer = hello; // outer > hello
      with
          ...            // this code is executed just before do-end goes out of scope
      end

      _cfunc(hello)      // _cfunc > hello (_cfunc is a global function)
          finalize with
              ...        // this code is executed just before do-end goes out of scope
          end;
  end
.

A finalize block is tied to the scope of the dangerous pointer and gets executed automatically just before the associated block terminates. This way, programmers have means to handle the organism being reclaimed in a safe way.

Conclusion

Céu support three different ways to deal with dynamic allocation of organisms:

  • Local organisms should be used when the number of instances is known a priori.
  • Anonymous allocations should be used when the number of instances is arbitrary and the program only interacts with them at instantiation time.
  • Named allocations are the most flexible, but should only be used when the first two methods don’t apply.

In all cases, memory and trails reclamation is handled seamlessly, without programming efforts.

In practice, given that organisms have lines of execution and can react to the environment by themselves, anonymous organisms should be preferred over named organisms in order to avoid dealing with references explicitly.

In the next post, I’ll show a simple evaluation of the runtime costs of organisms in Céu.

http://www.ceu-lang.org/

Advertisements

Written by francisco

June 5, 2013 at 8:51 pm

Dynamic Applications in Céu (1/2)

with 4 comments

The basic prerequisite to build dynamic applications is language support to deal with abstractions and code reuse. Programming languages provide a multitude of abstraction mechanisms, from simple abstract data types, to OO classes. Regarding an abstraction, an effective mechanism should provide means to deal with at least the following points:

  • Hide its internal implementation details.
  • Expose a uniform programming interface to manipulate it.
  • Control its life cycle.

As an example, to build an ADT in C, one can define a struct, hide it with a typedef, expose functions to manipulate it, and control instances with local variables or malloc/free. Classes extend ADTs with richer mechanisms such as inheritance and polymorphism. Furthermore, the life cycle of an object is typically controlled automatically through a garbage collector.

Céu organisms

Abstractions in Céu are created through organisms, which basically reconcile threads and objects into a single concept:

  • An organism has intrinsic execution, being able to react to the environment on its own.
  • An organism exposes properties and actions in order to interact with other organisms during its life cycle.

Like an object, an organism exposes properties and methods (events in Céu) that can be accessed and invoked (emitted in Céu) by other instances. Like a thread, an organism has its own line(s) of execution, with persistent local variables and execution state.
In contrast, an object method call typically shares the same execution context with its calling method. Likewise, a thread does not expose fields or methods.

An example

The program below defines the class HelloWorld and executes two instances of it:

  class HelloWorld with
     var int id;   // organism interface
  do               // organism body
     every 1s do
         _printf("[%d] Hello world!\n",
                  this.id);
     end
  end

  var HelloWorld hello1, hello2;
  hello1.id = 1;
  hello2.id = 2;
  await FOREVER;
.

The behavior can be visualized in the video on the right. The top-level code creates two instances of the class HelloWorld, initializes the exposed id fields, and then awaits forever. As organisms have “life”, the two instances react to the environment autonomously, printing the “Hello world!” message every second.

Note in the example that organisms are simply declared as normal variables, which are automatically spawned by the language runtime to execute in parallel with its enclosing block.

In the following variation, we add the event stop in the class interface and include another line of execution in the organism body:

  class HelloWorld with
     var   int  id;
     event void stop;
  do
     par/or do
         every 1s do
             _printf("[%d] Hello world!\n",
                      this.id);
         end
     with
         await this.stop;
     end
  end

  var HelloWorld hello1, hello2;
  hello1.id = 1;
  hello2.id = 2;

  await 3s500ms;
  emit hello1.stop;
  hello2.id = 5;
  await 2s;
  emit hello2.stop;

  await FOREVER;
.

Now, besides printing the message every second, each organism also waits for the event stop in parallel. The par/or construct splits the running line of execution in two, rejoining when any of them terminate. (Céu also provides the par/and construct.)

After the top-level code instantiates the two organisms, it waits 3s500ms before taking the actions in sequence. At this point, the program has 5 active lines of execution: 1 in the top-level and 2 for each of the instances. Each organism prints its message 3 times before the top-level awakes from 3s500ms.

Then, the top-level emits the stop event to the first organism, which awakes and terminates. It also changes the id of the second organism and waits more 2s. During this period the second organism prints its message 2 times more (now with the id 5).

Note that although the first organism terminated its body, its reference hello1 is still visible. This way, the organism is still alive and its fields can be accessed normally (but now resembling a “dead” C struct).

Execution model

Lines of execution in Céu are known as trails and differ from threads in the very fundamental characteristic of how they are scheduled.

Céu is a synchronous language based on Esterel, in which lines of execution advance together with a unique global notion of time.
In practical terms, this means that Céu can provide seamless lock-free shared-memory concurrency. It also means that programs are deterministic and have reproducible execution. As a tradeoff, concurrency in Céu is not suitable for algorithmic-intensive activities as there is no automatic preemption among trails.

In contrast, asynchronous models have time independence among lines of execution, but either require synchronization primitives to acquire shared resources (e.g. locks and semaphores in pthreads), or completely forbid shared access in favor of message passing (e.g processes and channels in actor-based languages). In both cases, ensuring deterministic execution requires considerable programming efforts.

The post entitled “The case for synchronous concurrency” illustrates these differences in practical terms with an example.

The synchronous model of Céu is presented in more depth in these videos.
The videos also show organisms in action together with the SDL graphical library.

Conclusion

Céu organisms reconcile objects and threads in a single abstraction mechanism.

Classes specify the behavior of organisms, hiding implementation details and exposing an interface in which they can be manipulated by other organisms.

In the next post, I’ll show how Céu can control the life cycle of organisms with lexical scope in three different ways: local variables, named allocation, and anonymous allocation.

http://www.ceu-lang.org/

Written by francisco

May 22, 2013 at 6:59 pm

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.

Written by francisco

March 23, 2012 at 10:20 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

The problem with Events

with 2 comments

Following the discussion from here and here

Some problems arise from event-driven programming adoption:

  1. Inversion of control:
  2. Commanded by the environment, event-driven programs must quickly answer requests to keep the system up and running.
    For instance, if a program wants to perform a time consuming operation (e.g. I/O), it must demand it to be done in the background and register a callback to continue the previous operations. If a logical sequence has three of these time consuming operations, the job must be separated into that many callbacks.
    This characteristic leads to difficulty in visually understanding the applications’ control flow and is known as callback soup.

    Another bad consequence of this code separation is that the state kept in callbacks are independent of each other as all local variables residing in their stacks are lost on returning. To keep state, their stacks must be manually reconstructed in the heap and passed as extra parameter from callback to callback.
    This phenomenon is known as stack ripping.

    In this sense, threads offer a more natural way of programming as the programmer may use the conventional sequential flow, keeping all state in thread’s single stack.

  3. Multi-core processors:
  4. Another issue with the event-driven approach is the challenge to take advantage of multi-core architectures.

    In a common event-driven dispatcher, handlers must be run in sequence as they all share global state. When parallelized, two handlers would access the shared memory at the same time, leading to data corruption.

    This is not the case with threads which are already artificially run in parallel even in single-core, thus having all shared memory protected manually with programmed instructions.
    Well written multi-threaded programs take advantage of multi-core for free.

  5. Listener life cycle:
  6. Once a handler is registered for events it remains listening to them until a call to unregister is made.
    In some sense, this is similar to manual memory management. The system is not capable of deciding by itself when a listener must be unregistered.
    There is no such concept as “listen while some rule is valid”.


The first (and worst) problem is solved with cooperative multi-tasking.
A paper [1] explores this issue and shows this interesting graphic where the sweet spot is viewed as an improvement over both event-driven and multi-threading choices.

The second problem is a new one as multi-core architectures are still debuting.
I do have some ideas on this issue and believe that smarter people also do.
Giving different “colors” to unrelated callbacks is an option already in use [2].

The third problem arose on my own research and I’m searching for works to see if someone had already pointed that out. I’m working on a “listening scope” concept and wondered if something similar exists.

To conclude, I think that event-driven programming had always been seen more as technique than a true paradigm. Support in languages is very limited and always offered as a library layer that creates a small synchronous world for specific tasks.

[1] “Cooperative Task Management without Manual Stack Management”:
http://www.stanford.edu/class/cs240/readings/usenix2002-fibers.pdf
[2] “Multiprocessor Support for Event-Driven Programs”: people.csail.mit.edu/nickolai/papers/usenix2003-slides.pdf

Written by francisco

August 28, 2008 at 3:13 pm

“Cada Macaco no seu Galho”

with 3 comments

Or “A place for everything and everything in its place”.

In applications like games and multimedia systems several entities run concurrently, leading to a high degree of internal and external interactivity among them.
Internal entities might be game characters, graphical widgets, AI actions and so on, while external entities might be the mouse, keyboard, network and also the time.

Interaction may be better defined as synchronization in this scope.
Using a shooter game as an example, a character movement is synchronized with user controls, as a gun sight is with the mouse position. Also, animations must be synchronized, so that all objects move together.

Currently, when realizing that asynchronous threads are not adequate for these applications, most programmers use event-driven or observer pattern techniques (I’ll use the general term implicit invocation).

Synchronous functionality is present in some conventional languages, unfortunately they are barely used when known.
Continuations or coroutines are examples of such features present in languages like Scheme and Lua.
With coroutines, the programmer can keep state between successive calls to the same callback and avoid issues in implicit invocation such as inversion-of-control and stack-ripping.
It’s not by chance that Lua is so popular in the game industry.

A place is still reserved for asynchronous threads: exactly where you don’t need a high degree of synchronization.
If you want to compute the product of some 1000×1000 matrices, there’s no point on doing it synchronized, just go async.
You can still have some degree of synchronization, though. That would be in specific (and obvious) points like a memoization table for calculated results.

Well, this is only an opinion, still in the need for a more solid background.
I would like to see more papers around this topic, although it’s not easy to find bibliography defending asynchronous threads.
Maybe their advocates are just indifferent to this discussion or too busy debugging their applications.
What do you think?

Here is some bibliography:
[1] “Event-driven programming for robust software” (pdos.csail.mit.edu/~rtm/papers/dabek:event.pdf)
[2] “Why Threads Are A Bad Idea (for most purposes)” (http://www.stanford.edu/class/cs240/readings/threads-bad-usenix96.pdf)
[3] “The Problem with Threads” (http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf)
[4] “Why events are a bad idea for high-concurrency servers” (capriccio.cs.berkeley.edu/pubs/threads-hotos-2003.pdf)

Written by francisco

August 21, 2008 at 1:42 pm

Threads Are Evil

with 4 comments

I never refuse to express my opinion about threads: they are Evil.

Using threads is like selling your soul to Satan without even noticing it.
They offer you the paradise with concurrency and shared memory for your programs.
After the first week using it, you see yourself working full time to correct the “special cases” you weren’t aware of. After one month you become a slave of your own program.

The other (not so) common approach to concurrency is message passing.
It seems that it is always gaining popularity, but its use is still restricted to niches. It was never really adopted by a mainstream language.
Message passing eradicates memory corruption and is seen as a safer model.

What is common with these models is that they are both asynchronous and non-deterministic.
By asynchrony I mean that the concurrent entities run unaware of each other. If they want to synchronize, they must use a language primitive for it (receive, lock, synchronized, etc).
The non-determinism is also inherent here, one can never be sure when the scheduler will preempt a running entity. This is, of course, a source of non-deterministic bugs.

What is the point of using asynchronous languages to write synchronous programs?
We feel (probably we learnt) that we have no option: If we want to synchronize code we must do it explicitly.
That is so not true as I’ll try to defend here…

Written by francisco

August 16, 2008 at 4:07 pm