W pewnym biurze grupa urzędników obsługuje grupę klientów. Każdy urzędnik ma unikatowy identyfikator z zakresu od 1 do N. Algorytmy urzędników i klientów są następujące.
process Urzednik(ranga: 1..2, id: integer)
begin
while (true) do
Biuro.chce_pracowac(ranga, id);
rozmawiam_z_klientem;
Biuro.skonczylem();
odpoczywam;
done;
end;
process Klient
var ...;
begin
while (true) do
Biuro.chce_zalatwic_sprawe(...);
rozmawiam;
Biuro.zalatwilem(...);
wlasne_sprawy;
done;
end;
W biurze pracuje co najmniej jeden urzędnik wyższej rangi lub co najmniej dwóch urzędników niższej rangi.
Na wyposażenie biura składa się K (K>2) krzeseł, z których korzystają urzędnicy i klienci podczas rozmowy.
Do rozmowy dochodzi, jeżeli jest zainteresowany klient i chętny do pracy urzędnik wyższej rangi lub dwóch urzędników niższej rangi oraz wystaraczająca liczba krzeseł (każda osoba zajmuje jedno krzesło).
Urzędnicy w ramach każdej z grup pracują według kolejności zgłaszania się do pracy.
Klienci muszą dowiedzieć się z jakimi urzędnikami mają rozmawiać (muszą poznać ich identyfikatory)
Po skończonej rozmowie urzędnicy i klienci mogą zwalniać krzesła pojedynczo.
Biuro powinno pracować w ten sposób, aby obsłużyć jak największą liczbę klientów i jest to priorytetem w tym zadaniu.
Rozwiązanie:
monitor Biuro;
const
LICZBA_KRZESEL := ...;
var
id_1: integer := 0;
id_2: integer := 0;
ilu_urzednikow_2: integer;
urzednicy_1,urzednicy_2,klienci: condition;
ile_krzesel: integer := LICZBA_KRZESEL;
export procedure chce_pracowac(p_id: integer)
begin
if (ranga=1) then
begin
if (ile_krzesel<2 or empty(klienci))
wait(urzednicy_1);
ile_krzesel := ile_krzesel - 2;
id_1:=p_id;
id_2:=0;
signal(klienci);
end
else {: ranga=2 :}
begin
if (ile_krzesel<3 or empty(klienci) or ilu_urzednikow_2=0) then
begin
inc(ilu_urzednikow_2);
wait(urzednicy_2);
dec(ilu_urzednikow_2);
end;
if (id_1=0) then
begin
ile_krzesel := ile_krzesel - 3;
id_1 := id;
signal(urzednicy_2);
end;
else
begin
id_2 := id;
signal(klienci);
end;
end;
end;
export procedure chce_zalatwic_sprawe(var p_u_id1: integer; var p_u_id2: integer)
begin
if (ile_krzesel<2 or empty(urzednicy_1)) and (ile_krzesel<3 or ilu_urzednikow_2<2) then
begin
wait(klienci);
end;
else
begin
if (not empty(urzednicy_1) and ile_krzesel>=2) signal(urzednicy_1);
else signal(urzednicy_2);
end;
p_u_id1 := id_1;
p_u_id2 := id_2;
id_1 := 0;
id_2 := 0;
end;
export procedure skonczylem()
begin
inc(ile_krzesel);
if (not empty(urzednicy_1) and not empty(klienci) and ile_krzesel>=2) signal(urzednicy_1);
else if (ilu_urzednikow_2>=2 and not empty(klienci) and ile_krzesel>=3) signal(urzednicy_2);
end;
export procedure zalatwilem()
begin
skonczylem();
end;
Warto zastanowić się także nad rozwiązaniem tego problemu w przypadku gdy klient jest obarczony odpowiedzialnością zwolnienia wszystkich krzeseł.
export procedure skonczylem()
begin
end;
export procedure zalatwilem(var p_u_id1: integer; var p_u_id2: integer)
begin
ile_krzesel := ile_krzesel+2;
if (p_u_id2<>0) then ile_krzesel := ile_krzesel+1;
while (true)
begin
if (not empty(urzednicy_1) and not empty(klienci) and ile_krzesel>=2) signal(urzednicy_1);
else if (ilu_urzednikow_2>=2 and not empty(klienci) and ile_krzesel>=3) signal(urzednicy_2);
else break;
end;
end;
W tym przypadku może się zdarzyć, że zostanie wznowiona więcej niż jedna grupa, dlatego musimy dodać pętlę. Zachodzi pytanie, czy ta pętla musi się skończyć wykonywać. Odpowiedź jest tak, gdyż po obudzeniu przez klienta wykonującego pętlę nowa grupa rezerwuje krzesła. W związku z tym liczba_krzesel zmniejsza się i liczba procesów oczekujących zmniejsza się. W konsekwencji pętla się skończy (warunki staną się fałszywe). Zwiększyć liczbę krzeseł i zwiększyć liczbę procesów w kolejkach może tylko proces przychodząc do monitora z zewnątrz. Jednak żaden proces nie może wejść do monitora z zewnątrz, dopóki klient zwalniający (wykonujący pętlę) nie zakończy procedury (gdyż ten klient wykonuje tylko signal, a nie wykonuje wait). Na podstawie tych dwóch obserwacji można wnioskować że pętla się zakończy.