Файл: Tannenbaum.pdf

Вопросы и задания 513

9. Некоторые компьютеры позволяют осуществлять ввод-вывод непосред-

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

10. Операционные системы, в которых допускаются проецируемые в память

файлы, всегда требуют, чтобы файлы были отображены в границах страниц.

Например, если у нас есть страницы по 4 К, файл может быть отображен,

начиная с виртуального адреса 4096, но не с виртуального адреса 5000. Зачем
это нужно?

11. При загрузке сегментного регистра в Pentium II вызывается соответствую-

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

12. Программа в компьютере Pentium II обращается к локальному сегменту 10

со смещением 8000. Поле BASE сегмента 10 в локальной таблице дескрип-
торов содержит число 10000. Какой элемент таблицы страниц использует
Pentium II? Каков номер страницы? Каково смещение?

13. Рассмотрите возможные алгоритмы для удаления сегментов в сегментиро-

ванной памяти без страничной организации.

14. Сравните внутреннюю фрагментацию с внешней фрагментацией. Что мож-

но сделать, чтобы улучшить каждую из них?

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

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

дукт нужно убрать, чтобы освободить место для нового продукта. Мы знаем
два алгоритма: LRU и FIFO. Какой из них вы бы предпочли?

16. Почему блоки кэш-памяти всегда намного меньше, чем страницы в вирту-

альной памяти (бывает даже, что в 100 раз меньше)?

17. Почему многие системы файлов требуют, чтобы файл перед прочтением

явным образом открывался с помощью системного вызова

 open?

18. Сравните применение битового отображения и списка неиспользованных

пространств для слежения за свободным пространством на диске. Диск со-
стоит из 800 цилиндров, на каждом из которых расположено 5 дорожек по
32 сектора. Сколько понадобится «дырок», чтобы список «дырок» (список
свободной памяти) стал больше, чем битовое отображение? Предполагает-
ся, что единичный блок — это сектор и что для «дырки» требуется 32-бит-
ный элемент таблицы.

19. Чтобы сделать некоторые прогнозы относительно производительности дис-

ка, нужно иметь модель распределения памяти. Предположим, что диск рас-
сматривается как линейное адресное пространство из N» 1 секторов. Здесь
сначала идет последовательность блоков данных, затем неиспользованное
пространство, затем другая последовательность блоков данных и т. д. Эм-
пирические измерения показывают, что вероятностные распределения для

5 1 4 Глава 6. Уровень операционной системы

длин данных и неиспользованных пространств одинаковы, причем для

каждого из них вероятность быть

 i

 секторов составляет

 2''.

 Каково при этом

ожидаемое число «дырок» на диске?

20. На определенной машине программа может создавать столько файлов, сколь-

ко ей нужно, и все файлы могут увеличиваться в размерах во время выпол-

нения программы, причем операционная система не получает никаких до-

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

файлы в последовательных секторах? Поясните.

21. Рассмотрим один метод реализации команд для работы с семафорами. Вся-

кий раз, когда центральный процессор собирается совершить команду up или
down над семафором (семафор — это целочисленная переменная в памяти),
сначала он устанавливает приоритет центрального процессора таким обра-

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

ду процессами каждые 100 миллисекунд?

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

ложен семафор?

22. Компания, разрабатывающая операционные системы, получает жалобы от

своих клиентов по поводу последней разработки, которая поддерживает опе-

рации с семафорами. Клиенты решили, что аморально со стороны процес-

сов приостанавливать свою работу (то есть спать на работе). Чтобы угодить

своим клиентам, компания решила добавить третью операцию,

 peek.

 Эта

операция просто проверяет семафор, но не изменяет его и не блокирует про-

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

семафором операцию

 down.

 Будет ли эта идея работать, если семафор ис-

пользуют три и более процессов? А если два процесса?

23. Составьте таблицу, в которой в виде функции от времени от 0 до 1000 милли-

секунд показано, какие из трех процессов PI, P2 и РЗ работают, а какие бло-
кированы. Все три процесса выполняют команды up и down над одним и тем
же семафором. Если два процесса блокированы и совершается команда up,
то запускается процесс с меньшим номером, то есть Р1 имеет преимущество
над Р2 и РЗ и т. д. Изначально все три процесса работают, а значение сема-
фора равно 1.
При t=100 P1 совершает down.
При t=200 PI совершает down.
При t=300 PI совершает up.
При t=400 PI совершает down.
При t=500 PI совершает down.
При t=600 PI совершает up.
При t=700 PI совершает down.
При t=800 PI совершает up.
При t=900 PI совершает up.

Вопросы и задания 515

24. В системе бронирования билетов на авиарейсы необходимо быть уверен-

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

лу (предполагается, что процессы подчиняются правилам).

25. Чтобы сделать возможной реализацию семафоров на компьютере с несколь-

