Jeśli korzystam z blokad, czy mój algorytm może nadal być bez blokady?

10

Powszechną definicją bez blokady jest to, że co najmniej jeden proces robi postęp. 1

Jeśli mam prostą strukturę danych, taką jak kolejka, chronioną przez blokadę, wtedy jeden proces może zawsze robić postęp, ponieważ jeden proces może uzyskać blokadę, zrobić to, co chce i zwolnić.

Czy spełnia zatem definicję bez blokady?

1 Patrz np. M. Herlihy, V. Luchangco i M. Moir. Synchronizacja bez przeszkód: przykładowo podwójne kolejki. W Distributed Computing, 2003. „Jest bez blokady, jeśli zapewnia tylko, że jakiś wątek zawsze robi postępy”.

multithreading Joe Pension
źródło
3
Zawsze rozumiałem „bez blokady”, aby opisać strukturę danych i zestaw algorytmów, które nie używają blokad, tylko niewielki zestaw operacji na pamięci atomowej. Np. Drdobbs.com/parallel/writing-lock-free-code-a-corrected-queue/…
Paul Johnson

Odpowiedzi:

16

To nie jest definicja bez blokady.

Jeśli możesz zagwarantować postęp, to nie masz żadnych zakleszczeń , a jeśli ostatecznie spełnisz każde żądanie, nie masz głodu , ale nie masz blokady.

Wątpię, czy twój prosty przykład tak naprawdę to zapewnia. Potrzebujesz hierarchii blokad i tak dalej, aby faktycznie zagwarantować postęp w przypadku wielu blokad.

Ben Voigt
źródło
1
Używam definicji z M. Herlihy. Metodologia wdrażania wysoce współbieżnych obiektów danych. Transakcje dotyczące programowania języków i systemów, 1993. „Warunek bez blokady gwarantuje, że pewien proces zawsze będzie postępował pomimo arbitralnych awarii lub opóźnień innych procesów”
Joe Pension
12
@Joe: To nie jest definicja, to implikacja. Strzeż się logicznego błędu odwrotności.
Ben Voigt
2
Można również zacytować M. Herlihy, V. Luchangco i M. Moir. Synchronizacja bez przeszkód: przykładowo podwójne kolejki. W Distributed Computing, 2003. „Jest bez blokady, jeśli zapewnia tylko, że jakiś wątek zawsze robi postępy”.
Joe Pension
1
istnieje również brak głodu, który jest bardziej specyficzny niż brak impasu (każdy proces przebiega bez względu na to, co robią inne procesy), zauważ, że pętle CaS (oparte na prymitywach atomowych) nie są
maniak zapadkowy
5
@Joe: Jeśli reszta świata nazywa tę nieruchomość bez impasu , to użyję tego terminu. Nie, twój prosty przykład nie jest pozbawiony impasu. Aby zagwarantować, że coś nie jest zakleszczone, potrzebujesz nie tylko synchronizacji, ale także gwarancji, że żaden wątek nie wykona żadnej operacji blokowania podczas przytrzymywania blokady. „rób, co chce” jest wyjątkowo niejasne i nie wydaje się, aby zapewniało to gwarancję.
Ben Voigt
11

Studiowałem The Art of Multiprocessor Programming 1, a ich tekst jest niejasny, podobnie jak książka, do której się odwołujesz. Oto kilka cytatów z TAMPP:

Cytat 1 (Definicja bez blokady)

Metoda jest bez blokady, jeśli gwarantuje, że nieskończenie często niektóre wywołania metod kończą się w skończonej liczbie kroków.

Cytat 2 (Definicja nieblokowania)

oczekujące wywołanie metody total nigdy nie jest wymagane do oczekiwania na zakończenie innego oczekującego wywołania.

Cytat 3 (twierdzenie, że bez blokady nie blokuje się)

Warunki oczekiwania bez blokowania i bez blokowania gwarantują postęp obliczeń jako całości, niezależnie od tego, jak system planuje wątki.

Problem polega na tym, że twierdzenie z cytatu 3 nie wynika oczywiście z definicji z cytatu 1. Jak już wspomniano, zsynchronizowana kolejka wydaje się spełniać cytat 1: nieskończenie często jakaś metoda z powodzeniem uzyskuje blokadę i kończy.

Zwróć uwagę na dość niejasne zdanie w cytacie 3: „niezależnie od tego, jak system planuje wątki”. Nie jest to poprzedzone żadnym formalnym opisem „systemu szeregowania wątków”, więc pozostaje nam zrekonstruować jego właściwości w oparciu o nasze wstępne założenia, co powinny oznaczać definicje :

  1. system zawsze wykonuje instrukcje jakiegoś wątku;
  2. nigdy nie może wykonywać instrukcji dla danego wątku;
  3. wszystkie wątki wywołują rozważaną metodę.

