Jakie postępy i ograniczenia czekają w sekcji krytycznej?

Po pierwsze, pozwól, że przedstawię trochę terminologii. Sekcja krytyczna (CS) jest sekwencją instrukcji, która może być wykonywana przez co najwyżej jeden proces w tym samym czasie. Podczas korzystania z sekcji krytycznych, kod można podzielić na następujące sekcje:

// Some arbitrary code (such as initialization).

EnterCriticalSection(cs);

// The code that constitutes the CS.
// Only one process can be executing this code at the same time. 

LeaveCriticalSection(cs);

// Some arbitrary code. This is called the remainder section.

Pierwsza sekcja zawiera jakiś kod, taki jak kod inicjalizacji. Nie mamy nazwy dla tej sekcji. Druga sekcja to kod, który próbuje wejść do CS. Trzecia sekcja to sam CS. Czwarta część to kod, który opuszcza sekcję krytyczną. Piąta i ostatnia sekcja nazywa się sekcją pozostałą , która może zawierać dowolny kod. Zauważ, że sam CS może być różny między procesami(rozważ na przykład proces, który odbiera żądania od klienta i wstawia je do kolejki oraz inny proces, który przetwarza te żądania).

Aby upewnić się, że implementacja sekcji krytycznych działa prawidłowo, muszą być spełnione trzy warunki. Ty wspomniałem o dwóch z nich (co wyjaśnię dalej). Trzecim jest wzajemne wykluczenie, które jest oczywiście niezbędne. Warto zauważyć, że wzajemne wykluczenie dotyczy tylko sekcji CS I leave. Pozostałe trzy sekcje nie są jednak wyłączne.

Pierwszym warunkiem jest postęp . Celem tego warunku jest upewnienie się, że albo jakiś proces jest obecnie w CS i wykonuje jakąś pracę lub, jeśli był przynajmniej jeden proces, który chce wejść do CS, zrobi to, a następnie popracuj trochę. W obu przypadkach część pracy jest wykonywana, a zatem wszystkie procesy postępują ogólnie.

Postęp: jeśli żaden proces nie jest wykonywany w jego sekcji krytycznej i niektóre procesy chcą wejść do swoich sekcji krytycznych, wtedy tylko te procesy, które nie są wykonywane w pozostałej części mogą weź udział w podejmowaniu decyzji, który z nich wejdzie do sekcji krytycznej, i ta selekcja nie może być odroczona na czas nieokreślony.

Let ' s understand ta definicja zdanie po zdaniu.

Jeśli żaden proces nie jest wykonywany w jego sekcji krytycznej

Jeśli w jego sekcji krytycznej jest wykonywany proces (choć nie jest to wyraźnie określone, dotyczy to również sekcji leave), to oznacza to, że jakaś praca jest wykonywana. Więc robimy postępy. W przeciwnym razie, gdyby tak nie było...

I niektóre procesy chcą wejść do swoich sekcji krytycznych

Jeśli żaden proces nie chce wejść ich sekcje krytyczne, wtedy nie ma już pracy do wykonania. W przeciwnym razie, jeśli istnieje co najmniej jeden proces, który chce wejść do swojej sekcji krytycznej...

Wtedy tylko te procesy, które nie są wykonywane w pozostałej części

Oznacza to, że mówimy o tych procesach, które są wykonywane w jednej z dwóch pierwszych sekcji (pamiętaj, że żaden proces nie jest wykonywany w sekcji krytycznej ani w sekcji leave)...

Może uczestniczyć w podejmowaniu decyzji który następnie wejdzie do sekcji krytycznej,

Ponieważ jest co najmniej jeden proces, który chce wejść do jego CS, jakoś musimy wybrać jeden z nich, aby wejść do jego CS. Ale kto podejmie taką decyzję? Osoby, które już poprosiły o pozwolenie na wejście do swoich sekcji krytycznych, mają prawo uczestniczyć w podejmowaniu tej decyzji. Dodatkowo, te procesy, które mogą chcą wprowadzić swój CSs, ale nie zażądały jeszcze pozwolenia na to (oznacza to, że są w wykonaniu w pierwszej części) mają również prawo uczestniczyć w podejmowaniu tej decyzji.

I tego wyboru nie można odkładać na czas nieokreślony.

Oznacza to, że wybranie procesu, aby wprowadzić jego kod CS, zajmie ograniczoną ilość czasu. W szczególności nie nastąpi impas lub livelock. Więc po tym ograniczonym czasie, proces wejdzie do swojego CS i zrobi jakąś pracę, czyniąc postęp.

Teraz wyjaśnię ostatni warunek, a mianowicie ograniczone oczekiwanie . Celem tego warunku jest upewnienie się, że każdy proces ma szansę wejść do swojej sekcji krytycznej, tak aby żaden proces nie głodował na zawsze . Należy jednak pamiętać, że ani ten warunek, ani postęp nie gwarantują uczciwości. Implementacja CS nie musi być sprawiedliwa.

Bounded waiting: istnieje bound, lub limit, na liczbę czasy, kiedy inne procesy mogą wejść w ich krytyczne sekcje po złożeniu przez proces wniosku o wejście do jego sekcji krytycznej i zanim wniosek zostanie rozpatrzony.

Zrozummy tę definicję zdanie po zdaniu, zaczynając od ostatniego.

Po złożeniu przez proces prośby o wejście do jego sekcji krytycznej i zanim wniosek zostanie rozpatrzony.

Innymi słowy, jeśli istnieje proces, który zażądał wprowadzenia swojego pliku CS, ale jeszcze go nie wprowadził. Nazwijmy ten proces P.

Istnieje ograniczenie lub ograniczenie liczby czasy, w których inne procesy mogą wchodzić do swoich sekcji krytycznych

Podczas gdy P czeka na wejście do swojego CS, inne procesy mogą również czekać i niektóre procesy są wykonywane w jego CS. Gdy opuści swój CS, musi być wybrany inny proces, aby wejść do CS, który może lub nie musi być P. Załóżmy, że wybrano inny proces niż P. Ta sytuacja może się powtarzać. Oznacza to, że inne procesy mają szansę aby wprowadzić swój CSs, ale nigdy P. zauważ, że postęp jest dokonywany, ale przez inne procesy, a nie przez P. problem polega na tym, że P nie ma szansy wykonać żadnej pracy. Aby zapobiec głodowi, musi istnieć gwarancja, że P w końcu wejdzie do swojego CS. Aby tak się stało, liczba innych procesów wchodzących do ich CSs musi być ograniczona. W tym przypadku P na pewno będzie miał szansę wejść do swojego CS.

Chciałbym wspomnieć, że definicję CS można uogólnić tak, że w większość N procesów jest wykonywana w sekcjach krytycznych, gdzie N jest dowolną dodatnią liczbą całkowitą. Istnieją również warianty sekcji krytycznej czytelnik-pisarz.