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

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

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?

¹ 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”.

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.

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.

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

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.

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ą.

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 ...

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.