The Synchronous Blog

A blog about reactive programming languages.

Archive for the ‘Concepts’ Category

Interrupt Service Routines in Céu

leave a comment »

An Interrupt Service Routine (ISR) executes in reaction to an asynchronous hardware request, interrupting the ongoing computation in the CPU.
As an example, in an Arduino, whenever the USART subsystem receives a byte from the serial line, the CPU execution is redirected to the “USART_RX interrupt vector”, which is a predefined memory address containing the ISR to handle the byte received.
Only after the ISR returns that the interrupted computation resumes.

ISRs are often associated with a high-priority functionality that cannot wait long.
Complementing the USART example, if the execution of the ISR is too much delayed, some received bytes can be lost.

Likewise, the execution of an ISR should never take long, because other interrupts will not trigger in the meantime (although it is possible to nest ISRs).
For this reason, a typical USART ISR simply stores received bytes in a buffer so that the program can handle them afterwards.

ISRs in Céu:

Céu has primitive support for ISRs, which are declared similarly to functions.
However, instead of a name identifier, an ISR declaration requires a number that refers to the index in the interrupt vector for the specific platform.

When an interrupt occurs, not only the ISR executes, but Céu also enqueues the predefined event OS_INTERRUPT passing the ISR index.
This mechanism allows the time-critical operation associated with the interruption to be handled in the ISR, but encourage non-critical operations to be postponed and respect the event queue, which might already be holding events that occurred before the interruption.

The code snippets that follow is part of an USART driver for the Arduino.
The driver emits a READ output event to signal a received byte to other applications (i.e. they are awaiting READ).
The ISR just hold incoming bytes in a queue, while the main body is responsible for signaling each byte to all applications (in a lower priority).

/* variables to manage the buffer */

var byte[SZ] rxs;                   // buffer to hold received bytes
var u8 rx_get;                      // position to get the oldest byte
var u8 rx_put;                      // position to put the newest byte
atomic do
   rx_get = 0;                      // initialize get/put
   rx_put = 0;                      // the `atomic´ block disables interrupts

/* ISR for receiving byte (index "20" in the manual) */

function isr[20] do
   var u8 put = (rx_put + 1) % SZ;  // next position
   var byte c = _UDR0;              // receive the byte
   if put != rx_get then            // check buffer space
      rxs[rx_put] = c;              // save the received byte
      rx_put = put;                 // update to the next position

/* DRIVER body: receive bytes in a loop */

output byte READ;                    // the driver outputs received bytes to applications

loop do
   var int idx = await OS_INTERRUPT
                 until idx==20;      // USART0_RX_vect

   var byte c;                       // hold the received byte
      atomic do                      // protect the buffer manipulation new interrupts
         c = rxs[rx_get];            // get the next byte
         rx_get = (rx_get + 1) % SZ; // update to the next position
      emit READ => c;                // signal other applications


Note how the real-time/high-priority code to store received bytes in the buffer runs in the ISR, while the code that processes the buffer and signal other applications runs in the body of the driver after every occurrence of OS_INTERRUPT.

Given that ISRs share data with and abruptly interrupt the normal execution body, some sort of synchronization between them is necessary.
As a matter of fact, Céu tracks all variables that ISRs access and enforces all other accesses (outside them, in the normal execution body) to be protected with atomic blocks.


Céu provides primitive support for handling interrupt requests:

  • An ISR is declared similarly to a function, but specifies the interrupt vector index associated with it.
  • An ISR should only execute hard real-time operations, leaving lower priority operations to be handled in reaction to the associated OS_INTERRUPT event.
  • The static analysis enforces the use of atomic blocks for memory shared between ISRs and the normal execution body.


Written by francisco

April 13, 2014 at 11:42 am

A Synchronous Micro Kernel for Embedded Systems

with 2 comments

I’m working on a new operating system that follows the synchronous execution model of Céu.
In reality, the term micro kernel would be more accurate: I’m only concerned with scheduling and inter-process communication mechanisms.

Why a new micro kernel?

Many reasons. :)

General frustrations

(Accumulated over the years of using UNIX-based systems.)


We are still using select or threads to communicate with multiple applications at the same time:

  • select: multiplex all communication in a single point and deal with state explicitly (e.g., switch (state) {…}).
  • threads: decentralize the communication in multiple threads and deal with synchronization explicitly (e.g., locks, semaphores).

Both approaches are complex and error prone (threads, select/events).


It is difficult, if not impossible, to reproduce the behavior of a set of interacting applications (even of a single application):

  • Preemptive schedulers are highly sensitive to small timing variations.
  • Most programming languages offer non-deterministic concurrency models only (e.g. threads, actors).

OS/Language integration:

I’m not sure if the “everything is a file”  philosophy of UNIX-based systems is too generalist and language agnostic.
Maybe operating systems and programming languages should be designed in conjunction, with the latter offering first-class OS-level IPC mechanisms.

