Icke -blockerande algoritm - Non-blocking algorithm

Inte att förväxla med icke-blockerande I/O .

Inom datavetenskap kallas en algoritm icke-blockerande om fel eller avstängning av någon tråd inte kan orsaka fel eller avstängning av en annan tråd; för vissa operationer ger dessa algoritmer ett användbart alternativ till traditionella blockeringsimplementeringar . En icke-blockerande algoritm är låsfri om det finns garanterade systemövergripande framsteg och väntelös om det också är garanterat per tråds framsteg. "Icke-blockerande" användes som en synonym för "låsfritt" i litteraturen fram till introduktionen av hinderfrihet 2003.

Ordet "icke-blockerande" användes traditionellt för att beskriva telekommunikationsnät som kunde dirigera en anslutning genom en uppsättning reläer "utan att behöva ordna om befintliga samtal" (se Clos-nätverk ). Om telefonväxeln "inte är defekt kan den alltid göra anslutningen" (se icke -blockerande minimal spänningsomkopplare ).

Motivering

Huvudartikel: Nackdelar med lås

Det traditionella tillvägagångssättet för multi-threaded programmering är att använda lås för att synkronisera åtkomst till delade resurser . Synkroniseringsprimitiv som mutexes , semaforer och kritiska sektioner är alla mekanismer genom vilka en programmerare kan säkerställa att vissa kodavsnitt inte körs samtidigt, om det skulle skada delade minnesstrukturer. Om en tråd försöker skaffa ett lås som redan hålls av en annan tråd, blockeras tråden tills låset är ledigt.

Att blockera en tråd kan vara oönskat av många skäl. En uppenbar anledning är att även om tråden är blockerad kan den inte åstadkomma någonting: om den blockerade tråden hade utfört en högprioriterad eller realtidsuppgift skulle det vara mycket oönskat att stoppa dess framsteg.

Andra problem är mindre uppenbara. Till exempel kan vissa interaktioner mellan lås leda till felförhållanden som dödläge , livlås och prioriterad inversion . Att använda lås innebär också en avvägning mellan grovkornig låsning, vilket avsevärt kan minska möjligheterna till parallellitet och finkornig låsning, vilket kräver mer noggrann design, ökar låsningen och är mer benägen för buggar.

Till skillnad från blockeringsalgoritmer lider icke-blockerande algoritmer inte av dessa nackdelar och är dessutom säkra att använda i avbrottshanterare : även om den förhandsgängda tråden inte kan återupptas är framsteg fortfarande möjligt utan den. Däremot kan globala datastrukturer som skyddas av ömsesidigt uteslutning inte säkert nås i en avbrottshanterare, eftersom den föregående tråden kan vara den som håller låset - men detta kan enkelt åtgärdas genom att maskera avbrottsbegäran under den kritiska sektionen.

En låsfri datastruktur kan användas för att förbättra prestanda. En låsfri datastruktur ökar mängden tid som används i parallellkörning snarare än seriell körning, vilket förbättrar prestandan på en flerkärnig processor , eftersom åtkomst till den delade datastrukturen inte behöver serialiseras för att förbli sammanhängande.

Genomförande

Med några få undantag använder icke-blockerande algoritmer atom- läs-modifier-skriv- primitiv som hårdvaran måste tillhandahålla, varav den mest anmärkningsvärda är jämförelse och byte (CAS) . Kritiska sektioner implementeras nästan alltid med hjälp av standardgränssnitt över dessa primitiv (i allmänhet blockeras kritiska sektioner, även när de implementeras med dessa primitiv). På 1990-talet måste alla icke-blockerande algoritmer skrivas "nativt" med de underliggande primitiven för att uppnå acceptabel prestanda. Emellertid lovar det växande området för mjukvara transaktionsminne standardabstraktioner för att skriva effektiv icke-blockerande kod.

Mycket forskning har också gjorts för att tillhandahålla grundläggande datastrukturer som staplar , köer , uppsättningar och hashtabeller . Dessa gör att program enkelt kan utbyta data mellan trådar asynkront.

Dessutom är vissa icke-blockerande datastrukturer tillräckligt svaga för att kunna implementeras utan speciella atomprimitiv. Dessa undantag inkluderar:

  • en enkel läsare enkelskrivande ringbuffert FIFO , med en storlek som jämnt delar överflödet av en av de tillgängliga osignerade heltalstyperna, kan ovillkorligen implementeras säkert med endast en minnesbarriär
  • Läs-kopiera-uppdatering med en enda författare och valfritt antal läsare. (Läsarna är väntelösa; författaren är vanligtvis låsfri tills den behöver återta minnet).
  • Läs-kopiera-uppdatering med flera författare och valfritt antal läsare. (Läsarna är väntelösa; flera skribenter serierar i allmänhet med ett lås och är inte hinderfria).

Flera bibliotek använder internt låsfria tekniker, men det är svårt att skriva låsfri kod som är korrekt.

Vänta-frihet

Vänta-frihet är den starkaste icke-blockerande garantin för framsteg, som kombinerar garanterad systemomfattande genomströmning med svält- frihet. En algoritm är väntelös om varje operation har en gräns för antalet steg som algoritmen kommer att ta innan operationen slutförs. Den här egenskapen är avgörande för realtidssystem och är alltid trevlig att ha så länge prestationskostnaden inte är för hög.

