Systemy operacyjne
Systemy operacyjne
Maciej J. Bargielski
Maciej J. Bargielski
Pamięć operacyjna
Zarządzanie pamięcią
Zarządzanie pamięcią
Podstawy.
Logiczna i fizyczna przestrzeń adresowa.
Wymiana (swapping).
Przydział ciągły.
Stronicowanie.
Segmentacja.
Segmentacja ze stronicowaniem.
2
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Podstawy
Podstawy
Pamięć operacyjna lub główna (main memory) jest wielką tablicą
oznaczonych adresami słów lub bajtów.
Aby program mógł być wykonywany, musi zostać umieszczony w
procesie i wprowadzony do pamięci operacyjnej.
Zbiór procesów czekających na dysku na wprowadzenie do pamięci w
celu wykonania tworzy kolejkę wejściową (input queue).
Jeden z procesów zostaje wybrany i załadowany do pamięci; podczas
wykonywania pobiera rozkazy i dane z pamięci, a po zakończeniu
zwalnia zajmowaną pamięć.
Większość systemów pozwala procesowi użytkownika przebywać w
dowolnej części pamięci fizycznej  wpływa to na zakres adresów
dostępnych dla procesu.
Program użytkownika przechodzi kilka faz, zanim zostanie wykonany 
podczas tych faz reprezentacja adresów może ulegać zmianie.
W programie z
ródłowym adresy wyrażane są w sposób symboliczny
(np. licznik)  kompilator wiąże je z adresami względnymi, a
konsolidator wiąże dalej te adresy względne z adresami bezwzględnymi.
3
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Wiązanie adresów
Wiązanie adresów
Wiązanie rozkazów i danych z adresami pamięci może być
dokonane w dowolnym z trzech kroków:
1. Czas kompilacji: Jeżeli a priori znane jest miejsce, w
którym proces będzie przebywał w pamięci, to można
wygenerować kod bezwzględny (absolute code); zmiana
położenia kodu w pamięci wymaga jego rekompilacji.
2. Czas ładowania: Jeżeli przyszłe położenie procesu w
pamięci nie jest znane podczas kompilacji, to kompilator
musi generować kod przemieszczalny (relocatable code);
wiązanie adresów następuje w czasie ładowania kodu.
3. Czas wykonania: Jeżeli proces podczas wykonania
może być przemieszczany w pamięci, to wiązanie adresów
musi być opóz
nione do czasu wykonania  wymaga to
specjalnego sprzętu. (Stosowane w większości współczesnych
systemów)
4
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Schemat faz przetwarzania adresacji
Schemat faz przetwarzania adresacji
programu użytkowego
programu użytkowego
Faza
kompilacji
Program z
ródłowy Moduł wynikowy
KOMPILATOR
Inne moduły Moduł ładowalny
LINKER
wynikowe
Faza
ładowania
Biblioteka
LOADER
systemowa
Faza
Biblioteka ładowana
Program wynikowy
wykonania
dynamicznie
zakodowany
binarnie
5
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Logiczna i fizyczna przestrzeń adresowa
Logiczna i fizyczna przestrzeń adresowa
Adresy logiczne (wirtualne)  adresy generowane przez CPU.
Adresy fizyczne  adresy widziane przez jednostkę pamięci.
Adresy logiczne i fizyczne są:
takie same  w schematach wiązania adresów podczas kompilacji i
ładowania;
różne  w schematach wiązania adresów podczas wykonywania.
Zbiór wszystkich adresów logicznych generowanych przez program
nazywa się logiczną przestrzenią adresową, a zbiór
odpowiadających im adresów fizycznych  fizyczną przestrzenią
adresową.
Odwzorowywanie adresów logicznych na fizyczne jest dokonywane
przez jednostkę zarządzania pamięcią (memory management unit 
MMU)  jest to urządzenia sprzętowe.
Do każdego adresu generowanego przez proces użytkownika w chwili
odwołania się do pamięci jest dodawana wartość rejestru
przemieszczenia (relocation register).
Program użytkownika działa na adresach logicznych, nigdy nie ma do
czynienia z rzeczywistymi adresami fizycznymi.
6
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Przemieszczanie dynamiczne z użyciem
Przemieszczanie dynamiczne z użyciem
rejestru przemieszczenia
rejestru przemieszczenia
Rejestr
przemieszczenia
(bazowy)
12500
12869
Adres
369
Adres
Procesor
logiczny
fizyczny
Jednostka
Pamięć
zarządzania
operacyjna
pamięcią (MMU)
7
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
A
adowanie dynamiczne
A
adowanie dynamiczne
Przy ładowaniu dynamicznym (dynamic loading)
podprogram nie jest wprowadzany do pamięci dopóki nie
zostanie wywołany.
Gdy jakiś podprogram chce wywołać inny podprogram,
musi sprawdzić czy jest on w pamięci  jeżeli nie, to należy
wywołać program łączący i ładujący (reloctable linking
loader).
Wszystkie programy przechowywane są na dysku w
postaci kodów przemieszczalnych.
Lepsze wykorzystanie pamięci  nieużywany podprogram nie
zostanie nigdy załadowany.
Użyteczne, kiedy od czasu do czasu trzeba wykonać duże
fragmenty kodu, jak np. podprogramy obsługi błędów.
Nie wymaga specjalnego wsparcia ze strony systemu
operacyjnego  użytkownicy są odpowiedzialni za odpowiednie
projektowanie programów (system może dostarczać bibliotek do
ładowania dynamicznego).
8
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Konsolidacja dynamiczna
Konsolidacja dynamiczna
Konsolidacja statyczna  systemowe biblioteki języków
programowania są traktowane jak każdy inny moduł wynikowy i
dołączane przez program ładujący do binarnego obrazu programu.
Marnotrawstwo pamięci operacyjnej oraz przestrzeni dyskowej.
Konsolidacja dynamiczna (dynamic linking)  konsolidacja jest
opóz
niona do czasu wykonania programu.
W miejscu odwołania bibliotecznego w obrazie binarnym znajduje się
zakładka (stub) (namiastka procedury)  mały fragment kodu wskazujący,
jak odnalez
ć w pamięci lub załadować z dysku odpowiedni podprogram.
Zakładka wprowadza na swoje miejsce adres potrzebnego podprogramu i
powoduje jego wykonanie.
Wymaga wsparcia ze strony sytemu operacyjnego  sprawdzanie czy
podprogram biblioteczny jest w obszarach pamięci procesów oraz
zezwalanie by wiele procesów miało dostęp do tych samych adresów
pamięci.
Lepsze wykorzystanie pamięci operacyjnej oraz przestrzeni dyskowej.
Szczególnie użyteczna dla bibliotek, np. aktualizacja biblioteki nie
wymaga ponownej konsolidacji korzystających z niej programów
biblioteki dzielone (shared libraries).
9
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Nakładki (overlays)
Nakładki (overlays)
Przechowywanie w pamięci tylko tych rozkazów i danych,
które są stale potrzebne.
Inne rozkazy i dane są wprowadzane w miarę
zapotrzebowania  na miejsca zajmowane przez rozkazy
czy dane już zbyteczne.
Możliwość uruchamiania procesu większego od
przydzielonego mu obszaru pamięci.
Nie wymagają specjalnego wsparcia ze strony systemu
operacyjnego, mogą być w całości implementowane przez
użytkownika.
Projektowanie i programowanie nakładek jest
skomplikowane obecnie dość ograniczone w użyciu.
10
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Nakładki dwuprzebiegowego assemblera
Nakładki dwuprzebiegowego assemblera
Obszar pamięci: 150 KB
Tablica
Proces: 200 KB
symboli
20 KB
Wspólne
podprogramy
30 KB
Moduł obsługi
10 KB
nakładek
Przebieg 1 Przebieg 2
70 KB
90 KB
80 KB
11
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Wymiana (swapping)
Wymiana (swapping)
Proces może być tymczasowo odesłany z pamięci operacyjnej do
pamięci pomocniczej, a po jakimś czasie sprowadzony z powrotem w
celu kontynuacji wykonywania.
Do wymiany potrzebna jest pamięć pomocnicza (backing store)  jest
nią na ogół szybki dysk:
Musi być wystarczająco pojemny, aby pomieścić kopie obrazów pamięci
wszystkich użytkowników.
Musi umożliwiać bezpośredni dostęp do tych obrazów pamięci.
Wytaczanie i wtaczanie (roll-out, roll-in)  wariant wymiany używany
w algorytmach planowania priorytetowego, w którym proces o niższym
priorytecie jest odsyłany z pamięci po to by proces o wyższym
priorytecie mógł zostać załadowany i wykonany.
Główną częścią czasu wymiany jest czas przesyłania, który jest
proporcjonalny do ilości wymienianej pamięci.
Obecnie standardowa wymiana jest stosowana rzadko.
Zmodyfikowane wersje wymiany są stosowane w wielu
systemach, np. UNIX, Linux, MS Windows.
12
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Schematyczny obraz wymiany
Schematyczny obraz wymiany
System
Operacyjny
Przestrzeń
użytkownika
Proces P1
(1) Wysłanie
Proces P2
(2) Sprowadzenie
Pamięć pomocnicza
Pamięć operacyjna
13
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Przydział ciągły
Przydział ciągły
Pamięć operacyjna jest zwykle podzielona na dwie części:
dla rezydującego systemu operacyjnego  zwykle pamięć dolna;
dla procesów użytkownika  zwykle pamięć górna.
Przydział (alokacja) pojedynczego obszaru:
Do ochrony kodu i danych systemu operacyjnego ze strony procesów
użytkowników oraz tych procesów wzajemnie przed sobą używa się rejestru
przemieszczenia oraz rejestru granicznego.
Rejestr przemieszczenia zawiera wartość najmniejszego adresu fizycznego.
Rejestr graniczny zawiera górny zakres adresów logicznych.
Rejestr
Rejestr
przemieszczenia
graniczny
(bazowy)
Pamięć
operacyjna
Adres logiczny Adres fizyczny
Procesor
TAK
<
NIE
Pułapka: Błąd adresowania
14
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Przydział ciągły 2
Przydział ciągły 2
Przydział wielu obszarów:
Dziura (hole)  blok dostępnej pamięci; dziury różnych rozmiarów mogą
być rozproszone po całej pamięci.
Kiedy przybywa proces, poszukuje się dla niego odpowiednio obszernej
dziury  jeśli taka zostanie znaleziona, to z niej przydziela się mu pamięć.
Jeżeli nie znajdzie się wystarczająco duża dziura, to proces musi
poczekać.
System operacyjny przechowuje tablicę z informacjami o przydzielonych
oraz wolnych (dziury) obszarach pamięci.
SO SO SO SO
Proces 5 Proces 5 Proces 5 Proces 5
Proces 8 Proces 9 Proces 9
Proces 10
Dziura
Dziura
Dziura
Proces 2 Proces 2 Proces 2 Proces 2
15
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Dynamiczny przydział pamięci
Dynamiczny przydział pamięci
Jak na podstawie listy wolnych dziur spełnić zamówienie na obszar o
rozmiarze n?
Pierwsze dopasowanie (first-fit): Przydziela się pierwszą dziurę o
wystarczającej wielkości. Szuka się od początku wykazu dziur lub od
miejsca zakończenie ostatniego szukania.
Najlepsze dopasowanie (best-fit): Przydziela się najmniejszą z
dostatecznie dużych dziur. Zapewnia najmniejsze pozostałości, ale
wymaga przeszukiwania całej listy.
Najgorsze dopasowanie (worst-fit): Przydziela się największą dziurę.
Wymaga przeszukania całej listy, pozostawia po przydziale największą
dziurę (może być bardziej przydatna niż wiele małych).
Symulacje pokazują, że pierwsze dwie strategie są lepsze od
trzeciej pod względem zużycia czasu jak i pamięci (najszybsza jest
pierwsza)
16
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Fragmentacja pamięci
Fragmentacja pamięci
Fragmentacja zewnętrzna (external fragmentation): Suma wolnych
obszarów w pamięci wystarcza na spełnienie zamówienia, ale nie
tworzą one spójnego obszaru.
Reguła 50 procent  w strategii pierwszego dopasowania z powodu
fragmentacji straty wynoszą na ogół ok. 50% tego co zostało przydzielone.
Fragmentacja wewnętrzna (internal fragmentation): Przydzielona
pamięć może być nieco większa niż zamawiana (nie opłaca się
trzymać informacji o bardzo małych dziurach)  ten naddatek znajduje
się wewnątrz przydzielonego obszaru, ale jest niewykorzystywany.
Fragmentację zewnętrzną można redukować przez upakowanie:
Przetasowanie pamięci tak, aby cała wolna pamięć była w jednym bloku.
Upakowanie jest możliwe tylko przy dynamicznym wiązaniu adresów
wykonywanym podczas działania procesu.
Algorytm upakowania może być dość kosztowny.
Wybranie optymalnej strategii upakowywania jest dosyć trudne.
Dodatkowe trudności pojawiają się kiedy w systemie występuje
wymiana, np. problem przywrócenia procesu o statycznie ustalanych
adresach.
17
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Upakowanie pamięci
Upakowanie pamięci
System System System System
operacyjny operacyjny operacyjny operacyjny
P1 210K P1 210K P1 210K P1 210K
P2 200K P3 400K
400K
P3 400K
900K
P2 200K P2 200K
300K
P3 400K P3 400K
900K 900K
P2 200K
200K
Przemieszczono:
600 K 400 K 200 K
18
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Stronicowanie (paging)
Stronicowanie (paging)
Inne rozwiązanie problemu fragmentacji zewnętrznej  dopuszczenie
do nieciągłości logicznej przestrzeni adresowej, tzn. przydzielanie
procesowi dowolnych dostępnych miejsc pamięci fizycznej.
Podział pamięci fizycznej na bloki o stałej długości zwane ramkami
(frames); rozmiar zwykle jest potęgą 2, między 512 B a 16 MB.
Podział pamięci logicznej na bloki takiego samego rozmiaru zwane
stronami (pages).
System utrzymuje informację o wolnych i przydzielonych ramkach w tablicy
ramek (a także do jakiego procesu  lub procesów  ramka jest przydzielona).
Strony uruchamianego procesu przebywające w pamięci pomocniczej są
wprowadzane w wolne ramki pamięci operacyjnej (program rozmiaru n stron
potrzebuje n ramek  mogą być w dowolnym miejscu pamięci fizycznej).
Eliminuje się fragmentację zewnętrzną, ale pozostaje fragmentacja
wewnętrzna.
Adres generowany przez procesor składa się z dwóch części:
numer strony s (page number)  indeks w tablicy stron; tablica stron
zawiera adresy bazowe wszystkich stron w pamięci operacyjnej.
odległość na stronie o (page offset)  w połączeniu z adresem bazowym
daje adres fizyczny pamięci, który jest wysyłany do jednostki pamięci.
19
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Odwzorowanie adresów
Odwzorowanie adresów
segment
offset
SF
SL O SF O
Adres logiczny Adres fizyczny
Procesor
segment
PaO
SL
SL SF
Tablica stron
20
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Przykład stronicowania
Przykład stronicowania
Numer
ramki
0
1 Strona 0
Strona 1
0 1
2
Strona 2
1 4
3 Strona 2
Strona 3 2 3
3 6
Strona 4 4 Strona 1
Tablica
5
Pamięć logiczna translacji
stron
6 Strona 3
Pamięć fizyczna
21
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Implementacja tablicy stron
Implementacja tablicy stron
Tablica stron przechowywana jest w pamięci operacyjnej (jedynie
bardzo małe tablice można przechowywać w rejestrach).
Rejestr bazowy tablicy stron (page-table base register  PTBR)
służy do wskazywania położenia tablicy stron.
Rejestr długości tablicy stron (page-table length register  PTLR)
służy do podawania rozmiaru tablicy stron.
W takim schemacie każdy dostęp do danych/rozkazów wymaga
dwóch kontaktów z pamięcią  dwukrotne spowolnienie dostępu!
Standardowe rozwiązanie powyższego problemu  użycie szybkiej (ale
drogiej) pamięci podręcznej zwanej rejestrami asocjacyjnymi lub
buforami translacji adresów stron (translation look-aside buffers 
TLBs):
Każdy rejestr składa się z dwu części: klucza (znacznika) i wartości.
Porównywanie danego obiektu (numeru strony) z kluczami odbywa się
równocześnie dla wszystkich kluczy.
Jeżeli obiekt zostanie znaleziony, to wynikiem jest odpowiednia wartość -
numer ramki; jeżeli nie, to trzeba odwołać się do tablicy stron w pamięci.
22
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Stronicowanie z buforami TLB
Stronicowanie z buforami TLB
Pamięć
Procesor
fizyczna
S O
Numer Numer
Adres logiczny
strony ramki
Trafienie w
TLB
Bufory TLB
Adres fizyczny
R O
SR
Chybienie w
TLB
Tablica translacji
stron
23
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Czas dostępu i ochrona pamięci
Czas dostępu i ochrona pamięci
Efektywny czas dostępu do pamięci:
Czas dostępu do pamięci operacyjnej = �;
Współczynnik trafień (hit ratio) stron w rejestrach TLB = ą, (0 d"ąd" 1);
Czas przeglądania (lookup time) rejestrów TLB = � � �, (0 d"� d" 1);
Efektywny czas dostępu (effective access time  EAT):
EAT = ą (1 + �) � � + (1  ą) (2 + �) � �
EAT = (2 + �  ą) � ��! ą powinno być duże, a � małe!
Np. procesor Intel 80486: 32 rejestry TLB, ą = 0.98.
Ochrona pamięci:
Każdej ramce przypisuje się bit ochrony, który określa, czy strona jest
dostępna do czytania i pisania, czy tylko do czytania.
Dodatkowo do każdej pozycji w tablicy stron dołączany jest bit poprawności
(valid-invalid bit) mówiący, czy strona znajduje się w logicznej przestrzeni
adresowej procesu (a więc jest dozwolona), czy nie.
Niektóre systemy korzystają ze sprzętowego rejestru długości tablicy stron
(PTLR) wskazującego rozmiar tablicy stron  używa się go w celu
sprawdzenia, czy dany adres należy do przedziału dozwolonego dla
procesu.
24
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Stronicowanie wielopoziomowe
Stronicowanie wielopoziomowe
Współczesne systemy komputerowe umożliwiają stosowanie bardzo
dużych przestrzeni adresów logicznych:
Np. dla 32-bitowych adresów ponad milion stron o rozmiarze 4
KB; każda pozycja w tablicy stron ma 4 B, potrzeba więc 4 MB
fizycznej przestrzeni adresowej na samą tablicę stron dla każdego
procesu!
Jednym z możliwych rozwiązań jest schemat stronicowania
dwupoziomowego, w którym tablica stron jest podzielona na strony
(np. architektura komputera VAX, procesor Pentium II):
Na 32-bitowej maszynie o stronach rozmiaru 4 KB adres logiczny
na postać:
numer strony odległość na stronie
S1 S2 O
10 10 12
gdzie s1  indeks do zewnętrznej tablicy stron,
s2  przesunięcie na stronie tej zewnętrznej tablicy.
25
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Schemat dwupoziomowej tablicy stron
Schemat dwupoziomowej tablicy stron
0
1
2
1
14
15
30
16
15
2F
40
30
31
Zewnętrzna tablica Strona tablicy stron
stron S2
3F
S1
40
41
Pamięć
26
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Tłumaczenie adresu w schemacie
Tłumaczenie adresu w schemacie
stronicowania dwupoziomowego
stronicowania dwupoziomowego
27
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Stronicowanie trójpoziomowe
Stronicowanie trójpoziomowe
W architekturze 64-bitowej schemat stronicowania
dwupoziomowego nie wystarcza.
Można więc zastosować stronicowanie trójpoziomowe:
druga strona zewnętrzna strona zewnętrzna strona wewnętrzna offset
S1 S2 S3 O
32 10 10 12
Zewnętrzna tablica stron jest wciąż olbrzymia!
Można więc zastosować stronicowanie czteropoziomowe
& .
32-bitowy komputer SPARC obsługuje stronicowanie
trójpoziomowe, natomiast procesor Motorola 68030 
stronicowanie czteropoziomowe
28
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Haszowana tablica stron
Haszowana tablica stron
Do obsługi przestrzeni adresowych większych niż 32- bitowe często stosuje się
metodę haszowanej (mieszającej) tablicy stron (hash page table), gdzie
wartością haszowania jest numer strony wirtualnej.
Każdy wpis w takiej tablicy zawiera powiązaną listę elementów, które w wyniku
haszowania wyznaczają to samo miejsce (dają ten sam wynik).
Każdy element składa się z trzech pól:
a) numer strony wirtualnej,
b) wartość (numer) odwzorowanej ramki strony,
c) wskaz
nik do następnego elementu na liście powiązanej.
Algorytm odwzorowywania adresu:
1. Numer strony wirtualnej jest odwzorowywany przez funkcję haszującą
(mieszającą) na element tablicy z haszowaniem.
2. Argument funkcji haszującej jest porównywany z polem a) pierwszego
elementu na liście powiązanej.
3. W przypadku udanego dopasowania, numer odpowiedniej ramki strony
(pole b) elementu listy) jest używany do utworzenia adresu fizycznego.
4. W przeciwnym razie, próbę dopasowania wykonuje się dla następnego
elementu listy powiązanej itd.
Odmianą tego schematu są grupowane tablice stron (clustered page tables),
gdzie jeden wpis w tablicy odnosi się do kilkunastu stron (np. 16).
29
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Przykład haszowanej tablicy stron
Przykład haszowanej tablicy stron
30
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Odwrócona tablica stron
Odwrócona tablica stron
Wada zwykłych tablic stron: mogą zużywać wiele pamięci fizycznej  z
każdym procesem związana jest tablica stron.
Rozwiązaniem powyższego problemu może być odwrócona tablica
stron (inverted page table):
Posiada po jednej pozycji dla każdej ramki (rzeczywistej strony) pamięci
fizycznej (tablica jest indeksowana numerami ramek).
Każda pozycja zawiera adres wirtualny strony przechowywanej w ramce
oraz informacje o procesie, do którego ramka należy.
Jeżeli pojawia się odwołanie do pamięci, to następuje przeszukiwanie
odwróconej tablicy stron w celu dopasowania adresu wirtualnego.
Oszczędność pamięci: w systemie jest tylko jedna tablica stron!
Dłuższy czas potrzebny do przeszukania tablicy przy odwołaniu do
strony (ponieważ tablica ta jest uporządkowana wg. adresów
fizycznych, a przeglądanie dotyczy adresów wirtualnych).
Aby skrócić czas przeszukiwania używa się tablicy z haszowaniem
(hash table)  ograniczenia szukania do jednego lub co najwyżej kilku wpisów
w tablicy stron, ale wymaga dodatkowego sięgnięcia do pamięci.
31
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Architektura odwróconej tablicy stron
Architektura odwróconej tablicy stron
Pamięć
Adres logiczny
fizyczna
Procesor
PID S O R O
Adres fizyczny
R
Przeglądanie
PID S
Tablica stron
32
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Strony dzielone
Strony dzielone
Inną zaletą stronicowania jest możliwość dzielenia
wspólnego kodu (np. edytora) przez wiele procesów.
Kod dzielony:
Jedna kopia kodu wznawialnego (reentrant), tzn. takiego, który nie
modyfikuje sam siebie, może być współdzielona między wiele
procesów (np. edytory, kompilatory, systemy okien, baz danych).
Kod dzielony musi znajdować się w tej samej pozycji w fizycznej
przestrzeni adresowej wszystkich korzystających z niego procesów.
Trudne do implementacji dla odwróconej tablicy stron
Prywatny kod i dane:
Każdy proces posiada oddzielną kopię prywatnego kodu i danych.
Strony prywatnego kodu i danych mogą pojawiać się w dowolnym
miejscu w fizycznej przestrzeni adresowej.
33
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Segmentacja
Segmentacja
Segmentacja jest schematem zarządzania pamięcią urzeczywistniającym
sposób widzenia pamięci przez użytkownika.
Program jest zbiorem segmentów.
Segment to jednostka logiczna, taka jak: program główny, procedura,
funkcja, metoda, obiekt, stos, tablica symboli, tablice, zmienne lokalne i
globalne itd.
Dla ułatwienia implementacji segmenty są ponumerowane.
Adres logiczny:
Tablica segmentów: odwzorowuje dwuwymiarowe adresy logiczne w
jednowymiarowe adresy fizyczne. Każda pozycja składa się z dwóch części:
Baza segmentu  zawiera początkowy adres fizyczny segmentu w pamięci;
Granica segmentu  określa długość segmentu.
Implementacja tablicy segmentów:
Tablica segmentów na ogół przechowywana jest w pamięci.
Rejestr bazowy tablicy segmentów (segment-table base register  STBR)
wskazuje na tablicę segmentów w pamięci.
Rejestr długości tablicy segmentów (segment-table length register  STLR)
zawiera liczbę segmentów używanych przez program; numer segmentu s
jest dozwolony, jeżeli s < STLR.
34
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Sprzęt do segmentacji
Sprzęt do segmentacji
S
Pamięć
fizyczna
Granica Baza
Procesor
S O
Tablica segmentów
TAK
<
NIE
Pułapka: Błąd adresowania
35
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Przykład segmentacji
Przykład segmentacji
Granica Baza
1400
0 1000 1400 Segment 0
Program
1 400 3000
2 400 5200
2400
Segment 0
3
4 1000 3500
3000
5
Tablica symboli Segment 1
6
3400
Stos
Segment 1
3500
Segment 2 Tablica segmentów
Segment 4
4500
Podprogram
5200
Segment 4
5600
Segment 2
Logiczna przestrzeń adresowa
Pamięć fizyczna
36
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Ochrona i wspólne użytkowanie
Ochrona i wspólne użytkowanie
Zaletą segmentacji jest powiązanie ochrony pamięci z segmentami
(segmenty są określonymi semantycznie porcjami programu, które na
ogół powinny być używane w ten sam sposób).
Z każdą pozycją w tablicy segmentów związane są:
Bit poprawności  zero oznacza, ze użycie segmentu jest niedozwolone.
Prawa czytania/pisania/wykonywania dla danego segmentu.
Inną zaletą segmentacji jest dzielenie kodu lub danych:
Dzielenie występuje na poziomie całych segmentów, np. kilka procesów
może dzielić segmenty zawierające edytor, funkcje biblioteczne itd.
Dzielenie segmentów występuje wtedy, gdy wpisy w tablicach różnych
procesów wskazują na to samo miejsce w pamięci fizycznej.
Dowolna informacja może być dzielona, jeśli została zdefiniowana jako
segment.
Fragmentacja:
Segmenty mają różne długości, zatem przydział pamięci jest zagadnieniem
przydziału dynamicznego  na ogół rozwiązywane za pomocą algorytmu
pierwszego lub najlepszego dopasowania.
Występuje zewnętrzna fragmentacja  zależna od rozmiaru segmentów.
37
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Segmentacja ze stronicowaniem
Segmentacja ze stronicowaniem
Możliwe jest połączenie schematów stronicowania i segmentacji.
Procesor Intel 80386 (i póz
niejsze):
Maksymalna liczba segmentów w jednym procesie: 16 K, maksymalny
rozmiar segmentu: 4 GB, rozmiar strony: 4 KB.
Przestrzeń adresów logicznych podzielona na dwie strefy:
1. Strefa prywatnych segmentów procesu: 8 K segmentów  informacje o
niej znajdują się w tablicy lokalnych deskryptorów (local description table -
LDT).
2. Strefa segmentów wspólnych dla wszystkich procesów: 8 K segmentów
 informacje o niej znajdują się w tablicy globalnych deskryptorów (GDT).
Każdy segment jest stronicowany w schemacie stronicowania
dwupoziomowego (s1 = 10 b, s2 = 10 b, o = 12 b).
System MULTICS:
Rozwiązanie problemu fragmentacji zewnętrznej przez stronicowanie
segmentów (strona składa się z 1 K słów).
Wpis w tablicy segmentów zawiera nie adres segmentu, lecz adres bazowy
tablicy stron tego segmentu.
Ponieważ maksymalna liczba segmentów jest spora (262 144), co
wymagałoby dużej tablicy segmentów, więc stronicuje się tablicę
segmentów.
38
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna
Translacja adresu dla procesora Intel 80386
Translacja adresu dla procesora Intel 80386
Selektor Offset
Adres logiczny
Deskryptor segmentu
Tablica
deskryptorów
Katalog Strona Offset
Adres liniowy
Adres fizyczny
Ramka strony
Wpis katalogowy Pozycja tablicy stron
Katalog stron Tablica stron
Rejestr bazowy
katalogu stron
39
Maciej J. Bargielski � 2009: Systemy operacyjne. Pamięć operacyjna