Ważną zmianą w nowym jądrze 2.6 jest wprowadzenie tak zwanego odwrotnego odwzorowania stron (ang. reverse mapping). Pozwoliło ono na lepsze zarządzanie pamięcią wirtualną. Zmiana została wprowadzona przez Holendra Rika van Riel.
Aby dobrze zrozumieć na czym polega odwrotne odwzrorowanie stron należy najpierw zapownać się z zarządzaniem stronami i ramkami (pamięcią wirturalną) w Linuxie. A więc na początek krótkie przypomnienie.
Każdy proces ma swoją logiczną przestrzeń adresową, podzieloną na strony. Niektóre strony siedzą w ramkach, które są cześcią pamięci fizycznej. Co jakiś czas procesy chcą oglądać nowe strony, te które jeszcze nie siedzą w ramkach, należy je więc sciągać do pamięci fizycznej. Jednak ramek jest ograniczenie wiele, więc niektóre ramki trzeba zwalniać. Linux zwykle do zwolnienia wybiera te ramki, które już najdłużej nie były używane, w związku z tym nie wydaje się, żeby miały być używane w najbliższej przyszłości. I tu dochodzimy do sedna sprawy. Gdy zwalniana jest pewna ramka należy 'poinformować proces' o tym, że ta ramka została zwolniona, czyli odwołać się do odpowiedniej tablicy stron. W dalszej części zajmiemy się różnymi algorytmami stosowanymi do poinformowania odpowiednich procesów.
W Linuxie 2.4 wyszukiwanie wszystkich tablic stron było bardzo żmudnym zadaniem. Algorytm był najprostszy jaki tylko można sobie wyobrazić. Dla każdego procesu przeglądane były wszystkie jego tablice stron. Zauważmy, że algorytm ten jest bardzo wolny, ma jednak taką zaletę, że nie jest konieczne utrzymywania żadnych struktur na jego użytek. Jest jednak na tyle wolny, szczególnie dla dużej liczby procesów, że zdecydowano się go poprawić.
Nowy algorytm w jądrze 2.6 jest zupełnie inny. Dla każdej fizycznej strony (ramki) są pamiętane tablice stron, w których dana ramka jest widoczna. Konkretnie w strukturze page reprezentującej ramkę jednym z pól jest unia pte. Unia ta złożona jest z listy chain oraz wskaznika direct. W liście chain pamiętane są adresy tych tablic stron, w których pojawia się dana ramka. Pole direct jest optymalizacją, wskazuje na odpowiednią tablicę tylko i wyłącznie w przypadku, gdy jest ona jedna.
Zauważmy, że przy takich strukturach algorytm wyszukiwania wszystkich tablic stron, w których pojawia się dana ramka staje się bardzo prosty. Wystarczy tylko przejść po liście chain, lub spojrzeć pod wskaźnik direct. Nowy algorytm działa w czasie O(liczba procesów widzących ramkę), a nie tak, jak poprzedni O(liczba wszystkich procesów)
Warto zwrócić uwagę na to, że są dość wysokie koszty takiego przyspieszenia.
Po pierwsze dla każdej ramki pamiętamy wszystkie tablice stron, a więc jest to dość sporo pamięci.
Przy dużym obciążeniu systemu ta ilość pamięci może być rzeczywiście spora.
Druga sprawa to fakt, że system jest zmuszony do utrzymywania unii pte. Przy każdym zamapowaniu lub odmapowaniu pliku z pamięci, a
także przy zakończeniu procesu system musi odpowiednio uaktualniać strukturę.
Okazuje sie jednak, że mimo wszystko nowa zmiana jest bardzo korzystna, przyspiesza administrowanie pamięcią. Podobno trwają pracę nad ulepszeniem tego algorytmu i w nowych wersjach jądra możemy sie spodziewać poprawek.
Poniżej obrazek pokazujący struktury użyte do nowego algorytmu
Dla zainteresowanych podaję tutaj parę struktur z nowego jądra. Kod pochodzi konretnie z jądra 2.6.5.
struct page {
page_flags_t flags; /* atomic flags, some possibly
updated asynchronously */
atomic_t count; /* Usage count, see below. */
struct list_head list; /* ->mapping has some page lists. */
struct address_space *mapping; /* The inode (or ...) we belong to. */
unsigned long index; /* Our offset within mapping. */
struct list_head lru; /* Pageout list, eg. active_list;
protected by zone->lru_lock !! */
union {
struct pte_chain *chain;/* Reverse pte mapping pointer. */
* protected by PG_chainlock */
pte_addr_t direct;
} pte;
unsigned long private; /* mapping-private opaque data */
.............
};
#define NRPTE ((L1_CACHE_BYTES - sizeof(unsigned long))/sizeof(pte_addr_t))
struct pte_chain {
unsigned long next_and_idx;
pte_addr_t ptes[NRPTE];
} ____cacheline_aligned;
#if !defined(CONFIG_HIGHPTE)
typedef pte_t *pte_addr_t;
#endif
------------------------------------------------
typedef struct { unsigned long pte_low; } pte_t;
Korzystałem z następujących źródeł: