Objednávka paměti - Memory ordering

Pořadí paměti popisuje pořadí přístupů CPU k paměti počítače. Termín může odkazovat buď na uspořádání paměti generované kompilátorem během kompilace , nebo na uspořádání paměti generované CPU během běhu .

V moderních mikroprocesorech uspořádání paměti charakterizuje schopnost CPU změnit pořadí paměťových operací-je to typ provedení mimo pořadí . Přeskupení paměti lze použít k plnému využití šířky pásma sběrnice různých typů paměti, jako jsou mezipaměti a paměťové banky .

Na většině moderních uniprocesorů nejsou paměťové operace prováděny v pořadí určeném programovým kódem. V programech s jedním vláknem se zdá, že všechny operace byly provedeny v uvedeném pořadí, přičemž veškeré provedení mimo pořadí je programátoru skryto-nicméně v prostředích s více vlákny (nebo při propojení s jiným hardwarem prostřednictvím paměťových sběrnic) to může vést k problémy. Aby se předešlo problémům, lze v těchto případech použít paměťové bariéry .

Objednávání paměti v kompilačním čase

Většina programovacích jazyků má určitou představu o podprocesu provádění, který provádí příkazy v definovaném pořadí. Tradiční překladače překládají výrazy na vysoké úrovni do sekvence instrukcí na nízké úrovni vzhledem k programovému čítači na základní úrovni stroje.

Efekty spouštění jsou viditelné na dvou úrovních: v rámci programového kódu na vysoké úrovni a na úrovni počítače při pohledu na jiná vlákna nebo prvky zpracování v souběžném programování nebo během ladění při použití hardwarové ladicí pomůcky s přístupem ke stavu počítače ( určitá podpora pro toto je často zabudována přímo do CPU nebo mikrokontroléru jako funkčně nezávislé obvody kromě prováděcího jádra, které pokračuje v provozu, i když je samotné jádro zastaveno kvůli statické kontrole stavu jeho provedení). Pořadí paměti kompilace se týká prvního a nezabývá se těmito jinými pohledy.

Obecné problémy pořadí programu

Účinky vyhodnocení výrazů v pořadí programů

Během kompilace jsou hardwarové pokyny často generovány s jemnější granularitou, než je uvedeno v kódu vysoké úrovně. Primárním pozorovatelným efektem v procedurálním programování je přiřazení nové hodnoty pojmenované proměnné. 

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

Příkaz print následuje po příkazu, který přiřadí proměnné součet, a proto když tiskový příkaz odkazuje na vypočítanou proměnnou sum, odkazuje na tento výsledek jako pozorovatelný efekt předchozí sekvence provedení. Jak je definováno pravidly posloupnosti programu, když printvolání funkce odkazuje sum, hodnota summusí být hodnota naposledy provedeného přiřazení proměnné sum(v tomto případě bezprostředně předchozí příkaz).

Na úrovni strojů může několik počítačů sčítat tři čísla dohromady v jedné instrukci, a proto bude muset překladač tento výraz přeložit do dvou operací sčítání. Pokud sémantika programového jazyka omezí kompilátor na překlad výrazu v pořadí zleva doprava (například), generovaný kód bude vypadat, jako by programátor v původním programu napsal následující příkazy: 

  sum = a + b;
  sum = sum + c;

Pokud je kompilátoru povoleno využívat asociativní vlastnost sčítání, může místo toho generovat: 

  sum = b + c; 
  sum = a + sum;

Pokud je kompilátoru také povoleno využívat komutativní vlastnost sčítání, může místo toho generovat: 

  sum = a + c; 
  sum = sum + b;

Všimněte si toho, že celočíselný datový typ ve většině programovacích jazyků sleduje pouze algebru pro matematická celá čísla bez přetečení celých čísel a že aritmetika s plovoucí desetinnou čárkou u datového typu s plovoucí desetinnou čárkou, který je k dispozici ve většině programovacích jazyků, není při zaokrouhlování efektů komutativní. pořadí výrazu viditelné v malých rozdílech vypočítaného výsledku (malé počáteční rozdíly však mohou kaskádovitě přecházet do libovolně velkých rozdílů při delším výpočtu).

Pokud má programátor obavy z přetečení celých čísel nebo zaokrouhlování v plovoucí desetinné čárce, může být stejný program kódován na původní vysoké úrovni následujícím způsobem: 

  sum = a + b; 
  sum = sum + c;

