Závodní podmínky - Race condition

„Kritická rasa“ přeadresuje tady. Pro akademické hnutí, viz kritickou rasovou teorii .
Závodní stav v logickém obvodu. Zde ∆ t 1 a ∆ t 2 představují zpoždění šíření logických prvků. Když se vstupní hodnota A změní z nízké na vysokou, obvod vydá krátkou dobu trvání (∆ t 1 + ∆ t 2 ) - ∆ t 2 = ∆ t 1 .

Spor nebo nebezpečí závod je podmínka z elektroniky , software nebo jiný systém , kde věcná chování systému je závislá na pořadí nebo načasování jiných nekontrolovatelných událostí. Stává se chyba , když jeden nebo více z možných chování je nežádoucí.

Pojem závodní podmínky byl již používán v roce 1954, například v doktorské práci Davida A. Huffmana „Syntéza sekvenčních spínacích obvodů“.

K závodním podmínkám může dojít zejména v logických obvodech , vícevláknových nebo distribuovaných softwarových programech.

V elektronice

Typický příklad rasy může nastat, když logická brána kombinuje signály, které cestovaly po různých cestách ze stejného zdroje. Vstupy do brány se mohou měnit v mírně odlišných časech v reakci na změnu zdrojového signálu. Výstup se může na krátkou dobu změnit na nežádoucí stav, než se vrátí zpět do navrženého stavu. Některé systémy mohou takové závady tolerovat, ale pokud tento výstup funguje jako hodinový signál například pro další systémy, které obsahují paměť, systém se může rychle odchýlit od svého navrženého chování (ve skutečnosti se dočasná závada stane trvalou závadou).

Zvažte například bránu se dvěma vstupy AND napájenou následující logikou:

Logický signál na jednom vstupu a jeho negace (¬ je logická negace ), na jiném vstupu teoreticky nikdy nezíská skutečnou hodnotu: Pokud však změny v hodnotě trvá déle, než se rozšíří na druhý vstup než na první když se změní z false na true, pak bude následovat krátká perioda, během které jsou oba vstupy pravdivé, a tak výstup brány bude také pravdivý.

Kritické a nekritické formy

Kritický Spor dochází, když je pořadí, ve kterém se změní vnitřní proměnné určuje případný stát, že státní stroj skončí v.

Nekritická Spor dochází, když je pořadí, ve kterém se změní vnitřní proměnné neurčuje případný stav, stavový stroj skončí v.

Statické, dynamické a esenciální formy

Stav statický závod nastane, když se signál a její komplement kombinovat.

Stav dynamický závod nastane, když to má za následek více přechodů, kdy pouze jeden je určen. Jsou způsobeny interakcí mezi branami. Lze jej eliminovat použitím maximálně dvou úrovní hradlování.

Zásadní spor nastane, když vstupní má dva přechody v době kratší než celková doba šíření zpětné vazby. Někdy jsou vytvrzeny pomocí indukčních zpožďovacích linkových prvků, aby se účinně prodloužila doba trvání vstupního signálu.

Řešení

Designové techniky, jako jsou mapy Karnaugh, vybízejí designéry, aby rozpoznali a odstranili závodní podmínky dříve, než způsobí problémy. Logická redundance může být často přidána k odstranění některých druhů ras.

Kromě těchto problémů mohou některé logické prvky vstupovat do metastabilních stavů , což vytváří další problémy pro návrháře obvodů.

V softwaru

V softwaru vzniká spor, když počítačový program, aby správně fungoval, závisí na posloupnosti nebo načasování procesů nebo vláken programu . Kritické závodní podmínky způsobují neplatné spuštění a chyby softwaru . Kritické rasy se často stávají, když procesy nebo vlákna závisí na nějakém sdíleném stavu. Operace ve sdílených stavech se provádějí v kritických sekcích, které se musí vzájemně vylučovat . Nedodržení tohoto pravidla může poškodit sdílený stav.

