The Synchronous Blog

A blog about reactive programming languages.

Posts Tagged ‘tinyos

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

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

Céu v0.2

leave a comment »

The new version of Céu is released!

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

September 26, 2012 at 7:32 pm

“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!

Abstract:

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

[ANN] Céu in a Box

leave a comment »

Céu in a Box (CiB) is a distribution of Xubuntu 12.04 [1] that comes pre-installed with the Céu Programming Language environment [2].

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

CiB is distributed as a single .ova file to be used wit VirtualBox [3].
[1]: http://xubuntu.org
[2]: http://www.ceu-lang.org
[3]: http://www.virtualbox.org

Written by francisco

July 9, 2012 at 11:54 am

Céu + Wireless Sensor Networks

with one comment

Wireless Sensor Networks (WSNs) are composed of tiny devices (known as “motes”) that sense the environment and communicate via radio. The image on the right shows two “micaz” motes.

The restricted resources of motes and the unlimited possibilities for WSNs applications made this platform an interesting target for Céu [1]. We integrated Céu with TinyOS [2] in order to use the abstracted radio services the operating system already provides.

The following demo uses a fixed ring topology with three motes placed side by side within their radio ranges.
The motes should follow the same behavior: receive a message with an integer counter, show it on the leds, wait for 1 second, increment the counter, and forward it to the mote on its right.

As the topology constitutes a ring, the counter will be incremented forever while traversing the three motes. If a mote does not receive a message within 5 seconds, it should blink the red led every 500 milliseconds until a new message is received.
The mote with id=0 is responsible for initiating the process at boot time, and also when the network is down, after 10 seconds of inactivity.

Follows the video for the application executing:

 

The code

Let’s start with the code that receives the message and forwards it to the next mote:

 1:  loop do
 2:      _message_t* msg = await Radio_receive;
 3:      int* cnt = _Radio_getPayload(msg);
 4:      _Leds_set(*cnt);
 5:      await 1s;
 6:      *cnt = *cnt + 1;
 7:      _Radio_setDestination(msg, (_TOS_NODE_ID+1)%3);
 8:      emit Radio_send(msg);
 9:  end

 

The code is an endless loop that first awaits a radio message (line 2), gets a pointer to its data region (line 3), shows the received counter on the leds (line 4), and then awaits 1s (line 5) before incrementing the counter in the message (line 6) and forwarding it to the next mote (lines 7-8).
Because this code does not handle failures, it is straight to the point and easy to follow.
Actually, this is the final code for this task, as the handler for errors is placed in a parallel trail.

To handle failures, we use a monitoring trail in parallel with the communicating trail, as shown in the following code:

 0:  par do
1-9:    // COMMUNICATING TRAIL (previous code)
10:  with
11:     loop do
12:        par/or do
13:           await 5s;
14:           par do
15:              loop do
16:                 emit retry;
17:                 await 10s;
18:              end
19:           with
20:              _Leds_set(0);
21:              loop do
22:                 _Leds_led0Toggle();
23:                await 500ms;
24:              end
25:           end
26:        with
27:           await Radio_receive;
28:        end
29:     end
30:  end

 

The network-down behavior constitutes the lines 13 to 25. After 5 seconds of inactivity is detected (line 13), two new activities run parallel: one that retries the communication every 10 seconds by signaling the internal event retry (lines 15-18); and another that blinks the red led every 500 milliseconds (lines 20-24).

The trick to restore the normal behavior of the network is to await the Radio_receive event (line 27) in a par/or (line 12) with the network-down behavior to kill it whenever the network link is restored. By surrounding everything with a loop (line 11), we ensure that the error detection is continuous.

Finally, we need to code the initiating/retrying process that sends the first message from the mote with id=0. As expected we place the code in parallel with the other activities, as the follows:

 0:  par do
1-9:    // COMMUNICATING TRAIL
10:   with
11-29:  // MONITORING TRAIL
30:  with
31:     if _TOS_NODE_ID == 0 then
32:        loop do
33:           _message_t msg;
34:           int* cnt = _Radio_getPayload(&msg);
35:           *cnt = 1;
36:           _Radio_setDestination(&msg, 1);
37:           _Radio_setPayloadLength(&msg, sizeof);
38:           emit Radio_send(&msg);
39:           await retry;
40:        end
41:     else
42:        await Forever;
43:     end
44:  end

 

We start by checking if the mote has id=0 (line 31). If this is not the case, we simply await forever on this trail (line 42).
Otherwise, the loop (lines 32-40) sends the first message as soon as the mote is turned on (line 36-38).
It then waits for a retry emit (line 39) to loop and resend the initial message.

Conclusion

This demo shows how complementary activities in an application can be written in separate and need not to be mixed in the code.
The activities are then combined together through parallel compositions and communication via internal events to achieve the intended behavior.
The complete source code is less than 70 lines and includes all definitions and code to initialize the radio.
The generated code consumes 13.5 Kbytes of ROM and 450 bytes of SRAM.

[1]: http://www.ceu-lang.org/

[2]: http://www.tinyos.net/

Written by francisco

July 4, 2012 at 4:33 pm

Posted in Examples

Tagged with , , , , ,