Porządkowanie pamięci

Porządkowanie pamięci opisuje kolejność dostępów do pamięci komputera przez procesor. Termin ten może odnosić się albo do porządku pamięci generowanego przez kompilator w czasie kompilacji , albo do porządku pamięci generowanego przez procesor w czasie wykonywania .

W nowoczesnych mikroprocesorach kolejność pamięci charakteryzuje zdolność procesora do zmiany kolejności operacji pamięciowych – jest to rodzaj wykonywania poza kolejnością . Zmiana kolejności pamięci może być wykorzystana do pełnego wykorzystania przepustowości magistrali różnych typów pamięci, takich jak pamięci podręczne i banki pamięci .

Na większości nowoczesnych uniprocesorów operacje pamięciowe nie są wykonywane w kolejności określonej przez kod programu. W programach jednowątkowych wydaje się, że wszystkie operacje zostały wykonane w określonej kolejności, a wszystkie operacje poza kolejnością są ukryte dla programisty – jednak w środowiskach wielowątkowych (lub podczas łączenia się z innym sprzętem za pośrednictwem magistrali pamięci) może to prowadzić do problemy. Aby uniknąć problemów, w takich przypadkach można zastosować bariery pamięci .

Kolejność pamięci w czasie kompilacji

Większość języków programowania ma pewne pojęcie wątku wykonania, który wykonuje instrukcje w określonej kolejności. Tradycyjne kompilatory tłumaczą wyrażenia wysokiego poziomu na sekwencję instrukcji niskiego poziomu względem licznika programu na podstawowym poziomie maszyny.

Efekty wykonania są widoczne na dwóch poziomach: w kodzie programu na wysokim poziomie oraz na poziomie maszyny widzianej przez inne wątki lub elementy przetwarzające w programowaniu współbieżnym lub podczas debugowania przy użyciu sprzętowego wspomagania debugowania z dostępem do stanu maszyny ( pewne wsparcie dla tego jest często wbudowane bezpośrednio w procesor lub mikrokontroler jako funkcjonalnie niezależny obwód oprócz rdzenia wykonawczego, który nadal działa, nawet gdy sam rdzeń jest zatrzymany w celu statycznej kontroli jego stanu wykonania). Porządek pamięci w czasie kompilacji dotyczy tego pierwszego i nie zajmuje się tymi innymi poglądami.

Ogólne zagadnienia porządku programu

Efekty oceny wyrażeń w kolejności programu

Podczas kompilacji instrukcje sprzętowe są często generowane z większą szczegółowością niż określona w kodzie wysokiego poziomu. Podstawowym obserwowalnym efektem w programowaniu proceduralnym jest przypisanie nowej wartości nazwanej zmiennej. 

suma = a + b + c; drukuj(suma);

Instrukcja print następuje po instrukcji, która przypisuje zmiennej sum, a zatem gdy instrukcja print odwołuje się do obliczonej sumy zmiennej , odwołuje się do tego wyniku jako obserwowalnego efektu wcześniejszej sekwencji wykonania. Zgodnie z regułami sekwencji programu, gdy print odwołuje się do sum , wartość sum musi być wartością ostatnio wykonanego przypisania do zmiennej sum (w tym przypadku bezpośrednio poprzedzającej instrukcji).

Na poziomie maszyny niewiele maszyn może dodać trzy liczby do jednej instrukcji, więc kompilator będzie musiał przetłumaczyć to wyrażenie na dwie operacje dodawania. Jeśli semantyka języka programu ogranicza kompilator do tłumaczenia wyrażenia w kolejności od lewej do prawej (na przykład), wygenerowany kod będzie wyglądał tak, jakby programista napisał następujące instrukcje w oryginalnym programie:

suma = a + b; suma = suma + c;

Jeśli kompilator może wykorzystać właściwość asocjacyjną dodawania, może zamiast tego wygenerować: 

suma = b + do; suma = a + suma;

Jeśli kompilator może również wykorzystywać przemienną właściwość dodawania, może zamiast tego wygenerować: 