Datový závod je druh závodních podmínek. Datové závody jsou důležitou součástí různých formálních modelů paměti . Paměťový model definovaný ve standardech C11 a C ++ 11 uvádí, že program C nebo C ++ obsahující datovou rasu má nedefinované chování .

Rasy mohou být obtížně reprodukovatelné a laditelné, protože konečný výsledek je nedeterministický a závisí na relativním načasování mezi rušivými vlákny. Problémy tohoto druhu proto mohou zmizet při spuštění v režimu ladění, přidání dalšího protokolování nebo připojení ladicího programu. Chyba, která takto zmizí během pokusů o ladění, je často označována jako „ Heisenbug “. Je proto lepší vyhnout se závodním podmínkám pečlivým návrhem softwaru.

Příklad

Předpokládejme, že dvě vlákna zvyšují hodnotu globální celočíselné proměnné o 1. V ideálním případě by probíhala následující sekvence operací:

Vlákno 1 Vlákno 2 Celočíselná hodnota
0
číst hodnotu ← 0
zvýšit hodnotu 0
odepsat → 1
číst hodnotu ← 1
zvýšit hodnotu 1
odepsat → 2

V případě uvedeném výše je konečná hodnota 2, jak se očekávalo. Pokud však obě vlákna běží současně bez zamykání nebo synchronizace, může být výsledek operace špatný. Níže uvedený alternativní sled operací ukazuje tento scénář:

Vlákno 1 Vlákno 2 Celočíselná hodnota
0
číst hodnotu ← 0
číst hodnotu ← 0
zvýšit hodnotu 0
zvýšit hodnotu 0
odepsat → 1
odepsat → 1

V tomto případě je konečná hodnota 1 namísto očekávaného výsledku 2. K tomu dochází, protože zde se operace přírůstku vzájemně nevylučují. Vzájemně se vylučující operace jsou ty, které nelze přerušit při přístupu k nějakému prostředku, jako je umístění v paměti.

Datový závod

Ne všichni považují datové závody za podmnožinu závodních podmínek. Přesná definice datové rasy je specifická pro použitý formální model souběžnosti, ale obvykle se týká situace, kdy by se operace paměti v jednom vlákně mohla potenciálně pokusit o přístup k umístění paměti ve stejnou dobu, kdy je operace paměti v jiném vlákně zápis na toto paměťové místo v kontextu, kde je to nebezpečné. To znamená, že datová rasa se liší od rasy, protože je možné mít nedeterminismus kvůli načasování i v programu bez datových závodů, například v programu, ve kterém všechny přístupy do paměti používají pouze atomové operace .

To může být nebezpečné, protože na mnoha platformách, pokud dvě vlákna zapisují na místo v paměti současně, může být možné, aby místo v paměti skončilo s hodnotou, která je libovolnou a nesmyslnou kombinací bitů představujících hodnoty, které každé vlákno se pokoušelo zapsat; to může mít za následek poškození paměti, pokud je výsledná hodnota taková, kterou se ani jedno vlákno nepokoušelo zapsat (někdy se tomu říká ' roztrhaný zápis '). Podobně, pokud jedno vlákno čte z místa, zatímco do něj zapisuje jiné vlákno, může být možné, aby čtení vrátilo hodnotu, která je libovolnou a nesmyslnou kombinací bitů představujících hodnotu, kterou místo v paměti drželo před zápisem, a bitů představujících zapisovanou hodnotu.

Na mnoha platformách jsou pro simultánní přístup k dispozici speciální paměťové operace; v takových případech je typicky simultánní přístup pomocí těchto speciálních operací bezpečný, ale simultánní přístup pomocí jiných paměťových operací je nebezpečný. Někdy se takové speciální operace (které jsou bezpečné pro simultánní přístup) nazývají atomové nebo synchronizační operace, zatímco běžné operace (které nejsou pro simultánní přístup nebezpečné) se nazývají datové operace. To je pravděpodobně důvod, proč je termín datová rasa; na mnoha platformách, kde existuje spor, který zahrnuje pouze synchronizační operace, může být taková rasa nedeterministická, ale jinak bezpečná; ale datový závod by mohl vést k poškození paměti nebo nedefinovanému chování.

