Aterioivat filosofit

Aterioivat filosofit on Edsger Dijkstran ajatuksen pohjalta Tony Hoaren esittämä, tietojenkäsittelyyn liittyvä rinnakkaisuusongelma vuodelta 1965. Ongelma on seuraava:

Viisi filosofia istuu pyöreän pöydän ympärillä. Filosofit joko ajattelevat tai syövät – tarkemmin ilmaistuna ajattelevat, tulevat nälkäisiksi, syövät ja aloittavat taas ajattelun. Jokaisella filosofilla on edessään lautasellinen spagettia (joka ei koskaan lopu), ja lautasten väliin on asetettu yksi haarukka. Kukin filosofi tarvitsee kaksi haarukkaa syödäkseen, joten rinnakkain istuvat filosofit eivät voi syödä yhtä aikaa. Kun filosofi tulee nälkäiseksi, hän yrittää saada itselleen lautasen kummallakin puolella olevan haarukan. Jos haarukoiden saanti onnistuu, hän syö, laittaa haarukat takaisin pöydälle ja jatkaa miettimistään.

Tavoitteena on luoda algoritmi, jonka avulla filosofit pääsevät ajattelun lomassa syömään. Filosofit eivät saa keskustella keskenään, vaan kukin filosofi tekee itsenäisesti päätöksen haarukoiden käyttämisestä ja syömisestä vain oman tilansa ja lautasensa vieressä olevien haarukoiden perusteella.

Ongelmana on se, että ratkaisu voi nälkiintyä (engl. starvation, suomennettu myös ”nääntyminen”) tai lukkiutua (engl. deadlock).

Lukkiutuminen on tilanne, jossa kukaan ei pääse syömään koskaan. Näin voi tapahtua, jos algoritmin mukaan filosofi nostaa ensin oikean haarukan ja sitten vasemman haarukan. Jos kaikki filosofit tulevat nälkäisiksi yhtä aikaa, kukin heistä saa nostettua oikean haarukan käteensä, mutta kukaan ei saa vasenta haarukkaa. Niinpä kukaan ei pääse syömään, ja järjestelmä lukkiutuu.

Nälkiintyminen on tilanne, jossa filosofi joutuu odottamaan syömistään kohtuuttoman kauan. Tätä ei voi tapahtua, jos algoritmi on edellisessä kappaleessa kuvattu ”nosta ensin oikea haarukka ja sitten vasen”. Mutta jos lukkiutuminen on haluttu estää muuttamalla algoritmia siten, että tilanteessa, jossa filosofi ei saa vasenta haarukkaa, hän laskee oikean haarukan alas joksikin aikaa ja yrittää uudelleen hetken päästä, voi nälkiintyminen tapahtua. Olettakaamme, että filosofit 1, 2 ja 3 istuvat rinnakkain vasemmalta oikealle (oletamme, että filosofien 4 ja 5 toiminta ei olennaisesti vaikuta kokonaisuuteen). Filosofi 1 syö. Filosofi 2 tulee nälkäiseksi, ja saa nostettua oikean haarukan, mutta ei vasenta. Hän siis laskee oikean haarukan hetkeksi alas. Nyt kuitenkin filosofi 3 aloittaa syömisen, ja kun filosofi 2 yrittää uudelleen, hän ei saa edes oikeaa haarukkaa haltuunsa. Filosofi 1 lopettaa syömisen ja aloittaa ajattelemisen. Tällä välin filosofi 3 natustelee ruokaansa niin kauan, että filosofi 1 tulee nälkäiseksi jälleen ja aloittaa syömisen. Filosofi 3 siirtyy ajattelemaan, mutta aloittaa syömisen jälleen ennen, kuin filosofi 1 lopettaa syömisen. Jos näin jatkuu pitkään, filosofi 2 ei pääse syömään ja sananmukaisesti nälkiintyy.