Løpstilstand - Race condition

"Kritisk rase" omdirigerer her. For den akademiske bevegelsen, se Critical race theory .
Løpetilstand i en logisk krets. Her representerer ∆ t 1 og ∆ t 2 forplantningsforsinkelsene til de logiske elementene. Når inngangsverdien A endres fra lav til høy, gir kretsen en kort varighet (∆ t 1 + ∆ t 2 ) - ∆ t 2 = ∆ t 1 .

En løpstilstand eller løpsfare er tilstanden til en elektronikk , programvare eller annet system der systemets vesentlige oppførsel er avhengig av sekvensen eller timingen for andre ukontrollerbare hendelser. Det blir en feil når en eller flere av de mulige atferdene er uønsket.

Begrepet race condition var allerede i bruk innen 1954, for eksempel i David A. Huffmans doktoravhandling "The synthesis of sequential switching circuits".

Løpeforhold kan oppstå spesielt i logikkretser , multitrådede eller distribuerte programmer.

I elektronikk

Et typisk eksempel på en løpstilstand kan oppstå når en logisk gate kombinerer signaler som har gått langs forskjellige stier fra samme kilde. Inngangene til porten kan endres på litt forskjellige tidspunkter som svar på en endring i kildesignalet. Utgangen kan i en kort periode endres til en uønsket tilstand før den går tilbake til den utformede tilstanden. Enkelte systemer kan tolerere slike feil, men hvis denne utgangen fungerer som et klokkesignal for for eksempel systemer som inneholder minne, kan systemet raskt avvike fra den designede oppførselen (den midlertidige feilen blir faktisk en permanent feil).

Tenk for eksempel på en to-inngang OG gate som er matet med følgende logikk:

Et logisk signal på en inngang og dens negasjon, (¬ er en boolsk negasjon ), på en annen inngang gir i teorien aldri en sann verdi: Hvis det imidlertid tar lengre tid å forandre seg til verdien til den andre inngangen enn den første når endringer fra falsk til sann vil det oppstå en kort periode hvor begge inngangene er sanne, og dermed vil portens utgang også være sanne.

Kritiske og ikke-kritiske former

En kritisk løpstilstand oppstår når rekkefølgen der interne variabler endres bestemmer den endelige tilstanden som tilstandsmaskinen vil havne i.

En ikke-kritisk løpstilstand oppstår når rekkefølgen der interne variabler endres ikke bestemmer den endelige tilstanden som tilstandsmaskinen vil havne i.

Statiske, dynamiske og viktige former

En statisk løpstilstand oppstår når et signal og dets komplement kombineres.

En dynamisk løpstilstand oppstår når det resulterer i flere overganger når bare en er beregnet. De skyldes interaksjon mellom porter. Det kan elimineres ved å bruke ikke mer enn to nivåer av gating.

En vesentlig løpstilstand oppstår når en inngang har to overganger på mindre enn den totale tilbakemeldingstiden. Noen ganger blir de kurert ved hjelp av induktive forsinkelseslinjeelementer for effektivt å øke tidsvarigheten til et inngangssignal.

Løsninger

Designteknikker som Karnaugh -kart oppfordrer designere til å gjenkjenne og eliminere løpsforhold før de forårsaker problemer. Ofte kan logisk redundans legges til for å eliminere noen typer løp.

I tillegg til disse problemene kan noen logiske elementer gå inn i metastabile tilstander , noe som skaper ytterligere problemer for kretsdesignere.

I programvare

En løpstilstand oppstår i programvare når et dataprogram, for å fungere skikkelig, avhenger av sekvensen eller tidspunktet for programmets prosesser eller tråder . Kritiske løpeforhold forårsaker ugyldig kjøring og programvarefeil . Kritiske raseforhold skjer ofte når prosessene eller trådene er avhengig av en delt tilstand. Operasjoner på delte stater utføres i kritiske seksjoner som må utelukke gjensidig . Unnlatelse av å følge denne regelen kan ødelegge den delte staten.

