A5. Заміщення сторінок

просунутийспирається на модуль 11, модуль 12

Мета

У модулі 12 алгоритми заміщення описані словами. Тут вони перетворяться на числа, зокрема на один результат, який суперечить здоровому глузду: для FIFO більше пам’яті може означати більше сторінкових винятків.

Відтворити аномалію Беладі власними руками значно переконливіше, ніж прочитати про неї.

Що має вийти

./pagesim --frames 3 --algo fifo trace.txt
./pagesim --frames 3 --algo all  trace.txt

Вхід — траса звернень: номери сторінок, по одному на рядок. Порожні рядки й рядки з # ігноруються.

Вихід — рядок на алгоритм: назва, кількість винятків, кількість влучань, розділені пробілами. Автоперевірка спирається саме на цей формат.

fifo     9  3
lru     10  2
clock   10  2
optimal  7  5

Етапи

1. FIFO та оптимальний.

   Оптимальний потребує знання майбутнього — і саме тому реалізується легко: уся траса вже перед вами. Він потрібен як нижня межа, з якою порівнюється решта.

2. LRU.

   Точний LRU тут реалізувати можна, бо ви симулятор, а не апаратура. Зверніть увагу, скільки роботи це вимагає на кожне звернення — і чому в реальних системах так не роблять.

3. Годинниковий алгоритм.

   Кільце сторінок, біт звернення, стрілка. Порівняйте його результат з точним LRU: різниця має бути невеликою. Саме цей факт і виправдовує заміну LRU наближенням.

4. Аномалія Беладі.

   Знайдіть трасу, на якій FIFO з чотирма фреймами дає більше винятків, ніж з трьома. Класична: 1 2 3 4 1 2 5 1 2 3 4 5.

   Перевірте, що на LRU і на оптимальному аномалії немає — це і є практична різниця між стековими алгоритмами й нестековими.

5. Робочий набір.

   Побудуйте графік «кількість фреймів → винятки» для кожного алгоритму. На реальному трасі буде помітне коліно: після певної точки додавання пам’яті майже нічого не дає. Це і є розмір робочого набору.

6. Справжня траса.

   Згенеруйте трасу з реальної програми, а не випадкову. Найпростіше — valgrind --tool=lackey --trace-mem=yes і взяти старші біти адрес. Порівняйте результати з випадковою трасою: різниця показує, наскільки все тримається на локальності (модуль 2).

Випадкова траса нічого не доводить

На рівномірно випадкових зверненнях усі алгоритми дають майже однаковий результат — передбачати нема чого. Якщо ваші чотири алгоритми показали близькі числа, найімовірніше проблема не в них, а в трасі.

Автоперевірка

Перевірка лежить в архіві з файлами курсу, і команди нижче виконуються з розпакованого каталогу.

cd labs/a5-page-replacement
./check.sh ./pagesim

Перевірка ганяє траси з наперед відомими відповідями, включно з класичною послідовністю Беладі — і окремо контролює, що на LRU аномалія не відтворюється.

Часті помилки

Перше завантаження не рахується винятком. Рахується. Холодні промахи теж є винятками, і без них ваші числа не збіжаться з жодним підручником.

Годинниковий не скидає біт. Тоді він вироджується у FIFO. Стрілка мусить скидати біт у тих сторінок, які пропускає.

Оптимальний дивиться на все майбутнє. Достатньо знайти найближче наступне звернення для кожної сторінки, що зараз у кадрах.

Аномалія «не відтворюється». Перевірте, чи у вас справді FIFO, а чи ви випадково реалізували LRU. Якщо звернення до вже завантаженої сторінки пересуває її в кінець черги, це вже не FIFO.

Далі, якщо цікаво

Додати другий шанс із двома бітами (звернення + зміни), як у Linux, і подивитися, наскільки він ближчий до оптимального за звичайний годинниковий.