Во-первых, каков алгоритм замены страницы
Во время выполнения процесса, если страница, к которой он обращается, не существует в памяти, будет сгенерировано прерывание по ошибке страницы. Если в это время в памяти нет свободной страницы, операционной системе необходимо выбрать страницу в памяти, чтобы переместить ее, чтобы страница, к которой нужно получить доступ, могла быть загружена в память. Алгоритм, используемый для выбора страниц, подлежащих удалению, называется алгоритмом замены страниц. Хороший алгоритм замены страниц имеет низкую частоту замены страниц.
Во-вторых, общий алгоритм замены страницы
1. OPT (алгоритм оптимальной перестановки)
Оптимальный алгоритм замены: страницы, которые удаляются каждый раз, будут страницами, которые никогда не будут использоваться в будущем или не будут доступны в течение длительного времени. Это обеспечивает самый низкий уровень отказов страниц.
Например: если операционная система выделяет процессу 3 блока памяти, и процесс будет последовательно обращаться к 7, 5, 2, 3, 6, 2, 7, 1, 6, 7, 2, 3, 7, 2, 7.
Как показано на рисунке, на шаге 4 в память нужно перенести страницу 3. В это время память заполнена, поэтому нужно выбрать страницу из 7, 5 и 2 для исключения. По правилам алгоритма наилучшей замены ищем ее позже, в это время последовательно будут обращаться 2 и 7, поэтому будет исключена страница 5, то есть страница, к которой не обращались дольше всего.
2. FIFO (алгоритм «первым пришел – первым обслужен»)
Алгоритм FIFO является простейшим алгоритмом замены страниц. Как следует из названия, страница, удаляемая каждый раз FIFO, является первой страницей, поступающей в память. Метод реализации FIFO заключается в последовательном размещении страниц, переданных в память, в очередь, при необходимости замены страницы может быть выбрана страница, находящаяся в начале очереди.
Например: если операционная система выделяет процессу 3 блока памяти, и процесс будет последовательно обращаться к 7, 5, 2, 3, 6, 2, 7, 1, 6, 7, 2, 3, 7, 2, 7. Страница появляется в памяти следующим образом:
3. LRU (алгоритм, который в последнее время дольше всего не использовался)
LRU (наименее недавно использованная) — страница, которая удаляется каждый раз, — это страница, которая в последнее время не использовалась дольше всего. Следовательно, необходимо записать время t, прошедшее с момента последнего обращения к странице. Когда страницу необходимо удалить, выбирается страница с наибольшим t среди существующих страниц в памяти, то есть страница, которая не использовалась дольше всего.
Например: если операционная система выделяет процессу 3 блока памяти, и процесс будет последовательно обращаться к 7, 5, 2, 3, 6, 2, 7, 1, 6, 7, 2, 3, 7, 2, 7. Страница появляется в памяти следующим образом:
Как показано на рисунке, на четвертом шаге страницу 3 нужно перенести в память, а память в это время заполнена, и нужно выбрать страницу из 7, 5 и 2 для исключения. Согласно правилам LRU, время, прошедшее с момента последнего доступа к странице 7, равно 3, и он является самым большим, поэтому страница 7 исключается.
4. LFU (наименее используемый алгоритм)
LFU (Алгоритм наименее недавно использованного), который основан на идее «если данные использовались очень мало раз в недавнем периоде, вероятность их использования в будущем периоде также очень мала». Обратите внимание на разницу между алгоритмами LFU и LRU.Правило исключения LRU основано на времени доступа, а LFU основано на количестве доступов.
Например, если операционная система выделяет процессу 3 блока памяти, то процесс по очереди будет обращаться к 5, 4, 5, 3, 3, 2, 5, 1 и 4. Страница появляется в памяти следующим образом:
Как показано на рисунке, на восьмом шаге страницу 1 нужно перенести в память, а память в это время заполнена, и нужно выбрать страницу из 5, 2 и 3 для исключения. Согласно правилам LFU, количество раз, когда страница 2 использовалась за последний период, равно 1, что является наименьшим. Так что удалите страницу 2.
Для получения дополнительных технических статей, пожалуйста, отсканируйте код и подпишитесь на официальный аккаунт.