<<
>>

Оптимальный алгоритм (ОРТ)

Одним из последствий открытия аномалии Билэди стал поиск оптимального алгоритма, который при заданной строке обращений имел бы минимальную частоту page faults среди всех других алгоритмов. Такой алгоритм был найден.
Он прост: замещай страницу, которая не будет использоваться в течение самого длительного периода времени.

Каждая страница должна быть помечена числом инструкций, которые будут выполнены, прежде чем на эту страницу будет сделана первая ссылка. Выталкиваться должна страница, для которой это число наибольшее.

Этот алгоритм легко описать, но реализовать невозможно. ОС не знает, к какой странице будет следующее обращение. (Ранее такие проблемы возникали при планировании процессов — алгоритм SJF.)

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

<< | >>
Источник: В.Е. Карпов К.А. Коньков. Основы операционных систем. 2005 {original}

Еще по теме Оптимальный алгоритм (ОРТ):

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ
  3. АЛГОРИТМ УДАЧИ
  4. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. Оптимальные условия
  8. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  9. Алгоритм обработки результатов.
  10. АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
  11. ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО