SOP - Zarządzanie pamięcią.

Zarządzanie pamięcią



Streszczenie
W niniejszym wykładzie przedstawiamy różne sposoby zarządzania
pamięcią operacyjną w systemie.
Zaczynamy od najprostszego modelu, w którym proces otrzymuje jeden
spójny obszar pamięci, poprzez segmentację, stronicowanie, a
kończąc na segmentacji ze stronicowaniem.
Dla poszczególnych rozwiązań przedstawione są niezbędne
sprzętowe mechanizmy adresowania pamięci oraz sposoby
zarządzania nią.



Wprowadzenie
Jednym z zadań systemu operacyjnego jest zarządzanie zasobami systemowymi.
Jednym z podstawowych zasobów systemowych niezbędnych do działania procesów jest pamięć operacyjna.
Tak więc przydzielanie procesom pamięci operacyjnej jest jednym z podstawowych zadań systemu operacyjnego.
Dalej w tym wykładzie, przez "pamięć" będziemy zawsze rozumieć "pamięć operacyjną"

Pamięć możemy traktować jak dużą tablicę słów (maszynowych). W
zależności od architektury, słowo maszynowe składa się z określonej
liczby (będącej potęgą 2-ki) bitów, np. 32, 64 czy 128. Pozycję słowa w
tablicy, jaką jest pamięć, nazywamy adresem.
Adres jest liczbą binarną złożoną z określonej liczby bitów.
Zwykle liczba tych bitów jest również potęgą 2-ki, często taką samą jak w słowie maszynowym, choć nie zawsze.

W systemie operacyjnym działa zwykle równocześnie wiele procesów. Każdy
z nich, aby móc działać, musi być umieszczony w pamięci. Napotykamy tu
dwa problemy związane z pamięcią: Po pierwsze, każdy proces powinien
mieć dostęp do swojej pamięci, ale nie powinien mieć dostępu do pamięci
innych procesów. Należy więc zapewnić mechanizm ochrony pamięci.
Po drugie, kompilując program, trudno przewidzieć, w którym miejscu w pamięci będzie on umieszczony.
Jednym z rozwiązań tego problemu jest generowanie w trakcie kompilacji kodu przemieszczalnego.
W trakcie ładowania programu do pamięci, wszelkie adresy zawarte w takim kodzie mogą być odpowiednio przesuwane.

Czasami, gdy nie można zaspokoić zapotrzebowania na pamięć wszystkich procesów
(lub gdy mamy do czynienia ze zjawiskiem szamotania, o czym będzie mowa w następnym wykładzie)
system operacyjny musi wstrzymać wykonywanie niektórych procesów, zapisać je w pamięci masowej (na dysku),
a przydzieloną im pamięć operacyjną rozdzielić pomiędzy pozostałe procesy.
Po pewnym czasie, gdy dostępna jest odpowiednia ilość pamięci operacyjnej, procesy te można wznowić, ładując je z dysku.
Mechanizm taki nazywamy wymianą procesów.
Gdy mamy do czynienia z wymianą, proces może zostać załadowany w inne
miejsce w pamięci, niż to, w którym był poprzednio. Nie wystarczy
wówczas, aby kod programu stanowiącego proces był przemieszczalny. Cała
zawartość pamięci przydzielonej procesowi musi być przemieszczalna i to
w każdej chwili. Podobna konieczność przemieszczania występuje również
w przypadku pamięci wirtualnej, o czym będzie mowa w kolejnym
wykładzie. Problem przemieszczania zawartości pamięci
przydzielonej procesom rozwiązuje się tworząc na potrzeby procesu
odrębny obraz pamięci. Całą pamięć operacyjną dostępną w komputerze,
tak jak ją widzi system operacyjny, nazywamy pamięcią fizyczną.
Adresy pamięci fizycznej nazywamy adresami fizycznymi.
Posługując się adresami fizycznymi mamy dostęp do całej pamięci fizycznej.

