Semafor (programování) - Semaphore (programming)

Semaforu ( holandský : seinpaal , termín je používán v Dijkstra původní popis).

Ve vědě o počítačích , je semafor je proměnná nebo abstraktní datový typ používá k řízení přístupu na společný zdroj rozmanitými procesy a vyhnout se kritická sekce problémy v současném systému, jako je multitasking operační systém. Triviální semafor je jednoduchá proměnná, která se mění (například zvyšuje nebo zmenšuje nebo přepíná) v závislosti na podmínkách definovaných programátorem.

Užitečným způsobem, jak uvažovat o semaforu používaném v reálném systému, je záznam o tom, kolik jednotek konkrétního zdroje je k dispozici, spolu s operacemi, které tento záznam bezpečně upravují (tj. Aby se předešlo závodním podmínkám ), protože jednotky jsou získané nebo uvolněné, a v případě potřeby počkejte, až bude k dispozici jednotka zdroje.

Semafory jsou užitečným nástrojem v prevenci rasových podmínek; jejich použití však v žádném případě nezaručuje, že program tyto problémy neobsahuje. Semafory, které umožňují libovolný počet zdrojů, se nazývají počítající semafory , zatímco semafory, které jsou omezeny na hodnoty 0 a 1 (nebo zamčené/odemčené, nedostupné/dostupné), se nazývají binární semafory a používají se k implementaci zámků .

Koncept semaforu vynalezl nizozemský počítačový vědec Edsger Dijkstra v roce 1962 nebo 1963, kdy Dijkstra a jeho tým vyvíjeli operační systém pro Electrologica X8 . Tento systém se nakonec stal známým jako multiprogramovací systém .

Analogie knihovny

Předpokládejme, že knihovna má 10 stejných studoven, které může používat vždy jeden student. Pokud chtějí studenti využít studovnu, musí si na recepci vyžádat pokoj. Pokud nejsou žádné pokoje volné, studenti čekají u stolu, dokud se někdo pokoje nevzdá. Když student dokončí používání místnosti, musí se vrátit ke stolu a uvést, že se jedna místnost uvolnila.

V nejjednodušší implementaci úředník na recepci zná pouze počet volných místností, které zná pouze správně, pokud všichni studenti svůj pokoj skutečně využijí, když se pro ně přihlásí a vrátí je, až budou hotovi . Když student požádá o pokoj, úředník toto číslo sníží. Když student uvolní místnost, úředník toto číslo zvýší. Místnost lze používat tak dlouho, jak je požadováno, a proto není možné rezervovat pokoje předem.

V tomto případě držitel počtu na recepci představuje semafor s počítáním, místnosti jsou prostředkem a studenti představují procesy/vlákna. Hodnota semaforu v tomto scénáři je zpočátku 10, přičemž všechny místnosti jsou prázdné. Když student požádá o pokoj, bude mu udělen přístup a hodnota semaforu se změní na 9. Poté, co přijde další student, klesne na 8, potom na 7 atd. Pokud někdo požaduje místnost a aktuální hodnota semaforu je 0, je nucen čekat, dokud se místnost neuvolní (když se počet zvýší z 0). Pokud byla jedna z místností uvolněna, ale čeká na ni několik studentů, lze libovolnou metodou vybrat toho, kdo místnost obsadí (například FIFO nebo házení mincí). A samozřejmě musí student informovat úředníka o uvolnění svého pokoje až poté, co ho opravdu opustí, jinak může nastat nepříjemná situace, když takový student opouští pokoj (balí si učebnice atd.) a další student vstoupí do místnosti, než ji opustí.

Důležitá pozorování

Když se semafor používá k řízení přístupu k fondu zdrojů, sleduje pouze to, kolik zdrojů je volných; nezaznamenává, které ze zdrojů jsou volné. K výběru konkrétního volného zdroje může být vyžadován nějaký jiný mechanismus (případně zahrnující více semaforů).

Paradigma je obzvláště silné, protože počet semaforů může sloužit jako užitečný spouštěč pro řadu různých akcí. Knihovník výše může zhasnout světla ve studovně, když nezůstanou žádní studenti, nebo může umístit ceduli, která říká, že pokoje jsou velmi obsazené, když je většina místností obsazena.

Úspěch protokolu vyžaduje, aby jej aplikace správně dodržovaly. Spravedlnost a bezpečnost budou pravděpodobně ohroženy (což prakticky znamená, že se program může chovat pomalu, chovat se nevyzpytatelně, zablokovat nebo havarovat ), pokud se i jeden proces chová nesprávně. To zahrnuje:

  • vyžádání zdroje a jeho zapomenutí uvolnit;
  • uvolnění zdroje, který nebyl nikdy požadován;
  • držení zdroje po dlouhou dobu, aniž byste jej potřebovali;
  • pomocí zdroje, aniž byste o něj nejprve požádali (nebo po jeho uvolnění).

I když všechny procesy dodržují tato pravidla, může dojít k zablokování více zdrojů, pokud existují různé zdroje spravované různými semafory a když procesy potřebují použít více než jeden zdroj najednou, jak ukazuje problém filozofů stolování .

