Проблем нервозних пушача

У информатици, проблем нервозних пушача је пример проблема у области конкурентног програмирања. Први га је описао индијско-амерички академик Сухас Патил, 1971. године. Патил је искористио доказ из Петријеве мреже и утврдио да решење које користи семафоре Едсгера Дајкстре није могуће, те да је неопходна сложенија примитива за синхронизацију.

Опис проблема

У систему постоји један агент и три нервозна пушача. Агент поседује три неопходна предмета за лечење нервозе: папир, дуван и шибице. Један од пушача има бесконачне залихе папира, други дувана, а трећи шибица. Агент почиње тако што два различита предмета ставља на сто, један по један. Пушач, коме баш та два предмета недостају, узима их, завија и пали цигарету и ужива. Након тога обавештава агента да је завршио, а агент онда ставља два нова предмета на сто, итд.

Пример решења

Пример решења применом условних критичних региона у конкурентном Паскалу:

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.

Функција rand(2) генерише случајни број у опсегу од 0 до 2.

Конкурентност овог решења би се могла повећати уколико би се дозволило да се формирање новог скупа артикала обавља упоредно са коришћењем артикала из претходне итерације. У том случају би се променио једино код за агенте.

Види још

• Проблем читалаца и писаца
• Проблем филозофа за ручком
• Проблем произвођача и потрошача
• Паралелно израчунавање

Литература

• Радивојевић, Захарије; Икодиновић, Игор; Јовановић, Зоран (2018). Конкурентно и дистрибуирано програмирање (друго издање). Академска мисао, Београд.

Спољашње везе

• Проблем нервозних пушача и ограничења семафора, (језик: енглески)
• Ментор нити, (језик: енглески)