Mixed-criticality systems through real-time capability classes

EMB²

The Embedded Multicore Building Blocks [1][2] are a library developed by Siemens for the development of parallel applications, especially for heterogeneous systems-on-a-chip. EMB² is based on the Multicore Task Management API (MTAPI), a specification standardized by the Multicore Association for implementing task parallelism in embedded systems.

Furthermore, EMB² includes non-blocking, thread-safe data structures, parallel algorithms, and templates for developing data flow-oriented applications.

MTAPI describes components of heterogeneous embedded systems as nodes. A quad-core processor, for example, forms its own node, as do a GPU and a DSP. These nodes are then available for executing applications, with each node defining its own scheduling. It should be noted that MTAPI does not explicitly prescribe any scheduling strategies.

MTAPI applications consist of several tasks, where a task refers to a specific operation and its associated data. These tasks can be implemented through program code for various processor architectures or through hardware.

Tasks are managed and executed within the nodes. EMB² achieves this through priority-based work stealing (a general description of work stealing can be found in [3]). Each core has a queue for each priority level, which is processed. As soon as a core runs out of work, it "steals" an unprocessed task from another core. Task processing follows run-to-completion semantics. Once started, tasks are not interrupted.

This reduces the overhead of threads in parallel applications, as neither context switching nor the migration of tasks or data between cores is necessary. Furthermore, potential race conditions are prevented.

Global real-time scheduling

With increasing demands on embedded systems, multi-core and many-core systems have also found their way into the realm of real-time systems. These systems still pose a significant challenge, particularly scheduling. Accurate analysis of task systems regarding their timing behavior is often considerably more difficult than with comparable single-core systems.

Therefore, application tasks are often allocated to individual cores at design time and then managed using well-known single-core scheduling methods such as Earliest Deadline First (EDF), Deadline Monotonic or Rate Monotonic Scheduling.

While this approach may work satisfactorily for systems with few cores, it is associated with a number of problems. The associated combinatorial problem grows rapidly with the number of cores and tasks, making task allocation very complex. Furthermore, a fixed task distribution makes it difficult to achieve optimal system utilization.

Global scheduling methods are an alternative to task partitioning. Here, tasks awaiting processing are only distributed to free cores of the system by the scheduler at runtime.

A proven method from the field of global scheduling for real-time systems is Global EDF (GEDF). However, this approach can introduce additional overhead through task migration. This can lead to significant costs, especially in embedded systems with more complex memory hierarchies. These costs can be avoided by executing tasks according to run-to-completion semantics, similar to the EMB² model, i.e., by using non-preemptive scheduling. In [4], Guan et al. showed that non-preemptive GEDF exhibits comparable performance to preemptive GEDF in meeting deadlines, particularly on systems with many cores. Real-time guarantees can still be ensured.

Real-time capability classes

Below we describe the real-time capability classes that allow the simultaneous operation of applications with different requirements, both in terms of real-time capability and functional safety.

The classes specify fixed, immutable execution modes. An execution mode describes how the application is run (scheduling methods, task interruptibility) and defines synchronized access to shared resources. Depending on the application's criticality, access to shared resources can be enabled through wait-free algorithms. If necessary, explicit synchronization mechanisms, such as semaphores and mutexes, are used. This determines how and whether applications of different operating systems interact with each other regarding their resources, thus guaranteeing isolation between applications.

The classification of applications into real-time capability classes is based on their requirements regarding functional safety and the resulting real-time capability.

