Einestavad filosoofid

Allikas: Vikipeedia

Einestavad filosoofid on informaatikas klassikaline mudel probleemist, mis käsitleb mitmelõimeliste protsesside sünkronisatsiooni. Tänapäeval on lisatud antud probleemi käsitlemine enamuste informaatika põhist kõrgharidust pakkuvate koolide ainekavva.

Ajalugu[muuda | redigeeri lähteteksti]

Aastal 1971 kasutas Edsger Dijkstra sünkroneerimise probleemi küsimust, kus viiele magnetlint salvestusseadme juurdepääsule võistlesid viis arvutit. Peatselt pärast seda sõnastas Tony Hoare antud probleemi ümber einestavate filosoofide probleemina.[1].

Probleem[muuda | redigeeri lähteteksti]

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[muuda | redigeeri lähteteksti]

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. Antud 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. Antud olukord on inglise keeles tuntud terminina "starvation", ehk (filosoofi) nälgimine, mis kujutaks enesest lõime peaaegu olematut võimalust pääseda ligi ressursile.
  • Olukorda, kus filosoof pidevalt muudab oma staatust aga söönuks ei saa. Näitena võib kujutada olukorda, kus sama hetkeliselt haaravad kõik filosoofid vasaku kahvli, kuna aga paremalt pole kahvlit võtta ja soovides mitte nälgida otsustavad filosoofid kahvli käest panna ja oodata nt: 5 min ja proovida uuesti(ning olukord kordub). Antud 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. Antud olukord on inglise keeles tuntud terminina "concurrency", ehk ressursi puudulikus, mis kujutaks enesest samaaegset ressursi vajadust.

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.

Välja pakutud lahendused[muuda | redigeeri lähteteksti]

Teenindaja[muuda | redigeeri lähteteksti]

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 antud 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[muuda | redigeeri lähteteksti]

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

Eelised:

  • Tupik ei saa tekkida
  • Ei saa tekkida korduv tupik

Vaata ka[muuda | redigeeri lähteteksti]

Algmaterjalide ja märkmete viited[muuda | redigeeri lähteteksti]

  1. Dijkstra, Edsger W. (1971). "Hierarchical ordering of sequential processes". Acta Informatica 1: 115–138. 

Välislingid[muuda | redigeeri lähteteksti]