Problem filozofa za ručkom

U informatici, problem filozofa za ručkom je veoma često korišćen primer problema u oblasti konkurentnog programiranja. Osmišljen je tako da ilustruje probleme sinhronizacije i tehnike za njihovo rešavanje.

Ilustracija problema filozofa za ručkom. Prikazani filozofi u smeru kazaljke na satu su redom: Platon, Konfučije, Sokrat, Volter i Dekart.

Problem je prvi formulisao Edsger Dajkstra 1965. godine, a ubrzo nakon toga mu je Toni Hor dao sadašnju formulaciju.

Opis problema

Pet filozofa (Platon, Konfučije, Sokrat, Volter i Dekart) sedi oko okruglog stola. Svaki filozof provodi svoj život tako što naizmenično razmišlja i jede. Na sredini stola je velika posuda sa špagetima. Pošto su špageti dugački i isprepletani, a filozofi nisu veoma spretni, moraju da koriste dve viljuške kada jedu. Nažalost, postoji samo pet viljušaka, između svaka dva susedna filozofa po jedna. Filozofi mogu da dohvate samo viljušku koja je neposredno levo i neposredno desno od njih.

Primer rešenja

Primer rešenja primenom semafora u konkurentnom Paskalu, kod koga je mrtvo blokiranje izbegnuto idejom da procesi ne izvršavaju kritične sinhronizacione operacije istim redosledom, odnosno da svaki filozof kada želi da jede uzima prvo neparnu viljušku:

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.

Pored ovog postoje i brojne druge varijacije rešenja. Jedno od često korišćenih je rešenje kod kog se mrtvo blokiranje sprečava uvođenjem ograničenja na broj procesa koji mogu da pristupaju resursima (viljuškama). Po tom rešenju maksimalno četiri filozofa mogu da zatraže viljuške u isto vreme.

Vidi još

• Problem čitalaca i pisaca
• Problem nervoznih pušača
• Problem proizvođača i potrošača
• Edsger Dajkstra
• Toni Hor
• Paralelno izračunavanje

Literatura

• Radivojević, Zaharije; Ikodinović, Igor; Jovanović, Zoran (2018). Konkurentno i distribuirano programiranje (drugo izdanje). Akademska misao, Beograd.

Spoljašnje veze

• Diskusija problema sa kodom za 2 ili 4 filozofa Arhivirano na sajtu Wayback Machine (20. jul 2011), (jezik: engleski)
• Diskusija različitih solucija na sajtu Wayback Machine (arhivirano decembar 8, 2013), (jezik: engleski)
• Diskusija rešenja sa CB nitima na sajtu Wayback Machine (arhivirano mart 4, 2012), (jezik: engleski)
• Distribuirano simetrično rešenje, (jezik: engleski)
• Programiranje filozofa na večeri sa rešenjem, (jezik: engleski)
• Interaktivni primer problema sa filozofima, (jezik: engleski)(Java neophodna)
• Đavo dolazi na večeru, (jezik: engleski)
• Zašto ne kokoške? – Varijanta sa izgladnjivanjem jednog filozofa, (jezik: engleski)
• Mentor niti, (jezik: engleski)
• Rešenje problema filozofa na večeri sa asinhronim agentom, (jezik: engleski)
• Rešenje sa glumcima, (jezik: engleski)