Det visades på 1980-talet att alla algoritmer kan implementeras utan väntan, och många transformationer från seriekod, som kallas universella konstruktioner , har demonstrerats. Emellertid matchar den resulterande prestandan i allmänhet inte ens naiva blockeringsdesigner. Flera papper har sedan dess förbättrat prestandan för universella konstruktioner, men deras prestanda är fortfarande långt under blockerande konstruktioner.

Flera papper har undersökt svårigheten att skapa väntelösa algoritmer. Till exempel har det visat sig att de allmänt tillgängliga atomära villkorade primitiva, CAS och LL / SC , inte kan ge svält fria implementationer av många vanliga datastrukturer utan minneskostnader växer linjärt i antalet trådar.

Men i praktiken utgör dessa lägre gränser inte en verklig barriär eftersom att spendera en cachelinje eller exklusiv reservgranulat (upp till 2 KB på ARM) lagring per tråd i det delade minnet inte anses vara för dyrt för praktiska system (vanligtvis mängden lagra logiskt krävs är ett ord, men fysiskt CAS -operationer på samma cachelinje kommer att kollidera, och LL/SC -operationer i samma exklusiva reservgranulat kommer att kollidera, så mängden lagring som fysiskt krävs är större).

Väntelfria algoritmer var sällsynta fram till 2011, både inom forskning och i praktiken. Men 2011 presenterade Kogan och Petrank en väntelös köbyggnad på CAS- primitiv, allmänt tillgänglig på vanlig hårdvara. Deras konstruktion utökade den låsfria kön till Michael och Scott, vilket är en effektiv kö som ofta används i praktiken. Ett uppföljande papper av Kogan och Petrank gav en metod för att göra väntfria algoritmer snabba och använde denna metod för att göra väntelös kön praktiskt taget lika snabb som dess låsfria motsvarighet. Ett efterföljande dokument av Timnat och Petrank gav en automatisk mekanism för att generera väntelösa datastrukturer från låsfria. Således är väntelösa implementeringar nu tillgängliga för många datastrukturer.

Låsfrihet

Låsfrihet gör att enskilda trådar svälter men garanterar systemomfattande genomströmning. En algoritm är låsfri om, när programtrådarna körs under tillräckligt lång tid, åtminstone en av trådarna gör framsteg (för någon vettig definition av framsteg). Alla väntelösa algoritmer är låsfria.

I synnerhet om en tråd är avstängd garanterar en låsfri algoritm att de återstående trådarna fortfarande kan göra framsteg. Därför, om två trådar kan strida för samma mutexlås eller spinlock, är algoritmen inte låsfri. (Om vi ​​hänger upp en tråd som håller låset, blockeras den andra tråden.)

En algoritm är låsfri om oändligt ofta drift av vissa processorer kommer att lyckas i ett begränsat antal steg. Till exempel, om N -processorer försöker utföra en operation, kommer några av N -processerna att lyckas slutföra operationen i ett begränsat antal steg och andra kan misslyckas och försöka igen om de misslyckas. Skillnaden mellan väntelös och låsfri är att väntelös drift av varje process garanterat kommer att lyckas i ett begränsat antal steg, oavsett de andra processorerna.

I allmänhet kan en låsfri algoritm köras i fyra faser: att slutföra sin egen operation, assistera en hindrande operation, avbryta en blockerande operation och vänta. Att slutföra sin egen operation kompliceras av möjligheten till samtidig hjälp och abort, men är alltid den snabbaste vägen till slutförande.

Beslutet om när man ska assistera, avbryta eller vänta när ett hinder möts är en tvisthanterares ansvar . Detta kan vara mycket enkelt (stödja operationer med högre prioritet, avbryta sådana som har lägre prioritet) eller vara mer optimerade för att uppnå bättre genomströmning eller sänka latensen för prioriterade operationer.

Korrekt samtidig assistans är vanligtvis den mest komplexa delen av en låsfri algoritm och ofta mycket kostsam att utföra: inte bara bromsar den assisterande tråden, men tack vare mekaniken i delat minne kommer tråden som assisteras att bromsas också , om det fortfarande körs.

Obstruktion-frihet

Hindringsfrihet är den svagaste naturliga icke-blockerande framstegsgarantin. En algoritm är obstruktionsfri om en enda tråd som utförs isolerat (dvs med alla hindrande trådar avstängda) för ett begränsat antal steg kommer att slutföra sin operation. Alla låsfria algoritmer är hinderfria.

Obstruktionsfrihet kräver bara att en delvis avslutad operation kan avbrytas och ändringarna rullas tillbaka. Att släppa hjälp samtidigt kan ofta resultera i mycket enklare algoritmer som är lättare att validera. Att hindra systemet från att ständigt levande låsa är uppgiften för en stridshanterare.

Vissa hinderfria algoritmer använder ett par "konsistensmarkörer" i datastrukturen. Processer som läser datastrukturen läser först en konsistensmarkör, läser sedan relevant data i en intern buffert, läser sedan den andra markören och jämför sedan markörerna. Uppgifterna är konsekventa om de två markörerna är identiska. Markörer kan vara icke-identiska när läsningen avbryts av en annan process som uppdaterar datastrukturen. I ett sådant fall kasserar processen data i den interna bufferten och försöker igen.

Se även

Referenser

externa länkar