Вопросы 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 Мбайт. Какие свободные участки берутся для следующих последовательных запросов сегмента:

а) 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. Объем пространства на диске, который должен быть доступен для хранения страниц, связан с максимальным количеством процессов п, количеством байтов в виртуальном адресном пространстве v и числом байтов в оперативной памяти г. Выведите формулу минимально необходимого дискового пространства. Насколько эта величина реалистична?

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

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). Стек размещается в самой старшей странице. Сколько записей в таблице страниц необходимо для этого процесса, если используется традиционная (одноуровневая) страничная структура? Сколько записей в таблице страниц требуется при двухуровневой страничной структуре, у которой каждая часть имеет 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... состоит из повторений последовательности 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, означают соответственно Valid (приемлемая), Referenced (были обращения) и Modified (измененная).

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

б) Предположим, что вместо прерывания от таймера на такте 10 произошла ошибка отсутствия страницы, связанная с запросом на чтение страницы 4. Покажите содержимое новых записей таблицы. Дайте им объяснения. (Записи, не подвергшиеся изменению, можно опустить.)

35.

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

а) Что является таким атрибутом для алгоритма FIFO? Алгоритма LRU? Оптимального алгоритма?

б) Дайте общий алгоритм для этих алгоритмов замещения страниц.

36. Сколько времени займет загрузка программы размером 64 Кбайт с диска, у которого среднее время поиска составляет 5 мс, время раскрутки — 5 мс, а дорожки содержат по 1 Мбайт:

а) при размере страниц 2 Кбайт;

б) размере страниц 4 Кбайт?

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

37. У компьютера имеется четыре страничных блока. Время загрузки, время последнего обращения и биты R и M для каждой страницы приведены далее (время дано в тактах системных часов).


Какая страница будет удалена при использовании алгоритма:

а) NRU;

б) FIFO;

в) LRU;

г) «второй шанс»?

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

а) При каких условиях обновление таблицы страниц для процесса Б должно быть задержано даже при том, что обработка ошибки отсутствия страницы процесса А приведет к помещению совместно используемой страницы в память? Объясните.

б) Какова потенциальная стоимость задержки обновления таблицы страниц?

39. Рассмотрим следующий двумерный массив: int X[64][64];

Предположим, что система имеет четыре страничных блока по 128 слов (в одно слово помещается целочисленное значение). Программа, работающая с массивом X, помещается как раз на одной странице и всегда занимает страницу по адресу 0. А для подкачки данных используются оставшиеся три страничных блока. Массив X хранится в порядке старшинства строк (то есть в памяти Х[0][1] следует за Х[0][0]). Какой из приведенных далее фрагментов кода сгенерирует наименьшее количество ошибок отсутствия страниц? Обоснуйте свой ответ и подсчитайте общее количество таких ошибок.

41.
Одна из первых машин с системой разделения времени, PDP-1 компании DEC, имела память объемом 4 К 18-разрядных слов. В каждый конкретный момент времени она содержала в памяти один процесс. Когда планировщик принимал решение о запуске другого процесса, находящийся в памяти процесс записывался на страничный барабан с 4 К 18-разрядных слов по окружности барабана. Запись на барабан или чтение с него могли начинаться не только с нулевого, но и с любого другого слова. Как вы думаете, почему был выбран именно магнитный барабан?

42. Компьютер выделяет каждому процессу 65 536 байт адресного пространства, которое разделено на страницы по 4096 байт. У рассматриваемой программы текст занимает 32 768 байт, данные — 16 386 байт, а стек — 15 870 байт. Поместится ли эта программа в адресном пространстве машины? А если бы размер страницы был не 4096, а 512 байт, смогла бы тогда поместиться эта программа? На каждой странице должны содержаться либо текст, либо данные, либо стек, но не смесь двух или трех этих компонентов.

43. Было замечено, что количество команд, выполненных между ошибками отсутствия страницы, прямо пропорционально количеству выделенных программе страничных блоков. При удвоении доступной памяти удваивается и средний интервал между ошибками отсутствия страницы. Предположим, что обычная команда выполняется за 1 мкс, но если возникает ошибка отсутствия страницы, то она выполняется за 2001 мкс (то есть на обработку ошибки затрачивается 2 мс). Если время выполнения программы занимает 60 с и за это время возникает 15 000 ошибок отсутствия страницы, то сколько времени заняло бы выполнение программы при удвоении объема доступной памяти?

44. Группа разработчиков операционной системы для Frugal Computer Company обдумывает способ снижения объема резервного хранилища, необходимого для их
новой разработки. Ведущий специалист предложил вообще не сохранять текст программы в области подкачки, а просто загружать его постранично по мере надобности непосредственно из двоичного файла. Существуют ли условия, при которых этот замысел может быть осуществлен для текста программы? Существуют ли условия, при которых он может быть применен в отношении данных?

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

46. Объясните разницу между внутренней и внешней фрагментацией. Какая из них возникает в системах со страничной организацией? Какая из них возникает в системах, использующих чистую сегментацию?

47. При поддержке и сегментации, и страничной организации памяти, как в системе MULTICS, сначала должен быть найден дескриптор сегмента, а затем идентификатор страницы. Может ли таким же образом при двухуровневом поиске работать и буфер быстрого преобразования адреса (TLB)?

