The Dining Philosophers Problem este un exemplu clasic folosit în informatică pentru a ilustra problemele de sincronizare în dezvoltarea algoritmilor și tehnicilor paralele pentru rezolvarea acestor probleme.
Problema a fost formulată în 1965 de către Edsger Dijkstra ca un exercițiu de examinare pentru studenți. A fost luat un exemplu de acces concurent la o unitate de bandă . Curând problema a fost formulată de Anthony Hoare în forma în care este cunoscută astăzi [1] [2] [3] .
Cinci filozofi tăcuți stau în jurul unei mese rotunde, cu câte o farfurie cu spaghete în fața fiecărui filosof. Pe masă se află furculițe între fiecare pereche de filozofi cei mai apropiați.
Fiecare filosof poate fie să mănânce, fie să gândească. Mâncatul nu este limitat de cantitatea de spaghete rămasă - este implicită o aprovizionare infinită. Cu toate acestea, filosoful poate mânca doar când ține în mână două furculițe, luate din dreapta și din stânga (o formulare alternativă a problemei implică boluri cu orez și betisoare în loc de boluri cu spaghete și furculițe).
Fiecare filosof poate lua cea mai apropiată furculiță (dacă există una) sau o pune jos dacă ține deja una. Ridicarea fiecărei furculițe și returnarea acesteia la masă sunt acțiuni separate care trebuie efectuate una după alta.
Problema sarcinii este de a dezvolta un model de comportament ( algoritm paralel ) în care niciunul dintre filozofi nu va muri de foame, adică va alterna pentru totdeauna între mâncare și gândire.
Problema este formulată în așa fel încât să ilustreze problema evitării blocajului - o stare a sistemului în care progresul este imposibil.
De exemplu, s-ar putea sfătui fiecărui filozof să efectueze următorul algoritm:
Această soluție a problemei este incorectă: permite sistemului să ajungă într-o stare de blocaj, în care fiecare filosof a luat bifurcația din stânga și așteaptă ca bifurcația din dreapta să devină liberă [4] .
Problema înfometării resurselor poate apărea indiferent de blocaj dacă unul dintre filosofi nu poate pune mâna pe furcile din stânga și din dreapta din cauza problemelor de sincronizare. De exemplu, ar putea fi propusă o regulă conform căreia filozofii ar trebui să pună o furculiță înapoi pe masă după ce au așteptat cinci minute pentru ca o altă furculiță să fie disponibilă și să aștepte încă cinci minute înainte de a încerca să ia din nou în posesia furculițele. Această schemă elimină posibilitatea blocării (deoarece sistemul poate merge întotdeauna într-o altă stare), dar există încă posibilitatea unei „bucle” a sistemului ( ing. livelock ), în care starea sistemului se schimbă, dar aceasta nu efectuează nicio lucrare utilă. De exemplu, dacă toți cei cinci filozofi apar în sala de mese în același timp și fiecare ridică furculița din stânga în același timp, filozofii vor aștepta cinci minute în speranța că vor obține furculița din dreapta, apoi vor pune jos furculița din stânga și vor aștepta încă cinci minute înainte de a încerca să ia furcile.din nou.
Excluderea reciprocă este ideea principală a problemei filozofilor dining. Această problemă este un scenariu general, abstract, pentru a explica acest tip de problemă. Greșelile filozofilor ilustrează dificultățile care apar în programarea reală atunci când mai multe programe necesită acces exclusiv la resursele partajate. Aceste întrebări sunt studiate în domeniul calculului paralel .
Scopul inițial al lui Dijkstra în formularea Problemei filosofului dining a fost să demonstreze posibilele probleme cu dispozitivele computerizate externe, cum ar fi unitățile de bandă [1] . Cu toate acestea, domeniul de aplicare al acestei sarcini se extinde mult mai mult, iar complexitățile luate în considerare în sarcină apar mai des atunci când mai multe procese încearcă să acceseze un set de date care este actualizat.
Sistemele care trebuie să facă față unui număr mare de procese concurente (cum ar fi nucleele sistemului de operare ) folosesc mii de blocări și puncte de sincronizare. Acest lucru necesită respectarea strictă a metodologiilor și protocoalelor pentru a evita blocajele, înfometarea și coruperea datelor.
O soluție relativ simplă a problemei se obține prin adăugarea unui chelner lângă masă. Filosofii trebuie să aștepte permisiunea chelnerului înainte de a lua furculița. Deoarece chelnerul știe câte furculițe sunt în uz în prezent, el poate lua decizii cu privire la distribuirea furculițelor și astfel împiedică filozofii să se blocheze. Dacă patru din cinci furculițe sunt deja în uz, atunci următorul filosof care va cere o furculiță va trebui să aștepte permisiunea ospătarului - care nu va fi primită până când furculița nu va fi eliberată. Se presupune că filozoful încearcă întotdeauna să ia mai întâi furca din stânga, apoi pe cea dreaptă (sau invers), ceea ce simplifică logica. Chelnerul funcționează ca un semafor , concept introdus de Dijkstra în 1965 [5] .
Pentru a arăta cum funcționează această soluție, să presupunem că filozofii sunt etichetați de la A la D în sensul acelor de ceasornic. Dacă filozofii A și B mănâncă, atunci patru furculițe sunt ocupate. Filosoful B stă între A și C, astfel încât niciuna dintre furculițe nu îi este disponibilă. În același timp, filozofii D și D au acces la o furcă nefolosită între ei. Să presupunem că filosofului G îi este foame. Dacă ia imediat o furcă liberă, atunci blocarea reciprocă a filozofilor devine posibilă. Dacă în schimb cere permisiunea chelnerului, acesta îi cere să aștepte - și poți fi sigur că de îndată ce o pereche de furculițe este liberă, atunci cel puțin un filozof va putea lua două furculițe. Astfel, blocajul devine imposibil.
O altă soluție simplă se realizează prin atribuirea unei ordini parțiale resurselor (furcaturi în acest caz) și făcând convenția că resursele sunt solicitate în acea ordine și returnate în ordine inversă. De asemenea, nu ar trebui să existe două resurse nefuncționale utilizate de aceeași unitate de lucru.
Lăsați resursele (furcile) să fie numerotate de la 1 la 5, iar fiecare unitate de lucru (filozof) ia întotdeauna mai întâi furculița cu cea mai mică numărătoare și apoi furculița cu cea mai mare numărătoare dintre cele două disponibile. În continuare, filosoful pune jos furculița cu numărul mai mare, apoi pe cea cu numărul mai mic. În acest caz, dacă patru din cinci filozofi iau în același timp furculița cu cea mai mică numărătoare, va rămâne pe masă cea mai mare furculiță cu numerotație posibilă. Astfel, al cincilea filozof nu va putea lua nici măcar o furculiță. Mai mult, un singur filosof va avea acces la cea mai mare furculiță numerotată, așa că poate mânca cu două furculițe. Când a terminat de folosit furculițele, va pune mai întâi pe masă furculița cu cea mai mare numerotată, apoi pe cea mai mică, permițând astfel celuilalt filosof să ridice furculița lipsă și să înceapă să mănânce.
Această soluție a fost sugerată de Dijkstra.
În timp ce ierarhia resurselor evită blocajele, această soluție nu este întotdeauna practică, mai ales când lista resurselor necesare nu este cunoscută dinainte. De exemplu, dacă o unitate de lucru deține resursa 3 și 5 și decide că are nevoie de resursa 2, atunci trebuie să elibereze resursa 5, apoi 3, apoi să ia în posesie resursa 2 și să ia din nou resursele 3 și 5. înregistrările dintr- o bază de date nu ar funcționa eficient dacă aveau nevoie să elibereze toate înregistrările superscriptoare înainte de a intra în posesia noii înregistrări. Acest lucru face ca această metodă să fie nepractică.
Exemplul de mai jos arată o soluție în care furcile nu sunt reprezentate în mod explicit. Filosofii pot mânca dacă niciunul dintre vecinii lor nu mănâncă. Similar cu sistemul în care filozofii care nu pot ridica a doua furculiță trebuie să pună jos prima furculiță înainte de a încerca din nou.
În absența blocajelor legate de furculiță, filozofii trebuie să se asigure că începutul unei mese nu se bazează pe informații vechi despre starea vecinilor. De exemplu: dacă Filosoful B vede că A nu mănâncă la un moment dat și apoi se întoarce și se uită la C, A ar putea începe să mănânce în timp ce Filosoful B se uită la C. Folosind un singur mutex , această problemă poate fi evitată. Această blocare nu ține de furci, ci ține de decizia procedurilor care pot schimba starea filozofilor. Acesta este furnizat de monitor.
Algoritmul de monitorizare implementează o schemă de verificare, preluare și introducere și partajează blocarea exclusivă reciproc. Rețineți că filozofii care vor să mănânce nu vor avea furculițe.
Dacă monitorul îi permite filozofului care vrea să mănânce să acționeze, atunci filosoful ia din nou în posesia primei furculițe înainte de a o lua pe a doua, deja liberă.
La sfârșitul mesei curente, filosoful anunță monitorul că ambele furculițe sunt libere.
Este de remarcat faptul că acest algoritm de monitor nu rezolvă problema foametei. De exemplu, filozoful B poate aștepta la nesfârșit rândul său dacă filozofii A și B au perioade de mâncare care se suprapun. De asemenea, pentru a vă asigura că niciun filosof nu-i este foame, puteți urmări de câte ori un filosof înfometat nu a mâncat când vecinii săi și-au pus furculițele pe masă. Dacă numărul de ori depășește o anumită limită, un astfel de filozof va intra în starea de foame, iar algoritmul de monitorizare va forța procedura de achiziție a furcii, îndeplinind condiția de a preveni foamea oricăruia dintre vecini.
Filosoful, incapabil să ia furculițele pentru că vecinul său moare de foame, este într-un mod util de a aștepta ca vecinul vecinului să termine de mâncat. Această dependență suplimentară reduce concurența. Creșterea valorii pragului de foame reduce acest efect.