Dela via

Programöverväganden utan lås för Xbox 360 och Microsoft Windows

Låsfri programmering är ett sätt att på ett säkert sätt dela föränderliga data mellan flera trådar utan kostnad för att hämta och frigöra lås. Detta låter som ett universalmedel, men låslös programmering är komplex och subtil, och ger ibland inte de fördelar som det lovar. Låsfri programmering är särskilt komplex på Xbox 360.

Låsfri programmering är en giltig teknik för flertrådad programmering, men den bör inte användas lätt. Innan du använder det måste du förstå komplexiteten, och du bör mäta noggrant för att se till att det faktiskt ger dig de vinster som du förväntar dig. I många fall finns det enklare och snabbare lösningar, till exempel att dela data mindre ofta, som bör användas i stället.

Att använda låsfri programmering korrekt och säkert kräver betydande kunskaper om både maskinvaran och kompilatorn. Den här artikeln ger en översikt över några av de problem som du bör tänka på när du försöker använda låslösa programmeringstekniker.

Programmering med lås

När du skriver kod med flera trådar är det ofta nödvändigt att dela data mellan trådar. Om flera trådar läser och skriver delade datastrukturer samtidigt kan minnesskada uppstå. Det enklaste sättet att lösa det här problemet är att använda lås. Om ManipulateSharedData till exempel bara ska köras av en tråd i taget kan en CRITICAL_SECTION användas för att garantera detta, som i följande kod:

// Initialize
CRITICAL_SECTION cs;
InitializeCriticalSection(&cs);

// Use
void ManipulateSharedData()
{
    EnterCriticalSection(&cs);
    // Manipulate stuff...
    LeaveCriticalSection(&cs);
}

// Destroy
DeleteCriticalSection(&cs);

Den här koden är tämligen enkel och okomplicerad och det är lätt att se att den är korrekt. Programmering med lås har dock flera potentiella nackdelar. Om två trådar till exempel försöker förvärva samma två lås men förvärvar dem i en annan ordning kan du få ett dödläge. Om ett program har ett lås för länge – på grund av dålig design eller på grund av att tråden har bytts ut av en tråd med högre prioritet – kan andra trådar blockeras under lång tid. Den här risken är särskilt stor på Xbox 360 eftersom programvarutrådarna tilldelas en maskinvarutråd av utvecklaren och operativsystemet inte flyttar dem till en annan maskinvarutråd, även om en är inaktiv. Xbox 360 har inte heller något skydd mot prioriterad inversion, där en tråd med hög prioritet snurrar i en loop i väntan på att en tråd med låg prioritet ska frigöra ett lås. Slutligen, om ett uppskjutet proceduranrop eller avbrottshanteringsrutin försöker ta ett lås, kan du få ett dödläge.

Trots dessa problem är synkroniseringsprimitiver, såsom kritiska avsnitt, generellt det bästa sättet att hantera flera trådar. Om synkroniseringens primitiver är för långsamma är den bästa lösningen vanligtvis att använda dem mindre ofta. Men för dem som har råd med den extra komplexiteten är ett annat alternativ låsfri programmering.

Låsfri programmering

Låslös programmering, som namnet antyder, är en serie tekniker för att på ett säkert sätt manipulera delade data utan att använda lås. Det finns låslösa algoritmer för att skicka meddelanden, dela listor och köer med data och andra uppgifter.

När du utför låsfri programmering finns det två utmaningar som du måste hantera: icke-atomiska åtgärder och omordning.

Icke-atomiska åtgärder

En atomisk åtgärd är en som är odelbar – en där andra trådar garanteras att aldrig se åtgärden när den är hälften klar. Atomiska operationer är viktiga för låslös programmering, eftersom andra trådar utan dem kan se halvskrivna värden eller annars inkonsekvent tillstånd.

På alla moderna processorer kan du anta att läsningar och skrivningar av naturligt anpassade inbyggda typer är atomiska. Så länge minnesbussen är minst lika bred som den typ som läses eller skrivs, läser och skriver processorn dessa typer i en enda busstransaktion, vilket gör det omöjligt för andra trådar att se dem i ett halvt slutfört tillstånd. På x86 och x64 finns det ingen garanti för att läsningar och skrivningar som är större än åtta byte är atomiska. Det innebär att SSE (Streaming SIMD Extensions) 16-byte-läsningar och -skrivningar av register, samt strängoperationer, kanske inte är atomiska.

Läsningar och skrivningar av typer som inte är naturligt anpassade – till exempel att skriva DWORD:er som korsar fyra bytes gränser – garanteras inte vara atomiska. Processorn kan behöva göra dessa läsningar och skrivningar som flera busstransaktioner, vilket kan göra att en annan tråd kan ändra eller se data mitt i läsningen eller skrivning.

