Linux Kernel (Ядро линукса) (часть 3)

Дерево приоритетного поиска

Дерево приоритетного поиска, применяемое в Linux 2.6, основано на структуре данных, впервые предложенной Эдвардом Маккрейтом (Edward McCreight) в 1985 г. для представления множества перекрывающихся интервалов. Дерево Маккрейта является гибридом кучи и сбалансированного дерева поиска, используется оно для выполнения запросов на множестве интервалов (например, какие интервалы содержатся в данном”) за время, прямо пропорциональное высоте дерева и количеству интервалов в ответе.

Каждый интервал в дереве приоритетного поиска соответствует узлу и характеризуется двумя индексами: базисным индексом, который соответствует на
чальной точке интервала, и индексом кучи, который соответствует конечной точке. Дерево приоритетного поиска фактически является деревом поиска по базисному индексу с дополнительным кучевым свойством, заключающимся в том, что индекс кучи узла не может быть меньше индексов кучи его потомков.
Дерево приоритетного поиска Linux отличается от структуры Маккрейта в двух важных аспектах. Во-первых, дерево Linux не всегда сбалансировано (алгоритм балансирования дорог, как в отношении памяти, так и времени). Во-вторых, дерево Linux адаптировано под хранение областей памяти, а не интервалов.

Каждую область памяти можно рассматривать как интервал страниц файла, идентифицируемый начальной позицией в файле (базисный индекс) и конечной позицией (индекс кучи). Однако области памяти обычно начинаются с одних и тех же страниц (как правило, со страницы с индексом 0), а оригинальное дерево Маккрейта, к сожалению, не может хранить интервалы, имеющие одинаковые начальные точки. В качестве половинчатого решения каждый узел дерева приоритетного поиска Linux был снабжен дополнительным индексом размера (отличным от базисного индекса и индекса кучи), который соответствует размеру области памяти в страницах минус один. Индекс размера позволяет программе, выполняющей поиск, различать области памяти, начинающиеся с одной позиции в файле.

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

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

Слева на рисунке показаны семь областей памяти, покрывающие первые шесть страниц файла, и для каждого интервала приведены базисный индекс, индекс размера и индекс кучи. Справа нарисовано соответствующее дерево приоритетного поиска. Обратите внимание, что ни один потомок не имеет индекс кучи, превышающий индекс кучи его родителя. Кроме того, заметьте, что базисный индекс левого потомка любого узла никогда не превышает базисный индекс правого потомка; в случае равенства базисных индексов узлы упорядочиваются по индексу размера. Предположим, что алгоритм утилизации страничных кадров должен получить все области памяти, содержащие страницу с индексом 5. Алгоритм поиска начинает работу с корня (0,5,5): поскольку соответствующий интервал включает эту страницу, получена первая область памяти. Затем алгоритм переходит к левому потомку (0,4,4) корня и сравнивает индекс кучи (4) с индексом страницы: поскольку индекс кучи меньше, интервал не содержит эту страницу; более того, благодаря кучевому свойству дерева приоритетного поиска, ни один потомок этого узла не может содержать данную страницу. Тогда алгоритм переходит к правому потомку (2,3,5) корня. Соответствующий интервал содержит страницу, и, следовательно, получена вторая область памяти. Затем алгоритм посещает узлы- потомки (1,2,3) и (2,0,2), но обнаруживает, что ни один из них не содержит страницу.

Из-за недостатка места мы не сможем подробно описать структуры и функции, реализующие деревья приоритетного поиска Linux. Мы лишь упомянем, что узел дерева приоритетного поиска представляется структурой prio tree node, КОТОрая встроена В ПОЛе shared.prio tree node каждого деск- риптора области памяти. Структура данных shared.vm set применяется (как альтернатива структуре shared.prio tree node) для занесения дескриптора области памяти в дублирующий список узла дерева приоритетного поиска. Узлы этого дерева могут быть вставлены или удалены с помощью функций vma_prio_tree_insert И vma_prio_tree_remove . Обе ОНИ Принимают В качестве параметров адрес дескриптора области памяти и адрес корня дерева приоритетного поиска. Запросы к дереву выполняются с помощью макроса vma prio tree foreach, который реализует цикл по всем дескрипторам областей памяти, содержащим хотя бы одну страницу в указанном диапазоне линейных адресов.