The Synchronous Blog

A blog about reactive programming languages.

Posts Tagged ‘video

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.

Advertisements

Written by francisco

March 11, 2014 at 2:50 pm

The “Rocks!” game in Céu & SDL

leave a comment »

The “Rocks!” game is a spaceship shooter game for 2 simultaneous players on the same Android tablet:

https://play.google.com/store/apps/details?id=org.droid_in_the_sky.rocks

The game is completely written in Céu & SDL and uses the new dynamic extensions of the language.

The code is open source and is extensively commented. I plan to write a tutorial from it:

https://github.com/droid-in-the-sky/rocks

The game also compiles to run in the desktop.

Here’s a running session of the game (with a much faster speed):

Written by francisco

October 8, 2013 at 6:40 pm

Posted in Examples, News

Tagged with , , , , ,

Stress-testing Céu with SDL

with one comment

For a glimpse at the runtime costs of Céu, I created a simple application with SDL that animates 10000 rectangles on the screen.

My hypothesis is that lines of execution in Céu (a.k.a trails) are cheap and should be used carelessly, even for simple activities such as waiting for a single event and terminating. This way, the testing application in Céu has a peek of 40000 trails active at the same time, which are all visited by the scheduler on every frame.

I compare the implementation in Céu with a simpler application in C to serve as a benchmark.

The application in raw C is damn simple:

  • Declares a vector of 10000 rectangles.
  • Initializes each to 10×10 width/height, a random (x,y) position, and a random x velocity.
  • Animates them continuously, restarting from left when reaching the right side of the screen.
  • Achieved FPS = 120 .

The video shows the expected behavior, and the code, the full implementation.
(The video was adapted to 5000 rectangles to enable screencasting).

The application in Céu is considerably more complex (video and code):

  • The program has 5 lines of execution:
    1. On SDL_QUIT event: terminates the application.
    2. Every frame: clears the screen.
    3. Every 40ms: creates 30 new Rect organisms.
      • after 30s: kills all of them at once and restart the process
    4. Every frame: updates the screen.
    5. Every second: calculates the FPS.

    (technically they are 7 lines of execution because (3) and (5) are split in two)

  • The class Rect has 4 lines of execution:
    1. Every 200ms: varies the rectangle width, height, r, g, b (with a random epsilon).
    2. Every frame: animates the rectangle respecting its velocity, terminating when it reaches the end of the screen.
    3. Every frame: redraws the rectangle on screen.
    4. On termination: runs a simple finalizer (which maintains the number of organisms alive).
  • Achieved FPS = 107 . (when 10000 rectangles are on screen)

The main differences between the two implementations are marked in bold above and are summarized as follows:

  • The rectangles in Céu are allocated dynamically: in the peek, we have 750 rectangles being allocated (in the left side) and reclaimed (in the right side) every second.
  • Each rectangle on screen (10000 at most) has 4 active trails, all of which are visited by the scheduler every frame (4 x 10000 = 40000 lightweight threads active at the same time).
  • Finally, every 30 seconds the program restarts the spawning loop, killing all 10000 active organisms at once, running the associated finalizers, and reclaiming all memory.

Céu is a source-to-source compiler that generates single-threaded ansi-C code. This way, the generated code for the test application, although incomprehensible, can be compiled with gcc and tested in any computer that has SDL2:

  % gcc download_code.c -lSDL2
.

Conclusion

The simple SDL application in C is used as a benchmark to compare to a more complex application written in Céu, which shows a decrease around 10% in FPS.

Although the application in C could be re-implemented to achieve the same functionality (for a more strict comparison), the initial numbers are already satisfactory and make the point that the trail-oriented programming style of Céu is realistic, even in a highly dynamic scenario.

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

Written by francisco

June 6, 2013 at 12:04 am

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

Céu + Arduino

leave a comment »

A couple of months ago I acquired an Arduino Uno board [1] and started working on integrating it with Céu [2].

In this blog post, I depict a demo game that uses an LCD shield on the Arduino.

In the game, the player controls a “ship” that moves on screen and has to avoid collisions with meteors.

The video shows the game executing:

The game gets faster and more meteors appear on each phase. When the ship hits a meteor, the game restarts.

The code

The outermost loop of the game runs forever and restarts the game on every new phase or on “game over”:

    1: loop do
 2-12:     // CODE 1: set game attributes
   13:
   14:     _map_generate();
   15:     _redraw(step, ship, points);
   16:     await Key; // starting key
   17:
   18:     win =
19-45:         // CODE 2: the central loop
   46:
47-60:     // CODE 3: game over
   61: end

 

We split the remaining code in three blocks (to be expanded further):

  • CODE 1: sets (or resets) the game attributes, such as the ship position, speed, and game points
  • CODE 2: executes the main logic of the game, such as moving the ship and detecting collisions
  • CODE 3: executes the after game code, based on the result of “CODE 2” (win or !win)