suma = a + c; suma = suma + b;

Należy zauważyć, że typ danych liczb całkowitych w większości języków programowania jest zgodny z algebrą liczb całkowitych matematycznych tylko w przypadku braku przepełnienia liczb całkowitych i że arytmetyka zmiennoprzecinkowa na zmiennoprzecinkowym typie danych dostępnym w większości języków programowania nie jest przemienna w efektach zaokrąglania, dzięki czemu efekty rzędu wyrażeń widocznych w niewielkich różnicach obliczonego wyniku (niewielkie początkowe różnice mogą jednak kaskadować się w dowolnie duże różnice w dłuższym obliczeniu).

Jeśli programista obawia się przepełnienia liczb całkowitych lub efektów zaokrąglenia w liczbach zmiennoprzecinkowych, ten sam program może zostać zakodowany na oryginalnym wysokim poziomie w następujący sposób:

suma = a + b; suma = suma + c;

Efekty kolejności programu obejmujące wywołania funkcji

Wiele języków traktuje granicę instrukcji jako punkt sekwencji , wymuszając zakończenie wszystkich efektów jednej instrukcji przed wykonaniem następnej instrukcji. Zmusi to kompilator do wygenerowania kodu odpowiadającego wyrażonej kolejności instrukcji. Instrukcje są jednak często bardziej skomplikowane i mogą zawierać wywołania funkcji wewnętrznych . 

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

Na poziomie maszyny wywołanie funkcji zwykle wiąże się z ustawieniem ramki stosu dla wywołania funkcji, co wiąże się z wieloma odczytami i zapisami w pamięci maszyny. W większości języków kompilowanych kompilator może dowolnie porządkować wywołania funkcji f , g i h według własnego uznania, co skutkuje zmianami kolejności pamięci programu na dużą skalę. W czysto funkcjonalnym języku programowania wywołania funkcji nie mogą mieć skutków ubocznych na widoczny stan programu (inny niż jego wartość zwracana ), a różnica w kolejności pamięci maszyny wynikająca z kolejności wywołań funkcji będzie nieistotna dla semantyki programu. W językach proceduralnych wywoływane funkcje mogą mieć skutki uboczne, takie jak wykonywanie operacji we/wy lub aktualizowanie zmiennej w globalnym zasięgu programu, z których oba dają widoczne efekty w modelu programu.

Ponownie, programista zainteresowany tymi efektami może stać się bardziej pedantyczny w wyrażaniu oryginalnego programu źródłowego:

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

W językach programowania, w których granica instrukcji jest zdefiniowana jako punkt sekwencji, wywołania funkcji f , g i h muszą teraz być wykonywane w dokładnie takiej kolejności.

Specyficzne zagadnienia porządku pamięci

Efekty kolejności programu obejmujące wyrażenia wskaźnikowe

Rozważmy teraz to samo sumowanie wyrażone za pomocą wskaźnika pośredniego w języku takim jak C lub C++, który obsługuje wskaźniki : 

suma = *a + *b + *c;

Ocena wyrażenia *x jest określana jako „ dereferencja ” wskaźnika i obejmuje odczyt z pamięci w miejscu określonym przez bieżącą wartość x . Efekty odczytu ze wskaźnika są określane przez model pamięci architektury . Podczas odczytu ze standardowej pamięci programu nie występują żadne skutki uboczne ze względu na kolejność operacji odczytu z pamięci. W systemów wbudowanych bardzo często występuje mapowanie we/wy w pamięci gdzie odczyty i zapisy do pamięci wyzwalają operacje wejścia/wyjścia lub zmiany trybu pracy procesora, które są bardzo widocznymi skutkami ubocznymi. Dla powyższego przykładu załóżmy na razie, że wskaźniki wskazują na zwykłą pamięć programu, bez tych efektów ubocznych. Kompilator może dowolnie zmieniać kolejność tych odczytów w kolejności programu, jaką uzna za stosowną, i nie będzie żadnych efektów ubocznych widocznych dla programu.

