2011-gre-cs-practice-book.pdf/Q20 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: 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: Промах (заменяем 7, кадры: [6, 1, 3, 2]). | + | ;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]). | ||
Итог: | Итог: | ||
| Строка 76: | Строка 58: | ||
Всего промахов страниц = 10. | Всего промахов страниц = 10. | ||
| − | {{question-ok | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 14:08, 19 декабря 2024 (UTC)}} |
| − | + | ||
Версия 14:08, 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.