Minnesordning

Minnesordning beskriver ordningen för åtkomst till datorminne av en CPU. Termen kan hänvisa antingen till den minnesordning som genereras av kompilatorn under kompileringstid , eller till den minnesordning som genereras av en CPU under körning .

I moderna mikroprocessorer kännetecknar minnesordning processorns förmåga att ordna om minnesoperationer – det är en typ av exekvering som inte fungerar . Minnesomordning kan användas för att fullt ut utnyttja bussbandbredden för olika typer av minne såsom cacher och minnesbanker .

På de flesta moderna enprocessorer utförs inte minnesoperationer i den ordning som anges av programkoden. I entrådade program verkar alla operationer ha utförts i den angivna ordningen, med all out-of-order exekvering gömd för programmeraren – men i flertrådade miljöer (eller vid gränssnitt med annan hårdvara via minnesbussar) kan detta leda till att problem. För att undvika problem minnesbarriärer användas i dessa fall.

Beställning av kompileringstidsminne

De flesta programmeringsspråk har en uppfattning om en exekveringstråd som exekverar satser i en definierad ordning. Traditionella kompilatorer översätter högnivåuttryck till en sekvens av lågnivåinstruktioner i förhållande till en programräknare på underliggande maskinnivå.

Exekveringseffekter är synliga på två nivåer: inom programkoden på en hög nivå, och på maskinnivå som ses av andra trådar eller bearbetningselement i samtidig programmering , eller under felsökning när du använder en hårdvarufelsökningshjälp med tillgång till maskintillståndet ( visst stöd för detta är ofta inbyggt direkt i CPU:n eller mikrokontrollern som funktionellt oberoende kretsar förutom exekveringskärnan som fortsätter att fungera även när själva kärnan stoppas för statisk inspektion av dess exekveringsläge). Kompileringstidsminnesordning berör sig själv med den förra och bekymrar sig inte med dessa andra åsikter.

Allmänna frågor om programordning

Programordningseffekter av uttrycksutvärdering

Under kompileringen genereras ofta hårdvaruinstruktioner med en finare granularitet än vad som anges i högnivåkoden. Den primära observerbara effekten i en procedurprogrammering är tilldelning av ett nytt värde till en namngiven variabel. 

summa = a + b + c; print(summa);

Print-satsen följer satsen som tilldelar variabelsumman, och sålunda när print-satsen refererar till den beräknade variabelsumman refererar den till detta resultat som en observerbar effekt av den tidigare exekveringssekvensen. Som definierat av reglerna för programsekvens, när utskriftsfunktionsanropet refererar till sum , måste värdet på summan vara det för den senast utförda tilldelningen till variabelsumman ( i detta fall den omedelbart föregående satsen).

På maskinnivå kan få maskiner addera tre tal tillsammans i en enda instruktion, och därför måste kompilatorn översätta detta uttryck till två additionsoperationer. Om programspråkets semantik begränsar kompilatorn till att översätta uttrycket i ordning från vänster till höger (till exempel), kommer den genererade koden att se ut som om programmeraren hade skrivit följande satser i det ursprungliga programmet:

summa = a + b; summa = summa + c;

Om kompilatorn tillåts utnyttja den associativa egenskapen addition, kan den istället generera: 

summa = b + c; summa = a + summa;

Om kompilatorn också har tillåtelse att utnyttja den kommutativa egenskapen addition, kan den istället generera: 

summa = a + c; summa = summa + b;

Observera att heltalsdatatypen i de flesta programmeringsspråk endast följer algebran för de matematiska heltal i frånvaro av heltalsspill och att flyttalsaritmetik för flyttalsdatatypen som är tillgänglig i de flesta programmeringsspråk inte är kommutativ i avrundningseffekter, vilket gör effekter av uttrycksordningen som är synlig i små skillnader i det beräknade resultatet (små initiala skillnader kan dock övergå till godtyckligt stora skillnader över en längre beräkning).

Om programmeraren är oroad över heltalsspill eller avrundningseffekter i flyttal, kan samma program kodas på den ursprungliga höga nivån enligt följande:

summa = a + b; summa = summa + c;

