Zarządzanie pamięcią
Zarzadzanie pamięcią (Memory Management) na poziomie SO jest uwarunkowane
architekturą systemu cyfrowego. Podstawowymi elementami determinującymi wybór
konkretnej organizacji i jej struktury sÄ…:
·ð pole adresacji argumentów rozkazu
·ð jego miejsce w sÅ‚owie
·ð sprzÄ™towe możliwoÅ›ci jego przeksztaÅ‚cenia.
W zależności od długości pola adresacji (liczby bitów przeznaczonych na adres)
przestrzeń adresowa (PA) może pokrywać się z zakresem adresów PO, może być
większa lub mniejsza.
Funkcjami SO sÄ…:
·ð zagospodarowanie przestrzeni adresowej poprzez wykorzystanie
mechanizmów translacji adresu
·ð ochrona zawartoÅ›ci pamiÄ™ci
·ð dostÄ™p do obszarów dzielonych
·ð efektywna organizacja PO
Wielkość PO przeznaczonej na kod SO jest z reguły stała, natomiast problemem jest
przydział wolnej części PO procesom użytkowym Pu.
Istnieją trzy metody przydziału PO procesom Pu.
1. brak podziału - wolna przestrzeń adresowa jest w danej chwili w całości
przydzielona jednemu Pu
2. podział pamięci - wolna przestrzeń adresowa jest w danej chwili podzielona
na części, które są przydzielane pojedyńczym Pu
3. pamięć wirtualna - istnieje jedna lub wiele wirtualnych przestrzeni
adresowych przydzielanych pojedyńczym Pu, mających w niewielkim stopniu
pokrycie w pamięci operacyjnej
Pamięć niepodzielna
Brak możliwości podziału PA pamięci na fizycznie wyróżnione bloki wynika z braku
wyposażenia procesora w układy MM.
Wolna PA pozostała po załadowaniu SO jest w całości przydzielona pojedyńczemu
programowi użytkownika. W trakcie translacji początek adresacji jest określony
pierwszym wolnym adresem.
Wieloprogramowanie można realizować poprzez wymiatanie (swapping).
Pamięć dzielona
Celem dzielenia pamięci jest lepsze wykorzystanie elementów sprzętowych systemu,
a głównie procesora i pamięci.
Ponadto, jednoczesne załadowanie do PO więcej niż jednego Pu umożliwia szybkie
przełączanie procesora z jednego procesu na drugi.
W ramach systemów z podziałem pamięci można wyróżnić:
1. z podziałem statycznym
2. z podziałem dynamicznym
Podział statyczny dzieli pamięć na stałe partycje o różnej wielkości lub na bloki o
stałej długości zwane ramami (frame).
Podział dynamiczny jest realizowany z wykorzystaniem struktur opisujących wolne
bloki pamięci (WBP) o różnych długościach oraz mechanizmu wymiatania.
Podział dynamiczny
Przykładowe funkcje realizujące podział dynamiczny
Dla realizacji podziału dynamicznego pamięci można stosować następujące
hipotetyczne funkcje:
* przydziel(rozmiar, adres)
Wybranie spośród wolnych bloków, bloku pokrywającego zapotrzebowanie
(blok wolny może być większy bądz
równy blokowi określonemu przez
parametr rozmiar). Efektem wykonania funkcji jest przekazanie adresu
wybranego wolnego bloku poprzez parametr adres oraz usunięcie
przydzielonego bloku ze zbioru wolnych bloków.
malloc(size), calloc(n, size), realloc(ptr, size)
·ð zwolnij(adres)
Dołączenie bloku dotychczas zajętego do zbioru wolnych bloków.
free(ptr)
·ð informuj(rozmiar_max)
Przekazanie w argumencie rozmiar_max rozmiaru aktualnie największego
wolnego bloku.
msize(buffer)
Struktury danych wolnych bloków
Początkowo obszar wolny pamięci tworzy pojedyńczy blok. Następnie w trakcie
wykonywania funkcji przydziału bloków pamięci o żądanej długości z WBP
wydzielony jest fragment. Dalej kolejne wywołania funkcji przydziału i zwrotu
bloków, zgłaszane w dowolnym porządku, dzielą cały obszar pamięci na wolne i
zajęte bloki o różnych długościach.
Dla prawidłowej gospodarki wolnymi blokami zbiór WBP musi być zorganizowany
w jednÄ… strukturÄ™ (garbage collection). Wykorzystuje siÄ™ do tego celu :
·ð listy jedno lub dwukierunkowe
·ð mapy bitowe
·ð tablice wolnych bloków
Dobranie odpowiedniej struktury WBP w połączeniu z algorytmem alokacji ma
decydujące znaczenie dla sprawności MM.
Algorytmy alokacji
Zadaniem algorytmu alokacji jest wybranie WBP, w ramach którego może być
wydzielony obszar o żądanej długości. Obszar ten co do długości może być całym
blokiem lub jego częścią, pozostawiając niewykorzystany fragment jako WBP o
mniejszej dÅ‚ugoÅ›ci. W systemie może być okreÅ›lona wartość Dðn bÄ™dÄ…ca dÅ‚ugoÅ›ciÄ…
minimalną WBP. Jeżeli pozostały po przydziale fragment jest mniejszy od
minimalnego (Dðn), to część przydzielonego bloku tworzy fragmentacjÄ™.
W zależności od SO spotykamy różne algorytmy alokacji. Rozpatrzmy niektóre z
nich.
1. Algorytm pierwszej zgodności (First Fit)
Wybiera pierwszy blok ze zbioru WBP, którego długość jest nie mniejsza od
długości żądanego bloku.
2. Algorytm najlepszej zgodności (Best Fit)
Wybiera ze zbioru WBP blok o najmniejszej długości spełniający
wymagania zlecenia przydziału.
3. Algorytm najgorszej zgodności (Worst Fit)
Oparty na założeniu, że najkorzystniejsze jest przydzielanie obszarów
największych.
4. Algorytm bliz
niaków (Buddies)
Oparty na podziale pamięci (o długości 2k) na dwa bliz
niacze bloki. Jeden z
nich jest dalej połowiony, aż do uzyskania bloku o minimalnej długości
spełniającego wymagania zlecenia przydziału.
1. Przy wyborze algorytmu alokacji należy uwzględnić takie czynniki jak:
·ð prÄ™dkość
·ð prostotÄ™
·ð efekt fragmentacji
2. Efektom fragmentacji można przeciwdziałać przez:
·ð zwalnianie i scalanie
·ð zagÄ™szczanie i relokacje
·ð stronicowanie
Pamięć wirtualna
Def.
Pamięcią wirtualną nazywamy system pamięci złożony z co najmniej dwóch
rodzajów pamięci: małej i szybkiej (pamięci operacyjnej) oraz dużej, lecz wolnej
(pamięci pomocniczej), a także z dodatkowego sprzętu i oprogramowania
umożliwiającego automatyczne przenoszenie fragmentów pamięci z jednego
rodzaju pamięci do drugiego.
Pamięć wirtualna zatem sprawia wrażenie pamięci, której szybkość dostępu jest
zbliżona do szybkości dostępu pamięci operacyjnej i której pojemność jest równa
pojemności pamięci pomocniczej (PP).
Przy realizacji pamięci wirtualnej stosuje się następujące metody:
·ð stronicowanie
·ð segmentowanie
·ð stronicowanie z segmentowaniem
Stronicowanie
W odróżnieniu od organizacji dopuszczającej zmienne długości bloków, rozwiązanie
to bazuje na stałym podziale pamięci.
Jednostkami takiego podziału są:
* ramy, ramki (frame) dla pamięci fizycznej
* strony (page) dla wirtualnej PA procesu
System na bieżąco przydziela ramy procesom w ten sposób, że dany proces może
mieć część stron umieszczonych w PO (strony aktywne) a resztę stron - w PP (strony
nieaktywne). Mechanizm stronicowania ma dwa zadania:
·ð wykonywanie operacji odwzorowywania adresów wirtualnych (adw) w
adresy rzeczywiste (adr), czyli określenie, do której strony odnosi się adres w
programie, oraz znajdowanie ramy, którą bieżąco zajmuje dana strona
·ð przesyÅ‚anie - w zależnoÅ›ci od potrzeby - stron z PP do PO oraz odsyÅ‚anie nie
używanych już stron z powrotem z PO do PP
Opis rozmieszczenia stron oraz organizacja wolnych obszarów wymagają istnienia
specjalnych tablic zawierających niezbędne informacje.
SÄ… to odpowiednio:
·ð tablica stron
·ð tablica ram
Podział na ramy i strony wiąże się bezpośrednio z adresacją poprzez wydzielenie
w polu adresowym bitów na numer strony. Każdy adres składa się z:
n bitowego numeru strony, d bitowego przemieszczenia
Przykład stronicowania
Stronicowanie z dwoma poziomami tablic stron
page number page offset
pi
p2 d
10 10 12
Pamięć wirtualna nie stawia żadnych wymagań użytkownikowi i organizuje przydział
pamięci systemowo wykorzystując tablice ram i stron. Wymaga to:
* obsługi przez system przerwania, zwanego chybieniem (page fault),
sygnalizującego brak w PO strony, do której nastąpiło odwołanie. Strona taka mieści
się w PP i jest ściągana do PO na żądanie
* dla przyśpieszenia wyznaczania adr tablica stron aktualnie wykonywanego Pu jest
przenoszona do pamięci asocjacyjnej - w jednym cyklu dostępu następuje wybranie
adresu ramy.
Obsługa chybienia powoduje:
wskazanie ramy dla żądanej strony
zwolnienie wskazanej ramy
ściągnięcie żądanej strony w obszar wskazanej ramy
 aktualizacja tablicy ram