Proces, w odróżnieniu od systemu operacyjnego, nie powinien mieć dostępu do całej pamięci,
ale tylko do pamięci przydzielonej mu przez system operacyjny.
System operacyjny tworzy na potrzeby procesu obraz przydzielonej mu pamięci,
który nie zmienia się gdy zawartość pamięci przydzielonej procesowi jest przemieszczana w pamięci fizycznej.
Jest to pewnego rodzaju iluzja.
Pamięć, taką jak ją widzi dany proces, nazywamy pamięcią logiczną.
Adresy, którymi posługują się procesy, a które odnoszą się do ich pamięci logicznych, nazywamy
adresami logicznymi.
Pamięć logiczna jest realizowana przez mechanizm, który jest również odpowiedzialny za ochronę pamięci.
Mechanizm ten jest realizowany sprzętowo przez jednostkę zarządzania pamięcią
(ang. memory management unit, w skrócie MMU), która:

sprawdza, czy używane przez proces adresy logiczne są poprawnymi adresami,
tzn. czy odnoszą się do przydzielonej procesowi pamięci;
w przypadku, gdy adres logiczny jest niepoprawny, zgłaszany jest błąd,
tłumaczy adresy logiczne, na odpowiadające im adresy fizyczne.


Zwróćmy uwagę, że każdy proces ma własną pamięć logiczną.
Przełączanie kontekstu między procesami wymaga przeprogramowania MMU.
Tak więc konstrukcja MMU ma nie tylko wpływ na efektywność dostępu do pamięci,
ale również na czas przełączania kontekstu między procesami.

W dalszej części tego wykładu przedstawimy kilka modeli zarządzania pamięcią,
wraz ze strategiami przydzielania pamięci oraz odpowiadającymi im MMU.



Przydział ciągły
Przydział ciągły jest najprostszym z modeli zarządzania pamięcią.
W modelu tym każdemu procesowi przydziela się jeden spójny fragment pamięci fizycznej.
W systemie zwykle działa współbieżnie wiele procesów.
Pamięć fizyczna jest więc podzielona na zajęte i wolne fragmenty, co przedstawiono na poniższym rysunku.






Każdy proces widzi spójny obszar pamięci określonej wielkości.
Adresy logiczne mają zakres od 0 do wielkości przydzielonego obszaru minus jeden.
Poniższy rysunek przedstawia schemat budowy MMU.
MMU zawiera dwa programowalne rejestry.
Rejestr przemieszczenia zawiera początkowy adres fizyczny przydzielonego obszaru.
Rejestr graniczny zawiera wielkość przydzielonego obszaru.






Jeżeli adres logiczny jest większy od wielkości przydzielonego obszaru pamięci, to jest zgłaszany błąd.
W przeciwnym przypadku, adres fizyczny jest sumą adresu logicznego i adresu fizycznego początku przydzielonego obszaru.

Fragmentacja zewnętrzna i defragmentacja
W momencie uruchomienia procesu, system operacyjny musi przydzielić procesowi pamięć.
Wolna pamięć fizyczna może być poszatkowana przydzielonymi już obszarami na wiele fragmentów.
Może się więc tak zdarzyć, że łączna ilość wolnej pamięci będzie wystarczająca,
ale nie będzie jednego spójnego obszaru, wystarczająco dużego, żeby przydzielić z niego pamięć dla procesu.
Zjawisko takie nazywamy fragmentacją zewnętrzną.

Jeżeli mamy do czynienia z fragmentacją zewnętrzną, to konieczne staje się scalenie wolnych obszarów.
Scalanie takie nazywamy defragmentacją lub upakowaniem.
Defragmentacja jest kosztowna, ze względu na konieczność kopiowania dużych obszarów pamięci fizycznej.
Dlatego też należy starać się unikać fragmentacji zewnętrznej.
Poniższy rysunek przedstawia przykładową defragmentację.
Zwróćmy uwagę na to, że zajęte obszary nie muszą być upakowane razem, scalamy obszary wolne.






