Файл: Debian Таненбаум Бос.pdf

Вопросы  

291

Следующим шагом стал свопинг. При его использовании система может работать 
с таким количеством процессов, которое превышает возможности памяти по их одно-
временному размещению. Процессы, для которых не хватает места в памяти, целиком 
выгружаются на диск. Свободные области в памяти и на диске могут отслеживаться 
с помощью битовой матрицы или списка свободных участков.

Современные компьютеры зачастую поддерживают одну из форм виртуальной памяти. 
В простейшем виде адресное пространство каждого процесса делится на одинаковые по 
размеру блоки, называемые страницами, которые могут размещаться в любом доступ-
ном страничном блоке в памяти. Существует множество алгоритмов замещения стра-
ниц, наиболее подходящими из которых являются алгоритмы «старения» и WSClock.

Одного выбора алгоритма еще недостаточно, чтобы добиться от систем со страничной 
организацией памяти приемлемой работы, необходимо обратить внимание на такие 
вопросы, как определение рабочего набора, политика выделения памяти и размер 
страниц.

Сегментация помогает в управлении структурами данных, изменяющими свой размер 
во время выполнения программы, и упрощает процессы компоновки и совместного 
доступа. Она также облегчает предоставление различных видов защиты разным сег-
ментам. Иногда сегментация и разбивка на страницы комбинируются, предоставляя 
двумерную виртуальную память. Сегментация и страничная организация памяти 
поддерживаются такими системами, как MULTICS и 32-разрядная Intel x86. Вполне 
очевидно, что разработчики операционных систем теперь вряд ли сильно озабочены 
сегментацией (поскольку сделали ставку на другую модель памяти). Следовательно, 
похоже, что она очень быстро выйдет из моды. Сейчас поддержка реальной сегмента-
ции отсутствует даже на 64-разрядных версиях x86.

Вопросы

1.  Машина IBM 360 имела схему блокировки блоков размером 2 Кбайт, работающую 

за счет присвоения каждому из них 4-битового ключа и сравнения центральным 
процессором ключа при каждой ссылке к памяти с 4-битовым ключом в слове со-
стояния процессора. Назовите два недостатка этой схемы, не упомянутые в тексте.

2.  Базовый и ограничительный регистры, показанные на рис. 3.3, имеют одинаковое 

значение — 16 384. Как, по-вашему, это случайность или они всегда имеют одина-
ковые значения? Если это всего лишь случайность, то почему у них в этом примере 
одинаковые значения?

3.  В системе, использующей свопинг, неиспользуемые пространства ликвидируются 

за счет уплотнения. Предположим, что существует произвольное размещение мно-
жества «дыр» и множества сегментов данных и время чтения или записи 32-раз-
рядного слова составляет 4 нс. Сколько времени (примерно) займет уплотнение 
4 Гбайт? Чтобы упростить задачу, предположим, что слово 0 является частью 
«дыры», а слово с самым старшим адресом памяти содержит нужные данные.

4.  Дана система подкачки, в которой память состоит из свободных участков, распола-

гающихся в памяти в следующем порядке: 10 Мбайт, 4 Мбайт, 20 Мбайт, 18 Мбайт, 
7 Мбайт, 9 Мбайт, 12 Мбайт и 15 Мбайт. Какие свободные участки берутся для 
следующих последовательных запросов сегмента:

292  

 Глава 3. Управление памятью 

a) 12 Мбайт;

б) 10 Мбайт;

в) 9 Мбайт

по алгоритму «первое подходящее»? Теперь ответьте на этот же вопрос для ал-
горитмов «наиболее подходящее», «наименее подходящее» и «следующее под-
ходящее».

5.  Чем отличаются друг от друга физический и виртуальный адреса?

6.  Для каждого из следующих десятичных виртуальных адресов вычислите номер 

виртуальной страницы и смещение применительно к странице размером 4 Кбайт 
и странице размером 8 Кбайт: 20 000, 32 768, 60 000.

7.  Используя таблицу страниц, приведенную на рис. 3.9, дайте физический адрес, 

соответствующий каждому из следующих виртуальных адресов:

а) 20;

б) 4100;

в) 8300.

8.  Процессор Intel 8086 не имеет диспетчера памяти или поддержки виртуальной 

памяти. Тем не менее некоторые компании ранее продавали системы, содержащие 
исходные процессоры 8086 и выполняющие страничную подкачку. Дайте обосно-
ванное предположение о том, как они это сделали. 

Подсказка

: подумайте о том, где нужно разместить диспетчер памяти (MMU).

9.  Какой вид аппаратной поддержки необходим для того, чтобы работала страничная 

организация виртуальной памяти?

10.  Копирование при записи является интересной идеей, используемой на серверных 

системах. Имеет ли она какой-либо смысл применительно к смартфонам?

11.  Дана следующая программа на языке C:

    int X[N];
    int step = M; // M — это некая предопределенная константа
    for (int i = 0; i < N; i += step) X[i] = X[i] + 1;

а)  Какие значения M и N вызовут отсутствие данных в буфере быстрого преоб-

