В. Диспетчеризация потоков.

ЯДРА И ОПЕРАЦИОННЫЕ СИСТЕМЫРЕАЛЬНОГО ВРЕМЕНИ

Чтобы быстрее перейти к делу, при­мем как очевидные следующие момен­ты.

1. Когда-то операционных систем со­всем не было.

2. Через некоторое время после их появ­ления возникло направление ОС РВ.

3. Все ОС РВ являются многозадачны­ми операционными системами. Зада­чи делят между собой ресурсы вы­числительной системы, в том числе и процессорное время. Четкой границы между ядром (Кегnеl) и операционной системой нет. Различают их, как правило, по набору функциональных возможностей. Ядра предоставляют пользователю такие ба­зовые функции, как планирование и синхронизация задач, межзадачная коммуникация, управление памятью и т. п. Операционные системы в допол­нение к этому имеют файловую систе­му, сетевую поддержку, интерфейс с оператором и другие средства высокого уровня.

По своей внутренней архитектуре ОС РВ можно условно разделить на мо­нолитные ОС, ОС на основе микроядра и объектно-ориентированные ОС. Гра­фически различия в этих подходах ил­люстрируются рисунками 1, 2, 3. Пре­имущества и недостатки различных ар­хитектур достаточно очевидны, поэто­му подробно мы на них останавливать­ся не будем.

Задачи, процессы, потоки

Существуют различные оп­ределения термина «задача» для многозадачной ОС РВ. Мы будем считать задачей набор операции (машинных инструкций), предназначен­ный для выполнения логи­чески законченной функции системы. При этом задача конкурирует с другими зада­чами за получение контроля над ресурсами вычислитель­ной системы

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

Хорошим примером многопоточ­ной программы является редактор текста WORD, где в рамках одного приложения может одновременно происходить и набор текста, и провер­ка правописания.

Преимущества потоков

1.Так как множество потоков способ­но размещаться внутри одного ЕХЕ-модуля, это позволяет экономить ре­сурсы как внешней, так и внутрен­ней памяти.

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

3. Как правило, контекст потоков меньше, чем контекст процессов, а значит, время переключения между задачами-потоками меньше, чем между задачами-процессами.

4. Так как все потоки, а иногда и само ядро РВ размещаются в одном ЕХЕ-модуле, значительно упрощается ис­пользование программ-отладчиков (debager)

Недостатки потоков

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

2. То, что потоки имеют доступ к облас­тям данных друг друга, может при­вести к ситуации, когда некорректно работающий поток способен испор­тить данные другого потока. В отли­чие от этого процессы защищены от взаимного влияния, а попытка запи­си в «не свою» память приводит, как правило, к возникновению специ­ального прерывания по обработке «исключительных ситуаций». Реализация механизмов управления процессами и потоками, возможность их взаимного сосуществования и взаи­модействия определяются конкрет­ным ПО РВ.

ОСНОВНЫЕ СВОЙСТВА ЗАДАЧ

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

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

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

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

1. Активная задача - это задача, выпол­няемая системой в текущей момент времени.

2. Готовая задача - это задача, готовая к выполнению и ожидающая у плани­ровщика своей «очереди».

3. Блокированная задача - это задача, выполнение которой приостановле­но до наступления определенных со­бытий. Такими событиями могут быть освобождение необходимого задаче ресурса, поступление ожидае­мого сообщения, завершение интер­вала ожидания и т. п.

Пустая задача (Idle Task) - это зада­ча, запускаемая самой операционной системой в момент инициализации и выполняемая только тогда, когда в сис­теме нет других готовых для выполне­ния задач. Пустая задача запускается с самым низким приоритетом и, как пра­вило, представляет собой бесконечный цикл «ничего не делать». Наличие пус­той задачи предоставляет операцией ной системе удобный механизм отра­ботки ситуаций, когда нет ни одной готовой к выполнению задачи.

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

Реентерабельность (повторная входимость) означает возможность без

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

 

 

ПЛАНИРОВАНИЕ ЗАДАЧ

Важной частью любой ОС РВ является планировщик задач. Несмотря на то, что в разных источниках он может на­зываться по-разному (диспетчер задач, супервизор и т. н.), его функции оста­ются теми же: определить, какая из заадач должна выполняться в системе в каждый конкретный момент времени. Самым простым методом планирова­ния, не требующим никакого специального ПО и планировщика как тако-вого, является использование цикли­ческого алгоритма в стиле round robin:

void main (void)

{

for (;;) {

task0();

taskl();

task2();

/* и т. д. */

}

}

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

1. Подпрограммы не должны содер­жать циклов ожидания в стиле

while (TRUE) {

if (switch up()) {

lamp_off();

break;

}

}

2. Подпрограммы должны выполнять свою работу как можно быстрее, что-бы дать возможность работать следу­ющей подпрограмме.

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

Можно отметить следующие преиму­щества циклического алгоритма.

1. Простота использования и прозрач­ность для понимания.

