Базисне дерево

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

Як було показано в попередньому розділі, пошук в сторінковому кеші виконується на підставі інформації обєкта address_spac e і значення зміщення Кожен обєкт address_spac e має своє унікальне базисне дерево (radix tree), яке зберігається в полі pagetree це один з типів бінарних дерев дозволяє виконувати дуже швидкий пошук необхідної сторінки тільки на підставі значення зміщення в файлі Функції пошуку в сторінковому кеші, такі як find_get_pag e () і radix_tree_looku p (), виконують пошук з використанням заданого дерева і заданого обєкта

Основний код для роботи з базисними деревами знаходиться у файлі lib / radix-treeс Для використання базисних дерев необхідно підключити заголовний файл

Стара хеш-таблиця сторінок

Для ядер до серії 26 пошук в сторінковому кеші не виконувався за допомогою базисних дерев Замість цього підтримувалася глобальна хеш-таблиця всіх сторінок памяті в системі Спеціальна хеш-функція повертала двохзвязної список значень, повязаних з одним значенням ключа Якщо потрібна сторінка знаходиться в кеші, то один з елементів цього списку відповідає цій потрібній сторінці Якщо сторінка в кеші відсутній, то хеш-функція повертає значення NULL

Використання глобальної хеш-таблиці призводило до чотирьох основних проблем

• Хеш-таблиця захищалася однієї глобальної блокуванням Кількість конфліктів при захопленні цього блокування було досить великим навіть для не дуже великих машин В результаті страждала продуктивність

• Розмір хеш-таблиці був великим, тому що в ній містилася інформація про всіх сторінках памяті в сторінковому кеші, у той час як важливими є лише сторінки, повязані з одним конкретним файлом

• Продуктивність у разі невдалого звернення в кеш (коли шукана сторінка памяті не знаходиться в кеші) падала через необхідність просматрі вать всі елементи списку, повязаного із заданим ключем

• Хеш-таблиця вимагала більше памяті, ніж інші можливі рішення

Застосування в ядрах серії 26 сторінкового кешу на підставі базисних дерев дозволило вирішити ці проблеми

Джерело: Лав, Роберт Розробка ядра Linux, 2-е видання : Пер з англ – М: ТОВ «ІД Вільямс »2006 – 448 с : Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*