Programming Oracle

# Final Assessment - First semester 2020

# Final Assessment - First semester 2019

# Final Assessment - First semester 2018

# Tips

What To Understand About Esterel?

Synchronous model of time:

  • Time divided into sequence of discrete instants
  • Instructions either run and terminate in the same instant or explicitly in later instants

Idea of signals and broadcast:

  • “Variables” that take exactly one value each instant and don’t persist
  • Coherence rule: all writers run before any readers

Causality Issues:

  • Contradictory programs
  • How Esterel decides whether a program is correct

Compilation techniques:

  • Automata: Fast code, Doesn’t scale
  • Netlists: Scales well, Slow code, Good for causality
  • Control-flow: Scales well, Fast code, Bad at causality
  • Discrete Events: Scales well, Fast code, Better with more concurrency
race condition

# 2. Is there a data-race like the RTOS approach?

Answer

In Esterel, the occurrence of data races is less likely compared to the RTOS approach. Esterel is a synchronous programming language that enforces determinism by design. The language is specifically designed for the specification and verification of reactive systems, where the timing and synchronization of events are explicitly defined.

In Esterel, the concept of concurrency is based on the notion of logical parallelism rather than physical parallelism. Esterel programs consist of a set of concurrent processes that execute sequentially in logical time steps. The language provides constructs for specifying the timing constraints and synchronization requirements of these processes, ensuring that their interactions are well-defined and deterministic.

Since Esterel programs are executed in logical time steps and the language enforces deterministic execution, the potential for data races is significantly reduced. Esterel provides built-in mechanisms for synchronization and communication between processes using signals, enabling safe and controlled interactions. The language allows explicit specification of how signals are produced, consumed, and synchronized, ensuring proper coordination and avoiding data race situations.

However, it's important to note that while Esterel minimizes the risk of data races, it is still possible to introduce data races if shared variables or resources are used within the Esterel code in an unsafe manner. Care must be taken to properly handle s**hared data **if used, using appropriate synchronization techniques provided by the language.

In summary, the design principles of Esterel aim to minimize the occurrence of data races through its synchronous and deterministic execution model. However, it is crucial to follow best practices and use the language's synchronization mechanisms correctly to ensure the absence of data races in Esterel programs.

Data races

Data races occur in concurrent programming when multiple threads or processes access shared data concurrently without proper synchronization, and at least one of the accesses is a write operation. A data race is a form of undefined behavior that can lead to unexpected and erroneous program execution.

More formally, a data race occurs when the following conditions are met:

  1. Two or more threads or processes access the same memory location concurrently.
  2. At least one of the accesses is a write operation.
  3. There is no proper synchronization mechanism in place to ensure mutually exclusive access to the shared data.

Data races can result in various issues, including:

  1. Inconsistent or incorrect data: When multiple threads or processes simultaneously read and write to the same shared memory location without proper synchronization, the resulting data can be inconsistent or corrupted. This can lead to incorrect program behavior or unexpected results.

  2. Race conditions: Data races can give rise to race conditions, where the outcome of a program depends on the relative timing and interleaving of the concurrent accesses. Race conditions can cause non-deterministic behavior and make the program difficult to debug and reason about.

  3. Undefined behavior: Data races violate the rules of the programming language and can lead to undefined behavior. The behavior of the program becomes unpredictable, and it may exhibit different results on different runs or platforms.

Preventing data races requires the use of proper synchronization mechanisms, such as locks, semaphores, mutexes, or atomic operations, to ensure exclusive access to shared data. Synchronization ensures that only one thread or process can access the shared data at a given time, preventing data races and ensuring the correctness and consistency of concurrent programs.

Derived statement and Expansion

Derived statement

halt
1

Expansion

loop 
    pause 
end
1
2
3

Derived statement

sustain s
1

Expansion

loop 
    emit s; 
    pause 
end
1
2
3
4

Derived statement

present s then p end
1

Expansion

present s then 
    p 
    else nothing 
end
1
2
3
4

Derived statement

await s
1

Expansion

trap T in 
    loop 
        pause; 
        present s then 
            exit T 
        end 
    end loop 
end
1
2
3
4
5
6
7
8

Derived statement

await immediate s
1

Expansion

trap T in 
    loop 
        present s then 
            exit T 
        end; 
        pause 
    end loop 
end
1
2
3
4
5
6
7
8

Derived statement

suspend p when immediate s
1

Expansion

suspend present s then 
    pause 
end; 
p when s
1
2
3
4

Derived statement

abort p when (immediate) s
1

Expansion

trap T in 
    suspend p when (immediate) s; 
    exit T || await (immediate) s; 
    exit T; 
end
1
2
3
4
5

Derived statement

weak abort p when (immediate) s
1

Expansion

trap T in p; 
    exit T || await (immediate) s; 
    exit T; 
end
1
2
3
4

Derived statement

loop p each s
1

Expansion

loop 
    abort 
        p; 
        halt;
    when s 
end loop
1
2
3
4
5
6

Derived statement

every (immediate) s do p end every
1

Expansion

await (immediate) s; loop p each s
1