Autoren: Jens Harnisch, Li Lin, Albrecht Mayer, Gerhard Wirrer, Infineon Technologies AG<\/p>\n
Um die Leistungsf\u00e4higkeit moderner Mehrkernprozessoren nutzen zu k\u00f6nnen, sind je nach Anwendung eine gewisse Synchronisation, zum Beispiel durch Barrieren, und ein Schutz von Ressourcen, zum Beispiel durch Spinlocks, notwendig. Dadurch k\u00f6nnen Deadlocks entstehen, welche nat\u00fcrlich besonders f\u00fcr sicherheitskritische Systeme unerw\u00fcnscht sind. Ein alternatives Pro\u00adgrammier\u00admuster sind lockfreie Algorithmen. Diese m\u00fcssen f\u00fcr die von mehreren Kernen gemeinsam genutzten Datenstrukturen speziell angepasst werden. Es wird eine unbegrenzte Queue vorgestellt, bewertet und in Bezug zu anderen Herangehensweisen gesetzt.<\/strong><\/p>\n Mutexe, Semaphore und Events werden zur Synchronisation paralleler Prozesse \u00a0und zum Schutz gemeinsam genutzter Ressourcen, z.B. Datenstrukturen, von Betriebs\u00adsystemen bereitgestellt.<\/p>\n Zur Implementierung werden atomare Instruktionen der jeweiligen Rechner\u00adarchitektur genutzt. Eine Pseudonotierung f\u00fcr ein Spinlock wird im Folgenden angegeben:<\/p>\n inline void get_spinlock(volatile unsigned long* spinlock_ptr)<\/p>\n {<\/p>\n \u00a0\u00a0\u00a0\u00a0 while (swap(spinlock_ptr, BUSY) == BUSY)<\/p>\n \u00a0\u00a0\u00a0\u00a0 ;<\/p>\n }<\/p>\n Die Funktion swap, innerhalb welcher dann der atomare Maschinenbefehl swap Befehl genutzt wird, liest den aktuellen Wert von der Adresse spinlock_ptr und schreibt den Wert BUSY an die Adresse von spinlock_ptr. Die Ausf\u00fchrung des Maschinenbefehls an sich wird ohne Blockade funktionieren. Aber wenn der Spinlock nicht verf\u00fcgbar wird, dann wird die while-Schleife nicht verlassen; es entsteht ein Deadlock. So k\u00f6nnte es zum Beispiel sein, dass die Software auf einem anderen Kern abgest\u00fcrzt ist und daher der Spinlock nicht mehr freigegeben wird. Spinlocks k\u00f6nnen auch an Priorit\u00e4tsinversion beteiligt sein. Bei mehreren Spinlocks im Design w\u00e4chst die Komplexit\u00e4t. In der ersten Version von Linux f\u00fcr Mehr\u00adkernsysteme gab es daher nur den einen Big Kernel Lock. Allerdings wird damit teilweise die Leistungsf\u00e4higkeit eines Mehrkernsystems auf nur einen Kern reduziert.<\/p>\n Programmierung ohne Blockade (Lock Free Programming) stellt eine seit vielen Jahren bekannte Alternative zur Arbeit mit Mutexen und Spinlocks dar [1]. Dead\u00adlocks k\u00f6nnen damit nicht mehr entstehen. Algorithmen ohne Locks m\u00fcssen auf die zu sch\u00fctzende Datenstruktur angepasst werden, zum Beispiel eine Queue. Oft sind es zwar nur wenige Zeilen Quelltext, aber das Design ist komplex. Weiterhin ver\u00adschenkt man mit diesen Algorithmen potenziell Rechenleistung durch die spekulative Ausf\u00fchrung. Zumindest dieses Problem relativiert sich bei Verf\u00fcgbarkeit vieler Kerne. Das Prinzip lockfreier Programmierung ist gew\u00f6hnlich folgendes:<\/p>\n F\u00fcr die \u00dcberpr\u00fcfung, ob die Datenstruktur zwischenzeitlich ver\u00e4ndert wurde, kann man zum Beispiel einen Pointer nutzen. Zeigt der Pointer noch auf die gleiche Adresse wie beim Anlegen der Kopie, dann hat zwischendurch scheinbar kein anderer Prozess auf der Struktur gearbeitet. Bekannt ist aber das „ABA“ Problem. Dabei zeigt der Pointer beim Anlegen der Kopie auf Adresse A, ebenso wie auch bei der \u00dcberpr\u00fcfung nach Ausf\u00fchrung der Rechnung. Das kann aber Zufall sein. In Wahrheit zeigte der Pointer zwischen\u00addurch auf die Adresse B, ein weiterer Prozess hat die Struktur zwischenzeitlich manipuliert und sein Ergebnis zur\u00fcckgeschrieben. Wenn wir dieses Problem nicht beachten, \u00fcberschreiben wir das Ergebnis des weiteren Prozesses auf der sensiblen Datenstruktur. Zur L\u00f6sung des Problems kann zum Beispiel ein Z\u00e4hler eingef\u00fchrt werden, der bei jedem Zur\u00fcckschreiben der Struktur erh\u00f6ht wird.<\/p>\n Im Gegensatz zur Arbeit mit Mutexen oder Spinlocks, welche recht generisch eingesetzt werden k\u00f6nnen, muss lockfreie Programmierung an die jeweilige Datenstruktur angepasst werden, daher zum Beispiel an verlinkte Listen, Stacks oder Warte\u00adschlangen (Queues). Eine lockfreie unbegrenzte Queue, implementiert in C, wird im Folgenden vorgestellt. Die Software wurde auf einem AURIX 2nd Generation Microcontroller mit 6 Kernen in Betrieb genommen.<\/p>\n Kernelement der Queue ist eine Node, mit dem aktuellen Wert und einem Verweis auf den nachfolgenden Node:<\/p>\n struct Node<\/p>\n {<\/p>\n \u00a0\u00a0\u00a0\u00a0 int value;<\/p>\n \u00a0\u00a0\u00a0\u00a0 struct Node* next;<\/p>\n };<\/p>\n Das Design der Queue unterst\u00fctzt unbegrenzt viele Elemente in der Queue. Eine unbegrenzte Anzahl von Elementen ist nat\u00fcrlich unrealistisch f\u00fcr ein eingebettetes System, aber die Unterst\u00fctzung einer variablen Anzahl von Elementen, z.B. erkannter Objekte in einer Szene f\u00fcr autonomes Fahren, ist ein realistisches Szenario. Das Einf\u00fcgen und L\u00f6schen eines Elements wird im Folgenden erkl\u00e4rt.<\/p>\n Einf\u00fcgen eines Elements in die Queue (Enqueue) L\u00f6schen eines Elementes aus der Queue (Dequeue)<\/strong> Drei der ausgef\u00fchrten Schritte m\u00fcssen mit einer atomaren Compare-und-Swap Instruktion ausgef\u00fchrt werden, im Bild mit CAS bezeichnet. Die Ausf\u00fchrung der atomaren Instruktion kann nicht blockiert werden. Man kann die obige Implementierung der Queue mit herk\u00f6mmlichen Implementierungen f\u00fcr eine Queue vergleichen. Dort wird entweder ein Spinlock f\u00fcr die gesamte Queue verwendet, egal ob man ein Element l\u00f6scht oder eines hinzuf\u00fcgt. Oder zwei Spinlocks werden ver\u00adwendet, jeweils f\u00fcr Einf\u00fcgen bzw. L\u00f6schen eines Elements. Aber all diese her\u00adk\u00f6mmlichen Implementierungen k\u00f6nnen potenziell blockieren.<\/p>\n Analyse und Test von nicht blockierenden Algorithmen sind eher anspruchsvoller als von blockierenden Algorithmen. Gleichzeitigkeit wird ja bei nicht blockierenden Algorithmen explizit unterst\u00fctzt und nicht zeitweise ausgeschlossen, wie bei Imple\u00admentierungen mit Spinlocks. Auf der anderen Seite handelt es sich um ein weit\u00adgehend nichtsynchronisiertes Programmiermuster und nicht um ein Programmier\u00admuster mit Synchronisation, so wie bei Logical Execution Time. Die Programmierung mit nicht blockierenden Algorithmen \u00e4hnelt letztendlich eher Transactional Memory, bei welchem Transaktionen spekulativ ausgef\u00fchrt, aber bei Konflikten wieder r\u00fcckg\u00e4ngig gemacht werden. Die Komplexit\u00e4t nicht blockierender Algo\u00adrithmen muss auch beim Testen ber\u00fccksichtigt werden. Der entwickelte Algorithmus wurde nicht formal verifiziert, sondern nur analysiert. F\u00fcr diese Analyse war die Verf\u00fcgbarkeit des nichtintrusiven Tracesystems MCDS (Multi-Core Debug Solution) auf der Zielplattform, dem AURIX 2nd Generation Microcontroller TC39x, sehr hilfreich. So konnten verschiedene Szenarien der Gleichzeitigkeit genau nachverfolgt werden, z. B. die Sequenz der Zugriffe durch verschiedene Kerne f\u00fcr eine Korrektheitsanalyse, aber auch das exakte Zeitverhalten f\u00fcr eine Performanzanalyse. Beides wird durch\u00a0 besondere MCDS-Eigenschaften erm\u00f6glicht. Dazu z\u00e4hlt der parallele und zeitlich ausgerichtete Trace an verschiedenen Beobachtungspunkten mit sehr hoher zeitlicher Aufl\u00f6sung.<\/p>\n Da mit lockfreier Programmierung Deadlocks schon per Design ausgeschlossen sind, kann die Nutzung vor allem in sicherheitskritischer Software vorteilhaft sein. In [1] wurde dokumentiert, wie durch lockfreie Programmierung sogar eine h\u00f6here Performanz als mit Spinlocks erreicht wurde. Auf der anderen Seite muss lockfreie Programmierung immer speziell zugeschnitten werden auf die zu sch\u00fctzende Datenstruktur, und die Implementierungen sind schwerer verst\u00e4ndlich als die Nutzung eines Spinlocks. Obwohl lockfreie Programmierung schon seit vielen Jahren bekannt ist [1], ist die Verbreitung eher beschr\u00e4nkt. Die Unterst\u00fctzung lockfreier Programmierung in der C++ STL durch Execution Policies wird die Verbreitung sicher erh\u00f6hen. Da C++ auch im Embeeded Bereich zunehmend akzeptiert wird, einschlie\u00dflich eingeschr\u00e4nkter Nutzung der STL, wird lockfreie Programmierung sicher auch dort ihren Platz finden, auch in sicherheitskritischen Systemen mit Anforderungen f\u00fcr harte Echtzeit. Um eine konkrete Implementierung zu \u00fcberpr\u00fcfen, ist hardwareunterst\u00fctzes Tracing auf dem Microcontroller das Mittel der Wahl.<\/p>\n [1] Henry Massalin and Calton Pu. A Lock-Free Multiprocessor OS Kernel. Technical Report CUCS-005-91, Columbia University, 1991.<\/p>\n 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 Multicore \/Mikrocontroller.<\/p>\n Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie\u00a0hier<\/a>.<\/strong><\/p>\n Wertvolles Fachwissen zum Thema Multicore \/Mikrocontroller steht\u00a0hier\u00a0<\/a>f\u00fcr Sie zum kostenfreien Download bereit.<\/p>\nMotivation: Spinlocks und ihre Probleme<\/h2>\n
Blockadefreie Programmierung: Prinzipien, Vor- und Nachteile<\/h2>\n
\n
Beispiel: Eine unbegrenzt Queue<\/h2>\n
\n<\/strong>Anhand des Knotens mit dem Zeiger auf Ende (s. Bild 1,\u00a0PDF<\/a>) wird der letzte wirkliche Knoten ermittelt. Im Enqueue Schritt 1 wird das aktuelle Ende der Queue ermittelt (Knoten B), und der Zeiger next dieses Knotens B wird umgesetzt von NULL auf die Adresse von Knoten A. Knoten A soll ein neuer Knoten in der Queue werden. Die Queue ist jetzt in sich konsistent, damit kann auch der Zeiger next des Knotens Tail auf die Adresse von Knoten A umgesetzt werden.<\/p>\n
\nMit Hilfe des Knotens Head wird der aktuelle erste Knoten ermittelt; am Anfang ist das der W\u00e4chterknoten, auch genannt Sentinel. Der Knoten Sentinel zeigt auf den Knoten D, den eigentlichen letzten Knoten. In Dequeue Schritt 1 wird der eigentliche Wert des Knotens gelesen. In Schritt 2 wird der Zeiger next des Knoten Head umgesetzt auf Knoten D.<\/p>\nFazit<\/h2>\n
Literatur- und Quellenverzeichnis<\/h2>\n
\nMulticore – unsere Trainings & Coachings<\/h2>\n
\nMulticore – Fachwissen<\/h2>\n