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

Алгоритм "buddy-система"

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

Существует два основных способа борьбы с внешней фрагментацией:

- применение электронной схемы управления памятью для отображения групп несмежных свободных страничных кадров в непрерывные интервалы линейных адресов;
- разработка подходящей техники отслеживания существующих блоков из свободных смежных страничных кадров, которая позволяла бы, по возможности, избегать разбиения большого свободного блока ради удовлетворения запроса на меньший блок.
Второй подход является более предпочтительным для ядра по трем веским причинам:
- в некоторых случаях смежные страничные кадры действительно необходимы, потому что недостаточно иметь смежные линейные адреса для удовлетворения запроса. Типичным примером является запрос на память для буферов, назначаемых процессору DMA Поскольку большинство таких процессоров игнорирует электронную схему управления страницами и напрямую обращается к адресной шине при передаче нескольких секторов диска за одну операцию ввода/вывода, запрошенные буферы должны находиться в смежных страничных кадрах;
- даже если выделение смежных страничных кадров не является строго необходимым, оно имеет то достоинство, что оставляет неизменными таблицы страницы ядра. Почему их нежелательно изменять частые изменения Таблицы Страниц увеличивают среднее время обращения к памяти, потому что из-за них процессору приходится очищать содержимое TLB-буферов;
- ядро может обращаться к большим непрерывным фрагментам физической памяти, пользуясь 4-мегабайтными страницами. Это сокращает промахи мимо TLB-буфера, чем значительно уменьшает среднее время обращения к памяти.

Подход к решению проблемы внешней фрагментации, принятый в Linux, основан на хорошо известном алгоритме buddy-системы. Все свободные страничные кадры собираются в 11 списков, содержащих блоки, состоящие, соответственно, из 1,2, 4, 8, 16, 32, 64, 128, 256, 512 и 1024 смежных страничных кадров. Самый "крупный” запрос на 1024-страничных кадра соответствует непрерывному фрагменту памяти размером 4 Мбайт. Физический адрес первого страничного кадра в блоке кратен размеру группы. Например, начальный адрес блока из 16-страничных кадров кратен 16 х 212 (212 = 4096 является обычным размером страницы).

Мы объясним работу алгоритма на простом примере.

Предположим, что выдан запрос на группу из 256 смежных страничных кадров (то есть на один мегабайт памяти). Вначале алгоритм проверяет наличие свободного блока в списке блоков из 256-страничных кадров. Если такого блока нет, алгоритм ищет более крупный, 512-кадровый блок в соответствующем списке. Если такой блок найден, ядро выделяет 256 из 512-стра- ничных кадров для удовлетворения запроса и переносит оставшиеся 256-страничных кадров в список, содержащий 256-кадровые блоки. Если же свободного блока из 512-страничных кадров тоже нет, ядро ищет следующий более крупный блок (из 1024 кадров). Если его найти удалось, ядро выделяет 256 из 1024-страничных кадров для удовлетворения запроса, переносит первые 512 из оставшихся 768-страничных кадров в список 512-кадровых блоков, а остальные 256 кадров— в список 256-кадровых блоков. Если список 1024-кадровых блоков оказался пустым, алгоритм завершается и сигнализирует об ошибке.

Обратная операция, освобождение блоков страничных кадров, дала название этому алгоритму. Ядро пытается слить пары buddy-блоков размера b в один блок размера 2Ъ. Два блока считаются buddy-блоками (от англ. buddy” — приятель), если:
- оба блока имеют одинаковый размер
- они являются смежными физически;
- физический адрес первого страничного кадра в первом блоке кратен 2 х Ъ х 212.
Алгоритм работает итеративно. Если ему удается слить освобожденные блоки, он удваивает Ъ и пытается создать блоки большего размера.