Co To Jest Sekcja Krytyczna I Jak W Praktyce Jest Realizowana Jej Obsluga

Sekcja krytyczna - w programowaniu współbieżnym fragment kodu programu, który w danej chwili powinien być wykonywany przez nie więcej niż jeden wątek. Brak wzajemnego wykluczania się wykonywania sekcji krytycznych może spowodować błędy wykonania, np. dwukrotne zapisanie danej albo niepoprawna modyfikacja.

Rozpatrzmy dwa procesy zliczające liczbę wystąpień tego samego elementu:

Kod x = x + 1 rozkłada się na prostsze elementy:
1. wczytaj zmienną X
2. zwiększ zmienną X
3. zapisz zmienną X

W komputerze działają dwa takie procesy i zliczają wystąpienia:
1. początkowa wartość x = 1
2. proces 1 wykonuje instrukcję 1
3. system operacyjny przerywa działanie procesu 1 i przekazuje sterowanie do procesu 2,
4. proces 2 wykonuje wszystkie instrukcje i ustawia x na 2,
5. system przełącza działanie na proces 1
6. proces 1 zwiększa pobraną w pierwszym punkcie wartość o 1, czyli do 2, i wykonuje instrukcję 3
zapisując wartość 2.

Przy rozdzielnym działaniu programów wartość x powinna równać się 3 a nie 2.

Sekcje krytyczne realizuje się np. z wykorzystaniem muteksów lub semaforów.

Mutex (ang. Mutual Exclusion, wzajemne wykluczanie) to element stosowany w programowaniu służący do kontroli dostępu do zasobów niemożliwych do współdzielenia, inaczej mówiąc do realizowania sekcji krytycznych.

Implementacja muteksu musi spełniać następujące warunki:
Nie doprowadzanie do blokady - gdy kilka procesów wyraża chęć wejścia do sekcji krytycznej, jeden z nich musi w końcu wejść.
Nie może prowadzić do zagłodzenia - jeśli pewien proces wyraża chęć wejścia do sekcji krytycznej, to musi być w końcu dopuszczony. Jest to tak zwana uczciwość. Wyróżnia się:
uczciwość słabą, jeśli proces ciągle zgłasza żądanie, to w końcu zostanie dopuszczony do sekcji krytycznej.
uczciwość mocną, gdy proces zgłasza żądanie nieskończenie wiele razy, to zostanie w końcu dopuszczony do sekcji krytycznej
oczekiwanie liniowe, jeśli proces zgłasza żądanie, będzie dopuszczony do sekcji krytycznej nie później niż po tym jak każdy inny proces zostanie obsłużony jeden raz.
FIFO, tak jak w przypadku kolejki FIFO (pierwszy wszedł, pierwszy wyjdzie), procesy zostaną obsłużone w kolejności zgłoszenia żądań.
Nie może prowadzić do blokady w przypadku braku współzawodnictwa. Gdy tylko jeden proces wyraża chęć wejścia do sekcji krytycznej, powinien zostać dopuszczony.

Jednym ze sposobów na zastosowanie wzajemnego wykluczania jest uniemożliwienie występowania przerwań podczas wykonywania krytycznych fragmentów kodu. Jednak takie rozwiązanie sprawdza się w przypadku systemów jednoprocesorowych. Przy większej ilości procesorów implementuje się pętlę sprawdzającą wartość zmiennej (tzw. flagi) wskazującej na możliwość dostępu do sekcji krytycznej.

Wśród rozwiązań programistycznych istnieje wiele algorytmów, między innymi Algorytm Dekkera, Algorytm Petersona czy też algorytmy oparte na semaforach, lecz są one zazwyczaj niedoskonałe (doprowadzają do blokady, głodzenia lub wykorzystują znaczną ilość zasobów).

Semafor to jeden ze sposobów komunikacji międzyprocesowej. Semafory zostały po raz pierwszy opisane przez Edsgera Dijkstrę jako istotne rozwinięcie algorytmu Dekkera.

Typowy semafor implementowany jest jako zmienna typu całkowitego. Semafory dzieli się na binarne i zliczające. Semafor binarny może przyjmować wartości całkowite ze zbioru {0;1}, zliczający - również większe niż 1. Modyfikacja wartości semafora jest możliwa za pomocą trzech operacji: "init", "wait" ("P") oraz "signal" ("V"). Dwie ostatnie muszą być realizowane nieprzerwanie - "atomowo", aby uniknąć jednoczesnego sprawdzenia i modyfikacji przez więcej niż jedno zadanie.
P(Semafor s)
{
oczekuj s > 0, wówczas s := s-1; /* operacja atomowa */
}

V(Semafor s)
{
s := s+1; /* operacja atomowa */
}

Init(Semafor s, Całkowitoliczbowe v)
{
s := v;
}

Litery P i V zwykle są kojarzone ze słowami holenderskimi: passeren (przejść), proberen (próbować), vryjgeven (zwolnić), verhoog (zwiększać). Jednakże sam Dijkstra użycie liter P i V wyjaśniał nieco inaczej [1].

Najczęstszym zastosowaniem jest synchronizacja dostępu do zasobów systemowych współdzielonych przez kilka zadań, aby zapobiec problemom wynikającym z prób jednoczesnego dostępu i modyfikacji danego zasobu.

Semafory są zwykle implementowane w obszarze jądra systemu operacyjnego. Pozwala to na zaawansowaną obsługę zadań chcących uzyskać dostęp do zasobu:
wstrzymywanie ich do czasu zwolnienia semafora powiązanego z danym zasobem,
wznowienie pracy zadania oczekującego na semaforze,
utrzymywania semafora nawet po zakończeniu zadania, który go utworzyło.

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License