Problém spícího holiče: Porovnání verzí

'''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.

 

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í.

 

* 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.)

 

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.

 

Následující pseudokód vyjadřuje jedno možné řešení za použití tří [[Semafor (synchronizace)|semaforů]].

 

'''+ Semaphore Customers = 0''' // „fronta“ procesů zákazníků

'''+ Semaphore Barber = 0''' // semafor holiče

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.

 

'''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

'''}'''

 

'''while(true) {''' // běží v nekonečné smyčce

'''P(accessSeats)''' // snaží se získat zámek čekárny

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.

 

V [[Java (programovací jazyk)|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á [[Java (virtuální stroj)|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.

 

 

== Reference ==

 

== Externí odkazy ==