Programordningseffekter som involverar funktionsanrop

Många språk behandlar satsgränsen som en sekvenspunkt , vilket tvingar alla effekter av en sats att vara kompletta innan nästa sats exekveras. Detta kommer att tvinga kompilatorn att generera kod som motsvarar den uttryckta satsordningen. Påståenden är dock ofta mer komplicerade och kan innehålla interna funktionsanrop . 

summa = f(a) + g(b) + h(c);

På maskinnivå innebär anropet av en funktion vanligtvis att sätta upp en stackram för funktionsanropet, vilket innebär många läsningar och skrivningar till maskinminnet. I de flesta kompilerade språk är kompilatorn fri att beställa funktionsanropen f , g och h som den finner lämpligt, vilket resulterar i storskaliga förändringar av programminnesordningen. I ett rent funktionellt programmeringsspråk är funktionsanrop förbjudna att ha bieffekter på det synliga programtillståndet (annat än dess returvärde ) och skillnaden i maskinminnesordning på grund av funktionsanropsordning kommer att vara oviktig för programsemantik. I procedurspråk kan de anropade funktionerna ha sidoeffekter, som att utföra en I/O-operation eller att uppdatera en variabel i globalt programomfång, som båda ger synliga effekter med programmodellen.

Återigen, en programmerare som berörs av dessa effekter kan bli mer pedantisk när det gäller att uttrycka det ursprungliga källprogrammet:

summa = f(a); summa = summa + g(b); summa = summa + h(c);

måste funktionsanropen f , g och h nu köras i den exakta ordningen.

Specifika frågor om minnesordning

Programordningseffekter som involverar pekaruttryck

Betrakta nu samma summering uttryckt med pekarinriktning, på ett språk som C eller C++ som stöder pekare : 

summa = *a + *b + *c;

Att utvärdera uttrycket *x kallas " dereferencing " av en pekare och involverar läsning från minnet på en plats specificerad av det aktuella värdet på x . Effekterna av att läsa från en pekare bestäms av arkitekturens minnesmodell . När du läser från standardprogramlagring finns det inga biverkningar på grund av ordningen på minnesläsoperationerna. Inom inbyggda system är det mycket vanligt att ha minnesmappad I/O där läsning och skrivning till minne utlöser I/O-operationer, eller förändringar av processorns driftläge, vilket är mycket synliga bieffekter. För exemplet ovan, antag för närvarande att pekarna pekar på vanligt programminne, utan dessa biverkningar. Det är fritt fram för kompilatorn att ordna om dessa läsningar i programordning som den vill, och det kommer inte att finnas några programsynliga biverkningar.

Vad händer om det tilldelade värdet också är pekinriktat? 

*summa = *a + *b + *c;

Här är det osannolikt att språkdefinitionen tillåter kompilatorn att bryta isär detta enligt följande:

// som omskrivits av kompilatorn // allmänt förbjudet *summa = *a + *b; *summa = *summa + *c;

Detta skulle inte ses som effektivt i de flesta fall, och pekarskrivningar har potentiella bieffekter på det synliga maskintillståndet. Eftersom kompilatorn inte tillåts denna specifika delande transformation, måste den enda skrivningen till minnesplatsen för summa logiskt följa de tre pekarnas läsningar i värdeuttrycket.

Antag dock att programmeraren är bekymrad över den synliga semantiken för heltalsspill och bryter satsen isär som programnivå enligt följande:

// som direkt skrivits av programmeraren // med aliasproblem *sum = *a + *b; *summa = *summa + *c;

Den första satsen kodar två minnesläsningar, som måste föregå (i valfri ordning) den första skrivningen till *sum . Den andra satsen kodar två minnesläsningar (i valfri ordning) som måste föregå den andra uppdateringen av *sum . Detta garanterar ordningen för de två additionsoperationerna, men introducerar potentiellt ett nytt problem med adressaliasing : vilken som helst av dessa pekare kan potentiellt referera till samma minnesplats.

Till exempel, låt oss anta i det här exemplet att *c och *sum är alias till samma minnesplats, och skriver om båda versionerna av programmet med *sum som står för båda. 

