Brak w TLB i wielopoziomowy przebieg strony

Dlaczego pamięć wirtualna wymaga tłumaczenia na wszystkich poziomach

Pamięć wirtualna daje każdemu procesowi iluzję prywatnego, ciągłego przestrzeni adresowej, izolowanej od każdego innego procesu i często większej niż fizycznie zainstalowana pamięć RAM, mapując tę wirtualną przestrzeń na rozrzuteńczone fisze physical page frames, które są zazwyczaj po 4 kilobyty każda na systemach x86. To odrobinę indirekcyjności jest to, co sprawia, że ochrona pamięci jest możliwa — jedno proces nie może wyrazić prawidłowego adresu wskazującego na pamięć innego procesu, a to pozwala na funkcje takie jak wymiana fiszy do dysku, zapis tylko przy pisaniu dla fork i pliki mapowane do pamięci działa przezrocznie. Kosztem jest to, że każda operacja dostępu do pamięci, nie tylko rzadkie, musi mieć swój adres wirtualny przekształcony w fizyczny przed systemem pamięci będzie mógł pobrać coś, a to musi się stać szybko, aby nie stało się głównym kosztem każdej instrukcji ładowania i przechowywania. System operacyjny utrzymuje tę przekształcenie wirtualne na fizyczną w tablicach fiszów dla każdego procesu, ale tablica fiszów jest sama data structure siedząca w pamięci, więc bezwzględne sprawdzenie jej pod każdą operację dostępu oznaczałoby, że każda odniesienie do pamięci rzeczywiście wymaga wielu odnieśćń do pamięci, co byłoby nieakceptowalną mnożeniem opóźnień. Ta napięcie, potrzeba tłumaczenia pod każdą operację, ale nie chcąc płacić opóźnienia dostępu do pamięci za to tłumaczenie pod każdą operację, jest dokładnie problemem, który TLB jest zaprojektowany, aby rozwiązać. Rozumienie tego wyjaśnia wiele z tych, jak rzeczywistym działa system pamięci i jego wydajność.

TLB: Bufor przetłumaczeń

TLB to mały, bardzo associative cache, często zawierający od 64 do 1536 wpisów w zależności od poziomu i procesora, który przechowuje ostatnio używane mapowania numeru stron wirtualnej na numer ramki fizycznej bezpośrednio w szybkim sprzęcie blisko jądra CPU. Gdy CPU wystawia dostęp do pamięci, najpierw sprawdza, czy odpowiedni numer strony wirtualnej jest obecny w TLB; jeśli tak, to jest to trafienie TLB, a adres fizyczny jest dostępny prawie w jednym cyklu, nie wolniejszy niż typowe wyszukiwanie cache. Jeśli nie ma go, to jest to błąd TLB, a pełna przechodnica tablicy stron musi być wykonana przed tym, aby dostęp do pamięci mógł nastąpić w ogóle, co może dodać potencjalnie setki cykli opóźnienia. Ponieważ programy pokazują silną lokalność, powtarzająco dostępują do danych w takim małym zestawie stron przez krótkie okresy czasu, często osiągane są bardzo wysokie stopy trafień TLB, często przekraczające 99 procent dla dobrych obciążen, co sprawia, że nadmiar pamięci wirtualnej jest tolerowalny w praktyce. Obecnie współczesne procesory utrzymują oddzielne TLB dla instrukcji i danych, a często małe, bardzo szybkie L1 TLB wsparte większym, lekko wolniejszym L2 TLB, odbijając się na tym samym filozofii wielopoziomowego cacheowania używanej w cacheach danych. Niektóre architektury również obsługują strony ogromne, z rozmiarami stron 2MB lub 1GB zamiast standardowych 4KB, ponieważ taki wpis TLB może pokrywać znacznie więcej pamięci, co znacząco zmniejsza stopy błądów dla dużych, ciągłych struktur danych, takich jak bazy danych czy tablice obliczeń naukowych.

Przechodzenie przez wielopoziomową tabelę stron

Kiedy wystąpi brak w TLB (Pierwsze wyrenderowanie treści (FCP)), system musi sprawdzić rzeczywistą tabelę stron, ale pojedyncza płaskie tablica mapująca każdą możliwą stronę virtually directnie byłaby enormna. 64-bitowy przestrzeń adresowa z 4KB stron potrzebowałaby niepraktycznej liczby wpisów, jeśli byłaby implementowana jako jedno wielkie tablicy. Rozwiązanie używane przez prawie wszystkie współczesne architektury to wielopoziomowa, hierarchiczna tabela stron, często nazywana struktura drzewa radiks. Adres virtualny jest podzielony na kilka pole: najwyższe bity indeksują w górnej poziomowej kierunku stron, kolejne bity indeksują w drugiej poziomowej tabeli wskazywanej przez wpis znaleziony na pierwszym poziomie, a następnie tak dalej dla tyle poziomów, ile zdefiniuje architektura, zwykle czterech na x86-64, z najniższymi bitami służyjącymi jako offset w końcu fizycznego strony samej. Każda operacja wyszukiwania wymaga jednego rzeczywistego odczytu pamięci do pobrania wpisu dla danego poziomu, więc czteropoziomowe przechodzenie z pełnym brakiem wymaga do czterech kolejnych, zależnych odczytów pamięci tylko do obliczenia adresu fizycznego, przed tym samym instrukcji własny odczyt pamięci nawet mógłby rozpocząć się. Ten hierarchiczny podchód jest pamięcioefektywny dokładnie dlatego, że całe poddrzewa nieużywanej przestrzeni adresowej nigdy nie potrzebują w ogóle alokacji odpowiednich tabel stron, wpis, który nie jest obecny kończy przechodzenie o wiele wcześniej z błędem strony zamiast wymagać pełnej tablicy dla całej przestrzeni adresowej. Symulacja visaulizuje dokładnie to spadkowe wyszukiwanie, pokazując tabelę każdego poziomu, konkretne wpis wybrany przez każde pole adresu oraz śledzenie wskaźników, które w końcu prowadzą do numeru ramki fizycznego.