Every time the outermost loop is executed (lines 1-61), it resets the game attributes (CODE 1, lines 2-12), generates a new map, and redraws it on screen (lines 14-15).
Then, it waits for a starting key (line 16), and executes the main logic of the game in the central loop (CODE 2, lines 18-45) until the ship reaches the finish line or collides with a meteor. Based on the return status (line 18), the “game over” code (CODE 3, lines 47-60) may display an animation before restarting the game.

The game attributes (CODE 1) change depending on the result of the previous iteration of the outermost loop:

     // CODE 1: set game attributes
 2:  ship = 0;        // 1st LCD row
 3:  if !win then
 4:      dt = 500;    // game speed (500ms/step)
 5:      step = 0;    // current step
 6:      points = 0;  // number of steps alive
 7:  else
 8:      step = 0;
 9:      if dt > 100 then
10:          dt = dt - 50;
11:      end
12:  end

 

For the first game execution and whenever the ship collides with a meteor, variable `win´ is set to 0 (we omitted global declarations), hence, the attributes are reset to their initial values (lines 4-6). Otherwise, if the player reached the finish line (win=1), then the game gets faster, keeping the current points (lines 8-11).

The central loop of the game (CODE 2) is responsible for moving the ship as time elapses and for checking whether the ship reached the finish line or collided with a meteor:

     // CODE 2: the central loop
19:  par do
20:     loop do
21:        await(dt)ms;
22:        step = step + 1;
23:        _redraw(step, ship, points);
24:
25:        if _MAP[ship][step] == '#' then
26:           return 0;  // a collision
27:        end
28:
29:        if step == _FINISH then
30:           return 1;  // finish line
31:        end
32:
33:        points = points + 1;
34:     end
35:  with
36:     loop do
37:        int key = await Key;
38:        if key == _KEY_UP then
39:           ship = 0;
40:        end
41:        if key == _KEY_DOWN then
42:           ship = 1;
43:        end
44:     end
45:  end;

 

The central loop is actually split in two other loops in parallel: one to run the game steps (lines 20-34), and the other to handle input from the player (lines 36-44).

The game steps run periodically, depending on the current speed of the game (line 21). For each loop iteration, the step is incremented and the screen is redrawn (lines 22-23).
Then, the ship is checked for collision with meteors (lines 25-27), and with the finish line (lines 29-31).
Céu supports returning from blocks with an assignment, hence, lines 26 and 30 escape the whole par and assign to the `win´ variable in the outer loop (line 18).
The points are incremented before each iteration of the loop (line 33).

To handle input events, we wait for key presses in a loop (line 37) and change the ship position accordingly (lines 39, 42).
Note that there are no possible race conditions on variable `ship´ because the two loops in the par statement react to different events (i.e. wall-clock time and keys).

After returning from the central loop, we run the code for the “game over” behavior, which executes an animation if the ship collided with a meteor:

     // CODE 3: game over
47:  par/or do
48:     await Key;
49:  with
50:     if !win then
51:        loop do
52:           await 100ms;
53:           _lcd.setCursor(0, ship);
54:           _lcd.write('');
58:        end
59:     end
60:  end

 

The animation loop (lines 51-58) continuously displays the ship in the two directions, suggesting that it has hit a meteor.
The animation is interrupted when the player presses a key (line 48), proceeding to the game restart.

Finally, we need to generate the key events to the program itself. As we use a third-party push-button component, the default Arduino binding does not provide event handling for it.
We place the whole program in parallel with the input key generator:

   0:  par do
1-61:     // CODE FOR THE GAME
  62:  with
  63:     int key = _KEY_NONE;
  64:     loop do
  65:        int read1 = _analog2key(_analogRead(0));
  66:        await 50ms;
  67:        int read2 = _analog2key(_analogRead(0));
  68:        if read1==read2 && key!=read1 then
  69:           key = read1;
  70:           if key != _KEY_NONE then
  71:              async do
  72:                 emit Key = read1;
  73:              end
  74:           end
  75:        end
  76:     end
  77:  end

 

The code samples data of an analog port with a delay of 50ms to avoid bouncing (lines 65-67).
If two consecutive reads point to the same key and they are different from the previous change (line 68), then we change the key (line 69) and generate a new event (in the case of a key press, lines 70-74).
The `async´ block is mandatory for generating input events to the program.

Conclusion

Arduino is an interesting target platform for Céu, given its memory constraints and lack of a high-level programming alternative.

The demo shows how complementary activities can be written in separate to run in parallel, reducing complexity.
The code does not become polluted with tons of globals for controlling state, easing the code maintenance.

The complete source code is around 170 lines and also includes all C definitions to generate the map, redraw the scene on the LCD, etc.

[1] http://arduino.cc/

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

Written by francisco

July 8, 2012 at 10:25 pm

Posted in Examples

Tagged with , , ,

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