Rust Atomics und Schlösser

Kapitel 4. Unser eigenes Spin Lock bauen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Das Sperren eines regulären Mutex (siehe "Sperren: Mutexe und RwLocks") versetzt deinen Thread in den Ruhezustand, wenn der Mutex bereits gesperrt ist. So wird vermieden, dass Ressourcen verschwendet werden, während du darauf wartest, dass die Sperre freigegeben wird. Wenn eine Sperre nur kurz gehalten wird und die Threads, die sie sperren, parallel auf verschiedenen Prozessorkernen laufen, kann es für die Threads besser sein, wiederholt zu versuchen, sie zu sperren, ohne tatsächlichin den Ruhezustand zu gehen.

Ein Spin-Lock ist ein Mutex, der genau das tut. Der Versuch, einen bereits gesperrten Mutex zu sperren, führt zu einem Busy-Looping oder Spinning: Er versucht es immer wieder, bis er schließlich erfolgreich ist. Das kann Prozessorzyklen verschwenden, aber manchmal auch zu einer geringeren Latenz beim Sperren führen.

Hinweis

Viele Mutex-Implementierungen, darunter std::sync::Mutexauf einigen Plattformen, verhalten sich kurzzeitig wie ein Spin Lock, bevor sie das Betriebssystem auffordern, einen Thread in den Ruhezustand zu versetzen. Dies ist ein Versuch, das Beste aus beiden Welten zu kombinieren, obwohl es ganz vom jeweiligen Anwendungsfall abhängt, ob dieses Verhalten von Vorteil ist oder nicht.

In diesem Kapitel bauen wir unseren eigenen SpinLock Typ und wenden dabei an, was wir in den Kapiteln 2 und 3 gelernt haben. Wir sehen, wie wir das Typsystem von Rust nutzen können, um dem Benutzer unserer SpinLock eine sichere und nützliche Schnittstelle zu bieten.

Eine minimale Implementierung

Lass uns ein solches Spin Lock von Grund auf neu implementieren.

Die minimalste Version ist ziemlich einfach, wie folgt:

pub struct SpinLock {
    locked: AtomicBool,
}

Alles, was wir brauchen, ist ein einzelner Boolescher Wert, der angibt, ob er gesperrt ist oder nicht. Wir verwenden einen atomaren Booleschen Wert, da wir wollen, dass mehr als ein Thread gleichzeitig mit ihm interagieren kann.

Dann brauchen wir nur noch eine Konstruktorfunktion und die Methoden lock und unlock:

impl SpinLock {
    pub const fn new() -> Self {
        Self { locked: AtomicBool::new(false) }
    }

    pub fn lock(&self) {
        while self.locked.swap(true, Acquire) {
            std::hint::spin_loop();
        }
    }

    pub fn unlock(&self) {
        self.locked.store(false, Release);
    }
}

Der Boolesche Wert locked beginnt bei false, die Methode lock tauscht ihn gegen true aus und versucht es weiter, wenn er bereits true war, und die Methode unlock setzt ihn einfach zurück auf false.

Hinweis

Anstatt eine Tauschoperation zu verwenden, hätten wir auch eine Vergleichs- und Austauschoperation verwenden können, um atomar zu prüfen, ob der boolesche Wert false ist, und ihn in diesem Fall auf true zu setzen:

    while self.locked.compare_exchange_weak(
            false, true, Acquire, Relaxed).is_err()

Sie ist etwas ausführlicher, aber je nach Geschmack ist sie vielleicht einfacher zu verstehen, da sie das Konzept einer Operation, die fehlschlagen oder gelingen kann, deutlicher macht. Sie kann aber auch zu etwas anderen Anweisungen führen, wie wir in Kapitel 7 sehen werden.

In der Schleife while verwenden wir einen Spin-Loop-Hinweis, der dem Prozessor mitteilt, dass wir uns drehen, während wir auf eine Änderung warten. Auf den meisten größeren Plattformen führt dieser Hinweis zu einer speziellen Anweisung, die den Prozessorkern dazu veranlasst, sein Verhalten für eine solche Situation zu optimieren. Er kann zum Beispiel vorübergehend langsamer werden oder anderen nützlichen Dingen, die er tun kann, Vorrang geben. Im Gegensatz zu blockierenden Operationen wie thread::sleep oder thread::park führt ein Spin-Loop-Hinweis jedoch nicht dazu, dass das Betriebssystem aufgerufen wird, um deinen Thread zugunsten eines anderen Threads schlafen zu legen.

Tipp

Im Allgemeinen ist es eine gute Idee, einen solchen Hint in eine Spinschleife einzubauen. Je nach Situation kann es sogar sinnvoll sein, diesen Hint mehrmals auszuführen, bevor du versuchst, erneut auf die atomare Variable zuzugreifen. Wenn du dich für die letzten paar Nanosekunden Leistung interessierst und die optimale Strategie finden willst, musst du einen Benchmark für deinen speziellen Anwendungsfall durchführen. Leider können die Schlussfolgerungen solcher Benchmarks stark von der Hardware abhängen, wie wir in Kapitel 7 sehen werden.

Wir verwenden die Reihenfolge von Speichererwerb und -freigabe, um sicherzustellen, dass jeder Aufruf von unlock() eine "happens-before"-Beziehung zu den folgenden Aufrufen von lock() herstellt. Mit anderen Worten, um sicherzustellen, dass wir nach dem Sperren sicher davon ausgehen können, dass das, was beim letzten Mal passiert ist, bereits geschehen ist. Das ist der klassischste Anwendungsfall für die Reihenfolge von Speichererwerb und -freigabe: das Erwerben und Freigeben einer Sperre.

Abbildung 4-1 veranschaulicht eine Situation, in der unsere SpinLock verwendet wird, um den Zugriff auf einige gemeinsame Daten zu schützen, wobei zwei Threads gleichzeitig versuchen, die Sperre zu erhalten. Beachte, wie die Entsperrungsoperation des ersten Threads mit der Sperroperation des zweiten Threads eine "happens-before"-Beziehung bildet, die sicherstellt, dass die Threads nicht gleichzeitig auf die Daten zugreifen können.

Abbildung 4-1. Die "happens-before"-Beziehungen zwischen zwei Threads, die unser SpinLock verwenden, um den Zugriff auf einige gemeinsame Daten zu schützen

Ein unsicheres Spin Lock

Unser obiger Typ SpinLock hat eine völlig sichere Schnittstelle, da er selbst kein undefiniertes Verhalten verursacht, wenn er missbraucht wird. In den meisten Anwendungsfällen wird er jedoch verwendet, um Änderungen an einer gemeinsam genutzten Variablen zu schützen, was bedeutet, dass der Benutzer immer noch unsicheren, ungeprüften Code verwenden muss.

Um eine einfachere Schnittstelle zu schaffen, können wir die Methode lock so ändern, dass wir einen exklusiven Verweis (&mut T) auf die durch die Sperre geschützten Daten erhalten, denn in den meisten Anwendungsfällen ist es die Sperroperation, die garantiert, dass es sicher ist, exklusiven Zugriff anzunehmen.

Um das zu können, müssen wir den Typ so ändern, dass er generisch für die Art der Daten ist, die er schützt, und ein Feld hinzufügen, das diese Daten enthält. Da diese Daten verändert werden können (oder ausschließlich darauf zugegriffen werden kann), obwohl der Spin Lock selbst gemeinsam genutzt wird, müssen wir die interne Veränderbarkeit nutzen (siehe "Interne Veränderbarkeit"), wofür wir ein UnsafeCell verwenden:

use std::cell::UnsafeCell;

pub struct SpinLock<T> {
    locked: AtomicBool,
    value: UnsafeCell<T>,
}

Vorsichtshalber implementiert UnsafeCell nicht Sync, was bedeutet, dass unser Typ jetzt nicht mehr zwischen Threads ausgetauscht werden kann, was ihn ziemlich nutzlos macht. Um das zu beheben, müssen wir dem Compiler versprechen, dass es tatsächlich sicher ist, dass unser Typ zwischen Threads ausgetauscht werden kann. Da die Sperre jedoch verwendet werden kann, um Werte des Typs T von einem Thread zu einem anderen zu senden, müssen wir dieses Versprechen auf Typen beschränken, die sicher zwischen Threads gesendet werden können. Wir implementieren also (unsicher) Sync für SpinLock<T> für alle T, die Send implementieren, wie folgt:

unsafe impl<T> Sync for SpinLock<T> where T: Send {}

Beachte, dass wir nicht verlangen müssen, dass T Sync ist, weil unser SpinLock<T> nur einem Thread gleichzeitig den Zugriff auf das T erlaubt, das es schützt. Nur wenn wir mehreren Threads gleichzeitig Zugriff gewähren wollen, wie es eine Leser-Schreiber-Sperre für Leser tut, müssten wir (zusätzlich) T: Sync verlangen.

Als Nächstes muss unsere Funktion new einen Wert vom Typ T annehmen, um UnsafeCell zu initialisieren:

impl<T> SpinLock<T> {
    pub const fn new(value: T) -> Self {
        Self {
            locked: AtomicBool::new(false),
            value: UnsafeCell::new(value),
        }
    }

    …
}

Und dann kommen wir zum interessanten Teil: lock und unlock. Der Grund, warum wir all das tun, ist, dass wir in der Lage sind, ein &mut T von lock() zurückzugeben, damit der Benutzer keinen unsicheren, ungeprüften Code schreiben muss, wenn er unsere Sperre zum Schutz seiner Daten verwendet. Das bedeutet, dass wir jetzt unsicheren Code auf unserer Seite in der Implementierung von lock verwenden müssen. UnsafeCell kann uns über seine get() Methode einen Zeiger auf seinen Inhalt (*mut T) geben, den wir in einem unsafe Block wie folgt in eine Referenz umwandeln können:

    pub fn lock(&self) -> &mut T {
        while self.locked.swap(true, Acquire) {
            std::hint::spin_loop();
        }
        unsafe { &mut *self.value.get() }
    }

Da die Funktionssignatur von lock sowohl in der Eingabe als auch in der Ausgabe einen Verweis enthält, wurden die Lebenszeiten von &self und &mut T ausgelassen und als identisch angenommen (siehe "Elision von Lebenszeiten" in "Kapitel 10: Generische Typen, Traits und Lebenszeiten" im Rust-Buch):

    pub fn lock<'a>(&'a self) -> &'a mut T { … }

Dies zeigt deutlich, dass die Lebensdauer der zurückgegebenen Referenz die gleiche ist wie die von &self. Das bedeutet, dass wir behauptet haben, dass die zurückgegebene Referenz so lange gültig ist, wie die Sperre selbst existiert.

Wenn wir so tun, als gäbe es unlock() nicht, wäre dies eine absolut sichere und solide Schnittstelle. Eine SpinLock kann gesperrt werden, was zu einer &mut T führt, und kann dann nie wieder gesperrt werden, was garantiert, dass diese exklusive Referenz tatsächlich exklusiv ist.

Wenn wir versuchen, die Methode unlock() wieder einzufügen, brauchen wir jedoch eine Möglichkeit, die Lebensdauer der zurückgegebenen Referenz bis zum nächsten Aufruf von unlock() zu begrenzen. Wenn der Compiler Englisch versteht, würde das vielleicht funktionieren:

    pub fn lock<'a>(&self) -> &'a mut T
    where
        'a ends at the next call to unlock() on self,
        even if that's done by another thread.
        Oh, and it also ends when self is dropped, of course.
        (Thanks!)
    { … }

Leider ist das kein gültiges Rust. Anstatt zu versuchen, diese Einschränkung dem Compiler zu erklären, müssen wir sie dem Benutzer erklären. Um die Verantwortung auf den Benutzer zu übertragen, markieren wir die Funktion unlock als unsafe und hinterlassen eine Notiz, in der wir erklären, was sie tun müssen, damit alles in Ordnung ist:

    /// Safety: The &mut T from lock() must be gone!
    /// (And no cheating by keeping reference to fields of that T around!)
    pub unsafe fn unlock(&self) {
        self.locked.store(false, Release);
    }

Eine sichere Schnittstelle mit einem Lock Guard

Um eine vollständig sichere Schnittstelle anbieten zu können, müssen wir die Entsperrung an das Ende von &mut T binden. Das können wir erreichen, indem wir diese Referenz in unseren eigenen Typ einwickeln, der sich wie eine Referenz verhält, aber auch die Eigenschaft Drop implementiert, um etwas zu tun, wenn sie fallen gelassen wird.

Ein solcher Typ wird oft als Wächter bezeichnet, da er den Zustand des Schlosses effektiv bewacht und für diesen Zustand verantwortlich bleibt, bis er fallen gelassen wird.

Unser Typ Guard wird einfach einen Verweis auf SpinLock enthalten, so dass er sowohl auf sein UnsafeCell zugreifen als auch später das AtomicBool zurücksetzen kann:

pub struct Guard<T> {
    lock: &SpinLock<T>,
}

Wenn wir versuchen, dies zu kompilieren, meldet uns der Compiler jedoch:

error[E0106]: missing lifetime specifier
   --> src/lib.rs
    |
    |         lock: &SpinLock<T>,
    |               ^ expected named lifetime parameter
    |
help: consider introducing a named lifetime parameter
    |
    ~     pub struct Guard<'a, T> {
    |                      ^^^
    ~         lock: &'a SpinLock<T>,
    |                ^^
    |

Offensichtlich ist dies kein Ort, an dem Lebenszeiten ausgelassen werden können. Wir müssen explizit darauf hinweisen, dass die Referenz eine begrenzte Lebensdauer hat, genau wie es der Compiler vorschlägt:

pub struct Guard<'a, T> {
    lock: &'a SpinLock<T>,
}

Das garantiert, dass die Guard die SpinLock nicht überleben kann.

Als Nächstes ändern wir die Methode lock auf unserer SpinLock, um eine Guard zurückzugeben:

    pub fn lock(&self) -> Guard<T> {
        while self.locked.swap(true, Acquire) {
            std::hint::spin_loop();
        }
        Guard { lock: self }
    }

Unser Typ Guard hat keinen Konstruktor und sein Feld ist privat, also ist dies die einzige Möglichkeit für den Benutzer, eine Guard zu erhalten. Daher können wir sicher davon ausgehen, dass die Existenz einer Guard bedeutet, dass die SpinLock gesperrt wurde.

Damit sich Guard<T> wie ein (exklusiver) Verweis verhält, der transparent den Zugriff auf T ermöglicht, müssen wir die speziellen Eigenschaften Deref und DerefMut wie folgt implementieren:

use std::ops::{Deref, DerefMut};

impl<T> Deref for Guard<'_, T> {
    type Target = T;
    fn deref(&self) -> &T {
        // Safety: The very existence of this Guard
        // guarantees we've exclusively locked the lock.
        unsafe { &*self.lock.value.get() }
    }
}

impl<T> DerefMut for Guard<'_, T> {
    fn deref_mut(&mut self) -> &mut T {
        // Safety: The very existence of this Guard
        // guarantees we've exclusively locked the lock.
        unsafe { &mut *self.lock.value.get() }
    }
}

Im letzten Schritt implementieren wir Drop für Guard, wodurch wir die unsichere Methode unlock vollständig entfernen können:

impl<T> Drop for Guard<'_, T> {
    fn drop(&mut self) {
        self.lock.locked.store(false, Release);
    }
}

Und einfach so, durch die Magie von Drop und dem Typsystem von Rust, haben wir unserem SpinLock Typ eine sichere (und nützliche) Schnittstelle gegeben.

Lass es uns ausprobieren:

fn main() {
    let x = SpinLock::new(Vec::new());
    thread::scope(|s| {
        s.spawn(|| x.lock().push(1));
        s.spawn(|| {
            let mut g = x.lock();
            g.push(2);
            g.push(2);
        });
    });
    let g = x.lock();
    assert!(g.as_slice() == [1, 2, 2] || g.as_slice() == [2, 2, 1]);
}

Das obige Programm zeigt, wie einfach unser SpinLock zu bedienen ist. Dank Deref und DerefMut können wir die Methode Vec::push direkt auf der Wache aufrufen. Und dank Drop müssen wir uns keine Gedanken über die Entsperrung machen.

Es ist auch möglich, die Sperre explizit aufzuheben, indem du drop(g) aufrufst, um die Sperre aufzuheben. Wenn du versuchst, die Sperre zu früh aufzuheben, wird die Sperre durch einen Compilerfehler aufgehoben. Wenn du zum Beispiel drop(g); zwischen den beiden Zeilen push(2) einfügst, wird die zweite push nicht kompiliert, da du an dieser Stelle bereits g aufgehoben hast:

error[E0382]: borrow of moved value: `g`
   --> src/lib.rs
    |
    |     drop(g);
    |          - value moved here
    |     g.push(2);
    |     ^^^^^^^^^ value borrowed here after move

Dank des Typensystems von Rust können wir sicher sein, dass Fehler wie dieser erkannt werden, bevor wir unser Programm überhaupt ausführen können.

Zusammenfassung

• Ein Spin Lock ist eine Mutex, die während des Wartens in einer Schleife läuft oder spinnt.

• Spinning kann die Latenzzeit verringern, aber es kann auch eine Verschwendung von Taktzyklen sein und die Leistung verringern.

• Ein Spinschleifen-Hinweis, std::hint::spin_loop(), kann verwendet werden, um den Prozessor über eine Spinschleife zu informieren, was seine Effizienz erhöhen könnte.

• Eine SpinLock<T> kann nur mit einem AtomicBool und einem UnsafeCell<T> implementiert werden, wobei letzteres für die innere Veränderbarkeit notwendig ist (siehe "Innere Veränderbarkeit").

• Eine "happens-before"-Beziehung zwischen Unlock- und Lock-Operationen ist notwendig, um ein Data Race zu verhindern, das zu undefiniertem Verhalten führen würde.

• Acquire- und Release-Memory-Bestellungen sind perfekt für diesen Anwendungsfall geeignet.

• Wenn ungeprüfte Annahmen notwendig sind, um undefiniertes Verhalten zu vermeiden, kann die Verantwortung auf den Aufrufer verlagert werden, indem die Funktion unsafe gemacht wird.

• Die Eigenschaften Deref und DerefMut können verwendet werden, damit sich ein Typ wie eine Referenz verhält und transparent den Zugriff auf ein anderes Objekt ermöglicht.

• Die Drop Eigenschaft kann verwendet werden, um etwas zu tun, wenn ein Objekt fallen gelassen wird, z.B. wenn es aus dem Geltungsbereich geht oder wenn es an drop() übergeben wird.

• Ein Lock Guard ist ein nützliches Entwurfsmuster für einen speziellen Typ, der den (sicheren) Zugriff auf eine gesperrte Sperre repräsentiert. Ein solcher Typ verhält sich dank des Deref Traits in der Regel ähnlich wie eine Referenz und implementiert die automatische Entsperrung durch den Drop Trait.