Czy protokół STM zapewnia precyzyjne blokowanie istniejących struktur danych?

Question

Reading Bartosz Milewski fantastycznie blog post na STM, byłem podekscytowany, aby przeczytać, co następuje:

jednak brać pod uwagę ważny fakt: STM jest bardzo drobnoziarnista. W przypadku instancji podczas wstawiania elementu do drzewa transakcja STM blokuje tylko te węzły, które faktycznie modyfikujesz. STM z łatwością pokona rozwiązanie wykorzystujące jedną globalną blokadę na całe drzewo .

Jednak, jak rozumiem, zachowanie to nie jest automatyczne, prawda? Jeśli używam numeru TVar (Map k a), czy nie działa on jako pojedynczy globalny zamek na całej mapie? Aby uzyskać korzyści z tego drobiazgowego zachowania, ja (lub ktoś) musiałbym wdrożyć wymianę mapy (na przykład TMap), która zawiera wewnętrznie, TVars, prawda?

To może wydawać się oczywistym pytaniem, ale czytając o implementacji STM byłem zdezorientowany między odczytami TVar s a odczytami lokalizacji pamięci. Chcę tylko upewnić się, że mam to dobrze!

Bartosz idzie dalej do powiedzenia:

Per-węzła zamek Instrukcja jest trudne do wdrożenia poprawnie, ponieważ na ryzyko zakleszczenia.

Różnica z STM, jak zrozumieć, że podczas gdy realizacja STM w efekcie wykorzystuje blokuje drogę ręcznie zablokowana rozwiązanie może rzeczywista ACQuiry i zwolnienie blokad jest obsługiwany przez program, a nie programista - poprawny?

Answer 1

A TVar to komórka zmienna. W przypadku niezmiennych struktur żadne dwa wątki nie mogą przenosić modyfikacji tam iz powrotem, więc potrzebujemy jakiegoś pojęcia zmiennego komórki, aby wywołać efekt. W szczególności mamy

writeTVar :: TVar a -> a -> STM() 

który tworzy SMT działania zastępując wartość zmienny wewnątrz komórki. Możemy sekwencjonowania kilka z tych operacji razem, budując większe i bardziej złożone STM działania, a następnie zadzwonić

atomically :: STM a -> IO a 

do atomowo popełnić cały STM czynności naraz. Jest to "transakcyjna" część pamięci transakcyjnej oprogramowania: inne wątki z własnymi odwołaniami do tych zmiennoprzecinkowych komórek będą tylko świadkami całego działania, bez podelementów. Aby to osiągnąć Haskell może użyć blokowania lub czegoś bardziej sprytnego - jest to jedynie detal implementacyjny. Jedyną rzeczą, o której musisz wiedzieć, jest to, że akcje w twoim bloku mogą być uruchamiane wielokrotnie, jeśli to konieczne, a więc efekty uboczne poza modyfikacją niektórych komórek pamięci współdzielonej są zabronione.

Jak zatem uzyskać drobnoziarnistą współbieżność? Łatwo: po prostu dostarczamy więcej zmiennych komórek dla różnych wątków do synchronizacji. Na przykład możemy przeczytać co najmniej 3 różne typy Map.

TVar (Map k v) 
Map k (TVar v) 
TVar (Map k (TVar v)) 

Pierwszy pozwoli równoległych nici, aby modyfikacje całego Map na raz, tak że nie ma częściowe zmiany są widoczne. Drugi umożliwia zmiany w dowolnej zapisanej wartości, ale utrzymuje, że sama struktura mapy - wybór kluczy i wybór przechowywanych wartości - jest niezmienna, a zmian nie można łatwo propagować do innych wątków.

Ostateczny wybór, TVar (Map k (TVar v)) jest najbardziej elastyczny. Możemy dokonać modyfikacji hurtowych na Map poprzez synchronizację na zewnętrznym TVar i możemy dokonać zmian wartości zapisanych na mapie, odczytując wartości do wartości TVar i synchronizując działania w nich. Pełny zestaw możliwej semantyki dostępnej dla takiego drzewa jest niezliczony, pozwalając zarówno na "całkowite zablokowanie" i "indywidualne blokowanie wartości".