Table of Contents
Łącze internetowe jest dzielone między wielu użytkowników. Szerokość pasma wynosi N. Użytkownik chcąc korzystać z łącza, rezerwuje potrzebną szerokość (potrzebna_szerokosc>0 i potrzebna_szerokosc<=N) pasma. Użytkonik zwalnia zarezerwowaną szerokość pasma, gdy skończy z niego korzystać. Zsynchronizuj użytkowników, aby mogli korzystać z połączenia zgodnie ze swoimi potrzebami.
const
N = ...;
LICZBA_UZYTKOWNIKOW = ...;
procedure rezerwacja_pasma(szerokosc_dla_uzytkownika: integer)
begin
...
end;
procedure zwalnianie_pasma(szerokosc_dla_uzytkownika: integer)
begin
...
end;
process Uzytkownik(i: integer)
var
szerokosc_dla_uzytkownika: integer;
begin
while (true) do
begin
wlasne_sprawy();
szerokosc_dla_uzytkownika := losuj(1, N);
rezerwacja_pasma(szerokosc_dla_uzytkownika);
korzystanie_z_lacza();
zwalnianie_pasma(szerokosc_dla_uzytkownika);
end;
end;
var
i: integer;
begin
cobegin for i:=1 to LICZBA_UZYTKOWNIKOW do begin Uzytkownik(i); end; coend;
end;
Do rozwiązania tego problemy można wykorzystać metodę Pojedynczego Przetwarzania Żądań. Przetwarzanie żadania rezerwacji opakowujemy semaforem binarnym, w ten sposób przetwarzamy pojedynczo żądania.
var
szerokosc_niezarezerwowana: integer := N;
szerokosc_potrzebna: integer := -1;
rozpatrywanie_rezerwacji_pojedynczo: binary semaphore := 1;
czekajacy_uzytkownik: binary semaphore := 0;
ochrona: binary semaphore := 1;
procedure rezerwacja_pasma(szerokosc_dla_uzytkownika: integer)
begin
P(rozpatrywanie_rezerwacji_pojedynczo);
P(ochrona);
if (szerokosc_dla_uzytkownika<szerokosc_niezarezerwowana) then
begin
szerokosc_potrzebna := szerokosc_dla_uzytkownika;
V(ochrona);
P(czekajacy_uzytkownik);
P(ochrona);
end;
szerokosc_niezarezerwowana := szerokosc_niezarezerwowana - szerokosc_dla_uzytkownika;
V(ochrona);
V(rozpatrywanie_rezerwacji_pojedynczo);
end;
procedure zwalnianie_pasma(szerokosc_dla_uzytkownika: integer)
begin
P(ochrona);
szerokosc_niezarezerwowana := szerokosc_niezarezerwowana + szerokosc_dla_uzytkownika;
if (szerokosc_potrzebna<>-1 and szerokosc_niezarezerwowana>=szerokosc_potrzebna) then
begin
szerokosc_potrzebna:=-1;
V(czekajacy_uzytkownik);
end;
V(ochrona);
end;
Warto zwrócić także uwagę na błędną implementację, w której błąd jest bardzo subtelny.
var
szerokosc_niezarezerwowana: integer := N;
szerokosc_potrzebna: integer := -1;
rozpatrywanie_rezerwacji_pojedynczo: binary semaphore := 1;
czekajacy_uzytkownik: binary semaphore := 0;
ochrona: binary semaphore := 1;
procedure rezerwacja_pasma(szerokosc_dla_uzytkownika: integer)
begin
P(rozpatrywanie_rezerwacji_pojedynczo);
P(ochrona);
if (szerokosc_dla_uzytkownika<szerokosc_niezarezerwowana) then
begin
szerokosc_potrzebna := szerokosc_dla_uzytkownika;
V(ochrona);
P(czekajacy_uzytkownik);
P(ochrona);
szerokosc_potrzebna:=-1;{dodana instrukcja}
end;
szerokosc_niezarezerwowana := szerokosc_niezarezerwowana - szerokosc_dla_uzytkownika;
V(ochrona);
V(rozpatrywanie_rezerwacji_pojedynczo);
end;
procedure zwalnianie_pasma(szerokosc_dla_uzytkownika: integer)
begin
P(ochrona);
szerokosc_niezarezerwowana := szerokosc_niezarezerwowana + szerokosc_dla_uzytkownika;
if (szerokosc_potrzebna<>-1 and szerokosc_niezarezerwowana>=szerokosc_potrzebna) then
begin
{usunieta instrukcja szerokosc_potrzebna:=-1}
V(czekajacy_uzytkownik);
end;
V(ochrona);
end;
W tej implementacji semafor czekajacy_uzytkownik może zostać podniesiony dwa (a nawet więcej) razy. Dzieje się tak dlatego, że proces, który budzi proces czekający na semaforze czekajacy_uzytkownik powinien zapewnić, że inny proces zwracający pasmo nie będzie już drugi raz podnosił semafora czekajacy_uzytkownik, a tego nie robi. W rozwiązaniu poprawnym jest to zapewnione gdyż proces, który jako pierwszy budzi proces czekający na semaforze czekajacy_uzytkownik ustawia szerokosc_potrzebna na -1 i tym samym powoduje, że nikt inny nie będzie budził czekającego na semaforze czekajacy_uzytkownik procesu.
Problem obecny w niepoprawnym rozwiązaniu, może być naprawiony także w inny sposób. Można do tego wykorzystać technikę nazywaną Przekazywanie (Dziedziczenie) Sekcji Krytycznej. W tym przypadku będzie to polegało na zagwarantowaniu, że po procesie budzącym będzie się wykonywał proces budzony (typ samym zapewniamy że przed procesem budzonym nie będzie się wykonywał żeaden proces zwalniający szerokość pasma).
var
szerokosc_niezarezerwowana: integer := N;
szerokosc_potrzebna: integer := -1;
rozpatrywanie_rezerwacji_pojedynczo: binary semaphore := 1;
czekajacy_uzytkownik: binary semaphore := 0;
ochrona: binary semaphore := 1;
procedure rezerwacja_pasma(szerokosc_dla_uzytkownika: integer)
begin
P(rozpatrywanie_rezerwacji_pojedynczo);
P(ochrona);
if (szerokosc_dla_uzytkownika<szerokosc_niezarezerwowana) then
begin
szerokosc_potrzebna := szerokosc_dla_uzytkownika;
V(ochrona);
P(czekajacy_uzytkownik);
{korzystanie z przekazanej ochrona}
szerokosc_potrzebna:=-1;
end;
szerokosc_niezarezerwowana := szerokosc_niezarezerwowana - szerokosc_dla_uzytkownika;
V(ochrona);
V(rozpatrywanie_rezerwacji_pojedynczo);
end;
procedure zwalnianie_pasma(szerokosc_dla_uzytkownika: integer)
begin
P(ochrona);
szerokosc_niezarezerwowana := szerokosc_niezarezerwowana + szerokosc_dla_uzytkownika;
if (szerokosc_potrzebna<>-1 and szerokosc_niezarezerwowana>=szerokosc_potrzebna) then
V(czekajacy_uzytkownik); {przekazywanie ochrony}
else
V(ochrona);
end;