Главная » Ядро Linux » Базисное дерево

0

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

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

Основной код  для  работы  с  базисными деревьями находится   в  файле   lib / radix-tree.с . Для  использования базисных  деревьев  необходимо подключить заголовочный файл   <linux/radix-tree.h> .

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

Для  ядер до серии  2.6 поиск  в страничном кэше  не  выполнялся с помощью базисных  деревьев.  Вместо  этого  поддерживалась  глобальная  хеш-таблица  всех  страниц памяти  в системе.  Специальная  хеш-функция возвращала  двухсвязный  список  значений,  связанных  с одним  значением  ключа.  Если  нужная  страница  находится  в кэше, то один  из элементов  этого  списка  соответствует этой  нужной  странице.  Если  страница  в кэше  отсутствует, то хеш-функция возвращает значение  NULL.

Использование  глобальной хеш-таблицы приводило  к  четырем основным  проблемам.

• Хеш-таблица защищалась  одной   глобальной  блокировкой.  Количество  конфликтов  при  захвате этой  блокировки  было достаточно  большим  даже  для  не очень  больших  машин.  В результате  страдала  производительность.

• Размер  хеш-таблицы был  большим, потому  что  в ней  содержалась  информация обо  всех  страницах памяти в страничном кэше,  в то  время  как  важными являются лишь страницы,  связанные  с одним конкретным файлом.

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

• Хеш-таблица  требовала больше  памяти,  чем другие возможные  решения.

Применение   в ядрах серии  2.6 страничного  кэша  на  основании  базисных  деревьев  позволило решить  эти  проблемы.

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

По теме:

  • Комментарии