Войти
В компьютерной операционной системе, которая использует разбиение на страницы для управления виртуальной памятью, алгоритмы замены страниц решают, какие страницы памяти следует выгружать, иногда это называется подкачкой, или записывать на диск, когда необходимо выделить страницу памяти. Замена страницы происходит, когда запрошенная страница отсутствует в памяти ( ошибка страницы ), а свободная страница не может использоваться для удовлетворения выделения, либо потому, что их нет, либо потому, что количество свободных страниц ниже некоторого порогового значения.
При повторном обращении к странице, которая была выбрана для замены и выгружена, она должна быть выгружена (считана с диска), что предполагает ожидание завершения ввода-вывода. Это определяет качество алгоритма замены страниц: чем меньше время ожидания загрузки страниц, тем лучше алгоритм. Алгоритм замены страниц смотрит на ограниченную информацию о доступах к страницам, предоставляемую оборудованием, и пытается угадать, какие страницы следует заменить, чтобы минимизировать общее количество пропусков страниц, при этом уравновешивая это затратами (основное хранилище и время процессора) сам алгоритм.
Проблема замены страниц - это типичная онлайн-проблема с точки зрения конкурентного анализа в том смысле, что известен оптимальный детерминированный алгоритм.
Алгоритмы замены страниц были горячей темой исследований и дискуссий в 1960-х и 1970-х годах. Это в основном закончилось разработкой сложных LRU- аппроксимаций (реже использовавшихся в последнее время) и алгоритмов рабочих наборов. С тех пор некоторые базовые предположения, сделанные традиционными алгоритмами замены страниц, были признаны недействительными, что привело к возобновлению исследований. В частности, следующие тенденции в поведении базового оборудования и программного обеспечения пользовательского уровня повлияли на производительность алгоритмов замены страниц:
Требования к алгоритмам замены страниц изменились из-за различий в архитектурах ядра операционной системы. В частности, большинство современных ядер ОС имеют унифицированную виртуальную память и кеши файловой системы, что требует от алгоритма замены страниц выбора страницы среди страниц как виртуальных адресных пространств пользовательских программ, так и кэшированных файлов. Последние страницы обладают определенными свойствами. Например, они могут быть заблокированы или могут иметь требования к порядку записи, налагаемые журналированием. Более того, поскольку цель замены страницы - минимизировать общее время ожидания памяти, она должна учитывать требования к памяти, налагаемые другими подсистемами ядра, которые выделяют память. В результате замена страниц в современных ядрах ( Linux, FreeBSD и Solaris ) имеет тенденцию работать на уровне распределителя памяти ядра общего назначения, а не на более высоком уровне подсистемы виртуальной памяти.
Алгоритмы замены могут быть локальными или глобальными.
Когда процесс вызывает сбой страницы, алгоритм замены локальной страницы выбирает для замены некоторую страницу, которая принадлежит тому же процессу (или группе процессов, совместно использующих раздел памяти ). Алгоритм глобальной замены позволяет выбрать любую страницу в памяти.
Замена локальной страницы предполагает некоторую форму разделения памяти, которая определяет, сколько страниц должно быть назначено данному процессу или группе процессов. Наиболее популярные формы разбиения - это алгоритмы фиксированного разбиения и сбалансированного набора, основанные на модели рабочего набора. Преимущество замены локальной страницы заключается в ее масштабируемости: каждый процесс может обрабатывать свои сбои страниц независимо, что приводит к более стабильной производительности этого процесса. Однако глобальная замена страниц более эффективна для всей системы.
Современные компьютеры общего назначения и некоторые встроенные процессоры поддерживают виртуальную память. У каждого процесса есть собственное виртуальное адресное пространство. Таблицы страниц отображает подмножество процесса виртуальных адресов в физические адреса. Кроме того, в большинстве архитектур таблица страниц содержит бит «доступа» и бит «грязный» для каждой страницы в таблице страниц. ЦП устанавливает бит доступа, когда процесс читает или записывает память на этой странице. ЦП устанавливает грязный бит, когда процесс записывает память на этой странице. Операционная система может изменять биты доступа и грязные биты. Операционная система может обнаруживать доступ к памяти и файлам следующими способами:
readи writeв POSIX.Большинство алгоритмов замены просто возвращают в качестве результата целевую страницу. Это означает, что если целевая страница загрязнена (то есть содержит данные, которые должны быть записаны в стабильное хранилище, прежде чем страница может быть восстановлена), должен быть инициирован ввод-вывод для отправки этой страницы в стабильное хранилище (для очистки страницы). На заре виртуальной памяти время, затрачиваемое на очистку, не представляло особого беспокойства, поскольку виртуальная память впервые была реализована в системах с полнодуплексными каналами для стабильного хранилища, а очистка обычно перекрывалась с разбиением по страницам. С другой стороны, современное массовое оборудование не поддерживает полнодуплексную передачу, и очистка целевых страниц становится проблемой.
Чтобы справиться с этой ситуацией, применяются различные политики предварительной очистки. Предварительная очистка - это механизм, который запускает ввод-вывод на грязных страницах, которые (вероятно) скоро будут заменены. Идея состоит в том, что к тому времени, когда предварительно очищенная страница будет фактически выбрана для замены, ввод-вывод завершится и страница будет чистой. Предварительная очистка предполагает, что можно определить страницы, которые будут заменены в следующий раз. Слишком активная предварительная очистка может тратить впустую пропускную способность ввода-вывода из-за написания страниц, которые удается повторно загрязнить перед выбором для замены.
Некоторые системы используют подкачку по запросу - ожидание фактического запроса страницы перед ее загрузкой в ОЗУ.
Другие системы пытаются уменьшить задержку, угадывая, какие страницы не в ОЗУ, скорее всего, понадобятся в ближайшее время, и предварительно загружая такие страницы в ОЗУ до того, как эта страница будет запрошена. (Это часто происходит в сочетании с предварительной очисткой, которая определяет, какие страницы в настоящее время в ОЗУ вряд ли понадобятся в ближайшее время, и предварительно записывает их в хранилище).
Когда происходит сбой страницы, системы «упреждающего пейджинга» вводят не только страницу, на которую указывает ссылка, но и следующие несколько последовательных страниц (аналогично входной очереди предварительной выборки в ЦП).
Механизм предварительной выборки подкачки идет еще дальше в загрузке страниц (даже если они не являются последовательными), которые, вероятно, вскоре понадобятся.
Задача (h, k) -пейджинга является обобщением модели проблемы пейджинга: пусть h, k - положительные целые числа такие, что. Мы измеряем производительность алгоритма с размером кэша относительно теоретически оптимального алгоритма замены страницы. Если, мы предоставляем оптимальный алгоритм замены страниц с строго меньшими ресурсами.
Задача (h, k) -пейджинга - это способ измерить, как работает онлайн-алгоритм, сравнивая его с производительностью оптимального алгоритма, в частности, отдельно параметрируя размер кэша онлайн-алгоритма и оптимального алгоритма.
Алгоритмы маркировки - это общий класс алгоритмов разбиения на страницы. Для каждой страницы мы связываем ее с меткой. Изначально мы устанавливаем все страницы как неотмеченные. На этапе запросов страниц мы отмечаем страницу при первом запросе на этом этапе. Алгоритм маркировки - это такой алгоритм, который никогда не выгружает отмеченную страницу.
Если ALG - это алгоритм маркировки с размером кэша k, а OPT - оптимальный алгоритм с кешем размера h, где, то ALG является -конкурентным. Таким образом, каждый алгоритм оценки достигает конкурентоспособности.
LRU - это алгоритм маркировки, а FIFO - не алгоритм маркировки.
Алгоритм является консервативным, если в любой последовательной последовательности запросов, содержащей k или меньше различных ссылок на страницы, алгоритм вызовет k или меньше ошибок страниц.
Если ALG - консервативный алгоритм с размером кэша k, а OPT - оптимальный алгоритм с размером кэша, то ALG является -конкурентным. Таким образом, любой консервативный алгоритм достигает -конкурентоспособности.
LRU, FIFO и CLOCK - консервативные алгоритмы.
Существует множество алгоритмов замены страниц:
Теоретически оптимальный алгоритм замены страницы (также известный как OPT, алгоритм замены ясновидящего или оптимальная политика замены страницы Белади ) - это алгоритм, который работает следующим образом: когда страницу необходимо заменить, операционная система заменяет страницу, чье следующее использование произойдет дальше всего в будущем. Например, страница, которая не будет использоваться в течение следующих 6 секунд, будет заменена страницей, которая будет использоваться в течение следующих 0,4 секунды.
Этот алгоритм не может быть реализован в операционной системе общего назначения, потому что невозможно надежно вычислить, сколько времени пройдет до того, как страница будет использоваться, за исключением случаев, когда все программное обеспечение, которое будет запускаться в системе, либо известно заранее и поддается статический анализ его шаблонов ссылок на память или только класс приложений, позволяющих анализировать во время выполнения. Несмотря на это ограничение, существуют алгоритмы, которые могут обеспечивать почти оптимальную производительность - операционная система отслеживает все страницы, на которые ссылается программа, и использует эти данные для принятия решения о том, какие страницы следует заменять при последующих запусках. Этот алгоритм может предложить почти оптимальную производительность, но не при первом запуске программы и только в том случае, если шаблон обращения к памяти программы относительно постоянен при каждом запуске.
Анализ проблемы пейджинга также проводился в области онлайн-алгоритмов. Эффективность рандомизированных онлайн-алгоритмов для задачи разбиения на страницы измеряется с помощью амортизированного анализа.
Алгоритм замены неиспользованных недавно страниц (NRU) - это алгоритм, который способствует сохранению в памяти недавно использованных страниц. Этот алгоритм работает по следующему принципу: когда на страницу ссылаются, для этой страницы устанавливается бит ссылки, помечающий ее как указанную. Точно так же, когда страница модифицируется (записывается), устанавливается модифицированный бит. Установка битов обычно выполняется аппаратно, хотя это возможно и на программном уровне.
Через определенный фиксированный интервал времени срабатывает прерывание таймера и очищает указанный бит на всех страницах, поэтому только страницы, на которые есть ссылки в текущем интервале таймера, помечаются указанным битом. Когда страницу необходимо заменить, операционная система делит страницы на четыре класса:
Хотя не представляется возможным изменить страницу, но при этом на нее не будет ссылаться, это происходит, когда ссылочный бит страницы класса 3 сброшен прерыванием таймера. Алгоритм NRU выбирает случайную страницу из самой низкой категории для удаления. Таким образом, из четырех вышеперечисленных категорий страниц алгоритм NRU заменит страницу без ссылок и без изменений, если такая страница существует. Обратите внимание, что этот алгоритм подразумевает, что измененная, но не упоминаемая (в пределах последнего интервала таймера) страница менее важна, чем не измененная страница, на которую часто ссылаются.
NRU - это алгоритм маркировки, поэтому он -конкурентоспособен.
Самый простой алгоритм замены страниц - это алгоритм FIFO. Алгоритм замены страниц «первым пришел - первым обслужен» (FIFO) - это алгоритм с низкими накладными расходами, который требует небольшого учета со стороны операционной системы. Идея очевидна из названия - операционная система отслеживает все страницы в памяти в очереди, причем самые свежие поступления находятся сзади, а самые старые - впереди. Когда страницу необходимо заменить, выбирается страница в начале очереди (самая старая страница). Хотя FIFO дешев и интуитивно понятен, он плохо работает на практике. Таким образом, он редко используется в неизмененном виде. Этот алгоритм обнаруживает аномалию Белади. Проще говоря, при отказе страницы заменяется фрейм, который дольше всех находился в памяти.
Алгоритм замены страницы FIFO используется операционной системой VAX / VMS с некоторыми изменениями. Частичный второй шанс предоставляется за счет пропуска ограниченного числа записей с действительными ссылками на таблицу преобразования, и, кроме того, страницы перемещаются из рабочего набора процессов в общесистемный пул, из которого они могут быть восстановлены, если они еще не использовались повторно.
FIFO - это консервативный алгоритм, поэтому он конкурентоспособен.
Модифицированная форма алгоритма замены страницы FIFO, известная как алгоритм замены страницы второго шанса, работает относительно лучше, чем FIFO, при небольших затратах на улучшение. Он работает, глядя на переднюю часть очереди, как это делает FIFO, но вместо того, чтобы немедленно вывести эту страницу на страницу, он проверяет, установлен ли бит, на который он ссылается. Если он не установлен, страница выгружается. В противном случае указанный бит очищается, страница вставляется в конец очереди (как если бы это была новая страница), и этот процесс повторяется. Это также можно рассматривать как циклическую очередь. Если для всех страниц установлен бит ссылки, при втором обнаружении первой страницы в списке эта страница будет выгружена, так как теперь у нее сброшен бит ссылки. Если у всех страниц бит ссылки очищен, тогда алгоритм второго шанса вырождается в чистый FIFO.
Как следует из названия, «Второй шанс» дает каждой странице «второй шанс» - старая страница, на которую была сделана ссылка, вероятно, уже используется, и ее не следует заменять новой страницей, на которую не ссылались.
Clock - более эффективная версия FIFO, чем Second-Chance, потому что страницы не нужно постоянно перемещать в конец списка, но они выполняют ту же общую функцию, что и Second-Chance. Алгоритм часов хранит в памяти циклический список страниц, при этом «рука» (итератор) указывает на последний проверенный страничный фрейм в списке. Когда возникает ошибка страницы и не существует пустых кадров, тогда проверяется бит R (указанный) в местоположении руки. Если R равно 0, новая страница помещается на место страницы, на которую указывает «рука», и рука перемещается на одну позицию. В противном случае бит R очищается, затем стрелка часов увеличивается, и процесс повторяется до тех пор, пока страница не будет заменена. Этот алгоритм был впервые описан в 1969 г. Ф. Дж. Корбато.
ЧАСЫ - это консервативный алгоритм, поэтому он конкурентоспособен.
Алгоритм замены страниц, который использовался не так давно (LRU), хотя и похож по названию на NRU, отличается тем, что LRU отслеживает использование страницы в течение короткого периода времени, тогда как NRU просто смотрит на использование в последнем тактовом интервале. LRU исходит из того, что страницы, которые наиболее активно использовались в последних нескольких инструкциях, скорее всего, будут активно использоваться и в следующих нескольких инструкциях. Хотя LRU может обеспечить почти оптимальную производительность в теории (почти так же хорошо, как кэш адаптивной замены ), на практике это довольно дорого. Есть несколько методов реализации этого алгоритма, которые пытаются снизить стоимость, но сохранить максимальную производительность.
Самый затратный метод - это метод связанного списка, который использует связанный список, содержащий все страницы в памяти. В конце этого списка находится страница, которая использовалась меньше всего, а в начале - страница, которая использовалась последней. Стоимость этой реализации заключается в том, что элементы в списке придется перемещать по каждой ссылке в памяти, что является очень трудоемким процессом.
Другой метод, требующий аппаратной поддержки, заключается в следующем: предположим, что у оборудования есть 64-битный счетчик, который увеличивается при каждой инструкции. При каждом доступе к странице она получает значение, равное счетчику на момент доступа к странице. Всякий раз, когда страницу необходимо заменить, операционная система выбирает страницу с наименьшим счетчиком и меняет ее местами.
Из-за затрат на реализацию можно рассмотреть алгоритмы (подобные следующим), которые похожи на LRU, но предлагают более дешевые реализации.
Одним из важных преимуществ алгоритма LRU является то, что он поддается полному статистическому анализу. Было доказано, например, что LRU никогда не может привести к более чем N раз большему количеству ошибок страниц, чем алгоритм OPT, где N пропорционально количеству страниц в управляемом пуле.
С другой стороны, слабость LRU заключается в том, что его производительность имеет тенденцию к ухудшению под многими довольно распространенными эталонными шаблонами. Например, если в пуле LRU есть N страниц, приложение, выполняющее цикл по массиву из N + 1 страниц, вызовет отказ страницы при каждом доступе. Поскольку циклы над большими массивами являются обычным явлением, было приложено много усилий для изменения LRU, чтобы он лучше работал в таких ситуациях. Многие из предлагаемых модификаций LRU пытаются обнаружить циклические эталонные шаблоны и переключиться на подходящий алгоритм замены, такой как Most Recently Used (MRU).
Сравнение ARC с другими алгоритмами (LRU, MQ, 2Q, LRU-2, LRFU, LIRS ) можно найти в Megiddo amp; Modha 2004.
LRU - это алгоритм маркировки, поэтому он -конкурентоспособен.
Алгоритм случайной замены заменяет случайную страницу в памяти. Это исключает накладные расходы на отслеживание ссылок на страницы. Обычно он работает лучше, чем FIFO, а для циклических обращений к памяти он лучше, чем LRU, хотя в целом LRU на практике работает лучше. OS / 390 использует глобальное приближение LRU и возвращается к случайной замене, когда производительность LRU ухудшается, а процессор Intel i860 использовал политику случайной замены (Rhodehamel, 1989).
Алгоритм замены нечасто используемых страниц (NFU) требует счетчика, и каждая страница имеет свой собственный счетчик, который изначально установлен на 0. В каждом тактовом интервале счетчик всех страниц, на которые имеется ссылка в этом интервале, будет увеличиваться на 1. Фактически, счетчики отслеживают, как часто страница использовалась. Таким образом, при необходимости страницу с наименьшим счетчиком можно заменить.
Основная проблема с NFU заключается в том, что он отслеживает частоту использования без учета временного интервала использования. Таким образом, в многопроходном компиляторе страницы, которые интенсивно использовались во время первого прохода, но не нужны во втором проходе, будут иметь преимущество перед страницами, которые сравнительно мало используются во втором проходе, поскольку они имеют более высокие счетчики частоты. Это приводит к снижению производительности. Существуют и другие распространенные сценарии, в которых NFU будет работать аналогичным образом, например, при загрузке ОС. К счастью, существует похожий и лучший алгоритм, и его описание следует ниже.
Не часто используемый алгоритм замены страниц генерирует меньше ошибок страниц, чем алгоритм замены страниц, который использовался не так давно, когда таблица страниц содержит значения нулевого указателя.
Алгоритм устаревания является потомком алгоритма NFU с модификациями, чтобы он знал о временном интервале использования. Вместо того, чтобы просто увеличивать счетчики страниц, на которые есть ссылки, уделяя одинаковое внимание ссылкам на страницы независимо от времени, счетчик ссылок на странице сначала сдвигается вправо (делится на 2) перед добавлением указанного бита слева от этого двоичного числа. Например, если страница ссылалась на биты 1,0,0,1,1,0 за последние 6 тактов часов, ее счетчик, на который ссылаются, будет выглядеть следующим образом: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. Ссылки на страницы ближе в настоящее время имеют большее влияние, чем ссылки на страницы давным-давно. Это гарантирует, что страницы, на которые ссылаются позже, хотя и реже, будут иметь более высокий приоритет по сравнению со страницами, на которые чаще ссылались в прошлом. Таким образом, когда страницу необходимо заменить, будет выбрана страница с наименьшим счетчиком.
Следующий код Python моделирует алгоритм старения. Счетчики инициализируются с помощью0 и обновляется, как описано выше, с помощью операторов арифметического сдвига.
0 и обновляется, как описано выше, с помощью 
from collections.abc import Sequence def simulate_aging(Rs: Sequence, k: int) -gt; None: """Simulate aging.""" print(' t | R-bits (0-{length}) | Counters for pages 0-{length}'.format(length=len(Rs))) Vs = [0] * len(Rs[0]) for t, R in enumerate(Rs): Vs[:] = [R[i] lt;lt; k - 1 | V gt;gt; 1 for i, V in enumerate(Vs)] print('{:02d} | {} | [{}]'.format(t, R, ', '.join(['{:0{}b}'.format(V, k) for V in Vs]))) В данном примере R-битов для 6 страниц за 5 тактов тактовой частоты функция выводит следующий вывод, в котором перечислены R-биты для каждого такта t и отдельные значения счетчиков для каждой страницы в двоичном представлении.
gt;gt;gt; Rs = [[1,0,1,0,1,1], [1,1,0,0,1,0], [1,1,0,1,0,1], [1,0,0,0,1,0], [0,1,1,0,0,0]] gt;gt;gt; k = 8 gt;gt;gt; simulate_aging(Rs, k) t | R-bits (0-5) | Counters for pages 0-5 00 | [1, 0, 1, 0, 1, 1] | [10000000, 00000000, 10000000, 00000000, 10000000, 10000000] 01 | [1, 1, 0, 0, 1, 0] | [11000000, 10000000, 01000000, 00000000, 11000000, 01000000] 02 | [1, 1, 0, 1, 0, 1] | [11100000, 11000000, 00100000, 10000000, 01100000, 10100000] 03 | [1, 0, 0, 0, 1, 0] | [11110000, 01100000, 00010000, 01000000, 10110000, 01010000] 04 | [0, 1, 1, 0, 0, 0] | [01111000, 10110000, 10001000, 00100000, 01011000, 00101000]
Обратите внимание, что старение отличается от LRU в том смысле, что старение может отслеживать только ссылки в последней версии. 16/32 (в зависимости от разрядности целых чисел процессора) временных интервалов. Следовательно, две страницы могут иметь ссылочные счетчики 00000000, даже если на одну страницу ссылались 9 интервалов назад, а на другую 1000 интервалов назад. Вообще говоря, информации об использовании в течение последних 16 интервалов достаточно, чтобы принять правильное решение о том, какую страницу заменить. Таким образом, старение может предложить почти оптимальную производительность по умеренной цене.
Основная идея, лежащая в основе этого алгоритма, - это локальность ссылки, используемая в LRU, но разница в том, что в LDF локальность основана на расстоянии, а не на используемых ссылках. В LDF замените страницу, которая находится на наибольшем расстоянии от текущей страницы. Если две страницы находятся на одинаковом расстоянии, то страница, которая находится рядом с текущей страницей при повороте против часовой стрелки, будет заменена.
Многие из описанных выше методов предполагают наличие справочного бита, связанного с каждой страницей. Некоторое оборудование не имеет такого бита, поэтому для его эффективного использования требуются методы, которые хорошо работают без него.
Одним из ярких примеров является оборудование VAX, на котором работает OpenVMS. Эта система знает, была ли страница изменена, но не обязательно, если страница была прочитана. Его подход известен как кэширование вторичной страницы. Страницы, удаленные из рабочих наборов (как правило, частной памяти процесса), помещаются в специальные списки, оставаясь в физической памяти в течение некоторого времени. Удаление страницы из рабочего набора технически не является операцией замены страницы, но эффективно идентифицирует эту страницу как кандидата. Страница, резервное хранилище которой все еще действует (чье содержимое не загрязнено или его не нужно сохранять по другим причинам), помещается в конец списка бесплатных страниц. Страница, требующая записи в резервное хранилище, будет помещена в список измененных страниц. Эти действия обычно запускаются, когда размер списка бесплатных страниц становится ниже регулируемого порогового значения.
Страницы могут быть выбраны для удаления рабочего набора по существу случайным образом, с ожиданием того, что, если будет сделан неправильный выбор, будущая ссылка может извлечь эту страницу из списка Свободных или Измененных, прежде чем она будет удалена из физической памяти. Страница, на которую ссылаются таким образом, будет удалена из списка Free или Modified и помещена обратно в рабочий набор процесса. Список измененных страниц дополнительно предоставляет возможность записывать страницы в резервное хранилище группами по несколько страниц, повышая эффективность. Эти страницы могут быть затем помещены в список бесплатных страниц. Последовательность страниц, которая продвигается к началу списка бесплатных страниц, напоминает результаты механизма LRU или NRU, и общий эффект имеет сходство с алгоритмом второго шанса, описанным ранее.
Другой пример используется ядром Linux на ARM. Отсутствие аппаратной функциональности компенсируется наличием двух таблиц страниц - собственных таблиц страниц процессора без битов ссылок и грязных битов и таблиц страниц, поддерживаемых программным обеспечением, с необходимыми битами. Эмулируемые биты в таблице, обслуживаемой программным обеспечением, устанавливаются ошибками страниц. Чтобы получить ошибки страницы, очистка эмулированных битов во второй таблице отменяет некоторые права доступа к соответствующей странице, что реализуется путем изменения собственной таблицы.
Linux использует единый кеш страниц для
brk и анонимные mmaped -регионы. Это включает в себя кучу и стек программ пользовательского пространства. Написано для подкачки при выгрузке.mmapредакционные регионы. Если физическая страница присутствует в памяти и не изменена частным образом, она используется совместно с файловым кешем или буфером.shm_open.Единый страничный кеш работает с блоками наименьшего размера страницы, поддерживаемыми ЦП (4 КиБ в ARMv8, x86 и x86-64 ), с некоторыми страницами следующего большего размера (2 МиБ в x86-64 ), которые называются «огромными страницами». Linux. Страницы в кэше страниц делятся на «активный» набор и «неактивный» набор. Оба набора содержат список страниц LRU. В основном случае, когда к странице обращается программа пользовательского пространства, она помещается в начало неактивного набора. При повторном обращении к нему он перемещается в активный список. Linux перемещает страницы из активного набора в неактивный по мере необходимости, так что активный набор меньше неактивного набора. Когда страница перемещается в неактивный набор, она удаляется из таблицы страниц любого адресного пространства процесса без подкачки из физической памяти. Когда страница удаляется из неактивного набора, она выгружается из физической памяти. Размер «активного» и «неактивного» списка можно запросить /proc/meminfoв полях «Активный», «Неактивный», «Активный (анон)», «Неактивный (анон)», «Активный (файл)» и «Неактивный». (файл)".
Рабочий набор процесса - это набор страниц, которые, как ожидается, будут использоваться этим процессом в течение некоторого интервала времени.
«Модель рабочего набора» не является алгоритмом замены страниц в строгом смысле слова (на самом деле это своего рода среднесрочный планировщик )
