Ogólnie

 

Najpierw trochę poza tematem, opiszemy przydział ciągły pamięci by, odwołując się do niego, móc spokojnie wejść w segmentację.

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. 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 kompaktyfikacja

 

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 kompaktyfikacją lub upakowaniem. Kompaktyfikacja 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ą kompaktyfikację. Zwróćmy uwagę na to, że zajęte obszary nie muszą być upakowane razem, scalamy obszary wolne. Przenosimy segment P3, żeby zrobić trochę miejsca 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 kompaktyfikacja 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 kompaktyfikacji.
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. Wstawiamy segment P6 wg odpowiedniej strategii

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ć kompaktyfikację. 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. 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.