streamalism.org

1. Uvod

Problem Dining Philosophers jedan je od klasičnih problema koji su se nekada koristili opisati probleme sinkronizacije u okruženju s više niti i ilustrirati tehnike za njihovo rješavanje. Dijkstra je prvo formulirao ovaj problem i predstavio ga u vezi s računalima koji pristupaju perifernim uređajima s trakom.

Sadašnju formulaciju dao je Tony Hoare, koji je također poznat po tome što je izumio algoritam za sortiranje brzog sortiranja. U ovom članku analiziramo ovaj dobro poznati problem i kodiramo popularno rješenje.

2. Problem

Gornji dijagram predstavlja problem. Pet je tihih filozofa (P1 - P5) koji sjede oko kružnog stola i provode život jedući i razmišljajući.

Postoji pet vilica koje mogu dijeliti (1 - 5) i da bi mogli jesti, filozof mora imati vilice u obje ruke. Nakon što jede, obojicu spusti i tada ih može odabrati drugi filozof koji ponavlja isti ciklus.

Cilj je smisliti shemu / protokol koji pomaže filozofima da postignu svoj cilj jesti i razmišljati, a da ne umru od gladi.

3. Rješenje

Početno rješenje bilo bi natjerati svakog filozofa da slijedi sljedeći protokol:

