Difference between revisions of "Tasking Event-B Overview"

From Event-B
Jump to navigationJump to search
imported>Andy
imported>Andy
 
(159 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
=== Tasking Event-B ===
 
=== Tasking Event-B ===
The following text can be read in conjunction with the slides<ref name = "Zurich2010Slides">http://deploy-eprints.ecs.soton.ac.uk/260/2/CGSlidesAndy%2520Edmunds%2520-%2520Code%2520Generation%2520Slides.pdf</ref> from the Deploy Plenary Meeting - Zurich 2010.
+
Tasking Event-B can be viewed as an extension of the existing Event-B language. We use the existing approaches of refinement and decomposition to structure a project that is suitable for a Tasking Development. During the modelling phase parameters are introduced to facilitate decomposition. As a result of the decomposition process, parameters become part of the interface that enables event synchronization. We make use of this interface and add information (see [[#Implementing Events]]) to facilitate code generation. The tasking extension consists of the constructs in the following table.
 
 
Tasking Event-B can be viewed as an extension of the existing Event-B language. We use the existing approaches of refinement and decomposition to structure a development that is suitable for construction of a Tasking Development. At some point during the modelling phase parameters may have to be introduced to facilitate decomposition. This constitutes a natural part of the refinement process as it moves towards decomposition and on to the implementation level. During decomposition parameters form part of the interface that enables event synchronization. We make use of this interface and add information (see [[#Implementing Events]]) to facilitate code generation. The tasking extension consists of the constructs in the following table.
 
  
 
<center>
 
<center>
 
{| border="1"
 
{| border="1"
|Construct
+
!Construct
|Options
+
!Options
 
|-
 
|-
 
|Machine Type
 
|Machine Type
|DeclaredTask, AutoTask, SharedMachine
+
|[http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Tasking_Machines AutoTask], [http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Shared_Machines Shared], [http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#The_Environ_Machine Environ]
 
|-
 
|-
|Control
+
|[http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Control_Constructs_used_in_the_Task_body Task body]
|Sequence, Loop, Branch, EventSynch
+
|Sequence, Loop, Branch, Event, Output
 
|-
 
|-
|Task Type
+
|[http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Tasking_Machines Task Type]
|Periodic(n), Triggered, Repeating, OneShot
+
|Periodic, Repeating, OneShot
 
|-
 
|-
|Priority
+
|Priority
| -
+
| n
|-
 
|Event Type
 
|Branch, Loop, ProcedureDef, ProcedureSynch
 
|-
 
|Parameter Type
 
|ActualIn, ActualOut, FormalIn, FormalOut
 
 
|}
 
|}
 
</center>
 
</center>
  
=== Tasking Developments ===
+
==== Tasking Machines ====
A Tasking Development is generated programmatically, at the direction of the user; the Tasking Development consists of a number of machines (and perhaps associated contexts). In our approach we make use of the Event-B EMF extension mechanism which allows addition of new constructs to a model. The machines in the Tasking Development are extended with the constructs shown in the table, and may be viewed as keywords in a textual representation of the language. With extensions added, a Tasking Development can be translated to a common language model for mapping to implementation source code. There is also a translator that constructs new machines/contexts modelling the implementation, and these should refine/extend the existing elements of the Event-B project.
+
The following constructs relate to Tasking and Environ Machines, and provide implementation details. Timing of periodic tasks is not modelled formally. Tasking and Environ Machines model Ada tasks, so they can be map easily to Ada; and can implemented in C using the pthread library, or in Java using threads.
  
==== Tasking Machines ====
+
* Tasking Machines may be one of the following types:
The following constructs relate only to Tasking Machines, and provide implementation details. Timing of periodic tasks is not modelled formally. Tasking Machines are related to the concept of an Ada task. These can be implemented in Ada using tasks, in C using the pthread library C, or in Java using threads.
+
** AutoTasks - Anonymous Tasks running from start-up.
 +
 
 +
''Auto Tasks'' are tasks that will be declared and defined in the ''Main'' procedure of the implementation. The effect of this is that the ''Auto Tasks'' are created when the program first loads, and then activated (made ready to run) before the ''Main'' procedure body runs.
  
* Tasking Machines may be characterised by the following types:
+
* Tasking and Environ Machines options are:
** AutoTasks - Singleton Tasks.
+
** TaskType - Defines the scheduling, cycle and lifetime of a task. i.e. one-shot periodic or triggered. The period of a task is specified in milliseconds.
** Declared tasks - (Not currently used) A task template relating to an Ada ''tasktype'' declaration.
+
** Priority - An integer value is supplied, the task with the highest value priority takes precedence when being scheduled. The default priority is 5.
** TaskType - Defines the scheduling, cycle and lifetime of a task. i.e. one-shot periodic or triggered.
 
** Priority - An integer value is supplied, the task with the highest value priority takes precedence when being scheduled.
 
  
 
==== Shared Machines ====
 
==== Shared Machines ====
A Shared Machine corresponds to the concept of a protected resource, such as a monitor. They may be implemented in Ada as a Protected Object, in C using mutex locking, or in Java as a monitor.
+
A Shared Machine models a protected resource, such as a monitor. It may be implemented in Ada as a Protected Object, in C using mutex locking, or in Java as a monitor.
 +
 
 +
* A Shared Machine is identified using the ''Shared Machine'' annotation.
 +
 
 +
==== The Environ Machine ====
 +
An Environ machine is a model of the environment. It can be used to generate code for use in a simulation, or be discarded in the case that a simulated environment is not required.
  
* Applied to the Shared Machine we have:
+
* An Environ Machine is identified using the ''Environ Machine'' annotation.
** A SharedMachine ''keyword'' that identifies a machine as a Shared Machine.
 
  
=== Implementation Specifics ===
+
=== Control of Program Flow ===
At the stage where we are considering how to implement the Event-B development we need to think about controlling the flow of execution, and how events should be implemented. The following section describes the constructs that we have introduced to facilitate this.
+
At the implementation stage we need to think about controlling the flow of execution; and where interaction with the environment is concerned, how events should be implemented. The following section describes the constructs that we have introduced to facilitate this.
==== Control Constructs ====
+
==== Control Constructs used in the Task body ====
 
Each Tasking Machine has a ''task body'' which contains the flow control (algorithmic constructs).  
 
Each Tasking Machine has a ''task body'' which contains the flow control (algorithmic constructs).  
  
Line 56: Line 52:
 
** Branch - choice between a number of mutually exclusive events.
 
** Branch - choice between a number of mutually exclusive events.
 
** Loop - event repetition while it's guard remains true.
 
** Loop - event repetition while it's guard remains true.
** Event Synchronisation - synchronization between an event in a Tasking Machine and an event in a Shared Machine. Synchronization corresponds to an subroutine call with atomic (with respect to an external viewer) updates. The updates in the protected resource are implemented by a procedure call to a protected object, and tasks do no share stateThe synchronization construct also provides the means to specify parameter passing, both in and out of the task.
+
** Event - a wrapper for the Event-B element (soon to be redundant).   
** Event wrappers - The event synchronization construct is contained in an event wrapper. The wrapper may also contain a single event (we re-use the synchronization construct, but do not use it for synchronizing). The event may belong to the Tasking Machine, or to a Shared Machine that is visible to the task. Single events in a wrapper correspond to a subroutine call in an implementation.
+
** Text Output - writes textual output to the screen.
  
==== Implementing Events ====
+
The syntax for task bodies, as used in the Rose TaskBody editor, is as follows:
An event's role in the implementation is identified using the following extensions which are added to the event. Events used in task bodies are 'references' that make use of existing event definitions from the abstract development. The events are extended. to assist with translation, with a keyword indicating their role in the implementation.
 
  
* Event implementation.
+
<br/>
** Branch - In essence a task's event is split in the implementation; guards are mapped to branch conditions and actions are mapped to the branch body. If the branch refers to a Shared Machine event (procedureDef) then this is mapped to a simple procedure call.  
+
[[Image:Syntax2.png]]
** Loop - The task's event guard maps to the loop condition and actions to to loop body. If the loop refers to a Shared Machine event then it is mapped to a simple procedure call.
+
<br/>
** ProcedureSych - This usually indicates to the translator that the event maps to a subroutine, but an event in a task may not require a subroutine implementation if its role is simply to provide parameters for a procedure call.
 
** ProcedureDef - Identifies an event that maps to a (potentially blocking) subroutine definition. Event guards are implemented as a conditional wait; in Ada this is an entry barrier, and in C may use a pthread condition variable .
 
  
In an implementation, when an subroutine is defined, its formal parameters are replaced by actual parameter values at run-time. To assist the code generator we extend the Event-B parameters. We identify formal and actual parameters in the implementation, and add the following keywords to the event parameters, as follows:
+
The ''String'' will be an event name, a variable name, or a text fragment to be output to the screen. The concrete syntax is shown in bold red font. '*' indicates 0 or more; [] indicates 0 or 1.
  
* Event parameter types
+
==== Translating Branches ====
** FormalIn or FormalOut - event parameters are extended with the ParameterType construct. Extension with formal parameters indicates a mapping to formal parameters in the implementation.
+
In the explanation that follows, there may be a number of sub-branches, so we index the events of sub-branches (if they exist) with ''i''. Events can be used in the branching constructs, ''if'', ''elseif'' or ''else'', in the following way,
** ActualIn or ActualOut - Extension with an actual parameter indicates a mapping to an actual parameter in the implementation.
+
 
 +
if evt_1
 +
[ elseif evt_i ]*
 +
else evt _ n
 +
 
 +
where i = 2..(n-1)
 +
 
 +
The events are translated to pseudocode in the following way:
 +
 
 +
if( g_1 ) then a_1
 +
[ elsif( g_i ) then a_i end ]*
 +
else a_n end
 +
 
 +
However, the guards of each branch must be disjoint; and of all branches must be complete.
 +
 
 +
So the guards of each event should be as follows;
 +
 
 +
if evt_1 = g_1 -> a_1                // evt_1
 +
[ elseif not(g_(i-1)) & g_i -> a_i ] // evt_i starting from ''i'' = 2
 +
else not(g_(i-1)) -> a_n            // there of no guards ''g_n''
 +
 
 +
In each sub-branch the guards of the preceding branches are negated, and the current guard added. The current guard is translated to the branch condition in the code, and the other guards are redundant. The ''else'' branch is an exception since it has no guard of its own. In a future enhancement we can produce proof obligations to show that the branch is disjoint and guard coverage is complete.
 +
 
 +
===== Event Translation =====
 +
When an event, used in the task body, is translated to an implementation its translation depends on where it is used in the task body. The mappings are relatively simple for branch, loop, and sequence; but, in addition to the parent construct, the Event translation depends on whether it is part of a synchronization. Obviously the simplest translation is when no synchronization is involved. The translator checks the composed machine to see if the event is paired in a combined event. We say that events is a Tasking machine are local, and that events in a Shared or Environ machine, are remote. If there is no synchronization, then the actions of the local event are expanded in-line in the subroutine body.
 +
 
 +
<span style="color: RED">'''Note''': As a result of the decomposition process, the decomposition tool can produce a remote event, without a corresponding local event. This happens when modelling a task that updates a (remote) shared machine, but does not pass any parameters and has no local update. A local event, with no guards and skip action, must be added manually to the tasking machine, and also added to the composed machine. The code generator will then create an implementation with a subroutine call (with no parameters) causing only remote updates. The addition of the 'dummy' event will be automated in the future. It is not necessary to have a dummy remote event if a remote event does not exist.</span>
 +
 
 +
See [[ Outstanding Tooling Issues]]
 +
 
 +
===== Synchronization =====
 +
 
 +
Synchronization between local events (in AutoTasks) and remote events (in shared/Environ Machines) is determined using the composed machine. To use an event simply enter its name in the TaskBody editor. The translator will in-line any local actions, and add a call to perform remote updates, and obtain remote data.
 +
 
 +
Synchronization can corresponds to:
 +
* a subroutine call from a task to protected object, or,
 +
* a subroutine call from task to environment simulation (only for events used with a state-machine, when using the read/evaluate/write style of translation).
 +
* a rendezvous between a task and environ simulation (for events specified in a task body (i.e. at an time other than state-machine style above)).
 +
 
 +
In the case of a subroutine call the subroutine is an atomic (with respect to an external viewer) update to state. The updates in the protected resource are implemented by a procedure call to a protected object, and tasks do not share state.
 +
 
 +
=== Implementing Events ===
 +
An event's role in the implementation is identified by its parent in the task body. A description follows, in general terms, of the possible implementations of an event.
 +
 
 +
<span style="color: BLUE">'''Note''': An event can be to referred only '''once''' in a task body specification. Of course, shared events (in Shared machines) can be re-used, but this is done through synchronization. The task body only refers to local events</span>
 +
 
 +
* Event roles in implementation:
 +
** Branching: an event is split in the implementation; guards are mapped to branch conditions, and actions are mapped to the branch body. If the branch synchronizes with a Shared machine's event then this is mapped to a procedure call.
 +
** Looping: as in branching, the event is split; the guard maps to the loop condition, and actions to to loop body. If the event synchronizes with a Shared Machine event then it is mapped to a procedure call.
 +
** Event: if the event is not contained in a branch or loop then it is one of the following:
 +
*** A local-only event - the event only contains local updates, which are expanded to update actions in the implementation. In this case guards not permitted in the event.
 +
*** A synchronizing event - local updates are expanded to become update actions in the implementation, remote updates are performed by subroutine call. Guards in the remote event may block; in Ada this is implemented as an entry barrier, and in C can be implemented using a pthread condition variable.
 +
 
 +
=== Theories, for Generating Code ===
 +
 
 +
See [http://wiki.event-b.org/index.php/The_Use_of_Theories_in_Code_Generation The Use of Theories in Code Generation]
 +
 
 +
=== State-Machines and Code Generation ===
 +
 
 +
 
 +
See [http://wiki.event-b.org/index.php/State-Machines_and_Code_Generation State-Machines and Code Generation]
  
 
== References ==
 
== References ==
  
 
<references/>
 
<references/>
 +
 +
 +
[[Category:User documentation]]

Latest revision as of 08:43, 2 September 2013

Tasking Event-B

Tasking Event-B can be viewed as an extension of the existing Event-B language. We use the existing approaches of refinement and decomposition to structure a project that is suitable for a Tasking Development. During the modelling phase parameters are introduced to facilitate decomposition. As a result of the decomposition process, parameters become part of the interface that enables event synchronization. We make use of this interface and add information (see #Implementing Events) to facilitate code generation. The tasking extension consists of the constructs in the following table.

Construct Options
Machine Type AutoTask, Shared, Environ
Task body Sequence, Loop, Branch, Event, Output
Task Type Periodic, Repeating, OneShot
Priority n

Tasking Machines

The following constructs relate to Tasking and Environ Machines, and provide implementation details. Timing of periodic tasks is not modelled formally. Tasking and Environ Machines model Ada tasks, so they can be map easily to Ada; and can implemented in C using the pthread library, or in Java using threads.

  • Tasking Machines may be one of the following types:
    • AutoTasks - Anonymous Tasks running from start-up.

Auto Tasks are tasks that will be declared and defined in the Main procedure of the implementation. The effect of this is that the Auto Tasks are created when the program first loads, and then activated (made ready to run) before the Main procedure body runs.

  • Tasking and Environ Machines options are:
    • TaskType - Defines the scheduling, cycle and lifetime of a task. i.e. one-shot periodic or triggered. The period of a task is specified in milliseconds.
    • Priority - An integer value is supplied, the task with the highest value priority takes precedence when being scheduled. The default priority is 5.

Shared Machines

A Shared Machine models a protected resource, such as a monitor. It may be implemented in Ada as a Protected Object, in C using mutex locking, or in Java as a monitor.

  • A Shared Machine is identified using the Shared Machine annotation.

The Environ Machine

An Environ machine is a model of the environment. It can be used to generate code for use in a simulation, or be discarded in the case that a simulated environment is not required.

  • An Environ Machine is identified using the Environ Machine annotation.

Control of Program Flow

At the implementation stage we need to think about controlling the flow of execution; and where interaction with the environment is concerned, how events should be implemented. The following section describes the constructs that we have introduced to facilitate this.

Control Constructs used in the Task body

Each Tasking Machine has a task body which contains the flow control (algorithmic constructs).

  • We have the following constructs available in the Tasking Machine body:
    • Sequence - for imposing an order on events.
    • Branch - choice between a number of mutually exclusive events.
    • Loop - event repetition while it's guard remains true.
    • Event - a wrapper for the Event-B element (soon to be redundant).
    • Text Output - writes textual output to the screen.

The syntax for task bodies, as used in the Rose TaskBody editor, is as follows:


Syntax2.png


The String will be an event name, a variable name, or a text fragment to be output to the screen. The concrete syntax is shown in bold red font. '*' indicates 0 or more; [] indicates 0 or 1.

Translating Branches

In the explanation that follows, there may be a number of sub-branches, so we index the events of sub-branches (if they exist) with i. Events can be used in the branching constructs, if, elseif or else, in the following way,

if evt_1
[ elseif evt_i ]*
else evt _ n

where i = 2..(n-1)

The events are translated to pseudocode in the following way:

if( g_1 ) then a_1 
[ elsif( g_i ) then a_i end ]*
else a_n end

However, the guards of each branch must be disjoint; and of all branches must be complete.

So the guards of each event should be as follows;

if evt_1 = g_1 -> a_1                // evt_1 
[ elseif not(g_(i-1)) & g_i -> a_i ] // evt_i starting from i = 2
else not(g_(i-1)) -> a_n             // there of no guards g_n

In each sub-branch the guards of the preceding branches are negated, and the current guard added. The current guard is translated to the branch condition in the code, and the other guards are redundant. The else branch is an exception since it has no guard of its own. In a future enhancement we can produce proof obligations to show that the branch is disjoint and guard coverage is complete.

Event Translation

When an event, used in the task body, is translated to an implementation its translation depends on where it is used in the task body. The mappings are relatively simple for branch, loop, and sequence; but, in addition to the parent construct, the Event translation depends on whether it is part of a synchronization. Obviously the simplest translation is when no synchronization is involved. The translator checks the composed machine to see if the event is paired in a combined event. We say that events is a Tasking machine are local, and that events in a Shared or Environ machine, are remote. If there is no synchronization, then the actions of the local event are expanded in-line in the subroutine body.

Note: As a result of the decomposition process, the decomposition tool can produce a remote event, without a corresponding local event. This happens when modelling a task that updates a (remote) shared machine, but does not pass any parameters and has no local update. A local event, with no guards and skip action, must be added manually to the tasking machine, and also added to the composed machine. The code generator will then create an implementation with a subroutine call (with no parameters) causing only remote updates. The addition of the 'dummy' event will be automated in the future. It is not necessary to have a dummy remote event if a remote event does not exist.

See Outstanding Tooling Issues

Synchronization

Synchronization between local events (in AutoTasks) and remote events (in shared/Environ Machines) is determined using the composed machine. To use an event simply enter its name in the TaskBody editor. The translator will in-line any local actions, and add a call to perform remote updates, and obtain remote data.

Synchronization can corresponds to:

  • a subroutine call from a task to protected object, or,
  • a subroutine call from task to environment simulation (only for events used with a state-machine, when using the read/evaluate/write style of translation).
  • a rendezvous between a task and environ simulation (for events specified in a task body (i.e. at an time other than state-machine style above)).

In the case of a subroutine call the subroutine is an atomic (with respect to an external viewer) update to state. The updates in the protected resource are implemented by a procedure call to a protected object, and tasks do not share state.

Implementing Events

An event's role in the implementation is identified by its parent in the task body. A description follows, in general terms, of the possible implementations of an event.

Note: An event can be to referred only once in a task body specification. Of course, shared events (in Shared machines) can be re-used, but this is done through synchronization. The task body only refers to local events

  • Event roles in implementation:
    • Branching: an event is split in the implementation; guards are mapped to branch conditions, and actions are mapped to the branch body. If the branch synchronizes with a Shared machine's event then this is mapped to a procedure call.
    • Looping: as in branching, the event is split; the guard maps to the loop condition, and actions to to loop body. If the event synchronizes with a Shared Machine event then it is mapped to a procedure call.
    • Event: if the event is not contained in a branch or loop then it is one of the following:
      • A local-only event - the event only contains local updates, which are expanded to update actions in the implementation. In this case guards not permitted in the event.
      • A synchronizing event - local updates are expanded to become update actions in the implementation, remote updates are performed by subroutine call. Guards in the remote event may block; in Ada this is implemented as an entry barrier, and in C can be implemented using a pthread condition variable.

Theories, for Generating Code

See The Use of Theories in Code Generation

State-Machines and Code Generation

See State-Machines and Code Generation

References