Efekty programového řádu zahrnující volání funkcí

Mnoho jazyků považuje hranici příkazu za bod posloupnosti , což nutí všechny efekty jednoho příkazu dokončit před provedením dalšího příkazu. To donutí kompilátor generovat kód odpovídající vyjádřenému pořadí příkazů. Příkazy jsou však často komplikovanější a mohou obsahovat interní volání funkcí . 

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

Na úrovni počítače volání funkce obvykle zahrnuje nastavení rámce zásobníku pro volání funkce, což zahrnuje mnoho čtení a zápisů do paměti stroje. Ve většině kompilované jazyky, překladač je zatím objednat volání funkce f, ga hjak to najde pohodlné, což má za následek rozsáhlé změny v programové paměti pořadí. V čistě funkčním programovacím jazyce je zakázáno, aby volání funkcí mělo vedlejší účinky na viditelný stav programu (jiný než jeho návratová hodnota ) a rozdíl v pořadí paměti stroje v důsledku řazení volání funkcí bude pro sémantiku programu bezvýznamný. V procedurálních jazycích mohou mít volané funkce vedlejší efekty, jako je provádění I/O operace nebo aktualizace proměnné v globálním rozsahu programu, přičemž oba vytvářejí viditelné efekty s programovým modelem.

Programátor zabývající se těmito efekty může být při vyjádření původního zdrojového programu pedantičtější: 

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

V programovacích jazyků, kde je výpis hranice definován jako sekvence bodu, funkce volání f, ga hnyní musí provést v tomto přesném pořadí.

Specifické problémy pořadí paměti

Efekty programového řádu zahrnující výrazy ukazatele

Nyní zvažte stejné součty vyjádřené pomocí směrovosti ukazatelů v jazyce, jako je C nebo C ++, který podporuje ukazatele : 

  sum = *a + *b + *c;

Vyhodnocení výrazu *xse nazývá „ dereferencování “ ukazatele a zahrnuje čtení z paměti na místě určeném aktuální hodnotou x. Účinky čtení z ukazatele jsou určeny paměťovým modelem architektury . Při čtení ze standardního úložiště programu neexistují žádné vedlejší efekty kvůli pořadí operací čtení z paměti. V programování vestavěného systému je velmi běžné mít paměťově mapované I/O, kde se načítají a zapisují do paměti spouštěcí I/O operace nebo se mění operační režim procesoru, což jsou velmi viditelné vedlejší efekty. U výše uvedeného příkladu předpokládejme prozatím, že ukazatele směřují do běžné paměti programu, bez těchto vedlejších účinků. Kompilátor může libovolně změnit pořadí těchto čtení v pořadí programu, jak uzná za vhodné, a nebudou existovat žádné programově viditelné vedlejší efekty.

Co když přiřazená hodnota je také ukazatel indirected? 

  *sum = *a + *b + *c;

Zde je nepravděpodobné, že by definice jazyka umožnila kompilátoru toto rozdělit následujícím způsobem: 

  // as rewritten by the compiler
  // generally forbidden 
  *sum = *a + *b;
  *sum = *sum + *c;

To by ve většině případů nebylo považováno za efektivní a zápisy ukazatelů mají potenciální vedlejší účinky na stav viditelného počítače. Vzhledem k tomu, kompilátor není povoleno tento konkrétní transformaci štípání, jediný zápis do paměťového místa sumlogicky musí následovat tři ukazatel čte ve výrazu hodnoty.

Předpokládejme však, že programátora znepokojuje viditelná sémantika přetečení celých čísel a přeruší příkaz jako úroveň programu následovně: 

  // as directly authored by the programmer 
  // with aliasing concerns 
  *sum = *a + *b; 
  *sum = *sum + *c;

První příkaz kóduje dvě čtení z paměti, která musí předcházet (v libovolném pořadí) prvnímu zápisu *sum. Druhý příkaz kóduje dvě čtení paměti (v libovolném pořadí), která musí předcházet druhé aktualizaci *sum. To zaručuje pořadí dvou operací sčítání, ale potenciálně představuje nový problém aliasingu adres : kterýkoli z těchto ukazatelů by potenciálně mohl odkazovat na stejné umístění paměti.

