Architektura Komputerów/Wykład 12: Zarządzanie pamięcią

Plan wykładu





Funkcje systemu zarządzania pamięcią





Jednostka zarządzania pamięcią



  • Zarządzanie pamięcią wymaga umieszczenia pomiędzy jednostką wykonawczą procesora i pamięcią operacyjną dodatkowego bloku funkcjonalnego - jednostki zarządzania pamięcią
  • Adres wytwarzany przez jednostkę wykonawczą zgodnie z użytkowym modelem programowym procesora jest nazywany adresem logicznym lub wirtualnym
  • Adres ten trafia do jednostki zarządzania pamięcią która sprawdza poprawność odwołania i (dla poprawnych odwołań) generuje adres podawany na wejście pamięci fizycznej, zwany adresem fizycznym


Jednostka zarządzania pamięcią




Prosta relokacja



  • Prosta metoda zarządzania pamięcią stosowana w latach 60-tych XX wieku
  • Odwołania w trybie systemowym nie przechodzą przez jednostkę zarządzania pamięcią
    • system operuje w fizycznej przestrzeni adresowej


Jednostka relokacji - ICL1900/ODRA1300




Translacja adresu w jednostce relokacji



  • Jednostka zawiera dwa rejestry:
    • rejestr DATUM (base) zawiera fizyczny adres bazowy obszaru pamięci przypisanego procesowi
    • rejestr LIMIT zawiera adres fizyczny końca obszaru przydzielonego procesowi
      • w innych rozwiązaniach rejestr limitu zawiera rozmiar obszaru
  • Adres logiczny jest sumowany z zawartością rejestru bazowego
  • Uzyskany w ten sposób adres fizyczny jest porównywany z zawartością rejestru limitu
    • jeśli adres fizyczny przekracza wartość rejestru, odwołanie nie dochodzi do skutku i sygnalizowany jest błąd
  • Każdy proces ma własne wartości rejestrów bazy i limitu
    • podczas przełączania procesów następuje ładowanie nowych wartości do rejestrów


Prosta relokacja - alokacja pamięci



  • Alokacja pamięci realizowana przez rozszerzenie obszaru zajmowanego przez proces
  • Obszar może być rozszerzony, o ile obszar położony bezpośrednio za nim nie jest zajęty przez inny proces
    • w przypadku zajętości - system operacyjny przemieszcza procesy w pamięci w celu uzyskania wolnego obszaru o odpowiedniej długości
    • po przemieszczeniu obszaru system stosownie modyfikuje adresy bazowe i limity zawarte w deskryptorach procesów


Fragmentacja pamięci



  • Wielokrotna alokacja i dealokacja obszarów o różnych rozmiarach powoduje powstawanie w fizycznej przestrzeni adresowej wielu pustych obszarowo małych rozmiarach
  • Obszary te są zbyt małe, by można ich było użyć do alokacji kolejnego bloku pamięci, pomimo, że łączny rozmiar tych obszarów wystarczyłby do alokacji
  • Zjawisko to nazywa się fragmentacją zewnętrzną pamięci


Charakterystyka jednostki relokacji



  • Jednostka relokacji realizuje trzy z czterech funkcji zarządzania pamięcią
    • relokacja
    • ochrona - bez możliwości kontroli rodzaju odwołania (pobranie instrukcji/odczyt/zapis danych)
    • dynamiczna alokacja - tylko przez rozszerzenie obszaru, niska sprawność, powoduje fragmentację pamięci
  • Wirtualizacja niemożliwa wobec braku możliwości podziału przestrzeni adresowej procesu


Segmentacja



  • Segmentacja jest uogólnieniem metody relokacji
  • Jednostka zarządzania pamięcią implementująca segmentację jest nazywana jednostką segmentacji
  • Przestrzeń adresowa procesu podzielona w sposób wynikający z jej logicznej struktury
    • kod
    • dane statyczne
      • stałe, zmienne
    • stos
    • sterta
  • Obszary te mogą mieć różne długości - są one nazywane segmentami
  • Segmentacja jest zwykle widoczna na poziomie modelu programowego użytkownika


Adresy logiczne w segmentacji



  • Logiczna przestrzeń adresowa jest dwuwymiarowa
    • częściowe naruszenie postulatów von Neumanna 
  • Adres logiczny składa się z dwóch części:
    • identyfikatora segmentu
    • adresu wewnątrzsegmentowego (offset)
  • Jednostka transluje adresy w przestrzeni dwuwymiarowej do adresów w przestrzeni jednowymiarowej - liniowej
  • Adres generowany przez jednostkę segmentacji nazywa się adresem liniowym