Sémantika a implementace

Počítací semafory jsou vybaveny dvěma operacemi, historicky označovanými jako P a V ( alternativní názvy viz § Názvy operací ). Operace V zvyšuje semafor S a operace P jej zmenšuje.

Hodnota semaforu S je počet jednotek zdroje, které jsou aktuálně k dispozici. Operace P plýtvá časem nebo spí, dokud není k dispozici zdroj chráněný semaforem, kdy je zdroj okamžitě nárokován. Operace V je inverzní: zpřístupní zdroj znovu poté, co jej proces dokončí. Jednou z důležitých vlastností semaforu S je, že jeho hodnotu nelze změnit jinak než pomocí operací V a P.

Jednoduchý způsob, jak porozumět operacím čekání (P) a signálu (V), je:

  • čekat : Sníží hodnotu proměnné semaforu o 1. Pokud je nová hodnota proměnné semaforu záporná, proces provádějící čekání je blokován (tj. přidán do fronty semaforu). V opačném případě proces pokračuje v provádění, protože použil jednotku zdroje.
  • signál : Zvýší hodnotu proměnné semaforu o 1. Po přírůstku, pokud byla hodnota před přírůstkem záporná (to znamená, že procesy čekají na zdroj), přenese zablokovaný proces z fronty čekající na semafor do připravené fronty.

Mnoho operačních systémů poskytuje efektivní primafory semaforů, které odblokují proces čekání, když je semafor zvýšen. To znamená, že procesy neztrácejí čas zbytečnou kontrolou hodnoty semaforu.

Koncept počítání semaforu lze rozšířit o schopnost nárokovat nebo vrátit více než jednu „jednotku“ ze semaforu, což je technika implementovaná v Unixu . Upravené operace V a P jsou následující, pomocí hranatých závorek označují atomové operace , tj. Operace, které se zdají nedělitelné z pohledu jiných procesů:

function V(semaphore S, integer I):
    [S ← S + I]

function P(semaphore S, integer I):
    repeat:
        [if S ≥ I:
        S ← S − I
        break]

Zbývající část této části se však týká semaforů s unárními operacemi V a P, pokud není uvedeno jinak.

Aby se vyhnul hladovění , má semafor přidruženou frontu procesů (obvykle se sémantikou FIFO ). Pokud proces provádí operaci P na semaforu, který má hodnotu nula, proces se přidá do fronty semaforu a jeho provádění se pozastaví. Když jiný proces zvýší semafor provedením operace V a ve frontě jsou procesy, jeden z nich je odebrán z fronty a pokračuje v provádění. Pokud mají procesy různé priority, může být fronta seřazena podle priority, takže proces s nejvyšší prioritou je nejprve převzat z fronty.

Pokud implementace nezajistí atomičnost operací přírůstku, úbytku a srovnání, pak existuje riziko, že se na přírůstky nebo úbytky zapomene nebo že hodnota semaforu bude záporná. Atomicity lze dosáhnout použitím strojové instrukce, která je schopná číst, upravovat a zapisovat semafor v rámci jedné operace. Při absenci takové hardwarové instrukce může být atomická operace syntetizována použitím algoritmu vzájemného vyloučení softwaru . V uniprocesorových systémech lze atomické operace zajistit dočasným pozastavením předvolby nebo deaktivací hardwarových přerušení . Tento přístup nefunguje na víceprocesorových systémech, kde je možné, aby dva programy sdílející semafor běžely na různých procesorech současně. K vyřešení tohoto problému v systému s více procesory lze pomocí zamykací proměnné řídit přístup k semaforu. S proměnnou uzamčení se manipuluje pomocí příkazu test-and-set-lock .

Příklady

Triviální příklad

Uvažujme proměnnou A a logickou proměnnou S . K A se přistupuje pouze tehdy, když je S označeno jako true. Tak, S je semafor pro A .

Lze si představit signál semaforu ( S ) těsně před vlakovým nádražím ( A ). V tomto případě, pokud je signál zelený, lze vstoupit na vlakové nádraží. Pokud je žlutá nebo červená (nebo jiná barva), nelze se na nádraží dostat.

Přihlašovací fronta

Zvažte systém, který může podporovat pouze deset uživatelů (S = 10). Kdykoli se uživatel přihlásí, zavolá se P a sníží se semafor S o 1. Kdykoli se uživatel odhlásí, zavolá se V a zvýší S o 1, což představuje dostupný přihlašovací slot. Když je S 0, všichni uživatelé, kteří se chtějí přihlásit, musí počkat, dokud S > 0 a žádost o přihlášení se zařadí do fronty FIFO; vzájemné vyloučení se používá k zajištění toho, aby byly žádosti zařazeny do pořadí. Kdykoli se hodnota S stane větší než 0 (jsou k dispozici přihlašovací sloty), požadavek na přihlášení se odstraní a uživatel, který požadavek vlastní, se může přihlásit.

Problém výrobce a spotřebitele

V problému producent - spotřebitel jeden proces (výrobce) generuje datové položky a jiný proces (spotřebitel) je přijímá a používá. Komunikují pomocí fronty maximální velikosti N a podléhají následujícím podmínkám:

  • pokud je fronta prázdná, spotřebitel musí počkat, až výrobce něco vyrobí;
  • pokud je fronta plná, musí producent počkat, až spotřebitel něco spotřebuje.