Příklad definic datových závodů v konkrétních souběžných modelech

Přesná definice datové rasy se mezi formálními modely souběžnosti liší. To je důležité, protože souběžné chování je často neintuitivní, a proto se někdy používá formální uvažování.

Standard C ++ , v návrhu N4296 (2014-11-19), definuje datový závod následovně v sekci 1.10.23 (strana 14)

Dvě akce jsou potenciálně souběžné, pokud

  • jsou prováděny různými vlákny, popř
  • jsou bez následků a alespoň jednu provádí obsluha signálu.

Spuštění programu obsahuje datový závod, pokud obsahuje dvě potenciálně souběžné konfliktní akce, z nichž alespoň jedna není atomová a k žádnému nedojde dříve, kromě speciálního případu pro popisovače signálu popsaného níže [vynecháno]. Každý takový datový závod má za následek nedefinované chování.

Části této definice týkající se obsluh signálů jsou pro C ++ výstřední a nejsou typické pro definice datové rasy .

Papír Detection Data Races on Weak Memory Systems poskytuje jinou definici:

„dvě operace paměti jsou v konfliktu, pokud přistupují ke stejnému umístění a alespoň jedna z nich je operace zápisu ...“ dvě operace paměti, x a y, v sekvenčně konzistentním provádění tvoří rasu 〈x, y〉, iff x a y konfliktu a nejsou uspořádány vztahem hb1 provádění. Závod 〈x, y〉, je datový závod, pokud alespoň jeden z x nebo y je datová operace.

Zde máme dvě paměťové operace přistupující ke stejnému umístění, z nichž jedna je zápis.

Relace hb1 je definována na jiném místě v příspěvku a je příkladem typického vztahu „ happening -before “; intuitivně, pokud dokážeme, že jsme v situaci, kdy je zaručeno, že jedna paměťová operace X bude dokončena před zahájením jiné paměťové operace Y, pak řekneme, že „X se stane-před Y“. Pokud se nestane „X před Y“ ani „Y před X“, pak říkáme, že X a Y „nejsou uspořádány vztahem hb1“. Klauzuli „... a nejsou uspořádány vztahem hb1 provádění“ lze tedy intuitivně přeložit jako „... a X a Y jsou potenciálně souběžné“.

Článek považuje za nebezpečné pouze ty situace, ve kterých je alespoň jedna z paměťových operací „datovou operací“; v jiných částech tohoto článku článek také definuje třídu „ synchronizačních operací “, které jsou bezpečné pro potenciálně současné použití, na rozdíl od „datových operací“.

Language specifikace Java poskytuje jinou definici:

Dva přístupy ke stejné proměnné (čtení nebo zápis do ní) jsou považovány za konfliktní, pokud alespoň jeden z přístupů je zápis ... Když program obsahuje dva konfliktní přístupy (§17.4.1), které nejsou objednány relace happening-before, prý obsahuje datový závod ... datový závod nemůže způsobit nesprávné chování, jako je vrácení nesprávné délky pro pole.

Zásadní rozdíl mezi přístupem C ++ a Java spočívá v tom, že v C ++ je datový závod nedefinovaným chováním, zatímco v Javě datový závod ovlivňuje pouze „akce mezi vlákny“. To znamená, že v C ++ by pokus o spuštění programu obsahujícího datovou rasu mohl (a přitom dodržovat specifikaci) havarovat nebo by mohl vykazovat nejisté nebo bizarní chování, zatímco v Javě může pokus o spuštění programu obsahujícího datovou rasu vyprodukovat nežádoucí chování souběžnosti, ale je jinak (za předpokladu, že implementace dodržuje specifikaci) bezpečné.

SC pro DRF

