Списки и деревья областей памяти

Списки и деревья областей памяти

Как уже рассказывалось, к областям памяти осуществляется доступ с помощью двух структур данных дескриптора памяти: полей mmap и mm_rb. Эти две структуры данных независимо друг от друга указывают на все области памяти, связанные с данным дескриптором памяти. Они содержат указатели на одни и те же структуры vm_area_struct, просто эти указатели связаны друг с другом по-разному.

Первый контейнер, поле mmap, объединяет все объекты областей памяти в односвязный список. Структуры vm_area_struct объединяются в список с помощью своих полей vm_next. Области памяти отсортированы в порядке увеличения адресов (от наименьшего и до наибольшего). Первой области памяти соответствует структура vm_area_struct, на которую указывает само поле mmap. Указатель на самую последнюю структуру равен значению NULL.

Второе поле, mm_rb, объединяет все объекты областей памяти в красно-черное (red-black) дерево. На корень дерева указывает поле mm_rb, а каждая структура vm_area_struct присоединяется к дереву с помощью поля vm_rb.

Красно-черное дерево — это один из типов бинарного дерева. Каждый элемент красно-черного дерева называется узлом. Начальный узел является корнем дерева. Большинство узлов имеет два дочерних узла: левый дочерний узел и правый дочерний узел. Некоторые узлы имеют всего один дочерний узел, и, наконец, узлы, которые не имеют дочерних, называются листьями. Для любого узла все элементы дерева, которые находятся слева от данного узла, всегда меньше по своему значению, чем значение данного узла, а все элементы дерева, которые находятся справа от некоторого узла, всегда больше по значению, чем значение этого узла. Более того, каждому узлу присвоен цвет (красный или черный, отсюда и название этого типа деревьев) в соответствии со следующими двумя правилами: дочерние элементы красного узла являются черными и любой путь по дереву от узла к листьям должен содержать одинаковое количество черных узлов. Корень дерева всегда красный. Поиск, вставка и удаление элементов из такого дерева требуют количество операций порядка О(log(n)).

Связанный список используется, когда необходимо пройти по всем узлам. Красно- черное дерево используется, когда необходимо найти определенную область памяти адресного пространства. Таким образом, ядро использует избыточные структуры данных для обеспечения оптимальной производительности независимо от того, какие операции выполняются с областями памяти.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Закрепление областей

Из книги Excel. Мультимедийный курс автора Мединов Олег

Закрепление областей Предположим, что вы работаете с большой таблицей. В процессе работы вам приходится часто использовать полосы прокрутки, чтобы ввести данные в различные ячейки. При этом заголовки столбцов (самые различные, например: Товар, Цена, Количество,


Разделение окна на несколько областей

Из книги Word 2007.Популярный самоучитель автора Краинский И

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


2.2.7.1 . Зеркалирование дисковых областей

Из книги Руководство администратора баз данных Informix. автора Кустов Виктор

2.2.7.1 . Зеркалирование дисковых областей Зеркалирование в INFORMIX-OnLine DS - это дублирование связной дисковой области, выделенной под базу данных, на такую же по размеру область. Исходная область называется первичной, а ее копия - зеркальной. Цели, для которых применяется


Создание рабочих областей для собраний из Outlook 2007

Из книги Microsoft Windows SharePoint Services 3.0. Русская версия. Главы 9-16 автора Лондер Ольга

Создание рабочих областей для собраний из Outlook 2007 При создании запроса на собрание в Outlook 2007 можно также создать узел рабочей области для собраний или связать собрание с существующим узлом рабочей области. О рабочих областях для собраний рассказывалось в главе 8. Рабочие


Деревья - это списки и их элементы

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

Деревья - это списки и их элементы Класс дерева TREE - еще один яркий пример множественного наследования.Деревом называется иерархическая структура, составленная из узлов с данными. Обычно ее определяют так: "Дерево либо пусто, либо содержит объект, именуемый его корнем, с


У15.1 Окна как деревья

Из книги Программирование на языке Ruby [Идеология языка, теория и практика применения] автора Фултон Хэл

У15.1 Окна как деревья Класс WINDOW порожден от TREE [WINDOW]. Поясните суть родового параметра. Покажите, какое новое утверждение появится в связи с этим в инварианте


У15.7 Деревья

Из книги XSLT автора Хольцнер Стивен

У15.7 Деревья Согласно одной из интерпретаций, дерево - это рекурсивная структура, представляющая собой список деревьев. Замените приведенное в этой лекции описание класса TREE как наследника LINKED_LIST и LINKABLE новым вариантомclass TREE [G] inheritLIST [TREE [G]]feature ...endРасширьте это описание до


9.3. Деревья

Из книги Технология XSLT автора Валиков Алексей Николаевич

9.3. Деревья Я не увижу никогда, наверное, Поэму столь прекрасную как дерево. Джойс Килмер, «Деревья»[11] В информатике идея дерева считается интуитивно очевидной (правда, изображаются они обычно с корнем наверху, а листьями снизу). И немудрено, ведь в повседневной жизни мы


Создание областей

Из книги Разработка приложений в среде Linux. Второе издание автора Джонсон Майкл К.

Создание областей В версии 1.0 спецификации XSL у шаблонов страниц имелось пять областей (region). Центральная область, соответствующая основной части, телу страницы, называется областью тела (body region). Верхняя часть страницы, верхний колонтитул (header), называется передней


Создание встроенных областей:

Из книги КОМПАС-3D для студентов и школьников. Черчение, информатика, геометрия автора Большаков Владимир

Создание встроенных областей: <fo:inline> Как вы уже видели в главе 11, при помощи элемента <fo:inline> вы можете форматировать части текста, задавая для них задний фон, подчеркивая текст или заключая текст в границы. Элемент позволяет форматировать встроенную область из


Деревья

Из книги Разработка ядра Linux автора Лав Роберт

Деревья Прежде, чем мы приступим к рассмотрению типов узлов и отношений между ними, необходимо определиться с самой структурой дерева. Древовидная структура задает для своих элементов отношение ветвления, очень похожее на строение обычного дерева — есть корневой узел


13.2.3. Отмена отображения областей

Из книги автора

13.2.3. Отмена отображения областей После окончания отображения в памяти процесс может отменить отображение памяти с помощью munmap(). Это приводит к тому, что последующие доступы к этому адресу будут генерировать SIGSEGV (если только память не будет перераспределена) и сохраняет


13.2.4. Синхронизация областей памяти на диск

Из книги автора

13.2.4. Синхронизация областей памяти на диск Если для записи в файл используется карта памяти, модифицированные страницы памяти и файл будут в течение некоторого времени отличаться. Если процессу необходимо немедленно записать страницы на диск, для этого служит msync().#include


13.2.5. Блокировка областей памяти

Из книги автора

13.2.5. Блокировка областей памяти В Linux и многих других современных операционных системах для областей памяти можно организовать страничный обмен с диском (или отклонять, если их невозможно заменить каким-либо другим способом), когда возникает дефицит памяти. На


1.4.2. Штриховка замкнутых областей

Из книги автора

1.4.2. Штриховка замкнутых областей Штриховка замкнутых областей на чертежах в двумерных редакторах выполняется автоматически после задания границ и параметров штриховки. Границы штриховки, как правило, можно задавать вручную и (или) автоматически. Автоматический способ


Флаги областей VMA

Из книги автора

Флаги областей VMA Поле флагов vm_flags содержит битовые флаги, которые определены в файле <linux/mm.h>. Они указывают особенности поведения и содержат описательную информацию о страницах памяти, которые входят в данную область памяти. В отличие от прав доступа, которые связаны