Podręcznik

4. Pamięć wirtualna

Przy zastosowaniu stronicowania, założeniem jest, że aby program mógł być wykonany musi być całkowicie wczytany do pamięci RAM. W momencie kiedy zastosowana jest pamięć wirtualna, system operacyjny pozwala na wykorzystanie pamięci o większej pojemności od zainstalowanej pamięci RAM. Obszary logicznej przestrzeni adresowej, do których proces często się odwołuje przechowywane są w pamięci RAM. Obszary, do których proces odwołuje się rzadko, przechowywane są na dysku (może to znacznie obniżyć wydajność systemu). Przedłużenie pamięci RAM na dysk twardy nazywane jest pamięcią wirtualną. Należy zaznaczyć, że w żaden sposób nie da się uruchomić programu bezpośrednio z dysku twardego. Jest to związane ze sposobem dostępu do danych na dysku. Możemy z niego odczytać/zapisać klaster jako najmniejszą jednostkę alokacji (zwykle 4 kB). Do uruchomienia programu dostęp do danych musi być bajtowy (czyli musimy mieć możliwość odczytywania/zapisywania poszczególnych bajtów). Aby więc wykonać program zapisany w pamięci wirtualnej (na dysku) musimy ponownie wczytać go do pamięci RAM. Jeśli jednak dany fragment programu nie będzie nigdy wykorzystywany, może w ogóle nie być wczytany do pamięci RAM. Pamięć wirtualna zazwyczaj skonstruowana jest w oparciu o stronicowanie na żądanie (ang. on-demand paging). Ideę tego procesu przedstawiono na rysunku 14.

Rys. 14. Pamięć wirtualna

 

W logicznej przestrzeni adresowej proces zajmuje pewną liczbę ramek. Przestrzeń ta jest ciągła. Tablica stron (jak w zwykłym stronicowaniu) odwzorowuje ramki na strony w pamięci fizycznej RAM. Z tym, że w tym przypadku w tablicy stron wykorzystywany jest dodatkowy bit, bit poprawności. Bit ten informuje, czy strona jest w pamięci RAM, czy w pamięci pomocniczej, którą tworzy dysk twardy. Dodatkowo, w przypadku pamięci wirtualnej tablica stron przechowuje zazwyczaj dwa bity oznaczane „dirty” – D (do strony był zapis) i „accessed” – A (do strony było odniesienie). Dane w pamięci dyskowej są przechowywane na specjalnie sformatowanej partycji lub w pliku „swap”. System plików na partycjach wymiany jest specjalnie optymalizowany pod kątem szybkości dostępu do danych. Informacje prezentowane dla użytkownika mają w tym przypadku mało istotne znaczenie.

W najprostszym przypadku do pamięci RAM wprowadzane są tylko te strony, które są potrzebne. Jest to tzw. leniwa wymiana. W przypadku, kiedy system operacyjny wykryje brak strony (bit p) wykonywana jest sekwencja poleceń systemowych, która sprowadza się do:

• przechowania stanu przerwanego procesu,
• sprowadzenia brakującej strony do pamięci,
• wznowienia procesu w tym samym miejscu.

Do realizacji pamięci wirtualnej potrzebne jest wsparcie systemu operacyjnego, ale również pewne zaplecze sprzętowe, jak:

• tablica stron,
• pamięć pomocnicza,
• system operacyjny musi umożliwiać wznowienie procesu w miejscu przerwania.

Pamięć wirtualna może mieć bardzo duży wpływ na wydajność całego systemu. Dlatego musi być zaimplementowana bardzo rozważnie. Brak strony wywołuje całą sekwencję zdarzeń związaną z:

1. Obsługą przerwania wywołanego brakiem strony.
2. Czytaniem strony z dysku.
3. Wznowieniem procesu.

Pierwsza i trzecia czynność realizowana jest programowo i sprowadza się zwykle do kilkuset rozkazów. Czas realizacji tych rozkazów to 1 do 100 us. Najbardziej czasochłonne jest czytanie/zapisywanie strony na dysku. Czas dostępu do pamięci RAM mieści się zwykle w zakresie od 10 do 100 ns, natomiast dostęp do pamięci dyskowej trwa ok. 10 ms. Zatem błąd braku strony zwiększa czas dostępu 100 000 razy. Żeby nie dopuścić do wyraźnego spowolnienia systemu błędy braku stron mogą występować bardzo rzadko – 1 brak na kilka milionów odwołań.

Żeby wydajnie zaimplementować pamięć wirtualną trzeba rozwiązać dwa główne problemy:

• zastępowanie stron,
• przydział ramek.

W pewnym momencie wolne ramki mogą się skończyć. Przyjmijmy, że procesowi przydzielono k ramek pamięci oraz że wszystkie ramki są już zajęte. W takiej sytuacji przy błędzie braku strony musimy wybrać jedną ze stron obecnych w pamięci (stronę-ofiarę). Jeżeli ta strona została zmodyfikowana (D==1), to należy ją dodatkowo zapisać na dysk. Ma to spory wpływ na wydajność systemu, dlatego że w tym przypadku wymagane są dwa dostępy do dysku twardego. Następnie ramka odpowiadająca wybranej stronie jest zwalniana. Nietrywialnym zadaniem jest wybranie ramki-ofiary. Zazwyczaj chcemy, aby strony, do których proces się często odwołuje, przebywały na stale w pamięci. Powstaje tu problem jak określić “częstość odwołań do strony”.  Wybór strony-ofiary jest wykonywany przez algorytm zastępowania stron (ang. page replacement). Istnieje wiele algorytmów zastępowania stron, z których tylko nieliczne mają zastosowanie praktyczne.

