Вопросы 173

♦ первым пришел - первым обслужен (в порядке 10, 6, 2, 4, 8);

♦ кратчайшая задача - первая .

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

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

25. Для предсказания времени выполнения используется алгоритм старения с а = 1/2. Предыдущие четыре значения времени составляли 40, 20, 40 и 15 мс (первое значение - самое давнее). Оцените следующее время выполнения.

26. В гибкую систему реального времени поступают четыре периодических сигнала с периодами 50, 100, 200 и 250 мс. На обработку каждого сигнала требуется 35, 20, 10 и х мс времени процессора. Укажите максимальное значение х, при котором система остается поддающейся планированию.

27. Объясните причины широкого распространения двухуровневого планирования.

28. В процессе работы MINIX использует переменную proc ptr, содержащую указатель на ячейку текущего процесса в таблице процессов. Зачем?

29. В MINIX сообщения не буферизуются. Поясните, почему это приводит к проблемам с прерываниями таймера и клавиатуры.

30. Когда в MINIX приостановленному процессу отправляется сообщение, вызывается подпрограмма ready, которая помещает процесс в одну из очередей планировщика. Эта подпрограмма начинается с блокирования прерываний. Почему?

31. В MINIX функция mini rec содержит цикл. Зачем?

32. Схема диспетчеризации в MINIX в целом соответствует показанной на рис. 2.10, с различными приоритетами для разных классов. Нижний класс (пользовательские процессы) планируется по циклической схеме, но задачи и серверы всегда выполняются, пока не попадут в блокировку. Возможно ли, что процессы нижнего уровня будут зависать? Почему (или почему нет)?

33. Походит ли MINIX для решения задач реального времени (таких как сбор данных)? Если нет, то что можно сделать, чтобы исправить это?

34. Предположим, у вас имеется операционная система, предоставляющая семафоры. Реализуйте систему обмена сообщениями. Напишите подпрограммы для отправки и приема сообщений.

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

36. Решите предыдущую задачу, но теперь постарайтесь избежать зависаний. Для этого, когда бабуин хочет перебраться на восток, и при этом на веревке уже висят несколько обезьян, движущихся на запад, бабуин ждет, когда веревка освободится. Другое условие: нужно запретить для остальных движение на запад, пока он не перейдет на восток.

37. Решите задачу обедающих философов в стиле каждому философу по монитору .

38. Добавьте в ядро MINIX код, который бы подсчитывал, сколько раз процесс (или задача) i обратился к процессу (или задаче) j. Сделайте так, чтобы эта матрица выводилась по нажатию клавиши F4.

39. Измените планировщик MINIX так, чтобы он отслеживал, сколько времени каждый процесс занимал процессор последний раз. Когда все задачи и серверы освободят процессор для пользовательских процессов, выбирайте тот из них, который меньше всех тревожил процессор.

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

41. Перепишите макросы hwint master и hwint slave так, чтобы действия, выполняемые функцией save, были бы встроены в код. Насколько увеличился объем кода? Можете ли вы измерить прирост производительности?

Глава 3 Ввод/вывод

Одна из важнейших функций операционной системы состоит в управлении всеми устройствами ввода/вывода компьютера. Операционная система должна давать этим устройствам команды, перехватывать прерывания и обрабатывать ошибки. Она должна также обеспечить простой и удобный интерфейс между устройствами и остальной частью системы. Интерфейс, насколько это возможно, должен быть одинаковым для всех устройств (для достижения независимости от применяемого оборудования). Программное обеспечение ввода/вывода составляет существенную часть операционной системы. Тому, как операционная система управляет устройствами ввода/вывода, и посвящена эта глава.

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

Далее следует раздел, посвященный взаимной блокировке. Мы дадим строгое определение этому понятию, покажем, как взаимоблокировки возникают, представим две модели для их анализа и обсудим некоторые алгоритмы их предотвращения.

Затем мы сделаем общий обзор ввода/вывода в MINIX. После этого вступления мы подробно ознакомимся с четырьмя конкретными устройствами ввода/вывода: RAM-ДИСКОМ, жестким диском, часами и терминалом. Для каждого устройства мы рассмотрим его аппаратную часть, программное обеспечение и его реализацию в MINIX. Наконец, завершит главу краткое описание некоторых частей MINIX, расположенных на том же уровне, что и задачи ввода/вывода, но задачами не являющихся. Они предоставляют некоторые дополнительные службы для менеджера памяти и файловой системы, например выполняют передачу блоков данных от пользовательских процессов.

3.1. Принципы аппаратуры ввода/вывода

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