*summa = *a + *b + *summa;

Det är inga problem här. Det ursprungliga värdet av det vi ursprungligen skrev som *c går förlorat vid tilldelning av *summa , och detsamma är det ursprungliga värdet på *summa men detta skrevs över i första hand och det är inget speciellt problem. 

// vad programmet blir med *c och *summa aliased *sum = *a + *b; *summa = *summa + *summa;

Här skrivs det ursprungliga värdet av *summa över innan dess första åtkomst, och istället får vi den algebraiska motsvarigheten till: 

// algebraisk motsvarighet till aliasfallet ovan *summa = (*a + *b) + (*a + *b);

som tilldelar *summa ett helt annat värde på grund av omarrangemanget av satsen.

På grund av möjliga aliaseffekter är pekaruttryck svåra att ordna om utan att riskera synliga programeffekter. I det vanliga fallet kanske det inte finns något alias, så koden verkar köra normalt som tidigare. Men i edge-fallet där aliasing förekommer kan allvarliga programfel uppstå. Även om dessa kantfall är helt frånvarande i normal utförande, öppnar det dörren för en illvillig motståndare att skapa en ingång där aliasing finns, vilket potentiellt leder till en datorsäkerhetsexploatering .

En säker omordning av det tidigare programmet är som följer:

 // deklarera en temporär  lokal variabel  'temp' av lämplig typ temp = *a + *b; *summa = temp + *c;

Tänk slutligen på det indirekta fallet med tillagda funktionsanrop:

*summa = f(*a) + g(*b);

Kompilatorn kan välja att utvärdera *a och *b före endera funktionsanropet, den kan skjuta upp utvärderingen av *b till efter funktionsanropet f eller den kan skjuta upp utvärderingen av *a till efter funktionsanropet g . Om funktionen f och g är fria från synliga programbiverkningar kommer alla tre valen att producera ett program med samma synliga programeffekter. Om implementeringen av f eller g innehåller bieffekten av någon pekarskrivning som är föremål för aliasing med pekarna a eller b , är de tre valen benägna att producera olika synliga programeffekter.

Minnesordning i språkspecifikation

I allmänhet är kompilerade språk inte tillräckligt detaljerade i sin specifikation för att kompilatorn formellt vid kompileringstidpunkten ska kunna bestämma vilka pekare som potentiellt är aliasade och vilka som inte är det. Det säkraste tillvägagångssättet är att kompilatorn antar att alla pekare är potentiellt aliasade hela tiden. Denna nivå av konservativ pessimism tenderar att producera fruktansvärda prestationer jämfört med det optimistiska antagandet att det aldrig existerar något alias.

Som ett resultat av detta har många kompilerade språk på hög nivå, såsom C/C++, utvecklats till att ha intrikata och sofistikerade semantiska specifikationer om var kompilatorn tillåts göra optimistiska antaganden i kodomordning i strävan efter högsta möjliga prestanda, och där kompilatorn krävs för att göra pessimistiska antaganden i kodomordning för att undvika semantiska faror.

Den överlägset största klassen av biverkningar i ett modernt procedurspråk involverar minnesskrivoperationer, så regler kring minnesordning är en dominerande komponent i definitionen av programordningssemantik. Omordningen av funktionsanropen ovan kan tyckas vara en annan övervägande, men detta övergår vanligtvis till oro för minneseffekter internt i de anropade funktionerna som interagerar med minnesoperationer i uttrycket som genererar funktionsanropet.

Ytterligare svårigheter och komplikationer

Optimering under som-om

Moderna kompilatorer tar ibland detta ett steg längre med hjälp av en som-om-regel , där all omordning är tillåten (även mellan påståenden) om ingen effekt på den synliga programsemantiken blir resultatet. Enligt denna regel kan operationsordningen i den översatta koden variera kraftigt från den angivna programordningen. Om kompilatorn tillåts göra optimistiska antaganden om distinkta pekaruttryck som inte har någon aliasöverlappning i ett fall där sådan aliasing faktiskt existerar (detta skulle normalt klassificeras som ett dåligt format program som uppvisar odefinierat beteende), de negativa resultaten av en aggressiv kod- optimeringstransformation är omöjliga att gissa före kodexekvering eller direkt kodinspektion. Det odefinierade beteendets rike har nästan gränslösa manifestationer.

