Алгоритм восстановления фрейма страницы ( PFRA ) в ядре Linux является довольно сложным и использует несколько эвристик для решить, какую страницу выселить. Фактическое решение основано на многих факторах, но следующие два выделяются.
1. Списки последних использованных (LRU)
Linux делит память на различные зоны памяти , каждая зона имеет дескриптор зоны, и этот дескриптор наряду с другими хранилищами вещей ссылки на два очень важных списка, а именно активные и неактивные .
Активный список содержит страницы, к которым недавно обращались, а неактивный список - страницы, к которым не обращались в течение некоторого времени. Различные рамки страницы перемещаются из одного списка в другой и из списков в зависимости от шаблонов доступа.
2. Флаги дескриптора страницы
, следующие за двумя флагами в дескрипторе страницы, позволяют ядру определить, включена ли данная страница в один из приведенных выше списков.
PG_lru - страница находится в списке активных или неактивных страниц
PG_active - страница находится в списке активных страниц
Понимание Linux Ядра утверждает следующее, когда описывает, как PFRA фактически использует вышеуказанную информацию.
Основная идея алгоритма LRU заключается в том, чтобы связать счетчик, хранящий возраст страницы, с каждой страницей в ОЗУ, то есть интервал времени, прошедший с момента последнего доступа к странице. Этот счетчик позволяет PFRA восстанавливать только самую старую страницу любого процесса. Некоторые компьютерные платформы обеспечивают сложную поддержку алгоритмов LRU; † к сожалению, процессоры 80 × 86 не предлагают такую аппаратную функцию, поэтому ядро Linux не может полагаться на счетчик страниц, который отслеживает возраст каждой страницы. Чтобы справиться с этим ограничением, Linux использует бит доступа, включенный в каждую запись таблицы страниц, который автоматически устанавливается аппаратным обеспечением при доступе к странице; кроме того, возраст страницы представлен положением дескриптора страницы в одном из двух разных списков «Наименее недавно использованные (LRU)».