Schedules von Hand auszuprobieren findet einen Fehler nur, wenn man den richtigen errät. Ein Explorer führt das Programm unter allen Schedules aus, listet alle Ergebnisse auf und gibt Ihnen den Schedule, der es gebrochen hat. Für zwei Threads, die die Aufwärtstage von zehn SPY-Renditen zählen, gibt es 210 Schedules, und nur 10 davon liefern die richtige Zahl.
Wie viele Schedules gibt es?
Ein Schedule ist eine Reihenfolge von Zügen, und Thread t nimmt genau lengths[t] davon. Um die Reihenfolgen zu zählen, legt man alle Züge in eine Reihe (die Summe ihrer Längen), die sich auf so viele Arten anordnen lässt wie die Fakultät dieser Zahl; dann teilt man durch die Fakultät der Züge jedes Threads, denn das Vertauschen zweier Züge desselben Threads ergibt keinen neuen Schedule. Das ist der Multinomialkoeffizient. Er wächst schnell: Zwei Threads mit je 2 Zügen haben nur 6 Schedules, drei Threads mit je 3 Zügen haben 1.680 und zwei Threads mit je 10 Zügen haben 184.756. Deshalb kann niemand ein nebenläufiges Programm prüfen, indem er zufällige Schedules ausprobiert und hofft.
def count_schedules(lengths): total = factorial(sum(lengths)) for n in lengths: total //= factorial(n) return totalprint(count_schedules([2, 2]))print(count_schedules([3, 3, 3]))print(count_schedules([10, 10]))
6 1680 184756
Threads als Generatoren
Im letzten Labor war ein Thread eine Liste von Schritten. Echter Code lässt sich besser als gewöhnliches Python schreiben, daher ist ein Thread ab jetzt ein Generator, der das gemeinsame Dictionary nimmt und vor jedem Zugriff auf gemeinsame Daten yield ausführt. Ein Aufruf von next() führt den Thread dann bis zu seinem nächsten Zugriff und nicht weiter, sodass ein Zug genau ein Schritt ist, mit dem sich ein anderer Thread verzahnen kann. run_threads primt jeden Generator (lässt ihn bis zum ersten yield laufen), gibt dem durch jeden Schedule-Eintrag genannten Thread einen Zug und lässt nach dem Ende des Schedules die unfertigen Threads in Thread-Reihenfolge fertig werden. all_schedules listet alle Zugfolgen auf, indem es wählt, welcher Thread zuerst geht, und auf dem Rest rekursiv weitermacht. Unten die sechs Schedules zweier Threads, die je einmal erhöhen.
def all_schedules(lengths): if sum(lengths) == 0: return [[]] out = [] for tid, n in enumerate(lengths): if n: rest = list(lengths) rest[tid] -= 1 out += [[tid] + tail for tail in all_schedules(rest)] return outdef run_threads(make_threads, schedule, shared=None): shared = dict(shared or {}) threads = make_threads(shared) alive = [True] * len(threads) def turn(tid): try: next(threads[tid]) except StopIteration: alive[tid] = False for tid in range(len(threads)): turn(tid) for tid in schedule: if alive[tid]: turn(tid) while any(alive): for tid in range(len(threads)): if alive[tid]: turn(tid) return sharedtwo = lambda shared: [increments(1)(shared), increments(1)(shared)]for schedule in all_schedules([2, 2]): print(schedule, run_threads(two, schedule))
[0, 0, 1, 1] {'x': 2}
[0, 1, 0, 1] {'x': 1}
[0, 1, 1, 0] {'x': 1}
[1, 0, 0, 1] {'x': 1}
[1, 0, 1, 0] {'x': 1}
[1, 1, 0, 0] {'x': 2}Zwei der sechs Schedules enden bei 2, die anderen vier bei 1. Die beiden guten sind die, in denen ein Thread beide Schritte macht, bevor der andere beginnt. In den anderen vier lesen beide Threads, bevor einer schreibt, genau das verlorene Update des letzten Labors, nun gefunden ohne Raten.
Erkunden, dann fragen
explore führt das Programm unter allen Schedules aus und zählt, wie viele Schedules jeden Endzustand ergeben. Der Schlüssel ist ein sortiertes Tupel aus (Name, Wert)-Paaren, damit gleiche Zustände derselbe Schlüssel sind. find_schedule stellt die Frage eines Fehlerberichts: Welcher Schedule bricht meine Invariante? Es gibt den ersten zurück, und weil run_threads deterministisch ist, kann man ihn wiederholen, ausgeben oder in einen Test kopieren. Gibt es None zurück, gilt die Invariante unter jedem Schedule, was für dieses kleine Programm ein Beweis ist, keine Hoffnung.
def explore(make_threads, lengths, shared=None): outcomes = {} for schedule in all_schedules(lengths): key = tuple(sorted(run_threads(make_threads, schedule, shared).items())) outcomes[key] = outcomes.get(key, 0) + 1 return outcomesdef find_schedule(make_threads, lengths, check, shared=None): for schedule in all_schedules(lengths): if not check(run_threads(make_threads, schedule, shared)): return schedule return Noneprint(explore(two, [2, 2]))print(find_schedule(two, [2, 2], lambda shared: shared["x"] == 2))
{(('x', 2),): 2, (('x', 1),): 4}
[0, 1, 0, 1]Die Brute-Force-Aufzählung funktioniert für wenige Züge pro Thread und explodiert dann. Echte Explorer beschneiden: Sie merken sich bereits gesehene Zustände und überspringen Schedules, die nur Schritte umordnen, die einander nicht beeinflussen können. Die Idee bleibt dieselbe, was Sie hier bauen, ist also das richtige mentale Modell.
returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:10]ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]lengths = [2 * k for k in ups]many = lambda shared: [increments(k)(shared) for k in ups]print(ups, count_schedules(lengths))print({dict(key)["x"]: n for key, n in explore(many, lengths).items()})
[2, 3] 210
{5: 10, 4: 70, 3: 104, 2: 26}Die richtige Antwort x = 5 kommt in nur 10 der 210 Schedules vor, etwa 5 %. Ein Test, der das Programm einmal oder hundertmal auf einer echten Maschine ausführt, auf der sich die Threads selten genau so überlappen, würde fast immer bestehen und trotzdem einen Fehler ausliefern. Der Explorer kann ihn nicht übersehen, und find_schedule gibt Ihnen den ersten Schuldigen: [0, 0, 0, 1, 0, 1, 1, 1, 1, 1].
Eine Aussage über die Daten, die unabhängig vom Schedule gelten muss. Ein nebenläufiges Programm ist korrekt, wenn seine Invariante unter jedem Schedule gilt, und das Erkunden aller Schedules ist der Weg, sie für einen kleinen Fall zu prüfen.
Was Sie bauen werden
Das Labor folgt der Lektion: die Anzahl der Schedules, die Liste aller, die Maschine, die Generator-Threads unter einem Schedule ausführt, der Explorer, der Ergebnisse zählt, die Suche nach dem ersten Schedule, der eine Invariante bricht, und die Studie zweier Threads, die SPY-Aufwärtstage zählen.
- Funktion · FrageBaut auf
- count_schedules(lengths)Wie viele Schedules hat das Programm?Einfache Arithmetik
- all_schedules(lengths)Welche sind es, der Reihe nach?Einfache Arithmetik
- run_threads(make_threads, schedule, shared)Was hinterlässt ein Schedule?Einfache Arithmetik
- explore(make_threads, lengths, shared)Welche Ergebnisse gibt es, und wie oft?all_schedulesrun_threads
- find_schedule(make_threads, lengths, check)Welcher Schedule bricht die Invariante zuerst?all_schedulesrun_threads
- study(bars)Wie viele Schedules des SPY-Zählens gehen schief?count_schedulesexplorefind_schedule
Nächstes Thema: Der Explorer zeigt, dass der Fehler real ist; nun beheben wir ihn. Atomics und Read-Modify-Write fügt die Operationen hinzu, die ein Prozessor in einem unteilbaren Schritt ausführen kann, etwa Fetch-and-Add und Compare-and-Swap, und Sie prüfen mit dem Explorer, dass der Zähler unter jedem Schedule stimmt.
Lab: Was bewertet wird
6 Aufgaben · 100 Pkt.- Wie viele Schedules10 Pkt.
- Jeder Schedule15 Pkt.
- Die Threads ausführen25 Pkt.
- Jedes Ergebnis zählen20 Pkt.
- Der erste schlechte Schedule10 Pkt.
- Die Studie mit der SPY-Tabelle20 Pkt.