Sammansatta åtgärder, till exempel sekvensen read-modify-write som inträffar när du ökar en delad variabel, är inte atomiska. På Xbox 360 implementeras dessa åtgärder som flera instruktioner (lwz, addi och stw), och tråden kan avbrytas mitt i sekvensen. På x86 och x64 finns det en enda instruktion (inc) som kan användas för att öka en variabel i minnet. Om du använder den här instruktionen är inkrementeringen av en variabel atomisk på system med en processor, men den är fortfarande inte atomisk i system med flera processorer. Att göra inc atomic på x86- och x64-baserade system med flera processorer kräver att låsprefixet används, vilket hindrar en annan processor från att göra sin egen läs-ändra-skriv-sekvens mellan läsningen och skrivning av inc-instruktionen.

Följande kod visar några exempel:

// This write is not atomic because it is not natively aligned.
DWORD* pData = (DWORD*)(pChar + 1);
*pData = 0;

// This is not atomic because it is three separate operations.
++g_globalCounter;

// This write is atomic.
g_alignedGlobal = 0;

// This read is atomic.
DWORD local = g_alignedGlobal;

Garantera atomitet

Du kan vara säker på att du använder atomiska åtgärder genom en kombination av följande:

  • Naturligt atomiska operationer
  • Låser för att omsluta sammansatta åtgärder
  • Operativsystemfunktioner som implementerar atomiska versioner av populära sammansatta åtgärder

Att öka en variabel är inte en atomisk åtgärd, och inkrementering kan leda till att data skadas om de körs på flera trådar.

// This will be atomic.
g_globalCounter = 0;

// This is not atomic and gives undefined behavior
// if executed on multiple threads
++g_globalCounter;

Win32 levereras med en serie funktioner som erbjuder atomiska läs- och ändringsskrivningsversioner av flera vanliga åtgärder. Dessa är InterlockedXxx-familjen av funktioner. Om alla ändringar av den delade variabeln använder dessa funktioner är ändringarna trådsäkra.

// Incrementing our variable in a safe lockless way.
InterlockedIncrement(&g_globalCounter);

Ordna om

Ett mer subtilt problem är att ordna om. Läsningar och skrivningar sker inte alltid i den ordning som du har skrivit dem i koden, vilket kan leda till mycket förvirrande problem. I många algoritmer med flera trådar skriver en tråd vissa data och skriver sedan till en flagga som talar om för andra trådar att data är klara. Detta kallas för en skrivversion. Om skrivningarna sorteras om kan andra trådar märka att flaggan har satts innan de kan se de skrivna data.

På samma sätt läser en tråd i många fall från en flagga och läser sedan vissa delade data om flaggan säger att tråden har fått åtkomst till delade data. Detta kallas för läs och hämta. Om läsningar sorteras om kan data läsas från delad lagring före flaggan och de värden som visas kanske inte är uppdaterade.

Omordning av läsningar och skrivningar kan göras både av kompilatorn och av processorn. Kompilatorer och processorer har gjort den här omordningen i flera år, men på datorer med en processor var det mindre av ett problem. Detta beror på att CPU-omorganisering av läsningar och skrivningar är osynlig på enprocessor-datorer (för kod som inte är en del av en enhetsdrivrutin), och kompilatorns omorganisering av läsningar och skrivningar är mindre sannolikt att orsaka problem på enprocessor-datorer.

Om kompilatorn eller processorn ordnar om skrivningarna som visas i följande kod kan en annan tråd se att flaggan alive har angetts samtidigt som de gamla värdena för x eller y visas. Liknande omorganisering kan inträffa vid läsning.

I den här koden lägger en tråd till en ny post i sprite-matrisen:

// Create a new sprite by writing its position into an empty
// entry and then setting the 'alive' flag. If 'alive' is
// written before x or y then errors may occur.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
g_sprites[nextSprite].alive = true;

I nästa kodblock läser en annan tråd från sprite-matrisen:

