Do strony głównej

4.9 Stronicowanie





Wstęp

Tablice stron

Adresowanie

Zalety stronicowania

Wady stronicowania

Bibliografia






Wstęp


Stronicowanie polega na podziale pamięci na spójne
bloki ustalonej wielkości. Powoduje to znaczne ułatwienia przy obsłudze
pamięci, a także brak fragmentacji zewnętrznej ,
chociaż występuje fragmentacja wewnętrzna. Taki pojedyńczy
blok, na które jest podzielona pamięć nazywa się stroną, a jego
wielkość określa stała PAGE_SIZE w pliku page.h. W wersji
systemu, której dotyczy ten opis ma ona wielkość 4096 (bajtów, czyli 4
kB). W systemie Linux rozróżniamy dwa
rodzaje pamięci:


pamięć fizyczna

pamięć logiczna (wirtualna) jest to pamięć na użytek procesów
generowana przez jądro systemu. Pamięć ta może być wielkości nawet do 3
GB , mimo że teoretycznie powinna być ograniczona przez pamięć operacyjną
komputera. Dzieje się tak dlatego, że proces nie musi być w całości umieszczony
w pamięci operacyjnej aby być wykonywany. Część pamięci , która została
mu przydzielona może być przechwywana na dysku , a dopiero w razie odwołania
do niej wczytana do pamięci operacyjnej. Proces jednak nie wie czy pamięć
, do której się odwołuje jast na dysku twardym , dyskietce czy w pamięci
operacyjnej komputera , gdyż to wymianę stron między pamięcią a urządzeniem
zewnętrznym organizuje jądro (patrz : wymiana
). Z punktu widzenia procesu posiada on do dyspozycji bardzo dużą , jednorodną
i szybką pamięć logiczną.


To właśnie pamięć logiczna jest podzielona na strony. Skoro każda
strona musi mieć swój odpowiednik w pamięci fizycznej , to sensownie byłoby
podzielić także tę pamięć na bloki wielkości PAGE_SIZE. Tak też jest to
zrobione. Blok pamięci fizycznej wielkości PAGE_SIZE nazywa się ramką
.





Tablice stron


Tłumaczeniem adresów logicznych pamięci procesów na adresy
fizyczne zajmuje się MMU - Memory Menagement Unit
czyli sprzętowa jednostka zarządzania pamięcią. W momencie gdy proces przechodzi
do stanu wykonywania , jądro systemu przekazuje do MMU adres tablicy stron
procesu. Indeksami tej tablicy są logiczne numery stron procesu , a
wartościami adresy ramek , w których te strony są przechowywane. Nie jest
to jednak zwykła tablica lecz tablica potrójnie pośrednia :



Tablica zewnętrzna posiada 1k wskaźników do tablic środkowych,
tablica środkowa zawiera 1k wskaźników do tablic wewnętrznych , a każda
z nich dopiero 1k wskaźników do adresów ramek. Jest to mechanizm podobny
do użytego przy zarządzaniu wolnymi obszarami dyskowymi. W ten sposób można
zaadresować 1k * 1k * 1k = 1G stron czyli 4096 GB. Z tej liczby widać ,
że potrójna pośredniość została wykonana na wyrost. W rzeczywistości wykorzystywana
jest tylko podwójna pośredniość gdyż tablice środkowe wskazują na
jedną tylko tablicę wewnętrzną ( a nie na 1024 ).
Element
wskazywany przez tablicę wewnętrzną zawiera oprócz adresu ramki także inne
informacje. Adres ramki jest wielokrotnością jej rozmiaru (czyli 4 kB)
więc 12 bitów adresu do dokładnego miejsca w pamięci można zagospodarować
w inny sposób. Wykorzystywane jest 7 z nich m.in. do zaznaczenia czy ramka
jest aktualnie w pamięci, czy można na niej pisać, czy jest chroniona.
Taka struktura
jest wbrew pozorom bardzo łatwa w użyciu , charakteryzuje się szybkim dostępem
do danych ( w przzeciwieństwie do listy) a także oszczędnością pamięci
( w przeciwieństwie do jednowymiarowej długiej tablicy). Oszczędność pamięci
polega na tym, że przy małej ilości pamięci wykorzystywanej przez proces
większość tablic wewnętrznych nie będzie istniała.





Adresowanie


Każdy proces korzysta ze swojej pamięci logicznej. Aby
zająć , zwolnić lub pobrać zawartość kawałka pamięci o danym adresie logicznym
trzeba tenże adres przekształcić na adres fizyczny i dokonać właściwej
operacji. Tłumaczenie odbywa się w oparciu o tablicę
stron danego procesu. W momencie gdy proces jest wznawiany do wykonywania,
jądro informuje MMU gdzie znajduje się tablica stron tego procesu. Od tego
momentu proces odwołuje się do pamięci logicznej, a MMU dba o to , aby
w rzeczywistości odwołanie dotyczyło pamięci fizycznej. Sprzętowe wykonywanie
tłumaczenia adresów logicznych na fizyczne jest dużo szybsze niż tłumaczenie
programowe. Dzieje się tak dlatego, że operacja ta jest bardzo prosta -
wymaga jedynie zamiany części bitów na inne (pobrane z tablicy stron procesu).
Oto jak to się odbywa.

