Blokady są zwykle wdrażane za pomocą instrukcji testowania i ustawiania oraz wymiany na poziomie maszyny. Czy istnieją inne implementacje, które ich nie wykorzystują?
Czy możemy również powiedzieć, że wszystkie rozwiązania problemu krytycznego na poziomie sprzętowym można podzielić na trzy, a mianowicie: wyłączanie przerwań, testowanie i ustawianie oraz zamiana?
Odpowiedzi:
Tak, możesz wdrożyć wzajemne wykluczanie tylko z ładowaniem pamięci i instrukcjami przechowywania. Istnieje długa tradycja opracowywania kolejno prostszych rozwiązań tego problemu.
Najwcześniejsza znana mi wersja, zwana „rozwiązaniem Dekkera”, została wprowadzona w Dijkstra, Edsger W .; „Współpracujące procesy sekwencyjne”, w: F. Genuys, red., Programming Languages: NATO Advanced Study Institute , s. 43–112, Academic Press, 1968 . Od tego czasu pojawiło się kilkadziesiąt rozwiązań. Omówię tylko kilka z tych bardziej znaczących.
Lamport, Leslie; „Nowe rozwiązanie problemu współbieżnego programowania Dijkstry”, Comm ACM 17 (8): 453-455, 1974 wprowadza „algorytm piekarniczy” (ponieważ opiera się na analogii ludzi przyjmujących liczby w celu ustalenia kolejności, w jakiej będą podawane w sklepie piekarni). Jedną ze szczególnie godnych uwagi cech tego algorytmu jest to, że pokazuje, że atomowość sprzętu wcale nie jest wymagana do rozwiązania problemu wzajemnego wykluczenia. Odczyty nakładające się na zapisy w tej samej lokalizacji mogą zwrócić dowolną wartość, a algorytm nadal działa. Lamport omawia to nieco w opisie artykułu na swojej stronie głównej .
Rozwiązanie Petersona, Peterson, GL; „Mity na temat problemu wzajemnego wykluczenia”, Inf. Proc. Łotysz. , 12 (3): 115-116, 1981 , to taki, który został specjalnie zaprojektowany, aby był łatwy do zrozumienia i uzasadnienia. Wreszcie, moim ulubionym jest Lamport, Leslie; „Szybki algorytm wzajemnego wykluczenia”, ACM Trans. Komp. Sys. , 5 (1): 1-11, 1987. W tym artykule Lamport starał się zoptymalizować rozwiązanie problemu wzajemnego wykluczenia w (powszechnym) przypadku, gdy nie ma sprzeczności w części krytycznej. Gwarantuje wzajemne wykluczenie i swobodę impasu, ale nie sprawiedliwość. Jest to (uważam) pierwszy algorytm wzajemnego wykluczania wykorzystujący tylko normalne odczyty i zapisy, które mogą zsynchronizować N procesorów w czasie O (1), gdy nie ma rywalizacji. (Kiedy dochodzi do rywalizacji, opiera się ona na teście O (N).) Nieformalnie demonstruje, że najlepiej, co możesz zrobić w przypadku bez rywalizacji, jest siedem dostępów do pamięci. (Zarówno Dekker, jak i Peterson robią to z 4, ale mogą obsłużyć tylko 2 procesory, kiedy rozszerzysz ich algorytmy na N, będą musieli dodać dodatkowy dostęp O (N).)
Najwyraźniej ludzie, którzy pracują nad rozwiązaniem problemu wzajemnego wykluczenia za pomocą samej pamięci, czytają i piszą, są sfrustrowani brakiem zrozumienia problemu i jego rozwiązań przez innych ludzi. Świadczy o tym częściowo tytuł artykułu Petersona („Mity o problemie wzajemnego wykluczenia”), a częściowo krótka notka Lamport opublikowana w 1991 r .: Lamport, Leslie; „Problem wzajemnego wykluczenia został rozwiązany”, Comm ACM 34 (1): 110, 1991 , który Lamport opisuje nieco gorzko na swojej stronie głównej .
Tak więc, aby odpowiedzieć na drugie pytanie: Nie. Istnieje wiele więcej niż trzy kategorie sprzętowych rozwiązań problemu sekcji krytycznej (używanie tylko ładowań i sklepów to jedna, inne obejmują instrukcje porównywania i zamiany, powiązane z ładowaniem / warunkowe w sklepie instrukcje (za pomocą protokołu koherencji pamięci podręcznej do testowania atomowości) oraz instrukcje pobierania i dodawania). W innym sensie istnieje naprawdę tylko jedna kategoria rozwiązań: te, które wymagają uzyskania szeregu procesów asynchronicznych w celu uzgodnienia globalnej kolejności zdarzeń .
(Zauważ, że ta odpowiedź jest (obszerną) edycją wcześniejszej odpowiedzi, którą podałem na zupełnie inne pytanie ).