Det är programmerarens ansvar att konsultera språkspecifikationen för att undvika att skriva dåligt utformade program där semantiken eventuellt ändras som ett resultat av laglig kompilatoroptimering. Fortran lägger traditionellt en stor börda på programmeraren att vara medveten om dessa problem, med systemprogrammeringsspråken C och C++ inte långt efter.

Vissa högnivåspråk eliminerar pekarkonstruktioner helt och hållet, eftersom denna nivå av vakenhet och uppmärksamhet på detaljer anses vara för hög för att tillförlitligt kunna upprätthållas även bland professionella programmerare.

Ett fullständigt grepp om semantik för minnesordning anses vara en mystisk specialisering även bland underpopulationen av professionella systemprogrammerare som vanligtvis är bäst informerade inom detta ämnesområde. De flesta programmerare nöjer sig med ett adekvat arbetsgrepp om dessa frågor inom den normala domänen av deras programmeringsexpertis. I den yttersta änden av specialiseringen inom minnesordningssemantik finns de programmerare som skapar mjukvaruramverk till stöd för samtidiga beräkningsmodeller .

Aliasing av lokala variabler

Observera att lokala variabler inte kan antas vara fria från alias om en pekare till en sådan variabel kommer ut i naturen:

summa = f(&a) + g(a);

Det går inte att säga vad funktionen f kan ha gjort med den medföljande pekaren till a , inklusive att lämna en kopia i globalt tillstånd som funktionen g senare kommer åt. I det enklaste fallet f ett nytt värde till variabeln a , vilket gör detta uttryck dåligt definierat i exekveringsordning. f kan på ett påfallande sätt förhindras från att göra detta genom att tillämpa en const-kvalificerare på deklarationen av dess pekarargument, vilket gör uttrycket väldefinierat. Således har den moderna kulturen med C/C++ blivit något besatt av att tillhandahålla const-kvalificerare för att fungera argumentdeklarationer i alla genomförbara fall.

C och C++ tillåter att insidan av f typ kastar bort constness-attributet som en farlig hjälp. Om f gör detta på ett sätt som kan bryta uttrycket ovan, bör det inte deklarera pekarargumenttypen som const i första hand.

Andra högnivåspråk lutar mot ett sådant deklarationsattribut som motsvarar en stark garanti utan kryphål som bryter mot denna garanti som tillhandahålls inom själva språket; alla spel är avstängda på denna språkgaranti om din applikation länkar ett bibliotek skrivet på ett annat programmeringsspråk (även om detta anses vara extremt dålig design).

Implementering av minnesbarriär vid kompilering

Se även: Minnesspärr

Dessa barriärer hindrar en kompilator från att ordna om instruktioner under kompileringstiden – de förhindrar inte omordning av CPU under körning.

  • Alla dessa GNU inline assembler-satser förbjuder GCC- kompilatorn att omordna läs- och skrivkommandon runt den: 
 asm volatile("" ::: "minne"); __asm__ __volatile__ ("" ::: "minne");
  • Denna C11/C++11-funktion förbjuder kompilatorn att omordna läs- och skrivkommandon runt den: 
 atomic_signal_fence(memory_order_acq_rel); 
 __memory_barrier() 
 _ReadWriteBarrier()

Kombinerade barriärer

I många programmeringsspråk kan olika typer av barriärer kombineras med andra operationer (som load, store, atomic increment, atomic compare och swap), så ingen extra minnesbarriär behövs före eller efter det (eller båda). Beroende på en CPU-arkitektur som är inriktad på kommer dessa språkkonstruktioner att översättas till antingen speciella instruktioner, till flera instruktioner (dvs. barriär och belastning), eller till normal instruktion, beroende på beställningsgarantier för hårdvaran.

Beställning av körtidsminne

I symmetriska multiprocessing (SMP) mikroprocessorsystem