Co jeśli przypisana wartość jest również pośrednia ze wskaźnikiem? 

*suma = *a + *b + *c;

Tutaj definicja języka raczej nie pozwoli kompilatorowi na rozbicie tego w następujący sposób:

// przepisane przez kompilator // generalnie zabronione *sum = *a + *b; *suma = *suma + *c;

W większości przypadków nie byłoby to postrzegane jako wydajne, a zapisy wskaźników mają potencjalne skutki uboczne w widocznym stanie maszyny. Ponieważ kompilator nie zezwala na tę konkretną transformację podziału, jedyny zapis w pamięci sumy musi logicznie następować po odczytach trzech wskaźników w wyrażeniu wartości.

Załóżmy jednak, że programista jest zaniepokojony widoczną semantyką przepełnienia liczb całkowitych i rozbija instrukcję na poziomie programu w następujący sposób:

// bezpośrednio autorstwa programisty // z aliasingiem dotyczy *sum = *a + *b; *suma = *suma + *c;

Pierwsza instrukcja koduje dwa odczyty pamięci, które muszą poprzedzać (w dowolnej kolejności) pierwszy zapis do *sum . Druga instrukcja koduje dwa odczyty pamięci (w dowolnej kolejności), które muszą poprzedzać drugą aktualizację *sum . Gwarantuje to kolejność dwóch operacji dodawania, ale potencjalnie wprowadza nowy problem aliasingu adresów : każdy z tych wskaźników może potencjalnie odnosić się do tego samego miejsca w pamięci.

Na przykład, załóżmy w tym przykładzie, że *c i *sum są aliasami do tego samego miejsca w pamięci i przepiszmy obie wersje programu z *sum w miejsce obu. 

*suma = *a + *b + *suma;

Nie ma tutaj żadnych problemów. Oryginalna wartość tego, co pierwotnie zapisaliśmy jako *c , zostaje utracona po przypisaniu do *sum , podobnie jak pierwotna wartość *sum , ale została ona nadpisana w pierwszej kolejności i nie ma specjalnego znaczenia. 

// czym staje się program z *c i *sum aliased *sum = *a + *b; *suma = *suma + *suma;

Tutaj pierwotna wartość *sum jest nadpisywana przed jej pierwszym dostępem i zamiast tego otrzymujemy algebraiczny odpowiednik: 

// algebraiczny odpowiednik powyższego aliasu *sum = (*a + *b) + (*a + *b);

który przypisuje zupełnie inną wartość do *sum ze względu na przegrupowanie instrukcji.

Ze względu na możliwe efekty aliasingu wyrażenia wskaźnika są trudne do zmiany kolejności bez ryzyka widocznych efektów programu. W typowym przypadku aliasing może nie działać, więc kod wydaje się działać normalnie, jak poprzednio. Ale w skrajnym przypadku, w którym występuje aliasing, mogą wystąpić poważne błędy programu. Nawet jeśli te skrajne przypadki są całkowicie nieobecne podczas normalnego wykonywania, złośliwemu przeciwnikowi otwiera to drzwi do wymyślenia danych wejściowych, w których istnieje alias, co potencjalnie prowadzi do wykorzystania luki w zabezpieczeniach komputera .

Bezpieczna zmiana kolejności poprzedniego programu jest następująca:

 // zadeklaruj tymczasową  zmienną lokalną  'temp' odpowiedniego typu temp = *a + *b; *suma = temp + *c;

Na koniec rozważ przypadek pośredni z dodanymi wywołaniami funkcji:

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

Kompilator może zdecydować się na ocenę *a i *b przed wywołaniem dowolnej funkcji, może odroczyć ocenę *b do czasu po wywołaniu funkcji f lub może odroczyć ocenę *a do czasu po wywołaniu funkcji g . Jeśli funkcje f i g są wolne od widocznych efektów ubocznych programu, to wszystkie trzy wybory spowodują utworzenie programu z tymi samymi widocznymi efektami programowymi. Jeśli implementacja f lub g zawierają efekt uboczny dowolnego zapisu wskaźnika podlegającego aliasingowi ze wskaźnikami a lub b , te trzy opcje mogą dawać różne widoczne efekty programu.