Figure 1 (see PDFFigure 1 shows an overview of the real-time capability class model. Starting with the unmodified EMB² library, they extend, gradually increasing, towards hard real-time guarantees.

Real-time capability class EMB²

The EMB² class currently incorporates the EMB² library. Application tasks are distributed evenly across the system's nodes using round-robin. They are then processed using priority-based work stealing, guaranteeing high throughput. The tasks follow run-to-completion semantics.

Access to shared data is protected by non-blocking data structures.

Real-time capability class Real-time EMB²

Just like in the EMB² class, tasks in the real-time class are processed using run-to-completion semantics. Access to shared resources also occurs via non-blocking data structures.

Instead of work stealing, non-preemptive GEDF is used. This results in lower throughput for tasks, but real-time guarantees for task completion can be given.

Real-time capability class Preemptive EMB²

The Preemptive EMB² class describes classic, hard real-time systems. Tasks can be interrupted during their execution. This minimizes negative impacts on other tasks.

Instead of the previous non-blocking data structures, blocking data structures and synchronization mechanisms (e.g., semaphores and mutexes) are used. Potential priority inversions when accessing shared resources are prevented through the use of appropriate protocols.

Implementation of real-time capability classes in EMB²

As a reference implementation of the real-time capability classes, real-time scheduling, as described in the Real-Time EMB² class, was implemented in EMB². For this purpose, the MTAPI implementation was extended and the EMB² interfaces were expanded to allow task deadlines to be specified when using parallel algorithms.

As previously explained, in the EMB² class, a node's tasks are processed using priority-based work stealing. Each core manages the tasks awaiting execution in its own queue, according to their priority.

To implement the global EDF algorithm, the local queues in the MTAPI implementation were replaced by a node-wide task queue. This queue contains all tasks ready for execution, sorted by deadline.

The centralized queue guarantees that at each scheduling point, the task with the next deadline is executed. This fulfills the requirements for GEDF. Scheduling points occur whenever a task has been completed.

The scheduling mode for a node can be set during initialization:

embb::mtapi::NodeAttribute attr;

attr.SetSchedulerMode(GLOBAL_EDF);

embb::mtapi::Node::Initialize(DOMAIN_ID, NODE_ID, attr);

After the nodes have been initialized, tasks with a defined deadline can be started using so-called execution policies:

auto deadline_duration = embb::base::DurationMilliseconds(40);

embb::mtapi::ExecutionPolicy deadline(deadline_duration);

embb::mtapi::TaskAttribute deadline_attribute;

deadline_attribute.SetPolicy(deadline);

node.Start(task, arguments, results, deadline_attribute);

Furthermore, it is possible to start several related tasks with a common deadline, as is necessary for parallel algorithms (the code to be executed in parallel by the ForEach loop is given below by a lambda function):

std::vector values = {1, 2, 3, 4, 5, 6, 7, 8, 9};

embb::mtapi::ExecutionPolicy deadline(deadline_duration);

embb::algorithms::ForEach(values.begin(), values.end(),

[] (int& val) {val *= val;}, deadline_policy);

Summary

Due to functional and non-functional requirements, modern real-time systems must enable the parallel execution of applications with varying demands on real-time capability and functional safety. The presented real-time capability classes facilitate the better description and implementation of such systems. Furthermore, a reference implementation for scheduling real-time applications using the Global-EDF method in EMB² was presented. In subsequent steps, the concept we developed will be examined with regard to known real-time metrics and ported to an automotive platform.

Bibliography

[1] T. Schüle. „EMB² = Parallel + Heterogeneous – Parallel Programming of Systems-on-a-Chip“. ESE Congress, 2015.
[2] T. School. „Embedded Multicore Building Blocks – Parallel Programming Made Easy“. Embedded World, 2015.
[3] Robert D. Blumofe, Charles E. Leiserson. „Scheduling multithreaded computations by work stealing.“ Journal of the ACM, Volume 46, No. 5, 1999.
[4] N. Guan, W. Yi, Z. Gu, Q. Deng, G. Yu. „New Schedulability Test Conditions for Non-preemptive Scheduling on Multiprocessor Platforms“. Real-Time Systems Symposium, 2008.

Download the article as a PDF

Real-time – MicroConsult Training & Coaching

Do you want to bring yourself up to date with the latest technology?

Then find out more here MircoConsult offers training courses/seminars/workshops and individual coaching on the topic of embedded and real-time software development.

Training & coaching on the other topics in our portfolio can be found here. here.

Real-time expertise

Valuable expertise in the field of embedded and real-time software development is available. here Available for you to download free of charge.

To the specialist information

You can find expertise on other topics in our portfolio here. here.