Det finns flera minneskonsistensmodeller för SMP -system:

  • Sekventiell konsistens (alla läsningar och alla skrivningar är i ordning)
  • Avslappnad konsistens (vissa typer av omordning är tillåtna)
    • Laster kan ordnas om efter laster (för bättre fungerande cachekoherens, bättre skalning)
    • Laster kan beställas om efter butik
    • Butiker kan beställas om efter butiker
    • Butiker kan beställas om efter laddningar
  • Svag konsistens (läsningar och skrivningar ordnas om godtyckligt, begränsas endast av explicita minnesbarriärer )

På vissa processorer

  • Atomoperationer kan ordnas om med laster och förråd.
  • Det kan finnas inkoherent instruktionscachepipeline, vilket förhindrar att självmodifierande kod exekveras utan speciella instruktioner för instruktionscache-spolning/återladdning.
  • Beroende laster kan omordnas (detta är unikt för Alpha). Om processorn hämtar en pekare till vissa data efter denna omordning, kanske den inte hämtar själva datan utan använder inaktuella data som den redan har cachelagrat och ännu inte ogiltigförklarad. Att tillåta denna avslappning gör cachehårdvaran enklare och snabbare men leder till kravet på minnesbarriärer för läsare och skribenter. På Alpha-hårdvara (som multiprocessor Alpha 21264- system) bearbetas cache-radsinvalideringar som skickas till andra processorer på lata sätt som standard, såvida de inte uttryckligen begärs att behandlas mellan beroende laddningar. Alpha-arkitekturspecifikationen tillåter också andra former av beroende belastningar omordning, till exempel genom att använda spekulativa dataläsningar innan man vet att den verkliga pekaren ska avreferens.
Minnesordning i vissa arkitekturer
Typ Alfa ARMv7 MIPS RISC-V PA-RISC KRAFT SPARC x86 AMD64 IA-64 z/Arkitektur
WMO TSO RMO PSO TSO
Laster kan beställas om efter laster Y Y
beror på genomförandet 		Y Y Y Y Y
Laster kan beställas om efter butik Y Y Y Y Y Y Y
Butiker kan beställas om efter butiker Y Y Y Y Y Y Y Y
Butiker kan beställas om efter laddningar Y Y Y Y Y Y Y Y Y Y Y Y Y
Atomic kan ordnas om med belastningar Y Y Y Y Y Y
Atomic kan beställas om med butiker Y Y Y Y Y Y Y
Beroende laster kan beställas om Y
Osammanhängande instruktionscache/pipeline Y Y Y Y Y Y Y Y Y Y
RISC-V-minnesbeställningsmodeller
WMO
Svag minnesordning (standard)
TSO
Total lagringsordning (stöds endast med Ztso-tillägget)
SPARC-minnesbeställningslägen
TSO
Total lagringsorder (standard)
RMO
Avslappnad minnesordning (stöds inte på senaste CPU:er)
PSO
Partial butiksorder (stöds inte på senaste processorer)

Implementering av hårdvaruminnesbarriär

Se även: Minnesspärr

Många arkitekturer med SMP-stöd har speciell hårdvaruinstruktion för att spola läsning och skrivning under körning . 

 lfence (asm), void _mm_lfence(void) sfence (asm), void _mm_sfence(void) mfence (asm), void _mm_mfence(void) 
 sync (asm) 
 sync (asm) 
 mf (asm) 
 dcs (asm) 
 dmb (asm) dsb (asm) isb (asm)

Kompilatorstöd för hårdvaruminnesbarriärer

Vissa kompilatorer stöder inbyggda program som avger instruktioner för hårdvaruminnesbarriär:

  • GCC , version 4.4.0 och senare, har __sync_synchronize .
  • Sedan C11 och C++11 lades ett atomic_thread_fence()- kommando till.
  • Microsoft Visual C++- kompilatorn har MemoryBarrier() .
  • Sun Studio Compiler Suite har __machine_r_barrier , __machine_w_barrier och __machine_rw_barrier .

Se även

Vidare läsning

Hämtad från " https://en.wikipedia.org/w/index.php?title=Memory_ordering&oldid=1137609192 "