2. Если исключить из рассмотрения прерывания, система полностью де­терминирована. Задачи всегда вызываются в одной и той же последова­тельности, что позволяет достаточно просто произвести анализ «наихуд­шего случая» и вычислить макси­мальную задержку.

3. Минимальные размеры кода и дан­ных. Кроме того, в отличие от алго­ритмов с вытеснением, для всех за­дач необходим только один стек.

4. Отсутствуют ошибки, обусловлен­ные «гонками».

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

Перейдем теперь к другому широко используемому алгоритму планирова­ния. Речь пойдет о режиме разделе­ния времени. Алго­ритм реализуется следующим образом:

каждой задаче отводится определен­ное количество квантов времени (обычно кратно 1 мс), в течение кото­рых задача может монопольно зани­мать процессорное время. После того как заданный интервал времени исте­кает, управление передается следую­щей готовой к выполнению задаче, имеющей наивысший приоритет. Та, в свою очередь, выполняется в течение отведенного для нес промежутка вре­мени, после чего все повторяется в сти­ле round robin. Легко заметить, что та­кой алгоритм работы может привести к определенным проблемам. Предста­вим, что в системе работают 7 задач, 3из которых имеют высокий приоритет, а 4 — низкий. Низкоприоритетные за­дачи могут никогда не получить управ­ление, так как три высокоприоритет­ные задачи будут делить все процес­сорное время между собой. Единствен­ную возможность для низкоприори­тетных задач получить управление предоставляет ситуация, когда все вы­сокоприоритетные задачи находятся в блокированном состоянии.

Для решения этой проблемы приме­няется прием, получивший название равнодоступность (fairness). При этом реализуется принцип адаптивной приоритетности, когда приоритет за­дачи, которая выполняется слишком долго, постепенно уменьшается, позво­ляя менее приоритетным задачам по­лучить свою долю процессорного вре­мени. Равнодоступность применяется главным образом в многопользова­тельских системах и редко применяет­ся в системах реального времени.

Кооперативная многозадачность - это еще один алгоритм переключе­ния задач, с которым широкие массы компьютерной общественности знако­мы по операционной системе Windows З.х. Задача, получившая управление, выполняется до тех пор, пока она сама по своей инициативе не передаст уп­равление другой задаче. По сути это продолжение идеологии round robin, и нет нужды объяснять, почему алго­ритм кооперативной многозадачнос­ти в чистом виде мало применяется в системах реального времени.

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

 

В общем случае алгоритмы планирования должны соответствовать кри­териям оптимальности функционирования системы. Однако, если для сис­тем «жесткого» реального времени та­кой критерий очевиден: «ВСЕГДА и ВСЁ делать вовремя», то для систем «мягкого» реального времени это мо­жет' быть, например, минимальное «максимальное запаздывание» или средневзвешенная своевременность завершения операций. В зависимости от критериев оптимальности могут применяться алгоритмы планирова­ния задач, отличные от рассмотрен­ных.

Необходимо отметить, что в одной вычислительной системе могут одно­временно сосуществовать задачи и «жесткого», и «мягкого» реального вре­мени, и что только одна из этих задач, обладающая наивысшим приорите­том, может быть по-настоящему де­терминированной.

Не стоит особо увлекаться приори­тетами. Коли система нормально рабо­тает, когда все задачи имеют одинако­вый приоритет, то и слава Богу. Если нет, то можно присвоить высокий приоритет «критической» задаче, и низкий приоритет всем остальным. Если у вас больше одной «критичес­кой» задачи, при недостаточном быстродействии системы имеет смысл рассмотреть многопроцессорную конфигурацию или, отказавшись от ПО РВ, перейти к простому циклическому алгоритму.

Как правило, разработчики стара­ются свести свою систему реального времени к наиболее простым конфи­гурациям, характерным для систем «жесткого» реального времени, иногда даже в ущерб эффективности исполь­зования вычислительных ресурсов. Причина понятна: сложные динами­ческие системы весьма трудно анали­зировать и отлаживать, поэтому лучше заплатить за более мощный процес­сор, чем иметь в будущем проблемы из-за непредвиденного поведения системы. В связи с этим большинство существующих систем реального вре­мени представляют собой статичес­кие системы с фиксированными при­оритетами. Часто в системе реализует­ся несколько «режимов» работы, каж­дый из которых имеет свой набор вы­полняемых задач с заранее заданными приоритетами. Значительная часть особо ответственных систем по-преж­нму реализуется без применения коммерческих ОС РВ вообще.

В. Диспетчеризация потоков.

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

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

• Локальная Диспетчеризация. Потоки конкурируют только с другими потоками того же самого процесса. Диспетчеризация производится на двух уровнях. Сначала подвергаются диспетчеризации все процессы по отношению друг к другу. Затем потоки выбранного процесса конкурируют друг с другом за центральный процессор.

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

 

СИНХРОНИЗАЦИЯ ЗАДАЧ

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

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

2. Необходимо упорядочить доступ нескольких задач к разделяемому ресурсу.

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

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

