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

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

.=1 if

Системы реального времени, удовлетворяющие этому условию, называются поддающимися планированию или планируемыми.

В качестве примера рассмотрим гибкую систему реального времени с тремя периодическими сигналами с периодами в 100, 200 и 500 мс соответственно. Если на обработку этих сигналов уходит, в том же порядке, 50, 30 и 100 мс, система является поддающейся планированию, поскольку 0,5 + 0,15 + 0,2 < 1. Даже при добавлении четвертого сигнала с периодом в 1 с системой все равно можно будет управлять через планирование, пока время обработки сигнала не превысит 150 мс. В этих расчетах существенным является предположение, что время переключения между процессами пренебрежимо мало.

Алгоритмы планирования для систем реального времени бывают как статическими, так и динамическими. В первом случае все решения планирования принимаются заранее, еще до запуска системы. Во втором случае решения выносятся по ходу дела. Рассмотрим в общих чертах несколько динамических алгоритмов планирования реального времени. Классический вариант носит название алгоритма постоянной скорости (rate monotonic algorithm, Liu и Layland, 1973). В нем процессам предварительно назначаются приоритеты, пропорциональные частоте возникновения переключений. Например, если один процесс работает каждые 50 мс, а второй каждые 100 мс, то первый может получить приоритет 50, а второй 10. В момент запуска планировщик всегда инициирует процесс, имеющий больший приоритет, прерывая, если нужно, текущий. Авторы алгоритма доказали, что он является оптимальным.

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

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

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

2.4.8. Двухуровневый механизм

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

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

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

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

1. Сколько времени прощло с тех пор, как процесс был выгружен на диск или загружен с диска?

2. Сколько времени процесс уже использовал процессор?

3. Каков размер процесса (маленькие процессы не мещают)?

4. Какова актуальность процесса?

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

2.4.9. Политика и механизм планирования

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

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

2.5. Обзор процессов в MINIX

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