Předpokládejme například, že v tomto příkladu jsou *ca *sumjsou přiřazeny ke stejnému umístění v paměti, a přepište obě verze programu tak, že pro ně budete *sumstát. 

  *sum = *a + *b + *sum;

Zde nejsou žádné problémy. Původní hodnota toho, co jsme původně napsali, *cje ztracena při přiřazení *sum, stejně jako původní hodnota, *sumale toto bylo v první řadě přepsáno a není to zvláštní. 

  // what the program becomes with *c and *sum aliased 
  *sum = *a + *b;
  *sum = *sum + *sum;

Zde je původní hodnota *sumpřepsána před jejím prvním přístupem a místo toho získáme algebraický ekvivalent: 

  // algebraic equivalent of the aliased case above
  *sum = (*a + *b) + (*a + *b);

který přiřazuje zcela jinou hodnotu *sumkvůli přeskupení příkazů.

Kvůli možným efektům aliasingu je obtížné přeskupit výrazy ukazatele bez rizika viditelných efektů programu. V běžném případě nemusí existovat žádné aliasing, takže se zdá, že kód běží normálně jako dříve. Ale v okrajovém případě, kde je přítomno aliasing, mohou vzniknout závažné chyby programu. I když tyto okrajové případy při běžném provádění zcela chybí, otevírá to bránu pro zlomyslného protivníka, aby vytvořil vstup tam, kde existuje aliasing, což potenciálně může vést k zneužití počítačové bezpečnosti .

Bezpečné přeuspořádání předchozího programu je následující: 

  // declare a temporary local variable 'temp' of suitable type 
  temp = *a + *b; 
  *sum = temp + *c;

Nakonec zvažte nepřímý případ s přidanými voláním funkcí: 

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

Kompilátor se může rozhodnout vyhodnotit *aa *bpřed každým voláním funkce může odložit vyhodnocení *baž po volání funkce fnebo může odložit vyhodnocení *aaž po volání funkce g. Pokud funkce fa gjsou bez programů viditelné vedlejší efekty, všechny tři volby vytvoří program se stejnými viditelnými efekty programu. Pokud implementace fnebo gobsahují vedlejší účinek jakéhokoli zápisu ukazatele podléhajícího aliasingu s ukazateli anebo b, tyto tři možnosti mohou vytvářet různé viditelné efekty programu.

Pořadí paměti v jazykové specifikaci

Zkompilované jazyky obecně nejsou ve své specifikaci dostatečně podrobné, aby kompilátor formálně v době kompilace určil, které ukazatele jsou potenciálně aliasy a které nikoli. Nejbezpečnějším postupem je, když kompilátor předpokládá, že všechny ukazatele jsou potenciálně aliasy za všech okolností. Tato úroveň konzervativního pesimismu má tendenci produkovat strašný výkon ve srovnání s optimistickým předpokladem, že žádné aliasing nikdy neexistuje.

Výsledkem je, že mnoho vysoce kompilovaných jazyků, jako je C/C ++, se vyvinulo tak, aby mělo složité a propracované sémantické specifikace o tom, kde je kompilátoru dovoleno vytvářet optimistické předpoklady při přeskupování kódu za účelem dosažení nejvyššího možného výkonu a kde kompilátor je povinen provádět pesimistické předpoklady při změně pořadí kódu, aby se předešlo sémantickým nebezpečím.

Zdaleka největší třída vedlejších účinků v moderním procedurálním jazyce zahrnuje operace zápisu do paměti, takže pravidla kolem uspořádání paměti jsou dominantní součástí definice sémantiky pořadí programů. Uspořádání výše uvedených volání funkcí se může zdát jako jiné hledisko, ale toto obvykle přechází do obav z paměťových efektů interních do volaných funkcí, které interagují s paměťovými operacemi ve výrazu, který generuje volání funkce.

Další potíže a komplikace

Optimalizace za as-if

