6. SZEREGOWANIE PROCESÓW
Szeregowaniem wykonania procesów zajmuje się zarówno system operacyjny, jak i
programista.
System zarządza wszystkimi wykonywanymi procesami „na niskim poziomie”,
kierując się
jedynie priorytetami procesów i dostępnością zasobów, na które zgłaszają
zapotrzebowanie.
Programista zarządza uruchamianymi przez siebie procesami, korzystając z
mechanizmów
koordynacji dostępnych w używanym przez niego języku programowania.
Koordynacja jest
potrzebna w przypadku korzystania ze wspólnych zasobów. Jakie mogą być
oczekiwania wobec
kolejności udostępniania zasobów procesom ?
Uczciwość słaba
(weak fairness, justice)
Program nazywamy słabo uczciwym, jeżeli dla każdego jego wykonania i dla
każdego jego procesu
zachodzi: jeżeli proces od pewnego momentu nieprzerwanie zgłasza
zapotrzebowanie na pewien
zasób, to kiedyś będzie ono obsłużone.
W praktyce oznacza to, że w momencie zgłoszenia zapotrzebowania proces
zostaje zawieszony
i czeka na przydział zasobu. Czas oczekiwania może być dowolnie długi.
Uczciwość mocna
(strong fairness, compassion)
Program nazywamy mocno uczciwym, jeżeli dla każdego jego wykonania i
każdego procesu
zachodzi: jeżeli proces zgłasza zapotrzebowanie dostatecznie wiele razy, to
kiedyś będzie ono
obsłużone.
Oznacza to, że jeżeli proces wykonując się co pewien czas sprawdza, czy
potrzebny zasób jest już
dostępny, to po pewnym (dowolnie długim) czasie otrzyma przydział tego zasobu.
Oczekiwanie liniowe
Program ma własność oczekiwania liniowego, jeżeli dla każdego jego wykonania
i każdego procesu
zachodzi: jeżeli proces zgłosi zapotrzebowanie, to będzie ono obsłużone, zanim
dowolny inny proces
czekający na ten sam zasób będzie obsłużony więcej, niż raz.
Jest to własność o bardziej praktycznym charakterze, niż dwie poprzednie, gdyż
pozwala oszacować
(choćby tylko z grubsza) czas oczekiwania na przydział.
FIFO (kolejka prosta)
Program ma własność FIFO, jeżeli dla każdego jego wykonania i każdego
procesu zachodzi: jeżeli
proces zgłosi zapotrzebowanie, to będzie ono obsłużone przed każdym
zapotrzebowaniem zgłoszo-
nym później.
Ta definicja może odnosić się jedynie do programu wykonywanego w systemie
ściśle powiązanym,
gdyż tylko w tym przypadku ma sens pojęcie czasu bezwzględnego i
jednoczesności. W przypadku
systemu luźno powiązanego można korzystać co najwyżej z pojęcia oczekiwania
liniowego.
Korzystając z wyżej wprowadzonych pojęć, można teraz dokładniej określić
własności semaforów
związane z szeregowaniem uruchamiania oczekujących procesów:
Semafor ze zbiorem oczekujących jest to semafor, dla którego wybór
procesu do uruchomienia
spośród oczekujących procesów jest niedeterministyczny.
Semafor taki nazywamy też semaforem słabo uczciwym, gdyż jeżeli od
pewnego momentu stale ma
wartość dodatnią, to czas oczekiwania pod nim dla każdego procesu jest
skończony.
Semafor silnie uczciwy to semafor o własności: jeżeli operacja sygnalizuj
będzie wykonana na
semaforze nieskończenie wiele razy, to czas oczekiwania pod tym semaforem dla
każdego procesu
będzie skończony.
Semafor z kolejką oczekujących to semafor, który wstrzymywane procesy
wstawia do kolejki
prostej, a kolejne operacje sygnalizuj uruchamiają je w takiej kolejności, w jakiej
zostały wstrzymane.
Uwaga.
Każdy semafor z kolejką oczekujących jest silnie uczciwy, ale niekoniecznie na
odwrót.
Pojęcia semafora ze zbiorem oczekujących i z kolejką oczekujących są pojęciami
o charakterze
implementacyjnym, pojęcia semafora słabo uczciwego i silnie uczciwego są
pojęciami abstrakcyj-
nymi (odnoszą się do bardziej ogólnych własności).
7. KLASYCZNE PROBLEMY WSPÓŁBIEŻNOŚCI
Dwa klasyczne problemy zostały już przedstawione na poprzednim wykładzie:
problem wzajemnego
wykluczania
(mutual exclusion)
i problem producenta i konsumenta
(producer and consumer)
.
1) Problem wzajemnego wykluczania.
Przedstawione rozwiązanie zakładało istnienie implementacji semaforów w
systemie. Co więcej, dla
liczby procesów większej od 2, brak możliwości głodzenia procesów zależał od
uczciwości użytego
semafora. Obecnie przedstawimy rozwiązania nie korzystające z semaforów, a
jedynie zakładające
niepodzielność operacji podstawienia oraz operacji await.
a) Algorytm Dekkera
kto: 1..2 - zmienna wspólna do zapisu i odczytu, wskazuje, który proces ma
prawo nalegać na
wejście do sekcji krytycznej;
ki: 0..1 - zmienne wspólne do odczytu, ale prywatne do zapisu, ki = 0
wskazuje, że i - ty proces
zgłosił potrzebę wejścia do sekcji krytycznej.
{ k1 = 1, k2 = 1, kto = 1 }
while true do while true do
begin begin
niekrytyczna1;
niekrytyczna2;
k1 := 0; k2 := 0;
while k2 = 0 do
protokół
while k1
= 0 do
if kto = 2 then
wejściowy
if
kto = 1 then
begin
begin
k1 := 1;
k2 := 1;
P1: await (kto = 1); || P2 :
await (kto = 2);
k1 := 0
k2 := 0
end;
end;
krytyczna1;
krytyczna2;
k1 := 1;
protokół
k2 := 1;
kto := 2
wyjściowy
kto := 1
end end
P1
:
|| P2 :
niekrytyczna1
niekrytyczna2
krytyczna1
krytyczna
2
k1 := 0
k2 :=
0
k2 =
1 ?
k1 =
1 ?
k2 = 0
?
kto =
2 ?
k1 := 1
kto =
1 ?
k1 :=
1
kto :=
2
k1 := 0
kto = 1
?
k2 := 1
k1 =
0 ?
kto = 2 ?
kto =
1 ?
k2 := 1
kto =
2 ?
k2 := 0
kto := 1
b) Algorytm Petersona
yi : boolean - zmienne wspólne do czytania, prywatne do pisania, yi = true
oznacza, że
Pi zgłasza chęć wejścia do sekcji krytycznej;
t : boolean - zmienna wspólna do czytania i pisania („przełącznik
dwustanowy”).
{ y1 y2 t }
while true do while true do
begin begin
niekrytyczna1;
niekrytyczna2;
y1 := true; y2 := true;
P1: t := false; || P2 : t := true;
await ( y2 t );
protokół wejściowy
await ( y1
t );
krytyczna1; krytyczna2;
y1 := false
protokół wyjściowy
y2 := false
end end
Uwaga: testowanie podwójnego warunku powinno być operacją niepodzielną (np.
na bitach 1 bajtu) !
P1:
||
P2 :
niekrytyczna1
niekrytyczna2
y1 := true
y2 := true
t := false
t := true
y2 t ?
y1 t ?
krytyczna1
krytyczna2
y1 := false
y2 := false
Powyższe rozwiązania nie dają się w prosty sposób uogólnić dla liczby procesów
większej, niż 2.
Rozwiązania ogólne (nie korzystające z silnie uczciwych semaforów) istnieją, ale
są skomplikowane.
Algorytm „piekarniany” potrzebuje do koordynacji zmiennych przyjmujących
dowolnie duże wartości
naturalne i ma czasochłonny protokół wejściowy (nawet przy braku rywalizacji
procesów). Lepsze
rozwiązania - Peterson 1983, Lamport 1987.
2) Problem producenta i konsumenta
Na poprzednim wykładzie były przedstawione dwa rozwiązania: z buforem
cyklicznym i semaforami,
oraz z kanałem komunikacyjnym. Problem ten ma również wersję ogólniejszą:
wielu producentów
i wielu konsumentów korzysta ze wspólnego bufora.
3) Problem czytelników i pisarzy
Problem ten jest abstrakcją problemu dostępu do wielodostępnej bazy danych.
Każdy proces aktuali-
zujący dane (pisarz) musi mieć wyłączność dostępu do danych (czytelni), ale
procesy, które tylko
czytają (czytelnicy), mogą pracować jednocześnie.
Idea rozwiązania:
(gwarantującego niemożliwość głodzenia zarówno
czytelników, jak i pisarzy)
Przybywający pisarze ustawiani są w kolejkę prostą, przybywający czytelnicy
gromadzeni są
w zbiorze. Mechanizm koordynujący wpuszcza na przemian pojedynczych
pisarzy i cały zbiór
zgromadzonych czytelników. Wpuszczenie może mieć miejsce dopiero po
opuszczeniu czytelni
przez poprzednich użytkowników / użytkownika. Jeżeli kolejka oczekujących
pisarzy jest pusta,
a w czytelni przebywają czytelnicy, każdy nowo przybyły czytelnik jest od razu
wpuszczany.
Jeśli w zbiorze nie oczekują żadni czytelnicy, kolejno przybywający pisarze są
wpuszczani po
zakończeniu pobytu w czytelni przez poprzednika.
Najprostsze rozwiązanie - przy użyciu monitora.
kolejka pisarzy
zbiór
czytelników
czytelnia
4) Problem ucztujących filozofów
n =
5
Założenia:
a) każdy filozof może przebywać w dwóch stanach:
myślenie
i
jedzenie
;
b) każdy widelec jest zasobem współdzielonym przez dwóch sąsiadów na
zasadzie wyłączności
dostępu;
c) do jedzenia potrzebne są dwa widelce;
d) widelce muszą być brane sekwencyjnie (nie jednocześnie) przez jednego
filozofa;
e) czasy przebywania w stanach
myślenie
i
jedzenie
są zawsze skończone.
F
0
F1
F2
F3
F4
w1
w2
w3
w4
w0
Rozwiązanie symetryczne może doprowadzić do blokady (na przykład wszyscy
filozofowie mogą
jednocześnie podnieść lewe widelce). Rozwiązanie, które nie doprowadzi do
blokady ani do gło-
dzenia jednego z filozofów, musi „psuć” symetrię.
a) Rozwiązanie z ograniczaniem liczby „aktywnych” filozofów do n-1:
jadalnia: semafor = 4;
widelec: array [0..4] of semafor = 1;
while true do
{program i-tego filozofa}
begin
myślenie;
czekaj(jadalnia);
czekaj(widelec[i] );
czekaj(widelec[(i+1) mod 5] );
jedzenie;
sygnalizuj(widelec[i] );
sygnalizuj(widelec[(i+1) mod 5] );
sygnalizuj(jadalnia)
end
b) Rozwiązanie ze zróżnicowaniem programów filozofów:
i = 0, ..., 3 i = 4
widelec : array [0..4] of semafor = 1;
while true do while true do
begin begin
myślenie; myślenie;
czekaj(widelec[i] ); czekaj(widelec[0] );
czekaj(widelec[i+1] ); czekaj(widelec[4] );
jedzenie; jedzenie;
sygnalizuj(widelec[i] ); sygnalizuj(widelec[4] );
sygnalizuj(widelec[i+1] ) sygnalizuj(widelec[0] )
end end
Oba powyższe rozwiązania wykluczają zarówno możliwość blokady, jak i
indywidualnego głodzenia.