Zum Inhalt
wannacode

Atomare Operationen und unveränderliche Objekte

Kurz gesagt: Eine atomare Operation läuft in einem Stück, ohne dass ein anderer Thread dazwischenfunkt; Python hat keine atomare Ganzzahl und kein Compare-and-set, also schützt du Daten mit einem Lock, und ein unveränderliches Objekt ändert sich nie.

Problem

Ein Lock für ein einziges +1

Ein Flash-Sale: 100 Kopfhörer zum halben Preis, um 10:00. Die Produktseite wird tausende Male pro Sekunde geöffnet, und jedes Öffnen erhöht den Seitenaufruf-Zähler. Aus der Lektion über Sperren weißt du, wie man keine Erhöhungen verliert: ein Lock um views++.

Das ist richtig. Aber jeder Thread stellt sich für ein einziges +1 vor dem Lock an. Ein Thread, der das Lock nicht bekommt, wird oft schlafen gelegt und später vom Betriebssystem geweckt. Das kostet viel mehr als die Addition selbst.

Das zweite Problem ist schlimmer. Das letzte Stück wird mit „wenn eins da ist, um 1 verringern“ gekauft. Das sind zwei Schritte, und dazwischen kann ein anderer Thread dasselbe Stück nehmen.

Die Idee

Ein unteilbarer Schritt

Der Prozessor hat Befehle, die eine Speicherzelle in einem unteilbaren Schritt lesen, ändern und schreiben. Kein anderer Thread kann dazwischenkommen. Das ist eine atomare Operation. Es gibt kein Lock, niemand steht an und niemand schläft.

Python hat keine atomare Ganzzahl. views += 1 besteht für den Interpreter aus mehreren Schritten, mit dem GIL und ohne. Python hat also drei ehrliche Wege:

  • ein Lock um die Erhöhung, wie in der Lektion über Sperren;
  • eine Warteschlange, in die die Threads die Ereignisse schicken, während ein Thread zählt (in den späteren Lektionen);
  • jeder Thread zählt an seinem eigenen Platz, und am Ende werden die Plätze addiert. Dann wird nichts geteilt, und nichts muss geschützt werden.

Hier ist der dritte Weg.

Sieh es dir an

Der Seitenaufruf-Zähler

Vier Threads mit je 100.000 Aufrufen:

counts = [0] * 4




def visitor(slot):
    for _ in range(100_000):
        counts[slot] += 1  # nur dieser Thread schreibt hier




threads = [threading.Thread(target=visitor, args=(slot,))
           for slot in range(4)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print(f"Aufrufe: {sum(counts)}")
Ausgabe
Aufrufe: 400000

400.000 bei jedem Lauf. Jeder Thread schreibt nur in sein eigenes counts[slot], also kommt keiner dem anderen in den Weg. sum(counts) wird erst nach join aufgerufen, wenn die Threads fertig sind.

Genauer, für Neugierige

In fremdem Code begegnet dir next(counter) auf itertools.count() als „atomarer“ Zähler. In CPython mit dem GIL verliert er wirklich keine Werte, aber das ist ein Implementierungsdetail, kein Versprechen der Sprache. In Python 3.13 ohne GIL (free-threaded) verlass dich nicht darauf. In Java ist diese Idee (getrennt zählen, am Ende addieren) eine fertige Klasse: LongAdder.

Wie viel schneller als ein Lock ist das? Das hängt von der Maschine ab und davon, wie viele Threads um eine Zelle kämpfen. Ohne Kampf ist ein atomares +1 ein paar Nanosekunden. Ein Lock ohne Kampf ist nahe daran. Der Unterschied kommt mit vielen Threads: Dann legt das Lock Threads schlafen, während die atomare Operation nur wiederholt.

Die Idee

Prüfen und ändern: Compare-and-set

Kaufen ist nicht nur −1. Es ist „wenn mindestens eins da ist, um 1 verringern“. Die Prüfung und die Änderung müssen ein Schritt sein.

Dafür gibt es eine allgemeinere atomare Operation: Compare-and-set (CAS). Du gibst ihr zwei Zahlen: was du dort vermutest und was du dort haben willst. Sie ändert den Wert nur, wenn er noch so ist, wie du denkst, und sagt dir, ob es geklappt hat. Hat ein anderer Thread ihn inzwischen geändert, fasst CAS nichts an und antwortet „nein“.

Dann ist Kaufen eine Schleife:

  1. den Bestand lesen;
  2. ist er 0, ablehnen;
  3. CAS: „Wenn es noch so viel ist, mach eins weniger daraus“;
  4. schlägt CAS fehl, hat inzwischen jemand gekauft: zurück zu 1.
Python hat kein CAS. Damit du die Idee siehst, ist AtomicCell unten ein kleiner Ersatz: compare_and_set macht die Prüfung und die Änderung unter einem Lock. Ein echtes CAS ist ein Prozessorbefehl, ohne Lock.

Sieh es dir an

Die letzten drei Kopfhörer

class AtomicCell:
    """Python hat kein CAS: ein kleiner Ersatz mit einem Lock"""


    def __init__(self, value):
        self._value = value
        self._lock = threading.Lock()


    def get(self):
        return self._value


    def compare_and_set(self, expected, new):
        with self._lock:
            if self._value != expected:
                return False
            self._value = new
            return True




class FlashSale:
    def __init__(self, items):
        self.stock = AtomicCell(items)


    def try_buy(self):
        while True:
            left = self.stock.get()
            if left == 0:
                return False  # ausverkauft
            if self.stock.compare_and_set(left, left - 1):
                return True
            # jemand hat stock geändert: noch einmal lesen
Schritt für Schritt, in Worten
  1. Die letzten 3 Kopfhörer: Der Bestand ist 3. Threads A und B rufen try_buy() gleichzeitig auf.
  2. A liest den Bestand: left = 3.
  3. B liest ihn, bevor A etwas geändert hat: ebenfalls 3.
  4. B: compare_and_set(3, 2). „Wenn es noch 3 ist, mach 2 daraus.“ Es ist noch 3, also wird 2 geschrieben. B hat gekauft.
  5. A versucht dasselbe: „wenn es noch 3 ist …“. Jetzt ist es 2, also wird nichts geschrieben, und die Antwort ist false. Nichts geht verloren.
  6. A wartet nicht und gibt nicht auf: Die Schleife läuft weiter, und A liest noch einmal: 2. Kein Thread hat geschlafen.
  7. A: „wenn es noch 2 ist, mach 1 daraus“. Es ist noch 2: 1 wird geschrieben. Auch A hat gekauft.
  8. Zwei Käufer, zwei verkauft, Bestand 1. Es gibt kein Lock: Der Prozessor prüft und schreibt in einem Schritt, und wer verliert, wiederholt nur die Schleife.

Niemand wartet: Der Thread, der verloren hat, wiederholt nur zwei Zeilen. Das nennt man lock-free. Hundert Stück bei 160 Versuchen:

sale = FlashSale(100)
results = []  # list.append ist von vielen Threads aus sicher




def buyers():
    for _ in range(40):
        results.append(sale.try_buy())




threads = [threading.Thread(target=buyers) for _ in range(4)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print("Verkauft:", results.count(True))
print("Abgelehnt:", results.count(False))
print("Bestand:", sale.stock.get())
Ausgabe
Verkauft: 100
Abgelehnt: 60
Bestand: 0

Wie oft die Schleife durchlaufen wurde, ist bei jedem Lauf anders, deshalb gibt das Programm es nicht aus. Die Summen sind immer gleich: 100 verkauft, 60 abgelehnt, 0 im Bestand.

Genauer, für Neugierige

In echtem Python-Code schreibst du kein AtomicCell. Du legst ein Lock um die Prüfung und das Verringern, und es tut dasselbe:

class FlashSale:
    def __init__(self, items):
        self.stock = items
        self.lock = threading.Lock()


    def try_buy(self):
        with self.lock:
            if self.stock == 0:
                return False  # ausverkauft
            self.stock -= 1
            return True
Ausgabe
Verkauft: 100
Abgelehnt: 60
Bestand: 0

Probier es aus

Sag die Ausgabe voraus

Hier sind die zwei „Threads“ nacheinander in einem Thread geschrieben, damit die Reihenfolge bei jedem Lauf dieselbe ist wie in der Szene. Was gibt es aus?

AtomicCell ist die Klasse aus der Szene.
stock = AtomicCell(3)
seen_by_a = stock.get()
seen_by_b = stock.get()
print("B:", stock.compare_and_set(seen_by_b, seen_by_b - 1))
print("A:", stock.compare_and_set(seen_by_a, seen_by_a - 1))
seen_by_a = stock.get()
print("A noch einmal:", stock.compare_and_set(seen_by_a, seen_by_a - 1))
print("Bestand:", stock.get())
Antwort

Probier es aus

Ergänze

Womit vergleicht das CAS beim Kaufen?

if self.stock.compare_and_set(, left - 1):

Probier es aus

Finde den Fehler

Ein Kollege hat das Kaufen vereinfacht. Jede Zeile für sich ist sicher, und trotzdem werden im Sale 103 Kopfhörer von 100 verkauft. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Problem

Die Preisliste, die sich mittendrin ändert

Um 10:00 startet der Admin die Aktion: Kopfhörer von 60 auf 48 €, Hülle von 15 auf 12 €, Kabel von 5 auf 4 €. Gleichzeitig berechnen die Kassen Warenkörbe. Liegen die Preise in einem gemeinsamen Dictionary und ändern sich einzeln, kann eine Kasse den neuen Preis der Kopfhörer und den alten der Hülle lesen:

# Admin
prices["headphones"] = 48
prices["case"] = 12
prices["cable"] = 4


# Checkout, gleichzeitig
total = sum(prices[item] for item in cart)

Der Warenkorb kostet 68 €: eine Summe, die zu keinem Zeitpunkt stimmte. Nicht mit den alten Preisen (80 €), nicht mit den neuen (64 €).

Die Idee

Nicht ändern, ganz ersetzen

Die Preisliste wird oft gelesen und selten geändert. Dann ändere sie nie. Mach sie zu einem unveränderlichen Objekt: Einmal erstellt, bleibt sie gleich. Für die Aktion macht der Admin eine neue Preisliste und tauscht eine Referenz: „Die aktuelle Preisliste ist diese.“

  • Ein Objekt, das niemand ändert, können beliebig viele Threads ohne jeden Schutz lesen.
  • Das Einzige, was geteilt wird, ist die Referenz, und sie zu tauschen ist ein atomarer Schritt.
  • Die Kasse nimmt die Referenz einmal zu Beginn des Warenkorbs und berechnet den ganzen Warenkorb damit. Sie sieht die ganze alte oder die ganze neue Preisliste, nie eine Mischung.

@dataclass(frozen=True) verbietet das Ändern der Felder. Das Dictionary darin kann sich aber noch ändern, deshalb ist es ein MappingProxyType: eine nur lesbare Sicht auf das Dictionary. Das Tauschen ist eine gewöhnliche Zuweisung: current = PriceList(...). Das Zuweisen eines Namens ist in Python ein Schritt, also liest die Kasse entweder das alte oder das neue Objekt.

@dataclass(frozen=True)
class PriceList:
    version: int
    prices: MappingProxyType  # nur lesbar


    def total(self, cart):
        return sum(self.prices[item] for item in cart)
regular = MappingProxyType({"headphones": 60, "case": 15, "cable": 5})
promo = MappingProxyType({"headphones": 48, "case": 12, "cable": 4})
cart = ["headphones", "case", "cable"]
current = PriceList(1, regular)
mixed = 0




def admin():
    global current
    for v in range(2, 1002):
        prices = promo if v % 2 == 0 else regular
        current = PriceList(v, prices)  # ein neuer Schnappschuss, eine Referenz




def checkout():
    global mixed
    for _ in range(20_000):
        price_list = current  # ein Schnappschuss für den ganzen Warenkorb
        total = price_list.total(cart)
        if total not in (80, 64):
            mixed += 1




threads = [threading.Thread(target=admin), threading.Thread(target=checkout)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print("Geprüfte Summen: 20000")
print("Gemischte Summen:", mixed)
print(f"Letzte Version: {current.version}, Summe {current.total(cart)} €")
Ausgabe
Geprüfte Summen: 20000
Gemischte Summen: 0
Letzte Version: 1001, Summe 80 €
Die Kasse hat zehntausende Warenkörbe geprüft, während sich die Preisliste tausendmal geändert hat, und keine einzige Summe ist gemischt. Wie viele Warenkörbe nach der alten und wie viele nach der neuen Liste liefen, ist bei jedem Lauf anders, deshalb gibt das Programm es nicht aus.
Genauer, für Neugierige

So funktionieren auch „Copy-on-write“-Collections: CopyOnWriteArrayList in Java, ImmutableList in C#. Jede Änderung macht eine neue Kopie, und das Lesen braucht kein Lock. Das lohnt sich bei vielen Lesevorgängen und wenigen Schreibvorgängen. Wird oft geschrieben, wird das Kopieren teuer.

Unveränderlichkeit ist nur ehrlich, wenn sie bis ganz nach unten reicht. Ein Objekt mit einem final-Feld, das auf eine veränderbare Liste zeigt, ist nicht unveränderlich: Die Liste lässt sich von außen ändern. Deshalb reicht frozen=True nicht, und das Dictionary ist ein MappingProxyType.

So ist es in den anderen Sprachen: record und Map.copyOf mit AtomicReference in Java; record mit ImmutableDictionary und Volatile oder Interlocked.Exchange in C#; eine frozen-Dataclass, ein tuple oder MappingProxyType und Zuweisung in Python; Object.freeze und Nachrichten zwischen Workern in JavaScript.

Die Idee

Wenn atomar nicht reicht

Eine Reservierung verschiebt ein Stück vom Bestand in die Zahl der Reservierten. Die Regel ist, dass beide zusammen immer 10.000 sind. Zwei atomare Variablen halten sie nicht ein:

stock = 10
reserved = 0




def reserve():
    global stock, reserved
    stock -= 1     # in Python ist nicht einmal eine Zeile atomar,
    reserved += 1  # geschweige denn beide zusammen

Zwischen den beiden Zeilen sieht der Prüfer insgesamt 9.999. Atomar schützt einen Wert. Geht es in der Regel um mehrere Werte zusammen, brauchst du ein Lock um alle Änderungen und um die Prüfung:

class Warehouse:
    def __init__(self, stock):
        self.stock = stock
        self.reserved = 0
        self.lock = threading.Lock()


    def reserve(self):
        with self.lock:  # beide oder keine
            if self.stock == 0:
                return False
            self.stock -= 1
            self.reserved += 1
            return True


    def audit(self):
        with self.lock:
            return self.stock + self.reserved


    def report(self):
        with self.lock:
            return f"Bestand: {self.stock}, reserviert: {self.reserved}"
warehouse = Warehouse(10_000)
broken = 0




def reserver():
    while warehouse.reserve():
        pass




def auditor():
    global broken
    for _ in range(20_000):
        if warehouse.audit() != 10_000:
            broken += 1




threads = [threading.Thread(target=f) for f in (reserver, reserver, auditor)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print(warehouse.report())
print("Fehlerhafte Prüfungen:", broken)
Ausgabe
Bestand: 0, reserviert: 10000
Fehlerhafte Prüfungen: 0
Genauer, für Neugierige

Ein anderer Weg ohne Lock: beide Werte in einem unveränderlichen Objekt (Bestand, Reserviert) und der Tausch mit einem CAS auf die Referenz. Ein neues Objekt mit beiden neuen Werten ersetzt das alte auf einen Schlag. Das verbindet die zwei Ideen dieser Lektion, aber das Lock ist meist klarer.

Was wann zu benutzen ist:

  • ein Wert, ein Zähler oder ein Flag: eine atomare Operation;
  • einen Wert prüfen und ändern: eine CAS-Schleife;
  • Daten, die viel gelesen und selten geändert werden: ein unveränderliches Objekt und ein Tausch der Referenz;
  • mehrere zusammenhängende Werte: ein Lock.

Übung

Ein Gutschein mit begrenzter Einlösezahl

Löse die Aufgabe in deinem Editor.

Der Gutschein „SPRING20“ kann 50-mal eingelöst werden. Acht Threads mit je 10 Kunden versuchen gleichzeitig, ihn einzulösen. Schreibe Coupon mit try_use() so, dass der Gutschein nie öfter als 50-mal eingelöst wird. Mit einem Lock um die Prüfung und das Verringern. Gib aus, wie oft er eingelöst wurde, wie viele Ablehnungen es gab und wie viele Einlösungen übrig sind:

Ausgabe
Eingelöst: 50
Abgelehnt: 30
Übrig: 0

Weitere Aufgaben

  • Das Maximum. Halte die größte Bestellung des Tages fest, während viele Threads Bestellungen hinzufügen. Tipp: eine CAS-Schleife, die nur schreibt, wenn die neue größer ist.
  • Zwei Aktionen. Gib der Preisliste eine Version und lass zwei Admins gleichzeitig veröffentlichen. Wie verhinderst du, dass die Aktion des einen Admins verloren geht? (Tipp: Tausche die Referenz nur mit CAS, wenn die Version noch die ist, die du gelesen hast.)
  • Der Prüfer ohne Lock. Lege den Bestand und die Zahl der Reservierten in ein unveränderliches Objekt und tausche es mit CAS. Prüfe, dass der Prüfer weiterhin immer 10.000 sieht.

Test

Teste dich

1. Der Bestand ist 6. Ein Thread ruft CAS auf: „Wenn es 5 ist, mach 4 daraus.“ Was passiert?
2. tryBuy hat „wenn der Bestand > 0 ist“ und dann „um 1 verringern“. Beide Zeilen sind atomar. Warum verkauft es trotzdem mehr, als da ist?
3. Die Kassen lesen die Preisliste tausende Male pro Sekunde, und sie ändert sich einmal am Tag. Wie teilst du sie am besten?
4. Du reservierst ein Stück: Der Bestand sinkt um 1, und die Zahl der Reservierten steigt um 1. Der Prüfer kontrolliert, dass die Summe immer 10.000 ist. Was brauchst du?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·