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.

Opis problema

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.

Primer rešenja

Primer rešenja primenom uslovnih kritičnih regiona u konkurentnom Paskalu:

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.

Vidi još

• Problem čitalaca i pisaca
• Problem filozofa za ručkom
• Problem proizvođača i potrošača
• Paralelno izračunavanje

Literatura

• Radivojević, Zaharije; Ikodinović, Igor; Jovanović, Zoran (2018). Konkurentno i distribuirano programiranje (drugo izdanje). Akademska misao, Beograd.

Spoljašnje veze

• Problem nervoznih pušača i ograničenja semafora, (jezik: engleski)
• Mentor niti, (jezik: engleski)