Kolejność pamięci w specyfikacji języka

Ogólnie rzecz biorąc, języki kompilowane nie są wystarczająco szczegółowe w swojej specyfikacji, aby kompilator mógł formalnie określić w czasie kompilacji, które wskaźniki są potencjalnie aliasowane, a które nie. Najbezpieczniejszym sposobem działania jest założenie przez kompilator, że wszystkie wskaźniki są potencjalnie aliasowane przez cały czas. Ten poziom konserwatywnego pesymizmu zwykle daje fatalne wyniki w porównaniu z optymistycznym założeniem, że aliasing nigdy nie istnieje.

W rezultacie wiele skompilowanych języków wysokiego poziomu, takich jak C/C++, ewoluowało w kierunku skomplikowanych i wyrafinowanych specyfikacji semantycznych określających, gdzie kompilatorowi wolno przyjmować optymistyczne założenia przy zmianie kolejności kodu w dążeniu do najwyższej możliwej wydajności, a gdzie kompilator jest zobowiązany do przyjęcia pesymistycznych założeń przy zmianie kolejności kodu, aby uniknąć zagrożeń semantycznych.

Zdecydowanie największa klasa efektów ubocznych we współczesnym języku proceduralnym obejmuje operacje zapisu w pamięci, więc reguły dotyczące porządkowania pamięci są dominującym elementem w definicji semantyki kolejności programów. Zmiana kolejności wywołań funkcji powyżej może wydawać się innym zagadnieniem, ale zwykle sprowadza się to do obaw o efekty pamięciowe wewnętrzne wywołanych funkcji, które wchodzą w interakcje z operacjami pamięciowymi w wyrażeniu, które generuje wywołanie funkcji.

Dodatkowe trudności i komplikacje

Optymalizacja pod warunkiem, że

Współczesne kompilatory czasami idą o krok dalej za pomocą zasady „jak gdyby” , w której dowolna zmiana kolejności jest dozwolona (nawet między instrukcjami), jeśli nie ma to wpływu na widoczną semantykę programu. Zgodnie z tą regułą kolejność operacji w przetłumaczonym kodzie może znacznie różnić się od określonej kolejności programu. Jeśli kompilator może przyjąć optymistyczne założenia co do różnych wyrażeń wskazujących, które nie nakładają się aliasów w przypadku, gdy takie aliasowanie rzeczywiście istnieje (zwykle byłoby to klasyfikowane jako źle sformułowany program wykazujący niezdefiniowane zachowanie ), negatywnych skutków agresywnej transformacji optymalizacyjnej kodu nie można odgadnąć przed wykonaniem kodu lub bezpośrednią inspekcją kodu. Sfera niezdefiniowanych zachowań ma niemal nieograniczone przejawy.

Programista jest odpowiedzialny za zapoznanie się ze specyfikacją języka, aby uniknąć pisania źle sformułowanych programów, w których semantyka może zostać zmieniona w wyniku jakiejkolwiek legalnej optymalizacji kompilatora. Fortran tradycyjnie nakłada na programistę duże obciążenie, aby był świadomy tych problemów, a języki programowania systemów C i C++ nie są daleko w tyle.

Niektóre języki wysokiego poziomu całkowicie eliminują konstrukcje wskaźników, ponieważ ten poziom czujności i dbałości o szczegóły jest uważany za zbyt wysoki, aby można go było niezawodnie utrzymać nawet wśród profesjonalnych programistów.

