Краткая сравнительная характеристика алгоритмов замещения страниц

Только что мы рассмотрели несколько различных алгоритмов замещения страниц. В этом разделе дадим им краткую сравнительную характеристику. Список рассмотренных алгоритмов представлен в табл. 3.2.
Таблица 3.2.
Список рассмотренных алгоритмов замещения страниц


Оптимальный алгоритм удаляет страницу с самым отдаленным предстоящим обращением. К сожалению, у нас нет способа определения, какая это будет страница, поэтому на практике этот алгоритм использоваться не может. Но он полезен в качестве оценочного критерия при рассмотрении других алгоритмов.

Алгоритм исключения недавно использованной страницы (NRU) делит страницы на четыре класса в зависимости от состояния битов R и M. Затем выбирает произвольную страницу из класса с самым низким номером. Этот алгоритм нетрудно реализовать, но он слишком примитивен. Есть более подходящие алгоритмы.

Алгоритм FIFO предполагает отслеживание порядка, в котором страницы были загружены в память, путем сохранения сведений об этих страницах в связанном списке. Это упрощает удаление самой старой страницы, но она-то как раз и может все еще использоваться, поэтому FIFO — неподходящий выбор.

Алгоритм «второй шанс» является модификацией алгоритма FIFO и перед удалением страницы проверяет, не используется ли она в данный момент. Если страница все еще используется, она остается в памяти. Эта модификация существенно повышает производительность. Алгоритм «часы» является простой разновидностью алгоритма «второй шанс». Он имеет такой же показатель производительности, но требует несколько меньшего времени на свое выполнение.

Алгоритм LRU превосходен во всех отношениях, но не может быть реализован без специального оборудования. Если такое оборудование недоступно, то он не может быть использован. Алгоритм NFU является грубой попыткой приблизиться к алгоритму LRU. Его нельзя признать удачным. А вот алгоритм старения — куда более удачное приближение к алгоритму LRU, которое к тому же может быть эффективно реализовано и считается хорошим выбором.

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

В итоге наиболее приемлемыми алгоритмами являются алгоритм старения и алгоритм WSClock. Они основаны на LRU и рабочем наборе соответственно. Оба обеспечивают неплохую производительность страничной организации памяти и могут быть эффективно реализованы. Существует также ряд других хороших алгоритмов, но эти два, наверное, имеют наибольшее практическое значение.

3.5.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Краткая сравнительная характеристика алгоритмов замещения страниц:

  1. СИСТЕМЫ ОЦЕНИВАНИЯ И ИХ КРАТКАЯ ХАРАКТЕРИСТИКА
  2. Краткая характеристика планет
  3. Краткая характеристика полей
  4. I. 1. 1. Краткая характеристика системного подход.
  5. Краткая характеристика знаков Зодиака
  6. Дадим краткую характеристику сути проблем.
  7. § 1. Сравнительная характеристика договоров поручения, комиссии, агентирования
  8. Краткая характеристика Основного закона. Его главные черты
  9. Первая страница
  10. ЗАМЕЩЕНИЕ
  11. ЗАМЕЩЕНИЕ
  12. 1. Программа учебного курса «Сравнительное правоведение (основные правовые системы современности)» Общая часть Введение в теорию и историю сравнительного правоведения
  13. Порядок замещения поста главы государства