Adres logiczny zajmuje 32 bity z czego 20 bitów idzie na numer strony
(stąd powstaje ograniczenie na ilość stron procesu: 2 ^ 20 stron czyli
1M stron czyli 4 GB), a 12 bitów na przesunięcie na wskazanej stronie (
2 ^ 12 B = 4kB = wielkość strony = maksymalne przesunięcie ) . W tabeli
stron procesu znajduje się położenie (adres) ramki odpowiadającej stronie
o numerze wskazanym przez pierwsze 20 bitów adresu logicznego. Do uzyskanego
adresu fizycznego ramki (20 bitów) dodaje się żądane przesunięcie (12 bitów)
i uzyskuje adres fizyczny , o który chodziło .

PRZYKŁAD :

Chcemy odczytać wartość zmiennej typu int (2 bajty) która mieści
się w pamięci logicznej pod adresem : 5A6F4B27 (szesnastkowo). Numer logiczny
strony to pierwsze 20 bitów czyli : 5A6F4 , a przesunięcie to B27 (czyli
dziesiętnie : 2855 bajt na wskazanej stronie) . Przypuśćmy że w tablicy
stron danego procesu stronie o numerze 5A6F4 odpowiada ramka o adresie
21C38000. Na końcu muszą być trzy zera gdyż adres ramki jest wielokrotnością
rozmiaru ramki , który wynosi 4096 (szestnastkowo : 1000). Do uzyskanego
adresu dodawane jest przesunięcie na stronie :
21C38000 + B27 = 21C38B27
W ten sposób uzyskaliśmy adres fizyczny szukanej zmiennej.

Powstaje pytanie : czemu proces posiada pośrednią pamięć wirtualną ,
a nie od razu fizyczną ?

Dlatego , że w przeciwnym przypadku nimożliwe byłoby współbi
eżne wykonanie dwóch procesów z zachodzącymi na siebie zbioram i adr esów
. Zbiory te musiałyby być rozłączne , co spowodowałoby duże ograniczenia
na maksymalną ilość pamięci dla procesów ( ograniczeniem byłaby wielkość
pamięci operacyjnej komputera ). Przydzielenie pamięci dyskowej procesowi
spowodowałoby znowu , że każde odwołanie do niej zajmowałoby strasznie
dużo czasu , co wydłużyłoby wykonywanie programów setki lub nawet tysiące
razy.





Zalety stronicowania


Główną zaletą stronicowania jest brak fragmentacji
zewnętrznej czyli sytuacji , w której w pamięci robią się dziury ,
z których już nikt nie skorzysta.


PRZYKŁAD :

Załóżmy , że pozwolnieniu obszaru pamięci wielkości 2 kB ktoś zgłasza
zapotrzebowanie na 1,9 kB , które zostaje mu przydzielone z uprzednio zwolnionego
obszaru. Powstaje niezagospodarowany kawałek pamięci wielkości ok. 100
bajtów ( o ile nie uda się go włączyć do kolejnego obszaru , który być
może też jest wolny). Jest on na tyle mały , że być może nigdy nie znajdzie
się na niego chętny i ta część pamięci zostanie bezużyteczna. Taka sytuacja
może się zdarzać często i w sumie takie dziury spowodowałyby , że sporej
części pamięci nie można wykorzystać.


Przydzielanie pamięci w kawałkach ustalonego rozmiaru zapobiega
fragmentacji zewnętrznej gdyż najmniejszy nie użyty blok pamięci ma rozmiar
jednej strony. Taki blok ma równe sznse zostać użytym jak każdy inny ,
ponieważ proces i tak dostaje pamięć po jednej ramce ( a nie kilka na raz
).
Wiąże się z tym także inna zaleta. Proces , który zgłasza zapotrzebowanie
na kilka ramek dostaje je pojedyńczo , co powoduje , że nie muszą być one
spójnym blokiem pamięci fizycznej. Można wyobrazić sobie sytuację
, w której procesy muszą dostawać spójne bloki pamięci : proces czeka na
obszar wielkości 10 ramek , a w systemie wolnych jest wiele bloków wielkości
od jednej do dziewięciu ramek, ale nie ma większych. Proces musi czekać
, mimo że w sumie wolnej pamięci jest tyle, że można by zrealizować wielokrotnie
większe żądanie.







Wady stronicowania


Wad stronicowania jest niewiele , i pewnie dlatego jest ono
podstawą zarządzania pamięcią wszystkich wersji systemu UNIX. Jedyne wady
jakie przychodzą do głowy to:


fragmentacja wewnętrzna - proces może potrzebować dużo mniej
niż 4 kB pamięci , a mimo to dostanie blok tej wielkości . Pozostała część
strony nie zostanie być może użyta.

koszt utrzymywania pamięci w postaci stron i ramek - dla każdej strony
i ramki trzyma się informacje o nich (zajmują kilka bajtów ) co w sumie
daje pokaźną ilość pamięci.


Eliminowanie jednej z dwóch wyżej wymienionych wad powoduje narastanie
drugiej. Zwiększenie stałej PAGE_SIZE spowodowałoby mniejszy koszt urzymania
pamięci (mniejsza liczba ramek i stron) ale większą fragmentację zeenętrzną.
Natomiast zmniejszenie tej stałej zniwelowałoby efekt fragmentacji wewnętrznej
(mniejsze strony - mniej do zmarnowania ) ale zwiększyłoby się koszty (
rośnie liczba stron i ramek).





Bibliografia

plik : page_alloc.c

plik : page.h

plik : memory.c

Maurice J. Bach "Budowa systemu operacyjnego UNIX"




Autor: Maciej Kwiatkowski