streamalism.org

1. Úvod

Problém Jedálni filozofi sú jedným z klasických problémov, ktoré sa zvykli používať popísať problémy so synchronizáciou v prostredí s viacerými vláknami a ilustrovať techniky ich riešenia. Dijkstra najskôr sformuloval tento problém a predstavil ho ohľadom počítačov, ktoré pristupujú k perifériám páskových jednotiek.

Súčasnú formuláciu dal Tony Hoare, ktorý je tiež známy tým, že vymyslel algoritmus triedenia quicksort. V tomto článku analyzujeme tento známy problém a kódujeme populárne riešenie.

2. Problém

Vyššie uvedená schéma predstavuje problém. Okolo kruhového stola sedí päť tichých filozofov (P1 - P5), ktorí trávia život jedením a premýšľaním.

Existuje päť vidličiek na zdieľanie (1 - 5) a na to, aby mohol jesť, musí mať filozof vidličky v oboch rukách. Po jedle ich oboch položí a potom si ich môže vybrať ďalší filozof, ktorý opakuje rovnaký cyklus.

Cieľom je vymyslieť schému / protokol, ktorý pomôže filozofom dosiahnuť ich cieľ jesť a myslieť bez toho, aby umreli od hladu.

3. Riešenie

Prvotným riešením by bolo prinútiť každého z filozofov dodržiavať nasledujúci protokol:

while (true) {// Spočiatku premýšľanie o živote, vesmíre a všetkom myslieť (); // Daj si pauzu od premýšľania, teraz hladný pick_up_left_fork (); pick_up_right_fork (); jesť (); put_down_right_fork (); put_down_left_fork (); // Už nie je hladný. Späť k premýšľaniu! } 

Ako popisuje vyššie uvedený pseudokód, každý filozof spočiatku uvažuje. Po určitom čase filozof vyhladne a chce jesť.

V tejto chvíli natiahne sa po vidličkách na oboch stranách a akonáhle ich dostane, pokračuje v jedle. Keď je jedlo hotové, filozof potom odloží vidličky, aby boli dostupné pre jeho suseda.

4. Implementácia

Každého z našich filozofov modelujeme ako triedy, ktoré implementujú Spustiteľné aby sme ich mohli spúšťať ako samostatné vlákna. Každý Filozof má prístup k dvom vidliciam na ľavej a pravej strane:

public class Philosopher implementuje Runnable {// Vidlice na oboch stranách tohto Philosopher private Object leftFork; private Object rightFork; public Philosopher (Object leftFork, Object rightFork) {this.leftFork = leftFork; this.rightFork = rightFork; } @Override public void run () {// Na vyplnenie tejto metódy}}

Máme tiež metódu, ktorá dáva pokyny a Filozof vykonať akciu - jesť, myslieť alebo získavať vidličky v rámci prípravy na jedlo:

public class Philosopher implements Runnable {// Member variables, standard constructor private void doAction (String action) throws InterruptedException {System.out.println (Thread.currentThread (). getName () + "" + action); Thread.sleep ((((int) (Math.random () * 100))); } // Zvyšok metód napísaných skôr}

Ako je uvedené v kóde vyššie, každá akcia je simulovaná pozastavením vyvolávacieho vlákna na náhodný čas, takže príkaz na vykonanie nie je vynútený samotným časom.

Teraz poďme implementovať základnú logiku a Filozof.

Aby sme simulovali získanie vidlice, musíme ju uzamknúť tak, aby neexistovali dve Filozof vlákna ho získavajú súčasne.

Aby sme to dosiahli, používame synchronizované kľúčové slovo na získanie interného monitora vidlicového objektu a zabránenie rovnakým vláknam v iných vláknach. Sprievodca po synchronizované kľúčové slovo v Jave nájdete tu. Pokračujeme v implementácii run () metóda v Filozof trieda teraz:

public class Philosopher implementuje Runnable {// Členské premenné, metódy definované skôr @Override public void run () {try {while (true) {// thinking doAction (System.nanoTime () + ": Thinking"); synchronized (leftFork) {doAction (System.nanoTime () + ": Zdvihnutá ľavá vidlica"); synchronized (rightFork) {// eating doAction (System.nanoTime () + ": Picked right fork - eating"); doAction (System.nanoTime () + ": Dajte dole pravú vidlicu"); } // Späť na myslenie doAction (System.nanoTime () + ": Dajte ľavú vidlicu. Späť na premýšľanie"); }}} catch (InterruptedException e) {Thread.currentThread (). interrupt (); návrat; }}} 

Táto schéma presne implementuje vyššie opísanú schému: a Filozof chvíľu rozmýšľa a potom sa rozhodne jesť.

Potom získa vidličky po ľavej a pravej strane a začne jesť. Po dokončení vidlice položí. Ku každej akcii tiež pridávame časové značky, ktoré nám pomôžu pochopiť poradie, v akom sa udalosti vyskytujú.

Na naštartovanie celého procesu napíšeme klienta, ktorý vytvorí 5 Filozofi ako vlákna a spustí všetky:

verejná trieda DiningPhilosophers {public static void main (String [] args) vyvolá Výnimku {Filozof [] filozofi = nový Filozof [5]; Vidlice objektu [] = nový objekt [philosophers.length]; for (int i = 0; i <forks.length; i ++) {forks [i] = new Object (); } for (int i = 0; i <philosophers.length; i ++) {Object leftFork = forks [i]; Object rightFork = forks [(i + 1)% forks.length]; filozofi [i] = nový Filozof (leftFork, rightFork); Vlákno t = nové vlákno (filozofi [i], „Filozof“ + (i + 1)); t.start (); }}}

Každú z vidličiek modelujeme ako generické objekty Java a vyrábame ich toľko, koľko je filozofov. Každý míňame Filozof jeho ľavú a pravú vidlicu, ktorú sa pokúša uzamknúť pomocou synchronizované kľúčové slovo.

Spustenie tohto kódu vedie k výstupu podobnému nasledujúcemu. Váš výstup sa bude pravdepodobne líšiť od toho, ktorý je uvedený nižšie, hlavne preto, že spánok () metóda je vyvolaná pre iný interval:

Philosopher 1 8038014601251: Thinking Philosopher 2 8038014828862: Thinking Philosopher 3 8038015066722: Thinking Philosopher 4 8038015284511: Thinking Philosopher 5 8038015468564: Thinking Philosopher 1 8038016857288: Picked left 80380 vidlica Filozof 4 8038063952219: Zdvihnutá ľavá vidlica Filozof 1 8038067505168: Položte pravú vidlicu Filozof 2 8038089505264: Zdvihnutá ľavá vidlica Filozof 1 8038089505264: Položte ľavú vidlicu. Späť k premýšľaniu Philosopher 5 8038111040317: Zdvihnutá ľavá vidlica

Všetko Filozofs spočiatku začať myslieť, a my to vidíme Filozof 1 pokračuje v zdvíhaní ľavej a pravej vidlice, potom zje a pokračuje v položení oboch dolu, po čom ho zdvihne program „Filozof 5“.

5. Problém s riešením: uviaznutie

Aj keď sa zdá, že vyššie uvedené riešenie je správne, nastáva problém zablokovania.

Zablokovanie je situácia, keď je pokrok systému zastavený, pretože každý proces čaká na získanie zdroja, ktorý vlastní nejaký iný proces.

To isté môžeme potvrdiť niekoľkonásobným spustením vyššie uvedeného kódu a kontrolou, či niekedy iba zablokuje. Tu je ukážka výstupu, ktorý demonštruje vyššie uvedený problém:

Philosopher 1 8487540546530: Thinking Philosopher 2 8487542012975: Thinking Philosopher 3 8487543057508: Thinking Philosopher 4 8487543318428: Thinking Philosopher 5 8487544590144: Thinking Philosopher 3 8487589069046: Picked75 8487548 4 8487617680958: Zdvihnutá ľavá vidlica Filozof 2 8487631148853: Zdvihnutá ľavá vidlica

V tejto situácii každý z Filozofs získal svoju ľavú vidlicu, ale nemôže získať svoju pravú vidlicu, pretože ju už získal jeho sused. Táto situácia sa všeobecne nazýva kruhové čakanie a je jednou z podmienok, ktorá vedie k zablokovaniu a bráni pokroku v systéme.

6. Riešenie zablokovania

Ako sme videli vyššie, primárnym dôvodom zablokovania je podmienka kruhového čakania, keď každý proces čaká na zdroj, ktorý drží iný proces. Preto, aby sme sa vyhli zablokovaniu, musíme sa ubezpečiť, že je prerušená podmienka kruhového čakania. Existuje niekoľko spôsobov, ako to dosiahnuť, najjednoduchší je tento:

Všetci filozofi siahajú najskôr po svojej ľavej vidlici, okrem jedného, ​​ktorý najskôr siahne po svojej pravej vidlici.

Implementujeme to do nášho existujúceho kódu vykonaním relatívne malej zmeny v kóde:

verejná trieda DiningPhilosophers {public static void main (String [] args) vyvolá Výnimku {final Filozof [] filozofi = nový Filozof [5]; Vidlice objektu [] = nový objekt [philosophers.length]; for (int i = 0; i <forks.length; i ++) {forks [i] = new Object (); } for (int i = 0; i <philosophers.length; i ++) {Object leftFork = forks [i]; Object rightFork = vidlice [(i + 1)% vidlice.dĺžka]; if (i == philosophers.length - 1) {// Posledný filozof zdvihne pravú vidlicu prví filozofi [i] = nový Filozof (rightFork, leftFork); } else {filozofi [i] = nový Filozof (leftFork, rightFork); } Vlákno t = nové vlákno (filozofi [i], „Filozof“ + (i + 1)); t.start (); }}} 

Zmena prichádza v riadkoch 17-19 vyššie uvedeného kódu, kde uvádzame podmienku, vďaka ktorej posledný filozof najskôr siahne po svojej pravej vidlici namiesto ľavej. Týmto sa preruší podmienka kruhového čakania a môžeme odvrátiť zablokovanie.

Nasledujúci výstup ukazuje jeden z prípadov, keď všetky Filozofzískajú možnosť premýšľať a jesť bez toho, aby uviazli na mŕtvom bode:

Filozof 1 88519839556188: Thinking Philosopher 2 88519840186495: Thinking Philosopher 3 88519840647695: Thinking Philosopher 4 88519840870182: Thinking Philosopher 5 88519840956443: Thinking Philosopher 3 88519864404195: 885195 5 88519876989405: Zdvihnutá pravá vidlička - jedenie Filozof 2 88519935045524: Zdvihnutá ľavá vidlica Filozof 5 88519951109805: Položená pravá vidlica Filozof 4 88519997119634: Zdvihnutá pravá vidlica - jedenie Filozofa 5 885199971132k: Položená ľavá vidlica Späť k mysleniu Filozof 5 88520011135846: Thinking Filozof 1 88520011129013: Zdvihnutá ľavá vidlica Filozof 4 88520028194269: Položte pravú vidlicu Filozof 4 88520057160194: Položte ľavú vidlicu. Späť k mysleniu Filozof 3 88520067162257: Zdvihnutá pravá vidlica - jedenie Filozof 4 88520067158414: Thinking Filozof 3 88520160247801: Položte pravú vidlicu Filozof 4 88520249049308: Zdvihnite ľavú vidlicu Filozof 3 88520249119769: Položte ľavú vidlicu Späť k premýšľaniu 

Môže sa overiť niekoľkonásobným spustením kódu, že je systém bez zablokovania, ku ktorému došlo predtým.

7. Záver

V tomto článku sme preskúmali slávny problém Jedálni filozofi a koncepcie kruhového čakania a zablokovania. Naprogramovali sme jednoduché riešenie, ktoré spôsobilo zablokovanie, a vykonali sme jednoduchú zmenu, aby sa prerušilo kruhové čakanie a zabránilo sa zablokovaniu. Je to len začiatok a sofistikovanejšie riešenia existujú.

Kód tohto článku nájdete na GitHub.