Translacja adresu w jednostce segmentacji



  • Jednostka segmentacji otrzymuje na wejściu adres w postaci pary (identyfikator segmentu, adres wewnątrzsegmentowy) oraz informacje o typie i poziomie zaufania dostępu
  • Na podstawie identyfikatora segmentu jednostka segmentacji odnajduje deskryptor segmentu
  • Deskryptor segmentu zawiera:
    • znacznik ważności
    • prawa dostępu do segmentu
    • rozmiar segmentu
    • liniowy adres bazowy segmentu



  • Jednostka segmentacji zgłasza błąd dostępu i uniemożliwia wykonanie odwołania do pamięci jeżeli:
    • deskryptor jest nieważny
    • typ dostępu jest niezgodn z prawami dostępu określonymi w deskryptorze
    • adres wewnątrzsegmentowy przekracza rozmiar segmentu
  • Jeżeli błąd nie zostanie wykryty, jednostka segmentacji generuje adres liniowy odwołania poprzez zsumowanie liniowego adresu bazowego z deskryptora segmentu z adresem wewnątrzsegmentowym przesłanym przez jednostkę wykonawczą


Deskryptor segmentu - x86




Alokacja pamięci w komputerach z segmentacją



  • Alokacja może następować na dwa sposoby:
    • rozszerzenie istniejącego segmentu sterty
    • alokacja nowego segmentu sterty
  • W obu przypadkach następuje fragmentacja pamięci
    • rozszerzenie istniejącego segmentu zwykle wymaga przemieszczenia tego lub innych segmentów


Pamięć wirtualna na bazie segmentacji



  • Realizacja systemu pamięci wirtualnej wymaga podzielenia przestrzeni adresowej procesu na wiele fragmentów
    • w przypadku segmentacji oznacza to konieczność podzielenie programu na wiele segmentów kodu i sterty
  • Typowo przestrzeń adresowa składa się z:
    • jednego lub wielu segmentów kodu
    • jednego segmentu danych statycznych (ew. wydzielony segment stałych)
    • jednego segmentu stosu
    • jednego lub wielu segmentów sterty
  • Podział kodu i sterty komplikuje operacje na wskaźnikach
  • Występuje fragmentacja pamięci masowej, której uciąglanie jest bardzo wolne (sekundy lub minuty)


Charakterystyka segmentacji



  • Zalety:
    • skuteczna relokacja
    • b. dobra ochrona, wynikająca ze struktury logicznej przestrzeni adresowej
  • Wady:
    • komplikacja modelu programowego (dwuelementowy adres)
    • problematyczna i niewydajna dynamiczna alokacja
    • praktycznie nierealizowalna pamięć wirtualna
  • Segmentacja w opisanej postaci praktycznie nie występuje we współczesnych architekturach
    • za wyjątkiem x86 - zaszłość historyczna
  • Niektóre architektury implementują uproszczoną segmentację niewidoczną w modelu programowym użytkownika - IBM POWER


Stronicowanie



  • Polega na podziale logicznej i fizycznej przestrzeni adresowej na bloki o długości wyrażonej potęgą liczby 2, naturalnie wyrównane
  • Podział nie ma związku z logiczną strukturą przestrzeni adresowej
  • Bloki przestrzeni logicznej są nazywane stronami logicznym/wirtualnymi lub stronami
  • Bloki przestrzeni fizycznej są nazywane stronami fizycznymi lub ramkami stron
  • W dawniejszych realizacjach rozmiar stron jest stały, w nowszych może być kilka rozmiarów stron
    • rozmiar strony zależy od jednostki zarządzania pamięcią i ew. systemu operacyjnego
  • Stronicowanie jest niewidoczne w modelu programowym
 

Jednostka stronicowania



  • Jednostka zarządzania pamięcią realizująca metodę stronicowania jest nazywana jednostką stronicowania 
  • Typowy rozmiar strony wynosi 4 lub 8 KB (rok 2006)
    • niektóre jednostki stronicowania umożliwiają również jedoczesną pracę z większymi stronami
  • Translacja adresu polega na przyporządkowaniu stronie logicznej strony wirtulanej
  • Dla potrzeb translacji adres logiczny jest wewnątrz jednostki stronicowania dzielony na dwa pola
    • numer strony wirtualnej (VPN)
    • adres wewnątrzstronicowy (offset)
  • Podczas translacji VPN zostaje zastąpiony przez numer strony fizycznej (PPN)
    • adres wewnątrzstronicowy nie zmienia się


Stronicowanie - translacja adresów