Moderní kompilátory to někdy posouvají o krok dále pomocí pravidla jako kdyby , ve kterém je povoleno jakékoli přeskupování (i přes příkazy), pokud nemá žádný vliv na viditelnou sémantiku programu. Podle tohoto pravidla se pořadí operací v přeloženém kódu může výrazně lišit od zadaného pořadí programu. Pokud je kompilátoru povoleno provádět optimistické předpoklady o výrazných výrazech ukazatelů, které se v případě, že takové aliasingy skutečně překrývají, nepřekrývají žádné aliasy (toto by normálně bylo klasifikováno jako špatně vytvořený program vykazující nedefinované chování ), nepříznivé výsledky agresivního kódu- optimalizační transformaci nelze odhadnout před spuštěním kódu nebo přímou kontrolou kódu. Oblast nedefinovaného chování má téměř neomezené projevy.

Je zodpovědností programátora konzultovat specifikaci jazyka, aby se vyhnul psaní špatně vytvořených programů, kde jsou sémantika potenciálně změněna v důsledku jakékoli legální optimalizace kompilátoru. Fortran tradičně klade velkou zátěž na programátora, aby si byl těchto problémů vědom, přičemž systémy programovacích jazyků C a C ++ nejsou nijak pozadu.

Některé jazyky na vysoké úrovni zcela eliminují konstrukci ukazatelů, protože tato úroveň bdělosti a pozornosti k detailům je považována za příliš vysokou na to, aby se spolehlivě udržela i mezi profesionálními programátory.

Kompletní pochopení sémantiky paměťového řádu je považováno za tajemnou specializaci i mezi subpopulací profesionálních systémových programátorů, kteří jsou v této oblasti obvykle nejlépe informováni. Většina programátorů se spokojí s adekvátním pracovním uchopením těchto problémů v rámci běžné oblasti své znalosti programování. Na extrémním konci specializace na sémantiku pořadí paměti jsou programátoři, kteří vytvářejí softwarové rámce na podporu souběžných výpočetních modelů.

Aliasing lokálních proměnných

Všimněte si, že nelze předpokládat, že lokální proměnné jsou bez aliasingu, pokud ukazatel na takovou proměnnou uniká do volné přírody: 

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

Nelze říci, k čemu by funkce fs dodaným ukazatelem mohla udělat a, včetně ponechání kopie v globálním stavu, ke které funkce gpozději přistupuje. V nejjednodušším případě fzapíše do proměnné novou hodnotu a, takže tento výraz bude špatně definován v pořadí provedení. flze v tom viditelně zabránit použitím kvalifikátoru const na deklaraci jeho argumentu ukazatele, čímž je výraz dobře definován. Moderní kultura C/C ++ se tak stala poněkud obsedantní ohledně poskytování konstant kvalifikátorů pro deklarace funkcí ve všech životaschopných případech.

C a C ++ dovolí vnitřní části fk druhu obsazení atributu constness pryč jako nebezpečný výhodný. Pokud fto udělá způsobem, který může narušit výše uvedený výraz, nemělo by být na prvním místě deklarace typu argumentu ukazatele jako const.

Jiné jazyky vyšší úrovně se přiklánějí k takovému atributu deklarace, který představuje silnou záruku bez smyček, které by porušovaly tuto záruku poskytovanou v samotném jazyce; všechny sázky jsou na tuto jazykovou záruku vypnuty, pokud vaše aplikace propojuje knihovnu napsanou v jiném programovacím jazyce (i když je to považováno za mimořádně špatný design).

Implementace bariéry paměti v době kompilace

Viz také: Paměťová bariéra

Tyto bariéry zabraňují kompilátoru měnit pořadí pokynů během kompilace - nezabraňují změně pořadí podle CPU během běhu.

  • Kterýkoli z těchto vložených příkazů assembleru GNU zakazuje kompilátoru GCC změnit pořadí příkazů pro čtení a zápis kolem něj:
asm volatile("" ::: "memory");
__asm__ __volatile__ ("" ::: "memory");
  • Tato funkce C11/C ++ 11 zakazuje kompilátoru změnit pořadí příkazů pro čtení a zápis kolem něj:
atomic_signal_fence(memory_order_acq_rel);

__memory_barrier()

_ReadWriteBarrier()

Kombinované bariéry

V mnoha programovacích jazycích lze různé typy bariér kombinovat s dalšími operacemi (jako je načítání, ukládání, atomový přírůstek, atomové porovnávání a swap), takže před ani za ním (nebo obojí) není potřeba žádná další paměťová bariéra. V závislosti na architektuře CPU, na kterou se zaměřuje, se tyto jazykové konstrukce převádějí buď na speciální instrukce, na více instrukcí (tj. Bariéra a zátěž), ​​nebo na normální instrukce, v závislosti na zárukách uspořádání hardwarové paměti.

