Dining Philosophers -ongelma on klassinen esimerkki, jota käytetään tietojenkäsittelytieteessä havainnollistamaan synkronointiongelmia kehitettäessä rinnakkaisia algoritmeja ja tekniikoita näiden ongelmien ratkaisemiseksi.
Edsger Dijkstra muotoili ongelman vuonna 1965 opiskelijoiden kokeeksi. Esimerkkinä otettiin kilpaileva pääsy nauha-asemaan . Pian Anthony Hoare muotoili ongelman siinä muodossa, jossa se nykyään tunnetaan [1] [2] [3] .
Viisi hiljaista filosofia istuu pyöreän pöydän ympärillä ja jokaisen filosofin edessä on spagettilautanen. Haarukat makaavat pöydällä lähimpien filosofien parin välissä.
Jokainen filosofi voi joko syödä tai ajatella. Jäljellä olevan spagetin määrä ei rajoita syömistä - se tarkoittaa ääretöntä tarjontaa. Filosofi voi kuitenkin syödä vain, kun hän pitää kädessään kahta haarukkaa oikealta ja vasemmalta (vaihtoehtoinen ongelman muotoilu tarkoittaa riisiä ja syömäpuikkoja spagettikulhojen ja haarukoiden sijaan).
Jokainen filosofi voi ottaa lähimmän haarukan (jos sellainen on saatavilla) tai laskea sen alas, jos hänellä on jo sellainen. Jokaisen haarukan poimiminen ja palauttaminen pöytään ovat erillisiä toimintoja, jotka on suoritettava peräkkäin.
Tehtävänä on kehittää käyttäytymismalli ( rinnakkaisalgoritmi ) , jossa kukaan filosofeista ei kuole nälkään, eli hän ikuisesti vuorottelee syömisen ja ajattelun välillä.
Ongelma on muotoiltu siten, että se havainnollistaa umpikujan välttämisen ongelmaa - järjestelmän tilaa , jossa edistyminen on mahdotonta.
Jokaista filosofia voitaisiin esimerkiksi neuvoa suorittamaan seuraava algoritmi:
Tämä ratkaisu ongelmaan on virheellinen: sen avulla järjestelmä pääsee umpikujaan, jossa jokainen filosofi on ottanut vasemmanpuoleisen haarukan ja odottaa oikeanpuoleisen haarukan vapautumista [4] .
Resurssien nälkäongelma voi ilmetä umpikujasta riippumatta , jos joku filosofeista ei saa käsiinsä vasenta ja oikeaa haarukkaa synkronointiongelmien vuoksi. Voidaan esimerkiksi ehdottaa sääntöä, jonka mukaan filosofien tulisi laittaa haarukka takaisin pöydälle odotettuaan viisi minuuttia, että toinen haarukka tulee saataville, ja odottamaan vielä viisi minuuttia ennen kuin yrittävät ottaa haarukat uudelleen haltuunsa. Tämä kaava eliminoi eston mahdollisuuden (koska järjestelmä voi aina mennä toiseen tilaan), mutta silti on olemassa mahdollisuus järjestelmän "silmukkaan" ( eng. livelock ), jossa järjestelmän tila muuttuu, mutta se ei tee mitään hyödyllistä työtä. Esimerkiksi, jos kaikki viisi filosofia ilmestyvät ruokasaliin samaan aikaan ja jokainen poimii vasemman haarukan samaan aikaan, filosofit odottavat viisi minuuttia toivoen saavansa oikean haarukan, sitten laskevat vasemman haarukan alas ja odottavat. vielä viisi minuuttia ennen kuin yrität saada haarukat.
Keskinäinen poissulkeminen on Dining Philosophers -ongelman pääidea . Tämä ongelma on yleinen, abstrakti skenaario tämän tyyppisen ongelman selittämiseksi. Filosofien virheet havainnollistavat vaikeuksia, joita syntyy todellisessa ohjelmoinnissa, kun useat ohjelmat vaativat yksinoikeudella pääsyn jaettuihin resursseihin. Näitä kysymyksiä tutkitaan rinnakkaislaskennan alalla .
Dijkstran alkuperäinen tavoite muotoillessaan Ruokailufilosofin ongelmaa oli osoittaa mahdolliset ongelmat ulkoisissa tietokonelaitteissa, kuten nauha-asemissa [1] . Tämän tehtävän laajuus kuitenkin laajenee paljon pidemmälle, ja tehtävässä huomioituja monimutkaisia tekijöitä syntyy useammin, kun useat prosessit yrittävät päästä päivitettävään tietojoukkoon.
Järjestelmät, joiden on käsiteltävä useita samanaikaisia prosesseja (kuten käyttöjärjestelmän ytimet ), käyttävät tuhansia lukkoja ja synkronointipisteitä. Tämä edellyttää tiukkaa menetelmien ja protokollien noudattamista, jos halutaan välttää umpikuja, nälänhätä ja tietojen korruptio.
Suhteellisen yksinkertainen ratkaisu ongelmaan saadaan lisäämällä tarjoilija pöydän viereen. Filosofien on odotettava tarjoilijan lupaa ennen haarukan ottamista. Koska tarjoilija tietää kuinka monta haarukkaa on tällä hetkellä käytössä, hän voi tehdä päätöksiä haarukoiden jakelusta ja näin estää filosofien lukkiutumasta. Jos neljä viidestä haarukasta on jo käytössä, seuraava filosofi, joka pyytää haarukkaa, joutuu odottamaan tarjoilijan lupaa, jota ei saa ennen kuin haarukka vapautetaan. Oletetaan, että filosofi yrittää aina ensin ottaa vasemman haarukan ja sitten oikean (tai päinvastoin), mikä yksinkertaistaa logiikkaa. Tarjoilija toimii kuin semafori , Dijkstra esitteli sen vuonna 1965 [5] .
Osoittaaksemme, kuinka tämä ratkaisu toimii, oletetaan, että filosofit on merkitty A:sta D:hen myötäpäivään. Jos filosofit A ja B syövät, niin neljä haarukkaa on varattu. Filosofi B istuu A:n ja C:n välissä, joten kumpikaan haarukka ei ole hänen käytettävissään. Samanaikaisesti filosofeilla D ja D on käytössään yksi käyttämätön haarukka heidän välillään. Oletetaan, että filosofi G on nälkäinen. Jos hän ottaa välittömästi vapaan haarukan, filosofien vastavuoroinen estäminen tulee mahdolliseksi. Jos hän sen sijaan pyytää lupaa tarjoilijalta, hän pyytää häntä odottamaan - ja voit olla varma, että heti kun haarukkapari on vapaana, niin ainakin yksi filosofi voi ottaa kaksi haarukkaa. Siten umpikujasta tulee mahdotonta.
Toinen yksinkertainen ratkaisu saavutetaan antamalla resursseille (tässä tapauksessa haarukoille) osittainen järjestys ja tekemällä sopimus, että resurssit pyydetään tässä järjestyksessä ja palautetaan käänteisessä järjestyksessä. Samassa työyksikössä ei myöskään saa olla kahta epäkunnossa olevaa resurssia.
Olkoon resurssit (haarukat) numeroitu 1:stä 5:een, ja jokainen työyksikkö (filosofi) ottaa aina ensin pienimmän haarukan ja sitten suurimman haarukan kahdesta käytettävissä olevasta. Seuraavaksi filosofi laskee ensin haarukan, jolla on suurempi numero, ja sitten sen, jolla on pienempi numero. Tässä tapauksessa, jos neljä viidestä filosofista ottaa pienimmän numeroidun haarukan samaan aikaan, suurin mahdollinen numeroitu haarukka jää pöydälle. Siten viides filosofi ei voi ottaa ainuttakaan haarukkaa. Lisäksi vain yhdellä filosofilla on pääsy korkeimpaan haarukkaan, joten hän voi syödä kahdella haarukalla. Kun hän on lopettanut haarukoiden käytön, hän asettaa ensin pöydälle suurimman numeron haarukan, sitten pienemmän, jolloin toinen filosofi voi poimia puuttuvan haarukan ja aloittaa syömisen.
Tätä ratkaisua ehdotti Dijkstra.
Vaikka resurssihierarkia välttää lukkiutumisen, tämä ratkaisu ei ole aina käytännöllinen, varsinkin kun tarvittavien resurssien luetteloa ei tiedetä etukäteen. Jos esimerkiksi työyksikkö pitää hallussaan resursseja 3 ja 5 ja päättää tarvitsevansa resurssia 2, sen on vapautettava resurssi 5, sitten 3, sitten otettava resurssi 2 haltuunsa ja otettava resurssit 3 ja 5 uudelleen. tietokannan tietueet eivät toimisi tehokkaasti, jos heidän piti julkaista kaikki yläindeksillä merkityt tietueet ennen uuden tietueen ottamista haltuunsa. Tämä tekee tästä menetelmästä epäkäytännöllisen.
Alla oleva esimerkki esittää ratkaisun, jossa haarukoita ei ole eksplisiittisesti esitetty. Filosofit voivat syödä, jos kukaan heidän naapureistaan ei syö. Samanlainen järjestelmä, jossa filosofien, jotka eivät voi ottaa toista haarukkaa, on laskettava ensimmäinen haarukka ennen kuin he yrittävät uudelleen.
Haarukoihin liittyvien tukosten puuttuessa filosofien on varmistettava, että aterian aloitus ei perustu vanhaan tietoon naapureiden tilasta. Esimerkki: Jos filosofi B näkee, että A ei syö tiettyyn aikaan, ja kääntyy sitten ympäri ja katsoo C:tä, A voisi aloittaa syömisen, kun filosofi B katsoo C:tä. Käyttämällä yhtä mutexia tämä ongelma voidaan välttää. Tämä esto ei liity haarukoihin, vaan se liittyy päätökseen menettelyistä, jotka voivat muuttaa filosofien tilaa. Tämän tarjoaa monitori.
Valvontaalgoritmi toteuttaa tarkista, ota ja laita -mallin ja jakaa toisensa poissulkevan lukituksen. Huomaa, että filosofeilla, jotka haluavat syödä, ei ole haarukkaa.
Jos monitori antaa syödä haluavan filosofin toimia, niin filosofi ottaa jälleen haltuunsa ensimmäisen haarukan ennen kuin ottaa jo vapaan toisen.
Nykyisen aterian lopussa filosofi ilmoittaa monitorille, että molemmat haarukat ovat ilmaisia.
On syytä huomata, että tämä monitorialgoritmi ei ratkaise nälkäongelmaa. Esimerkiksi filosofi B voi odottaa vuoroaan loputtomiin, jos filosofeilla A ja B on päällekkäisiä ruokailujaksoja. Varmistaaksesi, ettei yksikään filosofi jää nälkäiseksi, voit seurata, kuinka monta kertaa nälkäinen filosofi ei ole syönyt, kun hänen naapurinsa laittavat haarukkansa pöytään. Jos kertojen määrä ylittää tietyn rajan, tällainen filosofi siirtyy nälkätilaan ja monitorialgoritmi pakottaa haarukan hankintamenettelyn täyttäen ehdon minkä tahansa naapurin nälkään estämisestä.
Filosofi, joka ei voi ottaa haarukoita, koska hänen naapurinsa näkee nälkää, odottaa hyödyllisessä tilassa, että naapurin naapuri lopettaa syömisen. Tämä lisäriippuvuus vähentää samanaikaisuutta. Nälkäkynnyksen nostaminen vähentää tätä vaikutusta.