Problem nervoznih pušača
U informatici, problem nervoznih pušača je primer problema u oblasti konkurentnog programiranja. Prvi ga je opisao indijsko-američki akademik Suhas Patil, 1971. godine. Patil je iskoristio dokaz iz Petrijeve mreže i utvrdio da rešenje koje koristi semafore Edsgera Dajkstre nije moguće, te da je neophodna složenija primitiva za sinhronizaciju.[1]
Opis problema
[uredi | uredi izvor]U sistemu postoji jedan agent i tri nervozna pušača. Agent poseduje tri neophodna predmeta za lečenje nervoze: papir, duvan i šibice. Jedan od pušača ima beskonačne zalihe papira, drugi duvana, a treći šibica. Agent počinje tako što dva različita predmeta stavlja na sto, jedan po jedan. Pušač, kome baš ta dva predmeta nedostaju, uzima ih, zavija i pali cigaretu i uživa. Nakon toga obaveštava agenta da je završio, a agent onda stavlja dva nova predmeta na sto, itd.[2]
Primer rešenja
[uredi | uredi izvor]Primer rešenja primenom uslovnih kritičnih regiona u konkurentnom Paskalu:[3]
program CigaretteSmokers;
type table = record
paper, tobacco, matches : boolean;
ok : boolean;
end;
var p : shared table;
procedure Agent;
var n : integer;
begin
while (true) do begin
n := random(2); //slucajni broj
region p do begin
case n of
0: begin
p.paper := false;
p.tobacco := true;
p.matches := true;
end;
1: begin
p.paper := true;
p.tobacco := false;
p.matches := true;
end;
2: begin
p.paper := true;
p.tobacco := false;
p.matches := false;
end;
else ;
end;
await(p.ok);
p.ok := false;
end;
end;
end;
procedure SmokerWithMatches;
begin
while (true) do begin
region p do begin
await(p.paper and p.tobacco);
p.paper := false;
p.tobacco := false;
end;
enjoy;
region p do
p.ok := true;
end;
end;
procedure SmokerWithTobacco;
begin
while (true) do begin
region p do begin
await(p.paper and p.matches);
p.paper := false;
p.matches := false;
end;
enjoy;
region p do
p.ok := true;
end;
end;
procedure SmokerWithPaper;
begin
while (true) do begin
region p do begin
await(p.tobacco and p.matches);
p.matches := false;
p.tobacco := false;
end;
enjoy;
region p do
p.ok := true;
end;
end;
begin
p.paper := false;
p.tobacco := false;
p.matches := false;
p.ok :- false;
cobegin
Agent;
SmokerWithPaper;
SmokerWithTobacco;
SmokerWithMatches;
coend;
end.
Funkcija rand(2) generiše slučajni broj u opsegu od 0 do 2.
Konkurentnost ovog rešenja bi se mogla povećati ukoliko bi se dozvolilo da se formiranje novog skupa artikala obavlja uporedno sa korišćenjem artikala iz prethodne iteracije. U tom slučaju bi se promenio jedino kod za agente.[4]
Vidi još
[uredi | uredi izvor]- Problem čitalaca i pisaca
- Problem filozofa za ručkom
- Problem proizvođača i potrošača
- Paralelno izračunavanje
Reference
[uredi | uredi izvor]- ^ Patil, Suhas S. (februar 1971). Limitations and Capabilities of Dijkstra's Semaphore Primitives for Coordination among Processes (Tehnički izveštaj). MIT, Project MAC, Computation Structures Group. Memo 57.
- ^ Radivojević, Zaharije; Ikodinović, Igor; Jovanović, Zoran (2018). Konkurentno i distribuirano programiranje (drugo izdanje). Akademska misao. str. 130.
- ^ Radivojević, Zaharije; Ikodinović, Igor; Jovanović, Zoran (2018). Konkurentno i distribuirano programiranje (drugo izdanje). Akademska misao. str. 131-133.
- ^ Radivojević, Zaharije; Ikodinović, Igor; Jovanović, Zoran (2018). Konkurentno i distribuirano programiranje (drugo izdanje). Akademska misao. str. 133, 134.
Literatura
[uredi | uredi izvor]- Radivojević, Zaharije; Ikodinović, Igor; Jovanović, Zoran (2018). Konkurentno i distribuirano programiranje (drugo izdanje). Akademska misao, Beograd.
Spoljašnje veze
[uredi | uredi izvor]- Problem nervoznih pušača i ograničenja semafora, (jezik: engleski)
- Mentor niti, (jezik: engleski)