разования данных (TLB) для каждого выполнения внутреннего цикла, если 
программа запущена на машине с размером страниц 4 Кбайт и TLB емкостью 
64 записи?

б)  Изменится ли ваш ответ на вопрос а, если цикл будет повторен многократно? 

Обоснуйте ответ.

12.  Объем пространства на диске, который должен быть доступен для хранения 

страниц, связан с максимальным количеством процессов n, количеством байтов 
в виртуальном адресном пространстве v и числом байтов в оперативной памяти r. 
Выведите формулу минимально необходимого дискового пространства. Насколько 
эта величина реалистична?

13.  Если выполнение инструкции занимает 1 нс, а обработка ошибки отсутствия 

страницы занимает дополнительно n наносекунд, приведите формулу для вычис-
ления эффективного времени выполнения инструкции, если ошибки отсутствия 
страницы случаются каждые k инструкций.

Вопросы  

293

14.  У машины имеются 32-разрядное адресное пространство и страницы размером 

8 Кбайт. Таблица страниц имеет полную аппаратную поддержку, и на каждую ее 
запись отводится одно 32-разрядное слово. При запуске процесса таблица страниц 
копируется из памяти в аппаратуру машины, при этом на копирование одного 
слова тратится 100 нс. Какая доля процессорного времени тратится на загрузку 
таблицы страниц, если каждый процесс работает в течение 100 мс (включая время 
загрузки таблицы страниц)?

15.  Предположим, что у машины 48-разрядная виртуальная адресация и 32-разрядные 

физические адреса.
а)  Если размер страницы равен 4 Кбайт, то сколько записей будет в таблице стра-

ниц, имеющей только один уровень? Обоснуйте ответ.

б)  Предположим, что у этой же системы имеется буфер быстрого преобразования 

адреса — TLB, у которого 32 записи. Далее предположим, что в программе 
имеются команды, помещающиеся на одну страницу, и они последовательно 
считывают элементы формата длинного целого числа из массива, содержащего 
тысячи страниц. Насколько эффективна будет TLB в этом случае?

16.  У вас есть следующие данные о системе виртуальной памяти:

а)  TLB может хранить 1024 записи и может быть доступен за 1 тактовый цикл 

(1 нс).

б)  Запись таблицы страниц может быть найдена за 100 тактовых циклов, или 

100 нс.

в) Среднее время замещения страницы составляет 6 мс.

17.  Если ссылки на страницы обслуживаются с помощью TLB 99 % времени и только 

в 0,01 % случаев возникает ошибка отсутствия страницы, каким будет эффектив-
ное время преобразования адреса?

18.  Допустим, что в машине используются 38-разрядная виртуальная адресация 

и 32-разрядная физическая адресация.

а)  Каково основное преимущество многоуровневой таблицы страниц над одно-

уровневой?

б)  Сколько бит должно быть отведено под поле таблицы страниц самого верхнего 

уровня и под поле таблицы страниц следующего уровня при двухуровневой 
таблице страниц, страницах объемом 16 Кбайт и записях размером 4 байта? 
Обоснуйте ответ.

19. В разделе 3.3.4 утверждалось, что Pentium Pro расширяет каждую запись в ие-

рархии таблиц страниц до 64 разрядов, но по-прежнему может адресовать только 
4 Гбайт памяти. Объясните, как данное утверждение может быть истинным, когда 
у записей таблиц страниц имеется 64 разряда?

20.  Компьютер с 32-разрядным адресом использует двухуровневую таблицу страниц. 

Виртуальные адреса разбиты на 9-разрядное поле таблицы страниц верхнего уров-
ня, 11-разрядное поле таблицы страниц второго уровня и смещение. Чему равен 
размер страниц и сколько их в адресном пространстве?

21.  Компьютер поддерживает 32-разрядные виртуальные адреса и страницы размером 

4 Кбайт. Программа и данные умещаются в самой младшей странице (0–4095). 
Стек размещается в самой старшей странице. Сколько записей в таблице страниц 

294  

 Глава 3. Управление памятью 

необходимо для этого процесса, если используется традиционная (одноуровне-
вая) страничная структура? Сколько записей в таблице страниц требуется при 
двухуровневой страничной структуре, у которой каждая часть имеет 10 разрядов?

22.  Далее показана трассировка выполнения фрагмента программы на компьютере 

с 512-байтными страницами. Программа находится по адресу 1020, и ее указатель 
стека имеет значение 8192 (стек растет по направлению к 0). Дайте строку ссылки 
на страницу, сгенерированную этой программой. Каждая инструкция занимает 
4 байта (1 слово), включая непосредственно указанные константы. Обе ссылки, 
как на инструкцию, так и на данные, вычисляются в строке ссылки.

Загрузка слова 6144 в регистр 0.

Помещение значения регистра 0 в стек.

Вызов процедуры по адресу 5120 с помещением в стек возвращаемого адреса.

Вычитание непосредственно указанной константы 16 из указателя стека.

Сравнение фактического параметра с непосредственно указанной константой 4.

