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

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

Вопросы

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

2. На всех сушествуюших компьютерах как минимум часть обработчиков прерываний написана на ассемблере. Почему?

3. В тексте утверждалось, что модель, представленная на рис. 2.4, а, не подходит для файлового сервера с кэшем в памяти. Почему? Может ли каждый процесс иметь собственный кэш?

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

5. Что такое состояние состязания?

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

In file file.lock

7. Является ли выражение In file file.lock

эффективным механизмом разделения доступа для таких пользовательских программ, как сценарии в предыдущей задаче? Почему?

8. Будет ли работать решение активного ожидания с использованием переменной turn (рис. 2.6) в случае двух процессоров, совместно использующих общую память?

9. Рассмотрим компьютер, в котором нет инструкции tsl, но есть инструкция для обмена содержимого регистра и слова памяти за одну неделимую операцию. Можно ли применить эту инструкцию для написания программы enter region, аналогичной листингу 2.3?

10. Опишите коротко, как реализовать семафоры в операционной системе, умеющей блокировать прерывания.

11. Покажите, как можно реализовать считающие семафоры (то есть способные хранить произвольные значения) при помощи только бинарных семафоров и обычных машинных команд.

12. В разделе Примитивы межпроцессного взаимодействия была описана ситуация с высокоприоритетным процессом Н и низкоприоритетным процессом L, которая приводила к вечному зацикливанию процесса Н. Может ли возникнуть подобная проблема, если вместо планирования по приоритетам использовать карусельное? Поясните.

13. Синхронизация в мониторах происходит с использованием переменных состояния и двух специальных операций, wait и signal. Более общая форма синхронизации предполагает один примитив waituntil с произвольным булевым предикатом в качестве параметра. Например,

waituntil х<0 ог y+z<n

В данном случае примитив signal больше не нужен. Эта схема существенно более общая, чем схемы Хоара и Хансена, но тем не менее она не используется. Почему? Подсказка: подумайте о реализации.

14. В ресторане быстрого питания есть четыре категории обслуживающего персонала: 1) работники, принимающие заказы; 2) повара, готовящие пищу; 3) специалисты по упаковке блюд и 4) кассиры, принимающие у клиентов деньги и выдающие еду. Каждому из видов персонала можно сопоставить последовательный процесс взаимодействия. Какой формой межпроцессного взаимодействия они пользуются? Свяжите эту модель с процессами в UNIX.

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

16. Почему в процедуре take forks решения задачи обедающих философов (см. листинг 2.9) переменной состояния присваивается значение HUNGRY?

17. Рассмотрим процедуру put forks в листинге 2.9. Пусть переменной состояния присваивается значение THINKING после двух вызовов процедуры test, а не до. Как это повлияет на решение?

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

19. Компьютеры CDC 6600 в состоянии обрабатывать до 10 процессов ввода/ вывода одновременно благодаря интересной форме циклического планирования, называемой разделением процессора. Переключение между процессами происходит после каждой команды, поэтому команда 1 поступает от первого процесса, команда 2 - от второго и т. д. Переключение процессов производится аппаратными средствами, и издержки равны нулю. Если в отсутствие других процессов процессу для выполнения работы нужно Г секунд, сколько ему потребуется времени в случае п процессов?

20. Обычно планировщики с циклическим алгоритмом поддерживают список процессов, готовых к работе, причем каждый процесс находится в списке в единственном экземпляре. Что произойдет, если процесс окажется в списке дважды? Существует ли причина, по которой подобное изменение будет полезным?

21. Измерения показали, что время выполнения среднестатистического процесса до блокировки ввода/вывода равно Т. На переключение между процессами уходит время 5, которое теряется впустую. Напишите формулу расчета эффективности для циклического планирования с квантом Q, принимающим следующие значения:

1) Q = < ,

2) Q>T,

3) 5 < Q < Г,

4) Q = ,

5) Q около 0.

22. Запуска ожидают пять задач. Предполагаемое время выполнения задач составляет 9, 6, 3, 5 и X В каком порядке их следует запустить, чтобы минимизировать среднее время отклика? (Ответ должен зависеть от X.)

23. Пять пакетных задач. А, В, С, D, Е, поступают в компьютерный центр практически одновременно. Ожидается, что время их выполнения составит 10, 6, 2, 4 и 8 мин. Их установленные приоритеты равны 3, 5, 2, 1 и 4, причем 5 - высший приоритет. Определите среднее оборотное время для каждого из следующих алгоритмов планирования, пренебрегая потерями при переключении между процессами:

* циклическое планирование;

♦ планирование согласно приоритетам;