Problém spícího holiče

Problém spícího holiče je jeden z modelových případů, kdy v programu používajícím více vláken může nastat deadlock (uváznutí v mrtvém bodě). Za jeho autora je považován nizozemský informatik Edsger Dijkstra. Holič má pracovat, když jsou v holičství zákazníci a jinak spát. Holič a zákazníci jsou současně běžící procesy (vlákna) aplikace.

Popis problému

V hypotetickém holičství je jeden holič, jedna židle pro právě obsluhovaného zákazníka a více židlí v čekárně. Když holič ostříhá jednoho zákazníka, jde zkontrolovat čekárnu. Pokud zde čeká jiný zákazník, holič ho usadí na „pracovní“ židli a ostříhá ho. Pokud v čekárně není žádný zákazník, holič se posadí do své židle a spí.

Zákazník přicházející do holičství zjišťuje, co právě dělá holič. Pokud holič spí, zákazník jej vzbudí, posadí se na jeho židli a nechá se ostříhat. Pokud holič zrovna obsluhuje jiného zákazníka, nově příchozí zákazník se jde posadit do čekárny. Jsou-li všechny židle v čekárně obsazené, zákazník odejde a vrátí se později.

Problém v tomto příkladu nemusí být na první pohled zcela zřejmý. Pramení z toho, že činnosti holiče (kontrola čekárny) a zákazníků (kontrola stavu holiče, posazení se v čekárně…) trvají neznámou dobu. Program, který není proti deadlocku ošetřen, se může zaseknout v těchto případech:

  • Do holičství vejde zákazník a zjistí, že holič zrovna obsluhuje jiného zákazníka. Jde se tedy posadit do čekárny. Než ale do čekárny dojde, operační systém přidělí prostředky procesu holiče, který dostříhá stávajícího zákazníka a zkontroluje čekárnu, kde nikdo není. Jde tedy spát a čeká na zákazníka, zatímco zákazník v čekárně čeká na holiče.
  • Do holičství přijdou dva zákazníci najednou. V případě, že holič spí, oba se jej pokouší vzbudit a posadit se do jeho židle. Je-li holič zrovna zaneprázdněn, noví zákazníci se pokusí obsadit stejnou židli v čekárně. (Jinými slovy jeden proces změní stav volných židlí v čekárně, zatímco jiný proces tento údaj čte.)

Řešení

Pro řešení je nutné, aby zákazník měl možnost zjišťovat stav holiče (zdali stříhá jiného zákazníka, nebo spí) a aby jak zákazníci, tak holič mohli zjišťovat obsazenost čekárny. První z problémů zmíněných výše lze obejít tak, že zákazník bude kontrolovat stav holiče i pokud čekárna není prázdná. Příchod dalšího zákazníka tak naruší stav deadlocku. Není to ale optimální řešení a další problémy jím ošetřit nelze.

Problém spícího holiče má několik známých řešení. Základem všech z nich je vzájemné vyloučení přístupu ke sdíleným zdrojům. Sdílené zdroje představují holičova židle a čekárna. Pokud do holičství dorazí dva zákazníci zároveň, pouze jeden z nich může jít dovnitř a zkontrolovat stav holiče, případně holiče vzbudit, zatímco vlákno druhého zákazníka čeká. Čekárnu musí sdílet vlákna zákazníků i vlákno holiče, aby v jeden okamžik jen jeden zákazník mohl obsazovat židli a holič ani jiný zákazník během této činnosti nemohl zjišťovat obsazenost čekárny. V okamžiku, kdy jde holič zkontrolovat čekárnu, musí být zákazníkům zamezeno zjišťovat stav holiče.

Při použití zámků získává holič zámek v momentě, než jde zkontrolovat čekárnu a pouští jej, když začne stříhat zákazníka nebo jde spát. Zákazník musí získat zámek, než vstoupí do holičství, a uvolnit jej, když se posadí do holičovy židle nebo do čekárny.

Rozšířením původního problému spícího holiče je problém více spících holičů. Při jeho řešení je navíc nutno obstarat koordinaci mezi několika holiči, aby se například dva nepokoušeli ostříhat jednoho zákazníka.

Řešení s využitím semaforu

Následující pseudokód vyjadřuje jedno možné řešení za použití tří semaforů.

  • Deklarace proměnných:
 + Semaphore Customers = 0 // „fronta“ procesů zákazníků
 + Semaphore Barber = 0 // semafor holiče
 + Semaphore accessSeats = 1 // semafor židlí v čekárně
 + int NumberOfFreeSeats = N // počet volných židlí v čekárně