Zjawisko fragmentacji zewnętrznej występuje nie tylko przy
przydzielaniu pamięci procesom.
Występuje wszędzie tam, gdzie zarządzamy pamięcią na podobnych
zasadach, np. przy zarządzaniu stertą (ang. heap).
W tym przypadku nie zawsze defragmentacja jest możliwa --
zależy to od realizacji wskaźników w języku programowania.
Jeśli jest możliwa, to zwykle jest połączona z usuwaniem
niedostępnych obszarów pamięci, czyli
odśmiecaniem.

Strategie przydziału pamięci
Gdy system operacyjny przydziela procesowi obszar pamięci, to zwykle może go przydzielić z
jednego z wielu obszarów wolnej pamięci.
Oczywiście obszar wolnej pamięci, z którego przydzielamy pamięć musi być wystarczająco duży.
Istnieje kilka strategii wybierania, z którego obszaru przydzielić pamięć.

First-Fit
Jest to najprostsza możliwa strategia.
Wybierany jest pierwszy (pod względem adresów) wolny obszar, który jest wystarczająco duży.

Best-Fit
Wybieramy najmniejszy wolny obszar, który jest wystarczająco duży.
Pomysł, który się kryje za tą strategią jest następujący:
Wolny obszar jest zwykle większy niż przydzielany obszar, więc po przydzieleniu część wolnego obszaru pozostaje wolna.
W przypadku strategii best-fit, taka "końcówka" jest możliwie najmniejsza.
Jeśli w przyszłości nie wykorzystamy jej, to straty z powodu fragmentacji zewnętrznej będą możliwie małe.

Worst-fit
Przydzielamy pamięć zawsze z największego wolnego obszaru (oczywiście, o ile jest on wystarczająco duży).
W przypadku tej strategii, część obszaru, która pozostaje wolna jest możliwie jak największa.
Jest więc szansa, że będzie można ją jeszcze wykorzystać bez konieczności defragmentacji.


Wszystkie te strategie to tylko heurystyki.
Żadna z nich nie gwarantuje optymalnego rozmieszczenia przydzielanych obszarów.
Jest to niemożliwe, bo nie można przewidzieć jakie będą zapotrzebowania procesów, które dopiero się pojawią.
W praktyce, najlepiej spisują się strategie Best-Fit i First-Fit.

Poniższy rysunek przedstawia przykład działanie tych strategii.






Wszystkie te strategie mają zastosowanie nie tylko w budowie systemów operacyjnych, ale
wszędzie tam, gdzie przydzielamy pamięć w formie spójnych obszarów różnej wielkości,
np. w zarządzaniu stertą (o czym czytelnik dowie się w przyszłości, poznając budowę kompilatorów).



Segmentacja
Pamięć wykorzystywana przez proces, z logicznego punktu widzenia, nie stanowi jednego spójnego obszaru.
Zwykle składa się z kilku segmentów.
Typowe segmenty to: kod programu, zmienne globalne, stos i sterta.
System operacyjny może więc przydzielać procesom pamięć nie w postaci jednego spójnego bloku,
ale kilku takich bloków, segmentów.
Co więcej, proces może w trakcie działania prosić o przydzielenie lub zwolnienie segmentów.

Nadal mamy do czynienia z fragmentacją zewnętrzną i nadal możemy stosować
defragmentację.
Stosujemy również te same strategie przydzielania pamięci, co w przypadku przydziału ciągłego.
Jedyna różnica między segmentacją, a przydziałem ciągłym polega na tym, że proces ma dostęp
do kilku segmentów, a nie tylko do jednego.

Adres logiczny składa się z dwóch części: numeru segmentu i adresu w obrębie segmentu.
Budowa MMU przypomina tę dla przydziału ciągłego, z tym, że zamiast jednego rejestru początkowego i przemieszczenia mamy
dwie tablice, zawierające po jednej komórce dla każdego segmentu.