Переход при равенстве на адрес 5152.

23.  Компьютер, у которого процессы имеют адресные пространства по 1024 стра-

ницы, хранит таблицы страниц в памяти. На чтение слова из таблицы страниц 
затрачивается 5 нс. Чтобы уменьшить затраты, в компьютере используется бу-
фер быстрого преобразования адреса (TLB), содержащий 32 пары (виртуальная 
страница, физический страничный блок), который может выполнить поиск за 1 нс. 
Каким должно быть соотношение успешных обращений к буферу, чтобы средние 
издержки снизились до 2 нс?

24. Как может устройство ассоциативной памяти, необходимое буферу TLB, быть 

реализовано аппаратно и каково влияние такой конструкции на расширяемость 
архитектуры?

25.  Машина поддерживает 48-разрядные виртуальные адреса и 32-разрядные фи-

зические адреса. Размер страницы равен 8 Кбайт. Сколько должно быть записей 
в таблице страниц?

26.  Компьютер с размером страницы 8 Кбайт, объемом оперативной памяти 256 Кбайт 

и размером виртуального адресного пространства 64 Гбайт использует для реа-
лизации своей виртуальной памяти инвертированную таблицу страниц. Каков 
должен быть размер хэш-таблицы, чтобы обеспечить среднее значение длины 
хэш-цепочки меньше 1? Предположим, что размер хэш-таблицы кратен степени 
числа 2.

27.  Студент, изучающий курс конструирования компиляторов, предложил профессору 

проект написания компилятора, получающего список страничных обращений, ко-
торый может использоваться для реализации оптимального алгоритма замещения 
страниц. Возможно ли это? Почему возможно или невозможно? Существует ли 
какой-нибудь способ, который мог бы повысить эффективность страничной под-
качки во время работы программы?

28.  Предположим, что поток обращений к виртуальным страницам содержит повто-

рения длинных последовательностей обращений к страницам, за которыми время 
от времени следуют произвольные обращения к страницам. К примеру, следующая 
последовательность: 0, 1, ... , 511, 431, 0, 1, ... , 511, 332, 0, 1... состоит из повторений 

Вопросы  

295

последовательности 0, 1, ... , 511, за которой следует произвольное обращение 
к страницам 431 и 332.

а)  Почему стандартные алгоритмы замещения страниц (LRU, FIFO, «часы») не 

смогут эффективно справляться с нагрузкой по распределению страниц, кото-
рая будет меньше, чем длина последовательности?

б)  Если этой программе было выделено 500 страничных блоков, то опишите под-

ход к замещению страниц, который имел бы намного лучшую производитель-
ность, чем алгоритмы LRU, FIFO или «часы».

29.  Если в системе с четырьмя страничными блоками и восемью страницами ис-

пользуется алгоритм замещения страниц FIFO, то сколько ошибок отсутствия 
страниц произойдет для последовательности обращений 0172327103 при условии, 
что четыре страничных блока изначально пусты? А теперь решите эту задачу для 
алгоритма LRU.

30.  Рассмотрим последовательность страниц, показанную на рис. 3.14, б. Предпо-

ложим, что биты R для страниц от B до A равны 11011011. Какая страница будет 
удалена при использовании алгоритма «второй шанс»?

31.  У небольшого компьютера на смарт-карте имеется четыре страничных блока. Во 

время первого такта системных часов биты R равны 0111 (у страницы 0 бит R ра-
вен 0, у остальных — 1). Во время последующих тактов системных часов биты R 
принимают значения 1011, 1010, 1101, 0010, 1010, 1100 и 0001. Напишите четыре 
значения, которые примет счетчик после последнего такта при использовании 
алгоритма старения с 8-разрядным счетчиком.

32. Приведите 

простой 

пример последовательности обращений к страницам, в котором 

первые страницы, выбранные для удаления, различались бы для алгоритмов замеще-
ния страниц «часы» и LRU. Предположим, что процессу выделены три страничных 
блока и строка обращений содержит номера страниц из набора 0, 1, 2, 3.

33.  В алгоритме WSClock (см. рис. 3.19, в) стрелка указывает на страницу с битом 

R = 0. Будет ли удалена эта страница, если t = 400? Будет ли она удалена, если 
t = 1000?

34.  Предположим, что алгоритм замещения страниц WSClock использует значение t, 

равное двум тактам, и состояние системы имеет следующий вид:

Страница

Отметка времени

V

R

M

0

6

1

0

1

1

9

1

1

0

2

9

1

1

1

3

7

1

0

0

4

4

0

0

0

где три флаговых бита, V, R и M, означают соответственно Valid (приемлемая), 
Referenced (были обращения) и Modified (измененная).

а)  Покажите содержимое новых записей таблицы после того, как на такте 10 про-

изошло прерывание от таймера. Дайте им объяснения. (Записи, не подвергши-
еся изменению, можно опустить.)

б)  Предположим, что вместо прерывания от таймера на такте 10 произошла ошиб-

ка отсутствия страницы, связанная с запросом на чтение страницы 4. Покажите