Wykonywać można jedynie program umieszczony w pamięci głównej (pamięci operacyjnej)
Wiązanie instrukcji i danych z adresami w pamięci może się odbywać w czasie:
kompilacji: jeśli są znane a priori adresy w pamięci, to generuje się kod absolutny; zmiana położenia kodu w pamięci wymaga jego rekompilacji;
ładowania: trzeba generować kod przemieszczalny;
wykonania: jeśli proces może się przemieszczać w pamięci podczas wykonania, to trzeba wiązać dynamicznie; wymaga to specjalnego sprzętu.
Dynamiczne ładowanie - program ładuje się do pamięci dopiero po wywołaniu.
Dynamiczne łączenie - łączenie opóźnione do czasu wykonania; zazwyczaj dotyczy bibliotek systemowych.
Nakładki - w pamięci przechowuje się tylko te części przestrzeni adresowej, które są niezbędne w danej chwili; umożliwia wykonywanie programów większych od przydzielonego im obszaru pamięci; implementowane przez użytkownika.
Logiczna i fizyczna przestrzeń adresowa:
adresy logiczne (wirtualne): generowane przez CPU;
adresy fizyczne: widziane przez jednostkę pamięci;
adresy logiczne i fizyczne są:
Jednostka zarządzająca pamięcią (ang. Memory Management Unit, MMU): urządzenie sprzętowe, które odwzorowuje adresy wirtualne na fizyczne.
Wymiana (ang. swapping):
Proces może zostać czasowo wysłany z pamięci głównej do zewnętrznej, a po jakimś czasie sprowadzony ponownie do pamięci głównej
Jako pamięć zewnętrzna na potrzeby wymiany służy duży szybki dysk z dostępem bezpośrednim.
Główny narzut: czas transmisji.
różne wersje wymiany są realizowane w wielu systemach, np. w różnych wersjach Uniksa czy Microsoft Windows.
Przydział pojedynczego obszaru
Pamięć podzielona na dwa obszary: dla rezydującego systemu operacyjnego i dla użytkownika.
Rejestr bazowy (relokacji) i graniczny służą do ochrony oraz do dynamicznej translacji adresów logicznych na fizyczne.
Np. IBM PC: BIOS (programy sterujące urządzeń) w ROM-ie (górne adresy), SO w RAM-ie (dolne adresy).
Przydział wielu obszarów
W systemach wieloprogramowych w pamięci równocześnie przebywa wiele programów, każdy we własnym obszarze.
Metoda stref statycznych: pamięć jest na stałe podzielona na obszary o ustalonej wielkości (np. IBM OS/360 MFT).
Metoda stref dynamicznych: liczba i wielkość stref zmienia się dynamicznie (np. IBM OS/360 MVT).
Dziura: wolny obszar pamięci; dziury różnych rozmiarów są rozrzucone po pamięci.
Strategia wyboru wolnego obszaru:
Pierwszy pasujący (ang. first fit): przydziela pierwszy obszar o wystarczającej wielkości (następny pasujący: szukanie rozpoczyna się od miejsca, w którym ostatnio zakończono szukanie); z reguły krótszy czas szukania.
Najlepiej pasujący (ang. best fit): przydziela się najmniejszy z dostatecznie dużych obszarów; wymaga przeszukania całej listy (o ile nie jest uporządkowana wg rozmiaru); pozostająca część obszaru jest najmniejsza.
Najgorzej pasujący (ang. worst fit): przydziela się największy obszar; wymaga przeszukania całej listy; pozostająca część obszaru jest największa.
Pierwszy pasujący i najlepiej pasujący są zwykle lepsze w terminach czasu i wykorzystania pamięci.
Fragmentacja zewnętrzna: suma wolnych obszarów w pamięci wystarcza na spełnienie żądania, lecz nie stanowi spójnego obszaru.
Fragmentacja wewnętrzna: przydzielona pamięć może być nieco większa niż żądana. Różnica między tymi wielkościami znajduje się wewnątrz przydzielonego obszaru, lecz nie jest wykorzystywana.
Redukowanie fragmentacji zewnętrznej przez defragmentację: umieszczenie całej wolnej pamięci w jednym bloku; możliwe tylko w przypadku, gdy adresy są wiązane w czasie wykonania; różne strategie defragmentacji; defragmentacja a operacje wejścia-wyjścia.
Pamięć fizyczna jest podzielona na bloki jednakowego rozmiaru, zwane ramkami (rozmiar ramki jest potęgą 2, między 0.5 K bajtów a 8 K bajtów).
Logiczna przestrzeń adresowa procesu jest podzielona na bloki o rozmiarze takim jak ramki, zwane stronami.
Strony przebywają w pamięci pomocniczej, są sprowadzane do pamięci głównej i umieszczane w wolnych ramkach (program o n stronach potrzebuje n ramek); strony nie muszą zajmować ciągłego obszaru fizycznego.
Fragmentacja wewnętrzna, brak fragmentacji zewnętrznej (małe ramki to mniejsza fragmentacja wewnętrzna, ale większy narzut na tablice stron).
System przechowuje informacje o wolnych ramkach (w tablicy ramek).
Tablica stron procesu służy do odwzorowywania adresów logicznych w adresy fizyczne.
Adres logiczny składa się z dwóch części:
Rysunek: Sprzęt stronicujący (źródło: Silberschatz, Galvin, Podstawy systemów operacyjnych)
Implementacja tablicy stron:
Tablica stron jest przechowywana w pamięci głównej.
Rejestr bazowy tablicy stron wskazuje jej początek. Każdy dostęp do danych/instrukcji programu wymaga dwóch dostępów do pamięci głównej.
Przyśpieszenie translacji jest możliwe dzięki zastosowaniu rejestrów asocjacyjnych (zwanych także buforami translacji bliskiego otoczenia, ang. Translation Lookaside Buffer, TLB).
Rysunek: Sprzęt stronicujący z buforami TLB (źródło: Silberschatz, Galvin, Podstawy systemów operacyjnych)
Porównanie pozycji z kluczami w rejestrach asocjacyjnych odbywa się równocześnie dla wszystkich kluczy (szybkie, ale drogie). Wynik: pole wartości. Jeśli nie ma, to trzeba zajrzeć do tablicy stron.
Współczynnik trafień (ang. hit ratio) - procent numerów stron znajdowanych w rejestrach asocjacyjnych (zależy od liczby rejestrów).
Efektywny czas dostępu do pamięci:
Odwrotna tablica stron
Posiada po jednej pozycji dla każdej ramki; pozycja zawiera adres wirtualny strony umieszczonej w ramce oraz identyfikator procesu będącego właścicielem strony
W porównaniu z tradycyjną tablicą stron zmniejsza zużycie pamięci, ale wydłuża czas potrzebny na znalezienie adresu.
Użycie tablicy mieszającej pozwala skrócić czas wyszukiwania.
Rysunek:Odwrócona tablica stron (źródło: Silberschatz, Galvin, Podstawy systemów operacyjnych)
Stronicowanie umożliwia dzielenie wspólnego kodu (taki kod musi być wielowejściowy, ang. reentrant, czyli nie może modyfikować sam siebie); edytory, kompilatory itp.
Do ochrony pamięci służą bity ochrony przypisane każdej ramce i zwykle umieszczone w tablicy stron.
Schemat zarządzania pamięcią zgodny ze sposobem widzenia pamięci przez użytkownika.
Program jest zbiorem segmentów. Segment jest jednostką logiczną, taką jak: program główny, procedura, funkcja, stos, tablica symboli, tablice, zmienne lokalne i globalne.
Adres logiczny: (numer_segmentu, przesunięcie).
Tablica segmentów: każda pozycja zawiera fizyczny adres początku segmentu i rozmiar segmentu.
Rejestr bazowy tablicy segmentów zawiera adres tablicy.
Ochrona: z każdą pozycją w tablicy segmentów są związane bity ochrony.
Dzielenie: na poziomie segmentów jest bardziej naturalne niż na poziomie stron, ten sam adres w różnych pozycjach tablicy stron różnych procesów.
Przydział pamięci: pierwszy/najlepszy pasujący, fragmentacja zewnętrzna.
Multics: każdy segment ma swoją tablicę stron, znika problem fragmentacji zewnętrznej; deskryptor segmentu zawiera adres tablicy stron segmentu (w pamięci), długość segmentu i pomocnicze bity; tablica segmentów jest też stronicowana.
Intel 80386 - translacja adresu (na jednym rysunku)
Rysunek: Tłumaczenie adresu w procesorze Intel 80386 (źródło: Silberschatz, Galvin, Podstawy systemów operacyjnych)
Umożliwia wykonywanie procesów, pomimo że nie są one w całości przechowywane w pamięci operacyjnej ani nie zajmują spójnych obszarów pamięci.
Logiczna przestrzeń adresowa może być dużo większa od fizycznej przestrzeni adresowej.
Tworzy iluzję dużej, jednorodnej i szybkiej pamięci.
Procesy mogą współdzielić fragmenty swojej przestrzeni adresowej.
Części przestrzeni adresowej procesów są relokowalne, czyli mogą być umieszczone w dowolnym miejscu w pamięci fizycznej i mogą być przemieszczane w trakcie wykonania procesu.
Techniki realizacji pamięci wirtualnej: stronicowanie na żądanie, segmentacja na żądanie, segmentacja ze stronicowaniem.
Strona jest sprowadzana do pamięci dopiero wtedy, gdy jest potrzebna: mniej wejścia-wyjścia, mniejsze zapotrzebowanie na pamięć, więcej użytkowników.
Strona jest potrzebna, gdy pojawia się do niej odwołanie.
Z każdą pozycją w tablicy stron jest związany bit poprawności odwołania (1 - strona w pamięci, 0 - strona poza pamięcią).
Odwołanie do strony z bitem poprawności równym 0 powoduje błąd braku strony (ang. page fault). System operacyjny:
Co się dzieje, gdy nie ma wolnej ramki?
Wymiana stron (ang. page replacement) - SO znajduje w pamięci stronę (najmniej używaną) i usuwa ją na dysk.
Niektóre strony mogą być sprowadzane do pamięci wielokrotnie.
Zarządzanie pamięcią w Linuksie 2.4.19 jest opisane bardzo szczegółowo przez A. Naynai'ego w Memory Management in Linux (ma 393 strony!).
Zarządzanie pamięcią w Linuksie 2.4.20 (z informacją co się pojawi w 2.6) jest opisane bardzo szczegółowo przez Mela Gormana w Understanding the Linux Virtual Memory Manager (zdalnie) i (lokalnie, PDF).
O systemie bliźniaków można także przeczytać w krótszym opracowaniu Mela Gormana: Buddy Algorithm (zdezauktualizowała się jedynie informacja o mapach bitowych).
O stronach, ramkach, przerwaniach i innych podstawach traktuje krótkie opracowanie Mela Gormana The Basics.
W Linuksie część pamięci fizycznej RAM (ang. Random Access Memory) jest alokowana na stałe na potrzeby kodu i statycznych struktur danych jądra. Cała pozostała pamięć podlega stronicowaniu i jest wykorzystywana w celu:
zaspokojenia żądań jądra dotyczących buforów, deskryptorów i innych dynamicznych stuktur danych jądra,
zaspokojenia żądań procesów dotyczących zwykłych obszarów pamięci oraz do odwzorowywania plików w pamięci,
zwiększenia wydajności operacji wejścia-wyjścia z/do urządzeń blokowych przez utrzymywanie podręcznej pamięci buforowej.
Pamięć fizyczna RAM podlegająca stronicowaniu jest podzielona na ramki, rozmiar ramki definiuje stała PAGE_SIZE (plik include/asm-i386/page.h):
Wszystkie ramki w systemie są opisane w tablicy mem_map (tzw. tablicy ramek):
extern struct page *mem_map;
która zawiera elementy typu struct page. Podczas inicjowania systemu jądro zaczyna zajmować dla siebie miejsce od dolnych adresów pamięci. Po zakończeniu ładowania systemowych danych i kodu cała pozostała pamięć jest dzielona na ramki. W tym momencie jest inicjowana tablica mem_map.
Definicja struktury page:
typedef struct page {
unsigned long flags;
atomic_t _count;
atomic_t _mapcount;
struct {
unsigned long private;
struct address_space *mapping;
}
pgoff_t index;
struct list_head lru;
...
};
Wartością pola jest licznik odwołań do strony. Jeśli ma wartość -1, to ramka jest wolna. Jeśli ma wartość większą lub równą 0, to ramka jest przydzielona jednemu lub większej liczbie procesów lub przechowuje struktury danych jądra.
Pole używane przez kilka modułów jądra, z różnym przeznaczeniem. Jest wskaźnikiem do listy buforów, w przypadku gdy strona zawiera bufory. Jeśli ramka jest wolna, to jest wykorzystywana w systemie bliźniaków.
Używana gdy strona trafia do pamięci podręcznej stron lub gdy należy do anonimowego obszaru.
Używane przez kilka modułów jadra, z różnym przeznaczeniem. Na przykład identyfikuje pozycję przechowywanych w ramce danych w ich obrazie na dysku lub w ramach anonimowego obszaru. Może też przechowywać identyfikator strony wymiecionej na dysk.
Zawiera wskaźniki do podwójnie wiązanej listy stron, uporządkowanej w kolejności LRU. Gdy ramka jest wolna, to jest wykorzystywane w systemie bliźniaków do łączenia wolnych obszarów w listę.
Oto niektóre flagi używane w polu flags. Uwaga: zmiana oraz testowanie wartości tego pola zazwyczaj jest operacją niepodzielną.
#define PG_locked 0
#define PG_error 1
#define PG_referenced 2
#define PG_uptodate 3
#define PG_dirty 4
#define PG_lru 6
#define PG_active 7
#define PG_slab 8
#define PG_highmem 11
#define PG_reserved 14
Wszystkie strony procesów mogą uczestniczyć w operacjach wejścia-wyjścia:
Bit ten służy do zakładania blokady na ramce na czas operacji wejścia-wyjścia. Ustawia się go przed zainicjowaniem operacji i czyści po zakończeniu. Pole page->wait służy jako kolejka procesów oczekujących na zakończenie wejścia-wyścia na tej stronie.
Bit ten informuje o tym, czy operacja wejścia-wyjścia w ramce zakończyła się sukcesem.
Bit ten jest wykorzystywany w procesie wyboru strony do odesłania na urządzenie wymiany. Bit ten jest zapalany za każdym razem kiedy system odwołuje sie do strony w tej ramce poprzez kolejkę mieszającą (mapping, index). Ten bit razem z bitem odwołania w tablicy stron jest używany do manipulowania wiekiem strony page->age i przesuwania strony na listach active, inactive_dirty i inactive_clean. Warto zauważyć, że do ochrony bitu PG_referenced, listy page_lru oraz list active, inactive_dirty i inactive_clean służy klucz pagemap_lru_lock, a nie bit PG_locked. Bit jest sprawdzany i modyfikowany w funkcji odpowiedzialnej za wybór ramki do zwolnienia. Jeśli ramka ma zapalony bit PG_referenced, to jest on zerowany, a strona nie jest odsyłana na urządzenie wymiany.
Bit ten mówi, czy zawartość ramki jest aktualna. Ustawia się go po pomyślnym zakończeniu operacji czytania z dysku do ramki.
Strony z zapalonym bitem PG_highmem nie są na stałe odwzorowane do wirtualnej przestrzeni adresowej jądra, trzeba je odwzorować osobno, żeby móc wykonać na nich operację wejścia-wyjścia. Struktura struct page (bity z informacją) jest zawsze odwzorowana do przestrzeni adresowej jądra.
Ustawia się go w przypadku ramek zarezerowanych na potrzeby jądra lub nieużywalnych.
Pamięć fizyczna RAM podlegająca stronicowaniu jest dzielona na strefy. Na komputerach klasy PC mamy trzy strefy. Oto fragment definicji strefy.
/*
* ZONE_DMA < 16 MB ISA DMA capable memory
* ZONE_NORMAL 16-896 MB direct mapped by the kernel
* ZONE_HIGHMEM > 896 MB only page cache and user processes
*/
struct zone {
spinlock_t lock;
unsigned long free_pages;
unsigned long pages_min, pages_low, pages_high;
struct free_area free_area[MAX_ORDER];
/* Fields commonly accessed by the page reclaim scanner */
spinlock_t lru_lock;
struct list_head active_list;
struct list_head inactive_list;
....
};
#define ZONE_DMA 0
#define ZONE_NORMAL 2
#define ZONE_HIGHMEM 3
Strefy są związane z różnym przeznaczeniem pamięci fizycznej. Obsługa wolnych ramek w każdej strefie przebiega analogicznie.
Informacje o ramkach zawierających wolne obszary pamięci fizycznej są przechowywane w strukturze free_area, a informacje o ramkach zajętych w tablicach stron procesów i w tablicy stron jądra.
struct free_area free_area[MAX_ORDER];
Struktura free_area została zaprojektowana z myślą o algorytmie bliźniaków. Jest to tablica cyklicznych list wolnych obszarów pamięci fizycznej o różnych rozmiarach. Wielkość tablicy określa stała MAX_ORDER równa 11. Do i-tego pola tablicy jest dowiązana lista wolnych i spójnych kawałków pamięci o wielkości: (2^i) * PAGE_SIZE, gdzie i = 0..MAX_ORDER -1. Czyli pierwsza lista zawiera kawałki pamięci wielkości jednej strony, a ostatnia kawałki wielkości 1024 stron. Każdy taki kawałek pamięci, mimo że może składać się z wielu stron, jest spójnym blokiem pamięci fizycznej.
Pole tablicy free_area zawiera strukturę typu struct free_area (Uwaga: struktura w tej postaci pojawiła się po raz pierwszy w jądrze 2.6.11, poprzednio jednym z pól była mapa bitowa):
struct free_area {
struct list_head free_list;
unsigned long nr_free;
};
Jedenaście takich struktur jest głowami jedenastu list cyklicznych. Pole nr_free zawiera liczbę wolnych obszarów ustalonego rozmiaru. Informacja o byciu wolnym obszarem określonego rozmiaru jest zawarta w strukturze page (gdy ramka jest wolna): pole private pierwszej ramki w bloku 2^k wolnych ramek przechowuje liczbę k, a pole flags ma ustawioną flagę PG_BUDDY. Funkcja page_is_buddy() przekazuje TRUE, gdy strona jest początkiem obszaru wolnego o rozmiarze 'order' stron:
#define PageBuddy(page) test_bit(PG_buddy, &(page)->flags)
static inline int page_is_buddy(struct page *page, int order)
{
if (PageBuddy(page) && page_order(page) == order) {
BUG_ON(page_count(page) != 0);
return 1;
}
return 0;
}
unsigned long __get_free_pages(unsigned int gfp_mask, unsigned int order)
Funkcja ta żąda przydzielenia wolnego obszaru pamięci i przekazuje adres liniowy przydzielonego obszaru (parametr order mówi, w której kolejce obszarów zacząć szukać, gdyż jest żądaniem bloku wielkości (2^order) * PAGE_SIZE). Szukanie obszaru do przydzielenia zaczyna się od kolejki o numerze order. Jeśli nie jest ona pusta, to wyjmuje się jeden element i przekazuje jego adres jako wynik funkcji. Jeśli kolejka jest pusta, to szuka się pierwszej niepustej kolejki na prawo (tzn. jednej z kolejek zawierających większe obszary pamięci). Gdy taka się znajdzie, wyjmuje się jeden jej element. Jest on oczywiście za duży więc trzeba go podzielić. Dotąd dzieli się go na połowy, aż otrzymany fragment jest żądanej wielkości. Pozostałe po dzieleniu połówki wstawia się do odpowiednich kolejek jako obszary gotowe do przydzielenia, uaktualniając równocześnie informacje o przynależności obszarów do systemu bliźniaków.
static void __free_pages_ok (struct page *page, unsigned int order)
Funkcja ta zwalnia obszar wskazany (pośrednio) przez page o wielkości: (2^order) *PAGE_SIZE i wstawia go do jednej z kolejek w tablicy free_area.Obszar zwalniany musiał być kiedyś przydzielony. Skoro był przydzielony, to musiał być wydzielony z bloku dwa razy większego. Być może jego bliźniak (czyli druga połowa tego większego bloku) też jest wolny i można je będzie połączyć z powrotem w jeden większy spójny obszar. Jeśli to się uda, to można szukać bliźniaka dla tego większego kawałka itd. Wykonuje się to w pętli dotąd, aż szukany bliźniak okaże się być zajęty. Dodaje się wtedy blok do odpowiedniej kolejki, a także aktualizuje informacje o przynależności obszarów do systemu bliźniaków.
Czemu ma służyć struktura free_area skoro proces żądający kilku ramek pamięci i tak dostaje je po jednej i to wcale nie w spójnym bloku? Otóż struktura ta powstała głównie na użytek jądra, które musi mieć przydzielane spójne obszary pamięci i to w różnych rozmiarach.
Algorytm bliźniaków jest bardzo szybki. Wynika to z tego, że większość operacji arytmetycznych polega na przesunięciu dwójkowym lub zamianie bitu. Dlatego właśnie tablica free_area jest indeksowana potęgami dwójki.
Każdy obszar dołączony do kolejki jest wstawiany na jej początek, natomiast pobieranie następuje z początku lub ze środka (jeśli chcemy wyjąć bliźniaka o danym adresie ).
| Janina Mincer-Daszkiewicz |