Et dataløp er en type løpstilstand. Dataraser er viktige deler av ulike formelle minnemodeller . Minnemodellen som er definert i C11- og C ++ 11 -standardene, spesifiserer at et C- eller C ++ - program som inneholder et datarase har udefinert oppførsel .

En løpstilstand kan være vanskelig å reprodusere og feilsøke fordi sluttresultatet er ubestemt og avhenger av den relative timingen mellom forstyrrende tråder. Problemer av denne art kan derfor forsvinne når du kjører i feilsøkingsmodus, legger til ekstra logging eller legger til en feilsøkingsprogram. En feil som forsvinner slik under feilsøkingsforsøk blir ofte referert til som en " Heisenbug ". Det er derfor bedre å unngå løpsforhold ved nøye programvaredesign.

Eksempel

Anta at to tråder hver øker verdien til en global heltallsvariabel med 1. Ideelt sett vil følgende operasjonsrekkefølge finne sted:

Tråd 1 Tråd 2 Heltall verdi
0
lese verdi ← 0
øke verdien 0
skrive tilbake → 1
lese verdi ← 1
øke verdien 1
skrive tilbake → 2

I tilfellet vist ovenfor er sluttverdien 2, som forventet. Men hvis de to trådene kjøres samtidig uten låsing eller synkronisering, kan utfallet av operasjonen være feil. Den alternative operasjonsrekkefølgen nedenfor viser dette scenariet:

Tråd 1 Tråd 2 Heltall verdi
0
lese verdi ← 0
lese verdi ← 0
øke verdien 0
øke verdien 0
skrive tilbake → 1
skrive tilbake → 1

I dette tilfellet er den endelige verdien 1 i stedet for det forventede resultatet på 2. Dette skjer fordi inkrementoperasjonene ikke utelukker hverandre. Gjensidig eksklusive operasjoner er de som ikke kan avbrytes mens du får tilgang til noen ressurser, for eksempel et minnested.

Dataløp

Ikke alle ser på dataløp som en delmengde av løpsforhold. Den presise definisjonen av datarase er spesifikk for den formelle samtidighetsmodellen som brukes, men refererer vanligvis til en situasjon der en minneoperasjon i en tråd potensielt kan forsøke å få tilgang til et minnelokasjon samtidig som en minneoperasjon i en annen tråd er skrive til det minnestedet, i en kontekst der dette er farlig. Dette innebærer at en datarase er forskjellig fra en rase -tilstand da det er mulig å ha ubestemmelse på grunn av timing selv i et program uten dataraser, for eksempel i et program der alle minnetilganger bare bruker atomoperasjoner .

Dette kan være farlig fordi på mange plattformer, hvis to tråder skriver til et minnested samtidig, kan det være mulig for minnestedet å ende opp med å ha en verdi som er en vilkårlig og meningsløs kombinasjon av bitene som representerer verdiene som hver tråd forsøkte å skrive; Dette kan resultere i hukommelseskorrupsjon hvis den resulterende verdien er en som ingen tråd forsøkte å skrive (noen ganger kalles dette en " revet skrive "). På samme måte, hvis en tråd leser fra et sted mens en annen tråd skriver til den, kan det være mulig for lesingen å returnere en verdi som er en vilkårlig og meningsløs kombinasjon av bitene som representerer verdien som minnestedet inneholdt før skrivingen, og bitene som representerer verdien som skrives.

På mange plattformer er det gitt spesielle minneoperasjoner for samtidig tilgang; i slike tilfeller er vanligvis samtidig tilgang ved bruk av disse spesialoperasjonene trygt, men samtidig tilgang ved bruk av andre minneoperasjoner er farlig. Noen ganger kan slike spesielle operasjoner (som er sikker for samtidig tilgang) kalles atom eller synkroniserings operasjoner, mens den normale virksomhet (som er usikre for samtidig tilgang) er kalt dataoperasjoner. Dette er trolig grunnen til at begrepet er data rase; på mange plattformer, der det er en løpstilstand som bare involverer synkroniseringsoperasjoner , kan et slikt løp være ubestemt, men ellers trygt; men en data løp kan føre til minnekorrupsjon eller udefinert atferd.