Semafor Customers udává počet zákazníků, kteří momentálně čekají na ostříhání a jeho hodnota může být maximálně počet židlí v čekárně. Barber je binární semafor holiče a accessSeats binární semafor čekárny. Operace P (snížení) na semaforu čekárny znamená výše popsané získání zámku – teprve nyní může holič nebo zákazník zjišťovat a měnit stav čekárny bez nebezpečí, že by stav mezitím měnilo jiné vlákno.

  • Proces holiče:
 while(true) { // běží v nekonečné smyčce
   P(Customers) // pokouší se získat zákazníka, pokud žádný není k dispozici, spí, dokud není probuzen
   (...)
   P(accessSeats) // holič je vzhůru a chystá se přijmout zákazníka z čekárny, nejdříve ale musí získat její zámek
   NumberOfFreeSeats++ // nyní může bezpečně uvolnit jednu židli
   V(Barber)  // nyní může zámek holiče získat některé z vláken zákazníků
   V(accessSeats) // uvolnění zámku čekárny
   (...) // zde holič stříhá zákazníka
 }
  • Proces zákazníka:
 while(true) { // běží v nekonečné smyčce
   P(accessSeats) // snaží se získat zámek čekárny
   if ( NumberOfFreeSeats > 0 ) { // nyní může zjistit, kolik židlí je volných
     NumberOfFreeSeats-- // je-li alespoň jedna volná, posadí se na ni
     V(Customers) // zvýší hodnotu semaforu Customers - upozorní holiče na nového zákazníka
     V(accessSeats) // uvolní zámek čekárny
     P(Barber) // snaží se získat zámek holiče; pokud je holič zaneprázdněný, semafor způsobí, že vlákno čeká (wait), dokud se zámek neuvolní
     (...) // zde je zákazník obsluhován holičem
   } else { // pokud nejsou volné žádné židle
     V(accessSeats) // musí vlákno ještě uvolnit zámek čekárny
     // zákazník odchází neostříhán
   }
 }

Výše popsaný algoritmus zabraňuje deadlocku. Jak lze však vidět na procesu zákazníka, může vyústit v situaci, kdy jeden zákazník opakovaně přichází do holičství a nikdy nenajde žádnou volnou židli v čekárně, tudíž nikdy není ostříhán. Proces tak nikdy nemůže doběhnout do konce a nastává situace nazývaná resource starvation neboli hladovění procesu po zdrojích.

Řešení v jazyce Java (s využitím synchronizace)

V Javě není třeba psát semafory, využijeme-li klíčové slovo synchronized. Program pak probíhá stejně, jako s použitím semaforů, ty však není třeba explicitně psát a o režii se stará virtuální stroj. Synchronizované mohou být celé metody (uvedením synchronized v hlavičce), vybrané bloky kódu (ve složených závorkách za synchronized) nebo datové kolekce. Synchronizovaný kód může v jednom okamžiku vykonávat pouze jedno vlákno, druhé příchozí vlákno musí čekat.

Synchronizované metody budou vypadat následovně:

  • ve třídě holiče metoda zjištění stavu a metoda/blok, během kterého probíhá stříhání; metody se budou volat z vlákna zákazníka
  • ve třídě obsluhující „čekárnu“ synchronizované metody pro zjištění počtu obsazených židlí (budou provádět zákazníci i holič), výběr zákazníka (bude provádět holič) a obsazení židle (budou provádět zákazníci). Tyto metody nahradí funkci semaforu Customers z předchozího příkladu, takže ve třídě zákazníka už žádné synchronizované metody potřeba nejsou.

Ještě snazším řešením je využití synchronizovaných front. Od verze 5 je součástí standardní instalace Javy také balíček java.util.concurrent, který obsahuje kromě jiného rozhraní (interface) BlockingQueue, jeho potomka BlockingDeque a několik jejich implementací. Fronta, jejíž kapacita je omezená, symbolizuje čekárnu. Pro programátora je nejjednodušší, aby vlákno holiče provádělo v nekonečné smyčce metodu take (výběr zákazníka z čekárny; je-li prázdná, vlákno holiče čeká) a vlákna zákazníků se zařazovaly do fronty metodou put (je-li čekárna plná, vlákno zákazníka čeká). V tomto případě ani není nutné zjišťovat obsazenost čekárny – fronta toto obstarává automaticky.

Jedna z implementací BlockingQueue, ArrayBlockingQueue, poskytuje volitelnou funkci „spravedlivosti“ (fairness policy). Při nastavení této volby na true se vlákna čekající na uvolnění kapacity ve frontě řadí dle pořadí příchodu, čímž řeší výše zmíněný problém hladovění po zdrojích.

Reference

V tomto článku byl použit překlad textu z článku Sleeping barber problem na anglické Wikipedii.

Externí odkazy

Související články