Strony brakujące, zderzenia TLB i rzeczywiste koszty

Przebieg tabeli stron może skończyć się na dwa bardzo różne sposoby. Jeśli wszystkie wpisy na każdym poziomie są obecne i oznaczone jako prawidłowe, przebieg powoduje sukces, procesor ma teraz adres fizyczny, a nową przekształcenie przechowuje w TLB przed zakończeniem oryginalnego dostępu do pamięci. Ale jeśli którykolwiek wpis na liście jest oznaczony jako nieobecny, być może dlatego, że ta strona nigdy nie została alokowana, lub została wymieniona na dysk aby zwolnić pamięć fizyczną, sprzęt podnosi wyjście braku strony, blokując proces do systemu operacyjnego, który musi następnie allokować nową stronę, załadować potrzebne dane z powrotem z dysku, lub zakończyć proces ze względu na nieprawidłowy dostęp, przed ponownym wykonaniem oryginalnej instrukcji. Strona brakująca wymagająca odczytu z dysku jest ogromnie droga, potencjalnie milion razy wolniejsza niż trafienie w TLB, co jest powodem dla którego systemy operacyjne pracują nad minimalizacją częstotliwości wyjści brakujących stron poprzez techniki takie jak przewidywane załadowywania i inteligentne polityki wymiany stron. Istnieje drugie, bardziej niewidoczne koszt specyficzny dla systemów wielokoreowych nazywany zderzeniem TLB: gdy jedna koreta zmienia wpis w tabeli stron, być może odznaczając stronę, każda inna koreta może nadal przechowywać teraz stare przekształcenie strony w TLB, więc system operacyjny musi wysłać interwencję międzyprocesową do każdej innej korety zmuszając ją do wykaszlenia odpowiedniego wpisu w TLB, operacja synchronizacji, która może być nieoczekiwanie droga na systemach z wieloma koretami. Oba te koszty, strony brakujące i zderzenia TLB, istnieją dokładnie dlatego, że TLB jest pamięcią podręczną, a pamięci podręczne zawsze wprowadzają fundamentalny problem utrzymania zgodności kopii przechowywanych z podstawą prawdziwą.

Dlaczego wzory dostępu zmieniają wszystko

Stosunek trafień w TLB jest bardzo czuły na sposób, w jaki program dotyka pamięci, co wyjaśnia, dlaczego ta sama algorytmy zaimplementowana w dwóch różnych sposobach może wykonywać się znacząco inaczej, nawet jeśli obie są logicznie poprawne. Seryjne lub zablokowane wzory dostępu, takie jak iterowanie po tablicy w porządku kolejnościowego lub przetwarzanie macierzy w blokach przyjaznych dla pamięci podręcznej, dotykają małej, stabilnej grupy stron w każdym momencie, utrzymując zestaw pracujący zrozumiały w granicach tego, co TLB może przechować, co prowadzi do stosunków trafień blisko 100 procent. Rozrzucane wzory dostępu losowe, takie jak śledzenie wskaźników przez dużą listę związaną lub tabelę hash rozłożoną na gigabajty pamięci, czy iterowanie po dużej macierzy w nieprawidłowej kolejności wymiarów, dotykają nowej, innej strony prawie na każdym dostępie, nadmiernie przekraczając zdolność TLB i spowodowując ciąg drogich braków, każdy z nich wyzwania nowy multiwielopoziomowy przebieg. To dokładnie dlaczego systemy baz danych, biblioteki obliczeń naukowych oraz uruchamiania o wysokiej wydajności nadużywają się layoutem danych, decyzjami struktura- tablica w stosunku do tablica-struktury, algorytmów niezależnych od pamięci podręcznej i użyciu dużych stron, nie dlatego, że podstawowe obliczenia się zmieniają, ale ponieważ rezultujący wzór dostępu do pamięci bezpośrednio determinuje jak często TLB musi być przebiegany. Symulacja pozwala na bezpośrednie porównanie seryjnego wzoru dostępu z rozrzucanym na tej samej wielkości danych i obserwować dramatyczną różnicę w tym, ile razy droga droga skomplikowana multiwielopoziomowa jest wyzwania, a ile razy szybka ścieżka trafień TLB jest zastosowana.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz TLB Miss & Multi-Level Page Table Walk i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.