Теоретически оптимальная замена страницы
Теоретически оптимальный алгоритм замены страниц работает следующим образом: если необходимо поменять страницу на диск, система выбирает ту, которая будет использоваться не позднее, чем.
Этот алгоритм носит чисто теоретический характер, поскольку он не может быть надежно реализован в классической операционной системе. Существуют алгоритмы, которые анализируют выполнение программы и могут очень близко подойти к теоретически оптимальному алгоритму после нескольких циклов «обучения» при условии, что программа ведет себя аналогичным (предсказуемым) образом с каждым циклом.
Используя этот теоретический алгоритм «наилучшего случая», оценивается эффективность других алгоритмов.
NRU — не использовался недавно
Неиспользованные недавно (NRU) — это алгоритм, который сохраняет в памяти недавно использованные страницы в качестве приоритета.
Этот алгоритм работает по принципу присвоения свойств отдельным страницам, а именно: бит ссылки (на страницу была сделана ссылка) и бит изменения (страница была изменена).
Для каждой страницы запускается таймер, который сбрасывает ее свойства через определенное время. Это гарантирует, что недавно использованные страницы предпочтительно сохраняются в памяти, а недавно неиспользованные страницы выгружаются на диск.
Это алгоритм тегирования, поэтому используется соответствующий рейтинг эффективности.
FIFO — первым пришел, первым ушел
Это простой алгоритм разбиения по страницам, использующий (как уже ясно из заголовка) структуру первой страницы, и это правда, что когда размер очереди (памяти) исчерпан, меняет местами страница, которая находится в очереди дольше всего.
Это очень «дешевый» алгоритм с точки зрения системных ресурсов, однако его эффективность очень низкая, поэтому он практически не используется.
Это консервативный алгоритм.
Второй шанс (алгоритм второго шанса)
Это модификация алгоритма FIFO (см. Выше). Это значительно более эффективный алгоритм с относительно небольшим увеличением требований к системным ресурсам. Он использует комбинацию алгоритмов FIFO и NRU, которые, как и FIFO, проверяют начало очереди, но вместо того, чтобы сразу переставлять первую страницу на диск, он проверяет, назначен ли ей бит refrenced, если это так, переходит к следующей странице и завершает работу.
Если на всех страницах установлен бит, на который указывает ссылка, то во втором цикле выполняется замена первой страницы в очереди.
Часы (алгоритм часов)
Это более эффективный вариант алгоритма FIFO (также по отношению к алгоритму второго шанса). Пространство подкачки расположено в виде круга (часы), в котором перемещается указатель (рука), указывающий на последнюю проверенную страницу (или пустой фрейм подкачки).
Если память заканчивается, наличие refrenced бита проверяется на странице, где находится указатель. Если бит R равен 0, старая страница выгружается на диск, и на ее место записывается новая страница. Если значение бита R равно 1, оно меняется на 0, и указатель перемещается на одну позицию. Этот процесс повторяется до тех пор, пока не будет написана новая страница.
LRU — наименее использованный
Этот алгоритм похож на алгоритм NRU, за исключением того, что, хотя NRU работает только с отдельными тактами таймера LRU, он работает со страницами, которые использовались в последних нескольких инструкциях.
Идея алгоритма состоит в том, что страницы, которые наиболее часто использовались в недавнем прошлом, скорее всего, будут использоваться снова в ближайшем будущем.
Основная проблема алгоритма LRU заключается в очень дорогой реализации в контексте системных ресурсов.
Базовая (и самая дорогая) реализация LRU заключается в использовании списка ссылок, в котором последние использованные страницы находятся сзади, а большинство — впереди. Сложность этой реализации связана с тем, что этот лист необходимо перемещать каждый раз при доступе к памяти.
Другой способ реализации возможен с использованием аппаратного счетчика. В этом случае текущее значение счетчика всегда присваивается «вызываемой» странице. Затем заменяются страницы с наименьшим значением. Однако эта реализация также очень требовательна и все еще не подходит для современного оборудования.
Поэтому большим недостатком LRU являются требования к производительности. Существует большое количество его модификаций, использующих LRU лишь частично или только в отдельных случаях.
Это алгоритм маркировки.
Случайный
Этот алгоритм просто заменяет случайную страницу в памяти, имеет низкую производительность и в большинстве случаев работает лучше, чем FIFO. Однако обычно он менее оптимален, чем LRU.
NFU — не часто используется
Этот алгоритм работает по принципу счетчиков, которые назначаются каждой странице и изначально установлены на ноль. Затем в каждом интервале таймера все вызываемые страницы добавляются к их счетчику 1. При подкачке предпочтительнее страница с наименьшим значением счетчика.
Самый большой недостаток NFU в том, что алгоритм не учитывает частоту использования страниц, а только их количество. Это, конечно, проблематично, когда, например, одна группа страниц широко используется в первой части процесса, а во второй — гораздо более важная группа, которая до сих пор использовалась только спорадически.
Старение
Это производная от алгоритма NFU, она работает аналогично с той разницей, что счетчик делится на 2 в каждом тике, а затем в конечном итоге увеличивается. Это обеспечивает большую актуальность последних ссылок.
По сути, единственным недостатком алгоритма устаревания является тот факт, что он может отслеживать ссылки только с 16- или 32-битными интервалами (в зависимости от процессора ). Однако на практике это не большая проблема, потому что для большинства задач этого диапазона достаточно.
Следовательно, это алгоритм умеренно требовательный, но очень близкий к оптимальному алгоритму.