Доказательство оптимальной замены страницы (OPT)
Мне нужно доказать, что оптимальный алгоритм замены страниц действительно оптимален, и я не уверен, как именно начать. Я думал, что может быть доказательством от противоречия, но как только я сформулировал альтернативное утверждение, я не был уверен, как показать, что оно будет иметь столько же или меньше ошибок на странице, чем OPT.
2 ответа
Наибольшее расстояние вперед (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" используется просто как "имя", не путайте его с "Оптимальной техникой замены страницы".