Bufor translacji



  • Podstawową strukturą sprzętową jednostki stronicowania jest bufor translacji, występujący pod nazwami:
    • TLB (translation lookaside buffer) - nazwa historyczna, najczęściej używana
    • TB (translation buffer)
    • ATC (address translation cache)
  • Bufor translacji przechowuje pewną liczbę ostatnio używanych ważnych deskryptorów stron
  • Bufor jest kieszenią pełnoasoscjacyjną lub zbiorowo-asoscjacyjną o wysokiej asocjacynjości




Translacja adresu w jednostce stronicowania



  • Na podstawie VPN bufor translacji odnajduje deskryptor strony
    • przy braku deskryptora strony (chybienie TLB) - inicjowana jest akcja zależna od realizacji jednostki stronicowania
  • Deskryptor strony zawiera
    • znacznik ważności (zawsze ważny jeśli deskryptor jest w TLB)
    • znaczniki praw dostępu do strony
    • fizyczny numer strony
    • dodatkowe bity atrybutów - do wykorzystania przez system operacyjny
  • Jeżeli informacja o typie dostępu z jednostki wykonawczej nie jest zgodna z prawami dostępu opisanymi w deskryptorze -jednostka stronicowania zgłasza błąd i blokuje dostęp
  • W przeciwnym razie adres fizyczny powstaje przez konkatenację fizycznego numeru strony i adresu wewnątrzstronicowego


Deskryptor strony - x86




Obsługa chybień bufora translacji

 

  • W przypadku chybienia konieczne jest załadowanie nowego deskryptora strony do bufora translacji
  • Deskryptory stron są przechowywane przez system operacyjny w tablicach umieszczonych w pamięci
    • w "CISCowych" jednostkach stronicowania pobraniem deskryptora z pamięci zajmuje się mikrokod jednostki stronicowania (x86, SPARC)
    • w "RlSCowych" jednostkach stronicowania chybienie TLB generuje błąd. obsługiwany przez system operacyjny-ładowaniem deskryptora zajmuje się system (MIPS. Alpha)
  • Do TLB nie ładuje się deskryptorów nieważnych
    • napotkanie nieważnego deskryptora generuje błąd dostępu


Implantacja pamięci wirtualnej na bazie stronicowania



  • Duża liczba stron umożliwia elastyczne określenie zbioru roboczego
    • wiele stron "chwilowo niepotrzebnych" może zostać przeniesionych do pamięci masowej
    • algorytm wymiany stron może korzystać z bitów znaczników dostępu (Acessed) i zapisu (Dirty) w deskryptorach stron
  • Stały rozmiar strony eliminuje fragmentację pamięci operacyjnej i masowej
    • w miejscu zwolnionym przez stronę zawsze można zaalokować nową stronę
    • brak konieczności uciąglania pamięci operacyjnej i masowej
  • Implementacja pamięci wirtulanej jest łatwa i efektywna
  • Stronicowanie zostało opracowane z myślą o implementacji systemu pamięci wirtualnej


Przechowywanie deskryptorów stron



  • Typowy przypadek:
    • procesor 32-bitowy
    • strony o rozmiarze 4 KB
    • przestrzeń adresowa zawiera 220 stron
    • prosty deskryptor strony zajmuje 4 bajty
    • 220 deskryptorów - 4 MB
  • W celu zmniejszenia zajętości pamięci deskryptory przechowuje się w pamięci strukturach tablicowo-drzewiastych
    • drzewo tablic (przykład - x86)
      • tablice zawierają po 1024 deskryptory
      • dwa poziomy tablic
    • deskryptor nieważny oznacza brak następnej tablicy - cały fragment przestrzeni adresowej jest nieważny
    • deskryptor ważny wskazuje tablicę deskryptorów



  • Odwzorowanie adresów wirtualnych w fizyczne jest unikatowe dla każdego procesu
  • Każdy proces ma własne tablice deskryptorów
  • Tablica pierwszego poziomu jest wskazywana przez specjalny rejestr procesora - rejestr bazowy tablic deskryptorów stron
    • jest to rejestr systemowy, niedostępny dla użytkownika
    • jest on przeładowywany podczas przełączania procesów
    • w x86 rejestr ten nosi oznaczenie CR3


Dwupoziomowe tablice deskryptorów




Dwupoziomowe tablice deskryptorów (x86)



  • Adres wirtualny dzieli się na 3 pola
    • INDEX1 - 10 bitów
    • INDEX2 - 10 bitów
    • OFFSET - 12 bitów
  • Najbardziej znaczące bity adresu wybierają deskryptor z tablicy pierwszego poziomu
    • jeden deskryptor opisuje 222 = 4 MB przestrzeni adresowej
    • deskryptor nieważny oznacza, że proces nie ma dostępu do całego 4-megabajtowego obszaru przestrzeni adresowej
    • deskryptor ważny wskazuje tablicę drugiego poziomu
  • Tablica drugiego poziomu jest indeksowana wartością INDEX2
    • tablica zawiera deskryptory stron
  • Każda tablica ma rozmiar 4 KB, czyli zajmuje jedną stronę