Wskazaniem ramy, w przypadku braku ram wolnych zajmuje siÄ™ algorytm
wymiany (replacement algorithms).
Zadaniem tego algorytmu jest usunięcie z PO strony najmniej potrzebnej w
przyszłości i sprowadzenie na jej miejsce żądanej strony.
Uwagi:
·ð dobór dÅ‚ugoÅ›ci strony ma wpÅ‚yw na fragmentacje wewnÄ™trznÄ…
(niewykorzystaną część ostatniej strony procesu) oraz upakowanie
procesów w pamięci
·ð dla stron współdzielonych tablice powinny być modyfikowane tak, aby
wskazywały wszystkie korzystające z danej strony procesy. W praktyce
wyróżnia się:
·ð strony jednoprocesowe
·ð strony wieloprocesowe
Współdzielenie stron
Algorytmy wymiany
1. FIFO (First-In First-Out)
Usuwa stronę, która jako pierwsza (najdawniej) została sprowadzona do PO.
2. LIFO (Last-In First-Out)
Usuwa stronę, która została sprowadzona do PO jako ostatnia.
3. LRU (Least Recently Used)
Usuwa stronę, do której najdłużej nie było odwołań (najdawniej używaną)
4. LFU (Least Frequently Used)
Usuwa stronę, do której było najmniej odwołań (o najmniejszej częstości
odwołań)
5. MRU (Most Recently Used)
Usuwa stronę ostatnio używaną
6. MFU (Most Frequently Used)
Usuwa stronę najczęściej używaną
7. RAND (Random)
Usuwa stronÄ™ wybranÄ… losowo
8. LNR (Longest Next Reference)
Usuwa stronę o maksymalnej wartości odległości wprzód (forward distance)
9. WS (Working Set)
Usuwa stronÄ™ spoza zbioru roboczego
10. ATLAS (od nazwy komputera z pierwszÄ… PW)
Bazuje na miarach czasu bezczynności strony zakładając, że
wykorzystywane sÄ… cyklicznie.
Efektywność funkcjonowania PW
Liczba chybień występujących w trakcie realizacji łańcucha odwołań jest zależna od:
·ð pojemnoÅ›ci PO
·ð stosowanego algorytmu
Obciążenie SO obsługą PW może prowadzić do załamania systemu (trashing).
Wynika to z nadmiernego (częstego) wykorzystywania systemu do wymiany stron i
relatywnie niskiego wykorzystania do innych celów.
Załamanie na krzywej przepustowości jest najbardziej widoczne w systemach
wieloprogramowych, w których przy założeniu poprawności algorytmu wymiany
przydzielona programom pamięć jest zbyt mała.
W celu unika tego typu sytuacji stosuje się kryteria globalne o dużym stopniu
złożoności np. określa się przepustowość na bieżąco (liczbę uchybień) i
przekroczenie określonego progu jest sygnalizowane.
Segmentacja
Celem segmentacji jest organizacja PA w taki sposób, by odzwierciedlała logiczny
podział informacji. Przestrzeń adresów (PA) dzieli się na segmenty, takie na
przykład jak:
·ð tekst programu
·ð dane lokalne
·ð dane wspólne
·ð stos systemowy i tp.
Przy organizacji pamięci wirtualnej programista może korzystać z dużej liczby
segmentów i w odniesieniach do nich używać nadanych przez siebie nazw. W ten
sposób PA staje się dwuwymiarowa, ponieważ adresy w programie identyfikuje się
za pomocÄ… :
·ð nazwy segmentu
·ð adresu wewnÄ…trz segmentu.
Odwzorowanie adresu może być implementowane za pomocą tworzonej dla każdego
procesu tablicy segmentów, w której element o numerze s zawiera adres bazy
(adres początku) i długość segmentu s danego procesu. Elementy tablicy
segmentów nazywa się czasem deskryptorami segmentu (segment descriptor).
·ð celem segmentacji jest logiczny podziaÅ‚ PA, podczas gdy celem
stronicowania jest fizyczny podział pamięci, którą chcemy implementować
jako pamięć na tym samym poziomie
·ð strony majÄ… ustalony rozmiar wynikajÄ…cy z architektury komputera, podczas
gdy rozmiar segmentów może być dowolny, określony przez programistę
·ð w przypadku dużych programów nie można wszystkich segmentów umieÅ›cić
w PO, zwłaszcza gdy pamięć musi być dzielona między kilka procesów. Mamy
więc do czynienia z taką sytuacją, w której PW jest większa od pamięci
fizycznej
1
4
1
2
3
2
4
3
user space physical memory space
·ð możemy zatem zastosować albo stronicowanie, albo wymieniać caÅ‚e
segmenty
·ð w przypadku stronicowania każdy segment skÅ‚ada siÄ™ na ogół z kilku stron i
ma własną tablicę stron
Przykład współdzielenia segmentów
Translacja adresów w architekturze Intel 30386
·ð segmentacja z dwupoziomowym stronicowaniem