PL 
EnglishDomyślny
Українська📄 Zastępowanie stron — LRU, FIFO i optymalny
Przepuść ciąg odwołań przez algorytmy zastępowania stron FIFO, LRU, Clock i optymalny, licząc błędy stron. Zobacz anomalię Bélády'ego, w której dodanie ramek pogarsza wynik FIFO zamiast go poprawiać.
O symulacji
Ten symulator przepuszcza ustalony zestaw ramek pamięci przez podany przez użytkownika ciąg odwołań (reference string) według czterech klasycznych polityk podmiany stron — FIFO, LRU, Clock (druga szansa) i optymalnej Bélády'ego — animując tablicę ramek odwołanie po odwołaniu i zaznaczając każdą komórkę na czerwono przy błędzie strony. Wbudowany preset odtwarza anomalię Bélády'ego: nieintuicyjny przypadek, w którym danie FIFO więcej ramek powoduje więcej błędów stron, a nie mniej.
🔬 Co pokazuje
Symulację stronicowania pamięci wirtualnej ramka po ramce: każda kolumna to jedno odwołanie z ciągu, każdy wiersz to fizyczna ramka, trafienia są oznaczone na zielono, a błędy na czerwono, a wysiedlony slot jest podświetlany za każdym razem, gdy błąd wymusza podmianę. Błędy stron, trafienia oraz wynikowy współczynnik trafień aktualizują się na żywo w miarę postępu animacji.
🎮 Jak korzystać
Wybierz politykę z listy rozwijanej, edytuj ciąg odwołań lub kliknij Randomise, i przeciągnij suwak Frames, aby zmienić liczbę stron mieszczących się jednocześnie w pamięci. Naciśnij Play, aby animować krok po kroku, lub Step, aby przejść o jedno odwołanie, i kliknij przycisk presetu anomalii Bélády'ego, aby wczytać klasyczny ciąg 1 2 3 4 1 2 5 1 2 3 4 5 z wybranym FIFO — a następnie porównaj liczbę błędów przy 3 ramkach i przy 4.
💡 Czy wiesz, że?
Anomalia Bélády'ego, odkryta przez László Bélády'ego w 1969 roku, była prawdziwym zaskoczeniem dla wczesnych projektantów systemów operacyjnych, którzy zakładali, że więcej pamięci nigdy nie może pogorszyć działania polityki cache'owania. Jest możliwa tylko przy algorytmach niebędących algorytmami stosowymi, jak FIFO; LRU i Optimal są dowodliwie odporne, ponieważ zbiór stron przechowywanych przy n ramkach jest zawsze podzbiorem zbioru przechowywanego przy n+1 ramkach.
Najczęściej zadawane pytania
Co dokładnie animuje ten symulator?
Bierze podany przez ciebie ciąg odwołań — sekwencję numerów stron, do których proces odwołuje się w czasie — i odtwarza go odwołanie po odwołaniu na ustalonej liczbie ramek pamięci, używając wybranej polityki podmiany stron. Każda kolumna w tablicy ramek reprezentuje jedno odwołanie, każdy wiersz jedną fizyczną ramkę, a każdy krok jest oznaczony jako trafienie (strona już obecna) lub błąd (stronę trzeba było załadować, ewentualnie wysiedlając inną).
Czym różnią się w tej symulacji FIFO, LRU, Clock i Optimal?
FIFO wysiedla stronę, która jest obecna najdłużej, śledzoną za pomocą prostego obracającego się wskaźnika. LRU wysiedla stronę, do której odwoływano się najdawniej, korzystając ze znacznika czasu zapisywanego przy każdym trafieniu. Clock tanio przybliża LRU poprzez cykliczne skanowanie bitów odwołania, dając niedawno dotkniętym stronom drugą szansę przed wysiedleniem. Optimal spogląda w przód w ciągu odwołań i wysiedla stronę, której następne użycie jest najdalej w przyszłości — dowodliwie najlepszy możliwy wybór, choć wymaga wiedzy, której żaden prawdziwy system nie posiada.
Jak odtworzyć anomalię Bélády'ego w symulatorze?
Kliknij przycisk presetu „Bélády's anomaly preset”, który wczytuje ciąg odwołań 1 2 3 4 1 2 5 1 2 3 4 5 i wybiera FIFO. Uruchom go przy suwaku Frames ustawionym na 3, zanotuj liczbę błędów, następnie zwiększ Frames do 4 i uruchom ponownie: FIFO daje 10 błędów przy 4 ramkach wobec 9 przy 3, mimo że otrzymał więcej pamięci. Przełączenie polityki na LRU lub Optimal dla tego samego ciągu pokazuje, że błędy tylko maleją lub pozostają na tym samym poziomie w miarę zwiększania liczby ramek.
Dlaczego tylko niektóre algorytmy mogą cierpieć na anomalię Bélády'ego?
LRU i Optimal to „algorytmy stosowe”: zbiór stron, które utrzymują przy n ramkach, jest zawsze podzbiorem tego, co utrzymywałyby przy n+1 ramkach, co matematycznie gwarantuje, że błędy nigdy nie rosną wraz ze wzrostem pamięci. FIFO i Clock nie mają tej własności stosowej — konkretna strona, którą polityka FIFO wybiera do wysiedlenia, może się zmieniać w sposób, który nie jest po prostu „zachowaj wszystko z przypadku mniejszej liczby ramek plus jedną więcej”, co otwiera drogę do anomalnego zachowania.
Co właściwie mierzą współczynnik trafień i liczba błędów stron?
Każde odwołanie w ciągu jest klasyfikowane jako trafienie (strona już w ramce) lub błąd (strona nieobecna, wymagająca załadowania i ewentualnie wysiedlenia). Współczynnik trafień to po prostu trafienia podzielone przez wszystkie odwołania, i jest to standardowy sposób, w jaki podręczniki systemów operacyjnych porównują polityki podmiany na tym samym obciążeniu: wyższy współczynnik trafień przy tej samej ilości pamięci oznacza mniej kosztownych odczytów z dysku.