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.