Доказательство оптимальной замены страницы (OPT)

Мне нужно доказать, что оптимальный алгоритм замены страниц действительно оптимален, и я не уверен, как именно начать. Я думал, что может быть доказательством от противоречия, но как только я сформулировал альтернативное утверждение, я не был уверен, как показать, что оно будет иметь столько же или меньше ошибок на странице, чем OPT.

2 ответа

Это для финала CSE 330 завтра?

Наибольшее расстояние вперед (LFD)

  • Замените страницу, следующий запрос которой самый дальний (в будущем)

Теорема:

  • LFD (самое длинное расстояние вперед) является оптимальным алгоритмом.

Доказательство:

  • Для противоречия предположим, что LFD не является оптимальным
  • Тогда существует конечная входная последовательность α, на которой LFD не является оптимальной (предположим, что длина α равна | α| = n)
  • Пусть OPT - оптимальное решение для α такое, что

- OPT обрабатывает запросы 1,2, …, i так же, как LFD

- OPT обрабатывает запрос i+1 иначе, чем LFD

- Любая другая оптимальная стратегия обрабатывает один из первых запросов i+1 не так, как LDF.

• Следовательно, OPT является оптимальным решением, которое ведет себя так же, как LFD, как можно дольше -> у нас есть i

Цель: построить OPT′, идентичный LFD для запроса. 1, …, я + 1

Случай 1: Запрос i+1 не приводит к ошибке страницы

• LFD не меняет содержимое быстрой памяти

• OPT ведет себя иначе, чем LFD -> OPT заменяет некоторые страницы в быстрой памяти

- Что касается запроса i+1, оба алгоритма ведут себя одинаково, они также имеют одинаковое быстрое содержимое памяти

- поэтому OPT не требует новой страницы для запроса i+1

- Следовательно, OPT также может загрузить эту страницу позже (без дополнительных затрат) -> OPT′

Случай 2: Запрос i+1 приводит к ошибке страницы

• LFD и OPT перемещают одну и ту же страницу в быструю память, но они высвобождают разные страницы

- Если OPT загружает более одной страницы, все страницы, которые не требуются для запроса i+1, также могут быть загружены позже

• Скажем, LFD выселяет страницу p, а OPT выселяет страницу p '

По определению LFD, p 'требуется снова перед страницей p

карта замены страницы

Сейчас есть 2 случая:

а) OPT сохраняет р в быстрой памяти до запроса ℓ

- OPT может выселить p по запросу i+1, оставив вместо него p′ и загрузить p (вместо p′) обратно в быструю память по запросу ℓ, без каких-либо дополнительных затрат, аналогично LFD

б) OPT выселяет p по запросу ℓ '<ℓ

- OPT может высвободить p по запросу i+1, оставив вместо него p ', и загрузить p, высвободив p' по запросу ℓ '(переключить вытеснения p и p'), опять же, аналогично LFD

следовательно, OPT не лучшее решение, чем LFD.

то есть, LFD является оптимальной техникой замены страницы.

LFD также называется оптимальной техникой замены страниц (OPT).

PS: в доказательстве имя "OPT" используется просто как "имя", не путайте его с "Оптимальной техникой замены страницы".

Другие вопросы по тегам