Структура таблиці сторінок

Організація таблиці сторінок – один з ключових елементів відображення адрес в сторінковій і сегментно-сторінковій схемах. Розглянемо структуру таблиці сторінок для випадку сторінкової організації детальніше.

Отже, віртуальна адреса складається з віртуального номера сторінки і зсуву. Номер запису в таблиці сторінок відповідає номеру віртуальної сторінки. Розмір запису коливається від системи до системи, але найчастіше він складає 32 бита. З цього запису в таблиці сторінок знаходиться номер кадру для даної віртуальної сторінки, потім додається зсув і формується фізична адреса. Окрім цього запис в таблиці сторінок містить інформацію про атрибути сторінки. Це біти присутності і захисту (наприклад, 0 – read/write, 1 – read only...). Також можуть бути вказані: біт модифікації, який встановлюється, якщо вміст сторінки модифікований, і дозволяє контролювати необхідність перезапису сторінки на диск; біт посилання, який допомагає виділити маловикористовувані сторінки; битий, що вирішує кешування, і інші керівники биті. Відмітимо, що адреси сторінок на диску не є частиною таблиці сторінок.

Основну проблему для ефективної реалізації таблиці сторінок створюють великі розміри віртуальних адресних просторів сучасних комп'ютерів, які зазвичай визначаються розрядністю архітектури процесора. Найпоширенішими на сьогодні є 32-розрядні процесори, що дозволяють створювати віртуальні адресні простори розміром 4 Гбайт (для 64-розрядних комп'ютерів ця величина дорівнює 264 байт). Крім того, існує проблема швидкості відображення, яка вирішується за рахунок використання так званої асоціативної пам'яті (див. наступний розділ).

Підрахуємо зразковий розмір таблиці сторінок. У 32-бітовому адресному просторі при розмірі сторінки 4 Кбайт (Intel) отримуємо 232/212=220, тобто приблизно мільйон сторінок, а в 64-бітовому і того більш. Таким чином, таблиця повинна мати приблизно мільйон рядків (entry), причому запис в рядку складається з декількох байтів. Відмітимо, що кожен процес потребує своєї таблиці сторінок (а у разі сегментно-сторінкової схеми бажано мати по одній таблиці сторінок на кожен сегмент).

Зрозуміло, що кількість пам'яті, що відводиться таблицям сторінок, не може бути таке велике. Для того, щоб уникнути розміщення в пам'яті величезної таблиці, її розбивають на ряд фрагментів. У оперативній пам'яті зберігають лише деякі, необхідні для конкретного моменту виконання фрагменти таблиці сторінок. Через властивість локальності число таких фрагментів відносно невелике. Виконати розбиття таблиці сторінок на частини можна по-різному. Найбільш поширений спосіб розбиття – організація так званої багаторівневої таблиці сторінок. Для прикладу розглянемо дворівневу таблицю з розміром сторінок 4 Кбайт, реалізовану в 32-розрядній архітектурі Intel.

Таблиця, що складається з 220 рядків, розбивається на 210 таблиць другого рівня по 210 рядків. Ці таблиці другого рівня об'єднані в загальну структуру за допомогою однієї таблиці першого рівня, що складається з 210 рядків. 32-розрядна адреса ділиться на 10-розрядне поле p1, 10-розрядне поле p2 і 12-розрядний зсув d. Поле p1 указує на потрібний рядок в таблиці першого рівня, поле p2 – другого, а поле d локалізує потрібний байт усередині вказаного сторінкового кадру (див. мал. 9.1).

Рис. 11.1. Приклад дворівневої таблиці сторінок

За допомогою всього лише однієї таблиці другого рівня можна охопити 4 Мбайт (4 Кбайт x 1024) оперативної пам'яті. Таким чином, для розміщення процесу з великим об'ємом займаної пам'яті досить мати в оперативній пам'яті одну таблицю першого рівня і декілька таблиць другого рівня. Очевидно, що сумарна кількість рядків в цих таблицях багато менше 220. Такий підхід природним чином узагальнюється на три і більш за рівні таблиці.

Наявність декількох рівнів, природно, знижує продуктивність менеджера пам'яті. Не дивлячись на те що розміри таблиць на кожному рівні підібрані так, щоб таблиця поміщалася цілком усередині однієї сторінки, звернення до кожного рівня – це окреме звернення до пам'яті. Таким чином, трансляція адреси може зажадати декількох звернень до пам'яті.

Кількість рівнів в таблиці сторінок залежить від конкретних особливостей архітектури. Можна привести приклади реалізації однорівневого (DEC PDP-11), дворівневого (Intel, DEC VAX), трирівневого (Sun SPARC, DEC Alpha) пейджинга, а також пейджинга із заданою кількістю рівнів (Motorola). Функціонування RISC-процессора MIPS R2000 здійснюється взагалі без таблиці сторінок. Тут пошук потрібної сторінки, якщо ця сторінка відсутня в асоціативній пам'яті, повинна узяти на себе ОС (так званий zero level paging).