O czym lepiej zapomnieć?

Afiliacja: Wydział Matematyki, Informatyki i Mechaniki, Uniwersytet Warszawski

Mam wrażenie, że jeszcze kilka lat temu każda reklama laptopa składała się wyłącznie z wykrzykiwanych przez lektora kolejnych angielskich skrótów (np. RAM, SSD, HDMI), czasami wraz z wartościami liczbowymi je opisującymi. Wydaje mi się, że celem tych reklam nie było przekazanie widzowi informacji o parametrach sprzedawanego sprzętu, a jedynie zrobienie wrażenia na tych, którzy nie wiedzieli, co oznaczają wymienione skróty i wartości liczbowe, tak aby zyskali przekonanie, że prezentowany laptop korzysta z najnowszych technologii w ich najlepszym wydaniu. Z biegiem czasu ilość takich reklam się zmniejszała, pewnie przez fakt, że coraz więcej konsumentów ma świadomość, czym różni się np. pamięć RAM od dysku SSD.

W tym artykule skupimy się właśnie na parametrach związanych z pamięcią. Wiemy, że rodzajów pamięci w komputerze jest kilka – mamy m.in. rejestry, cache, RAM, dysk SSD, dysk twardy. To, czym się one od siebie różnią, świetnie opisał Tomasz Idziaszek w artykule Pamięć w komputerze w \(\Delta^{5}_{16}\). Nie będziemy tutaj powtarzać całego artykułu, ale wspomnimy tylko najważniejszy wniosek – główne różnice pomiędzy wymienionymi rodzajami pamięci to ich cena i szybkość dostępu do danych. Im szybszy jest jakiś rodzaj pamięci, tym jest droższy i mniej mamy go w komputerze. Dla przykładu laptop, na którym piszę ten artykuł, ma \(477\) GB pamięci na dysku SSD i \(16\) GB (czyli prawie \(30\) razy mniej) szybszej pamięci RAM.

W jaki sposób ta zależność między ilością a szybkością różnych rodzajów pamięci wpływa na działanie procesora? Generalnie zasada jest prosta – jeśli procesor musi skorzystać z danych, które znajdują się w wolniejszej pamięci, to przenosi je do szybszej pamięci, aby mieć do nich łatwiejszy dostęp. W teorii brzmi świetnie, ale przecież szybszej pamięci mamy mniej. Co, jeśli procesor chce przenieść jakieś dane z dysku SSD do pamięci RAM, ale okazuje się, że jest ona już w całości wypełniona? Nie ma rady, trzeba wtedy coś z pamięci RAM usunąć (np. zapisać część danych z powrotem na dysku SSD, zwalniając fragment RAM-u). No dobrze, ale jak wybrać, które dane odeślemy na SSD? Na pewno jeśli w RAM-ie mamy jakieś dane, z których nie będziemy korzystać w najbliższym czasie, to wydają się one dobrym kandydatem – przecież i tak nie są nam potrzebne w pamięci z szybkim dostępem. Ponadto, jeśli do jakiejś porcji danych odwołujemy się co chwila, to odesłanie ich na dysk SSD skończy się tym, że za chwilę znów będziemy musieli je ściągać do RAM-u, co spowolni działanie komputera. Widać więc, że podjęcie właściwej decyzji jest kluczowe dla zapewnienia efektywnego działania komputera.

Teoretyczny model pamięci w komputerze

