4.9 Stronicowanie
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:
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ą .
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.
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.
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.
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:
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).