Ticketschloss - Ticket lock

In der Informatik , eine Ticketsperre ist ein Synchronisationsmechanismus oder Algorithmus Verriegelungs , dass eine Art ist spinlock dass uses „Tickets“ zu steuern , die Gewinde der Ausführung erlaubt ist , eine Eingabe kritischen Abschnitt .

Überblick

Beispiel für ein Ticket und ein "Now Serving" -Zeichen, die im Ticket Queue Management System verwendet werden.

Das Grundkonzept einer Ticketsperre ähnelt dem Ticketwarteschlangenverwaltungssystem. Dies ist die Methode, mit der viele Bäckereien und Feinkostläden Kunden in der Reihenfolge ihres Eintreffens bedienen, ohne sie in einer Reihe stehen zu lassen. Im Allgemeinen gibt es eine Art Spender, aus dem Kunden bei der Ankunft fortlaufend nummerierte Tickets ziehen. Der Spender hat normalerweise ein Schild darüber oder in der Nähe, auf dem etwa "Bitte nehmen Sie eine Nummer" steht. Es gibt normalerweise auch ein dynamisches Zeichen, normalerweise digital, das die Ticketnummer anzeigt, die jetzt zugestellt wird. Jedes Mal, wenn die nächste Ticketnummer (Kunde) zur Zustellung bereit ist, wird das Zeichen "Now Serving" erhöht und die Nummer aufgerufen. Auf diese Weise können alle wartenden Kunden wissen, wie viele Personen sich noch in der Warteschlange oder Warteschlange vor ihnen befinden.

Wie dieses System ist eine Ticketsperre ein Warteschlangen-basierter Mechanismus (FIFO) . Es bietet den Vorteil der Fairness beim Erwerb von Schlössern und funktioniert wie folgt: Es gibt zwei ganzzahlige Werte, die bei 0 beginnen. Der erste Wert ist das Warteschlangenticket, der zweite ist das Warteschlangenticket. Das Warteschlangenticket ist die Position des Threads in der Warteschlange, und das Warteschlangenticket ist das Ticket oder die Warteschlangenposition, die jetzt die Sperre hat (Now Serving).

Wenn ein Thread ankommt, erhält er das Warteschlangenticket atomar und erhöht es dann. Die Atomizität dieser Operation ist erforderlich, um zu verhindern, dass zwei Threads gleichzeitig dieselbe Ticketnummer erhalten können. Anschließend wird der Ticketwert vor dem Inkrement mit dem Wert des Warteschlangentickets verglichen. Wenn sie gleich sind, darf der Thread den kritischen Abschnitt betreten. Wenn sie nicht identisch sind, muss sich bereits ein anderer Thread im kritischen Bereich befinden und dieser Thread muss beschäftigt warten oder nachgeben. Wenn ein Thread den von der Sperre gesteuerten kritischen Abschnitt verlässt, erhöht er das Dequeue-Ticket atomar. Dadurch kann der nächste wartende Thread, der mit der nächsten fortlaufenden Ticketnummer, den kritischen Abschnitt betreten.

Fairness beim Erwerb von Schlössern

Der Begriff der Fairness beim Erwerb von Sperren gilt für die Reihenfolge, in der Threads eine Sperre erfolgreich erwerben. Wenn irgendeine Art von Fairness implementiert ist, verhindert , dass es einen Faden davor ausgehungert für eine lange Zeit von der Ausführung wegen Unfähigkeit , eine Sperre für andere Threads zu erfassen. Ohne Fairness-Garantien kann es vorkommen, dass die Ausführung eines Threads (oder mehrerer Threads) im Vergleich zu anderen Threads unverhältnismäßig lange dauert. Es wird nun ein einfaches Beispiel vorgestellt, um zu zeigen, wie ein Thread aufgrund mangelnder Fairness bei der Sperrenerfassung übermäßig verzögert werden kann.

Angenommen, drei Threads, die jeweils auf einem von drei Prozessoren ausgeführt werden, führen den folgenden Pseudocode aus, der eine Sperre ohne Berücksichtigung der Fairness verwendet.

while (1) {
    lock {
        …
        critical section
        …
    }
    unlock
}

Nehmen wir nun weiter an, dass die physikalische Anordnung der drei Prozessoren P1, P2 und P3 zu einer ungleichmäßigen Speicherzugriffszeit auf den Ort der gemeinsam genutzten Sperrvariablen führt. Die Reihenfolge der Erhöhung der Zugriffszeit auf die Sperrvariable für die drei Prozessoren ist P1 <P2 <P3. Daher ist P1 beim Erwerb der Sperre immer am vorteilhaftesten, gefolgt von P2, wobei P3 am stärksten benachteiligt ist. Wie diese Situation ohne Fairness-Garantie zu einem Thread-Hunger führt, zeigt die folgende Abbildung der Ausführung des obigen Pseudocodes durch diese drei Prozessoren.

Zu Beginn ist die Sperre frei und alle drei Prozessoren versuchen gleichzeitig, die Sperre zu erlangen (Zeitpunkt 1). Da P1 die schnellste Zugriffszeit auf das Schloss hat, wird es zuerst erfasst und betritt den kritischen Bereich. P2 und P3 drehen sich jetzt, während sich P1 im kritischen Bereich befindet (Zeitpunkt 2). Beim Verlassen des kritischen Abschnitts (Zeitpunkt 3) führt P1 eine Entsperrung durch und gibt die Sperre frei. Da P2 schneller auf die Sperre zugreifen kann als P3, erhält es als nächstes die Sperre und betritt den kritischen Bereich (Zeitpunkt 4). Während sich P2 im kritischen Bereich befindet, versucht P1 erneut, die Sperre zu erlangen, kann dies jedoch nicht (Zeit 5), wodurch er gezwungen wird, zusammen mit P3 zu warten. Sobald P2 den kritischen Abschnitt beendet und eine Freischaltung durchgeführt hat, versuchen sowohl P1 als auch P3 gleichzeitig, ihn erneut zu erfassen (Zeitpunkt 6). Aber P1 mit seiner schnelleren Zugriffszeit gewinnt erneut und betritt damit den kritischen Abschnitt (Zeit 7). Dieses Muster, dass P3 die Sperre nicht erhalten kann, wird auf unbestimmte Zeit fortgesetzt, bis entweder P1 oder P2 aufhören, zu versuchen, sie zu erfassen.

Dies zeigt die Notwendigkeit, unter bestimmten Umständen ein gewisses Maß an Fairness beim Erwerb von Schlössern sicherzustellen. Nicht alle Schlösser verfügen über Mechanismen, die ein gewisses Maß an Fairness gewährleisten und das Potenzial für ähnliche Situationen wie oben dargestellt lassen. Im Abschnitt Vergleich von Sperren unten finden Sie Beispiele für Sperren, für die keine Fairness-Garantien implementiert sind.

Implementierung der Ticketsperre

In einem NUMA- System (Non-Uniform Memory Architecture) ist eine Sperrenimplementierung wichtig, die ein gewisses Maß an Fairness bei der Sperrenerfassung garantiert . Die Ticketsperre ist eine Implementierung von Spinlock , die dieses gewünschte Attribut hinzufügt. Der folgende Pseudocode zeigt die Vorgänge zum Initialisieren der Sperre, zum Erfassen der Sperre und zum Aufheben der Sperre. Ein Aufruf von ticketLock_acquire würde dem kritischen Abschnitt des Codes vorausgehen und ticketLock_release würde ihm folgen. Jeder Prozessor verfolgt seinen Zug über den Wert des my_tickets jedes Prozessors.

Das Pseudocode-Beispiel von Yan Solihin ist in der folgenden Abbildung aufgeführt.

 1 ticketLock_init(int *next_ticket, int *now_serving)
 2 {
 3     *now_serving = *next_ticket = 0;
 4 }
 5 
 6 ticketLock_acquire(int *next_ticket, int *now_serving)
 7 {
 8     my_ticket = fetch_and_inc(next_ticket);
 9     while (*now_serving != my_ticket) {}
10 }
11 
12 ticketLock_release(int *now_serving)
13 {
14     ++*now_serving;
15 }