Aby przeanalizować przedstawiony problem w szczegółach, posłużymy się uproszczonym modelem pamięci w komputerze. Założymy mianowicie, że mamy tylko dwa jej rodzaje – pamięć szybką i pamięć wolną. Komputer zwykle operuje na większych fragmentach pamięci, nazywanych stronami (w zależności od kontekstu mówimy też o blokach albo ramkach) – typowy rozmiar strony to coś rzędu \(4\) kB. Przyjmiemy więc, że w pamięci szybkiej możemy pomieścić maksymalnie \(k\) stron danych (inaczej można powiedzieć, że składa się ona z \(k\) ramek), natomiast pamięć wolna jest nieograniczona i może pomieścić nieskończenie wiele stron. W trakcie swojego działania procesor potrzebuje czasami odwołać się do danych znajdujących się na konkretnych stronach. Jeśli strona \(s,\) do której procesor chce się odwołać, znajduje się akurat w pamięci szybkiej, to nie ma żadnego problemu. Gorzej, jeśli strony \(s\) w pamięci szybkiej nie ma – wtedy mamy do czynienia z błędem braku strony (ang. page fault). Procesor musi sprowadzić stronę z pamięci wolnej do pamięci szybkiej, co zajmuje pewien czas. Ponadto, jeśli w pamięci szybkiej mamy już zajęte wszystkie \(k\) ramek, to procesor musi wybrać jedną stronę \(s',\) która aktualnie znajduje się w pamięci szybkiej, i usunąć ją (inaczej: zapomnieć) poprzez odesłanie jej do pamięci wolnej. Oczywiście chcielibyśmy w taki sposób wybierać stronę do zapomnienia, żeby zminimalizować liczbę błędów braku strony w czasie działania procesora. W ten sposób zapewnimy, że komputer będzie działać efektywnie.

Strategia FIFO

Jednym z możliwych algorytmów wyboru, którą stronę zapomnieć, jest strategia FIFO (ang. first in, first out). Zgodnie z jej założeniami, jeśli musimy zapomnieć którąś stronę, to wybieramy tę, która była najdawniej załadowana do pamięci szybkiej. Prześledźmy działanie tego algorytmu na konkretnym przykładzie. Załóżmy, że w pamięci szybkiej możemy zmieścić \(k = 3\) strony, zaś procesor generuje kolejno odwołania do stron \(D, E, C, A, D, E, B, D, E, C, A, B.\) Oczywiście na samym początku nasza pamięć szybka jest pusta, więc pierwsze odwołanie do strony \(D\) spowoduje błąd braku strony i załadowanie \(D.\) Podobnie będzie przy dwóch kolejnych odwołaniach do stron \(E\) i \(C.\) Po tych trzech pierwszych odwołaniach mamy \(3\) błędy braku strony i trzymamy w pamięci szybkiej strony \(D, E, C.\) Kiedy procesor generuje odwołanie do strony \(A,\) znowu mamy błąd braku strony. Tym razem jednak musimy zdecydować, którą ze stron aktualnie trzymanych w pamięci szybkiej zapomnimy. Skoro trzymamy się strategii FIFO, to decydujemy się na usunięcie \(D,\) ponieważ ona była najwcześniej dodana. Mamy więc już \(4\) błędy braku strony, a w pamięci szybkiej trzymamy \(E, C, A.\) Dalszy przebieg algorytmu zaznaczamy w tabelce poniżej.

W górnym rzędzie \(*\) oznacza, że wystąpił błąd braku strony. Z kolei w trzech dolnych wierszach trzymamy zawartość pamięci szybkiej po wczytaniu kolejnej strony, w kolejności, w jakiej były załadowane do pamięci.

Okazało się, że dla tego ciągu strategia FIFO spowodowała aż \(9\) błędów braku strony. Jednak prawdopodobnie było to spowodowane tym, że mieliśmy tylko \(k = 3\) ramki do dyspozycji. Oczywiście, gdyby ramek było więcej, to błędów braku strony byłoby mniej. Dla przykładu zobaczmy w tabelce, co dzieje się dla \(k = 4.\)

Czyli rzeczywiście dla większej liczby dostępnych ramek algorytm FIFO zrobił mniej błędów braku strony. Zaraz! Przecież teraz mieliśmy \(10\) takich błędów, a dla trzech ramek było ich tylko \(9\)! Jak to możliwe, że gdy mamy więcej dostępnej pamięci, powstaje więcej błędów braku strony, które spowalniają procesor? Czy w takim razie, żeby przyspieszyć nieco swój komputer, powinienem zmniejszyć ilość dostępnego RAM-u? Przecież to brzmi absurdalnie.

Cechą niektórych algorytmów wymiany strony jest to, że przy odpowiednio spreparowanym ciągu odwołań zwiększenie liczby dostępnych ramek w pamięci szybkiej zwiększa liczbę błędów braku strony. Taką sytuację nazywamy anomalią Bélády’ego, od nazwiska informatyka, który w 1969 roku zademonstrował ją po raz pierwszy. Nie oznacza to jednak, że przy każdym ciągu odwołań zwiększenie liczby ramek będzie skutkowało większą liczbą błędów. Dla przykładu, jeśli dla rozważanego ciągu zwiększymy dostępną szybką pamięć do \(k = 5\) ramek, to wtedy błędów braku strony będzie już tylko \(5.\)

László Bélády (1928–2021) – węgierski informatyk pracujący zarówno na uniwersytetach, jak i w sektorze prywatnym.

Algorytm FIFO, mimo że jest bardzo prosty w implementacji (wystarczy trzymać jedną kolejkę ze stronami wczytywanymi do pamięci szybkiej), nie jest w praktyce używany we współczesnych systemach operacyjnych. Wynika to z tego, że nie bierze pod uwagę, czy do jakiejś strony były ostatnio odwołania, a tylko kiedy była wczytana, co intuicyjnie nie ma związku z częstością korzystania z niej.

Strategia LRU

Strategia, która wydaje się lepszym rozwiązaniem problemu zarządzania pamięcią, to LRU (ang. least recently used). Mówi ona, żeby usuwać tę stronę, która była używana najdawniej. Jest ona trudniejsza do implementacji od strategii FIFO, ale we współczesnych systemach operacyjnych używa się jej albo jakichś jej przybliżeń. Zobaczmy, jak strategia ta radzi sobie z rozważanym ciągiem odwołań, analizując jej działanie dla \(k = 3\) ramek w tabelce poniżej.

Tym razem w trzech dolnych wierszach trzymamy zawartość pamięci szybkiej po wczytaniu kolejnej strony w kolejności ostatniego odwołania.

Wyszło nam \(10\) błędów braku strony. Czy jeśli dołożymy jeszcze jedną ramkę \((k = 4)\), to liczba błędów się zwiększy? Zachęcamy Czytelnika do samodzielnego sprawdzenia, ile błędów wtedy wyjdzie. Okazuje się, że w ogólności zachodzi następujące twierdzenie.

Twierdzenie. Strategia LRU jest wolna od anomalii Bélády’ego. To znaczy, dla dowolnego ciągu odwołań do pamięci \(S\) i liczb \(k_1 \le k_2\) liczba błędów braku strony dla ciągu \(S\) przy strategii LRU z \(k_2\) dostępnymi ramkami w pamięci szybkiej nie będzie większa niż dla strategii LRU z \(k_1\) ramkami.

Strategia optymalna

Rozpatrzyliśmy już dwa algorytmy wymiany stron. Dla rozważanego ciągu przy strategii FIFO z trzema ramkami wystąpiło \(9\) błędów braku strony, a dla strategii LRU z taką samą liczbą ramek było ich \(10.\) Można zadać sobie pytanie, ile najmniej błędów braku strony może się pojawić przy odpowiednio dobranej strategii korzystającej z takiej liczby ramek. No i oczywiście jak taka najlepsza możliwa strategia wygląda.

Okazuje się, że strategię optymalną można bardzo łatwo opisać – z pamięci szybkiej należy zapominać tę stronę, do której odwołanie nastąpi najpóźniej w przyszłości. Dla rozważanego ciągu jeśli zastosujemy strategię optymalną z \({k = 3}\) ramkami, to po pierwszych trzech błędach braku strony, kiedy to wczytamy do pamięci \(D, E, C,\) widząc następne odwołanie do strony \(A,\) zapomnimy z pamięci stronę \(C.\) Rzeczywiście, do strony \(D\) będziemy się odwoływać już w kolejnym kroku, do strony \(E\) jeszcze w kolejnym, podczas gdy następne odwołanie do strony \(C\) występuje dopiero za sześć kroków. Jak dokładnie zadziała algorytm optymalny dla \(k = 3,\) przeanalizujmy w poniższej tabelce.

Tym razem w trzech dolnych wierszach trzymamy zawartość pamięci szybkiej po wczytaniu kolejnej strony w kolejności, w jakiej odwołamy się do tych stron w przyszłości.

Tym razem było tylko \(7\) błędów braku strony, czyli rzeczywiście mniej niż dla strategii FIFO i LRU. Pozostawiamy Czytelnikowi dowód, że tak zdefiniowana strategia jest rzeczywiście optymalna, czyli dla każdego możliwego ciągu odwołań popełni nie więcej błędów braku strony niż dowolna inna strategia z taką samą liczbą ramek. Oczywiście własność ta oznacza, że strategia optymalna jest wolna od anomalii Bélády’ego.

Skoro znamy strategię optymalną, to czemu w ogóle rozważaliśmy FIFO i LRU? Jako że jest optymalna, to przecież najbardziej opłaca się ją zaimplementować w systemie operacyjnym! Otóż strategia optymalna ma jedną podstawową wadę – nie da się jej zaimplementować w praktyce. Decyzja o tym, którą stronę usunąć, wymagała, żeby przeanalizować, jakie odwołania do stron pojawią się w przyszłości, a przecież żaden komputer nie potrafi przewidzieć, co zaraz zrobi użytkownik. Ma on wiedzę tylko o tym, jakie odwołania pojawiały się w przeszłości. Tak to niestety się czasami zdarza, że teoretycznie najlepsze rozwiązania nie są możliwe do zrealizowania w praktyce. Okazuje się jednak, że strategia LRU z \(2k\) stronami popełni z grubsza dwa razy więcej błędów braku strony niż strategia optymalna z \(k\) stronami. To jednak temat na zupełnie inny artykuł.

Konkretnie Sleator i Tarjan pokazali w 1985 roku, że jeśli algorytm optymalny z \(k_{\textup{OPT}}\) ramkami popełni \(t\) błędów braku strony, to algorytm LRU z \(k_{\textup{LRU}} \ge k_{\textup{OPT}}\) ramkami popełni takich błędów co najwyżej \[\frac{k_{\textup{LRU}}}{k_{\textup{LRU}} - k_{\textup{OPT}} + 1}(t + k_{\textup{OPT}}).\]