Пређи на садржај

Проблем филозофа за ручком

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

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

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

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

[уреди | уреди извор]

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

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

[уреди | уреди извор]

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

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.

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

Види још

[уреди | уреди извор]

Референце

[уреди | уреди извор]
  1. ^ Dijkstra, Edsger W. EWD-1000. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  2. ^ J. Díaz; I. Ramos (1981). Formalization of Programming Concepts: International Colloquium, Peniscola, Spain, April 19–25, 1981. Proceedings. Birkhäuser. стр. 323 , 326. ISBN 978-3-540-10699-9. 
  3. ^ Hoare, C. A. R. (2004) [originally published in 1985 by Prentice Hall International]. „Communicating Sequential Processes” (PDF). usingcsp.com. 
  4. ^ Радивојевић, Захарије; Икодиновић, Игор; Јовановић, Зоран (2018). Конкурентно и дистрибуирано програмирање (друго издање). Академска мисао. стр. 30. 
  5. ^ Радивојевић, Захарије; Икодиновић, Игор; Јовановић, Зоран (2018). Конкурентно и дистрибуирано програмирање (друго издање). Академска мисао. стр. 34. 
  6. ^ Радивојевић, Захарије; Икодиновић, Игор; Јовановић, Зоран (2018). Конкурентно и дистрибуирано програмирање (друго издање). Академска мисао. стр. 35. 

Литература

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

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

[уреди | уреди извор]
Преузето из „https://sr.wikipedia.org/w/index.php?title=Проблем_филозофа_за_ручком&oldid=26983110”