У информатици, проблем нервозних пушача је пример проблема у области конкурентног програмирања. Први га је описао индијско-амерички академик Сухас Патил, 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). Конкурентно и дистрибуирано програмирање (друго издање). Академска мисао, Београд.
Спољашње везе Проблем нервозних пушача и ограничења семафора, Ментор нити,
Категорија:Информатика