Tasking Event-B Overview

From Event-B
Revision as of 11:28, 25 November 2011 by imported>Andy (→‎Control Constructs)
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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 DeclaredTask, AutoTask, SharedMachine, Environ
Control Sequence, Loop, Branch, Event, Output
Task Type Periodic(n), Triggered, Repeating, OneShot
Priority -
Event Role Actuating, Sensing
Addressed Variable Address, Base

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 implemented easily in Ada; 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.
    • Declared tasks - (Not currently used) A task template relating to an Ada tasktype declaration.

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

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:

TaskBody ::=
 TaskBody ; TaskBody
 | if Event 
  (elsif Event)* 
  [else Event]
 | do Event [finally Event]
 | Event
 | Output String Variable



Synchronization corresponds to:

  • a subroutine call from task to shared machine, or,
  • sensing or actuating of environment variables.

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 no share state. The synchronization construct also provides the means to specify parameter passing, both in and out of the task.

In the case of a sensing or actuating event, the updates of the action correspond to reads of monitored variables, and writes to controlled variables of the environment.

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, a Shared Machine that is visible to the task, or the Environ machine. Single events in a wrapper correspond to a subroutine call in an implementation.

When Editing the EMF model the constructs have the following names:

Construct EMF name
Sequence Seq
Branch Branch
Loop Do
Text Output Output
EventWrapper EventWrapper
SynchEvents SynchEvents

The Abstract Syntax

The following BNF syntax relates to the EMF model that developers will use in the tutorial. The task body is used to specify the ordering of events. The use of the EMF editor should be seen as a short term solution, in the longer term a suitable form-based or text-based editor is envisaged. Text, Variable and Event nodes are terminals in the syntax, they relate to Event-B elements.

     TaskBody ::= Seq | Branch | Do | EventWrapper | Output 

     Seq  ::=  TaskBody TaskBody

     Branch ::=  Body [SubBranch] Else

     SubBranch ::=  Body [SubBranch]

     Else ::=  EventWrapper

     Body ::=  EventWrapper

     Do ::=  Body [Finally]

     Finally ::=  EventWrapper

     Output ::=  Text Variable

     EventWrapper ::=  SynchEvents

     SynchEvents ::=  Local Remote

     Local ::=  Event

     Remote ::=  Event

Implementing Events

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 role.
    • 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.
    • 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.
    • ProcedureSynch - 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 .
    • Sensing - Identifies an event that maps to a read from the environment. If the environment is simulated without address variables then the sensing event is similar to a ProcedureSynch event, in that it has an update action that models assignment of a return value from a subroutine call. The event parameters act like the actualIn parameters of a ProcedureSynch event. On the other hand, if the event has addressed variables associated with its event parameters, then they map to direct reads from memory mapped variables in the generated code.
    • Actuating - Identifies an event that maps to a write to the environment. If the environment is simulated without address variables then the actuating event has no update action, the parameters act like actualOut parameters of a ProcedureSynch event. If a sensing event has addressed variables associated with its parameters then they map to direct writes to memory mapped variables in the generated code.

Sensing (and actuating) can be viewed as a kind of synchronisation. Synchronisation between tasks and shared objects are represented as subroutine calls. The sensing/actuating synchronisations only occur between tasks and the environment. In implementable code, 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:

  • Event parameter types - Note: formal parameters are place-holders in a subroutine; they are replaced by the actual parameters at call time.
    • FormalIn or FormalOut - event parameters are extended with the ParameterType construct. Extension with formal parameters indicates a mapping to formal parameters in the implementation.
    • ActualIn or ActualOut - Extension with an actual parameter indicates a mapping to an actual parameter in the implementation.
Addressed Variables

When sensing monitored variables, or actuating controlled variables in the environment, we may wish to use explicit memory addresses for use in the final implementation, or perhaps in the environment simulation too. We can link a task's event parameters, and an Environ machines variables, with specific addresses and use these in the generated code.

References