250px|мини|десно|Илустрација проблема филозофа за ручком. Приказани филозофи у смеру казаљке на сату су редом: Платон, Конфучије, Сократ, Волтер и Декарт.

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

Проблем је први формулисао Едсгер Дајкстра 1965. године, а убрзо након тога му је Тони Хор дао садашњу формулацију.

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

Пет филозофа (Платон, Конфучије, Сократ, Волтер и Декарт) седи око округлог стола. Сваки филозоф проводи свој живот тако што наизменично размишља и једе. На средини стола је велика посуда са шпагетима. Пошто су шпагети дугачки и испреплетани, а филозофи нису веома спретни, морају да користе две виљушке када једу. Нажалост, постоји само пет виљушака, између свака два суседна филозофа по једна. Филозофи могу да дохвате само виљушку која је непосредно лево и непосредно десно од њих.

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

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

program DiningPhilosophers; const N = 5;

var mutexfork : array[0..N-1] of semaphore; i : integer;

procedure think; begin //misli... end;

procedure eat; begin //jede... end;

procedure Philosopher(i : 0..N-1); var first, second : 0..N-1; begin if (i mod 2 = 1) then begin first := i; //prva viljuska koju ce uzeti second := (i+1) mod N //druga viljuska koju ce uzeti end else begin first := (i+1) mod N //prva viljuska koju ce uzeti second := i //druga viljuska koji ce uzeti end; while (true) do begin think; wait(mutexfork[first]); wait(mutexfork[second]); eat; signal(mutexfork[first]); signal(mutexfork[second]) end end;

begin for i := 0 to N-1 do init(mutexfork[i], 1); cobegin Philosopher(0); //... Philosopher(N-1); coend end.

Поред овог постоје и бројне друге варијације решења. Једно од често коришћених је решење код ког се мртво блокирање спречава увођењем ограничења на број процеса који могу да приступају ресурсима (виљушкама). По том решењу максимално четири филозофа могу да затраже виљушке у исто време.

Види још

Проблем читалаца и писаца Проблем нервозних пушача Проблем произвођача и потрошача Едсгер Дајкстра Тони Хор Паралелно израчунавање

Референце

Литература

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

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

Дискусија проблема са кодом за 2 или 4 филозофа , , , Дистрибуирано симетрично решење, Програмирање филозофа на вечери са решењем, Интерактивни пример проблема са филозофима, (Java неопходна) Ђаво долази на вечеру, Зашто не кокошке? – Варијанта са изгладњивањем једног филозофа, Ментор нити, Решење проблема филозофа на вечери са асинхроним агентом, Решење са глумцима,

Категорија:Информатика