Eksempeldefinisjoner av dataraser i bestemte samtidighetsmodeller

Den presise definisjonen av datarase er forskjellig på tvers av formelle samtidighetsmodeller. Dette er viktig fordi samtidig oppførsel ofte er ikke-intuitiv, og derfor brukes formell resonnement noen ganger.

Den C ++ standard , i utkast N4296 (2014-11-19), definerer data løp som følger i seksjon 1.10.23 (side 14)

To handlinger er potensielt samtidige hvis

  • de utføres av forskjellige tråder, eller
  • de blir ikke sekvensert, og minst én blir utført av en signalbehandler.

Utførelsen av et program inneholder et datarase hvis det inneholder to potensielt samtidige motstridende handlinger, hvorav den ene ikke er atomisk, og ingen av dem skjer før den andre, bortsett fra spesialtilfellet for signalbehandlere beskrevet nedenfor [utelatt]. Enhver slik datarase resulterer i udefinert oppførsel.

Delene av denne definisjonen knyttet til signalbehandlere er særegne for C ++ og er ikke typiske for definisjoner av datarase .

Papiret Detecting Data Races on Weak Memory Systems gir en annen definisjon:

"to minneoperasjoner konflikter hvis de får tilgang til samme sted og minst en av dem er en skriveoperasjon ..." To minneoperasjoner, x og y, i en sekvensielt konsekvent utførelse danner et løp 〈x, y〉, iff x og y konflikt, og de er ikke ordnet av henrettelsesforholdet hb1. Løpet <x, y>, er en data løp iff minst en av x eller y er en dataoperasjon.

Her har vi to minneoperasjoner som får tilgang til samme sted, hvorav den ene er en skrive.

Hb1-forholdet er definert andre steder i avisen, og er et eksempel på en typisk " skjer-før " -relasjon; intuitivt, hvis vi kan bevise at vi er i en situasjon der en minneoperasjon X garantert vil bli utført til fullføring før en annen minneoperasjon Y begynner, så sier vi at "X skjer-før Y". Hvis verken "X skjer-før Y" eller "Y skjer-før X", så sier vi at X og Y er "ikke ordnet av hb1-forholdet". Så klausulen "... og de er ikke ordnet etter henvisningens hb1 -forhold" kan intuitivt oversettes som "... og X og Y er potensielt samtidige".

Papiret anser farlig bare de situasjonene der minst en av minneoperasjonene er en "dataoperasjon"; i andre deler av denne artikkelen definerer papiret også en klasse med " synkroniseringsoperasjoner " som er trygge for potensielt samtidig bruk, i motsetning til "dataoperasjoner".

The Java Language Specification gir en annen definisjon:

To tilganger til (leser av eller skriver til) den samme variabelen sies å være motstridende hvis minst én av tilgangene er en skrive ... Når et program inneholder to motstridende tilganger (§17.4.1) som ikke er bestilt av en skjer-før-forholdet, sies det å inneholde et datarase ... et datarase kan ikke forårsake feil oppførsel, for eksempel å returnere feil lengde for en matrise.

En kritisk forskjell mellom C ++-tilnærmingen og Java-tilnærmingen er at et dataløp i C ++ er udefinert oppførsel, mens et datarase i Java bare påvirker "inter-thread actions". Dette betyr at i C ++ kan et forsøk på å utføre et program som inneholder et datarase (mens det fortsatt holder seg til spesifikasjonen) krasje eller kunne utvise usikker eller bisarr oppførsel, mens et forsøk på å utføre et program som inneholder et datarase kan gi uønsket samtidighetsatferd, men er ellers (forutsatt at implementeringen overholder spesifikasjonen) trygg.

SC for DRF