кими процессорами, которые разделяют общую память, разработчики вклю-
чают в машину команду для проверки и блокирования. Команда TSL X прове-
ряет ячейку X. Если содержание равно 0, семафоры устанавливаются на 1 за
один неделимый цикл памяти, а следующая команда пропускается. Если
содержание ячейки не равно О, TSL работает как пустая операция. Используя
TSL, можно написать процедуры

 lock

 и

 unlock

 со следующими свойствами:

lock{x)

 проверяет, заперт ли

 х.

 Если нет, эта процедура запирает

 х

 и возвра-

щает управление;

 unlock

 отменяет существующую блокировку. Если

 х

 уже

заперт, процедура просто ждет, пока он не освободится, и только после этого
запирает

 х

 и возвращает управление. Если все процессы запирают таблицу

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

 lock

 и

unlock

 на ассемблере.

26. Каково будет значение

 in

 и

 out

 для кольцевого буфера длиной в 65 слов по-

сле каждой из следующих операций? Изначально значения

 in

 и

 out

 равны 0.

а. 22 слова помещаются в буфер;
б. 9 слов удаляются из буфера;
в. 40 слов помещаются в буфер;
г. 17 слов удаляются из буфера;
д. 12 слов помещаются в буфер;
е. 45 слов удаляются из буфера;
ж. 8 слов помещаются в буфер;
з. 11 слов удаляются из буфера.

27. Предположим, что одна из версий UNIX использует 2 К блоков на диске и

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

28. Предположим, что системный вызов UNIX

unlink("/usr/ast/bin/game3")

был выполнен в контексте рис. 6.27. Опишите подробно, какие изменения
произойдут в системе директорий.

29. Представьте, что вам нужно реализовать систему UNIX на микрокомпьюте-

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

5 1 6 Глава 6. Уровень операционной системы

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

30. Комиссия по защите дескрипторов файлов выдвинула протест против сис-

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

31. В системе NT можно составить список управления доступом таким обра-

зом, чтобы один пользователь не имел доступа ни к одному из файлов, а все
остальные имели полный доступ к ним. Как это можно реализовать?

32. Опишите два способа программирования работы процессора-производителя

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

33. Работу алгоритмов замещения страниц обычно проверяют путем моделиро-

вания. Предположим, что вам нужно написать моделирующую программу

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

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

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

34. Напишите программу для UNIX или NT, которая на входе получает имя

директории. Программа должна печатать список файлов этой директории,
каждый файл на отдельной строке, а после имени файла должен печататься
размер файла. Имена файлов должны располагаться в том порядке, в кото-
ром они появляются в директории. Неиспользованные слоты в директории
должны выводиться с пометой (неиспользованный).

Глава 7

Уровень языка ассемблера

В четвертой, пятой и шестой главах мы обсуждали три уровня, которые имеются

в большинстве современных компьютеров. В этой главе речь пойдет о еще одном

уровне, который также присутствует практически во всех современных машинах.

Это уровень языка ассемблера. Уровень языка ассемблера существенно отлича-

ется от трех предыдущих, поскольку он реализуется с помощью трансляции, а не

с помощью интерпретации.

Программы, которые преобразуют пользовательские программы, написанные

на каком-либо определенном языке, в другой язык, называются

 трансляторами.

Язык, на котором изначально написана программа, называется

 входным языком,

а язык, на который транслируется эта программа, называется

 выходным языком.

Входной язык и выходной язык определяют уровни. Если имеется процессор, ко-

торый может выполнять программы, написанные на входном языке, то нет необ-

ходимости транслировать исходную программу на другой язык.

Трансляция используется в том случае, если есть аппаратный или программ-

ный процессор для выходного языка и нет процессора для входного языка. Если

трансляция выполнена правильно, то оттранслированная программа будет давать

точно такие же результаты, что и исходная программа (если бы существовал под-

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

который сначала будет транслировать программы на выходной уровень, а затем

выполнять полученные программы.

Важно понимать разницу между трансляцией и интерпретацией

1

. При транс-

ляции исходная программа на входном языке не выполняется сразу. Сначала она

преобразуется в эквивалентную программу, так называемую

 объектную програм-

му,

 или

 исполняемую двоичную программу,

 которая выполняется только после

завершения трансляции. При трансляции нужно пройти следующие два шага:

1. Создание эквивалентной программы на выходном языке.

2. Выполнение полученной программы.
Эти два шага выполняются не одновременно. Второй шаг начинается только

после завершения первого. В интерпретации есть только один шаг: выполнение

исходной программы. Никакой эквивалентной программы порождать не нужно,

хотя иногда исходная программа преобразуется в промежуточную форму (напри-

мер, в код Java) для упрощения интерпретации.

В отечественной литературе принято и интерпретацию, и компиляцию (именно компиляцию автор

здесь называет трансляцией) называть трансляцией. Другими словами, трансляторы могут быть либо

компиляторами, либо интерпретаторами. —

 Примеч. научн. ред.