Particular demands

I also have particular demands related to ongoing projects in our research group.

Micro platforms:

We work with highly-constrained embedded platforms (e.g., 16MHz, 64Kb FLASH, 4Kb RAM).

With such little resources, we can take advantage of the synchronous concurrency model to be more economic:

  • Processes share the same event queue.
  • Processes share the same stack.
  • Cooperative scheduling instead of preemptive (together with language guarantees that processes do cooperate).

Distributed WSNs:

Wireless Sensor Networks demand more functionality from operating systems:

  • Processes that communicate might not be on the same network node.
  • Applications need to be replaced remotely.


The video that follows shows a working demo of the OS:

(To see the texts in the video, please use a resolution of at least 480p in the “settings” icon.)

Together with the kernel, the microcontroller is preloaded with three processes:

  • An USART driver.
  • A shell that allows us to start/stop applications.
  • An USART<=>shell bridge that stores received bytes from the serial line until the command is complete.

These processes have no special rights, they are only preloaded so that we can command the microcontroller remotely.

In the first demo (0s-35s), after booting the microcontroller, we issue a sequence of commands through the terminal:

  • Upload a blinking application to address 0xF000.
  • Load address 0xF000 as process 0.
  • Start process 0.
  • Stop process 0 after some time.

Then, with the OS still up and running, we upload a similar application (it only blinks a different LED) to the same address and repeat the sequence of commands. The visual result is to see the blinking LED to change from red to yellow.

The second demo (35s-1min14s) issues another sequence of commands to upload and start three other applications:

  • A GPIO driver.
  • Two blinking applications [code1,code2].

Now, while the first application executes and blinks the yellow LED, we upload another application to blink the red LED.

Both applications rely on the the GPIO driver and avoid to duplicate the GPIO functions (as happens in the first demo).

The link command connects the applications with the GPIO driver. For example, to link the output call PIN_MODE of application 1 with the input call PIN_MODE of the driver (application 0), we write <link 1 1 0 243> (i.e., link app 1 / output 1 => app 0 / input 243).

(Sorry, event identifiers must be “hardcoded” as numbers instead of names.)

Check also the code for the USART driver, shell, USART<=>shell bridge, and GPIO driver.

Details in another post to come.

Written by francisco

March 11, 2014 at 2:50 pm

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;
     every 1s do
         _printf("[%d] Hello world!\n",

  var HelloWorld hello1, hello2; = 1; = 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; = 1;
     var HelloWorld hello2; = 2;
     await 5s;
  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:

      var int i = 1;
      every 1s do
          spawn HelloWorld with
     = i;
          i = i + 1;

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;
              var int i = 1;
              every 1s do
                  spawn HelloWorld with
             = i;
                  i = i + 1;

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:

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

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;
      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

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

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

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

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

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.


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.

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",

  var HelloWorld hello1, hello2; = 1; = 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;
     par/or do
         every 1s do
             _printf("[%d] Hello world!\n",
         await this.stop;

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

  await 3s500ms;
  emit hello1.stop; = 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.


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.

Written by francisco

May 22, 2013 at 6:59 pm

Dynamic Memory Management in Embedded Systems

with 4 comments

Dynamic functionality in embedded systems is usually discouraged due to resource constraints.
However, some types of applications inherently require memory allocation.

As an example, protocols in sensor networks typically forward messages through nodes at a non-deterministic rate, given that the number of neighbors and transmission periods can vary.
Hence, many protocols require dynamic memory management to hold receiving messages until they are successfully forwarded.

A simple FIFO queue might not be always optimal because forwarding a message may involve multiple steps with delays (e.g. transmission acknowledgments).
In such scenario, the protocol would rather handle multiple messages at the same time, raising the possibility of a message received later be discarded first.

Unfortunately, out-of-the-box dynamic memory schemes, such as malloc/free, are not suitable for embedded systems which have quite different requirements in comparison to standard desktop systems.

Follows a list of issues concerning memory management schemes in embedded systems:

  1. Memory corruption
    Many embedded systems lack memory protection, and continuous allocations in the heap may end up corrupting the stack (and vice versa).
  2. Run-time overhead
    Memory management requires extra run-time bookkeeping. Also, in the context of embedded systems, a predictable execution model can be even more important than the fastest scheme on the average.
  3. Metadata overhead
    Metadata used by the memory manager can spend precious bytes (e.g. linked lists of free blocks).
  4. Memory fragmentation
    For constrained memory platforms, unusable holes between and inside allocated blocks (external and internal fragmentation, respectively) can waste a big percentage of available memory.
  5. Unreproducible execution
    Successive executions of the same program may allocate memory in different ways, possibly leading to different outcomes (e.g. an allocation fail).
  6. Deallocation hazards
    Properly deallocating memory is far from trivial. A missed deallocation leads to a memory leak that wastes memory, while deallocating a memory block still in use leads to a dangling pointer that will eventually crash the application.

As the C standard is loose about these issues, out-of-the-box malloc/free can perform bad in all items.
Furthermore, deallocation hazards are inherent in schemes that require an explicit free operation.

Garbage collected systems eliminate deallocation hazards, but may incur unacceptable run-time overheads.

Memory Pools

Embedded systems usually rely on memory pools to manage dynamic memory.
In the context of sensor networks, both TinyOS and Coniki OSes offer and promote the use of memory pools (through Pool and MEMB, respectively).

A memory pool allocates N predefined fixed-sized blocks of memory that can be used by the application.
Most of the raised concerns are alleviated with this scheme:

  1. Because the allocation is static, the maximum amount of memory is known at compile time, reducing considerably the risk of memory corruption.
  2. The run-time overhead is minimal as implementations use simple arrays to hold the memory blocks. For instance, in the TinyOS implementation both allocation and deallocation are O(1).
  3. TinyOS’ Pools use an auxiliary vector of size N to hold pointers for free blocks.
  4. Regardless of different allocation patterns in applications, memory pools will always guarantee the minimal N of memory blocks. Hence, external fragmentation is non-existent. Internal fragmentation, however, can be an issue and is discussed below.
  5. Given that the memory operations are simple and handle fixed-size blocks, the execution is always deterministic and predictable.
  6. Memory pools are still manipulated through malloc/free-like operations. Hence, all challenges to properly deallocate memory still hold.

Internal fragmentation occurs when an allocated memory block is bigger than the requested size.
Given that memory pools can only handle fixed-size blocks, any allocation that requests smaller blocks will contain internal fragmentation (allocation of bigger blocks always fail).
That said, embedded applications are usually simple and contain only one or two different object units that require dynamic allocation.
This way, an application will use a different memory pool for each kind of object, thus also eliminating internal fragmentation.


Memory pools are the way to go for dynamic allocation in embedded systems.

They offer memory compactness, efficient and small operations, and predictable execution.

However, programming dynamic applications is still hard and error prone, given that missing and wrong deallocations may lead to memory leaks and subtle crashes.

In the next post I will show how Céu offers safer and higher level mechanisms for dynamic applications, while using memory pools transparently under the hoods.

Written by francisco

May 20, 2013 at 7:45 pm

Céu “organisms”

leave a comment »

I’m about to release the version 0.4 of Céu (already available on github [1] and a dedicated VM [2]).

The language had many improvements [3], but by far, the addition of a “class” system was the most significant.

A powerful abstraction functionality is a must to augment the scope of the language from constrained embedded systems to mobile and desktop platforms.

I’ve been playing with Céu + SDL [4] for a while and came up with this idea of mixing objects (interface+explicit state) with trails (subprograms+implicit state) into a single functionality (an “organism”).

The videos that follow go through the most important concepts of Céu, starting from the basics of synchronous parallel compositions, up to the class system with scoped objects that are automatically reclaimed by the language run-time.


Céu basics


Céu with SDL


Céu organisms


Céu dynamic organisms




[3] (see HISTORY)


Written by francisco

May 10, 2013 at 12:30 pm

Posted in Concepts, News

Tagged with , , , , ,

“Céu: Embedded, Safe, and Reactive Programming”

with one comment

We have published a technical report entitled “Céu: Embedded, Safe, and Reactive Programming”.

Enjoy the reading!


Céu is a programming language that unifies the features found in dataflow and imperative synchronous reactive languages, offering a high-level and safe alternative to event-driven and multithreaded systems for embedded systems.

Céu supports concurrent lines of execution that run in time steps and are allowed to share variables. However, the synchronous and static nature of Céu enables a compile time analysis that can enforce deterministic and memory-safe programs.

Céu also introduces first-class support for “wall-clock” time (i.e. time from the real world), and offers seamless integration with C and simulation of programs in the language itself.

The Céu compiler generates single-threaded code comparable to handcrafted C programs in terms of size and portability.

Table of Contents:

  1. Introduction
  2. The Language Céu
    1. Parallel compositions
    2. Internal events & Dataflow support
    3. Wall-clock time
    4. Integration with C
    5. Bounded execution
    6. Determinism
    7. Asynchronous execution
    8. Simulation in Céu
    9. GALS execution
  3. Demo applications
    1. WSN ring
    2. Arduino ship game
    3. SDL game simulation
  4. Implementation of Céu
    1. Temporal analysis
    2. Memory layout
    3. Gate allocation
    4. Code generation
    5. Reactive execution
    6. Evaluation
  5. Related work
    1. Synchronous model
    2. Asynchronous model
  6. Conclusion