2011-gre-cs-practice-book.pdf/Q20
Задача зарезервирована: Yaroslav Klimov М05-304Б 05:26, 19 декабря 2024 (UTC)
Вопрос: Q20-08c765
Рассмотрите следующую последовательность ссылок на страницы: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1.
Предполагая, что доступно 4 кадра страниц, и что все кадры изначально пустые, сколько всего будет возникать промахов страниц при использовании политики замены страниц Least Recently Used (LRU)?
Ответы
- 6
- 7
- 9
- Правильный ответ: 10
- 11
Объяснение
Исходники — вопрос 20 на 25 странице книги «2011-gre-cs-practice-book.pdf»
Политика LRU (наименее недавно использованная) работает следующим образом:
- Если страница запрашивается, но её нет в памяти (промах страницы), то нужно поместить её в кадр.
- Если все кадры заполнены, удаляется страница, которая не использовалась дольше всего.
- Ведётся учёт порядка использования страниц.
Алгоритм решения:
1. Изначально кадры пустые.
2. Просматриваем каждую страницу из последовательности по порядку.
3. Отслеживаем, находятся ли текущие страницы в кадрах.
4. Если страница отсутствует, происходит промах, и мы либо добавляем её в пустой кадр, либо заменяем старую страницу по принципу LRU.
Выполнение пошагово:
Имеем 4 кадра (пустые в начале). Просматриваем страницы последовательно:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1
1: Промах (кадры: [1])
2: Промах (кадры: [1, 2])
3: Промах (кадры: [1, 2, 3])
4: Промах (кадры: [1, 2, 3, 4])
2: Удача (страница уже в кадре).
1: Удача (страница уже в кадре).
5: Промах (заменяем 3 — самая давно неиспользуемая, кадры: [1, 2, 4, 5])
6: Промах (заменяем 4, кадры: [1, 2, 5, 6])
2: Удача (страница уже в кадре).
1: Удача (страница уже в кадре).
2: Удача (страница уже в кадре).
3: Промах (заменяем 5, кадры: [1, 2, 6, 3])
7: Промах (заменяем 6, кадры: [1, 2, 3, 7])
6: Промах (заменяем 1, кадры: [6, 2, 3, 7])
3: Удача (страница уже в кадре).
2: Удача (страница уже в кадре).
1: Промах (заменяем 7, кадры: [6, 1, 3, 2]).
Итог:
Всего промахов страниц = 10.
Решено: Yaroslav Klimov М05-304Б 05:30, 19 декабря 2024 (UTC)
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.