while (true) {// U početku razmišljanje o životu, svemiru i svemu misle (); // Odmorite se od razmišljanja, gladni sada pick_up_left_fork (); pick_up_right_fork (); jesti(); put_down_right_fork (); put_down_left_fork (); // Više nisam gladan. Povratak na razmišljanje! } 

Kao što gornji pseudo kod opisuje, svaki filozof u početku razmišlja. Nakon određenog vremena filozof ogladni i poželi jesti.

U ovom trenutku, posegne za rašljama s obje strane i kad ih obje uhvati, nastavlja jesti. Jednom kad se jede, filozof zatim odlaže vilice, tako da su dostupne njegovom susjedu.

4. Provedba

Modeliramo svakog našeg filozofa kao nastavu koja provodi Izvodljivo sučelje kako bismo ih mogli pokretati kao zasebne niti. Svaki Filozof ima pristup dvjema rašljama s lijeve i desne strane:

javna klasa Philosopher implementira Runnable {// račve s obje strane ovog privatnog objekta Philosopher leftFork; private Object rightFork; javni filozof (Objekt leftFork, Objekt rightFork) {this.leftFork = leftFork; this.rightFork = rightFork; } @Override public void run () {// Ipak za popunjavanje ove metode}}

Također imamo metodu koja upućuje a Filozof za izvođenje radnje - jesti, razmišljati ili nabaviti vilice u pripremi za jelo:

javna klasa Philosopher implementira Runnable {// varijable člana, standardni konstruktor private void doAction (akcija niza) baca InterruptedException {System.out.println (Thread.currentThread (). getName () + "" + action); Thread.sleep (((int) (Math.random () * 100))); } // Ostatak prethodno napisanih metoda}

Kao što je prikazano u gornjem kodu, svaka se akcija simulira suspendiranjem niti koja poziva na slučajan vremenski period, tako da nalog za izvršenje ne provodi samo vrijeme.

Sada, implementirajmo sržnu logiku a Filozof.

Da bismo simulirali stjecanje vilice, moramo je zaključati tako da nema dvije Filozof niti ga stječu istodobno.

Da bismo to postigli, koristimo sinkronizirano ključna riječ za stjecanje unutarnjeg monitora objekta vilice i sprečavanje drugih niti da rade isto. Vodič kroz sinkronizirano Ključnu riječ u Javi možete pronaći ovdje. Nastavljamo s provedbom trčanje() metoda u Filozof razred sada:

javna klasa Philosopher implementira Runnable {// varijable člana, metode definirane ranije @Override public void run () {try {while (true) {// razmišljanje doAction (System.nanoTime () + ": Thinking"); sinkronizirano (leftFork) {doAction (System.nanoTime () + ": Podignuta lijeva vilica"); sinkronizirano (rightFork) {// jesti doAction (System.nanoTime () + ": Podignuta desna vilica - jesti"); doAction (System.nanoTime () + ": Odložite desnu vilicu"); } // Povratak na razmišljanje doAction (System.nanoTime () + ": Spusti lijevu vilicu. Natrag na razmišljanje"); }}} catch (InterruptedException e) {Thread.currentThread (). interrupt (); povratak; }}} 

Ova shema točno provodi onu prethodno opisanu: a Filozof neko vrijeme razmišlja, a zatim odluči jesti.

Nakon toga nabavlja vilice s lijeve i desne strane i počinje jesti. Po završetku stavlja vilice. Također dodamo vremenske oznake svakoj radnji, što bi nam pomoglo da razumijemo redoslijed kojim se događaji događaju.

Da bismo započeli cijeli postupak, pišemo klijenta koji kreira 5 Filozofi kao niti i pokreće ih sve:

public class DiningPhilosophers {public static void main (String [] args) baca iznimku {Philosopher [] filozofi = novi filozof [5]; Objekt [] račva = novi objekt [filozofi.duljina]; for (int i = 0; i <forks.length; i ++) {forks [i] = novi objekt (); } for (int i = 0; i <filozofi.duljina; i ++) {Objekt leftFork = forks [i]; Objekt rightFork = forks [(i + 1)% forks.length]; filozofi [i] = novi filozof (leftFork, rightFork); Tema t = nova nit (filozofi [i], "Filozof" + (i + 1)); t.start (); }}}

Svaku račvicu modeliramo kao generički Java objekt i izrađujemo ih onoliko koliko ima filozofa. Prolazimo svaku Filozof lijeve i desne vilice koje pokušava zaključati pomoću sinkronizirano ključna riječ.

Pokretanje ovog koda rezultira izlazom sličnim sljedećem. Izlaz će se najvjerojatnije razlikovati od dolje navedenog, uglavnom zato što spavati() metoda se poziva za drugi interval:

Filozof 1 8038014601251: Razmišljajući filozof 2 8038014828862: Razmišljajući filozof 3 8038015066722: Razmišljajući filozof 4 8038015284511: Razmišljajući filozof 5 8038015468564: Razmišljajući filozof 1 8038016857288: pokupljen levo 803 vilica Filozof 4 8038063952219: Podignuta lijeva vilica Filozof 1 8038067505168: Odložite desnu vilicu Filozof 2 8038089505264: Podignuta lijeva vilica Filozof 1 8038089505264: Odložite lijevu vilicu. Povratak razmišljanju Philosopher 5 8038111040317: Podignuta lijeva vilica

Svi FilozofU početku počinjemo razmišljati, i to vidimo Filozof 1 nastavlja podizati lijevu i desnu rašlju, zatim jede i nastavlja spuštati obojicu, nakon čega je `Philosopher 5` podiže.

5. Problem s rješenjem: Zastoj

Iako se čini da je gornje rješenje točno, javlja se problem zastoja.

Zastoj je situacija u kojoj je napredak sustava zaustavljen jer svaki proces čeka da stekne resurs koji drži neki drugi proces.

To možemo potvrditi pokretanjem gornjeg koda nekoliko puta i provjerom da ponekad kôd jednostavno visi. Evo primjera rezultata koji pokazuju gornju poteškoću:

Philosopher 1 8487540546530: Thinking Philosopher 2 8487542012975: Thinking Philosopher 3 8487543057508: Thinking Philosopher 4 8487543318428: Thinking Philosopher 5 8487544590144: Thinking Philosopher 3 8487589069046: left for Philosof 8 4 8487617680958: Podignuta lijeva vilica Filozof 2 8487631148853: Podignuta lijeva vilica

U ovoj situaciji, svaki od Filozofs je nabavio lijevu vilicu, ali ne može dobiti desnu, jer ju je susjed već stekao. Ova je situacija uobičajeno poznata kao kružno čekanje i jedan je od uvjeta koji rezultira zastojem i sprečava napredak sustava.

6. Rješavanje mrtve točke

Kao što smo vidjeli gore, primarni razlog zastoja je stanje kružnog čekanja gdje svaki proces čeka na resurs koji drži neki drugi proces. Stoga, da bismo izbjegli mrtvu situaciju, moramo osigurati da je kružno stanje čekanja narušeno. Postoji nekoliko načina da se to postigne, a najjednostavniji je sljedeći:

Svi filozofi prvo posežu za lijevom račvom, osim one koja prva poseže za desnom vilicom.

To implementiramo u naš postojeći kôd čineći relativno malu promjenu u kodu:

javna klasa DiningPhilosophers {javna statička praznina main (String [] args) baca iznimku {final Philosopher [] filozofi = novi filozof [5]; Objekt [] račva = novi objekt [filozofi.duljina]; for (int i = 0; i <forks.length; i ++) {forks [i] = novi objekt (); } for (int i = 0; i <filozofi.duljina; i ++) {Objekt leftFork = forks [i]; Objekt rightFork = forks [(i + 1)% forks.length]; if (i == filozofi.duljina - 1) {// Posljednji filozof podiže desnu račvu prvi filozofi [i] = novi filozof (rightFork, leftFork); } else {filozofi [i] = novi filozof (leftFork, rightFork); } Tema t = nova nit (filozofi [i], "Filozof" + (i + 1)); t.start (); }}} 

Promjena dolazi u redovima 17-19 gornjeg koda, gdje uvodimo uvjet zbog kojeg posljednji filozof prvo poseže za desnom, umjesto lijevom vilicom. To narušava kružno stanje čekanja i možemo spriječiti zastoj.

Sljedeći izlaz prikazuje jedan od slučajeva kada svi Filozofdobiju priliku razmišljati i jesti, bez zastoja:

Philosopher 1 88519839556188: Thinking Philosopher 2 88519840186495: Thinking Philosopher 3 88519840647695: Thinking Philosopher 4 88519840870182: Thinking Philosopher 5 88519840956443: Thinking Philosophe 3 88519864404195 Philosophe Pick up 5: Philosophe 5 88519876989405: Podignuta desna vilica - Filozof jede 2 88519935045524: Podignuta lijeva vilica Filozof. Povratak razmišljanju Filozof 5 88520011135846: Razmišljajući filozof 1 88520011129013: Podignuta lijeva vilica Filozof 4 88520028194269: Odložite desnu vilicu Filozof 4 88520057160194: Odložite lijevu vilicu. Povratak razmišljanju Filozof 3 88520067162257: Podignuta desna vilica - Filozof koji jede 4 88520067158414: Filozof koji razmišlja 3 88520160247801: Spuštena desna vilica Filozof 4 88520249049308: Podignuta lijeva vilica Filozof 3 88520249119769: Spuštena lijeva vilica. Povratak na razmišljanje 

Putem pokretanja koda može se provjeriti da je sustav bez situacije mrtve točke koja se dogodila prije.

7. Zaključak

U ovom smo članku istražili poznati problem Dining Philosophers i koncepti kružnog čekanja i mrtve točke. Kodirali smo jednostavno rješenje koje je uzrokovalo zastoj i napravili jednostavnu promjenu kako bismo prekinuli kružno čekanje i izbjegli zastoj. Ovo je samo početak, a postoje i sofisticiranija rješenja.

Kôd za ovaj članak nalazi se na GitHubu.