Inhalt
Spinlocks stellen eine der einfachsten Formen von gegenseitigen Ausschlussmechanismen dar, die in Mehrprozessorsystem-Betriebssystemen verwendet werden. Ihre Hauptaufgabe besteht darin, den gleichzeitigen Zugriff mehrerer Kerne auf kritische Abschnitte zu verhindern und so Datenkonsistenz und Integrität zu gewährleisten. Im Allgemeinen schützen Spinlocks vor einer Unterbrechung auf der aktuellen CPU – oft durch Deaktivieren von Interrupts – und verhindern gleichzeitig, dass andere Kerne auf den geschützten Codebereich zugreifen, indem sie atomare Speicheroperationen nutzen. Das definierende Merkmal eines Spinlocks ist, dass ein Thread, der versucht, einen bereits von einem anderen gehaltenen Lock zu erwerben, aktiv wartet oder "spinnt" und kontinuierlich prüft, bis der Lock verfügbar wird. Dieses Verhalten führt zu CPU-Zeitverbrauch während der Wartezeiten, weshalb Spinlocks nur für minimale Zeiträume gehalten werden sollten und idealerweise nicht unterbrochen werden dürfen, solange sie besessen werden.\n\nHistorisch basierten frühe Spinlock-Implementierungen rein auf Standard-Speicheroperationen wie Laden und Speichern. Klassische Algorithmen wie die von Eisenberg & McGuire oder der Lamport Bakery zeigten diesen Ansatz. Mit dem Aufkommen moderner Mehrkernprozessoren, insbesondere solcher mit schwachen Speichermodellen wie x86- und x86-64-Architekturen, versagen diese naiven Implementierungen jedoch oft darin, Korrektheit zu garantieren. Obwohl Speicherbarrieren diese Probleme beheben können, verringern sie die Effizienz. Folglich verlassen sich moderne Spinlocks auf leistungsfähigere atomare Speicheroperationen, die von der Hardware bereitgestellt werden, wie Test-and-Set, Compare-and-Swap und Load-Linked/Store-Conditional-Instruktionen. Diese Operationen gewährleisten Atomizität und korrekte Synchronisation, die für die korrekte Funktion des Spinlocks entscheidend sind.\n\nEin einfacher Spinlock im Benutzermodus kann in C unter Verwendung der atomaren Intrinsics von GCC implementiert werden. Der Lock-Zustand wird durch eine Ganzzahl dargestellt, wobei Null anzeigt, dass der Lock frei ist, und Eins, dass er gehalten wird. Erwerbsversuche beinhalten eine atomare Compare-and-Swap-Operation, die den Lock atomar von frei auf gehalten umschaltet. Dieser Ansatz, gekennzeichnet durch die Verwendung der stärksten Speicherordnungssemantik (__ATOMIC_SEQ_CST), gewährleistet sequentielle Konsistenz über Kerne hinweg, wenn auch mit potenziellen Ineffizienzen. Ein Nachteil dieses einfachen Designs ist die Möglichkeit von Unfairness bei Konkurrenz; das Speichersubsystem bestimmt zufällig, welcher Kern den Lock als nächstes erhält, was manchmal zu ungleichen Zugriffsfrequenzen über die Kerne führt.\n\nUm Fairnessprobleme zu adressieren, verwenden Spinlock-Designs manchmal einen Ticketmechanismus, der eine First-In-First-Out-(FIFO)-Reihenfolge erzwingt. Ticket-Spinlocks vergeben eine inkrementierende Ticketnummer an jeden Anforderer und gewähren den Zugriff in aufsteigender Ticketreihenfolge. Dieser Ansatz garantiert Fairness, da jeder Thread seine Reihenfolge abwartet, ähnlich dem Lamport Bakery-Algorithmus. Implementierungstechnisch verwaltet der Ticket-Lock zwei Zähler – Front und Back – die das aktuell bediente Ticket und das nächste zu vergebende Ticket repräsentieren. Wenn das Ticket eines Threads mit dem Front-Zähler übereinstimmt, erhält er Zugriff auf den kritischen Abschnitt. Diese Methode hat sich selbst auf großen Mehrkernsystemen als sehr fair erwiesen.\n\nLinux-Kernel verwenden oft komplexere, warteschlangenbasierte Spinlocks, die komplex sind und sich über mehrere Quellcodedateien erstrecken. Fokussiert man jedoch auf 32-Bit-ARM-Plattformen, nutzt die Spinlock-Implementierung die Load-Linked/Store-Conditional-(ldrex/strex)-Instruktionen des Prozessors, um atomare Inkremente durchzuführen und eine korrekte Synchronisation sicherzustellen. Die Datenstruktur, die den Lock repräsentiert, kann entweder als 32-Bit-Ganzzahl oder als zwei 16-Bit-Felder betrachtet werden, die wie die Front- und Back-Zähler im Ticket-Lock funktionieren. Die Verwendung von prefetchw (das zum pldw-Befehl kompiliert) bereitet die Cache-Linie zum Schreiben vor und optimiert nachfolgende Lock-Operationen.\n\nDer ARM-Spinlock-Erwerbscode verwendet einen Inline-Assembly-Block, der das Verhalten des Ticket-Locks eng nachahmt. Die ldrex-Instruktion lädt den Wert des Locks und markiert die Speicherstelle für exklusiven Zugriff. Der Code inkrementiert die oberen 16 Bits des Lock-Werts, um eine neue Ticketnummer zu erzeugen. Anschließend versucht strex, diesen Wert bedingt zu speichern, was nur gelingt, wenn kein anderer Prozessor den Speicher verändert hat. Scheitert der Speicherzugriff, wird der Vorgang wiederholt, wodurch Atomizität durch optimistische Nebenläufigkeitskontrolle gewährleistet wird. Dieser Mechanismus ermöglicht eine effiziente, niedrigstufige Synchronisation, die auf die Besonderheiten der ARM-Architektur zugeschnitten ist.