Důležitým aspektem datových závodů je, že v některých kontextech je program, který neobsahuje datové závody, zaručeně spuštěn sekvenčně konzistentním způsobem, což výrazně usnadňuje uvažování o souběžném chování programu. O formálních modelech paměti, které poskytují takovou záruku, se říká, že vykazují vlastnost „SC for DRF“ (Sequential Consistency for Data Race Freedom). Tento přístup údajně dosáhl nedávného konsensu (pravděpodobně ve srovnání s přístupy, které zaručují sekvenční konzistenci ve všech případech, nebo přístupy, které ji vůbec nezaručují).

Například v Javě je tato záruka přímo specifikována:

Program je správně synchronizován právě tehdy, pokud jsou všechny sekvenčně konzistentní spouštění bez datových závodů.

Pokud je program správně synchronizován, budou se všechna spuštění programu postupně shodovat (§17.4.3).

To je extrémně silná záruka pro programátory. Programátoři nemusí uvažovat o přeskupování, aby zjistili, že jejich kód obsahuje datové rasy. Při určování, zda je jejich kód správně synchronizován, proto nemusí uvažovat o změně pořadí. Jakmile je provedeno zjištění, že kód je správně synchronizován, programátor se nemusí obávat, že by změny pořadí ovlivnily jeho kód.

Program musí být správně synchronizován, aby se předešlo druhům neintuitivního chování, které lze pozorovat při změně pořadí kódu. Použití správné synchronizace nezaručuje, že celkové chování programu je správné. Jeho použití však umožňuje programátorovi jednoduchým způsobem uvažovat o možném chování programu; chování správně synchronizovaného programu je mnohem méně závislé na možné změně pořadí. Bez správné synchronizace je možné velmi podivné, matoucí a neintuitivní chování.

Naproti tomu návrh specifikace C ++ přímo nevyžaduje vlastnost SC pro DRF, ale pouze konstatuje, že existuje věta, která jej poskytuje:

[Poznámka: Je možné ukázat, že programy, které správně používají operace mutexes a memory_order_seq_cst k zabránění všem datovým rasám a nepoužívají žádné další synchronizační operace, se chovají tak, jako by operace prováděné jejich vlákny byly jednoduše proloženy, přičemž každý výpočet hodnoty objektu byl přijat. od posledního vedlejšího účinku na ten objekt v tom prokládání. Běžně se tomu říká „sekvenční konzistence“. To však platí pouze pro programy bez datových závodů a programy bez datových závodů nemohou sledovat většinu transformací programu, které nemění sémantiku programu s jedním vláknem. Ve skutečnosti je většina transformací programu s jedním vláknem nadále povolena, protože jakýkoli program, který se ve výsledku chová odlišně, musí provést nedefinovanou operaci.

Všimněte si toho, že návrh konceptu C ++ připouští možnost programů, které jsou platné, ale používají synchronizační operace s jinou paměťovou řádkou, než je paměťová_řádka_seq_cst, v takovém případě může být výsledkem program, který je správný, ale u kterého není poskytována žádná záruka postupné konzistence. Jinými slovy, v C ++ nejsou některé správné programy postupně konzistentní. Předpokládá se, že tento přístup poskytne programátorům C ++ svobodu volby rychlejšího spouštění programu za cenu toho, že se vzdají jednoduchého uvažování o svém programu.

Existují různé věty, často poskytované ve formě paměťových modelů, které poskytují SC pro záruky DRF v různých kontextech. Prostory těchto vět obvykle kladou omezení na paměťový model (a tedy na implementaci) a také na programátora; to znamená, že typicky je to tak, že existují programy, které nesplňují předpoklady věty a u kterých nebylo možné zaručit, že budou prováděny sekvenčně konzistentním způsobem.

Paměťový model DRF1 poskytuje SC pro DRF a umožňuje optimalizaci modelů WO (slabé uspořádání), RCsc ( konzistence uvolnění se sekvenčně konzistentními speciálními operacemi), paměťového modelu VAX a paměťových modelů bez datových závodů. Paměťový model PLpc poskytuje SC pro DRF a umožňuje optimalizaci modelů TSO ( Total Store Order ), PSO, PC ( Processor Consistency ) a RCpc ( Release Consistency with processor consistent special operations). DRFrlx poskytuje náčrt SC pro větu DRF za přítomnosti uvolněných atomů.

Zabezpečení počítače

Mnoho softwarových závodů má související důsledky na zabezpečení počítače . Rasa umožňuje útočníkovi s přístupem ke sdílenému prostředku způsobit nefunkčnost ostatních aktérů, kteří tento zdroj využívají, což má za následek efekty včetně odmítnutí služby a eskalace oprávnění .

Specifický druh rasy zahrnuje kontrolu predikátu (např. Pro autentizaci ), poté působení na predikát, zatímco stav se může měnit mezi časem kontroly a časem použití . Pokud tento druh chyby existuje v kódu citlivém na zabezpečení , vytvoří se chyba zabezpečení nazývaná chyba TOCTTOU ( time-of-check-to-time-of-use ).

Závodní podmínky se také záměrně používají k vytváření hardwarových generátorů náhodných čísel a fyzicky neuzavíratelných funkcí . PUF lze vytvořit navržením topologií obvodů se stejnými cestami k uzlu a spoléháním se na výrobní variace, které náhodně určí, které cesty se dokončí jako první. Měřením specifické sady výsledků závodních podmínek každého vyrobeného okruhu lze pro každý okruh shromáždit profil a uchovat jej v tajnosti, aby bylo možné později ověřit identitu okruhu.

Souborové systémy

Při pokusech o úpravu nebo přístup k systému souborů může dojít ke srážce dvou nebo více programů, což může mít za následek poškození dat nebo eskalaci oprávnění. Zamykání souborů poskytuje běžně používané řešení. Těžkopádnější náprava zahrnuje uspořádání systému tak, aby jeden jedinečný proces (spuštění démona nebo podobného) měl výhradní přístup k souboru a všechny ostatní procesy, které potřebují přístup k datům v tomto souboru, tak činily pouze prostřednictvím meziprocesové komunikace. s tím jediným procesem. To vyžaduje synchronizaci na úrovni procesu.

Jiná forma sporů existuje v souborových systémech, kde se nesouvisející programy mohou navzájem ovlivňovat tím, že najednou vyčerpají dostupné prostředky, jako je místo na disku, místo v paměti nebo cykly procesoru. Software, který není pečlivě navržen tak, aby předvídal a zvládal tuto rasovou situaci, se pak může stát nepředvídatelným. V systému, který se jeví jako velmi spolehlivý, může být takové riziko dlouhodobě přehlíženo. Nakonec se ale může nahromadit dostatek dat nebo může být přidáno dost jiného softwaru, který kriticky destabilizuje mnoho částí systému. Příkladem toho bylo, že nedlouho po přistání došlo téměř ke ztrátě „Spirit“ Mars Rover . Řešením je, aby si software před zahájením úkolu vyžádal a rezervoval všechny zdroje, které bude potřebovat; pokud tento požadavek selže, bude úkol odložen, čímž se vyhnete mnoha bodům, kde mohlo dojít k selhání. Alternativně může být každý z těchto bodů vybaven zpracováním chyb nebo úspěšnost celého úkolu lze ověřit poté, než budete pokračovat. Běžnějším přístupem je jednoduše ověřit, že je před spuštěním úkolu k dispozici dostatek systémových prostředků; to však nemusí být dostačující, protože ve složitých systémech mohou být akce jiných spuštěných programů nepředvídatelné.

Sítě

V síti zvažte distribuovanou chatovací síť jako IRC , kde uživatel, který spustí kanál, automaticky získá oprávnění provozovatele kanálu. Pokud se dva uživatelé na různých serverech, na různých koncích stejné sítě, pokusí spustit kanál se stejným názvem současně, příslušný server každého uživatele udělí každému uživateli oprávnění provozovatele kanálu, protože žádný server dosud neobdržel signál jiného serveru, že tomuto kanálu přidělil. (Tento problém byl do značné míry vyřešen různými implementacemi IRC serverů.)

V tomto případě rasy koncept „ sdíleného zdroje “ pokrývá stav sítě (jaké kanály existují a jaké uživatelé je spustili a mají tedy jaká oprávnění), které může každý server libovolně měnit, pokud signalizuje ostatním serverům v síti změny, aby mohli aktualizovat své pojetí stavu sítě. Nicméně, zpoždění v síti umožňuje druh spor popsáno. V tomto případě by odstartování závodních podmínek zavedením formy kontroly nad přístupem ke sdílenému zdroji - řekněme jmenování jednoho serveru, který by řídil, kdo má jaká oprávnění - znamenalo přeměnit distribuovanou síť na centralizovanou (alespoň pro tuto jednu část) provozu sítě).

