UK 
EnglishТипова
Polski📄 Заміщення сторінок — LRU, FIFO та оптимальне
Проганяйте рядок звернень через політики заміщення FIFO, LRU, Clock та оптимальну, рахуючи промахи сторінок. Побачте аномалію Біледі, де додавання кадрів робить FIFO гіршим, а не кращим.
Про цю симуляцію
Цей симулятор проганяє фіксований набір кадрів пам'яті через наданий користувачем рядок звернень за чотирма класичними політиками заміщення сторінок — FIFO, LRU, Clock (другий шанс) та Оптимальною (Біледі) — анімуючи таблицю кадрів по одному зверненню за раз і забарвлюючи кожну клітинку в червоний при промаху. Вбудований пресет відтворює аномалію Біледі: контрінтуїтивний випадок, коли надання FIFO більшої кількості кадрів дає більше промахів сторінок, а не менше.
🔬 Що показано
Покрокова симуляція сторінкової організації віртуальної пам'яті: кожен стовпець — одне звернення з рядка, кожен рядок — фізичний кадр, влучення позначено зеленим, а промахи — червоним, і виселений слот підсвічується щоразу, коли промах змушує до заміщення. Промахи сторінок, влучення та результуючий коефіцієнт влучень оновлюються наживо по мірі просування анімації.
🎮 Як користуватися
Оберіть політику зі спадного списку, відредагуйте рядок звернень або натисніть Randomise, і перетягніть повзунок Frames, щоб змінити, скільки сторінок вміщується в пам'яті одночасно. Натисніть Play, щоб анімувати покроково, або Step, щоб просунутися на одне звернення, і натисніть кнопку пресету «Аномалія Біледі», щоб завантажити класичний рядок 1 2 3 4 1 2 5 1 2 3 4 5 з обраним FIFO — а потім порівняйте кількість промахів при 3 та 4 кадрах.
💡 Чи знали ви?
Аномалію Біледі, відкриту Ласло Біледі у 1969 році, стала справжнім сюрпризом для ранніх розробників операційних систем, які вважали, що більше пам'яті ніколи не може погіршити роботу політики кешування. Вона можлива лише з нестековими алгоритмами, як-от FIFO; LRU та Оптимальний доведено імунні до неї, оскільки набір сторінок, що утримуються з n кадрами, завжди є підмножиною набору, що утримується з n+1 кадрами.
Часті запитання
Що саме анімує цей симулятор?
Він бере наданий вами рядок звернень — послідовність номерів сторінок, до яких звертається процес з часом — і відтворює його по одному зверненню за раз проти фіксованої кількості кадрів пам'яті, використовуючи обрану вами політику заміщення сторінок. Кожен стовпець таблиці кадрів відповідає одному зверненню, кожен рядок — одному фізичному кадру, і кожен крок позначається як влучення (сторінка вже резидентна) або промах (сторінку довелося завантажити, можливо, виселивши іншу).
Чим відрізняються FIFO, LRU, Clock та Оптимальний у цій симуляції?
FIFO виселяє сторінку, яка перебуває в пам'яті найдовше, відстежуючи це простим оберталистим вказівником. LRU виселяє сторінку, до якої зверталися найдавніше, використовуючи мітку часу, записану при кожному влученні. Clock дешево наближає LRU круговим скануванням бітів посилання, даючи нещодавно торкнутим сторінкам другий шанс перед виселенням. Оптимальний заглядає вперед у рядку звернень і виселяє сторінку, наступне використання якої найвіддаленіше в майбутньому — доведено найкращий можливий вибір, хоча він потребує знань, яких жодна реальна система не має.
Як відтворити аномалію Біледі в симуляторі?
Натисніть кнопку «Пресет аномалії Біледі», яка завантажує рядок звернень 1 2 3 4 1 2 5 1 2 3 4 5 і обирає FIFO. Запустіть з повзунком Frames на 3, зафіксуйте кількість промахів, потім збільште Frames до 4 і запустіть знову: FIFO дає 10 промахів з 4 кадрами проти 9 з 3, хоча йому дали більше пам'яті. Перемикання на LRU чи Оптимальний на тому самому рядку показує, що промахи лише зменшуються або лишаються незмінними при збільшенні кадрів.
Чому лише деякі алгоритми можуть страждати від аномалії Біледі?
LRU та Оптимальний — «стекові алгоритми»: набір сторінок, які вони утримують з n кадрами, завжди є підмножиною того, що вони утримували б з n+1 кадрами, що математично гарантує: промахи ніколи не зростають при збільшенні пам'яті. FIFO та Clock не мають цієї стекової властивості — конкретна сторінка, яку обирає для виселення політика FIFO, може змінюватися не за принципом «зберегти все з випадку меншої кількості кадрів плюс одна», що відкриває шлях до аномальної поведінки.
Що насправді вимірюють коефіцієнт влучень і кількість промахів сторінок?
Кожне звернення в рядку класифікується як влучення (сторінка вже в кадрі) або промах (сторінка відсутня, потребує завантаження й можливо виселення). Коефіцієнт влучень — це просто влучення, поділені на загальну кількість звернень, і саме так підручники з операційних систем стандартно порівнюють політики заміщення на тому самому навантаженні: вищий коефіцієнт влучень для заданого обсягу пам'яті означає менше дорогих звернень до диска.