Вопросы 335

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

В MINIX драйверы устройств реализованы в виде процессов, встроенных в ядро. Мы рассмотрели драйверы RAM-диска, жесткого диска, часов и драйвер терминала. Задача синхронного таймера и задача системы не являются драйверами устройств, но имеют точно такую же структуру. У каждой из этих задач есть главный цикл, в котором принимаются и обрабатываются запросы, в конечном итоге формируется и отправляется ответное сообщение о результатах. Все задачи разделяют общее адресное пространство. Задачи RAM-диска, жесткого диска и гибкого диска используют один общий главный цикл и разделяют некоторые функции. Тем не менее каждая задача является независимым процессом. Несколько различных терминалов на системной консоли, последовательные интерфейсы и сетевые подключения обслуживаются единственной задачей терминала.

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

Вопросы

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

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

Основываясь на скорости вращения и геометрии дисков дисковода и жесткого диска, скажите, какова битовая скорость обмена данными между бу-

ферами контроллера и самим диском. Сравните с другими формами ввода/вывода (последовательные линии и сеть).

4. Представьте себе гибкий диск, у которого шаг чередования секторов равен двум, как на рис. 3.3, в. На каждой дорожке диска восемь секторов по 512 байт. Скорость врашения диска 300 об/мин. Сколько времени потребуется, чтобы прочитать все секторы дорожки в правильном порядке, если предположить, что головка диска уже позиционирована на нужную дорожку, а чтобы сектор О переместился под головку, требуется 1 /2 оборота диска? Чему равна скорость считывания данных? Теперь повторите то же задание для диска без чередования с теми же характеристиками. Как сильно снижается скорость из-за чередования?

5. Коммутатор терминалов DM-11, который давным-давно использовался на PDP-11, чтобы определить, является ли входяший бит единицей или нулем, считывал значение с каждой из линий в семь раз чаше скорости передачи данных. Считывание значения с одной линии требует 5,7 мс. Сколько линий со скоростью 1200 бод мог бы поддерживать DM-11?

6. Локальная сеть используется следующим образом. Пользователь обращается к системному вызову, чтобы записать пакеты данных в сеть. Затем операционная система копирует данные в буфер ядра. После этого данные копируются в схему сетевого адаптера. После того как все байты попадают в контроллер, они посылаются по сети со скоростью 10 Мбит/с. Получающий данные сетевой контроллер сохраняет каждый бит спустя 1 мкс после его отправки. Когда последний бит получен, центральный процессор компьютера-адресата прерывается, и ядро копирует прибывший пакет в свой буфер, чтобы исследовать его. Поняв, какому пользователю предназначается пакет, ядро копирует данные в пространство пользователя. Если предположить, что каждое прерывание и его обработка занимает 1 мс, размер пакетов равен 1024 байт (не считая заголовков), а копирование одного байта 1 мкс, то чему будет равна максимальная скорость, с которой один процесс может передавать данные другому процессу? Предположите, что отправитель блокируется, пока получатель не закончит работу и не отправит обратно подтверждение. Для простоты допустим, что временем получения подтверждения можно пренебречь.

7. Что такое независимость от устройств?

8. В каком из четырех уровней программного обеспечения ввода/вывода выполняются следующие действия:

1) вычисление номеров дорожки, сектора и головки для чтения диска;

2) поддержание кэша последних блоков;

3) запись команд в регистры устройства;

4) проверка разрешения доступа пользователя к устройству;

5) преобразование двоичного целого числа в А5СП-символы для вывода на печать.

9. Почему файлы, посылаемые на принтер, обычно перед печатью накапливаются на диске?

10. Рассмотрим рис. 3.6. Предположим, что на шаге п процесс С вместо ресурса R запрашивает ресурс S. Приведет ли это к взаимоблокировке? А если он запросит оба ресурса, то есть и S и R?

И. Внимательно посмотрите на рис. 3.8, б. Если процесс D запросит еще одну единицу, приведет это к безопасному состоянию или к небезопасному? Что будет, если запрос поступит от процесса С вместо процесса D?

12. Все траектории на рис. 3.9 горизонтальны или вертикальны. Можете ли вы представить себе условия, при которых также были бы возможны наклонные траектории?

13. Предположим, процесс А на рис. 3.10 запросил последний ленточный накопитель. Приведет ли это к взаимной блокировке?

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

15. Может ли система находиться в состоянии, не являющимся ни состоянием взаимоблокировки, ни безопасным состоянием? Если да, приведите пример. Если нет, докажите, что все состояния либо являются тупиками, либо они безопасны.

16. Распределенная система, использующая почтовые ящики, имеет два примитива межпроцессного взаимодействия: send (послать) и receive (получить). Второй примитив указывает процесс, от которого следует получить сообщение, и блокируется, если сообщения от процесса недоступны, даже несмотря на то, что могут ожидаться сообщения от других процессов. Здесь нет общих ресурсов, но процессам необходимо часто связываться друг с другом относительно других вопросов. Возможна ли взаимоблокировка? Аргументируйте ответ.

17. Сотни одинаковых процессов в электронных системах межбанковского перевода денежных средств работают следующим образом. Каждый процесс читает входную строку, определяющую количество денег для перевода, кредитовый и дебетовый счета. Затем он блокирует оба счета и выполняет транзакцию, а после завершения перевода снимает блокировку. При параллельно работающем большом количестве процессов существует опасность, что, имея заблокированным счет х, процесс будет неспособен заблокировать счет у, поскольку счет у уже окажется заблокированным процессом, в данный момент ожидающим счет х. Разработайте схему действия, избегающую взаимоблокировок. Не освобождайте запись счета до тех пор, пока вы не закончите транзакцию. (Иначе говоря, не позволяются решения, в которых один счет блокируется и затем немедленно освобождается, если другие счета заблокированы.)