// Draw all sprites. If the reads of x and y are moved ahead of
// the read of 'alive' then errors may occur.
for( int i = 0; i < numSprites; ++i )
{
    if( g_sprites[nextSprite].alive )
    {
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

För att göra det här sprite-systemet säkert måste vi förhindra både kompilator- och CPU-omordning av läsningar och skrivningar.

Förstå CPU-omorganisering av skrivoperationer

Vissa processorer ordnar om skrivningar så att de är externt synliga för andra processorer eller enheter i icke-programordning. Denna omarrangering är aldrig synlig för enkeltrådad kod som inte är drivrutinkod, men den kan orsaka problem i kod med flera trådar.

Xbox 360

Även om Xbox 360-processorn inte ändrar ordning på instruktionerna ordnas skrivåtgärderna om, vilket slutförs efter själva instruktionerna. Denna omorganisering av skrivningar tillåts specifikt av PowerPC-minnesmodellens krav.

Skrivningar på Xbox 360 går inte direkt till L2-cachen. För att förbättra skrivbandbredden för L2-cachen går de istället igenom lagringsköer och vidare till lagringssamlingsbuffertar. Lagringsbuffertarna tillåter att 64-byte-block kan skrivas till L2-cachen i ett enda steg. Det finns åtta lagringsbuffertar som möjliggör effektiv skrivning till flera olika minnesområden.

Lagringsbuffertarna skrivs normalt till L2-cachen i FIFO-ordning (first-in-first-out). Men om målcacheraden för en skrivoperation inte finns i L2-cachen kan den här skrivningen fördröjas medan cacheraden hämtas från minnet.

Även om lagringsbuffertar skrivs till L2-cachen i strikt FIFO-ordning garanterar detta inte att enskilda skrivningar skrivs till L2-cachen i ordning. Anta till exempel att processorn skriver till plats 0x1000, sedan till plats 0x2000 och sedan till plats 0x1004. Den första skrivning allokerar en lagringsbuffert och placerar den framför kön. Den andra skrivningen allokerar en annan lagrings-samlingsbuffert och lägger den näst i kön. Den tredje skrivning lägger sina data till den första lagringsbufferten, som finns kvar längst fram i kön. Därför hamnar den tredje skrivningen i L2-cachen före den andra skrivningen.

Omordning som orsakas av lagringsinsamlingsbuffertar är i grunden oförutsägbar, särskilt eftersom båda trådarna på en kärna delar lagringsinsamlingsbuffertarna, vilket gör allokeringen och tömningen av dem mycket varierande.

Det här är ett exempel på hur skrivningar kan ordnas om. Det kan finnas andra möjligheter.

x86 och x64

Även om x86- och x64-processorer gör omordningsinstruktioner, ändrar de vanligtvis inte ordning på skrivåtgärder i förhållande till andra skrivningar. Det finns vissa undantag för sammanlagt skrivminne. Dessutom kan strängoperationer (MOVS och STOS) och 16-byte SSE-skrivningar ordnas om internt, men annars sorteras skrivningarna inte om inbördes.

Förstå CPU-omarrangemang av avläsningar

Vissa CPU:er ordnar om läsoperationer så att de effektivt kommer från delad lagring utanför programordning. Den här omarrangeringen är aldrig synlig för kod som är enkeltrådad och inte en drivrutin, men kan orsaka problem i kod med flera trådar.

Xbox 360

Cachemissar kan orsaka att vissa läsningar fördröjs, vilket i praktiken gör att läsningar kommer från delat minne i fel ordning, och tidpunkten för dessa cachemissar är i grunden oförutsägbar. Prefetching och förgreningsförutsägelse kan också leda till att data kommer från delat minne i oregelbunden ordning. Det här är bara några exempel på hur läsningar kan ordnas om. Det kan finnas andra möjligheter. Den här omorganiseringen av läsningar tillåts specifikt av PowerPC-minnesmodellen.

x86 och x64

Även om x86- och x64-processorer gör omordningsinstruktioner, ändrar de vanligtvis inte ordning på läsåtgärder i förhållande till andra läsningar. Strängåtgärder (MOVS och STOS) samt SSE-läsningar i 16-byte kan ordnas om internt, men annars ändras inte läsordningen inbördes.

Annan omordning

Även om x86- och x64-processorer inte ändrar ordning på skrivningar i förhållande till andra skrivningar eller ändrar ordning på läsningar i förhållande till andra läsningar, kan de sortera om läsningar i förhållande till skrivningar. Mer specifikt, om ett program skriver till en plats följt av läsning från en annan plats, kan läsdata komma från delat minne innan de skrivna data kommer dit. Den här omordningen kan bryta vissa algoritmer, till exempel Dekker-algoritmer för ömsesidig uteslutning. I Dekker-algoritmen anger varje tråd en flagga som anger att den vill ange den kritiska regionen och kontrollerar sedan den andra trådens flagga för att se om den andra tråden finns i den kritiska regionen eller försöker ange den. Den första koden följer.

volatile bool f0 = false;
volatile bool f1 = false;

void P0Acquire()
{
    // Indicate intention to enter critical region
    f0 = true;
    // Check for other thread in or entering critical region
    while (f1)
    {
        // Handle contention.
    }
    // critical region
    ...
}


void P1Acquire()
{
    // Indicate intention to enter critical region
    f1 = true;
    // Check for other thread in or entering critical region
    while (f0)
    {
        // Handle contention.
    }
    // critical region
    ...
}

Problemet är att läsningen av f1 i P0Acquire kan läsa från delad lagring innan skrivningen till f0 når delad lagring. Under tiden kan läsningen av f0 i P1Acquire läsa från gemensam lagring innan skrivningen av f1 når gemensam lagring. Nettoeffekten är att båda trådarna anger sina flaggor till TRUE, och båda trådarna ser den andra trådens flagga som FALSE, så båda går in i den kritiska regionen. Även om problem med omordning på x86- och x64-baserade system är mindre vanliga än på Xbox 360, kan de definitivt fortfarande inträffa. Dekker-algoritmen fungerar inte utan maskinvaruminnesbarriärer på någon av dessa plattformar.

x86- och x64-processorer ändrar inte ordning på en skrivning före en tidigare läsning. x86- och x64-processorer ändrar bara ordning på läsningar före tidigare skrivningar om de riktar in sig på olika platser.

PowerPC-processorer kan ordna om läsningar före skrivningar och kan ordna om skrivningar före läsningar, så länge de är till olika adresser.

Omordningssammanfattning

Xbox 360 CPU ordnar om minnesåtgärder mycket mer aggressivt än x86- och x64-processorer, vilket visas i följande tabell. Mer information finns i processordokumentationen.

Ändra ordning på aktivitet x86 och x64 Xbox 360
Läshandlingar som går före andra läshandlingar Nej Ja
Skrivningar som prioriteras framför andra skrivningar Nej Ja
Skrivningar prioriteras framför läsningar Nej Ja
Läsning prioriteras före skrivning Ja Ja

 

Read-Acquire och Write-Release Hinder

Huvudkonstruktionerna som används för att förhindra omordning av läsa och skriva kallas för read-acquire och write-release barriärer. En avläsning för att ta kontroll är en läsning av en flagga eller annan variabel för att få ägarskap av en resurs, tillsammans med en spärr mot omordning. På samma sätt är en skriv-frigivning en skrivning av en flagga eller annan variabel för att överföra ägarskapet av en resurs, tillsammans med ett hinder mot omordning.

De formella definitionerna, med tillstånd av Herb Sutter, är:

  • En läsoperation med hämtning körs innan alla senare läsningar och skrivningar av samma tråd i programordning.
  • En skrivversion körs efter alla läsningar och skrivningar av samma tråd som föregår den i programordning.

När din kod förvärvar ägarskap för något minne, antingen genom att skaffa ett lås eller genom att ta bort ett objekt från en delad länkad lista (utan lås), sker alltid en läsoperation: att testa en flagga eller pekare för att se om ägarskapet för minnet har förvärvats. Den här läsningen kan vara en del av en InterlockedXxx- operation, i vilket fall den innefattar både en läsning och en skrivning, men det är läsningen som avgör om ägarskap har erhållits. När ägarskapet för minnet har erhållits, läser man vanligtvis värden från eller skriver till det minnet. Det är mycket viktigt att dessa läsningar och skrivningar utförs efter att ägarskapet har erhållits. En läs-förvärvande barriärmekanism garanterar detta.

När ägarskapet för en del minne frigörs, antingen genom att ett lås frigörs eller genom att ett objekt skickas till en delad länkad lista, finns det alltid en skrivning som meddelar andra trådar om att minnet nu är tillgängligt för dem. Medan din kod hade ägarskap över minnet, läste den förmodligen från eller skrev till det, och det är mycket viktigt att dessa läsningar och skrivningar utförs innan ägarskapet frigörs. En skriv-släpp barriär garanterar detta.

Det är enklast att tänka på read-acquire och write-release barriärer som enskilda operationer. De måste dock ibland konstrueras från två delar: en läsning eller skrivning och en barriär som inte tillåter att läsningar eller skrivningar flyttas över den. I det här fallet är placeringen av barriären kritisk. För en läs-och-hämta-barriär kommer läsningen av flaggan först, sedan barriären och sedan läsningar och skrivningar av den delade datan. För en skrivfrisläppningsbarriär kommer läsningarna och skrivningarna av delade data först, sedan barriären och sedan flaggans skrivning.

// Read that acquires the data.
if( g_flag )
{
    // Guarantee that the read of the flag executes before
    // all reads and writes that follow in program order.
    BarrierOfSomeSort();

    // Now we can read and write the shared data.
    int localVariable = sharedData.y;
    sharedData.x = 0;

    // Guarantee that the write to the flag executes after all
    // reads and writes that precede it in program order.
    BarrierOfSomeSort();
    
    // Write that releases the data.
    g_flag = false;
}

Den enda skillnaden mellan en läs-acquire och en skriv-release är platsen för minnesbarriären. En read-acquire har barriären efter låsåtgärden, och en skriv-release har barriären före. I båda fallen ligger barriären mellan referenserna till det låsta minnet och referenserna till låset.

För att förstå varför hinder behövs både när du hämtar och när du lanserar data är det bäst (och mest exakt) att tänka på dessa hinder som att garantera synkronisering med delat minne, inte med andra processorer. Om en processor använder en skriv-frisättning för att frigöra en datastruktur till delat minne, och en annan processor använder en läs-inhämtning för att få åtkomst till den datastrukturen från delat minne, så kommer koden att fungera korrekt. Om någon av processorerna inte använder rätt barriär kan datadelningen misslyckas.

Det är viktigt att du använder rätt barriär för att förhindra kompilator- och CPU-omordning för din plattform.

En av fördelarna med att använda synkroniseringsprimiterna som tillhandahålls av operativsystemet är att alla innehåller lämpliga minnesbarriärer.

Förhindra omordning av kompilator

En kompilators uppgift är att aggressivt optimera koden för att förbättra prestandan. Detta inkluderar omorganisera instruktioner var det än är till hjälp och var det än inte kommer att ändra beteende. Eftersom C++ Standard aldrig nämner multitrådning, och eftersom kompilatorn inte vet vilken kod som måste vara trådsäker, förutsätter kompilatorn att koden är enkeltrådad när du bestämmer vilka omorganiseringar den kan göra på ett säkert sätt. Därför måste du berätta för kompilatorn när det inte är tillåtet att ordna om läsningar och skrivningar.

Med Visual C++ kan du förhindra omordning av kompilatorn med hjälp av kompilatorns inbyggda _ReadWriteBarrier. När du infogar _ReadWriteBarrier i koden kommer kompilatorn inte att flytta läsningar och skrivningar över den.

#if _MSC_VER < 1400
    // With VC++ 2003 you need to declare _ReadWriteBarrier
    extern "C" void _ReadWriteBarrier();
#else
    // With VC++ 2005 you can get the declaration from intrin.h
#include <intrin.h>
#endif
// Tell the compiler that this is an intrinsic, not a function.
#pragma intrinsic(_ReadWriteBarrier)

// Create a new sprite by filling in a previously empty entry.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
// Write-release, barrier followed by write.
// Guarantee that the compiler leaves the write to the flag
// after all reads and writes that precede it in program order.
_ReadWriteBarrier();
g_sprites[nextSprite].alive = true;

I följande kod läser en annan tråd från sprite-matrisen:

// Draw all sprites.
for( int i = 0; i < numSprites; ++i )
{

    // Read-acquire, read followed by barrier.
    if( g_sprites[nextSprite].alive )
    {
    
        // Guarantee that the compiler leaves the read of the flag
        // before all reads and writes that follow in program order.
        _ReadWriteBarrier();
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Det är viktigt att förstå att _ReadWriteBarrier inte infogar några ytterligare instruktioner och inte hindrar processorn från att ordna om läsningar och skrivningar– det hindrar bara kompilatorn från att ordna om dem. Därför räcker _ReadWriteBarrier när du implementerar en skrivfrisläppningsbarriär på x86 och x64 (eftersom x86 och x64 inte ändrar ordning på skrivningar och en normal skrivning räcker för att frigöra ett lås), men i de flesta andra fall är det också nödvändigt att förhindra att processorn ordnar om läsningar och skrivningar.

Du kan också använda _ReadWriteBarrier när du skriver till icke-cachebart skrivkombinerat minne för att förhindra omordning av skrivoperationer. I det här fallet hjälper _ReadWriteBarrier till att förbättra prestanda genom att garantera att skrivningar sker i processorns föredragna linjära ordning.

Det är också möjligt att använda _ReadBarrier och _WriteBarrier instruktioner för mer exakt kontroll över omordning av kompilatorn. Kompilatorn flyttar inte läsningar över en _ReadBarrieroch flyttar inte skrivningar över en _WriteBarrier.

Förhindra cpu-omordning

Cpu-omordningen är mer subtil än omordning av kompilatorn. Du kan aldrig se det hända direkt, du ser bara oförklarliga buggar. För att förhindra cpu-omordning av läsningar och skrivningar måste du använda instruktioner för minnesbarriärer på vissa processorer. Namnet på en minnesbarriär på Xbox 360 och i Windows är MemoryBarrier. Det här makrot implementeras på rätt sätt för varje plattform.

På Xbox 360 definieras MemoryBarrier som lwsync (lightweight sync), som även är tillgänglig via den __lwsync inbyggda funktionen, vilken definieras i ppcintrinsics.h. __lwsync fungerar också som en kompilatorminnesbarriär, vilket förhindrar omorganisera läsningar och skrivningar av kompilatorn.

Instruktionen lwsync är en minnesbarriär på Xbox 360 som synkroniserar en processorkärna med L2-cachen. Det garanterar att alla skrivningar före lwsync når L2-cachen innan några följande skrivningar. Det garanterar också att alla läsningar som följer lwsync inte får äldre data från L2 än tidigare läsningar. Den enda typ av omordning som den inte förhindrar är en läsning som går före en skrivning till en annan adress. Därför framtvingar lwsync minnesordning som matchar standardminnesordningen på x86- och x64-processorer. För att få fullständig minnesordning krävs den dyrare synkroniseringsinstruktionen (även kallat tungviktssynkronisering), men i de flesta fall krävs inte detta. Alternativen för minnesomordning på Xbox 360 visas i följande tabell.

Omordning av Xbox 360 Ingen synkronisering lwsync synkronisering
Läsningar som överstiger andra läsningar Ja Nej Nej
Förskrivningar som sker före skrivningar Ja Nej Nej
Skrivningar förekommer före läsningar Ja Nej Nej
Läsningar prioriteras framför skrivningar Ja Ja Nej

 

PowerPC har också synkroniseringsinstruktionerna isync och eieio (som används för att styra omordningen till cachelagringshämtat minne). Dessa synkroniseringsinstruktioner bör inte behövas för normal synkronisering.

I Windows definieras MemoryBarrier i Winnt.h och ger dig en annan minnesbarriärinstruktion beroende på om du kompilerar för x86 eller x64. Minnesbarriärinstruktionen fungerar som en fullständig barriär, vilket förhindrar all omordning av läsningar och skrivningar över barriären. Därför ger MemoryBarrier på Windows en starkare återordningsgaranti än den gör på Xbox 360.

På Xbox 360, och på många andra processorer, finns det ytterligare ett sätt att förhindra omlagring av läshantering av processorn. Om du läser en pekare och sedan använder pekaren för att läsa in andra data garanterar PROCESSORn att avläsningarna av pekaren inte är äldre än pekarens läsning. Om låsflaggan är en pekare och om alla läsningar av delade data görs via pekaren kan MemoryBarrier utelämnas, vilket ger en blygsam prestandabesparing.

Data* localPointer = g_sharedPointer;
if( localPointer )
{
    // No import barrier is needed--all reads off of localPointer
    // are guaranteed to not be reordered past the read of
    // localPointer.
    int localVariable = localPointer->y;
    // A memory barrier is needed to stop the read of g_global
    // from being speculatively moved ahead of the read of
    // g_sharedPointer.
    int localVariable2 = g_global;
}

Instruktionen MemoryBarrier förhindrar endast omordning av läsningar och skrivningar till cacheminne. Om du allokerar minne som PAGE_NOCACHE eller PAGE_WRITECOMBINE, en vanlig teknik för enhetsdrivrutinsförfattare och för spelutvecklare på Xbox 360, MemoryBarrier inte har någon effekt på åtkomsten till det här minnet. De flesta utvecklare behöver inte synkronisering av minne som inte går att cachelagrar. Det ligger utanför den här artikelns omfång.

Sammankopplade funktioner och cpu-omordning

Ibland görs läsningen eller skrivningen som hämtar eller släpper en resurs med någon av de InterlockedXxx-funktionerna. På Windows förenklar det här saker och ting, eftersom funktionerna InterlockedXxx i Windows alla är fullständiga minnesbarriärer. De har effektivt en CPU-minnesbarriär både före och efter dem, vilket innebär att de i sig är en fullständig read-acquire- eller write-release-barriär.

På Xbox 360 innehåller funktionerna InterlockedXxx inte processorminnesbarriärer. De förhindrar kompilatoromordning av läsningar och skrivningar, men inte CPU-omordning. I de flesta fall när du använder InterlockedXxx-funktioner på Xbox 360 bör du därför föregå eller följa dem med en __lwsyncför att göra dem till en läs-acquire- eller skriv-release-barriär. För enkelhetens skull och för enklare läsbarhet finns det Hämta och Frisläpp versioner av många av InterlockedXxx funktioner. Dessa levereras med en inbyggd minnesbarriär. Till exempel InterlockedIncrementAcquire gör en sammanflätad ökning följt av en __lwsync minnesbarriär för att ge fullständig läsinläsningsfunktion.

Vi rekommenderar att du använder Acquire and Release versioner av funktionerna InterlockedXxx (varav de flesta även är tillgängliga i Windows, utan prestandastraff) för att göra avsikten tydligare och för att göra det enklare att få instruktioner för minnesbarriären på rätt plats. All användning av InterlockedXxx på Xbox 360 utan minnesbarriär bör undersökas mycket noggrant, eftersom det ofta är en bugg.

Det här exemplet visar hur en tråd kan skicka uppgifter eller annan data till en annan tråd genom att använda versionerna av funktionerna Acquire och Release i InterlockedXxxSList. Funktionerna InterlockedXxxSList är en familj av funktioner för att underhålla en delad enkel länkad lista utan lås. Observera att Hämta och Frigöra varianter av dessa funktioner inte är tillgängliga på Windows, men de vanliga versionerna av dessa funktioner är en fullständig minnesbarriär på Windows.

// Declarations for the Task class go here.

// Add a new task to the list using lockless programming.
void AddTask( DWORD ID, DWORD data )
{
    Task* newItem = new Task( ID, data );
    InterlockedPushEntrySListRelease( g_taskList, newItem );
}

// Remove a task from the list, using lockless programming.
// This will return NULL if there are no items in the list.
Task* GetTask()
{
    Task* result = (Task*)
        InterlockedPopEntrySListAcquire( g_taskList );
    return result;
}

Flyktiga variabler och omordning

C++ Standard säger att läsningar av flyktiga variabler inte kan cachelagras, att flyktiga skrivningar inte kan fördröjas och att flyktiga läsningar och skrivningar inte kan flyttas förbi varandra. Detta räcker för att kommunicera med maskinvaruenheter, vilket är syftet med det flyktiga nyckelordet i C++ Standard.

Standardgarantierna räcker dock inte för att använda 'volatile' vid multitrådning. C++-standarden hindrar inte kompilatorn från att omordna icke-flyktiga läsningar och skrivningar i förhållande till flyktiga läsningar och skrivningar, och den säger inget om att förhindra omordning av CPU:n.

Visual C++ 2005 går utöver standard-C++ för att definiera multitrådsvänliga semantik för flyktig variabel åtkomst. Från och med Visual C++ 2005 definieras läsningar från volatile variabler som att ha läs-förvärvs-semantik, och skrivningar till volatile variabler definieras som att ha skriv-frigivnings-semantik. Det innebär att kompilatorn inte ordnar om några läsningar och skrivningar förbi dem, och i Windows ser det till att processorn inte heller gör det.

Det är viktigt att förstå att dessa nya garantier endast gäller för Visual C++ 2005 och framtida versioner av Visual C++. Kompilatorer från andra leverantörer implementerar vanligtvis olika semantik, utan de extra garantierna för Visual C++ 2005. På Xbox 360 infogar kompilatorn inte heller några instruktioner för att förhindra att processorn ändrar ordning på läsningar och skrivningar.

Exempel på en Lock-Free datapipe

Ett rör är en konstruktion som låter en eller flera trådar skriva data som sedan läss av andra trådar. En låsfri version av ett rör kan vara ett elegant och effektivt sätt att skicka arbete från tråd till tråd. DirectX SDK tillhandahåller LockFreePipe, ett låsfritt rör med enläsare, enskrivare, tillgängligt i DXUTLockFreePipe.h. Samma LockFreePipe finns i Xbox 360 SDK i AtgLockFreePipe.h.

LockFreePipe kan användas när två trådar har en producent-/konsumentrelation. Producenttråden kan skriva data till kanalen så att konsumenttråden kan bearbeta dem vid ett senare tillfälle, utan att någonsin blockeras. Om röret fylls upp misslyckas skrivoperationer, och producenttråden måste försöka igen senare, men detta skulle bara hända om producenttråden ligger före. Om röret blir tomt misslyckas läsningarna och konsumenttråden måste försöka på nytt senare, men detta sker bara om det inte finns något arbete för konsumenttråden att göra. Om de två parallella trådarna är välbalanserade och röret är tillräckligt stort, kan röret låta dem smidigt skicka data utan några fördröjningar eller blockeringar.

Xbox 360-prestanda

Prestandan för synkroniseringsinstruktioner och funktioner på Xbox 360 varierar beroende på vilken annan kod som körs. Det tar mycket längre tid att hämta lås om en annan tråd för närvarande äger låset. InterlockedIncrement och kritiska avsnittsåtgärder kommer att ta mycket längre tid om andra trådar skriver till samma cachelinje. Innehållet i butiksköerna kan också påverka prestanda. Därför är alla dessa tal bara approximationer, som genereras från mycket enkla tester:

  • lwsync mättes till 33-48 cykler.
  • InterlockedIncrement tog 225–260 cykler.
  • Att förvärva eller släppa ett kritiskt avsnitt mättes till att ta cirka 345 cykler.
  • Att låsa upp eller släppa en mutex beräknades ta cirka 2350 cykler.

Windows-prestanda

Prestandan för synkroniseringsinstruktioner och funktioner i Windows varierar mycket beroende på processortyp och konfiguration och på vilken annan kod som körs. System med flera kärnor och flera socketar tar ofta längre tid att köra synkroniseringsinstruktioner, och det tar mycket längre tid att hämta lås om en annan tråd för närvarande äger låset.

Men även vissa mått som genereras från mycket enkla tester är användbara:

  • MemoryBarrier beräknades ta 20-90 cykler.
  • InterlockedIncrement mätts till att ta 36-90 cykler.
  • Att förvärva eller frigöra ett kritiskt avsnitt mättes till att ta 40–100 cykler.
  • Att förvärva eller släppa en mutex mättes som att ta cirka 750-2500 cykler.

Dessa tester gjordes på Windows XP på en rad olika processorer. De korta tiderna var på en dator med en processor och de längre tiderna var på en dator med flera processorer.

Även om det är dyrare att skaffa och frigöra lås än att använda låsfri programmering, är det ännu bättre att dela data mindre ofta, vilket undviker kostnaden helt och hållet.

Prestanda tankar

Att hämta eller frigöra ett kritiskt avsnitt består av en minnesbarriär, en InterlockedXxx--åtgärd och lite extra kontroll för att hantera rekursion och att återgå till en mutex om det behövs. Du bör vara försiktig med att implementera ditt eget kritiska avsnitt, eftersom att snurra i en loop medan man väntar på att ett lås ska bli ledigt, utan att använda en mutex som reservlösning, kan orsaka betydande prestandaförlust. För kritiska avsnitt som är starkt utmanande men inte hålls länge bör du överväga att använda InitializeCriticalSectionAndSpinCount så att operativsystemet snurrar ett tag i väntan på att det kritiska avsnittet ska vara tillgängligt i stället för att omedelbart skjuta upp till en mutex om det kritiska avsnittet ägs när du försöker hämta det. För att identifiera kritiska sektioner som kan dra nytta av ett spinnantal är det nödvändigt att mäta längden på den typiska väntetiden för ett visst lås.

Om en delad heap används för minnesallokeringar – standardbeteendet – innebär varje minnesallokering och frigöring att ett lås måste erhållas. När antalet trådar och antalet allokeringar ökar, minskar prestandanivåerna och börjar så småningom minska. Genom att använda per-trådshögar eller minska antalet allokeringar kan man undvika den här låsflaskhalsen.

Om en tråd genererar data och en annan tråd förbrukar data kan de dela data ofta. Detta kan inträffa om en tråd läser in resurser och en annan tråd återger scenen. Om återgivningstråden refererar till de delade data vid varje renderingsanrop blir låsningskostnaderna höga. Mycket bättre prestanda kan uppnås om varje tråd har privata datastrukturer som sedan synkroniseras en gång per bildruta eller mindre.

Låslösa algoritmer garanteras inte vara snabbare än algoritmer som använder lås. Du bör kontrollera om lås faktiskt orsakar problem innan du försöker undvika dem, och du bör mäta om din låslösa kod faktiskt förbättrar prestandan.

Sammanfattning av plattformsskillnader

  • InterlockedXxx-funktioner förhindrar att processorn läser/skriver om i Windows, men inte på Xbox 360.
  • Läsning och skrivning av flyktiga variabler med Visual Studio C++ 2005 förhindrar omordning av cpu-läsning/skrivning i Windows, men på Xbox 360 förhindrar det bara omordning av kompilatorns läs-/skrivåtgärder.
  • Skrivningar sorteras om på Xbox 360, men inte på x86 eller x64.
  • Läsningar sorteras om på Xbox 360, men på x86 eller x64 sorteras de bara om i förhållande till skrivningar och endast om läsningar och skrivningar riktar sig till olika platser.

Rekommendationer

  • Använd lås när det är möjligt eftersom de är enklare att använda korrekt.
  • Undvik att låsa för ofta, så att låskostnaderna inte blir betydande.
  • För att undvika långa fördröjningar, undvik att hålla lås för länge.
  • Använd låslös programmering när det är lämpligt, men se till att vinsterna motiverar komplexiteten.
  • Använd låsfri programmering eller spinnlås i situationer där andra lås är förbjudna, till exempel när du delar data mellan uppskjutna proceduranrop och normal kod.
  • Använd endast låslösa standardprogrammeringsalgoritmer som har visat sig vara korrekta.
  • När du utför låsfri programmering bör du använda flyktiga flaggvariabler och instruktioner för minnesbarriärer efter behov.
  • När du använder InterlockedXxx på Xbox 360 använder du varianterna Acquire och Release.

Referenser

 

 

  • Last updated on