18. Алгоритм банкира работает в системе, где есть т. классов ресурсов и п процессов. При стремящихся к бесконечности mvin количество операций, которое нужно выполнить для проверки безопасности состояния, пропорционально тпи*. Что представляют собой величины а и Ь?

19. Золушка и Принц расторгают брак. Чтобы разделить свое имущество, они согласились на следующий алгоритм. Каждое утро любой из них может послать письмо адвокату другого, в котором запрашивает один предмет имущества. Поскольку день уходит на доставку писем, они пришли к соглашению, что если оба обнаруживают, что запросили один и тот же предмет в один и тот же день, на следующий день они посылают письмо с отменой запроса. Среди прочего имущества у них есть собака Буфер, конура Буфера, их канарейка Твитер и клетка Твитера. Животные любят свои жилища, поэтому было принято соглашение, что любой вариант раздела имущества, отделяющий животное от его дома, является недействительным, после которого весь раздел имущества требуется начать заново. И Золушка и Принц отчаянно хотят заполучить Буфера. Поскольку они могут уехать (отдельно друг от друга) в отпуск, каждый супруг запрограммировал персональный компьютер для обработки переговоров. Когда они возвращаются из отпусков, компьютеры все еще ведут переговоры. Почему? Возможна ли взаимоблокировка? Возможно ли голодание ? Аргументируйте ответ.

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

21. Драйвер диска получает запросы на чтение/запись к цилиндрам 10, 22, 20, 2, 40, 6 и 38. Перемещение блока головок с одного цилиндра на соседний занимает 6 мс. Сколько потребуется времени на перемещение головок при использовании алгоритма:

1) обслуживания в порядке поступления запросов;

2) обслуживания в первую очередь ближайшего цилиндра;

3) элеваторного (сначала блок головок двигается вверх);

4) во всех случаях начальное положение блока головок на цилиндре 20.

22. Продавец персональных компьютеров, посещая университет на юго-западе Амстердама для продажи партии компьютеров, заявляет, что его компания приложила существенные усилия по ускорению их версии UNIX. В качестве примера он отмечает, что в их драйвере диска применяется элеваторный алгоритм, а также обслуживание очереди запросов к одному цилиндру в порядке секторов. На студента Гарри Хакера его речь производит настолько сильное впечатление, что он покупает один компьютер. Гарри приносит компьютер домой и пишет программу, читающую случайные 10 ООО блоков диска. К его изумлению, замеренная им производительность идентична той, которой можно было ожидать при использовании алгорит-

Вопросы 339

ма обслуживания запросов в порядке поступления. Означает ли это, что продавец лгал?

23. В UNIX каждый процесс состоит из двух частей: в адресном пространстве пользователя и ядра. Является ли ядерная часть подпрограммой или сопрограммой?

24. На некотором компьютере обработчик прерываний от таймера выполняет свои действия за 2 мс (включая накладные расходы по переключению процессов). Прерывания от таймера поступают с частотой 60 Гц. Какая часть времени работы центрального процессора расходуется на таймер?

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

26. Почему терминалы, использующие интерфейс RS-232, управляются прерываниями, а терминалы с отображением на память - нет?

27. Рассмотрим работу терминала. Драйвер посылает один символ, после чего блокируется. За передачей символа в линию следует прерывание, затем драйвер разблокируется и посылает следующий символ и т. д. Какую часть времени центрального процессора занимает управление модемом, если обработка прерывания, вывод одного символа и каждая блокировка требует 4 мс? Будет ли этот метод работать с линиями 110 бод? А что насчет линий 4800 бод?

28. Вообразите в памяти терминал, содержащий 1200 х 800 пикселов. Для прокрутки окна центральный процессор (или контроллер) должен переместить все строки текста вверх, копируя их биты из одной части видеопамяти в другую. Допустим, в окне 66 строк по 80 символов в строке (всего 5280 символов), а каждый символ имеет 8 пикселов в щирину и 16 пикселов в высоту. Сколько времени займет прокрутка всего окна, если для копирования одного байта требуется 500 не? Если все строки имеют по 80 символов в длину, чему будет равна эквивалентная скорость терминала в бодах? Помещение одного символа на экран занимает 50 мкс. Подсчитайте скорость, если терминал цветной, 4 бит/пиксел.

29. Для чего в операционных системах нужны ESC-последовательности, например CTRL+V в MINIX?

30. Получив символ DEL (SIGINT), драйвер экрана MINIX очищает всю очередь на вывод для этого экрана. Почему?

31. У многих терминалов, использующих интерфейс RS-232, есть ESC-последовательности для удаления текущей строки и перемещения всех нижних строк на одну строку вверх. Как, по-вашему, реализована эта операция внутри терминала?

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

дый из которых помещается в квадрат 8x8 пикселов. Каждый ряд из 640 пикселов рисуется за один горизонтальный проход луча, что занимает 63,6 мкс, включая горизонтальное обратное движение луча. Экран перерисовывается 60 раз/с. При каждом выводе экрана требуется период времени на вертикальный обратный ход луча. Какую часть времени видеопамять оказывается доступной для записи?

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

34. Модифицируйте драйвер дисковода в MINIX, реализовав кэширование дорожек.

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

36. Реализуйте системный вызов UNIX profil, которого нет в MINIX.

37. Измените драйвер терминала в MINIX так, чтобы в дополнение к специальной клавише, удаляющей последний введенный символ, была клавиша, удаляющая последнее слово.

38. В систему MINIX был добавлен новый диск со сменным носителем. Этому устройству необходимо раскручивать диск каждый раз, после того как сменен носитель, и время раскрутки довольно велико. Ожидается, что в процессе работы системы носитель будет часто сменяться. Неожиданно подпрограмма waitfor из at wini.c оказалась неудовлетворительной. Разработайте новый вариант процедуры waitfor, которая после одной секунды активного ожидания нужного значения будет работать так: задача диска засыпает на одну секунду, затем проверяет значение порта, до тех пор пока не будет обнаружено нужное значение или не истечет заданный параметром TIMEOUT интервал времени.