Wprowadzenie

Zarządzanie pamięcią w Linuksie dotyczy wielu zagadnień i obejmuje całą gamę ciekawych algorytmów i struktur danych, na przykład: algorytm mieszający -- wykorzystany do obsługi ramek^15.1 pamięci buforowej systemu; algorytm wymiany stron -- w Linuksie jest to algorytm drugiej szansy, przybliżający LRU;^15.2 algorytm bliźniaków (ang. buddy) -- do zarządzania przydzielaniem pamięci dynamicznej w jądrze.

Poniżej omówiono algorytmy związane z zarządzaniem przestrzenią adresową procesów. W Linuksie do pamiętania informacji o obszarach wchodzących w skład przestrzeni adresowej procesu używa się drzew AVL. Sprawdzenie poprawności adresu wirtualnego wymaga więc odszukania węzła w drzewie AVL, a modyfikacja przestrzeni adresowej wiąże się z reorganizacją drzewa. Celem tej części pracy było sprawdzenie, w jakim stopniu ta dosyć skomplikowana struktura wpływa praktycznie na wydajność systemu. W tym celu zaprojektowano i przeprowadzono eksperymenty mające porównać cztery algorytmy wyszukiwania: w drzewie AVL, w uporządkowanej liście jednokierunkowej oraz w wymienionych strukturach wzbogaconych o pamiętanie ostatnio odwiedzonego węzła.
 

1999-05-21