Versenyhelyzet

A versenyhelyzet (angolul race condition) egy hibalehetőség a digitális hálózatokban és a számítógépes programokban. Versenyhelyzet akkor áll fenn, ha a rendszer kimenete függ attól, hogy egymástól független folyamatok milyen sorrendben vagy mekkora időbeli eltéréssel hajtódnak végre. Ha az események nem a tervezett sorrendben hajtódnak végre, akkor hiba keletkezik. A versenyhelyzetet tartalmazó program hibásnak tekintendő.

Versenyhelyzet előfordul az emlősök agyában is. Ezt patkányokon mutatták ki.

Az angol elnevezés a Reading Egyetemen, a National Symposium of Logic Design rendezvény alkalmából jelent meg D. Zissostól 1969. március 28-án, a The British Computer Society közreműködésével.

A digitális technikában

Versenyhelyzet egy NEM és egy ÉS kapuból álló logikai áramkörben. A bemenő jel (A) megváltozásakor ∆t₁ illetve ∆t₂ idő kell ahhoz, hogy megváltozzon a NEM, illetve az ÉS kapu kimenő jele. Mivel az ÉS kapunak a NEM kapun át érkező bemenete később változik meg, mint a közvetlen bemenete, a kimenet egy rövid ideig 1 lesz, noha a logikailag helyes kimenet bármilyen bemenet esetén 0.

A digitális hálózatokban a versenyhelyzet a hazárdjelenségek egyike. Az egyes hálózati elemek eltérő jelterjedési ideje miatt a bemenet megváltozása egyes utakon hamarabb okoz változást, mint másokon, ezért a kimeneten rövid ideig hamis (sem a régi, sem az új kimenetnek nem megfelelő) állapot, ún. glitch jelenhet meg. Egyes rendszerek nem érzékenyek az ilyen glitchekre, más rendszereken azonban katasztrofális hatásuk lehet, például egy órajel esetében, aminek az állapotváltásai időzítik a többi áramköri elem működését memóriát használó rendszerek számára. Ebben az esetben a vezérelt rendszer viselkedése hamar megváltozhat, az ideiglenes glitchből tartós glitch lesz.

Olyan hálózatoknál, ahol a kimenet vissza van csatolva a bemenetre (sorrendi hálózat), a glitchek újabb állapotváltozásokat okoznak, és így a rendszer egyre távolabb kerülhet a tervezett működéstől; végül akár egy hibás stabil állapot is kialakulhat (kritikus versenyhelyzet).

A versenyhelyzetek elemzésének és elkerülésének egy lehetséges eszköze a Karnaugh-tábla. Egyes versenyhelyzetek kiküszöbölésére a számításokat redundánsan végzik el. Egy másik eszköz a szinkron sorrendi hálózatok használata; ezekben a kimenetet nem közvetlenül, hanem valamilyen memóriaelemen keresztül csatolják vissza, ami a bemenet megváltozásától egy adott ideig nem veszi figyelembe a kimenet értékét, így az ennél rövidebb ideig tartó glitcheknek nincs hatása.

Egyes logikai elemek metastabil állapotba is kerülhetnek, ami további problémákat okoz.

A versenyhelyzet kritikus, ha a belső változók megváltozásának sorrendje hat a végső állapotra.

Statikus, ha egy jelet komplementerével kombináljuk.

Dinamikus, ha egy elvárt átmenet helyett több állapotátmenet valósul meg. Oka a kapuk közötti interakció. Kiküszöbölhető, ha a rétegek számát kettőben korlátozzuk.

Lényeges, ha egy bemenet hatására két átmenet következik be a visszacsatolásig tartó időn belül. Gyakran késleltetéssel küszöbölik ki.

A számítástechnikában

A versenyhelyzet tipikusan a többszálas programokra és az elosztott rendszerekre jellemző. Az ilyen rendszerekben az egyes szálak vagy alrendszerek egymástól függetlenül, egyidejűleg működnek, ugyanakkor vannak közös erőforrások, amelyekhez mindannyian hozzáférnek. Ha az egyik szálnak a közös erőforrást érintő, egymásra épülő műveletei között egy másik szál is hozzáfér ugyanahhoz az erőforráshoz, az versenyhelyzetet okozhat. Az ilyen rendszerekben kölcsönös kizárással vagy hasonló technikákkal kell garantálni, hogy amíg egy adott szál összetartozó műveleteket végez egy közös erőforráson, addig a többi szál ne férhessen hozzá.

A C11 és C++11 szabványokban definiált memóriamodell a data race kifejezést használja azokra a versenyhelyzetekre, amelyekben megosztott adatokon hajtanak végre potenciálisan konkurrens műveleteket, amelyek közül legalább egy írás. Egy ilyet tartalmazó program viselkedése definiálatlan. A Java memóriamodell a Java 5-től kezdve különböző relációkon keresztül értelmezve viselkedést rendel a rosszul szinkronizált programokhoz is.

A versenyhelyzetek nevezetesek arról, hogy nehéz reprodukálni és debuggolni, mivel a program működése nemdeterminisztikus, és az egymással versengő szálak közötti viszonylagos időzítéstől függ. Minden beavatkozás a program működésébe azzal járhat, hogy megváltozik a viszonylagos időzítés, így lehet, hogy a naplózás vagy a debuggoló rendszer teljesen kijavítja a hibát; ezek nélkül a program azonban továbbra is néha hibásan működik. Sőt, a program bármilyen módosítása újra felszínre hozhatja a hibát, ami ismét csak néha fordul elő. A Heisenberg-törvényre utalva ezeket a hibákat heisenbugnak is hívják. Ezért minden olyan program hibásnak tekinthető, ami az ütemezéstől függ.

Példa

A következőben egy egyszerű példát mutatunk be, amiben két szál egy közös változó értékét megnöveli 1-gyel. Az elvárt futás a következő:

Két szál mindegyike megnöveli eggyel egy közös változó értékét.

1. szál		2. szál		Közös változó
				0
0	←			0
1	+			0
1	→			1
1		1	←	1
1		2	+	1
1		2	→	2

A fenti esetben a végeredmény 2, ahogy az elvárt. Azonban, ha nincs szinkronizáció, akkor a végeredmény ettől eltérhet. Egy alternatív műveletsorozatot az alábbi táblázat mutat:

A közös változó végső értéke a két szál időzítésétől függ.

1. szál		2. szál		Közös változó
				0
0	←			0
0		0	←	0
1	+	0		0
1		1	+	0
1	→	1		1
1		1	→	1

Ekkor a végeredmény 1 az elvárt 2 helyett. Ennek oka, hogy a hozzáférés kölcsönös kizárás nélkül történik. A kölcsönös kizárás azt jelenti, hogy egy másik szál nem férhet hozzá ahhoz az adathoz, amivel egy másik éppen műveleteket végez.

Biztonság

A versenyhelyzetnek következményei lehetnek biztonsági szempontból is. Ez lehetővé teszi, hogy a támadó hozzáférjen a megosztott erőforráshoz, így a többi aktor hibásan kezd viselkedni, ami okozhat szolgáltatásmegtagadást és a jogkör kiterjesztését eredményezheti.

Speciális helyzet adódik, ha egy predikátumot kell ellenőrizni, például azonosítás szempontjából. A predikátumon végzett műveletek hatására értéke megváltozhat az ellenőrzés és a használat között. Biztonságkritikus kódban az efféle hibát time-of-check-to-time-of-use (TOCTTOU) bugnak nevezik.

Versenyhelyzeteket szándékosan használnak hardveres véletlengenerátorokhoz és fizikailag klónozhatatlan függvényekhez (PUF). Ez utóbbiakhoz az áramkört úgy tervezik, hogy egy csúcs több úton is elérhető legyen, és véletlenszerűen lesz az egyik vagy másik gyorsabb.

Fájlrendszerek

Ha két vagy több program egyszerre fér hozzá egy fájlhoz, akkor az adatvesztéshez vagy a jogkör kiterjesztéséhez vezethet. A leggyakrabban alkalmazott módszer a fájlok zárolása. Egy másik lehetőség, hogy egy démonnak kizárólagos hozzáférése van a fájlhoz, és amelyik program hozzá akar férni, azt csak a démonnal kommunikálva teheti. Ez folyamatszintű szinkronizációt igényel.

Előfordulhat, hogy ugyan a programok nem férnek hozzá ugyanahhoz a fájlhoz, viszont versengenek egymással más erőforrásokért, tárhelyért, memóriáért, processzoridőért. A nem megfelelően tervezett programok viselkedése megjósolhatatlanná válhat. Egy nagyon megbízható rendszerben egy ilyen hiba sokáig elkerülheti a figyelmet, azonban a tárhely fogytával vagy túl sok program indításával a rendszer több része elveszti stabilitását. Erre példa, hogy majdnem elvesztették a kapcsolatot a Spirit marsjáróval nem sokkal a leszállás után. Egy megoldás, hogy a programnak először is le kell foglalnia a szükséges erőforrásokat, mielőtt végrehajtja feladatát. Ha ez nem sikerül, akkor addig vár, amíg az erőforrások fel nem szabadulnak. A program végezhet hibakezelést is, felkészülve ezzel ezekre a hibákra. További lehetőség, hogy minden feladat befejezésekor ellenőrzést végez, és ha nem sikerül, akkor visszagöngyölíti. Gyakoribb, hogy előzőleg ellenőrzi, hogy van elég erőforrás, de ez nem teljesen biztos, mivel megjósolhatatlan, hogy más programok mit fognak csinálni.

