ЖУРНАЛ СТА 2/1997

сектор номер 10. Из приведенного примера видно, что ошибки, связан- ные с нереентерабельностью, трудно обнаружить, а последствия они могут вызвать самые катастрофические. ПЛАНИРОВАНИЕ ЗАДАЧ Важной частью любой ОС РВ явля- ется планировщик задач. Несмотря на то, что в разных источниках он может называться поразному (диспетчер за- дач, супервизор и т. п.), его функции остаются теми же: определить, какая из задач должна выполняться в систе- ме в каждый конкретный момент вре- мени. Самым простым методом пла- нирования, не требующим никакого специального ПО и планировщика как такового, является использование цик- лического алгоритма в стиле round robin: void main (void) { for (;;) { task0(); task1(); task2(); / * и т. д. * / } } Каждая «задача», представляющая со- бой отдельную подпрограмму, выпол- няется циклически. При этом надо придерживаться следующих правил: 1. Подпрограммы не должны содер- жать циклов ожидания в стиле while (TRUE) { if (switch_up()) { lamp_off(); break; } } 2. Подпрограммы должны выполнять свою работу как можно быстрее, что- бы дать возможность работать сле- дующей подпрограмме. 3. При необходимости подпрограмма мо- жетсохранятьсвоеокружениеитекущие результаты, чтобы в следующем цикле возобновить работу с того же места. Можно отметить следующие пре- имущества циклического алгоритма. 1. Простота использования и прозрач- ность для понимания. 2. Если исключить из рассмотрения прерывания, система полностью де- терминирована. Задачи всегда вы- зываются в одной и той же после- довательности, что позволяет доста- точно просто произвести анализ «наихудшего случая» и вычислить максимальную задержку. 3. Минимальные размеры кода и дан- ных. Кроме того, в отличие от алго- ритмов с вытеснением, для всех за- дач необходим только один стек. 4. Отсутствуют ошибки, обусловлен- ные «гонками». К недостаткам циклического алго- ритма можно отнести отсутствие при- оритетности и очередей. К тому же задачи вызываются независимо от то- го, должны ли они в данный момент чтолибо делать или нет, а на приклад- ного программиста ложится макси- мальная ответственность за работос- пособность системы. Перейдем теперь к другому широко используемому алгоритму планирова- ния. Речь пойдет о режиме разделе- ния времени . Существуют различные реализации в рамках этого алгоритма, и некоторые западные специалисты даже различают такие в общемто идентичные для нас понятия, как timeslicing и timesharing. Как правило, алгоритм реализуется следующим об- разом: каждой задаче отводится опре- деленное количество квантов време- ни (обычно кратно 1 мс), в течение ко- торых задача может монопольно зани- мать процессорное время. После того как заданный интервал времени исте- кает, управление передается следую- щей готовой к выполнению задаче, имеющей наивысший приоритет. Та, в свою очередь, выполняется в течение отведенного для нее промежутка вре- мени, после чего все повторяется в сти- ле round robin. Легко заметить, что та- кой алгоритм работы может привести к определенным проблемам. Предста- вим, что в системе работают 7 задач, 3 из которых имеют высокий приоритет, а 4 — низкий. Низкоприоритетные за- дачи могут никогда не получить уп- равление, так как три высокоприори- тетные задачи будут делить все процес- сорное время между собой. Единствен- ную возможность для низкоприори- тетных задач получить управление предоставляет ситуация, когда все вы- сокоприоритетные задачи находятся в блокированном состоянии. Для решения этой проблемы при- меняется прием, получивший назва- ние равнодоступность (fairness). При этом реализуется принцип адаптивной приоритетности, когда приоритет за- дачи, которая выполняется слишком долго, постепенно уменьшается, поз- воляя менее приоритетным задачам получить свою долю процессорного времени. Равнодоступность применя- ется главным образом в многопользо- вательских системах и редко приме- няется в системах реального времени. Кооперативная многозадачность — это еще один алгоритм переключе- ния задач, с которым широкие массы компьютерной общественности знако- мы по операционной системе Windows 3.х. Задача, получившая управление, выполняется до тех пор, пока она сама по своей инициативе не передаст уп- равление другой задаче. По сути это продолжение идеологии round robin, и нет нужды объяснять, почему алго- ритм кооперативной многозадачнос- ти в чистом виде мало применяется в системах реального времени. Приоритетная многозадачность с вытеснением — это, повидимому, наиболее часто используемый в ОС РВ принцип планирования. Основная идея состоит в том, что высокоприо- ритетная задача, как только для нее появляется работа, немедленно пре- рывает (вытесняет) низкоприоритет- ную. Другими словами, если какая либо задача переходит в состояние готовности, она немедленно получает управление, если текущая активная задача имеет более низкий приори- тет. Такое «вытеснение» происходит, например, когда высокоприоритетная задача получила ожидаемое сообще- ние, освободился запрошенный ею ресурс, произошло связанное с ней внешнее событие, исчерпался задан- ный интервал времени и т. п. Заканчивая рассмотрение основных принципов планирования задач, необ- ходимо отметить, что тема эта далеко не исчерпана. Диапазон систем реаль- ного времени весьма широк, начиная от полностью статических систем, где все задачи и их приоритеты заранее определены, до динамических систем, где набор выполняемых задач, их приоритеты и даже алгоритмы плани- рования могут меняться в процессе функционирования. Существуют, на- пример, системы, где каждая отдель- ная задача может участвовать в любом из трех алгоритмов планирования или их комбинации (вытеснение, раз- деление времени, кооперативность). В общем случае алгоритмы плани- рования должны соответствовать кри- териям оптимальности функциони- рования системы. Однако, если для систем «жесткого» реального време- ни такой критерий очевиден: «ВСЕГДА и ВСЁ делать вовремя», то для систем «мягкого» реального времени это мо- жет быть, например, минимальное «максимальное запаздывание» или средневзвешенная своевременность завершения операций. В зависимости от критериев оптимальности могут применяться алгоритмы планирова- ния задач, отличные от рассмотрен- ных. Например, может оказаться, что планировщик должен анализировать момент выдачи критичных по време- ни управляющих воздействий и запус- кать на выполнение ту задачу, кото- рая отвечает за ближайшие из них (алгоритм earliest deadline first, EDF). ОБЗОР Программное обеспечение 25 2/97