Autoren: Tobias Langer, Lukas Osinski und J\u00fcrgen Mottok, OTH Regensburg, Tobias Sch\u00fcle, Siemens AG & Ralph Mader, Continental AG<\/p>\n
Moderne eingebettete Systeme erfordern die parallele Ausf\u00fchrung von Anwendungen mit variierenden Kritikalit\u00e4ten hinsichtlich funktionaler Sicherheit und Echtzeitverhalten. Echtzeitf\u00e4higkeitsklassen bilden eine Basis, mit der solche Systeme entworfen werden k\u00f6nnen. Wir pr\u00e4sentieren eine erste Beschreibung des Echtzeitf\u00e4higkeitsklassenmodells sowie seine Referenzimplementierung auf Basis der Embedded Multicore Building Blocks (EMB\u00b2), einer Bibliothek f\u00fcr die parallele Programmierung eingebetteter Systeme.<\/strong><\/p>\n Im Bereich eingebetteter Plattformen lassen sich derzeit zwei Trends verfolgen: Zum einen steigt die Zahl der integrierten Kerne, so dass in Abgrenzung zu Multicore-Systemen bereits von Manycore-Systemen gesprochen wird; zum anderen werden zunehmend auf spezielle Anwendungen zugeschnittene Hardware-Komponenten wie DSPs, GPUs oder FPGAs in Prozessoren integriert, wodurch ein Wandel weg von homogenen hin zu heterogenen Systemen vollzogen wird.<\/p>\n Ein aktuelles Kernproblem ist die optimale Ausnutzung dieser Systeme. Hierbei helfen insbesondere moderne Task-basierte Konzepte f\u00fcr die parallele Programmierung, die mittlerweile in den meisten Sprachen zu finden sind. Mit EMB\u00b2 steht eine als Open Source Software verf\u00fcgbare L\u00f6sung bereit, die auch auf die Anforderungen an eingebettete Systeme zugeschnitten ist. Es zeichnet sich jedoch ab, dass zuk\u00fcnftige Systeme den parallelen Betrieb von Anwendungen gemischter Kritikalit\u00e4t hinsichtlich Echtzeitf\u00e4higkeit und funktionaler Sicherheitsanforderungen erlauben m\u00fcssen.<\/p>\n Das im Folgenden vorgestellte Echtzeitf\u00e4higkeitsklassenmodell separiert eingebettete Systeme in Stufen, welche Anwendungen entlang ihrer Kritikalit\u00e4t voneinander isolieren. Zudem beschreiben wir eine Referenzimplementierung einer dieser Kritikalit\u00e4tsstufen in EMB\u00b2.<\/p>\n Die Embedded Multicore Building Blocks [1][2] sind eine von Siemens entwickelte Bibliothek f\u00fcr die Entwicklung paralleler Anwendungen, insbesondere f\u00fcr heterogene Systems-on-a-Chip. EMB\u00b2 baut auf der Multicore Task Management API (MTAPI) auf, einer von der Multicore Association standardisierten Spezifikation f\u00fcr die Umsetzung von Task-Parallelit\u00e4t in eingebetteten Systemen.<\/p>\n Zudem enth\u00e4lt EMB\u00b2 nicht-blockierende, threadsichere Datenstrukturen, parallele Algorithmen sowie Schablonen f\u00fcr die Entwicklung von datenflussorientierten Applikationen.<\/p>\n MTAPI beschreibt Komponenten heterogener eingebetteter Systeme als Knoten (Nodes). Ein Prozessor mit 4 Kernen bildet beispielsweise einen eigenen Knoten, ebenso wie eine GPU oder ein DSP. Diese Nodes stehen dann zur Ausf\u00fchrung von Anwendungen bereit, wobei jeder Knoten sein eigenes Scheduling definiert. Es sei angemerkt, dass MTAPI keine Schedulingstrategien explizit vorschreibt.<\/p>\n MTAPI-Anwendungen bestehen aus mehreren Tasks, dabei bezeichnet ein Task eine bestimmte Aufgabe, sowie den zugeh\u00f6rigen Daten. Die Aufgaben k\u00f6nnen sowohl durch Programmcode f\u00fcr verschiedene Prozessorarchitekturen als auch durch Hardware realisiert werden.<\/p>\n Tasks werden innerhalb der Knoten verwaltet und ausgef\u00fchrt. EMB\u00b2 realisiert dies durch priorit\u00e4tenbasiertes Work Stealing (eine allgemeine Beschreibung von Work Stealing ist in [3] zu finden). Jeder Kern verf\u00fcgt \u00fcber eine Queue pro Priorit\u00e4tsstufe, welche abgearbeitet wird. Sobald ein Kern leerl\u00e4uft, „stiehlt“ er sich einen unbearbeiteten Task von einem anderen Kern. Die Verarbeitung der Tasks verl\u00e4uft nach Run-to-Completion-Semantik. Einmal gestartet, werden Tasks nicht mehr unterbrochen.<\/p>\n Dies reduziert bei parallelen Anwendungen den Overhead durch Threads, da weder Kontextwechsel notwendig sind, noch Tasks oder Daten zwischen Kernen migriert werden m\u00fcssen. Au\u00dferdem werden potenzielle Race Conditions unterbunden.<\/p>\n Mit steigenden Anforderungen an eingebettete Systeme haben Multi- und Manycore-Systeme auch im Bereich der Echtzeitsysteme Einzug gehalten. Diese Systeme stellen immer noch eine gro\u00dfe Herausforderung dar, insbesondere das Scheduling. Genaue Analysen der Task-Systeme hinsichtlich ihres Zeitverhaltens gestalten sich oft wesentlich schwieriger als bei vergleichbaren Single-Core-Systemen.<\/p>\n Daher werden h\u00e4ufig Anwendungstasks bereits zur Designzeit fest auf einzelne Kerne alloziert und dann durch bekannte Single-Core-Schedulingverfahren wie Earliest Deadline First (EDF), Deadline Monotonic oder Rate Monotonic Scheduling verwaltet.<\/p>\n Gerade f\u00fcr Systeme mit wenigen Kernen mag dieser Ansatz zufriedenstellend funktionieren, dennoch ist er mit einer Reihe von Problemen verbunden. Das zugeh\u00f6rige kombinatorische Problem w\u00e4chst rasant mit der Anzahl der Kerne und der Tasks, sodass die Aufteilung schnell sehr aufwendig wird. Auch l\u00e4sst eine feste Verteilung der Tasks nur schwer eine optimale Auslastung des Systems zu.<\/p>\n Globale Schedulingverfahren sind eine Alternative zur Task-Partitionierung. Hier werden zur Verarbeitung anstehende Tasks erst zur Laufzeit durch den Scheduler auf freie Kerne des Systems verteilt.<\/p>\n Ein bew\u00e4hrtes Verfahren aus dem Bereich der globalen Schedulingverfahren f\u00fcr Echtzeitsysteme ist Global EDF (GEDF). Bei diesem Vorgehen kann durch Taskmigration jedoch zus\u00e4tzlicher Overhead entstehen. Gerade bei eingebetteten Systemen mit komplexeren Speicherhierarchien k\u00f6nnen hier erhebliche Kosten entstehen. Diese Kosten k\u00f6nnen eingespart werden, wenn Tasks, \u00e4hnlich dem EMB\u00b2-Modell, nach Run-to-Completion Semantik ausgef\u00fchrt werden, also nicht-pr\u00e4emptives Scheduling eingesetzt wird. In [4] zeigten Guan et al., dass nicht-pr\u00e4emptives GEDF insbesondere auf Systemen mit vielen Kernen hinsichtlich der Einhaltung von Deadlines vergleichbares Verhalten zu pr\u00e4emptivem GEDF zeigt. Echtzeitgarantien k\u00f6nnen weiterhin gew\u00e4hrleistet werden.<\/p>\n Im Folgenden beschreiben wir die Echtzeitf\u00e4higkeitsklassen, welche den zeitgleichen Betrieb von Anwendungen mit verschiedenen Anforderungen, sowohl an Echtzeitf\u00e4higkeit als auch an funktionale Sicherheit, erlauben.<\/p>\n Die Klassen spezifizieren festgelegte, unver\u00e4nderliche Ausf\u00fchrungsmodi. Ein Ausf\u00fchrungsmodus beschreibt, wie die Anwendung ausgef\u00fchrt wird (Schedulingverfahren, Unterbrechbarkeit von Tasks), und legt den synchronisierten Zugriff auf gemeinsame Ressourcen fest. Abh\u00e4ngig von der Anwendungskritikalit\u00e4t kann der Zugriff auf gemeinsame Ressourcen durch wartefreie Algorithmen erm\u00f6glicht werden. Falls notwendig werden explizite Synchronisationsmechanismen, wie Semaphoren und Mutexe, verwendet. Somit wird festgelegt, wie und ob Anwendungen verschiedener Betriebsklassen hinsichtlich ihrer Betriebsmittel miteinander interagieren. Damit wird eine Isolation der Anwendungen zueinander garantiert.<\/p>\n Die Unterteilung der Anwendungen in Echtzeitf\u00e4higkeitsklassen erfolgt dabei entsprechend ihrer Anforderungen hinsichtlich funktionaler Sicherheit und der daraus resultierenden Echtzeitf\u00e4higkeit.<\/p>\n Abbildung 1 (siehe\u00a0PDF<\/a>) zeigt eine \u00dcbersicht \u00fcber das Modell der Echtzeitf\u00e4higkeitsklassen. Ausgehen von der nichtmodifizierten EMB\u00b2-Bibliothek erstrecken sie sich, graduell steigend, hin zu harten Echtzeitgarantien.<\/p>\n In der EMB\u00b2 Klasse findet sich die EMB\u00b2 Bibliothek nach aktuellem Stand wieder. Anwendungstasks werden durch Round-Robin gleichm\u00e4\u00dfig auf die Knoten des Systems verteilt. Dort werden sie im Anschluss durch priorit\u00e4tsbasiertes Work Stealing abgearbeitet, wodurch ein hoher Durchsatz garantiert wird. Die Tasks laufen dabei nach Run-to-Completion Semantik.<\/p>\n Der Zugriff auf gemeinsame Daten wird durch nicht-blockierende Datenstrukturen gesch\u00fctzt.<\/p>\n Ebenso wie in der EMB\u00b2 Klasse werden Tasks in der Echtzeit-Klasse mit Run-to-Completion-Semantik abgearbeitet. Der Zugriff auf gemeinsame Ressourcen erfolgt auch \u00fcber nicht-blockierende Datenstrukturen.<\/p>\n Anstelle von Work-Stealing kommt nicht-pr\u00e4emptives GEDF zum Einsatz. Dadurch werden Tasks mit geringerem Durchsatz abgearbeitet, allerdings k\u00f6nnen Echtzeitgarantien f\u00fcr die Fertigstellung der Tasks gegeben werden.<\/p>\n Die Pr\u00e4emptives EMB\u00b2 Klasse beschreibt klassische, harte Echtzeitsysteme. Tasks k\u00f6nnen w\u00e4hrend ihrer Ausf\u00fchrung unterbrochen werden. Dadurch werden negative Einfl\u00fcsse auf andere Tasks minimiert.<\/p>\n Anstelle der bisherigen nicht-blockierenden Datenstrukturen treten hier blockierende Datenstrukturen und Synchronisationsmittel (bspw. Semaphoren und Mutexe). M\u00f6gliche Priorit\u00e4tsinversionen beim Zugriff auf gemeinsame Ressourcen werden durch den Einsatz entsprechender Protokolle verhindert.<\/p>\n Als Referenzimplementierung der Echtzeitf\u00e4higkeitsklassen wurde das Echtzeitscheduling, wie es in der Echtzeit EMB\u00b2 Klasse beschrieben ist, in EMB\u00b2 umgesetzt. Dazu wurde die MTAPI-Implementierung erweitert und die EMB\u00b2-Schnittstellen dahingehend ausgebaut, dass Taskdeadlines bei der Benutzung der parallelen Algorithmen angegeben werden k\u00f6nnen.<\/p>\n Wie zuvor ausgef\u00fchrt, werden die Tasks eines Knoten bei in EMB\u00b2 Klasse durch priorit\u00e4tsbasiertes Work Stealing verarbeitet. Dabei verwaltet jeder Kern die zur Ausf\u00fchrung stehenden Tasks in Abh\u00e4ngigkeit ihrer Priorit\u00e4t in einer eigenen Queue.<\/p>\n Zur Umsetzung des globalen EDF-Algorithmus wurde in der MTAPI-Implementierung die lokalen Queues durch eine knotenweite Task-Queue ersetzt. Diese enth\u00e4lt alle, zur Ausf\u00fchrung bereitstehenden Tasks, sortiert nach Deadline.<\/p>\n Durch die zentralisierte Queue kann garantiert werden, dass zu jedem Schedulingzeitpunkt der Task mit der n\u00e4chsten Deadline ausgef\u00fchrt wird. Damit werden die Anforderungen f\u00fcr GEDF erf\u00fcllt. Die Schedulingzeitpunkte finden immer dann statt, wenn ein Task abgearbeitet wurde.<\/p>\n Der Schedulingmodus f\u00fcr einen Knoten kann bei der Initialisierung festgelegt werden:<\/p>\n embb::mtapi::NodeAttribute attr;<\/p>\n attr.SetSchedulerMode(GLOBAL_EDF);<\/p>\n embb::mtapi::Node::Initialize(DOMAIN_ID, NODE_ID, attr);<\/p>\n<\/div>\n <\/p>\n Nach der Initialisierung der Knoten k\u00f6nnen mithilfe sogenannter Execution Policies Tasks mit definierter Deadline gestartet werden:<\/p>\n auto deadline_duration = embb::base::DurationMilliseconds(40);<\/p>\n embb::mtapi::ExecutionPolicy deadline(deadline_duration);<\/p>\n embb::mtapi::TaskAttribute deadline_attribute;<\/p>\n deadline_attribute.SetPolicy(deadline);<\/p>\n node.Start(task, arguments, results, deadline_attribute);<\/p>\n<\/div>\n <\/p>\n Ferner ist es m\u00f6glich, mehrere zusammengeh\u00f6rige Tasks mit einer gemeinsamen Deadline zu starten, wie es beispielsweise f\u00fcr parallele Algorithmen notwendig ist (der durch die ForEach-Schleife parallel auszuf\u00fchrende Code ist im Folgenden durch eine Lambda-Funktion gegeben):<\/p>\n std::vector<int> values = {1, 2, 3, 4, 5, 6, 7, 8, 9};<\/p>\n embb::mtapi::ExecutionPolicy deadline(deadline_duration);<\/p>\n embb::algorithms::ForEach(values.begin(), values.end(),<\/p>\n [] (int& val) {val *= val;}, deadline_policy);<\/p>\n Aufgrund funktionaler wie nicht-funktionaler Anforderungen m\u00fcssen moderne Echtzeitsysteme die parallele Ausf\u00fchrung von Anwendungen mit verschiedenen Anspr\u00fcchen an Echtzeitf\u00e4higkeit und funktionale Sicherheit erm\u00f6glichen. Mithilfe der vorgestellten Echtzeitf\u00e4higkeitsklassen lassen sich solche Systeme besser beschreiben und umsetzen. Zudem wurde eine Referenzimplementierung f\u00fcr das Scheduling von Echtzeitanwendungen nach dem Global-EDF-Verfahren in EMB\u00b2 vorgestellt. In weiteren Schritten soll das von uns entwickelte Konzept hinsichtlich bekannter Echtzeitmetriken untersucht sowie f\u00fcr eine Automotive Plattform portiert werden.<\/p>\n [1] T. Sch\u00fcle. „EMB\u00b2 = Parallel + Heterogen \u2013 Parallele Programmierung von Systems-on-a-Chip“. ESE Kongress, 2015. Beitrag als PDF downloaden<\/strong><\/a><\/p>\n Wollen Sie sich auf den aktuellen Stand der Technik bringen?<\/strong><\/p>\n Dann informieren Sie sich\u00a0hier<\/strong>\u00a0<\/a>zu Schulungen\/ Seminaren\/ Trainings\/ Workshops und individuellen Coachings von MircoConsult zum Thema Embedded- und Echtzeit-Softwareentwicklung.<\/p>\n Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie\u00a0hier<\/a>.<\/strong><\/p>\n Wertvolles Fachwissen zum Thema Embedded- und Echtzeit-Softwareentwicklung steht\u00a0hier<\/strong>\u00a0<\/a>f\u00fcr Sie zum kostenfreien Download bereit.<\/p>\n Zu den Fachinformationen<\/strong><\/a> Echtzeitanwendungen im Kontext paralleler Programmiermodelle Autoren: Tobias Langer, Lukas Osinski und J\u00fcrgen Mottok, OTH Regensburg, Tobias Sch\u00fcle, Siemens AG & Ralph Mader, Continental AG Beitrag – Embedded Software Engineering Kongress 2016 Moderne eingebettete Systeme erfordern die parallele Ausf\u00fchrung von Anwendungen mit variierenden Kritikalit\u00e4ten hinsichtlich funktionaler Sicherheit und Echtzeitverhalten. Echtzeitf\u00e4higkeitsklassen bilden eine Basis, mit der solche […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","inline_featured_image":false,"footnotes":""},"categories":[],"tags":[],"class_list":["post-7998","post","type-post","status-publish","format-standard","hentry"],"acf":[],"yoast_head":"\nEMB2<\/sup><\/h2>\n
Globales Echtzeitscheduling<\/h2>\n
Echtzeitf\u00e4higkeitsklassen<\/h2>\n
Echtzeitf\u00e4higkeitsklasse EMB\u00b2<\/h2>\n
Echtzeitf\u00e4higkeitsklasse Echtzeit EMB\u00b2<\/h2>\n
Echtzeitf\u00e4higkeitsklasse Pr\u00e4emptives EMB\u00b2<\/h2>\n
Umsetzung der Echtzeitf\u00e4higkeitsklassen in EMB\u00b2<\/h2>\n
Zusammenfassung<\/h2>\n
Literaturverzeichnis<\/h2>\n
\n[2] T. Sch\u00fcle. „Embedded Multicore Building Blocks \u2013 Parallel Programming made Easy“. Embedded World, 2015.
\n[3] Robert D. Blumofe, Charles E. Leiserson. „Scheduling multithreaded computations by work stealing“. Journal of the ACM, Band 46, Nr. 5, 1999.
\n[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.<\/p>\n
\nEchtzeit – MicroConsult Trainings & Coachings<\/h2>\n
\nEchtzeit – Fachwissen<\/h2>\n
\n
\nFachwissen zu weiteren Themen unseren Portfolios finden Sie\u00a0hier<\/a>.<\/strong><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"