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

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

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

2.4. Планирование

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

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

Чтобы разработать алгоритм планирования, необходимо иметь представление о том, что должен делать хороший алгоритм. Некоторые задачи зависят от среды (системы пакетной обработки, интерактивные или реального времени), но есть одинаковые во всех системах, мы рассмотрим их ниже.

1. Равноправие - предоставление каждому процессу справедливой доли процессорного времени.

2. Использование процессора - поддержка постоянной занятости процессора.

3. Время отклика - быстрая реакция на запросы.

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

5. Пропускная способность - максимальное количество задач в час.

Несложное рассуждение показывает, что некоторые из перечисленных целей противоречат друг другу.

При всех обстоятельствах необходимо справедливое распределение процессорного времени. Сопоставимые процессы должны получать сопоставимое обслуживание. Выделить одному процессу намного больше ресурсов процессора, чем другому, эквивалентному, несправедливо. Разумеется, с различными категориями процессов следует обращаться весьма по-разному. Сравните, например, задачи обеспечения безопасности и начисления заработной платы в компьютерном центре атомной электростанции. Интерактивным пользователям, для которых важно небольшое время отклика, наверняка бы понравилось, если пакетные задачи не запускались бы вообще (ну, разве что, кроме времени с 3 часов ночи до 6 утра, когда все такие пользователи спят). Но тем, кто ставит задачи на обработку, такая идея придется не по вкусу, так как она нарушает пункт 4. Вообще говоря, можно показать, что алгоритм планирования, ориентированный на какой-то один класс задач, всегда плохо подходит для других классов. В конце концов, процессорное время ограничено. Чтобы дать одному пользователю больше, другому придется дать меньше. Такова жизнь.

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

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

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

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

2.4.1. Циклическое планирование

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

Следующий

Текущий вес

Текущий продесс

Рис. 2.9. Циклическое планирование: а - список процессов в состоянии готовности; б - список процессов в состоянии готовности после того, как процесс В исчерпал свой квант времени

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

Для увеличения эффективности назначим размер кванта, скажем, 100 мс. Теперь пропадает только 1 % времени. Но представьте, что будет в системе с разделением времени, если 10 пользователей одновременно нажмут клавишу возврата каретки. В список будет занесено 10 процессов. Если процессор был свободен, первый процесс будет запущен немедленно, второму придется ждать 100 мс и т. д. Последнему процессу, возможно, придется ждать целую секунду, если все остальные не блокируются за время кванта. Большинству пользователей секундная задержка вряд ли понравится.