5/30/2009
architektura komputerów
w. 7
Zarządzanie pamięcią
Zarządzanie pamięcią
Jednostka centralna dysponuje zwykle duża mocą obliczeniową. Sprawne wykorzystanie możliwości
jednostki przetwarzającej wymaga obecności systemu operacyjnego.
Procesory posiadajÄ… rozwiÄ…zania wspierajÄ…ce zadania systemu operacyjnego
Większość stosowanych systemów operacyjnych to systemy wieloprogramowe
W systemach jednoprogramowych program jest umieszczany pod stałymi adresami
W systemach jednoprogramowych z systemem operacyjnym pamięć jest dzielona miedzy SO
i program użytkowy.
W systemach wieloprogramowych w pamięci trzeba umieścić wiele programów
architektura komputerów w 7 1
5/30/2009
Zadania jednostki zarządzania pamięcią
Zarządzanie pamięcią:
uð Konieczność pomieszczenia w w ograniczonej przestrzeni pamiÄ™ci wielu procesów. (z czego część
będzie nieaktywna). Postuluje to zastosowanie skutecznego algorytmu wymiany procesów w SO
pomiędzy pamięcią operacyjna i zewnętrzną lub zwiększenie przestrzeni adresowej (np. przez
wirtualizacjÄ™)
uð Konieczność zapewnienia procesom identycznego sposobu widzenia przestrzeni adresowej.
Załadowanie kilku procesów oznacza, ze będą one umieszczone począwszy od różnych adresów
fizycznych w pamięci.
uð Ochrona kodu i danych
Fð Konieczność zapewnienia ochrony kodu i danych przed odczytem lub modyfikacjÄ… przez inny proces
Fð Ochrona przed niepoprawnym dostÄ™pem w obrÄ™bie procesu (np. wykonania danych)
uð Dynamiczna alokacja pamiÄ™ci dla poszczególnych procesów w razie potrzeby
uð Wirtualizacja przestrzeni pamiÄ™ci pozwalajÄ…ca na zwiÄ™kszenie dostÄ™pnej przestrzeni adresowej dla
każdego procesu
Zarządzanie pamięcią
Część kodu (jadro SO) jest stale obecne w pamięci operacyjnej
Pozostałą częścią trzeba zarządzać ładując i nadzorując wykonanie procesów
Proces operuje na adresach logicznych
Adres logiczny jest w jednostce zarządzania pamięcią:
uð Sprawdzany pod katem poprawnoÅ›ci
uð Zamieniany na adres fizyczny
Metody działania:
Relokacja
Segmentacja (podział na elementy o nierównej długości, może być widoczny dla
programisty)
Stronicowanie (podział na elementy o równej długości, niewidoczny dla programisty)
architektura komputerów w 7 2
5/30/2009
Relokacja
Wytwarzanie adresu fizycznego
" Proces korzysta z dwóch rejestrów MMU, jeden zawiera adres bazowy dla obliczania
adresu fizycznego, drugi adres końca przydzielonego obszaru (lub długość
przydzielonego obszaru)
pamięć
Adres logiczny
Obszar
Adres fizyczny przydzie
Adres bazowy lony dla
+
procesu
Adres końcowy
>
błąd
Relokacja
Pamięc podzielona jest na obszary
" o stałej (różnej) wielkości
" przydział metodą najlepszego dopasowania
lub na obszary
" o zmiennej wielkości
" Przydział żądanego obszaru, metody BF, FF
" Możliwość zwiększania przydzielonego obszaru o ile jest to możliwe
" Prowadzi do fragmentacji pamięci
pamięć
Obszar Obszar Obszar Obszar Obszar Obszar
systemo systemo systemo systemo systemo systemo
wy wy wy wy wy wy
proces4 proces4 proces4
proces1
proces5 proces5 proces5 proces5
proces2 proces2
proces3 proces3 proces3 proces3 proces3 proces3
proces6 proces6
proces7 proces7
architektura komputerów w 7 3
5/30/2009
Relokacja
Zwiększenie wymaganego obszaru może wymagać relokacji procesu.
Obszar Obszar
systemo systemo
Proces 1
wy wy
żąda
proces1 proces1
dodatkowej
pamięci
proces3 proces3
proces1
Segmentacja i stronicowanie
Segmentacja
" Przestrzeń adresowa procesu dzielona jest na segmenty zgodnie z jego logiczną
strukturÄ…
" Kod
" Dane
" Stos
" Adres logiczny składa się z dwóch elementów  adresu segmentu i przesunięcia
wewnÄ…trz segmentu
" Może być wiele segmentów zarówno dla kodu jak i danych
" Pamięć dla struktur danych w tej organizacji może być dynamicznie alokowana przez
zwiększenie rozmiaru segmentu (co może wymagać relokacji segmentu) lub
utworzenie nowego segmentu
" Możliwa jest ochrona poprzez określenie praw dostępu do segmentu
" Możliwe jest dopuszczanie kilku procesów do korzystania z segmentu danych
" Metoda posiada wady:
" dynamiczna alokacja pamięci prowadzi do fragmentacji
" Praktycznie nierealizowalna pamięć wirtualna
architektura komputerów w 7 4
5/30/2009
Segmentacja i stronicowanie
Segmentacja:
Adres logiczny w systemie z segmentacja składa się z
uð Identyfikatora segmentu
uð Adresu wewnÄ…trz segmentu (offset)
Na podstawie identyfikatora segmentu odnajdywany jest deskryptor
segmentu
Deskryptor segmentu zawiera
uð InformacjÄ™ o prawach dostÄ™pu
uð DÅ‚ugość segmentu
uð Adres bazowy segmentu
Translacja adresu polega na obliczeniu adresu fizycznego z adresu
bazowego i offsetu
Jeżeli
uð Typ dostÄ™pu jest niezgodny z prawami dostÄ™pu do segmentu
uð Offset przekracza zakres segmentu
uð Deskryptor jest nieważny
Jednostka zgłasza błąd.
Segmentacja i stronicowanie
Stronicowanie:
Uzasadnieniem stosowania stronicowania jest zasada lokalności
Podział pamięci na bloki o określonej długości  stronicowanie
Przestrzeń adresowa procesu jest jednowymiarowa  podział na strony odbywa się
przez odwzorowanie adresu logicznego na odnośnik do strony i offset na stronie
Bloki przestrzeni fizycznej - strony fizyczne
Bloki przestrzeni logicznej - strony logiczne
Stronicowanie nie jest widoczne dla programisty
Deskryptory stron umieszczane sÄ… w tablicach.
Opis strony zawiera znaczniki praw dostępu do strony i bity atrybutów
wykorzystywane przez SO
Stronicowanie jest głównym mechanizmem wykorzystywanym w budowie pamięci
wirtualnej
architektura komputerów w 7 5
5/30/2009
Segmentacja i stronicowanie
Stronicowanie:
Każdy z procesów posiada własną tablicę deskryptorów
proces może mieć większe rozmiary niż rozmiar pamięci.
uð VAX  max wielkość procesu 2 GB. = 222 stron 0,5KB
uð Tablica deskryptorów w tym przypadku ma wielkość 4MB
Stosowane są tablice dwupoziomowe i trójpoziomowe.
Typowy proces ma wielkość kilkudziesięciu MB
Typowa wielkość tablic dla procesu 20-80KB
Tablica pierwszego poziomu jest wskazywana przez specjalny rejestr procesora
(CR3 w Pentium)
uð Rejestr systemowy, niedostÄ™pny dla użytkownika
uð PrzeÅ‚adowywany w trakcie przeÅ‚Ä…czania procesów
Stronicowanie
Adres logiczny
offset
Strona
procesu A
Strona
procesu A
Strona
Adres fizyczny
Adres fizyczny
procesu A
offset
Strona
procesu A
Tablica procesu A
Typowy rozmiar strony  4kB lub 8 kB
Opis strony zawiera znaczniki praw dostępu do strony i bity atrybutów wykorzystywane
przez SO
W przypadku niezgodności typu dostępu z prawami dostępu w deskryptorze jednostka
blokuje dostęp i zgłasza błąd
architektura komputerów w 7 6
5/30/2009
Segmentacja i stronicowanie
Podstawowa jednostką sprzętową realizującą stronicowanie jest bufor translacji (TLB-
Translation Lookaside Buffer).
Adres logiczny jest dzielony na potrzeby stronicowania na dwie części  wirtualny numer
strony (VPN) i adres na stronie (offset)
Translacja adresu polega na przyporzÄ…dkowaniu stronie wirtualnej numeru strony
rzeczywistej.
TLB dysponuje cache asocjacyjnym i przechowuje deskryptory kilku ostatnio
wykorzystywanych stron. (W procesorze Pentium - 32)
Adres logiczny
VPN offset
TLB
VPN PPN
Adres fizyczny
PPN offset
Segmentacja i stronicowanie
Stronicowanie:
W przypadku niezgodności typu dostępu z prawami dostępu w deskryptorze jednostka
blokuje dostęp i zgłasza błąd
W przypadku chybienia (braku deskryptora strony w TLB) żądany deskryptor ładowany
jest z tablicy deskryptorów stron przechowywanej w pamięci.
Chybienie oznacza 2  4 dostępów do pamięci  istotna jest minimalizacja ilości
chybień
uð Chybienie wynika z maÅ‚ej pojemnoÅ›ci TLB
uð Duża ilość deskryptorów wynika z maÅ‚ego rozmiaru strony co wynika z wirtualizacji
uð Mniej deskryptorów to mniej chybieÅ„  pamięć przeznaczona dla jÄ…dra SO nie musi
podlegać wirtualizacji
uð Można użyć kilku rozmiarów stron
architektura komputerów w 7 7
5/30/2009
Stronicowanie  pamięć wirtualna
Nie jest konieczne ładowanie do pamięci wszystkich stron procesu. Strony
chwilowo niepotrzebne mogą być przechowywane w pamięci zewnętrznej
Minimalna przestrzeń potrzebna do funkcjonowania procesu  zbiór roboczy
Żądanie dostępu do strony nieobecnej w pamięci fizycznej powoduje błąd
dostępu i konieczność załadowania żądanej strony.
Żądana strona musi zostać sprowadzona do pamiÄ™ci (ððSO), tablica stron
zaktualizowana a próba dostępu procesu wykonana powtórnie po zakończeniu
operacji.
W przypadku braku miejsca jedna ze stron obecnych w pamięci operacyjnej
powinna być usunięta.
Proces wymiany może być nieefektywny ððmigotanie stron.
Nie należy wymieniać strony, która jest częścią zbioru roboczego
aktywnego procesu i nie należy uaktywniać procesu, którego zbiór roboczy
nie może być umieszczony w całości w pamięci
Pamięć wirtualna
Strategie zarządzania pamięcią
uð strategie pobierania (fetch policy)  decyzje, kiedy zaÅ‚adować informacjÄ™ do
pamięci głównej
uð strategie przydziaÅ‚u (placement policy)  reguÅ‚y i algorytmy wpasowania bloków
informacji w wolne obszary pamięci głównej
uð strategie wymiany (relocation policy)  reguÅ‚y i algorytmy usuwania informacji z
pamięci głównej.
Strategie pobierania
uð pobranie wymuszone (demand fetching) na skutek bÅ‚Ä™du braku obiektu
(missing item fault)
uð pobranie antycypowane (prefetching) na podstawie prognozy
architektura komputerów w 7 8
5/30/2009
Segmentacja i stronicowanie
" FlatModel
płaski model pamięci  bez
podziału na segmenty
" Segmented Model
Pamięć podzielona na segmenty
" Real-Address-Model
segmentacja typu x86
Pentium  Flat Model
architektura komputerów w 7 9
5/30/2009
Pentium  Flat Model
Relokacja Pentium  Protected Flat
Model
architektura komputerów w 7 10
5/30/2009
Relokacja Pentium  Segmented
Model
Zarządzanie pamięcią - Pentium
Niesegmentowana
pamięć niestronicowana
Niesegmentowana
pamięć stronicowana
segmentowana pamięć
niestronicowana
segmentowana pamięć
stronicowana
architektura komputerów w 7 11
5/30/2009
Segmentacja - Pentium
" Adres logiczny
31 0
Indeks segmentu TIPL Adres względny
RPL
15 3 0
RPL (Requested Privilege Level) - poziom uprzywilejowania
Indeks segmentu  indeks do tablicy segmentów
" Dla każdego segmentu określony jest poziom uprzywilejowania (0-3)
" Proces ma dostęp tylko do takich segmentów danych, których poziom
uprzywilejowania jest niższy lub równy poziomowi uprzywilejowania segmentu kodu.
" Niektóre rozkazy mogą być wykonywane wyłącznie na określonym poziomie
uprzywilejowania
" Poziom uprzywilejowania segmentu danych (clearance) określa dopuszczalność zapisu
dla segmentu.
Segmentacja - Pentium
architektura komputerów w 7 12
5/30/2009
Segmentacja - Pentium
31 0
Odniesienie do segmentuRPL Adres względny
15 3 0
RPL- poziom uprzywilejowania
Odniesienie do segmentu  indeks do tablicy segmentów
Odniesienie do segmentu Adres względny
Tablica
deskryptorów
Adres bazowy
Segment
+
Descriptor
Adres fizyczny
Segmentacja - Pentium
Deskryptor segmentu
D A D
Seg limit
Base 31:24 G / 0 V p P s type Base 23:16
16:19
B L L
Base 15:0 Segment limit 15:0
Struktura deskryptora segmentu (jedna pozycja w tablicy deskryptorów segmentów)
AVL  dostępny do użycia przez SO
BASE  bazowy adres segmentu
DPL  poziom uprzywilejowania deskryptora
G  ziarnistość (Segment Limit podany w bajtach lub jednostkach 4kB)
LIMIT  rozmiar segmentu
P  bit obecności
S  typ segmentu (dane/kod)
TYPE  typ segmentu (r/w,ro,execute, exp,accessed)
architektura komputerów w 7 13
5/30/2009
Segmentacja - Pentium
Rejestry segmentowe Pentium składają się z dwóch części. Część ukryta służy jako
cache dla informacji zawartej w tablicy deskryptorów segmentów i ładowana jest
każdorazowo wraz z zapisem widocznej części
Stronicowanie - Pentium . Pamięć wirtualna
Translacja adresu  strona 4KB
kartoteka tablica offset
Adres fizyczny
Odnośnik do strony
Odnośnik do
tablicy stron
PDBR
architektura komputerów w 7 14
5/30/2009
Stronicowanie - Pentium . Pamięć wirtualna
Translacja adresu  strona 4MB
31 22 21 0
kartoteka tablica offset
Adres fizyczny
Odnośnik do
strony
PDBR
Stronicowanie - Pentium . Pamięć wirtualna
Deskryptor strony 4KB.
p P p U R
Page Base Address avail G a d D C w / / p
t D t s W
G  strona globalna
Dirty  strona zmodyfikowana
Accessed  był dostęp do strony
PCD  zakaz buforowania w cache
PWT  buforowanie w cache typu write-trough
US  użytkownik/system
RW  RO/RW
Present  znacznik obecności w pamięci operacyjnej
architektura komputerów w 7 15
5/30/2009
Stronicowanie - Pentium . Pamięć wirtualna
Każdy proces ma własną tablicę 1 poziomu oraz kilka tablic 2 poziomu
Typowa zajętość pamięci przez tablice procesu  20-80KB
Część pamięci nie podlega wirtualizacji
uð JÄ…dro systemu
uð Bufory i sterowniki urzÄ…dzeÅ„ zewnÄ™trznych (np. pamięć obrazu)
Pentium . Zarządzanie pamięcią
architektura komputerów w 7 16