Taki schemat działania MMU sugeruje, że czas dostępu do pamięci logicznej jest dwukrotnie dłuższy
od czasu dostępu do pamięci fizycznej -- musimy najpierw odwołać się do tablic segmentów, a dopiero potem do
szukanego słowa w pamięci fizycznej.
W praktyce stosuje się dwa ulepszenia:

Lista segmentów jest ograniczona do kilku.
Wówczas dane na temat położenia segmentów mogą być przechowywane w wyspecjalizowanych rejestrach procesora.
Oprócz tablic segmentów mamy też mniejszą, podręczną tablicę segmentów przechowującą informacje o
ostatnio używanych segmentach.
(Rozwiązanie to jest analogiczne do opisanego niżej przy okazji stronicowania.)
Dostęp do podręcznej tablicy segmentów jest znacznie szybszy, gdyż nie znajduje się ona w pamięci operacyjnej,
ale w niedużej szybkiej pamięci stanowiącej część MMU.
W znakomitej większości przypadków dostęp do tablicy podręcznej wystarcza, a tylko w nielicznych przypadkach
nie ma w niej danych o szukanych segmentach i konieczne jest sięgnięcie do tablicy segmentów znajdującej się
w pamięci operacyjnej.
W rezultacie, oczekiwany czas dostępu do pamięci logicznej jest tylko nieznacznie dłuższy od
czasu dostępu do pamięci fizycznej.


Przełączając kontekst między procesami musimy zmienić zawartość tablic początków i rozmiarów segmentów.
Jest to stosunkowo czasochłonne.
Dlatego też czasami w specjalnych rejestrach pamięta się wskaźniki do tych tablic.
Wówczas przy przełączeniu kontekstu wystarczy zmienić tylko te wskaźniki.

Przy segmentacji procesy mogą współdzielić segmenty -- ten sam segment może się pojawiać w tablicach kilku procesów.
Ma to praktyczne zastosowanie, jeśli ten sam program uruchomimy kilka razy, to wszystkie tak powstałe procesy
mogą mieć ten sam segment kodu.
Wówczas stosuje się zwykle dodatkową ochronę segmentów --
procesy współdzielące ten sam segment kodu nie mogą go modyfikować.
Można też utworzyć segment współdzielony przez procesy, który może być modyfikowany.
Jest to przydatne wówczas, gdy mamy do czynienia ze współpracującymi procesami współbieżnymi,
a segment taki zawiera współdzielone dane.



Stronicowanie
Stronicowanie to rozwiązanie, w którym proces widzi spójny obszar pamięci logicznej,
ale nie tworzy ona spójnego obszaru w pamięci fizycznej.
Zarówno pamięć logiczna, jak i pamięć fizyczna jest podzielona na kawałki równej wielkości.
W odniesieniu do pamięci logicznej mówimy o stronach,
a w odniesieniu do pamięci fizycznej mówimy o ramkach.
Wielkość stron i ramek jest potęgą dwójki z przedziału od 512B
(bajtów) do 16MB.
Typowa wielkość to 4kB.
Strony i ramki są podstawowymi jednostkami przydziału pamięci.
W rezultacie, wielkość przydzielonego procesowi obszaru jest wielokrotnością wielkości ramek i stron.
Strony pamięci logicznej mogą być umieszczone w dowolnych ramkach pamięci fizycznej.
Nie muszą tworzyć spójnego obszaru w pamięci fizycznej, ani nie muszą występować w określonej kolejności.