Závodní podmínky mohou také existovat, když je počítačový program napsán s neblokujícími sokety . V takovém případě může být výkon programu závislý na rychlosti síťového připojení.

Životně důležité systémy

Softwarové chyby v životně důležitých systémech mohou být katastrofální. Mezi nedostatky stroje na radiační terapii Therac-25 patřily závodní podmínky , které vedly ke smrti nejméně tří pacientů a zranění několika dalších.

Dalším příkladem je systém energetického managementu poskytuje GE Energy a použitý Ohio založené FirstEnergy Corp (kromě jiných energetických zařízení). V podsystému alarmu existoval spor; když byla současně spuštěna tři klesající elektrická vedení, tento stav zabránil vyvolání výstrah monitorovacím technikům, což zpomalilo jejich povědomí o problému. Tato softwarová chyba nakonec vedla k severoamerickému výpadku proudu v roce 2003 . Společnost GE Energy později vyvinula softwarovou opravu k opravě dříve neobjevené chyby.

Nástroje

Existuje mnoho softwarových nástrojů, které pomáhají detekovat závodní podmínky v softwaru. Lze je z velké části rozdělit do dvou skupin: nástroje pro statickou analýzu a nástroje pro dynamickou analýzu .

Závit Bezpečnostní analýza je statický analytický nástroj pro analýzu anotace založené uvnitř procesní statické, původně zaveden jako pobočka gcc, a nyní znovu implementována v Clang , podporující pthreads.

Mezi dynamické analytické nástroje patří:

  • Intel Inspector , nástroj pro kontrolu a ladění paměti a vláken, který zvyšuje spolehlivost, zabezpečení a přesnost aplikací C/C ++ a Fortran; Intel Advisor , nástroj pro optimalizaci vektorizace SIMD založený na vzorkování a nástroj pro pomoc při vytváření závitů sdílené paměti pro vývojáře a architekty softwaru C, C ++, C#a Fortran;
  • ThreadSanitizer, který používá binární (na bázi Valgrind ) nebo zdrojové nástroje založené na LLVM a podporuje PThreads); a Helgrind, nástroj Valgrind pro detekci synchronizačních chyb v programech C, C ++ a Fortran, které používají primitiva vláken POSTH pthreads.
  • Data Race Detector je navržen tak, aby vyhledával datové závody v programovacím jazyce Go.

Existuje několik benchmarků navržených k vyhodnocení účinnosti nástrojů pro detekci datových závodů

  • DataRaceBench je srovnávací sada navržená k systematickému a kvantitativnímu vyhodnocování nástrojů pro detekci datových závodů, které analyzují vícevláknové aplikace napsané v OpenMP .

V jiných oblastech

Neuroscience ukazuje, že rasové podmínky mohou nastat také v mozku savců (potkanů).

V železniční signalizaci ve Velké Británii by při dodržování pravidla 55 došlo k rasovým podmínkám . Podle tohoto pravidla, pokud by vlak byl zastaven na běžící trati signálem, lokomotivní hasič by šel k stavědlu, aby připomněl signalistovi, že vlak byl přítomen. Minimálně v jednom případě, ve Winwicku v roce 1934, došlo k nehodě, protože spojař přijal další vlak, než dorazil hasič. Moderní signalizační praxe odstraňuje závodní podmínky tím, že umožňuje řidiči okamžitě kontaktovat rádiovou signalizační skříňku.

Viz také

Reference

externí odkazy