Zusammen mit dem obigen Pseudocode können wir sehen, dass jedes Mal, wenn ein Prozessor versucht, eine Sperre mit zu erhalten ticketLock_acquire(), fetch_and_inc aufgerufen wird, wobei der aktuelle Wert von next_ticket in den Thread private my_ticket zurückgegeben und das gemeinsam genutzte next_ticket erhöht wird. Es ist wichtig zu beachten, dass das Abrufen und Inkrementieren atomar erfolgt, wodurch keine anderen gleichzeitigen Zugriffsversuche zugelassen werden. Sobald my_ticket empfangen wurde, dreht sich jeder Thread in der while-Schleife, während now_serving nicht gleich my_ticket ist. Sobald now_serving dem my_ticket eines bestimmten Threads entspricht, können sie von ticketLock_acquire () zurückkehren und den kritischen Codeabschnitt eingeben. Nach dem kritischen Abschnitt des Codes führt der Thread ticketLock_release () aus, wodurch now_serving erhöht wird. Dadurch kann der Thread mit dem nächsten sequentiellen my_ticket aus ticketLock_acquire () austreten und den kritischen Abschnitt betreten. Da die my_ticket-Werte in der Reihenfolge des Eintreffens des Threads an der Sperre erfasst werden, wird garantiert, dass die nachfolgende Erfassung der Sperre ebenfalls in derselben Reihenfolge erfolgt. Somit ist die Fairness des Schlosserwerbs gewährleistet, wodurch eine FIFO-Bestellung erzwungen wird.

Die folgende Tabelle zeigt ein Beispiel für die Ticket-Sperre in Aktion in einem System mit vier Prozessoren (P1, P2, P3, P4), die um den Zugriff auf den kritischen Abschnitt konkurrieren. Zusammen mit der Spalte "Aktion" kann das Ergebnis basierend auf dem obigen Pseudocode beobachtet werden. Für jede Zeile werden die Variablenwerte angezeigt, die nach Abschluss der angegebenen Aktion (en) angezeigt wurden. Der wichtigste Punkt aus dem Beispiel ist, dass die ersten Versuche aller vier Prozessoren, die Sperre zu erhalten, dazu führen, dass nur der erste ankommt, der tatsächlich die Sperre erhält. Alle nachfolgenden Versuche, während der erste noch die Sperre hält, dienen dazu, die Warteschlange der Prozessoren zu bilden, die darauf warten, im kritischen Abschnitt an die Reihe zu kommen. Anschließend erhält jeder das Schloss nacheinander, sodass der nächste in der Reihe es erwerben kann, wenn der vorherige Inhaber das Schloss verlässt. Beachten Sie auch, dass ein anderer Prozessor jederzeit während der Sequenz der Sperrenerfassung / -freigabe durch andere Prozessoren eintreffen kann und einfach wartet, bis er an der Reihe ist.

Der erste Schritt vor der Verwendung der Sperre ist die Initialisierung aller Sperrvariablen (Zeile 1). Wenn next_ticket und now_serving auf 0 initialisiert werden, wird sichergestellt, dass der erste Thread, der versucht, die Sperre zu erhalten, Ticket 0 erhält und somit die Sperre erhält, da das Ticket mit now_serving übereinstimmt. Wenn P1 versucht, die Sperre zu erlangen, ist dies sofort erfolgreich und next_ticket wird auf 1 erhöht (Zeile 2). Wenn P3 versucht, die Sperre zu erlangen, erhält es 1 für sein my_ticket, das nächste Ticket wird auf 2 erhöht und muss warten, da now_serving immer noch 0 ist (Zeile 3). Wenn P2 versucht, die Sperre zu erlangen, erhält es 2 für sein my_ticket, next_ticket wird auf 3 erhöht und muss auch warten, da now_serving immer noch 0 ist (Zeile 4). P1 gibt nun die Sperre frei, indem now_serving auf 1 erhöht wird, sodass P3 sie aufgrund ihres my_ticket-Werts von 1 (Zeile 5) abrufen kann. Jetzt gibt P3 die Sperre frei und erhöht now_serving auf 2, sodass P2 sie abrufen kann (Zeile 6). Während P2 die Sperre hat, versucht P4, sie zu erfassen, erhält einen my_ticket-Wert von 3, erhöht next_ticket auf 4 und muss warten, da now_serving immer noch 2 ist (Zeile 7). Wenn P2 die Sperre aufhebt, wird now_serving auf 3 erhöht, sodass P4 sie abrufen kann (Zeile 8). Schließlich gibt P4 die Sperre frei und erhöht now_serving auf 4 (Zeile 9). Derzeit haben keine wartenden Threads diese Ticketnummer, sodass der nächste ankommende Thread 4 für sein Ticket erhält und sofort die Sperre erhält.

Vergleich von Schlössern

Die Linux-Kernel- Implementierung kann eine geringere Latenz aufweisen als die einfacheren Test-and-Set- oder Exchange- basierten Spinlock-Algorithmen auf modernen Maschinen. Beachten Sie die folgende Tabelle, wenn Sie verschiedene Arten von spinbasierten Sperren vergleichen. Die grundlegenderen Verriegelungsmechanismen haben eine geringere Latenzzeit als die erweiterten Verriegelungsmechanismen.

Vorteile

• Ein Vorteil einer Ticketsperre gegenüber anderen Spinlock-Algorithmen besteht darin, dass sie fair ist. Die wartenden Threads werden in einer First-In-First-Out- Basis verarbeitet, wenn die Ganzzahl des Dequeue-Tickets zunimmt, wodurch ein Verhungern verhindert wird .
• Ein Ticket-Lock-Algorithmus verhindert auch das Auftreten des Problems der donnernden Herde , da jeweils nur ein Thread versucht, in den kritischen Bereich einzutreten.
• Die Speicherung ist nicht unbedingt ein Problem, da sich alle Threads auf einer Variablen drehen, im Gegensatz zu Array-basierten Warteschlangensperren (ABQL), bei denen sich Threads auf einzelnen Elementen eines Arrays drehen.

Nachteile

• Ein Nachteil besteht darin, dass aufgrund der zusätzlichen Anweisungen, die zum Lesen und Testen des Werts erforderlich sind, auf dem sich alle Threads drehen, bevor eine Sperre aufgehoben wird, eine höhere Latenzzeit besteht.
• Ein weiterer großer Nachteil einer Ticketsperre besteht darin, dass sie nicht skalierbar ist. Untersuchungen haben ergeben, dass die Leistung exponentiell abnimmt, wenn Prozessoren zu einem Ticket Lock-System hinzugefügt werden.
• Ein weiteres Problem ergibt sich aus der Freigabe eines Schlosses. Alle Threads drehen sich um eine Variable. Wenn die Sperre aufgehoben wird, gibt es Ө (p) Ungültigmachungen (sowie Ө (p) Erfassungen). Dies liegt daran, dass alle Threads ihren Block erneut in den Cache laden und einen Test durchführen müssen, um festzustellen, ob sie zum kritischen Abschnitt zugelassen sind.

Geschichte

Die Ticketsperre wurde 1991 von Mellor-Crummey und Scott eingeführt. Dieser Algorithmus wurde 2008 aufgrund seiner Vorteile in den Linux-Kernel eingeführt , in paravirtualisierten Umgebungen mit Nachteilen jedoch weggelassen . Ab Juli 2010 wird daran gearbeitet, die Verwendung von Ticketschlössern bei der Paravirtualisierung zu ermöglichen. Seit März 2015 wird diese Art von Sperrschema von Red Hat Enterprise Linux in ihrem System wieder eingesetzt.

Verwandte Arbeiten

• Der Backalgorithmus von Lamport verwendet ein ähnliches Konzept eines "Tickets" oder "Zählers", verwendet jedoch keine atomaren Hardwareoperationen. Es wurde eher für Fehlertoleranz als für Leistung entwickelt. Anstatt dass alle Prozessoren den Freigabeschalter ständig überprüfen, dreht sich das Bäckereischloss, um die Tickets seiner Kollegen zu überprüfen.
• Warteschlangenbasierte Drehsperren garantieren Fairness, indem sie eine Warteschlange von Kellnern unterhalten und die Sperre dem ersten Kellner während eines Entsperrvorgangs gewähren.

Siehe auch

• Fetch-and-Add , eine weitere atomare Anweisung, die anstelle von Fetch-and-Inkrement zum Implementieren einer Ticketsperre verwendet werden kann

Verweise