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

Выделение и освобождение страничного слота

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

В Linux принят гибридный подход. Алгоритм всегда начинает с последнего выделенного страничного слота, если не возникает одна из следующих ситуаций:
- достигнут конец области подкачки;
- после последнего рестарта с начала области подкачки было выделено swapfile_cluster свободных страничных слотов (обычно 256).
Поле ciuster nr в дескрипторе swap info struct содержит количество выделенных свободных страничных слотов. Это поле сбрасывается в ноль, когда функция заново приступает к выделению с начала области подкачки. Поле ciuster next содержит индекс первого страничного слота, который нужно рассмотреть при следующем выделении10.

Чтобы ускорить процесс поиска свободных страничных слотов, ядро поддерживает в полях lowest bit и highest bit каждого дескриптора области подкачки самую свежую информацию. Эти поля определяют первый и последний страничные слоты, которые могут быть свободными. Иными словами, каждый страничный слот ниже lowest bit и выше highest bit наверняка занят.