Podział pamięci logicznej na strony nie jest widoczny dla procesu.
Z punktu widzenia procesu, pamięć logiczna ma spójny przedział adresów.
W momencie, gdy podzielimy pamięć logiczną na strony, to odpowiednia liczba bardziej znaczących bitów
w adresie określa stronę, a pozostałe mniej znaczące bity określają pozycję w obrębie strony.
MMU (w procesorze) musi sprawdzić, czy numer strony jest poprawny
i która ramka zawiera daną stronę.
Służy do tego tzw. tablica stron.
Tablica ta jest indeksowana numerami stron.
Dla danej strony zawiera ona numer ramki, w której znajduje się dana strona.

Taki schemat działania MMU sugeruje, że każde odwołanie do pamięci logicznej wymaga dwóch odwołań do pamięci fizycznej:
jednego do tablicy stron i jednego do danego słowa w pamięci fizycznej.
Byłby to zbyt duży narzut na czas dostępu do pamięci.
Dlatego też stosuje się dodatkowo podręczną tablicę stron.
Jest to szybka pamięć asocjacyjna, w której przechowuje się numery ramek dla pewnej liczby ostatnio używanych stron.
Odszukanie numeru strony w takiej tablicy jest dużo szybsze niż odwołanie do pełnej tablicy stron.
Programy charakteryzują się tzw. lokalnością, tzn. że kolejne odwołanie do pamięci z dużym prawdopodobieństwem
będzie w tej samej stronie, co jedna z ostatnio używanych stron.
Tak więc z prawdopodobieństwem bliskim 1 numer szukanej ramki znajdziemy w podręcznej tablicy stron.
Żeby zilustrować, jaki ma to wpływ na czas dostępu do pamięci logicznej rozważmy następujący przykład.
Załóżmy, że czas dostępu do pamięci fizycznej wynosi 2.5ns, a czas dostępu do pamięci asocjacyjnej wynosi 0.5ns,
oraz że numer ramki znajdujemy w tablicy asocjacyjnej z prawdopodobieństwem 0.98.
Tak więc oczekiwany czas dostępu do pamięci logicznej to:
0.98 * 0.5ns + 0.02 * (0.5ns + 2.5ns) + 2.5 ns = 3.05ns.

Poniższy rysunek przedstawia schemat działania MMU dla stronicowania.






Podobnie jak w przypadku segmentacji, jeżeli tablica stron znajduje się w ustalonym miejscu w pamięci,
to przełączając kontekst należy zmienić odpowiednio jej zawartość.
Czasami tablica stron nie ma ustalonego miejsca, lecz jest wskazywana przez wyspecjalizowany rejestr.
Wówczas wystarczy zmienić zawartość tego rejestru.


Fragmentacja wewnętrzna
Stosując stronicowanie unikamy fragmentacji zewnętrznej.
Bez względu na to jak są rozsiane po pamięci fizycznej wolne ramki, możemy z nich utworzyć spójny obszar pamięci logicznej.
Nadal nie jesteśmy jednak w stanie wykorzystać całej pamięci.
Jednostką przydziału pamięci jest strona/ramka.
Zwykle więc część ostatniej strony pozostanie niewykorzystana.
Z pewnym uproszczeniem, możemy przyjąć, że średnio połowa ostatniej strony w przydzielanym obszarze jest niewykorzystana.
Zjawisko to nazywamy fragmentacją wewnętrzną.
Fragmentacja wewnętrzna występuje wszędzie tam, gdzie wielkość przydzielanej pamięci musi być
wielokrotnością pewnej większej jednostki, np. strony.
Fragmentację wewnętrzną można zmniejszyć zmniejszając wielkość strony.
To jednak oznacza zwiększenie rozmiaru tablicy stron.
Wybierając wielkość stron należy wziąć pod uwagę zarówno straty związane z fragmentacją wewnętrzną,
jak i straty związane z przechowywaniem tablicy stron.


