Асоціативна пам'ять

Пошук номера кадра, відповідного до потрібної сторінки, у багаторівневій таблиці сторінок вимагає декількох звертань до основної пам'яті, тому займає багато часу. У деяких випадках така затримка неприпустима. Проблема прискорення пошуку зважується на рівні архітектури комп'ютера.

У відповідності із властивістю локальності більшість програм протягом деякого проміжку часу звертаються до невеликої кількості сторінок, тому активно використовується тільки невелика частина таблиці сторінок.

Природній розв'язок проблеми прискорення – постачити комп'ютер апаратним пристроєм для відображення віртуальних сторінок у фізичні без звертання до таблиці сторінок, тобто мати невелику, швидку кеш-пам'ять, що зберігає необхідну на даний момент частина таблиці сторінок. Цей пристрій називається асоціативною пам'яттю, іноді також уживають термін буфер пошуку трансляції (translation lookaside buffer – TLB).

Один запис таблиці в асоціативній пам'яті (один вхід) містить інформацію про одну віртуальну сторінку: її атрибути й кадр, у якому вона перебуває. Ці поля в точності відповідають полям у таблиці сторінок.

Тому що асоціативна пам'ять містить тільки деякі із записів таблиці сторінок, кожний запис в TLB повинна включати поле з номером віртуальної сторінки. Пам'ять називається асоціативної, тому що в ній відбувається одночасне порівняння номера відображуваної віртуальної сторінки з відповідним полем у всіх рядках цієї невеликої таблиці. Тому даний вид пам'яті досить дорого коштує. У рядку, полі віртуальної сторінки якої збіглося із шуканим значенням, перебуває номер сторінкового кадра. Звичайне число записів в TLB від 8 до 4096. Ріст кількості записів в асоціативній пам'яті повинен здійснюватися з урахуванням таких факторів, як розмір кэша основної пам'яті й кількості звертань до пам'яті при виконанні однієї команди.

Розглянемо функціонування менеджера пам'яті при наявності асоціативної пам'яті.

Спочатку інформація про відображення віртуальної сторінки у фізичну відшукується в асоціативній пам'яті. Якщо потрібний запис знайдений – усі нормально, за винятком випадків порушення привілеїв, коли запит на звертання до пам'яті відхиляється.

Якщо потрібний запис в асоціативній пам'яті отсутствует, відображення здійснюється через таблицю сторінок. Відбувається заміна однієї із записів в асоціативній пам'яті знайденим записом з таблиці сторінок. Тут ми зустрічаємося із традиційної для будь-якого кэша проблемою заміщення ( а саме яку із записів у кэше необхідно змінити). Конструкція асоціативної пам'яті повинна організовувати записи таким чином, щоб можна було ухвалити рішення щодо того, яка зі старих записів повинна бути вилучена при внесенні нових.

Число вдалих пошуків номера сторінки в асоціативній пам'яті стосовно загального числа пошуків називається hit (збіг) ratio (пропорція, відношення). Іноді також використовується термін «відсоток влучень у кеш». Таким чином, hit ratio – частина посилань, яка може бути зроблена з використанням асоціативної пам'яті. Звертання до тим самим сторінок підвищує hit ratio. Чим більше hit ratio, тем менше середній час доступу до даних, що перебувають в оперативній пам'яті.

Припустимо, наприклад, що для визначення адреси у випадку кеш-промаху через таблицю сторінок необхідно 100 нс, а для визначення адреси у випадку кеш-влучення через асоціативну пам'ять – 20 нс. З 90% hit ratio середній час визначення адреси – 0,9x20+0,1x100 = 28 нс.

Цілком прийнятна продуктивність сучасних ОС доводить ефективність використання асоціативної пам'яті. Високе значення ймовірності знаходження даних в асоціативній пам'яті пов'язане з наявністю в даних об'єктивних властивостей: просторової й тимчасової локальності.

Необхідно звернути увагу на наступний факт. При перемиканні контексту процесів потрібно добитися того, щоб новий процес «не бачив» в асоціативній пам'яті інформацію, що ставиться до попереднього процесу, наприклад очищати її. Таким чином, використання асоціативної пам'яті збільшує час перемикання контексту.

Розглянута дворівнева (асоціативна пам'ять + таблиця сторінок) схема перетворення адреси являє яскравий приклад ієрархії пам'яті, заснованої на використанні принципу локальності, про що говорилося у введенні до попередньої лекції.

Інвертована таблиця сторінок

Незважаючи на багаторівневу організацію, зберігання декількох таблиць сторінок великого розміру як і раніше являють собою проблему. Її значення особливе актуально для 64-розрядних архитектур, де число віртуальних сторінок дуже велике. Варіантом розв'язку є застосування інвертованої таблиці сторінок (inverted page table). Цей підхід застосовується на машинах Powerpc, деяких робочих станціях Hewlett-Packard, IBM RT, IBM AS/400 і ряді інших.

У цій таблиці втримується по одному запису на кожний сторінковий кадра фізичної пам'яті. Суттєво, що досить однієї таблиці для всіх процесів. Таким чином, для зберігання функції відображення потрібна фіксована частина основної пам'яті, незалежно від розрядності архітектури, розміру й кількості процесів. Наприклад, для комп'ютера Pentium c 256 Мбайт оперативної пам'яті потрібна таблиця розміром 64 Кбайт рядків.

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