Pełne zrozumienie semantyki kolejności pamięci jest uważane za tajemną specjalizację nawet wśród subpopulacji profesjonalnych programistów systemów, którzy zazwyczaj są najlepiej poinformowani w tej dziedzinie. Większość programistów zadowala się odpowiednim praktycznym zrozumieniem tych zagadnień w ramach normalnej dziedziny ich wiedzy programistycznej. Na skrajnym końcu specjalizacji w semantyce kolejności pamięci znajdują się programiści, którzy tworzą ramy oprogramowania obsługujące modele obliczeń współbieżnych .

Aliasowanie zmiennych lokalnych

Zauważ, że nie można założyć, że zmienne lokalne są wolne od aliasingu, jeśli wskaźnik do takiej zmiennej ucieka w dzicz:

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

Nie wiadomo, co funkcja f mogłaby zrobić z dostarczonym wskaźnikiem do a , w tym pozostawienie kopii w stanie globalnym, do którego funkcja g ma później dostęp. W najprostszym przypadku f zapisuje nową wartość do zmiennej a , czyniąc to wyrażenie źle zdefiniowanym w kolejności wykonywania. Można wyraźnie temu zapobiec, stosując kwalifikator const do deklaracji jego argumentu wskaźnika, czyniąc wyrażenie dobrze zdefiniowanym. Tak więc współczesna kultura C/C++ stała się nieco obsesyjna na punkcie dostarczania kwalifikatorów const do deklaracji argumentów funkcji we wszystkich możliwych przypadkach.

C i C++ pozwalają elementom wewnętrznym f na odrzucenie atrybutu constness jako niebezpiecznego rozwiązania. Jeśli f robi to w sposób, który może zepsuć powyższe wyrażenie, nie powinien przede wszystkim deklarować typu argumentu wskaźnika jako const.

Inne języki wysokiego poziomu przechylają się w kierunku takiego atrybutu deklaracji stanowiącego silną gwarancję bez luk, które mogłyby naruszyć tę gwarancję zapewnioną w samym języku; wszystkie zakłady na tę gwarancję językową są wyłączone, jeśli twoja aplikacja łączy bibliotekę napisaną w innym języku programowania (chociaż jest to uważane za wyjątkowo zły projekt).

Implementacja bariery pamięci w czasie kompilacji

Zobacz też: Bariera pamięci

Bariery te uniemożliwiają kompilatorowi zmianę kolejności instrukcji w czasie kompilacji – nie uniemożliwiają zmiany kolejności przez procesor w czasie wykonywania.

  • Każda z tych instrukcji wbudowanego asemblera GNU zabrania kompilatorowi GCC zmiany kolejności poleceń odczytu i zapisu wokół niej: 
 asm volatile("" ::: "memory"); __asm__ __volatile__ ("" ::: "pamięć");
  • Ta funkcja C11/C++11 zabrania kompilatorowi zmiany kolejności poleceń odczytu i zapisu wokół niej: 
 atomic_signal_fence(memory_order_acq_rel); 
 __memory_barrier() 
 _ReadWriteBarrier()

Bariery kombinowane

W wielu językach programowania różne typy barier można łączyć z innymi operacjami (takimi jak ładowanie, przechowywanie, przyrost atomowy, porównywanie atomowe i zamiana), więc nie jest potrzebna żadna dodatkowa bariera pamięci przed lub po niej (lub obie). W zależności od docelowej architektury procesora, te konstrukcje językowe będą przekładać się na instrukcje specjalne, instrukcje wielokrotne (tj. barierę i obciążenie) lub normalne instrukcje, w zależności od gwarancji kolejności pamięci sprzętowej.

Kolejność pamięci w czasie wykonywania

W symetrycznych systemach wieloprocesorowych (SMP).

Istnieje kilka modeli spójności pamięci dla systemów SMP :

  • Spójność sekwencyjna (wszystkie odczyty i wszystkie zapisy są w kolejności)
  • Zrelaksowana spójność (dozwolone są niektóre rodzaje zmiany kolejności)
    • Ładunki można zmienić po załadowaniu (dla lepszej spójności pamięci podręcznej, lepszego skalowania)
    • Ładunki można ponownie zamówić po sklepach
    • Sklepy można ponownie zamówić po sklepach
    • Sklepy można ponownie zamówić po załadowaniu
  • Słaba spójność (odczyty i zapisy są dowolnie zmieniane, ograniczone jedynie jawnymi barierami pamięci )