Давайте рассмотрим все четыре случая более подробно.

Связанные задачи

Взаимное согласование задач с помощью сообщений является одним из важнейших принципов операционных систем реального времени. Способы реализации межзадачного обмена отличаются большим разнообразием, что не в последнюю очередь приводит к обилию терминов в этой области. Можно встретить такие понятия, как сообщение (message), почтовый ящик (mail box), сигнал (signal), событие (event), прокси (proxy) и т. п. В дальнейшем будем называть сообщениями любой механизм явной передачи информации от одной задачи к другой (такие объекты, как семафоры, можно отнести к механизму неявной передачи сообщений).

Объем информации, передаваемой в сообщениях, может меняться от 1 бита до всей свободной емкости памяти вашей системы. Во многих ОС РВ компоненты операционной системы, так же как и пользовательские задачи, способны принимать и передавать сообщения. Сообщения могут быть асинхронными и синхронными. В первом случае доставка сообщений задаче производится после того, как она в плановом порядке получит управление, а во втором случае циркуляция сообщений оказывает непосредственное влияние на планирование задач. Например, задача, пославшая какое-либо сообщение, немедленно блокируется, если для продолжения ра­боты ей необходимо дождаться от ic'i.i или если низкоприоритетная за la'i.i шлет высоко! 1риоритетной зад.^п с" общение, которого последняя ожи (bi т то высокоприоритетная задача, если. конечно, используется 11риорит<-'гн:1я многозадачность с вытеснением ш медленно получит управление.

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

Однако наиболее часто используется принцип, когда каждая задача имеет свою очередь сообщений, в конец которой ставится всякое вновь полученное сообщение. Стандартный принцип обработки очереди сообщений, по принципу «первым вошел, первым вы шел» (FIFO) не всегда оптимално соответствует поставленной задаче. Сообщение может содержать как сами данные, предназначенные для передачи, так и указатель на такие данные В последнем случае обмен может npоизводиться с помощью разделяемых областей памяти, разделяемых файлов и т. п.

Общие ресурсы

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

Приведенный пример показывает, что ошибки, обусловленные «гонками»,

а) характерны для работы с любыми ресурсами, доступ к которым имеют несколько задач, и

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

Вот возможные пути решения проблемы.

1. Не использовать алгоритмы планирования задач с вытеснением. Это решение, правда, не всегда приемлемо.

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

3. Запретить прерывания на время доступа к разделяемым данным. Кардинальное решение, которое, впрочем, не приветствуется в системах реального времени.

4. Использовать для упорядочивания доступа к глобальным данным семафоры. Наиболее часто применяемое решение, которое, впрочем, может привести в некоторых случаях к «ин­версии приоритетов».

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

Возможные неприятности в борьбе за ресурсы.

Смертельный захват (1)сас11оск). В народе побочные проявления этой си­туации называются более прозаично -«зацикливание» или «зависание». Причина этого может быть достаточно проста - «задачи не поделили ресурсы». Пусть, например, Задача Л.за­хватила ресурс клавиатуры и ждет, ког­да освободится ресурс дисплея, а в это время Задача В также хочет пообщаться с пользователем и, успев захватить ресурс дисплея, ждет теперь, когда освободится клавиатура. Так и будут.задачи ждать друг друга до второго потопа, а пользователь будет и это время смотреть на пустой экран и ругать последними словами яйцеголовых программистов, которые не смогли сделать нормально работающую систему. В таких случаях рекомендуется придерживаться тактики «или все, или ничего». Другими словами, если задача не смогла получить все необходимые для дальнейшей работы ресурсы, она должна освободить всё, что уже захвачено, и, как говорится, «зайти через полчаса». Другим решением, которое уже упоминалось, является использо­вание серверов ресурсов.

Инверсия приоритетов (Рпоп1у туегяюп). Как уже отмечалось, алгоритмы планирования задач (управление доступом к процессорному времени) должны находиться в соответствии с методами управления доступом к другим ресурсам, а всё вместе - соответствовать критериям оптимального функционирования системы. Эффект инверсии приоритетов является след­ствием нарушения гармонии в этой области. Ситуация здесь похожа на «смертельный захват», однако сюжет закручен еще более лихо. Представим, что у нас есть высокоприоритетная Задача А, среднеприоритетная Задача В и низкоприоритетная Задача С. Пусть в начальный момент времени Задачи А и В блокированы в ожидании какого-либо внешнего события. Допустим, получившая в результате этого управление Задача С захватила Семафор А, но не успела она его отдать, как была прервана Задачей А. В свою очередь, Задача А при попытке захватить Семафор А будет блокирована, так как этот семафор уже захвачен Задачей С. Если к этому времени Задача В находится в состоянии готовности, то управление после этого получит именно она, как имеющая более высокий, чем у Задачи С, приоритет. Теперь Задача В может занимать процессорное время, пока ей не надоест, а мы получаем ситуацию, когда высокоприоритетная Задача А не может функционировать из-за того, что необходимый ей ресурс занят низкоприоритетной Задачей С.