Stronicowanie wielopoziomowe
Współcześnie spotykamy się najczęściej z architekturami, w których adresy logiczne mają 32 bądź 64 bity,
a typowy rozmiar strony to 4kB.
W przypadku adresów 32-bitowych i stron wielkości 4kB, sama tablica stron może mieć rozmiar 4MB.
Pamiętajmy, że dla każdego procesu musimy mieć inną tablicę stron i przełączać się między nimi
przy przełączaniu kontekstu.
Trudno wymagać, aby tablice stron zajmowały ona spójny obszar pamięci fizycznej.

Byłoby wygodnie, gdyby ten sam mechanizm zarządzania pamięcią można było zastosować do przydzielania
pamięci logicznej dla procesów oraz do przydzielania pamięci na ich tablice stron.
Zastanówmy się, jaka powinna być wielkość stron (w architekturze 32-bitowej), żeby tablica
stron sama akurat zajmowała jedną ramkę?
Jedna pozycja w tablicy stron zajmuje 4B.
Tak więc młodsze bity adresu, stanowiące adres w obrębie strony, powinny zajmować o 2 bity więcej
niż numer strony.
Czyli, starszych 15 bitów powinno stanowić numer strony, a młodszych 17 bitów powinno stanowić
adres w obrębie strony.
Daje to strony wielkości 128KB.

To stosunkowo dużo.
W rezultacie, straty na fragmentację wewnętrzną są dosyć duże.
Dlatego też stosuje się stronicowanie wielopoziomowe:
chcąc sięgnąć do określonego słowa pamięci logicznej musimy zajrzeć kolejno do kilku mniejszych tablic stron.
W przypadku architektury 32-bitowej są to dwa poziomy tablic stron.
Załóżmy, że 32-bitowy adres logiczny jest podzielony na trzy części.
Najstarsze bity określają pozycję w głównej tablicy stron (pierwszego rzędu).
W tej tablicy znajduje się wskaźnik do tablicy stron drugiego rzędu.
Środkowe bity adresu określają pozycję w tablicy stron drugiego rzędu, w której znajduje się już adres ramki.
Najmłodsze bity określają adres w obrębie strony/ramki.

Po ile bitów powinno być w tych trzech grupach?
Znowu chcielibyśmy, tablice stron, zarówno pierwszego jak i drugiego rzędu, akurat mieściły się w
pojedynczych ramkach.
Pojedyncza pozycja w tablicy stron zajmuje 4B.
Tak więc grupa najmłodszych bitów powinna zawierać o 2 bity więcej niż najstarsze i środkowe.
Stąd 32 bity adresu są podzielone tak:
najstarsze 10 bitów określa pozycję w tablicy stron pierwszego rzędu,
środkowe 10 bitów w określa pozycję w tablicy stron drugiego rzędu,
a najmłodsze 12 bitów to adres w obrębie strony.
Daje to strony i ramki wielkości 4KB, co utrzymuje fragmentację wewnętrzną na odpowiednim poziomie.
Teraz jest jasne, dlaczego taka właśnie taka jest zwykle wielkość stron.

Oczywiście możliwe jest stronicowanie o większej liczbie poziomów.
(Bez względu na liczbę poziomów stronicowania, dla poprawienia czasu dostępu do pamięci stosowane są
podręczne tablice stron).
Jest to przydatne w przypadku adresów logicznych dłuższych niż 32 bity.
Na przykład, w procesorach typu x86-64 stosuje się czterostopniowe stronicowanie
(przy stronach wielkości 4kB i 512 pozycjach w każdej tablicy stron).
Jak łatwo policzyć, pozwala to zaadresować 256TB, a więc tylko 48 z 64 bitów adresu jest wykorzystanych.
W chwili obecnej, w zupełności to wystarcza, a znacznie upraszcza to konstrukcję tablicy stron.







