Vi presenterar ett ramverk för effektiv tillämpning av statslös modellkontroll (SMC) på samtidiga program som körs under fragmentet Release-Acquire (RA) av C/C++11-minnesmodellen. Vårt tillvägagångssätt är baserat på att utforska de möjliga programbeställningar, som definierar i vilken ordning instruktioner för en tråd utförs, och läsa-från relationer, som anger hur läsningar få sina värden från skriver. Detta står i kontrast till tidigare tillvägagångssätt, som också utforskar de möjliga koherensordningarna, dvs. order mellan motstridiga texter. Eftersom oväntade testresultat såsom program kraschar eller påståenden överträdelser beror endast på avläsning-från relationen, undviker vi en potentiellt betydande källa till redundans. Vårt ramverk bygger på en ny teknik för att avgöra om en viss read-from relation är möjlig under RA semantiken. Vi definierar en SMC-algoritm som är bevisligen optimal i den meningen att den utforskar varje programordning och avläsning från relation exakt en gång. Detta optimala resultat är mycket starkare än tidigare jämförbara optimala resultat, som också tar hänsyn till samstämmigheten. Vi har implementerat vårt ramverk i verktyget Tracer. Experiment visar att Tracer kan vara betydligt snabbare än toppmoderna verktyg som kan hantera RA semantik. Optimal tillståndslös modell Kontrollera under Release-Acquire Semantics 135:3 Figur 1b 1. En DPOR algoritm baserad på Shasha-Snir spår (t.ex., [Abdulla et al. , 2016b) måste därför undersöka minst fyra avrättningar. Det är dock möjligt att ytterligare minska detta antal. Nämligen, en närmare inspektion visar att de två spåren τ 1 och τ 2 är likvärdiga, i den meningen att varje tråd går igenom samma sekvenser av lokala stater och beräknar samma resultat. Detta beror på att τ 1 och τ 2 har samma programordning (po) och read-from (rf) relation. Deras enda skillnad är hur skriver beställs av co, men detta är inte relevant för de beräknade resultaten. Det föregående exemplet visar att det finns en potential för att förbättra effektiviteten hos Dpor-algoritmer genom att använda en svagare ekvivalens som endast induceras av po och rf. I detta exempel, förbättringen är blygsam (minska antalet utforskade spår från fyra till tre), men det kan vara betydande, ibland även exponentiellt, för mer omfattande program. Flera nya Dpor tekniker försöker utnyttja den potential som erbjuds av en sådan svagare likvärdighet Huang 2015; Huang och Huang 2016; Norris och Demsky 2016]. Men, förutom det minimala fallet av en acyklisk kommunikationskurva, de är långt ifrån optimalt gör detta, eftersom de kan fortfarande utforska ett betydande antal olika utföranden med samma rf relation. Därför återstår utmaningen att definiera en mer effektiv DPOR-algoritm, som är optimal i den meningen att den utforskar just ett utförande i varje ekvivalensklass som induceras av po och rf. I detta dokument presenterar vi ett i grunden nytt tillvägagångssätt för att definiera DPOR-algoritmer, som optimalt utforskar endast de ekvivalensklasser som definieras av programordningen och avläsning från relationer. Vår metod är utvecklad för Release-Acquire (RA) fragmentet [Lahav et al. 2016 ] av C/C++11-minnesmodellen. RA är ett användbart och väluppfostrat fragment av C/C++11-minnesmodellen, vilket ger en bra balans mellan prestanda och programmerbarhet. I RA semantik, alla skriver är release accesses, medan alla avläsningar är förvärva åtkomster. RA möjliggör högpresterande implementeringar, men ger fortfarande tillräckligt starka garantier för grundläggande samtidiga algoritmer (såsom read-copy-update-mekanismen [Lahav et al. Europaparlamentets och rådets förordning (EU, Euratom) nr 966/2012 av den 25 oktober 2012 om finansiella regler för unionens allmänna budget och om upphävande av rådets förordning (EG, Euratom) nr 1605/2002 (EUT L 298, 26.10.2012, s. 1). Vår DPOR algoritm är baserad på ovanstående försvagning av Shasha-Snir spår, kallas svaga spår, som definieras av endast programordning och läsa-från relationer en utförande. Till exempel, programmet i Figur 1a har tre svaga spår, visas som τ 3, τ 4, och τ 5. Vår DPOR algoritm är bevisligen optimal för svaga spår, i den meningen att den utforskar just ett utförande för varje svag spår som är RA-konsistent, d.v.s. som kan utökas med viss samstämmighet relation som uppfyller begränsningarna i RA semantik. En viktig utmaning för vår DPOR-algoritm är att effektivt fastställa de fortsättningar av ett för närvarande utforskat spår som leder till vissa RA-konsistenta spår. T.ex., för programmet i Figur 1a, låter båda trådarna läsa från skrivandet av den andra tråden leder till RA-inkonsistens. Vi löser detta problem genom att definiera en mättnadsoperation, som utvidgar ett svagt spår med ett partiellt sammanhangsförhållande, som innehåller just de koherenskanter som måste finnas i varje motsvarande Shasha-Snir-spår. Under prospekteringen upprätthåller DPOR-algoritmen en mättad version av det för närvarande utforskade svaga spåret, och kan därför undersöka just de svaga spåren som är RA-konsistenta, utan att utföra meningslösa utforskningar. När en läshändelse läggs till bestämmer algoritmen den uppsättning skrivhändelser från vilka den kan få sitt värde samtidigt som RA-konsistens bevaras, och förgrenar sig i en separat fortsättning för varje sådan skrivhändelse. När en skrivhändelse läggs till lägger algoritmen bara till det till spåren. Det kan bevisas att detta bevarar RA-konsistensen, och även håller spåret mättat (en liten modifiering krävs för atomära read-modifiera-write händelser). Algoritmen måste också upptäcka om någon tidigare läsning kan läsa från en nytillagd text, och sedan bakåtspår för att låta skrivandet utföras innan den läses. Vi bevisar att vår DPOR algoritm inte utför något meningslöst arbete, i den meningen att (i) varje utforskning så småningom leder till en avslutad RA-konsistent utförande, dvs algoritmen aldrig 1 A Shasha-Snir spår innehåller också händelser som skriver ursprungliga värden, men dessa kan ignoreras för detta exempel.
För Release-Acquire semantics (RA) har REF utvecklat en DPOR algoritm som är optimal med avseende på rf ekvivalens.
Optimal stateless model checking under the release-acquire semantics
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}