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

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

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

Природне вирішення проблеми прискорення – забезпечити комп'ютер апаратним пристроєм для відображення віртуальних сторінок у фізичних без звернення до таблиці сторінок, тобто мати невелику, швидку кеш-пам'ять, що зберігає необхідну на даний момент частину таблиці сторінок. Цей пристрій називається асоціативною пам'яттю, іноді також використовують термін буфер пошуку трансляції (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 з 256 Мбайт оперативної пам'яті потрібна таблиця розміром 64 Кбайт рядків.

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