The Synchronous Blog

A blog about reactive programming languages.

Posts Tagged ‘wsn

REBLS’14 accepted paper: “Structured Reactive Programming with Céu”

leave a comment »

Our new paper, “Structured Reactive Programming with Céu”, will appear in the Workshop on Reactive and Event-based Languages & Systems (REBLS’14) at SPLASH.

REBLS succeeds REM as the new “reactive workshop” inside SPLASH.

The paper discusses our proposal for “organisms” as an abstraction mechanism for “Structured (Synchronous) Reactive Programming (SSRP)”. It is the textual version of the talk at the Strange Loop.

The preprint version of the paper can be downloaded here.

 

Written by francisco

September 25, 2014 at 12:58 am

Posted in News, Reactive Languages

Tagged with , , , ,

Céu v0.7

leave a comment »

The new version of Céu is released!

What’s new in v0.7:

  • Added support for functions and class methods (we relied on C for defining new functions).
  • Experimental support for interrupt service routines.
  • Experimental microkernel for Arduino.
  • Experimental `input/output´ requests.

Céu in a Box (CiB) is a Linux-based distribution that comes pre-installed with the Céu Programming Language environment:

The distribution contains the compiler together with bindings for the Arduino, TinyOS, and SDL platforms.

CiB is distributed as a single .ova file to be used with VirtualBox.

Written by francisco

April 3, 2014 at 5:30 pm

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.)

“Programmability”:

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).

Debugging/Safety:

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.

Demo

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

REM’13 accepted paper: “Advanced Control Reactivity for Embedded Systems”

with 3 comments

Our paper entitled “Advanced Control Reactivity for Embedded Systems” has been accepted in the Workshop on Reactivity, Events and Modularity (REM) this year in Indianapolis!

REM is a workshop inside the SPLASH/OOPSLA conference.

The preprint version for the paper can be downloaded here.

This is a more theoretical paper in comparison to our previous for SenSys.

We discuss how to build advanced control mechanisms on top of the reactive primitives of Céu and present a formal specification of the language.

Written by francisco

October 12, 2013 at 1:51 pm

Posted in News, Reactive Languages

Tagged with , , , , ,

SenSys’13 accepted paper: “Safe System-Level Concurrency on Resource-Constrained Nodes”

with 3 comments

Our paper entitled “Safe System-Level Concurrency on Resource-Constrained Nodes” has been accepted in SenSys this year in Rome!

The preprint version for the paper can be downloaded here.

I’m happy that Céu has been accepted in such a prestigious conference.

More information can be found here.

 

Written by francisco

September 16, 2013 at 11:30 am

Posted in News, Reactive Languages

Tagged with , , ,

Céu v0.6

leave a comment »

The new version of Céu is released!

What’s new in v0.6:

  •     Added support for asynchronous threads.
  •     Added support for the C preprocessor.
  •     Added tuple types for events.

Céu in a Box (CiB) is a Linux-based distribution that comes pre-installed with the Céu Programming Language environment.

The distribution contains the compiler together with bindings for the Arduino, TinyOS, and SDL platforms.

CiB is distributed as a single .ova file to be used with VirtualBox.

Written by francisco

August 20, 2013 at 11:45 am

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.

Conclusion

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