Організація захисту пам'яті процесу за допомогою біта valid-invalid ілюструється на рис. 16.8.
збільшити зображення
Мал. 16.8. Біт valid-invalid в таблиці сторінок.
Структура таблиці сторінок
Ієрархічні таблиці сторінок. Таблиці сторінок в операційних системах можуть бути по-різному організовані, при збереженні загальних принципів їх використання, описаних раніше. Розглянемо далі три основних способи організації таблиць сторінок - ієрархічні таблиці сторінок, хешировать таблиці сторінок і інвертовані таблиці сторінок.
Організація дворівневих таблиць сторінок зображена на рис. 16.9.
Мал. 16.9. Організація дворівневих таблиць сторінок.
Хешировать таблиці сторінок
Структура таблиці сторінок, описана в даному розділі, базується на понятті хеш-функції (hash function) [24 (запиту, не знайдено)] - целочисленной функції hash, визначеної на елементах s деякого простору пошуку S (рядках, великих числах і ін.) І приймаючої значення з відрізка [0, H-1] де H - натуральне число. Загальна ідея пошуку за допомогою хеш-функцій полягає в наступному: простір пошуку розбивається на H непересічних підмножин (списків) Sh, в кожному з яких зберігаються елементи, що мають однакове значення хеш-функції, рівне h. Таким чином, застосування хеш-функції дозволяє скоротити пошук в середньому в H раз: при пошуку елемента s спочатку обчислюємо hash (s), а потім виконуємо пошук тільки в списку Shash (s) Для полегшення доступу до хеш-списками зберігається також хеш-зміст - таблиця, що індексується значенням хеш-функції, кожен елемент якої містить посилання на початок відповідного списку.
збільшити зображення
Мал. 16.11. Хешировать таблиці сторінок.
Інвертовані таблиці сторінок
збільшити зображення
Мал. 16.12. Інвертовані таблиці сторінок.