W takim systemie metoda blokowania nie może być wolna od blokady: jeśli wątek przytrzymujący blokadę nigdy nie zostanie ponownie zaplanowany do wykonania, nie będzie innego wątku, który mógłby ukończyć wywołanie metody w skończonej liczbie kroków, ale będzie niektóre wątki wykonujące kroki metody. W przypadku bardziej realistycznego systemu, który gwarantuje, że w końcu da się czas procesora każdemu wątkowi, definicja musi wyraźnie zawierać właściwość nieblokującą:

Poprawiona definicja bez blokady

Metoda jest wolna od blokady, jeśli nie jest blokująca, a dodatkowo gwarantuje, że nieskończenie często niektóre wywołania metod kończą się w skończonej liczbie kroków.

1 Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, Elsevier 2008, ss. 58–60

Marko Topolnik
źródło
1
Brzmienie cytatu 1 jest naprawdę dziwne. Co rozumieją przez „nieskończenie często”? Oczywiście coś innego niż „zawsze”, więc w porządku, że metoda nigdy nie zwraca się w „niektórych” przypadkach?
Hulk
Tak, obfituje nieprecyzyjny język. Co w ogóle „często”? Myślę, że mają na myśli „w nieskończonej historii egzekucji to szczególne wydarzenie zdarza się nieskończenie wiele razy”.
Marko Topolnik
5

Terminologia nie zawsze jest spójna, ale myślę, że ważne jest, aby zadać następujące pytania dotyczące proponowanego algorytmu lub systemu:

  1. Czy jest jakaś sekwencja zdarzeń, w której wątki mogą utknąć, czekając na siebie, nawet jeśli wszystkie wątki będą miały cały czas pracy procesora, którego mogłyby użyć [jeśli tak, to nie jest to bez impasu]
  2. Jeśli jeden wątek był blokowany przez dowolnie długi czas, czy mogłoby to zablokować inne wątki lub zakłócać działanie systemu na dowolnie długi czas [jeśli tak, to nie blokuje].
  3. Czy istnieje co najmniej teoretycznie możliwa kombinacja planowania wątków, która mogłaby spowodować, że wszystkie wątki wielokrotnie powtarzałyby te same operacje, jednocześnie unieważniając pracę innych osób, bez żadnego postępu [jeśli tak, to nie jest bez blokady]
  4. Jeśli niektóre wątki mają wystarczająco dużo czasu procesora w stosunku do innego, czy mogłyby zmusić ten drugi wątek do ponawiania swoich operacji w nieskończoność [jeśli tak, to nie jest to czekanie bez oczekiwania].

