Semafor (programovanie): Rozdiel medzi revíziami

'''Semafor''', v programovaní, je zabezpečená [[premenná]] (entita zachovávajúca hodnotu) alebo premenná [[abstraktný dátový typ|abstraktného dátového typu]] (entita spájajúca viac premenných, ktoré môžu a nemusia byť číselné) ktoré nahrádzajú klasickú metódu pre obmedzenie prístupu k zdieľaným prostriedkom, ako [[zdieľaná pamäť]], v [[multiprogramovom]] prostredí (systém, kde sa spúšťa alebo chce spustiť viacero programov naraz). Semafory existujú vo veľa variantoch, avšak týmto pojmom obyčajne myslíme '''počítací semafor''', keďže '''binárny semafor''' je známy ako [[mutex]]. Počítací semafor je počítadlo pre množinu voľných zdrojov, skôr ako uzamykací/odomykací flag pre jeden zdroj. Vymyslel ho [[Edsger Dijkstra]].

 

Semafory sú klasické riešenie na predchádzanie [[race conditions]] a [[problém hladných filozofov|problému hladných filozofov]], aj keď nepredchádzajú vzniku [[deadlock|deadlock-u zdrojov]].

 

== Úvod ==

 

K semaforu možno pristupovať len pomocou nasledovných operácii. Tie, ktoré sú označené ako atomické, nemôžu byť prerušené (t. j. ak sa systém rozhodne, že je čas "zmeniť" proces, nemôže ho zmeniť uprostred týchto inštrukcií). Dôvod je popísaný nižšie.

 

P(Semaphore s) // Získanie zdroja

 

Všimnime si, že zvyšovanie premennej ''s'' nesmie byť prerušené a procedúra ''P'' nesmie byť prerušená, ak ''s'' je väčšie od 0. Toto sa dá dosiahnuť pomocou špeciálnej inštrukcie [[test-and-set]] (ak to v danej architektúre [[inštrukčná sada]] podporuje) alebo (ak to je [[jednoprocesorový systém]]) sa dá zakázať [[prerušenie]] na zabránenie prepnutia procesu.

 

Hodnota semafora je počet jednotiek, ktoré sú v našom zdroji voľné. (Ak je tam iba jedna jednotka, je použitý "[[Binárna sústava|binárny]] semafor" s hodnotami 0 alebo 1.) Procedúra ''P'' používa [[činné čakanie]] (vo svojom čase nerobí nič) alebo spí (povie systému, nech ju neplánuje), kým zdroj nie je dostupný, keď pri zobudení ho hneď získa pre seba. ''V'' je opak; po skončení jeho používania procesom jednoducho urobí zdroj znova dostupný. ''Init'' je použitý len na inicializovanie semaforu pred tým, ako sa použije. Procedúry ''P'' a ''V'' musia byť [[atomické (programovanie)|atomické]], čo znamená, že uprostred týchto procedúr nesmie byť naplánovaný žiadny iný proces, ktorý by na tomto semafore robil inú operáciu.

 

 

