2011-gre-cs-practice-book.pdf/Q20 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 77: Строка 77:
  
 
{{question-ok|}}
 
{{question-ok|}}
 +
{{checkme|[[Участник:Yaroslav Klimov М05-304Б|Yaroslav Klimov М05-304Б]] 05:30, 19 декабря 2024 (UTC)}}

Версия 05:30, 19 декабря 2024

Задача зарезервирована: 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.Check-me-animated.gif Решено: Yaroslav Klimov М05-304Б 05:30, 19 декабря 2024 (UTC)

Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q20&oldid=34023»