Semaforové řešení problému producent - spotřebitel sleduje stav fronty dvěma semafory: emptyCountpočet prázdných míst ve frontě a fullCountpočet prvků ve frontě. Aby byla zachována integrita, emptyCountmůže být nižší (ale nikdy vyšší) než skutečný počet prázdných míst ve frontě a fullCountmůže být nižší (ale nikdy vyšší) než skutečný počet položek ve frontě. Prázdná místa a položky představují dva druhy zdrojů, prázdná pole a plná pole a semafory emptyCounta fullCountudržují kontrolu nad těmito prostředky.

Binární semafor useQueuezajišťuje, že integrita stavu samotné fronty není narušena, například dvěma producenty, kteří se pokoušejí přidat položky do prázdné fronty současně, čímž narušují její vnitřní stav. Alternativně lze místo binárního semaforu použít mutex .

Hodnota emptyCountzpočátku je N , fullCountje zpočátku 0 a useQueueje zpočátku 1.

Výrobce opakovaně provádí následující:

produce:
    P(emptyCount)
    P(useQueue)
    putItemIntoQueue(item)
    V(useQueue)
    V(fullCount)

Spotřebitel opakovaně provádí následující

consume:
    P(fullCount)
    P(useQueue)
    item ← getItemFromQueue()
    V(useQueue)
    V(emptyCount)

Níže je podstatný příklad:

  1. Jediný spotřebitel vstupuje do své kritické části. Protože fullCountje 0, spotřebitel blokuje.
  2. Několik producentů vstupuje do sekce kritické pro výrobce. Z důvodu omezení jejich vstupu nesmí do jejich kritické sekce vstoupit více než N producentů emptyCount.
  3. Producenti, jeden po druhém, získají přístup do fronty prostřednictvím useQueuea ukládají položky do fronty.
  4. Jakmile první výrobce opustí svou kritickou část, fullCountzvýší se, což jednomu spotřebiteli umožní vstoupit do její kritické sekce.

Všimněte si toho, že emptyCountmůže být mnohem nižší, než je skutečný počet prázdných míst ve frontě, například v případě, kdy jej mnozí producenti zmenšili, ale čekají, useQueueaž se zaplní, než zaplní prázdná místa. Všimněte si toho, že vždy platí, a to pouze tehdy, pokud žádní producenti ani spotřebitelé neprovádějí své kritické sekce. emptyCount + fullCount ≤ N

Názvy operací

Kanonická jména V a P pocházejí z iniciál holandských slov. V je obecně vysvětlován jako verhogen („zvýšení“). Pro P bylo nabídnuto několik vysvětlení, včetně proberen („otestovat“ nebo „vyzkoušet“), passeren („projít“) a pakken („chytit“). Dijkstra je nejčasnější papír na toto téma dává passering (“míjení”) jako význam pro P , a vrijgave (“vydání”) jako význam pro V. To také uvádí, že terminologie je převzata z toho použitý v železničních signálech. Dijkstra následně napsal, že má v úmyslu P zastupovat prolaag , zkratka pro sonda te verlagen , doslova „zkuste snížit“ nebo paralelně s výrazy používanými v druhém případě „zkuste snížit“.

V ALGOL 68 , linuxovém jádře a v některých učebnicích angličtiny se operace V a P nazývají nahoru a dolů . V praxi softwarového inženýrství se jim často říká signál a čekání , uvolnění a získání (což standardní knihovna Java používá) nebo post and pend . Některé texty je nazývají vyklidit a obstarat, aby odpovídaly původním holandským iniciálkám.

Semafory vs. mutexy

Mutex je blokovací mechanismus , který v některých případech používá stejnou základní provedení jako binární semaforu. Rozdíly mezi nimi jsou v tom, jak jsou používány. Zatímco binární semafor může být hovorově označován jako mutex, skutečný mutex má konkrétnější případ použití a definici, protože pouze úkol, který zamkl mutex, má jej odemknout. Cílem tohoto omezení je zvládnout některé potenciální problémy s používáním semaforů:

  1. Inverze priority : Pokud mutex ví, kdo jej zamkl, a má jej odemknout, je možné prosadit prioritu tohoto úkolu, kdykoli na mutexu začne čekat úkol s vyšší prioritou.
  2. Předčasné ukončení úkolu: Mutexy mohou také zajistit bezpečnost smazání, kde úkol držící mutex nemůže být omylem odstraněn.
  3. Zablokování ukončení: Pokud se úloha držení mutexu z jakéhokoli důvodu ukončí, OS může uvolnit mutex a signalizovat čekající úkoly této podmínky.
  4. Zablokování rekurze: Úkol je oprávněn zamknout reentrantní mutex vícekrát, protože jej odemkne stejně často.
  5. Náhodné uvolnění: Při uvolnění mutexu dojde k chybě, pokud uvolňovací úkol není jeho vlastníkem.

Viz také

Reference

externí odkazy

Úvod

Reference