The Synchronous Blog

A blog about reactive programming languages.

Posts Tagged ‘shared-memory

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
end

/* 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
   end
end

/* 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
      end
      emit READ => c;                // signal other applications
   ...
end


 

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.

Conclusion:

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.

 

Advertisements

Written by francisco

April 13, 2014 at 11:42 am

“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

Paper accepted.

leave a comment »

Good news received last week:

Dear Mr. Francisco Sant’Anna,

I am pleased to confirm that your paper “LuaGravity, a Reactive Language
Based on Implicit Invocation” has been accepted for presentation and
publication at SBLP 2009.

All papers went through a rigorous reviewing process by the program
committee. Out of 30 research papers and 3 tutorials submitted, 12
papers and 1 tutorial were accepted.

Please make sure that in the preparation of the final paper you
carefully address the reviewers’ comments. Additionally, at least one
author is required to register in the conference for your paper to
appear in the proceedings.

Congratulations again on having your paper accepted. We look forward to
seeing you in Gramado!

Reviewer’s comments already addressed and final version submitted! One reviewer in particular pointed several constructive observations, which we took very seriously in the final version.

Follows the abstract for the paper:

The reactive programming paradigm covers a wide range of applications, such as
games and multimedia systems.
Mainstream languages do not offer proper support for reactive programming,
lacking language-level primitives that focus on synchronism and interactions
within application parts.
We propose an imperative reactive language, called
LuaGravity, based on
unconventional implicit invocation mechanisms.
LuaGravity allows dataflow programming, sequential imperative execution, and
deterministic use of shared-memory.
With this work, we intend to unite the essential features of reactive languages
while keeping a convenient imperative style of programming.

SBLP [1] is the main Brazilian congress on programming languages. This year it will be held in Gramado on August 18-21.

[1] http://sblp2009.ucpel.tche.br/

“A Synchronous Reactive Language based on Implicit Invocation”

leave a comment »

Observados os dispositivos do art. 6º da DELIBERAÇÃO 001/76, será defendida no dia 16/03/2009 às 10:00h, no local RDC511, a DISSERTAÇÃO DE MESTRADO intitulada “A Synchronous Reactive Language based on Implicit Invocation” do(a) aluno(a) Francisco Figueiredo Goytacaz Sant’Anna candidato ao título de Mestre em Informática.

Abstract:


The reactive programming paradigm covers a wide range of applications, such as games and multimedia systems.
Mainstream languages neglect reactive programming, lacking language-level primitives that focus on synchronism and interactions within application parts.


We propose a new reactive synchronous language, with an imperative style, whose primitives are based on unconventional implicit invocation mechanisms.
With this work, we intend to unite the essential features of reactive languages while keeping a convenient imperative style of programming.
A reactive scheduler is responsible for executing reactors, our processing units, based on dependency relations between them built dynamically.
Our language provides dataflow programming, sequential imperative execution, and deterministic use of shared-memory.

Written by francisco

March 9, 2009 at 10:13 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