Odwrotna tablica stron
Jak jednak wygląda tablica stron w systemach w pełni 64-bitowych?
64 bity pozwalają zaadresować 16EB eksabajtów (czyli 17 179 869 184 GB)!
Bez względu na to, ile byśmy nie mieli poziomów stronicowania, tablica stron dla takiej przestrzeni adresowej
(przyjmując wielkość strony 4kB) zajmowałaby ok. 32PB!
Dlatego też, w systemach w pełni 64-bitowych stosuje się tzw. odwrotną tablicę stron.
Odwrotna tablica stron zawiera tyle pozycji, ile ramek pamięci fizycznej jest faktycznie
zainstalowanych w komputerze (lub wielokrotność tej liczby, np. czterokrotność).
W każdej pozycji tablicy pamiętana jest para: numer strony i numer ramki, w której ona się znajduje.
Dzięki temu, wielkość odwrotnej tablicy stron jest proporcjonalna do wielkości pamięci fizycznej faktycznie
zainstalowanej w komputerze i stanowi jej niewielki ułamek.
Jak jednak przetłumaczyć numer strony na numer ramki, nie przeglądając całej tablicy?
Otóż odwrotna tablica stron jest tablicą mieszającą (ang. hash-table) -- strukturą
słownikową o stałym oczekiwanym czasie dostępu.
Dodatkowo, zwykle obliczanie funkcji mieszającej jest zaimplementowane sprzętowo w MMU,
a odwrotnej tablicy stron towarzyszy szybka podręczna tablica stron.



Segmentacja ze stronicowaniem
Segmentacja ze stronicowaniem stanowi połączenie technik segmentacji i stronicowania.
Z punktu widzenia procesu, pamięć logiczna składa się z szeregu segmentów.
Jednak poszczególne segmenty nie są rozmieszczone w pamięci fizycznej w spójny sposób.
Są one dzielone na strony i każda strona może być pamiętana w dowolnej ramce.
Tak więc adres logiczny składa się z numeru segmentu i adresu w obrębie segmentu.
Na podstawie numeru segmentu można wyznaczyć tablicę stron określającą rozmieszczenie stron tworzących segment.

Podobnie jak w przypadku stronicowania, możemy mieć do czynienia ze stronicowaniem wielopoziomowym,
jak również z podręczną tablicą stron.

Dzięki połączeniu technik segmentacji i stronicowania, możemy z jednej strony przydzielać procesom wiele segmentów,
czy współdzielić segmenty, a z drugiej strony unikamy fragmentacji zewnętrznej.

Możliwych jest wiele sposobów konstrukcji MMU.
Poniżej przedstawiamy schemat tłumaczenia adresu logicznego na fizyczny w procesorze Intel 80386.
W przypadku tego procesora, segment jest identyfikowany przez tzw. selektor.
Selektor jest tłumaczony na tzw. deskryptor, który po dodaniu do adresu w obrębie segmentu tworzy logiczny adres liniowy.
Adres ten jest następnie tłumaczony na adres fizyczny poprzez dwustopniową tablicę stron.
Adres tablicy stron pierwszego rzędu jest przechowywany w specjalnym rejestrze procesora,
tzw. rejestrze bazowym tablicy stron.









Podsumowanie
Przedstawiliśmy podstawowe modele zarządzania pamięcią operacyjną:
przydział ciągły, segmentację, stronicowanie i segmentację ze
stronicowaniem. Na ich przykładzie możemy prześledzić wzajemne
sprzężenie technologii stosowanych w systemach operacyjnych i przez
producentów sprzętu. Inne są potrzeby prostego systemu, jakim jest np.
DOS, a inne zaawansowanych systemów operacyjnych, takich jak Unix (czy
Linux). Powstawanie zaawansowanych technik, takich jak np. segmentacja
ze stronicowaniem pośrednim, skłoniło producentów mikroprocesorów, do
wyposażenia ich produktów w odpowiednio zaawansowane MMU. To z kolei
umożliwiło wdrożenie tych zaawansowanych technik w systemach
operacyjnych na mikrokomputery.
W przypadku komputerów typu PC i zarządzania pamięcią, kluczowe było opracowanie procesora Intel 80386,
umożliwiającego segmentację ze stronicowaniem i ochronę pamięci.
To z kolei umożliwiło np. stworzenie systemu Linux.