48. Рассмотрим программу, у которой есть два показанных далее сегмента: содержащий команды сегмент 0 и содержащий данные, используемые в режиме чтения и записи, сегмент 1. У сегмента 0 имеется защита, позволяющая производить только чтение и выполнение, а у сегмента 1 есть защита, позволяющая производить только чтение и запись. Система памяти относится к виртуальным системам с подкачкой страниц по требованию, у которой есть 4-разрядный номер страницы и 10-разрядное смещение. Таблицы страниц и защита находятся в следующем состоянии (все числа в таблице являются десятичными).


Для всех приведенных далее случаев либо дайте реальный (фактический) адрес памяти, получающийся в результате динамического преобразования адреса, либо идентифицируйте тип возникающей ошибки (которая может быть либо ошибкой отсутствия страницы, либо ошибкой защиты):

а) извлечь данные из сегмента 1, страницы 1, из адреса со смещением 3;

б) сохранить данные в сегменте 0, странице 0, в адресе со смещением 16;

в) извлечь данные из сегмента 1, страницы 4, из адреса со смещением 28;

г) передать управление ячейке в сегменте 1, странице 3, со смещением 32.

49. Можете ли вы представить ситуацию, при которой была бы неприемлема идея поддержки виртуальной памяти? Что можно было бы извлечь полезного из отсутствия поддержки виртуальной памяти? Обоснуйте ответ.

50. В виртуальной памяти предоставляется механизм для изолирования одного процесса от другого. Какие трудности в управлении памятью могут возникать, если разрешить одновременную работу двух операционных систем? Как эти трудности можно разрешить?

51. Постройте гистограмму и вычислите средний и медианный размеры исполняемых двоичных файлов на своем компьютере. В системе Windows следует взять в расчет все файлы с расширениями .exe и .dll, в системе UNIX — все исполняемые файлы в каталогах /bin, /usr/bin и /local/bin, не являющиеся сценариями (или воспользуйтесь утилитой file, чтобы найти все исполняемые файлы). Принимая во внимание внутреннюю фрагментацию и размер таблицы страниц, сделайте обоснованные предположения о размере записи в таблице страниц. Считайте, что все программмы запускаются с одинаковой частотой и поэтому должны учитываться на равных началах.

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

53. Напишите программу, моделирующую миниатюрную систему подкачки, использующую алгоритм WSClock. Система считается миниатюрной, поскольку будет построена на предположении об отсутствии ссылок на запись (что не слишком реалистично), а прекращение процесса и его создание проигнорированы (вечная жизнь). Входными данными будут:

• пороговое значение периода восстановления;

• интервал прерывания от таймера, выраженный в виде количества обращений к памяти;

• файл, содержащий последовательность ссылок на страницы.

а) Опишите основную структуру данных и алгоритмы в вашей реализации.

б) Покажите, что модель ведет себя ожидаемо для простого (но нетривиального) примера ввода.

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

г) Объясните, что нужно для расширения программы для обслуживания потока ссылок на страницы, который также включает записи.

54. Напишите программу, демонстрирующую влияние отсутствия нужных записей в буфере TLB на эффективное время доступа к памяти, путем измерения времени каждого доступа, затрачиваемого на проход большого массива.

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

б) Запустите программу на компьютере и опишите, насколько полученные данные оправдали ваши ожидания.

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

55. Напишите программу, демонстрирующую разницу между использованием локальной и глобальной политики замещения страниц для простого случая использования двух процессов. Вам понадобится подпрограмма, генерирующая строку обращений к страницам на основе статистической модели. У этой модели есть N состояний, пронумерованных от 0 до N - 1, которые представляют каждое из возможных обращений к страницам, а вероятностьp1, связанная с каждым состоянием i, означает возможность того, что следующее обращение будет к той же самой странице. В противном случае следующее обращение будет к одной из других страниц с равной для всех них вероятностью.

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

б) Вычислите уровень ошибок отсутствия страницы для примера, в котором имеется один процесс и фиксированное количество страничных блоков. Объясните правильность поведения программы.

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

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

56. Напишите программу, которая может быть использована для сравнения эффективности добавления поля тега к записям TLB, когда управление передается между двумя программами. Поле тега используется для эффективного обозначения каждой записи идентификатором процесса. Учтите, что TLB без тега может быть смоделирован путем выставления требования, чтобы у всех записей TLB в любое время имелся один и тот же тег. В качестве входных данных будут использоваться:

• количество доступных записей TLB;

• интервал прерывания от таймера, выраженный в виде количества обращений к памяти;

• файл, содержащий последовательность записей (процесс, ссылки на страницы);

• цена обновления одной TLB-записи entry.

а) Опишите основную структуру данных и алгоритмы в вашей реализации.

б) Покажите, что модель ведет себя ожидаемо для простого (но нетривиального) примера ввода.

в) Постройте график функции, отображающий количество обновлений TLB на 1000 обращений к памяти.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Вопросы 1.:

  1. Основные ошибки при задавании вопросов. Слишком открытые вопросы.
  2. ВОПРОС О РЕЛИГИИ - ЭТО ВОПРОС О ВЛАСТИ Молитва Господня и семейные порядки
  3. Вопросы без альтернатив, или открытые вопросы
  4. 2.6. Умеем ли мы задавать вопросы? Классификация типов вопросов
  5. § 9 Критика гражданской формы брака. – Вопрос о введении ее в русское законодательство. – Браки у раскольников и вопрос о законности сих браков.
  6. Вопрошающее наблюдение: вопрос без вопроса
  7. 7.1. СКРЫТЫЕ ВОПРОСЫ
  8. 3.3.1. Неструктурированные вопросы
  9. Вопросы
  10. Вопросы
  11. Ключевой вопрос
  12. Наводящие вопросы.
  13. Закрытые вопросы.
  14. Подготовительные вопросы.