Hálózatok

Egy IRC-hez hasonló elosztott chat hálózatban az a felhasználó, amelyik megnyit egy csatornát, adminisztrátori jogot szerez arra a csatornára. Versenyhelyzet fordul elő, ha két felhasználó két szerverről ugyanazzal a névvel nyit csatornát ugyanoda, akkor mindketten megkapják az adminisztrátori jogot, mivel egyik szerver sem értesült arról, hogy ez a csatorna már meg van nyitva. Ezt a problémát azóta már megoldották az implementációk.

Ebben az esetben a megosztott erőforrásba beletartozik a hálózat állapota (mely csatornák léteznek, kik nyitották őket, ebből következően kiknek vannak előjogai). Ezt bármely szerver megváltoztathatja, de értesítenie kell a többi szervert a változásról. Azonban ez az információ lehet, hogy késve érkezik meg. Egy külön névszerver beiktatása, ami adminisztrálná a változásokat, központosítaná a hálózatot.

Versenyhelyzet nem blokkoló socketekkel is előfordulhat. Ekkor a program sebessége függhet a hálózati kapcsolat sebességétől.

Biztonságkritikus rendszerek

Biztonságkritikus rendszerekben a versenyhelyzet különösen nagy veszéllyel jár, hiszen nagy anyagi kárt, akár halált is okozhat. A Therac-25 sugárkezelő gép nyalábjait irányító rendszerek közötti versenyhelyzet legalább három beteg halálát és több beteg sérülését okozták.

Egy másik példa a GE Energy által alkotott Energy Management System. Ezt használta az Ohio központú FirstEnergy Corp is. A versenyhelyzet a figyelmeztető alrendszerben adódott. A rendszer nem figyelmeztetett, ha egyszerre legalább három távvezetékben adódott hiba, így azokat később vették észre. 2003 augusztus 14-én áramszünet alakult ki az Amerikai Egyesült Államok északkeleti részén és Ontario kanadai tartományban. Ezt a hibát a GE Energy javította.

Eszközök

A versenyhelyzet felismerését és kezelését több eszköz segíti. Ezek lehetnek statikus vagy dinamikus elemzők.

A Thread Safety Analysis statikus elemző annotációkon alapuló procedúrán belüli elemzést végez. Eredetileg a gcc egy ága tartalmazta, de a Clangben is megvalósították, ahol is támogatja a PThreads szálakat.

A dinamikus eszközök közé tartozik az Intel Inspector, ami ellenőrzi a szálakat, a memóriát, hogy növelje a megbízhatóságot, biztonságot és pontosságot Fortran, C és C++ alkalmazásokban. Az Intel Advisor mintavételezésen alapul, SIMD vektorizációs optimalizációt végez, továbbá szálkezelést és memóriahasználatot elemez C, C++, C# és Fortran programok számára. A ThreadSanitizer vizsgálja a forrást és a már lefordított bináris programot. LLVM alapú, támogatja a PThreads szálakat. A Helgrind egy Valgrind alapú eszköz, ami felderíti a szinkronizációs hibákat C, C++ és Fortran programokban, amelyek POSIX pthreads szálakkal működnek.

Források

• (1990. augusztus 1.) „Starvation and Critical Race Analyzers for Ada”. IEEE Transactions on Software Engineering 16 (8), 829–843. o. DOI:10.1109/32.57622. 
• Algorithms for the optimal state assignment of asynchronous state machines, Advanced Research in VLSI, 1995. Proceedings., 16th Conference on, 59–75. o.. DOI: 10.1109/ARVLSI.1995.515611 (1995. március 1.). ISBN 0-8186-7047-9  as PDF
• Paper "A Novel Framework for Solving the State Assignment Problem for Event-Based Specifications" by Luciano Lavagno, Cho W. Moon, Robert K. Brayton, and Alberto Sangiovanni-Vincentelli
• Wheeler, David A.: Secure programmer: Prevent race conditions—Resource contention can be used against you (PDF). IBM developerWorks, 2004. október 7. [2009. február 1-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. május 18.)
• Chapter "Avoid Race Conditions" (Secure Programming for Linux and Unix HOWTO)
• Race conditions, security, and immutability in Java, with sample source code and comparison to C code, by Chiral Software
• Karpov, Andrey: Interview with Dmitriy Vyukov — the author of Relacy Race Detector (RRD). Intel Software Library Articles, 2009. április 11.
• Microsoft Support description

Fordítás

• Ez a szócikk részben vagy egészben a Race condition című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.