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

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

Мета

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

Після цієї роботи ви зможете:

реалізувати FIFO, LRU, годинниковий і оптимальний алгоритми і порахувати для кожного кількість винятків на заданій трасі;
відтворити аномалію Беладі на FIFO і пояснити, чому на LRU і на оптимальному вона неможлива;
пояснити, чому точний LRU не реалізують апаратно і чим його заміняє годинниковий алгоритм;
прочитати графік «кількість фреймів → винятки» і показати на ньому розмір робочого набору програми;
сказати, чому випадкова траса нічого не доводить і звідки взяти справжню.

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

Завдання

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

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

Що має вміти:

чотири алгоритми з іменами fifo, lru, clock і optimal; --algo all запускає всі разом;
вхід: траса звернень, номери сторінок по одному на рядок. Порожні рядки й рядки з # ігноруються;
вихід: рядок на алгоритм, у якому назва, кількість винятків і кількість влучань розділені пробілами. Автоперевірка знаходить рядок за назвою алгоритму і читає з нього друге поле;
перше завантаження сторінки рахується як виняток; фреймів може бути від одного і більше.

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

Чого робити не треба. Симулювати таблицю сторінок, TLB чи трансляцію адрес не потрібно: на вході вже номери сторінок. Швидкість симулятора не вимірюється, тож масив фреймів і лінійний пошук цілком підходять.

Обмеження. Перевірка запускає pagesim як виконуваний файл і читає лише вивід, тож мова реалізації на неї не впливає; на запуск є 20 секунд.

Що записати у звіт:

кількість винятків для FIFO, LRU й оптимального на трасі 1 2 3 4 1 2 5 1 2 3 4 5 з трьома і з чотирма фреймами;
скільки роботи на кожне звернення вимагає точний LRU у вашій реалізації і чому апаратура так не робить;
графік «кількість фреймів → винятки» для чотирьох алгоритмів на справжній трасі і коліно, яке ви вважаєте розміром робочого набору;
ті самі алгоритми на випадковій трасі й пояснення різниці.

Готово, коли:

./check.sh ./pagesim проходить усі тринадцять перевірок, включно з відтворенням аномалії Беладі на FIFO і її відсутністю на LRU;
графік побудовано на трасі зі справжньої програми;
у звіті є чотири пункти вище.

Перед початком

Прочитайте в модулі 12 розділи «Заміщення сторінок» (разом з Aside про аномалію Беладі) і «Робочий набір і трешинг», а в модулі 11 розділ «Запис таблиці сторінок», де описано біт звернення для годинникового алгоритму.
Розпакуйте архів курсу: перевірка лежить у labs/a5-page-replacement/check.sh, траси вона створює сама.
Для справжньої траси потрібен valgrind з інструментом lackey; у Vagrant-машині й після setup/provision.sh він уже є. Підійде будь-який Linux, зокрема контейнер і WSL2.

Етапи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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