Testen und einstellen - Test-and-set

In der Informatik ist der Test-and-Set- Befehl ein Befehl, der verwendet wird, um 1 in einen Speicherplatz zu schreiben (setzen) und seinen alten Wert als einzelne atomare (dh nicht unterbrechbare) Operation zurückzugeben. Der Anrufer kann dann das Ergebnis "testen", um zu sehen, ob der Zustand durch den Anruf geändert wurde. Wenn mehrere Prozesse auf denselben Speicherort zugreifen können und wenn ein Prozess derzeit ein Test-und-Setzen durchführt, kann kein anderer Prozess einen weiteren Test-und-Setzen beginnen, bis das Testen-und-Setzen des ersten Prozesses beendet ist. Eine CPU kann einen Test-and-Set-Befehl verwenden, der von einer anderen elektronischen Komponente angeboten wird, wie beispielsweise einem Dual-Port-RAM ; eine CPU selbst kann auch einen Test-and-Set-Befehl anbieten.

Eine Sperre kann mit einem atomaren Test-and-Set-Befehl wie folgt erstellt werden: 

function Lock(boolean *lock) { 
    while (test_and_set(lock) == 1); 
}

Dieser Code geht davon aus, dass der Speicherplatz irgendwann vor dem ersten Test-and-Set auf 0 initialisiert wurde. Der aufrufende Prozess erhält die Sperre, wenn der alte Wert 0 war, andernfalls dreht sich die while-Schleife und wartet darauf, die Sperre zu erhalten. Dies wird als Spinlock bezeichnet . Zu jedem Zeitpunkt kann der Inhaber des Schlosses einfach den Speicherplatz auf 0 zurücksetzen, um das Schloss zur Übernahme durch einen anderen freizugeben - dies erfordert keine besondere Handhabung, da der Inhaber diesen Speicherplatz "besitzt". " Test and Test-and-set " ist ein weiteres Beispiel.

Maurice Herlihy (1991) bewies, dass Test-and-Set (1-Bit-Vergleich) eine endliche Konsenszahl hat und das Warte-freie Konsensproblem für höchstens zwei gleichzeitige Prozesse lösen kann . Im Gegensatz dazu bietet Compare-and-Swap (32-Bit-Comparand) eine allgemeinere Lösung für dieses Problem, und in einigen Implementierungen ist Compare-Double-and-Swap (64-Bit-Comparand) auch für erweiterte Dienstprogramme verfügbar.

Hardware-Implementierung von Test-and-Set

DPRAM- Test-and-Set-Anweisungen können auf viele Arten funktionieren. Hier sind zwei Variationen, die beide einen DPRAM beschreiben, der genau 2 Ports bereitstellt, wodurch 2 separate elektronische Komponenten (wie 2 CPUs) auf jeden Speicherplatz im DPRAM zugreifen können.

Variante 1

Wenn die CPU 1 einen Test-and-Set-Befehl ausgibt, macht das DPRAM zuerst eine "interne Notiz", indem es die Adresse des Speicherplatzes an einer speziellen Stelle ablegt. Wenn CPU 2 an dieser Stelle zufällig einen Test-and-Set-Befehl für denselben Speicherplatz ausgibt, überprüft das DPRAM zuerst seinen "internen Hinweis", erkennt die Situation und gibt einen BUSY-Interrupt aus, der CPU 2 mitteilt, dass es warten und erneut versuchen. Dies ist eine Implementierung eines Busy Waiting oder Spinlock unter Verwendung des Interrupt-Mechanismus. Da dies alles mit Hardware-Geschwindigkeit geschieht, ist die Wartezeit von CPU 2 sehr kurz, um den Spin-Lock zu verlassen.

Unabhängig davon, ob CPU 2 versucht hat, auf den Speicherplatz zuzugreifen, führt das DPRAM den von CPU 1 gegebenen Test durch. Wenn der Test erfolgreich ist, setzt das DPRAM den Speicherplatz auf den von CPU 1 angegebenen Wert. Dann löscht das DPRAM seine "internen" note", dass CPU 1 dort schrieb. An diesem Punkt könnte die CPU 2 einen Test-and-Set ausgeben, der erfolgreich sein würde.

Variante 2

Die CPU 1 gibt einen Test-und-Set-Befehl aus, um in den "Speicherplatz A" zu schreiben. Der DPRAM speichert den Wert nicht sofort im Speicherplatz A, sondern verschiebt stattdessen gleichzeitig den aktuellen Wert in ein spezielles Register, während er den Inhalt des Speicherplatzes A auf einen speziellen "Flag-Wert" setzt. Wenn an diesem Punkt die CPU 2 einen Test-and-Set an die Speicherstelle A ausgibt, erkennt der DPRAM den speziellen Flag-Wert und gibt wie in Variante 1 eine BUSY-Unterbrechung aus.

Unabhängig davon, ob CPU 2 versucht hat, auf den Speicherplatz zuzugreifen oder nicht, führt das DPRAM jetzt den Test von CPU 1 durch. Wenn der Test erfolgreich ist, setzt das DPRAM den Speicherplatz A auf den von der CPU 1 spezifizierten Wert. Wenn der Test fehlschlägt, kopiert der DPRAM den Wert vom Spezialregister zurück zum Speicherplatz A. Jede Operation löscht den Spezialmerkerwert. Wenn CPU 2 jetzt ein Test-and-Set ausgibt, wird es erfolgreich sein.

Softwareimplementierung von Test-and-Set

Einige Befehlssätze haben einen atomaren Test-and-Set-Maschinensprachbefehl. Beispiele sind x86 und IBM System/360 und seine Nachfolger (einschließlich z/Architecture ). Diejenigen, die dies nicht tun, können immer noch einen atomaren Test-and-Set mit einem Read-Modify-Write- oder Compare-and-Swap- Befehl implementieren .

Die Anweisung test and set verwendet bei Verwendung mit booleschen Werten eine Logik wie die in der folgenden Funktion gezeigte, mit der Ausnahme, dass die Funktion atomar ausgeführt werden muss . Das heißt, kein anderer Prozess darf in der Lage sein, die Funktion mitten in der Ausführung zu unterbrechen und dabei einen Zustand zu sehen, der nur während der Ausführung der Funktion existiert. Das erfordert Hardware-Unterstützung; es kann nicht wie gezeigt implementiert werden. Dennoch hilft der gezeigte Code, das Verhalten von Test-and-Set zu erklären. HINWEIS: In diesem Beispiel wird angenommen, dass 'lock' per Referenz (oder per Name) übergeben wird, aber die Zuweisung zu 'initial' erstellt einen neuen Wert (nicht nur das Kopieren einer Referenz). 

function TestAndSet(boolean_ref lock) {
    boolean initial = lock;
    lock = true;
    return initial;
}

Der gezeigte Code ist nicht nur nicht atomar im Sinne des Test-and-Set-Befehls, er unterscheidet sich auch von den obigen Beschreibungen zu DPRAM-Hardware-Test-and-Set. Hier sind der eingestellte Wert und der Test fest und unveränderlich, und der Wert wird unabhängig vom Ergebnis des Tests aktualisiert, während beim DPRAM-Test-and-Set der Speicher nur gesetzt wird, wenn der Test erfolgreich ist, und der Wert einzustellen und die Testbedingung werden von der CPU vorgegeben. Hier darf der zu setzende Wert nur 1 sein, aber wenn 0 und 1 als die einzigen gültigen Werte für den Speicherplatz betrachtet werden und "Wert ungleich Null" der einzige erlaubte Test ist, dann entspricht dies dem für DPRAM-Hardware beschriebenen Fall ( oder insbesondere reduziert sich der DPRAM-Fall unter diesen Einschränkungen darauf). Aus dieser Sicht kann dies korrekterweise "Test-and-Set" im vollen, herkömmlichen Sinne dieses Begriffs genannt werden. Der wesentliche zu beachtende Punkt ist die allgemeine Absicht und das Prinzip von Test-and-Set: Ein Wert wird in einer atomaren Operation sowohl getestet als auch gesetzt, so dass kein anderer Programmthread oder -prozess den Zielspeicherort ändern kann, nachdem er getestet wurde, aber vorher eingestellt ist. (Das liegt daran, dass der Standort nur dann festgelegt werden muss, wenn er aktuell einen bestimmten Wert hat, nicht wenn er diesen Wert schon einmal hatte.)

In der Programmiersprache C sieht die Implementierung wie folgt aus: 

#define LOCKED 1

int test_and_set(int* lockPtr) {
    int oldValue;

    // -- Start of atomic segment --
    // This should be interpreted as pseudocode for illustrative purposes only.
    // Traditional compilation of this code will not guarantee atomicity, the
    // use of shared memory (i.e., non-cached values), protection from compiler
    // optimizations, or other required properties.
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    // -- End of atomic segment --

    return oldValue;
}

Der Code zeigt auch, dass es wirklich zwei Operationen gibt: ein atomares Lesen-Ändern-Schreiben und einen Test. Nur das Lesen-Ändern-Schreiben muss atomar sein. (Dies ist der Fall, da das Verzögern des Wertvergleichs um einen beliebigen Zeitraum das Ergebnis des Tests nicht ändert, sobald der zu testende Wert erhalten wurde. Sobald der Code den Anfangswert schreibt, ist das Ergebnis des Tests festgelegt, auch wenn es wurde noch nicht berechnet — zB durch den ==-Operator.)

Gegenseitiger Ausschluss durch Test-and-Set

Eine Möglichkeit, den gegenseitigen Ausschluss zu implementieren, besteht darin, eine Test-and-Set-basierte Sperre wie folgt zu verwenden:

Pseudo-C-Implementierung

volatile int lock = 0;

void critical() {
    while (test_and_set(&lock) == 1);
    critical section  // only one process can be in this section at a time
    lock = 0;  // release lock when finished with the critical section
}

Die Lock-Variable ist eine Shared-Variable, dh auf sie kann von allen Prozessoren/Threads zugegriffen werden. Beachten Sie das flüchtige Schlüsselwort. In Abwesenheit von flüchtigen Elementen können der Compiler und/oder die CPU(s) den Zugriff optimieren, um zwischengespeicherte Werte zu sperren und/oder zwischengespeicherte Werte zu verwenden, wodurch der obige Code fehlerhaft wird. Umgekehrt und leider das Vorhandensein von flüchtigen nicht nicht garantieren , dass Lese- und Schreibvorgängen in dem Speicher verpflichtet hat . Einige Compiler erstellen Speicherbarrieren, um sicherzustellen, dass Operationen im Speicher abgelegt werden, aber da die Semantik von volatile in C/C++ ziemlich vage ist, werden dies nicht alle Compiler tun. Lesen Sie in der Dokumentation Ihres Compilers nach, ob dies der Fall ist.

Diese Funktion kann von mehreren Prozessen aufgerufen werden, es wird jedoch garantiert, dass sich jeweils nur ein Prozess im kritischen Abschnitt befindet . Der Rest der Prozesse dreht sich weiter, bis sie die Sperre erhalten. Es ist möglich, dass einem Prozess die Sperre nie erteilt wird. In einem solchen Fall wird es endlos durchlaufen. Dies ist ein Nachteil dieser Implementierung, da sie keine Fairness gewährleistet. Diese Fragen werden im Leistungsteil näher erläutert .

Montagedurchführung

enter_region:        ; A "jump to" tag; function entry point.

  tsl reg, flag      ; Test and Set Lock; flag is the
                     ; shared variable; it is copied
                     ; into the register reg and flag
                     ; then atomically set to 1.

  cmp reg, #0        ; Was flag zero on entry_region?

  jnz enter_region   ; Jump to enter_region if
                     ; reg is non-zero; i.e.,
                     ; flag was non-zero on entry.

  ret                ; Exit; i.e., flag was zero on
                     ; entry. If we get here, tsl
                     ; will have set it non-zero; thus,
                     ; we have claimed the resource
                     ; associated with flag.

leave_region:
  move flag, #0      ; store 0 in flag
  ret                ; return to caller

Hier tslist eine atomare Anweisung und flagdie Lock-Variable. Der Prozess kehrt nicht zurück, es sei denn, er erhält die Sperre.

Leistungsbewertung von Test-and-Set-Schlössern

Die vier wichtigsten Bewertungsmetriken für Sperren im Allgemeinen sind unbestrittene Latenz beim Sperrenerwerb, Busverkehr, Fairness und Speicherung.

Test-and-Set schneidet bei zwei von ihnen schlecht ab, nämlich hoher Busverkehr und Ungerechtigkeit.

Wenn Prozessor P1 eine Sperre erhalten hat und Prozessor P2 ebenfalls auf die Sperre wartet, führt P2 weiterhin Bustransaktionen durch, um die Sperre zu erlangen. Wenn ein Prozessor eine Sperre erhalten hat, versuchen alle anderen Prozessoren, die ebenfalls dieselbe Sperre erhalten möchten, durch wiederholtes Initiieren von Bustransaktionen, die Sperre zu erhalten, bis sie die Sperre erhalten. Dies erhöht den Busverkehrsbedarf von Test-and-Set deutlich. Dies verlangsamt den gesamten anderen Verkehr von Cache- und Kohärenzfehlern . Es verlangsamt den gesamten Abschnitt, da der Verkehr durch fehlgeschlagene Lock-Erfassungsversuche gesättigt ist. Test-and-Test-and-Set ist eine Verbesserung gegenüber TSL, da es nicht kontinuierlich Lock-Acquisition-Anforderungen initiiert.

Wenn wir Fairness berücksichtigen, prüfen wir, ob ein Prozessor eine faire Chance hat, die Sperre zu erhalten, wenn sie freigegeben wird. Im Extremfall kann der Prozessor verhungern, dh er kann die Sperre für längere Zeit nicht erlangen, obwohl sie während dieser Zeit frei geworden ist.

Der Speicheraufwand für TSL ist praktisch gering, da nur eine Sperre erforderlich ist. Die unbestrittene Latenz ist ebenfalls gering, da nur ein atomarer Befehl und eine Verzweigung benötigt werden.

Siehe auch

Verweise

  1. ^ Anderson, TE (1990-01-01). „Die Leistung von Spin-Lock-Alternativen für Multiprozessoren mit geteiltem Geld“. IEEE-Transaktionen auf parallelen und verteilten Systemen . 1 (1): 6–16. doi : 10.1109/71.80120 . ISSN  1045-9219 .
  2. ^ Herlihy, Maurice (Januar 1991). "Wartefreie Synchronisation" (PDF) . ACM-Trans. Programm. Lang. Syst . 13 (1): 124–149. CiteSeerX  10.1.1.56.5659 . doi : 10.1145/114005.102808 . Abgerufen 2007-05-20 .
  3. ^ "BTS – Bittest und Set" . www.felixcloutier.com . Abgerufen 2016-11-21 .
  4. ^ „IBM-Wissenscenter“ . www.ibm.com . Abgerufen 2016-11-21 .
  5. ^ Remzi H. Arpaci-Dusseau und Andrea C. Arpaci-Dusseau (2015). Betriebssysteme: Three Easy Pieces (0.91 ed.). Arpaci-Dusseau-Bücher – über http://www.ostep.org/ .
  6. ^ Solihin, Yan (2009). Grundlagen der parallelen Computerarchitektur: Multichip- und Multicore-Systeme . P. 252. ISBN 9780984163007.
  7. ^ Solihin, Yan (2016). Grundlagen der parallelen Architektur . Boca Raton, FL: CRC-Presse. ISBN 978-1-4822-1118-4.

Externe Links