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

Описание алгоритма PFRA

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

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

К сожалению, поиск хорошего алгоритма утилизации страничных кадров носит, в основном, эмпирический характер и имеет слабые теоретические обоснования. Ситуация в какой-то степени аналогична оценке факторов, определяющих динамический приоритет процесса: главная цель — подобрать параметры так, чтобы была достигнута высокая производительность системы, и не искать объяснений, почему все работает хорошо. Нередко разработчики руководствуются принципом давайте попробуем и посмотрим, что получится”. Неприятным побочным эффектом подобного эмпирического проектирования является быстрое изменение кода. Учитывая вышесказанное, мы не можем гарантировать, что алгоритм утилизации памяти, который мы собираемся описать (и который применяется в Linux 2.6.11), будет официально принятым алгоритмом в последней версии ядра Linux 2.6 в момент, когда вы будете читать эту книгу. Впрочем, общие идеи и основные эвристические правила, описанные здесь, должны остаться неизмененными.

Бывает, что за деревьями не видно леса. Поэтому мы вначале представим несколько общих правил, принятых в алгоритме PFRA. Эти правила встроены в функции, которые будут описаны далее в этой главе.

- В первую очередь освобождать безвредные” страницы— страницы кэшей диска и памяти, на которые не ссылается ни один процесс, должны утилизироваться раньше страниц, принадлежащих адресным пространствам процессов режима пользователя, ведь в первом случае утилизация страничного кадра может быть выполнена без модификации записи в Таблице Страниц. Как мы увидим в разд. "Списки давно неиспользуемых
страниц (LRU)” далее в этой главе, это правило до некоторой степени смягчается введением фактора тенденции к выгрузке”.
- Сделать все страницы процесса в режиме пользователя утилизируемыми — если не принимать во внимание заблокированные страницы, алгоритм PFRA должен быть в состоянии украсть” любую страницу процесса, работающего в режиме пользователя. Таким образом, процессы, которые спят” слишком долго, постепенно растеряют все свои страничные кадры.
- Утилизировать совместно используемый страничный кадр за счет одновременного стирания всех записей в таблице страниц, ссылающихся на него — когда алгоритм PFRA пытается освободить страничный кадр, совместно используемый несколькими процессами, он стирает все записи в таблице страниц, ссылающиеся на этот кадр, и только потом утилизирует его.
- Утилизировать только неиспользуемые” страницы— алгоритм PFRA применяет упрощенную версию алгоритма замещения давно не используемых элементов, когда делит страницы на используемые и неиспользуемые2. Если к странице продолжительное время не обращались, то вероятность, что процесс обратится к ней в ближайшем будущем, мала, и страницу можно считать неиспользуемой. С другой стороны, если последнее обращение к странице произошло недавно, то вероятность повторного обращения велика, и страницу следует считать используемой. Алгоритм PFRA утилизирует только неиспользуемые страницы. Это еще одно проявление принципа локальности, положенная в основу алгоритма давно не используемых элементов” состоит в том, чтобы связать с каждой страницей в оперативной памяти счетчик возраста, т. е. интервал времени с последнего обращения к этой странице. Такой счетчик позволит алгоритму PFRA утилизировать только самые старые страницы любого процесса. Некоторые компьютерные платформы предоставляют сложную поддержку алгоритмам давно не используемых элементов”3. К сожалению, процессоры 80x86 такой аппаратной возможности не имеют, и ядро Linux не может полагаться на счетчик, отсчитывающий возраст каждой страницы. Чтобы выйти из положения, Linux использует бит Accessed, имеющийся у каждой записи Таблицы Страниц. Этот бит автоматически устанавливается аппаратной частью при обращении к странице. Кроме того, возраст страницы
представлен позицией ее дескриптора в одном из двух списков Итак, алгоритм утилизации страничных кадров является комбинацией нескольких эвристик:
- тщательного определения порядка, в котором проверяются кэши;
- упорядочения страниц по возрасту (давно не используемые страницы должны освобождаться раньше страниц, использованных недавно);
- разграничения страниц по состоянию (например, ”не грязные” страницы являются более подходящими кандидатами, чем грязные”, поскольку их не нужно записывать на диск).