Znaczące znaczenie algorytmów niezablokowanych nie polega na tym, że są one szybsze niż algorytmy niezablokowane, ale raczej na tym, że nie mają skłonności do umierania, jeśli wątek zostanie rozwiązany [zauważ, że taka gwarancja wymaga jedynie że algorytmy nie są blokujące, ale wszystkie algorytmy bez blokady są]. Algorytm bez blokady może korzystać z blokad, ale tylko wtedy, gdy próby uzyskania blokady obejmują limity czasu wraz z algorytmami zapewniającymi, że ktoś będzie mógł robić postępy (na przykład algorytm może wykorzystywać CompareExchangepętlę jako podstawową metoda arbitrażu, ale używaj blokad, aby arbitrażować dostęp, gdy wydaje się, że rywalizacja wydaje się wysoka; jeśli blokada wydaje się być utrzymywana zbyt długo, inne wątki mogą zdecydować o rezygnacji z używania tej blokady i zamiast tego stworzyć nową.CompareExchange, porzucenie blokady przez klientów nie zagroziłoby spójności systemu, choć może to oznaczać, że kod, który trzymał starą blokadę, nie wykona żadnej pracy, dopóki nie zrezygnuje ze starej blokady i nie znajdzie się w kolejce do nowej.

supercat
źródło
Różni się to od standardowej terminologii: twoje 2. odnosi się do standardowego znaczenia nieblokowania, natomiast 3. odnosi się do swobody blokowania.
Marko Topolnik
Widziałem niespójne zastosowania terminologiczne i nie znam „oficjalnego” standardu. Najważniejsze jest to, że istnieją różne gwarancje, które algorytm może zaoferować, i ważne jest, aby użyć algorytmu, który zapewnia gwarancje wystarczające do spełnienia wymagań aplikacji. Wiele dokumentów obejmuje tylko niektóre z powyższych gwarancji, ale zdarzają się przypadki, w których każdy może być w stanie spełnić wymagania dotyczące aplikacji łatwiej niż jakiekolwiek inne gwarancje, które spełniają te wymagania.
supercat
Myślę, że panuje zgoda co do tego, że terminologia przedstawiona w sztuce programowania wieloprocesorowego jest „standardowa”.
Marko Topolnik
@MarkoTopolnik: Zmienię post, aby go dopasować. Czy podoba Ci się nowa wersja ?.
supercat
Fajnie, bardzo miło.
Marko Topolnik
4

Musisz spojrzeć na „definicję”, którą zacytowałeś w kontekście :

Tradycyjnym sposobem wdrażania wspólnych struktur danych jest stosowanie wzajemnego wykluczania (blokad), aby zapewnić, że współbieżne operacje nie będą ze sobą kolidować. Blokowanie ma szereg wad w odniesieniu do inżynierii oprogramowania, odporności na błędy i skalowalności (patrz [8]). W odpowiedzi badacze zbadali szereg alternatywnych technik synchronizacji, które nie wykorzystują wzajemnego wykluczenia . Technika synchronizacji jest bez czekania, jeśli zapewnia, że ​​każdy wątek będzie kontynuował postęp w obliczu arbitralnego opóźnienia (lub nawet awarii) innych wątków. Jest bez blokady, jeśli zapewnia tylko, że jakiś wątek zawsze robi postępy.

Używasz zamków do wzajemnego wykluczenia, dlatego nie jest to technika bez zamka, o której mówią.

vartec
źródło
2

Jeśli korzystam z blokad, czy mój algorytm może nadal być bez blokady?

Może być, ale zależy to od algorytmu.

Jeśli mam prostą strukturę danych, taką jak kolejka, chronioną przez blokadę, wtedy jeden proces może zawsze robić postęp, ponieważ jeden proces może uzyskać blokadę, zrobić to, co chce i zwolnić.

Czy spełnia zatem definicję bez blokady?

Uwaga per se .

Jeśli krok „rób, co chce” nie wiąże się z nabywaniem innych blokad i gwarantuje się, że zakończy się w skończonym czasie, to ta konkretna część algorytmu będzie pozbawiona impasu.

Jeśli jednak te warunki wstępne nie zostaną spełnione, istnieje co najmniej możliwość impasu ...

Stephen C.
źródło
Po przestudiowaniu tekstu w sztuce programowania wieloprocesorowego doszedłem do wniosku, że muteksy zdecydowanie unieważniają definicję bez blokady, gdy definicja jest poprawnie zapisana. Dodałem odpowiedź na tę stronę, aby to wyjaśnić.
Marko Topolnik
1

Podany przykład nie jest pozbawiony blokady z następującego powodu.

Obsługa jednego wątku uzyskuje blokadę, a program operacyjny systemu operacyjnego zawiesił wątek na nieskończony samotny okres, a następnie cały wątek nie może zrobić postępu, ponieważ nie można uzyskać blokady uzyskanej przez zawieszony wątek.

Ogólnie rzecz biorąc, algorytmy wykorzystujące blokady nie są wolne od blokady.

Należy pamiętać, że brak blokady i brak blokady to dwie różne koncepcje. brak blokady oznacza, że ​​nie ma możliwości blokady, ale może istnieć blokada aktywacji, która może uniemożliwić postęp całego systemu. Swoboda blokowania jest silniejsza, ponieważ oznacza, że ​​niektóre wątki w systemie zawsze robią postępy ze skończoną liczbą kroków.

Chaoran
źródło
Spójrz na dokładniejszą definicję na Wikipedii: „Algorytm nie jest blokowany, jeśli spełnia wymagania, że ​​gdy wątki programu są uruchamiane wystarczająco długo, co najmniej jeden z nich robi postępy”. Wyklucza to przypadek zatrzymania nici. Postęp w zatrzymywaniu jest objęty swobodą blokowania , a nie blokowaniem .
Marko Topolnik
@MarkoTopolnik Twój komentarz w ogóle nie ma sensu. Swoboda blokowania obejmuje swobodę blokowania. Wszystko, co nie zawiera blokady, musi być wolne od przeszkód. Podana definicja nie wyklucza zatrzymywania wątków.
Chaoran
Pamiętaj, aby odróżnić „mający sens” od „bycia poprawnym”. Mój komentarz jest niepoprawny, jak wynika z mojej kolejnej odpowiedzi. Ale definicja Wikipedii jest również błędna lub przynajmniej dwuznaczna.
Marko Topolnik
@MarkoTopolnik Ponieważ przyznajesz, że twój komentarz jest niepoprawny, powinieneś go usunąć, aby uniknąć mylenia innych czytelników. Wikipedia jest często niepoprawna lub niejednoznaczna. Subtelne definicje, takie jak „swoboda zamka”, należy znaleźć w artykułach akademickich, takich jak cs.rochester.edu/~scott/papers/2006_PPoPP_synch_queues.pdf (definicja braku blokady znajduje się w sekcji 2.1)
Chaoran
Tak, jednym ze sposobów jest włączenie właściwości nieblokującej jako części definicji swobody blokowania. Stwierdzono to we wcześniejszej wersji mojej odpowiedzi.
Marko Topolnik