En viktig fasett ved dataraser er at et program som er fritt for dataseraser i noen sammenhenger garantert vil bli utført på en konsekvent måte, noe som i stor grad letter begrunnelsen om programmets samtidige oppførsel. Formelle minnemodeller som gir en slik garanti sies å ha en "SC for DRF" (Sequential Consistency for Data Race Freedom) -egenskap. Denne tilnærmingen har blitt sagt å ha oppnådd nylig konsensus (antagelig sammenlignet med tilnærminger som garanterer sekvensiell konsistens i alle tilfeller, eller tilnærminger som ikke garanterer det i det hele tatt).

For eksempel i Java er denne garantien spesifisert direkte:

Et program er korrekt synkronisert hvis og bare hvis alle sekvensielt konsekvente henrettelser er fri for dataraser.

Hvis et program er korrekt synkronisert, ser det ut til at alle kjøringer av programmet er konsekvent (§17.4.3).

Dette er en ekstremt sterk garanti for programmerere. Programmerere trenger ikke resonnere om ombestillinger for å finne ut at koden inneholder dataseraser. Derfor trenger de ikke resonnere om ombestillinger når de skal avgjøre om koden er riktig synkronisert. Når først beslutningen om at koden er riktig synkronisert er gjort, trenger ikke programmereren å bekymre seg for at ombestillinger vil påvirke koden hans.

Et program må synkroniseres riktig for å unngå den typen kontraintuitiv atferd som kan observeres når koden omorganiseres. Bruk av riktig synkronisering sikrer ikke at den generelle oppførselen til et program er korrekt. Imidlertid tillater bruken en programmerer å resonnere om mulig oppførsel av et program på en enkel måte; oppførselen til et korrekt synkronisert program er mye mindre avhengig av mulige ombestillinger. Uten riktig synkronisering er veldig merkelig, forvirrende og kontraintuitiv atferd mulig.

Derimot krever et utkast C ++ - spesifikasjon ikke direkte en SC for DRF -eiendom, men observerer bare at det finnes et teorem som gir det:

[Merk: Det kan vises at programmer som bruker mutexes og memory_order_seq_cst -operasjoner på riktig måte for å forhindre alle dataraser og ikke bruker andre synkroniseringsoperasjoner, oppfører seg som om operasjonene som ble utført av deres bestanddeler bare var sammenflettet, med hver verdiregning av et objekt som ble tatt fra den siste bivirkningen på det objektet i den innfellingene. Dette blir vanligvis referert til som "sekvensiell konsistens". Imidlertid gjelder dette bare programmer uten data-løp, og programmer uten data-løp kan ikke observere de fleste programtransformasjoner som ikke endrer enkelttrådet programsemantikk. Faktisk er de fleste enkeltrådede programtransformasjoner fortsatt tillatt, siden ethvert program som oppfører seg annerledes som et resultat, må utføre en udefinert operasjon.-sluttnotat

Vær oppmerksom på at C ++ - utkastsspesifikasjonen innrømmer muligheten for programmer som er gyldige, men som bruker synkroniseringsoperasjoner med en annen minneordre enn memory_order_seq_cst, i så fall kan resultatet bli et program som er riktig, men som det ikke gis garanti for konsekvens i sekvens. Med andre ord, i C ++ er noen riktige programmer ikke konsekvent. Denne tilnærmingen antas å gi C ++ - programmerere friheten til å velge raskere programkjøring på bekostning av å gi opp enkel resonnement om programmet sitt.

Det er forskjellige teorier, ofte gitt i form av minnemodeller, som gir SC for DRF -garantier gitt forskjellige sammenhenger. Premissene til disse teoremene setter vanligvis begrensninger på både minnemodellen (og derfor på implementeringen), og også på programmereren; det vil si, vanligvis er det slik at det er programmer som ikke oppfyller teoremets premisser og som ikke kan garanteres å utføres på en konsekvent måte.

DRF1-minnemodellen gir SC for DRF og tillater optimalisering av WO (svak rekkefølge), RCsc ( Release Consistency med sekvensielt konsistente spesialoperasjoner), VAX-minnemodell og data-race-free-0-minnemodeller. PLpc -minnemodellen gir SC for DRF og tillater optimalisering av TSO -modellene ( Total Store Order ), PSO, PC ( Processor Consistency ) og RCpc ( Release Consistency with processor consistency special operations). DRFrlx gir en skisse av en SC for DRF -teorem i nærvær av avslappet atom.

Datasikkerhet

Mange programvareløpstilstander har tilknyttede datasikkerhetsimplikasjoner . En løpstilstand tillater en angriper med tilgang til en delt ressurs å få andre aktører som bruker denne ressursen til å fungere feil, noe som resulterer i effekter inkludert tjenestenekt og opptrapping av privilegier .

En bestemt type løpstilstand innebærer å se etter et predikat (f.eks. For autentisering ), deretter handle på predikatet, mens staten kan skifte mellom tidspunktet for kontroll og brukstidspunktet . Når denne typen feil finnes i sikkerhetskänslig kode, opprettes det et sikkerhetsproblem som kalles en time-of-check-to-time-of-use ( TOCTTOU ) feil.

Løpeforhold brukes også med vilje til å lage maskinvare tilfeldige tallgeneratorer og fysisk uklonable funksjoner . PUF kan opprettes ved å designe kretstopologier med identiske baner til en node og stole på produksjonsvariasjoner for å tilfeldig bestemme hvilke baner som skal fullføres først. Ved å måle hver produsert krets spesifikke sett med løpstilstandsresultater, kan en profil samles for hver krets og holdes hemmelig for senere å verifisere en krets identitet.

Filsystemer

To eller flere programmer kan kollidere i forsøkene på å endre eller få tilgang til et filsystem, noe som kan føre til datakorrupsjon eller eskalering av privilegier. Fillås er en vanlig løsning. Et mer tungvint middel innebærer å organisere systemet på en slik måte at en unik prosess (kjøring av en demon eller lignende) har eksklusiv tilgang til filen, og alle andre prosesser som trenger tilgang til dataene i den filen, gjør det bare via kommunikasjon mellom prosesser med den ene prosessen. Dette krever synkronisering på prosessnivå.

En annen form for rase -tilstand eksisterer i filsystemer der ikke -relaterte programmer kan påvirke hverandre ved plutselig å bruke opp tilgjengelige ressurser som diskplass, minneplass eller prosessorsykluser. Programvare som ikke er nøye designet for å forutse og håndtere denne løpssituasjonen, kan da bli uforutsigbar. En slik risiko kan overses lenge i et system som virker veldig pålitelig. Men etter hvert kan nok data samle seg eller nok annen programvare kan legges til for å destabilisere kritisk mange deler av et system. Et eksempel på dette skjedde med nesten tap av Mars Rover "Spirit" ikke lenge etter landing. En løsning er at programvare ber om og reservere alle ressursene den trenger før en oppgave påbegynnes; hvis denne forespørselen mislykkes, blir oppgaven utsatt, og man unngår de mange punktene der feil kan ha oppstått. Alternativt kan hvert av disse punktene utstyres med feilhåndtering, eller suksessen med hele oppgaven kan bekreftes etterpå, før du fortsetter. En mer vanlig tilnærming er å ganske enkelt kontrollere at det er nok systemressurser tilgjengelig før du starter en oppgave. Imidlertid er dette kanskje ikke tilstrekkelig fordi handlingene til andre kjørende programmer i komplekse systemer kan være uforutsigbare.

Nettverk

I nettverk kan du vurdere et distribuert chat-nettverk som IRC , der en bruker som starter en kanal automatisk skaffer seg kanaloperatørrettigheter. Hvis to brukere på forskjellige servere, i forskjellige ender av det samme nettverket, prøver å starte den samme navngitte kanalen samtidig, vil hver brukers respektive server gi kanal-operatørrettigheter til hver bruker, siden ingen server ennå har mottatt andre serverens signal om at den har tildelt den kanalen. (Dette problemet har i stor grad blitt løst av forskjellige IRC -serverimplementeringer.)

I dette tilfellet med en rase -tilstand dekker begrepet " delt ressurs " nettverkets tilstand (hvilke kanaler som finnes, så vel som hva brukerne startet dem og derfor har hvilke privilegier), som hver server fritt kan endre så lenge den signaliserer de andre serverne på nettverket om endringene slik at de kan oppdatere sin oppfatning av nettverkets tilstand. Imidlertid muliggjør latenstiden på tvers av nettverket den type løpstilstand som er beskrevet. I dette tilfellet ville det å slå av løpebetingelser ved å pålegge en form for kontroll over tilgang til den delte ressursen - si, utnevne en server til å kontrollere hvem som har hvilke privilegier - bety å gjøre det distribuerte nettverket til et sentralisert (i det minste for den ene delen av nettverksoperasjonen).

Løpeforhold kan også eksistere når et dataprogram er skrevet med ikke-blokkerende kontakter , i så fall kan programmets ytelse være avhengig av hastigheten på nettverkskoblingen.

Livskritiske systemer

Programvarefeil i livskritiske systemer kan være katastrofale. Løpstilstander var blant feilene i Therac-25 strålebehandlingsmaskinen , noe som førte til at minst tre pasienter døde og flere flere ble skadet.

Et annet eksempel er energistyringssystemet levert av GE Energy og brukt av Ohio -baserte FirstEnergy Corp (blant andre kraftanlegg). En løpstilstand eksisterte i alarmundersystemet; da tre slappe kraftledninger ble utløst samtidig, forhindret tilstanden at varsler ble reist til overvåkingsteknikerne, noe som forsinket deres bevissthet om problemet. Denne programvarefeilen førte til slutt til den nordamerikanske Blackout i 2003 . GE Energy utviklet senere en programvareoppdatering for å rette opp den tidligere uoppdagede feilen.

Verktøy

Det finnes mange programvareverktøy for å oppdage løpsforhold i programvare. De kan i stor grad kategoriseres i to grupper: statiske analyseverktøy og dynamiske analyseverktøy .

Trådsikkerhetsanalyse er et statisk analyseverktøy for annotasjonsbasert statisk analyse innen prosedyrer, opprinnelig implementert som en gren av gcc, og nå reimplementert i Clang , som støtter PThreads.

Dynamiske analyseverktøy inkluderer:

  • Intel Inspector , et minne- og trådkontroll- og feilsøkingsverktøy for å øke påliteligheten, sikkerheten og nøyaktigheten til C/C ++ og Fortran -applikasjoner; Intel Advisor , et samplingsbasert, SIMD -vektoriseringsoptimalisering og verktøy for deling av minnetråding for C, C ++, C#og Fortran programvareutviklere og arkitekter;
  • ThreadSanitizer, som bruker binær ( Valgrind -basert) eller kilde, LLVM -basert instrumentering, og støtter PThreads); og Helgrind, et Valgrind -verktøy for å oppdage synkroniseringsfeil i C, C ++ og Fortran -programmer som bruker POSIX pthreads threading primitives.
  • Data Race Detector er designet for å finne dataraser på Go Programming -språket.

Det er flere benchmarks designet for å evaluere effektiviteten av dataraseregistreringsverktøy

  • DataRaceBench er en benchmark-pakke designet for å systematisk og kvantitativt evaluere dataraseregistreringsverktøy som analyserer flertrådede applikasjoner skrevet i OpenMP .

På andre områder

Nevrovitenskap viser at rase forhold også kan forekomme i pattedyr (rotte) hjerner.

I britisk jernbanesignalering vil det oppstå en løpstilstand ved gjennomføringen av regel 55 . I henhold til denne regelen, hvis et tog ble stoppet på en løpende linje av et signal, ville lokomotivbrannmannen gå til signalboksen for å minne signalmannen om at toget var tilstede. I minst ett tilfelle, i Winwick i 1934, skjedde det en ulykke fordi signalmannen godtok et annet tog før brannmannen ankom. Moderne signalpraksis fjerner løpstilstanden ved å gjøre det mulig for føreren å umiddelbart kontakte signalboksen via radio.

Se også

Referanser

Eksterne linker