Objednávání paměti za běhu

V symetrických víceprocesních (SMP) mikroprocesorových systémech

Pro systémy SMP existuje několik modelů konzistence paměti :

  • Sekvenční konzistence (všechna čtení a všechny zápisy jsou v pořadí)
  • Uvolněná konzistence (některé typy přeskupení jsou povoleny)
    • Zatížení lze po načtení změnit (pro lepší fungování koherence mezipaměti, lepší škálování)
    • Zatížení lze po prodejnách doobjednat
    • Obchody lze po prodejnách doobjednat
    • Obchody lze po načtení znovu objednat
  • Slabá konzistence (čtení a zápisy jsou libovolně seřazeny, omezeny pouze explicitními paměťovými překážkami )

Na některých CPU

  • Atomové operace lze doobjednat pomocí zatížení a skladů.
  • Může existovat nesouvislý kanál mezipaměti instrukcí, který brání spuštění samočinně se měnícího kódu bez zvláštních instrukcí pro vymazání/načtení mezipaměti instrukcí.
  • U závislých zatížení lze změnit pořadí (toto je jedinečné pro Alpha). Pokud procesor po této změně pořadí načte ukazatel na některá data, nemusí načíst samotná data, ale použije zastaralá data, která již uložil do mezipaměti a dosud nebyla zneplatněna. Povolení této relaxace zjednodušuje a zrychluje hardware mezipaměti, ale vede k požadavku paměťových bariér pro čtenáře a zapisovatele. Na hardwaru Alpha (jako systémy s více procesory Alpha 21264 ) zneplatnění mezipaměti odeslané jiným procesorům jsou ve výchozím nastavení zpracovávány líným způsobem, pokud není výslovně požadováno zpracování mezi závislými zatíženími. Specifikace architektury Alpha také umožňuje přeskupení jiných forem závislých zatížení, například pomocí spekulativních čtení dat před poznáním skutečného ukazatele, který má být dereferencován.
Pořadí paměti v některých architekturách
Typ Alfa ARMv7 MIPS RISC-V PA-RISC NAPÁJENÍ SPARC x86 AMD64 IA-64 z/Architektura
WMO TSO RMO PSO TSO
Zatížení lze po načtení znovu objednat Y Y závisí na
implementaci		 Y Y Y Y Y
Zatížení lze po prodejnách doobjednat Y Y Y Y Y Y Y
Obchody lze po prodejnách doobjednat Y Y Y Y Y Y Y Y
Obchody lze po načtení znovu objednat Y Y Y Y Y Y Y Y Y Y Y Y Y
Atomic lze doobjednat pomocí zatížení Y Y Y Y Y Y
Atomic lze doobjednat v obchodech Y Y Y Y Y Y Y
Závislé zatížení lze znovu objednat Y
Nesouvislý kanál mezipaměti instrukcí Y Y Y Y Y Y Y Y Y Y

Modely pro uspořádání paměti RISC-V:

WMO
Pořadí slabé paměti (výchozí)
TSO
Celková objednávka v obchodě (podporováno pouze u rozšíření Ztso)

Režimy uspořádání paměti SPARC:

TSO
Celková objednávka v obchodě (výchozí)
RMO
Pořadí uvolněné paměti (není podporováno na posledních CPU)
PSO
Částečná objednávka úložiště (není podporována na posledních CPU)

Implementace hardwarové bariéry paměti

Viz také: Paměťová bariéra

Mnoho architektur s podporou SMP má speciální hardwarové instrukce pro proplachování čtení a zápisů za běhu . 

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)

Podpora kompilátoru pro bariéry hardwarové paměti

Některé kompilátory podporují vestavěné moduly, které vydávají pokyny pro bariéru hardwarové paměti:

  • GCC , verze 4.4.0 a novější, má __sync_synchronize.
  • Od C11 a C ++ 11 atomic_thread_fence()byl přidán příkaz.
  • V Microsoft Visual C ++ kompilátor má MemoryBarrier().
  • Sun Studio Compiler Suite má __machine_r_barrier, __machine_w_barriera __machine_rw_barrier.

Viz také

Reference

Další čtení