Dwupoziomowe tablice stron - zajętość pamięci



  • Przestrzeń adresowa procesu dzieli się na część użytkownika i systemową
  • Część systemowa jest wspólna dla wszystkich procesów
    • tablice drugiego poziomu opisujące część systemową są wspólne dla wszystkich procesów
  • Każdy proces ma własną tablicę pierwszego poziomu
  • Każdy proces ma własne tablice drugiego poziomu opisujące przejrzeń adresową w części użytkownika
  • Typowy proces zajmuje do kiludziesięciu MB w czterech obszarach
    • potrzeba od czterech do kilkunastu tablic drugiego poziomu plus jednej pierwszego poziomu
    • typowa zajętość pamięci przez tablice - 20..80 KB. czyli niewiele ponad 1/1000 zajętości pamięci przez proces


Trójpoziomowe tablice deskryptorów



  • Zmiany alokacji w części systemowej o zasięgu przekraczającym 4 MB powodują konieczność modyfikowania tablic pierwszego poziomu
  • Przy dwupoziomowej strukturze tablic oznacza to konieczność modyfikacji wielu tablic pierwszego poziomu
  • Rozwiązanie - tablice trójpoziomowe
    • "nowy" pierwszy poziom dzieli przestrzeń adresową na kilka obszarów (np.4)
    • zmiany w systemowych tablicach drugiego (wcześniej pierwszego) poziomu nie wymagają zmian na pierwszym poziomie
      • zmienia się tylko zawartość tablic, a nie położenie


Trójpoziomowe tablice deskryptorów - x86




Stronicowanie w procesorach 64-bitowych



  • Adres logiczny - 64 bity
  • Adres wirtualny - krótszy od logicznego, np. 52 bity
    • dozwolony zakres adresów wirtualnych leży na początku i na końcu przestrzeni logicznej
    • są to tzw. adresy kanoniczne, w których pewna liczba najbardziej znaczących bitów ma tę samą wartość (0 albo 1)
    • odwołania do adresów niekanonicznych generują błąd dostępu
  • Długi adres wirtualny wymaga budowy struktur tablicowo-drzewiastych o dużej liczbie poziomów
    • AMD64 - 4 poziomy


Wielopoziomowe tablice deskryptorów - AMD64




Redukcja chybień bufora translacji



  • Chybienie bufora translacji powoduje konieczność przejrzenia struktur danych w pamięci (tzw. table walk)
  • Ponieważ chybienia są rzadkie, dane z tablic deskryptorów rzadko znajdują się w kieszeniach
    • konieczne wykonanie 2.4 dostępów do pamięci operacyjnej - we współczesnych procesorach jest to równoważne wykonaniu nawet kilkuset instrukcji
  • Wysoki koszt chybienia powoduje konieczność redukcji liczby chybień
  • Chybienia wynikają z ograniczonej pojemności bufora translacji
    • większa pojemność - mniejsza szybkość
    • liczbę chybień można zmniejszyć zmniejszając liczbę używanych deskryptorów



  • Duża liczba potrzebnych deskryptorów wynika z niewielkich rozmiarów stron
  • Małe rozmiary stron wynikają z potrzeby wirtualizacji
  • Brak wirtualizacji oznacza brak konieczności podziału przestrzeni adresowej na strony
  • Obszary nie podlegające wirtualizacji:
    • jądro systemu
    • cala pamięć fizyczna komputera odwzorowana w przestrzeni systemu
    • urządzenia wejścia-wyjścia, np. sterownik graficzny (pamięć obrazu)
  • Obszary te mogą być opisane mniejszą liczbą deskryptorów "dużych" stron


"Duże" strony - x86



  • "Normalny" deskryptor w tablicy pierwszego poziomu opisuje obszar 4 MB podzielony na strony po 4 KB
  • Deskryptor "dużej" strony w tablicy pierwszego poziomu opisuje obszar 4 MB nie podzielony na strony
    • jeden deskryptor wystarcza do opisu całych 4 MB przestrzeni adresowej
  • Analogiczne rozwiązanie istnieje dla wariantu z trzema poziomami tablic
  • duża strona ma rozmiar 2 MB
  • W AMD64 - dostępne strony o rozmiarze 2 MB i 1 GB
 

Stronicowanie ze stronami o rozmiarze 4MB - x86