Na niektórych procesorach

  • Operacje atomowe można zmienić za pomocą ładunków i magazynów.
  • Może istnieć niespójny potok pamięci podręcznej instrukcji, który uniemożliwia wykonanie samomodyfikującego się kodu bez specjalnych instrukcji opróżniania/przeładowywania pamięci podręcznej instrukcji.
  • Zależne ładunki można ponownie uporządkować (jest to unikalne dla Alpha). Jeśli procesor pobierze wskaźnik do niektórych danych po tej zmianie kolejności, może nie pobrać samych danych, ale użyć nieaktualnych danych, które już zapisał w pamięci podręcznej i nie zostały jeszcze unieważnione. Umożliwienie tego złagodzenia sprawia, że ​​sprzęt pamięci podręcznej jest prostszy i szybszy, ale prowadzi do wymogu barier pamięci dla czytelników i pisarzy. Na sprzęcie Alpha (takim jak wieloprocesorowy Alpha 21264 systemów) unieważnienia linii pamięci podręcznej wysyłane do innych procesorów są domyślnie przetwarzane w sposób leniwy, chyba że wyraźnie zażądano ich przetwarzania między zależnymi obciążeniami. Specyfikacja architektury Alpha pozwala również na inne formy zmiany kolejności obciążeń zależnych, na przykład przy użyciu spekulatywnych odczytów danych przed poznaniem rzeczywistego wskaźnika, który ma zostać wyłuskany.
Porządkowanie pamięci w niektórych architekturach
Typ Alfa ARMv7 MIPS RISC-V PA-RISC MOC SPARC x86 AMD64 IA-64 z/Architektura
WMO OSP RMO PSO OSP
Ładunki można ponownie zamówić po załadowaniu Y Y
zależą od realizacji 		Y Y Y Y Y
Ładunki można ponownie zamówić po sklepach Y Y Y Y Y Y Y
Sklepy można ponownie zamówić po sklepach Y Y Y Y Y Y Y Y
Sklepy można ponownie zamówić po załadowaniu Y Y Y Y Y Y Y Y Y Y Y Y Y
Atomic można zmienić z ładunkami Y Y Y Y Y Y
Atomic można ponownie zamówić w sklepach Y Y Y Y Y Y Y
Zależne obciążenia można zmienić Y
Niespójna pamięć podręczna/potok instrukcji Y Y Y Y Y Y Y Y Y Y
Modele zamawiania pamięci RISC-V
WMO
Słaba kolejność pamięci (domyślnie)
TSO
Całkowita kolejność pamięci (obsługiwana tylko z rozszerzeniem Ztso)
Tryby zamawiania pamięci SPARC
TSO
Całkowita kolejność pamięci (domyślnie)
RMO
Zrelaksowana kolejność pamięci (nieobsługiwana w najnowszych procesorach)
PSO
Częściowa kolejność w sklepie (nieobsługiwana w najnowszych procesorach)

Implementacja sprzętowej bariery pamięci

Zobacz też: Bariera pamięci

Wiele architektur z obsługą SMP ma specjalne instrukcje sprzętowe do opróżniania odczytów i zapisów w czasie wykonywania . 

 lfence (asm), void _mm_lfence (void) sfence (asm), void _mm_sfence (void) mfence (asm), void _mm_mfence (void) Synchronizacja 
 (asm) Synchronizacja  
 (asm) 
 MF (asm) 
 dcs (asm) 
 dmb (asm) dsb (asm) isb (asm)

Wsparcie kompilatora dla sprzętowych barier pamięci

Niektóre kompilatory obsługują wbudowane instrukcje emitujące sprzętową barierę pamięci:

Zobacz też

Dalsza lektura

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Memory_ordering&oldid=1137609192 ”