Einestavad filosoofid

Einestavad filosoofid on informaatikas klassikaline mudel probleemist, mis käsitleb mitmelõimeliste protsesside sünkroonimist. Tänapäeval on lisatud selle probleemi käsitlemine enamiku informaatikakõrgkoolide ainekavva.

Ajalugu

1971. aastal kasutas Edsger Dijkstra sünkroonimise probleemi küsimust, kus viiele magnetlintsalvestusseadmele juurdepääsu saamisel võistlesid viis arvutit. Peatselt pärast seda sõnastas Tony Hoare selle probleemi ümber einestavate filosoofide probleemina..

Probleem

Illustratsioon Einestavate filosoofide probleemist

Einestavate filosoofide probleemi saab üldistada vastavalt, kui ümarlaua ääres istuvad viis filosoofi, viites oma aega kas söömisele, mõtlemisele või nälgimisele (söömisjärjekorras ootamisele). Laua keskel on kauss toiduga (nt spagetid), mille serveerimiseks on ette nähtud kahvlid. Kahvlid on asetatud iga filosoofi vahele, nõnda et iga filosoofi parema ja vasaku käe all on kahvel, kokku on laual kahvleid viis. On eeldatud, et toidu serveerimine/söömine on keerukas protsess, seega filosoof peab kasutama selleks kahte kahvlit. Lauakommete kohaselt on kokku lepitud, et kasutada võib kahvleid, mis on filosoofile otseselt vastas.

Selgitus

Tegemist on teoreetilise kirjeldusega, mis seletab probleeme:

• Olukord, kus filosoofid on endale haaranud kahvli (ehk lukustanud objekti) ja püüavad eesmärgi saavutamiseks haarata teist kahvlit (lukustada veel üht objekti), mille on haaranud (lukustanud) teine filosoof. See olukord on inglise keeles tuntud terminina deadlock ehk tupik, mis kujutaks enesest kõigi lõimede lukustumist.
• Olukord, kus üks filosoof peab ootama söömise järjekorras määramatult kaua aega, sest kahvlid mida ta võiks söömiseks tarvitada on tema naaberfilosoofide käes. Sellise olukorra võib põhjustada asjaolu, kui antud olukorras 2 filosoofi, kes pole üksteise vastas, mõtlevad ja söövad teistest tunduvalt kiiremini. See olukord on inglise keeles tuntud terminina starvation ehk (filosoofi) nälgimine, mis kujutaks enesest lõime peaaegu olematut võimalust pääseda ressurssi lasutama.
• Olukorda, kus filosoof pidevalt muudab oma staatust, aga söönuks ei saa. Näitena võib kujutada olukorda, kus kõik filosoofid haaravad ühel ajal vasaku kahvli, kuna aga paremalt pole kahvlit võtta ja soovides mitte nälgida, otsustavad filosoofid kahvli käest panna ja oodata näiteks 5 minutit ja proovida uuesti (ning olukord kordub). See olukord on nälgimise erijuht, ning on inglise keeles tuntud terminina livelock ehk korduv tupik, mis kujutaks enesest lõimede korduvat lukustumist.
• Olukord iseenesest, ehk kahvleid on vähem, kui filosoofidel neid kõikidel võimalikel juhtudel vaja võiks minna. See olukord on inglise keeles tuntud terminina concurrency ehk ressursi puudulikkus, mis kujutaks enesest samaaegset ressursivajadust.

Selgitamaks sümbolismi, võib kujutada samaväärseteks:

• filosoofid = reaalajas üksteisest sõltumatud protsessid
• objekt või kahvel = piiratud ressursikogum

Tänapäeva arvutites on tihti rohkem kui üks protsessor, et aga sellest kasu saada, peab programm olema nõnda ehitatud. Üks võimalus selleks on kasutada lõimesid. Kuna lõimed võivad olla käivitatud teistes protsessorites, võib üldse esineda olukord, kus ressurss on mõne teise lõime taga kinni. Kusjuures ressursi suurus võib olla isegi vaid üks täisarvu suurusega mäluaadress.

Pakutud lahendused

Teenindaja

Lihtne lahendus on saavutatud, kui lauda liitub teenindaja. Filosoofid peavad küsima luba enne, kui soovivad kahvleid üles võtta. Kuna teenindaja on teadlik, mis kahvlid on kasutuses, võib ta sekkuda ja vältida tupikuid. Kui selles olukorras on neli kahvlit kasutuses, siis järgmine filosoof peab teenindajalt küsima luba, mis ei anta enne, kui kahvel on vabanenud kasutusest. Kõik filosoofid võtavad ja panevad käest esimesena vasaku käe all oleva kahvli(kõik peavad samamoodi käituma, seega vahet ei oleks, kui seda tehakse parema käega).

Eelised:

• Tupik ei saa tekkida

Ressursi hierarhia

Kahvlitele antakse primaarse eritunnusena unikaalne järjekorranumber. Filosoofid võtavad väiksema järjekorranumbriga kahvli esimesena. Söönuks saanuna annavad nad käest väiksema järjekorranumbriga kahvli.

Eelised:

• Tupik ei saa tekkida
• Ei saa tekkida korduv tupik

Vaata ka

• Programmeerimine
• Semafor (programmeerimine)
• Lõimed

Välislingid

• Näide probleemist ja lahendustest (Java-aplett; inglise, prantsuse ja saksa keeles)
• Interaktiivne näide (Java tugi on veebibrauseris vajalik)
• Arutlus erinevatest lahendustest