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

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

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

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

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

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

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

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

 1 program DiningPhilosophers;
 2 const N = 5;
 3 
 4 var mutexfork : array[0..N-1] of semaphore;
 5     i : integer;
 6 
 7 procedure think; 
 8 begin
 9 //misli...
10 end;
11 
12 procedure eat;
13 begin
14 //jede...
15 end;
16 
17 procedure Philosopher(i : 0..N-1);
18 var first, second : 0..N-1;
19 begin
20     if (i mod 2 = 1) then begin
21         first := i; //prva viljuska koju ce uzeti
22         second := (i+1) mod N //druga viljuska koju ce uzeti
23     end
24     else begin
25         first := (i+1) mod N //prva viljuska koju ce uzeti
26         second := i //druga viljuska koji ce uzeti
27     end;
28     while (true) do begin
29         think;
30         wait(mutexfork[first]);
31         wait(mutexfork[second]);
32         eat;
33         signal(mutexfork[first]);
34         signal(mutexfork[second])
35     end
36 end;
37 
38 begin
39     for i := 0 to N-1 do init(mutexfork[i], 1);
40     cobegin
41         Philosopher(0);
42         //...
43         Philosopher(N-1);
44     coend
45 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). Конкурентно и дистрибуирано програмирање (друго издање). Академска мисао, Београд.

Спољашње везеУреди