ABBs: Atomic Basic Blocks

Motivation

The internal composition of a real-time system is significantly affected by the structural elements of the underlying real-time systems architecture. These elements control how tasks are attached to external events and how cooperating tasks interact with each other.

Research and industry have brought up two fundamentally different manifestations of such real-time systems architectures: On the one hand, there are event-triggered systems and on the other hand, there are time-triggered systems. Event-triggered systems perform tasks directly in response to external events. As a consequence, it depends on the occurrence of these events at which time certain computations are carried out. Time-triggered systems, in contrast, use a static, pre-computed schedule table that is executed cyclically. Thus, at any given time, the task that is currently executed is known.

It is easy to figure out that the event-triggered paradigm can deal much better with events whose precise temporal specification is not known beforehand than its time-triggered counterpart. Such systems, on the other hand, are to be preferred if cyclic tasks are predominant. In that case, time-triggered systems offer a fully predictable behaviour. Thus, application scenarios that have different temporal characteristics are not supported equally well by these paradigms.

Hence, it is logical to go for that paradigm that suits the current application scenario best. Provided a real-time system is built from scratch, this is not a problem, as one can easily choose the ideal real-time paradigm. This is different if some parts of this system already exist; either because some components of other systems should be reused, or because the requirements of the real-time system that currently is being developed have changed. In that case, changing the real-time paradigm is a challenging undertaking, since the real-time systems architecture heavily influences the internal structure of a real-time system. Thus, you can find its structural elements spread all over the application. This especially affects cooperating tasks sharing common resources or exchanging intermediate results. Such critical sections and directed dependencies have to coordinated explicitly in event-triggered systems by means of e.g. semaphores. Within time-triggered systems, these situations are handled implicitly by ordering these tasks appropriately. So, switching the real-time paradigm normally demands for a manual and labour-intensive porting in most cases.

Major Goals

As pointed out above migrating event-triggered systems to time-triggered ones and vice versa is very cumbersome, so it could be quite hard to choose that real-time paradigm the suits the needs of the given real-time system best. Thus, the ambitious goal of this research project is to provide the real-time systems engineer a (semi-)automatic transition between those real-time paradigms to adapt the real-time application to the needs of the real-time system. Within this research project we focus on the transformation of event-triggered source systems to time-triggered target systems.

Such a transition tool, however, demands to deal with the following problems. The answers to them also provide an appropriate foundation of this tool:

• How to handle inter-task dependencies handled?

  Dependencies among cooperating tasks have to be preserved within the transformed target system, of course. For this purpose, such dependencies must be analysed within the source system and an appropriate abstraction is needed to describe them independently of the real-time systems architecture employed in the source system. These dependencies then can be mapped to the desired real-time systems architecture.

• How to ensure temporal requirements?

  Temporal requirements imposed by the real-time system's physical environment also have to be satisfied by the transformed real-time application. Therefore, these temporal properties have to be represented within the abstraction mentioned above. Furthermore, the applied transformation must ensure that these temporal requirements are met in the generated target system.

Solution Approach

Atomic Basic Blocks

By aggregating basic blocks ABBs partition the inter-procedural CFG into smaller portions that do not interact with other tasks. So, the boundaries of such ABBs (called ABB terminations) are marked by origins (called joins) and target points (called joinpoints) of inter-task dependencies. Normally, such joins are implemented by e.g. posting a semaphore and joinpoints can be implemented e.g. by waiting for a semaphore. Finally, inter-task dependencies connecting matching joins and joinpoints (e.g. when a particular semaphore posted at one join is awaited at another joinpoint) form a global dependency graph.

The following small example illustrated these concepts. Every time a character arrives at the serial interface, the task TASK(SerialByte) is activated. It collects the received characters and as soon as a message is complete it inserts the message into a buffer and informs the task TASK(MsgHandler) by setting the event MsgReceived. Thereby, a directed dependency among those tasks is created.

TASK(SerialByte) {
  unsigned char received = getByte();
  message_addTo(serialMsg,received);

  if(message_isComplete(serialMsg)) {
    buffer_insert(buffer,serialMsg);
    SetEvent(MsgHandler,MsgReceived);
  }

  TerminateTask();
}
      

TASK(MsgHandler) {
  Message *currentMsg = 0;
  Initialisation();

  WaitEvent(MsgReceived);
  ClearEvent(MsgReceived);
  currentMsg = buffer_get(buffer);
  handler(currentMsg);

  TerminateTask();
}
      

This directed dependency can be easily demonstrated using the CFGs extracted from TASK(SerialByte) and TASK(MsgHandler). It is easy to spot the conditional statement in the CFG of TASK(SerialByte) and the directed dependency that is indicated as dashed arrow.

In this small example every basic block (square box) is enclosed by a single ABB (boxes with rounded corners). Additionally, the basic blocks B2 and B4 are split up in two basic blocks each that also are enclosed by a single ABB. This is necessary as inter-task dependencies shall not originate from or end within the inside of an ABB. On the function level these ABBs just resemble the CFG that is made up by basic blocks. On the system level these CFGs are connected by an inter-task dependency forming a global dependency graph.

System Model

The global dependency graphs are connected to the temporal properties of the physical environment by means of a system model. A system model attaches events to the single tasks, and thereby describes how often certain tasks are released. Periodic events for example are characterised by their period, their phase and their jitter while only the minimum interarrival time (IAT) is known for non-periodic events. In the example picked up above the tasks TASK(SerialByte) and TASK(MsgHandler) both are triggered by a non-periodic event with an IAT of 50 µs and 100 ms respectively.

Furthermore, events so called physical events caused by changes in the real-time system's physical environment and logical events caused by internal state changes within the real-time application are distinguished. In the example above, TASK(SerialByte) is triggered by a physical and TASK(MsgHandler) is triggered by a logical event. Logical events allow for a precise and fine-grained description of the temporal properties of internal activities within a real-time system.

Finally, a deadline marks the latest possible point for the completion of a task. According to the consequences that arise in case of a deadline miss, these deadlines may be classified hard, firm or soft. All deadlines are given relative to the release of the triggered task.

The Real-Time Systems Compiler

Future Work

While working on ABBs and the RTSC we developed the idea that ABB-based dependency graphs are handy for other purposes, too, and are not restricted to the migration from event-triggered to time-triggered systems. Other promising applications comprise e.g. mapping such dependency graphs to multicore systems and distributed systems or replication certain portions of a safety critical real-time system. Currently we are investigating these ideas in the realm of the AORTA research project that is the sequel of the ABB project and is funded by the DFG.