Słownik

adres
liczba określająca pozycję słowa maszynowego w pamięci;
w zależności od architektury, jest to liczba binarna
złożona z określonej liczby bitów.

adres fizyczny
adres w pamięci fizycznej.

adres logiczny
adres w pamięci logicznej.

fragmentacja wewnętrzna
zjawisko występujące przy stronicowaniu i segmentacji ze
stronicowaniem;
jeżeli pamięć jest przydzielana większymi jednostkami
(strony/ramki),
to część ostatniej strony w przydzielanym obszarze jest
niewykorzystana.

fragmentacja zewnętrzna
zjawisko polegające na tym, że łączna ilość wolnej pamięci jest
wystarczająca do spełnienia zapotrzebowania, jednak pamięć ta
jest podzielona, co uniemożliwia spełnienie zapotrzebowania.

jednostka zarządzania pamięcią
(ang. memory management unit, w skrócie MMU)
sprzętowy mechanizm sprawdzający poprawność adresów
logicznych i tłumaczący adresy logiczne na adresy fizyczne.

kod przemieszczalny
kod wykonywalny programu, który może być umieszczony w dowolnym
miejscu pamięci;
wszelkie adresy zawarte w kodzie są odpowiednio przesuwane w
trakcie ładowania.

ochrona pamięci
Mechanizm zapewniający, że każdy z procesów obecnych w systemie ma dostęp do swojej pamięci,
ale nie do pamięci innych procesów, czy systemu operacyjnego.

odśmiecanie
usuwanie ze sterty (ang. heap) niedostępnych obszarów
pamięci, zwykle połączone ze scalaniem obszarów wolnych.

odwrotna tablica stron
tablica mieszająca kojarząca numery stron z odpowiadającymi im numerami ramek.

pamięć fizyczna
całość pamięci operacyjnej dostępnej w komputerze, tak jak
ją widzi system operacyjny.

pamięć logiczna
pamięć przydzielona procesowi, tak jak ją widzi dany proces.

ramka
jednostka przydziału pamięci fizycznej w stronicowaniu.

segment
spójny obszar pamięci będący jednostką przydziału pamięci procesom.

segmentacja
technika zarządzania pamięcią, polegająca na przydzielaniu procesom
wielu spójnych obszarów pamięci różnej wielkości, zwanych
segmentami.

strona
jednostka przydziału pamięci logicznej w stronicowaniu.

stronicowanie
technika zarządzania pamięcią, polegająca na podzieleniu na
kawałki równej wielkości pamięci logicznej procesów (strony) i
pamięci fizycznej (ramki);
strony pamięci logicznej mogą być w dowolny sposób rozmieszczone
w ramkach pamięci fizycznej.

tablica stron
w stronicowaniu, tablica przyporządkowująca numerom
stron numery zawierających je ramek.

wymiana procesów
mechanizm polegający na czasowym wstrzymaniu wykonywanego procesu
i odesłaniu go z pamięci operacyjnej do pamięci masowej (dysku).



Zadania

(6p.) Dana jest pamięć fizyczna wielkości 10MB.
Zasymuluj ciągły przydział pamięci dla strategii:
first-fit, best-fit i worst-fit, dla następującego
ciągu zdarzeń:

P1: przydziel 6MB,
P2: przydziel 3MB,
P3: przydziel 1MB,
P2: zwolnij,
P4: przydziel 2MB,
P1: zwolnij,
P5: przydziel 3MB,
P3: zwolnij,
P6: przydziel 2MB,
P7: przydziel 1MB.


(2p.) Czym różnią się adresy logiczne od fizycznych?
(2p.) Czym różni się fragmentacja zewnętrzna od wewnętrznej?



Strona przygotowana przez Marcina Kubicę i
Krzysztofa Stencla.