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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показана одна промежуточная версия этого же участника)
Строка 1: Строка 1:
−
{{reserve-task|[[Участник:Yaroslav Klimov М05-304Б|Yaroslav Klimov М05-304Б]] 05:26, 19 декабря 2024 (UTC)}}
 
 
== Вопрос: Q20-08c765 ==
 
== Вопрос: Q20-08c765 ==
  
−
Рассмотрите следующую последовательность ссылок на страницы: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1.
+
Рассмотрите следующую последовательность ссылок на страницы:  
 +
 +
  1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1.
  
−
Предполагая, что доступно 4 кадра страниц, и что все кадры изначально пустые, сколько всего будет возникать промахов страниц при использовании политики замены страниц Least Recently Used (LRU)?
+
Предполагая, что доступно 4 кадра страниц, и что все кадры изначально пустые, сколько всего будет возникать промахов страниц при использовании политики замены страниц [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BA%D1%8D%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F Least Recently Used] (LRU)?
  
 
=== Ответы ===
 
=== Ответы ===
Строка 16: Строка 17:
 
{{cstest-source|2011-gre-cs-practice-book.pdf|25|20}}
 
{{cstest-source|2011-gre-cs-practice-book.pdf|25|20}}
  
−
Политика LRU (наименее недавно использованная) работает следующим образом:
+
Политика LRU ([https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BA%D1%8D%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F наименее недавно использованная]) работает следующим образом:
  
 
* Если страница запрашивается, но её нет в памяти (промах страницы), то нужно поместить её в кадр.
 
* Если страница запрашивается, но её нет в памяти (промах страницы), то нужно поместить её в кадр.
Строка 24: Строка 25:
 
Алгоритм решения:
 
Алгоритм решения:
  
−
1. Изначально кадры пустые.
+
* 1. Изначально кадры пустые.
−
 
+
* 2. Просматриваем каждую страницу из последовательности по порядку.
−
2. Просматриваем каждую страницу из последовательности по порядку.
+
* 3. Отслеживаем, находятся ли текущие страницы в кадрах.
−
 
+
* 4. Если страница отсутствует, происходит промах, и мы либо добавляем её в пустой кадр, либо заменяем старую страницу по принципу LRU.
−
3. Отслеживаем, находятся ли текущие страницы в кадрах.
+
−
 
+
−
4. Если страница отсутствует, происходит промах, и мы либо добавляем её в пустой кадр, либо заменяем старую страницу по принципу LRU.
+
  
 
Выполнение пошагово:
 
Выполнение пошагово:
Строка 36: Строка 34:
 
Имеем 4 кадра (пустые в начале). Просматриваем страницы последовательно:
 
Имеем 4 кадра (пустые в начале). Просматриваем страницы последовательно:
  
−
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1
+
  1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1
  
−
1: Промах (кадры: [1])
+
;1: Промах (кадры: [1])
−
 
+
;2: Промах (кадры: [1, 2])
−
2: Промах (кадры: [1, 2])
+
;3: Промах (кадры: [1, 2, 3])
−
 
+
;4: Промах (кадры: [1, 2, 3, 4])
−
3: Промах (кадры: [1, 2, 3])
+
;2: Удача (страница уже в кадре).
−
 
+
;1: Удача (страница уже в кадре).
−
4: Промах (кадры: [1, 2, 3, 4])
+
;5: Промах (заменяем 3 — самая давно неиспользуемая, кадры: [1, 2, 4, 5])
−
 
+
;6: Промах (заменяем 4, кадры: [1, 2, 5, 6])
−
2: Удача (страница уже в кадре).
+
;2: Удача (страница уже в кадре).
−
 
+
;1: Удача (страница уже в кадре).
−
1: Удача (страница уже в кадре).
+
;2: Удача (страница уже в кадре).
−
 
+
;3: Промах (заменяем 5, кадры: [1, 2, 6, 3])
−
5: Промах (заменяем 3 — самая давно неиспользуемая, кадры: [1, 2, 4, 5])
+
;7: Промах (заменяем 6, кадры: [1, 2, 3, 7])
−
 
+
;6: Промах (заменяем 1, кадры: [6, 2, 3, 7])
−
6: Промах (заменяем 4, кадры: [1, 2, 5, 6])
+
;3: Удача (страница уже в кадре).
−
 
+
;2: Удача (страница уже в кадре).
−
2: Удача (страница уже в кадре).
+
;1: Промах (заменяем 7, кадры: [6, 1, 3, 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]).
+
  
 
Итог:
 
Итог:
Строка 76: Строка 58:
 
Всего промахов страниц = 10.
 
Всего промахов страниц = 10.
  
−
{{question-ok|}}
+
{{question-ok|[[Участник:StasFomin|StasFomin]] 14:08, 19 декабря 2024 (UTC)}}
−
{{checkme|[[Участник:Yaroslav Klimov М05-304Б|Yaroslav Klimov М05-304Б]] 05:30, 19 декабря 2024 (UTC)}}
+
 
 +
[[Категория:Кэш]]

Текущая версия на 14:09, 19 декабря 2024

Вопрос: 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.

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