Haskell: Wie funktioniert TVar?

Question

Wie funktioniert TVar? Von dem, was ich gelesen habe, versucht es, alle Transaktionen sofort nach dem Empfang auszuführen, eine Transaktion, die jedoch abgeschlossen wird, macht andere laufende Transaktionen ungültig, die dann neu gestartet werden müssen. Funktioniert TVar so?

Wenn dies der Fall wäre, wenn es Transaktionen mit 1 ms langen Transaktionen alle 100 ms geben würde, würde dies bedeuten, dass eine Transaktion, die 200 ms dauert, nie ausgeführt wird?

Answer 1

Solange zwei Transaktionen auf unterschiedliche TVars zugreifen, können beide gleichzeitig festgeschrieben werden, ohne sich gegenseitig zu entkräften.

einfach deutlich zu machen, wenn eine Transaktion für ungültig erklärt ist, lassen Sie sich das folgende Szenario vor:

1. Angenommen, t :: TVar Int-0 initialisiert und wird über readTVar t zu Beginn einer Transaktion A lesen.
2. Währenddessen wird in einem anderen Thread die Transaktion B gestartet, in der eine writeTVar t 1 ausgeführt wird. Nehmen Sie an, dass B vor A commits. Das STM-System wird prüfen, ob Inkonsistenzen vorliegen, und zu dem Schluss kommen, dass es sicher ist, dass B zu diesem Zeitpunkt festgeschrieben wird, sodass jetzt writeTVar t 1 wirksam wird.
3. Dies führt jedoch dazu, dass die Transaktion A ungültig wird, da der alte Wert 0 von t zu Beginn von A gelesen wurde. (Wenn A erlaubt wurde zu begehen, würden wir eine Verletzung der Unteilbarkeit bekommen.)

Das Originalpapier [1] auf Haskells STM-System (siehe Abschnitt 6.5) beantwortet Ihre Frage:

„Starvation Beispielsweise kann eine Transaktion, die für eine sehr lange Zeit unter läuft, wiederholt mit kürzeren Transaktionen in Konflikt geraten. Wir denken, dass ein Verhungern in der Praxis unwahrscheinlich ist, aber wir können nicht ohne weitere Erfahrung sagen. "

[1] Tim Harris, Simon Marlow, Simon Peyton Jones und Maurice Herlihy. ACM-Konferenz über Prinzipien und Praxis der Parallelprogrammierung 2005 (PPoPP'05).

Answer 2

Wenn es Transaktionen mit 1 ms langen Transaktionen alle 100 ms geben würde, würde dies bedeuten, dass eine Transaktion, die 200 ms dauert, nie abgeschlossen wird?

Transaktionen nur Konflikt, wenn sie die gleichen TVar s berühren, so dass, wenn einige der 1ms Transaktionen alle Variablen durch die 200ms Transaktionen beeinflusst vermieden werden, dann ist die 200ms würde man vervollständigen können. Darüber hinaus, da die STM Monade ziemlich streng ist, was innerhalb (nur Speicherzugriffe und reine Berechnungen!) Erlaubt ist, ist es sehr ungewöhnlich, eine solche Diskrepanz zwischen der Länge der Transaktionen zu haben; in der Regel werden sie nur ein paar Speicher liest/schreibt lange, und alle IO und andere Berechnungen werden außerhalb der Transaktion durchgeführt werden.Ob eine bestimmte Transaktion jemals für immer von anderen Transaktionen blockiert wird, ist ein bisschen ein Planungsproblem; Ich bin nicht 100% sicher, wie der aktuelle Scheduler von GHC aussieht, aber es erscheint plausibel, dass er älteren (oder höheren Ausfallraten) Transaktionen den Vorzug gibt.

Das gesagt, Livelock ist ein sehr reales Problem mit STM, und ist etwa so hinterhältig und als schwierig, als Deadlock in traditionelleren Locking Concurrency-Implementierungen zu begründen.

Wie funktioniert TVar?

Sie werden wahrscheinlich genießen this paper.