Skratky ''P'' a ''V'' pochádzajú z [[Dánčina|dánskych]] slov. ''V'' z ''verhoog'', t. j. "zvýšenie". Viac možností je však pre ''P'' (vrátane ''passeer'' pre "podať", ''probeer'' "skúsiť" a ''pakken'' "zobrať"), ale v podstate Dijkstra napísal, že spomínané ''P'' je z nového zloženého slova ''prolaag'',<ref>http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD74.PDF</ref> skratky pre ''probeer te verlagen'', čiže "skús-a-zníž" [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD51.html][http://lkml.org/lkml/2005/12/19/34]. Táto nejednoznačnosť vznikla pre nešťastnú charakteristiku dánčiny, kde slová ''zvýš'' a ''zníž'' obe začínajú na písmeno ''V'', a celé vypísané slová by boli veľmi ťažké na vyslovenie pre neznalcov dánčiny.

 

 

V [[programovací jazyk|programovacom jazyku]] [[ALGOL 68]], v [[Linux jadro|Linuxovom jadre]],<ref>[http://www.linuxgrill.com/anonymous/fire/netfilter/kernel-hacking-HOWTO-5.html#ss5.3 Kernel hacking howto na linuxgrill.com]</ref> a v niektorých anglických knihách, procedúry ''P'' a ''V'' sú nazývané ''down'' a ''up''. V niektorých príručkách zasa ''wait'' a ''signal'', ''acquire'' a ''release'' alebo ''pend'' a ''post''. Niektoré texty ich nazývajú ''procure'' a ''vacate'', aby sedeli s originálnymi dánskymi iniciálkami.

 

Aby sme sa vyhli činnému čakaniu, semafor môže mať priradenú [[fronta (dátová štruktúra)|frontu]] procesov (obyčajne [[FIFO|first-in, first-out]]). Ak proces vykoná procedúru ''P'' na semafore, ktorý má hodnotu 0, proces je pridaný do tejto fronty. Ak iný proces zvýši semafor vykonaním procedúry ''V'' a aspoň jeden proces je vo fronte semaforu, jeden z nich je vybratý a pokračuje vo svojom behu.

 

Počítací semafor možno rozšíriť o schopnosť vrátiť viac ako jednu 'jednotku' zo semafora. Takto skutočne pracuje UNIXový semafor. Upravené P a V procedúry:

 

P(Semaphore s, integer howmany)

 

Predpokladajme, že by si chceli dva procesy alokovať zásobníky. Jeden by chcel K zásobníkov a druhý L, kde K + L > N. Primitívna implementácia by volala K, resp. L, krát procedúru P na semafore v cykle. Avšak toto môže viesť k deadlocku: ak prvý proces dostane Z < K zásobníkov tak, že Z + L > N a operačný systém prepne na druhý proces, ktorý si začne tiež alokovať zásobníky, ten ich potom dostane N - Z (čo je menej ako L), semafor bude mať už 0 a teda druhý proces začne čakať. Prvý proces sa obnoví a pokúsi sa alokovať ďalší zásobník, ale semafor je stále 0 a teda aj on začne čakať. Žiaden s procesov teda nebude mať dostatok zásobníkov na pokračovanie činnosti a teda sa ani žiadne zásobníky uvoľnia. Teda sú zaseknuté v deadloku.

 

V modifikovanej verzii semaforu si prvý proces alokuje K zásobníkov na semafore, ktoré dostane v atomickej operácii, nechávajúc ešte N-K zásobníkov voľných na semafore. Potom príde druhý proces, ktorý sa bude snažiť získať L zásobníkov, ale to je viac ako je na semafore voľných a teda bude musieť čakať. Keď prvý proces skončí, uvoľní zásobníky a zvýši semafor, druhý proces môže byť zobudený a dostane všetky svoje zásobníky.

 

 

== Semafory v dnešnej dobe používané programátormi ==

Semafory sa stále bežne používajú v [[programovací jazyk|programovacích jazykoch]], ktoré nepodporujú inú priamejšiu formu synchronizácie. Sú to primitívne synchronizačné mechanizmy v mnohých [[operačný systém|operačných systémoch]]. Trend vo vývoji programovacích jazykov avšak smeruje k viac štruktúrovaným formám synchronizácie, ako [[monitor (synchronizácia)|monitory]] a [[kanál (programovanie)|kanály]]. Navyše semafory neriešia (viac-zdrojové) deadlocky, nechránia programátora pred ľahkými chybami znova použitia semafora, ktorý je už používaný tým istým procesom a uvoľnenia semafora na konci po použití.

 

 

== Ukážkové použitie ==

 

:Vlákno ''A'' potrebuje informáciu z dvoch databáz, kým môže pokračovať. Prístup k týmto databázam je kontrolovaný dvoma oddelenými vláknami ''B'' a ''C''. Tieto dve vlákna majú cyklus spracujúci správy; ktokoľvek kto potrebuje použiť jednu z daných databáz pošle dotaz do fronty korešpondujúcej databázy. Vlákno ''A'' inicializuje semafor ''S'' s <code>init(S,-1)</code>. ''A'' potom pošle požiadavku, vrátane pointra na semafor ''S'', pre obe vlákna ''B'' aj ''C''. Potom ''A'' zavolá <code>P(S)</code>, ktorý ho zablokuje. Zvyšné dve vlákna budú zatiaľ získavať informácie z databáz; keď skončia hľadanie danej informácie, zavolajú <code>V(S)</code> na zaslanom semafore. Až keď obe vlákna vykonali svoju prácu bude hodnota na semafore kladná a ''A'' môže pokračovať. Takto použitý semafor sa nazýva "počítací semafor."

 

Okrem počítacieho semafora je ešte napríklad "blokovací semafor". Blokovací semafor je semafor inicializovaný na 0. Potom ktorékoľvek vlákno pri zavolaní <code>P(S)</code> bude blokované, pokým iné vlákno nespraví <code>V(S)</code>. Toto je veľmi pekný spôsob konštrukcie medzi bežiacimi vláknami, ktoré majú byť kontrolované.

 

Najľahší prípad semafora je "binárny semafor", používaný na kontrolu prístupu k jedinému zdroju, čo je v princípe to isté ako [[mutex]]. Binárny semafor je stále inicializovaný na hodnotu 1. Keď chceme využiť zdroj, dané vlákno zavolá <code>P(S)</code> na zníženie hodnoty na 0 a vráti hodnotu 1 pomocou procedúry ''V'', keď je zdroj pripravený na uvoľnenie....

* [[Problém fajčiarov cigariet]]

* [[Problém hladných filozofov]]

* [[Problém čitateľov a zapisovateľov]]

* [[Problém spiaceho holiča]]

 

<references />

 

* ''Over Seinpalen (EWD 74)'', v ktorom Dijkstra uvádza koncept (po dánsky).

* ''The Little Book of Semaphores'', od Allena B. Downeyho, Green Tea Press.

 

== Externé odkazy ==

* [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD74.html Over Seinpalen (EWD 74)], v ktorom Dijkstra uvádza koncept (po dánsky)

* [http://www.opengroup.org/onlinepubs/009695399/basedefs/semaphore.h.html semaphore.h] programovací interface - The Open Group Base Specifications Issue 6, IEEE Std 1003.1 (EN)

* [http://codeproject.com/csharp/inprocsemaphore.asp Jednoduché použitie procesu v semafore v jazyku C#] (EN)

* [http://www.inet.sk/clanok/3752/synchronizacia-v-linuxe-semafory Iný popis tématiky a príklady v jazyku C] (SK)

* [http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/Semaphore.html J2SE class api/java/util/concurrent/Semaphore] (EN)

* [http://www.python.org/doc/lib/semaphore-objects.html Python Semaphore Objects] (EN)

* [http://cs.gmu.edu/cne/modules/ipc/ Inter-Process Communication Tutorial] (EN)

* [http://c2.com/cgi/wiki?SemaphoresForMutualExclusion Popis semaforov od Portland Pattern Repository] (EN)

* [http://greenteapress.com/semaphores/ ''The Little Book of Semaphores''], od Allena B. Downeyho (EN)

* [http://www.beatjapan.org/mirror/www.be.com/aboutbe/benewsletter/Issue26.html#Benaphores "BE Engineering Insights: Benaphores"], od Benoita Schillinga; detaily optimalizácie, ktoré môžu byť použité na implementáciu semaforov (EN)