Pierwszym jest algorytm optymalny. Mówi on, że należy zastąpić tą stronę, do której nie będziemy się odwoływać przez najdłuższy czas. Algorytm ten, ze względu na konieczność posiadania informacji o przyszłości, jest niemożliwy do zaimplementowania w praktyce. Jest on za to szeroko stosowany do porównywania z innymi algorytmami.

Jednym z najprostszych i najłatwiejszych do zaimplementowania jest algorytm FIFO (ang. First In First Out). Mówi on, że należy zastąpić tą stronę, która została sprowadzona jako pierwsza do pamięci. Sprowadzone strony tworzą kolejkę FIFO. Algorytm ten jest daleki od optymalnego. Strona, która była wprowadzona dawno do systemu może być cały czas potrzebna. Poza tym algorytm ten jest obarczony anomalią Belady'ego - większa liczba ramek niekoniecznie zmniejsza liczbę błędów stron.

Jednym z najbardziej obiecujących jest algorytm LRU (ang. Least Recently Used). W algorytmie tym zastępowana jest strona, która nie była najdłużej używana. Zakłada się, że ta strona nie będzie dalej potrzebna. Algorytm ten nie wykazuje anomalii Belady'ego. Jednak do zaimplementowania tego algorytmu w czystej postaci potrzebna jest pewne zaplecze sprzętowe, umożliwiające określenie liczby odwołań do strony w jednostce czasu. Większość systemów ma tylko bity A oraz D. Dlatego w praktyce stosuje się algorytmy przybliżające metodę LRU.

Jednym z takich algorytmów jest algorytm drugiej szansy. Jego zasada działania jest następująca:

• Jest to modyfikacja algorytmu FIFO.
• W standardowym algorytmie FIFO wybierana jest pierwsza strona z kolejki.
• W algorytmie drugiej szansy sprawdzany jest bit odniesienia A.
• Jeżeli A==0 (brak odniesienia) to strona jest wybierana na ofiarę.
• Jeżeli (A==1) (odniesienie) to: bit A jest ustawiany na zero, strona nie jest usuwana na dysk, strona jest przesunięta na koniec kolejki (otrzymuje drugą szansę).
• Przechodzimy do kolejnej strony w kolejce.

W algorytmie tym możemy też uwzględnić bit D „dirty”. Należy pamiętać, że strona która została zmodyfikowana musi być zaktualizowana w pamięci dyskowej. Operacja taka będzie wymagała dodatkowego czasu. Zapisywanie zmodyfikowanych stron może być realizowane w różny sposób:

• Strona zapisywana w momencie jej zastąpienia
  • mała liczba zapisów na dysk,
  • powolny algorytm - brak strony powoduje konieczność zapisania strony na dysk i wczytania strony z dysku.
• Strony zapisywane periodycznie w tle
  • proces drugoplanowy przegląda strony i zapisuje strony zmodyfikowane (D==1), do których ostatnio nie było odwołań,
  • zapisanie strony powoduje skasowanie bitu D.
  • proces drugoplanowy może zapisywać strony grupami (większa wydajność operacji dyskowych).

System operacyjny może też utrzymywać pewną pulę wolnych ramek.

Drugim ważnym problemem do rozwiązania, przy implementacji pamięci wirtualnej, jest odpowiedni przydział ramek do procesu. Przy stronicowaniu na żądanie w systemie wieloprogramowym zakłada się współistnienie wielu procesów. Strony mogą być przydzielane:

• lokalne - strona-ofiara jest wybrana wyłącznie spośród stron procesu,
• globalne - strona-ofiara jest wybrana spośród stron wszystkich procesów.

Przydział globalny jest bardziej optymalny. Innym problemem jest sposób rozdziału ramek między procesy. Tu można zastosować:

• przydział stałej liczby ramek, np. 100 ramek, 5 procesów, przydział po 20 ramek,
• przydział liczby ramek proporcjonalnie do rozmiaru procesu,
• przydział liczby ramek proporcjonalnie do rozmiaru procesu z uwzględnieniem priorytetów.

Oczywiście trzecia możliwość jest najbardziej optymalna i jest stosowana w praktyce. Powstaje jednak pytanie jaka jest optymalna liczba ramek, która powinna być przypisana do konkretnego procesu? W celu określenia tej optymalnej liczby ramek stosuje się model strefowy. Założeniem jest to, że proces może w różnych etapach swojego działania potrzebować różnej liczby ramek. W praktyce określa się górną i dolną granicę występowania braków stron dla procesu (Rys. 15). Jeśli osiągnięto górną granicę, to liczba braków stron jest zbyt duża i procesowi należy przydzielić więcej ramek. Jeśli osiągnięto dolną granicę, to liczba braków stron jest mała i procesowi można zabrać pewną liczbę ramek. W ten sposób można określić optymalną liczbę ramek dla procesu.

 

Rys. 15. Model strefowy