СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ. Уверенностью можно сказать, что ссылки на красивое словосо
 Скачать 288.74 Kb.
|
|
разделе ния времени. Существуют различные реализации в рамках этого алгоритма, и некоторые западные специалисты даже различают такие в общемто идентичные для нас понятия, как time slicing и timesharing. Как правило, алго ритм реализуется следующим образом: каждой задаче отводится определен ное количество квантов времени (обычно кратно 1 мс), в течение кото рых задача может монопольно зани мать процессорное время. После того как заданный интервал времени исте кает, управление передается следую щей готовой к выполнению задаче, имеющей наивысший приоритет. Та, в свою очередь, выполняется в течение отведенного для нее промежутка вре мени, после чего все повторяется в сти ле round robin. Легко заметить, что та кой алгоритм работы может привести к определенным проблемам. Предста вим, что в системе работают 7 задач, 3 из которых имеют высокий приоритет, а 4 – низкий. Низкоприоритетные за дачи могут никогда не получить управ ление, так как три высокоприоритет ные задачи будут делить все процес сорное время между собой. Единствен ную возможность для низкоприори тетных задач получить управление предоставляет ситуация, когда все вы сокоприоритетные задачи находятся в блокированном состоянии. Для решения этой проблемы приме няется прием, получивший название равнодоступность (fairness). При этом реализуется принцип адаптивной приоритетности, когда приоритет за дачи, которая выполняется слишком долго, постепенно уменьшается, позво ляя менее приоритетным задачам по лучить свою долю процессорного вре мени. Равнодоступность применяется главным образом в многопользова тельских системах и редко применяет ся в системах реального времени. Кооперативная многозадачность – это еще один алгоритм переключе ния задач, с которым широкие массы компьютерной общественности знако мы по операционной системе Windows 3.х. Задача, получившая управление, выполняется до тех пор, пока она сама по своей инициативе не передаст уп равление другой задаче. По сути это продолжение идеологии round robin, и нет нужды объяснять, почему алго ритм кооперативной многозадачнос ти в чистом виде мало применяется в системах реального времени. Приоритетная многозадачность с вытеснением – это, повидимому, наиболее часто используемый в ОС РВ принцип планирования. Основная идея состоит в том, что высокоприо ритетная задача, как только для нее по является работа, немедленно прерыва ет (вытесняет) низкоприоритетную. Другими словами, если какаялибо за дача переходит в состояние готовнос ти, она немедленно получает управле ние, если текущая активная задача имеет более низкий приоритет. Такое «вытеснение» происходит, например, когда высокоприоритетная задача по лучила ожидаемое сообщение, осво бодился запрошенный ею ресурс, про изошло связанное с ней внешнее со бытие, исчерпался заданный интервал времени и т. п. Заканчивая рассмотрение основных принципов планирования задач, необ ходимо отметить, что тема эта далеко не исчерпана. Диапазон систем реаль ного времени весьма широк, начиная от полностью статических систем, где все задачи и их приоритеты заранее определены, до динамических систем, где набор выполняемых задач, их при оритеты и даже алгоритмы планиро вания могут меняться в процессе функционирования. Существуют, на пример, системы, где каждая отдель ная задача может участвовать в любом из трех алгоритмов планирования или их комбинации (вытеснение, разделе ние времени, кооперативность). В общем случае алгоритмы плани рования должны соответствовать кри териям оптимальности функциониро вания системы. Однако, если для сис тем «жесткого» реального времени та кой критерий очевиден: «ВСЕГДА и ВСЁ делать вовремя», то для систем «мягкого» реального времени это мо жет быть, например, минимальное «максимальное запаздывание» или средневзвешенная своевременность завершения операций. В зависимости от критериев оптимальности могут применяться алгоритмы планирова ния задач, отличные от рассмотрен ных. Например, может оказаться, что планировщик должен анализировать момент выдачи критичных по време ни управляющих воздействий и запус кать на выполнение ту задачу, которая отвечает за ближайшие из них (алго ОБЗОР Программное обеспечение 25 2/97 (C) 1997 CTA Тел.: (095) 2340635 Факс: (095) 3303650 http://www.cta.ru ритм earliest deadline first, EDF). Необходимо отметить, что в одной вычислительной системе могут одно временно сосуществовать задачи и «жесткого», и «мягкого» реального вре мени, и что только одна из этих задач, обладающая наивысшим приорите том, может быть понастоящему де терминированной. Не стоит особо увлекаться приори тетами. Если система нормально рабо тает, когда все задачи имеют одинако вый приоритет, то и слава Богу. Если нет, то можно присвоить высокий приоритет «критической» задаче, и низкий приоритет всем остальным. Если у вас больше одной «критичес кой» задачи, при недостаточном быс тродействии системы имеет смысл рассмотреть многопроцессорную конфигурацию или, отказавшись от ПО РВ, перейти к простому цикличес кому алгоритму. Как правило, разработчики стара ются свести свою систему реального времени к наиболее простым конфи гурациям, характерным для систем «жесткого» реального времени, иногда даже в ущерб эффективности исполь зования вычислительных ресурсов. Причина понятна: сложные динами ческие системы весьма трудно анали зировать и отлаживать, поэтому лучше заплатить за более мощный процес сор, чем иметь в будущем проблемы изза непредвиденного поведения системы. В связи с этим большинство существующих систем реального вре мени представляют собой статичес кие системы с фиксированными при оритетами. Часто в системе реализует ся несколько «режимов» работы, каж дый из которых имеет свой набор вы полняемых задач с заранее заданными приоритетами. Значительная часть особо ответственных систем попреж нему реализуется без применения коммерческих ОС РВ вообще. СИНХРОНИЗАЦИЯ ЗАДАЧ Хотя каждая задача в системе, как правило, выполняет какуюлибо от дельную функцию, часто возникает необходимость в согласованности (синхронизации) действий, выполня емых различными задачами. Такая синхронизация необходима, в основ ном, в следующих случаях. 1. Функции, выполняемые различны ми задачами, связаны друг с другом. Например, если одна задача подго тавливает исходные данные для дру гой, то последняя не выполняется до тех пор, пока не получит от первой задачи соответствующего сообще ния. Одна из вариаций в этом случае – это когда задача при определенных условиях порождает одну или не сколько новых задач. 2. Необходимо упорядочить доступ не скольких задач к разделяемому ре сурсу. 3. Необходима синхронизация задачи с внешними событиями. Как правило, для этого используется механизм прерываний, с которым читатель, безусловно, знаком. 4. Необходима синхронизация задачи по времени. Диапазон различных ва риантов в этом случае достаточно широк, от привязки момента выдачи какоголибо воздействия к точному астрономическому времени до про стой задержки выполнения задачи на определенный интервал времени. Для решения этих вопросов в конеч ном счете используются специаль ные аппаратные средства, называе мые таймером. Давайте рассмотрим все четыре слу чая более подробно. Связанные задачи Взаимное согласование задач с по мощью сообщений является одним из важнейших принципов операционных систем реального времени. Способы реализации межзадачного обмена от личаются большим разнообразием, что не в последнюю очередь приводит к обилию терминов в этой области. Можно встретить такие понятия, как сообщение (message), почтовый ящик (mail box), сигнал (signal), событие (event), прокси (proxy) и т. п. Если, чи тая описание какойлибо ОС РВ, вы встретите уже знакомое название, не спешите делать выводы. Даже один и тот же термин может для разных ОС РВ обозначать разные вещи. Чтобы не за путаться, мы будем в дальнейшем назы вать сообщениями любой механизм яв ной передачи информации от одной задачи к другой (такие объекты, как се мафоры, можно отнести к механизму неявной передачи сообщений). Объем информации, передаваемой в сообщениях, может меняться от 1 бита до всей свободной емкости памяти ва шей системы. Во многих ОС РВ компо ненты операционной системы, так же как и пользовательские задачи, способ ны принимать и передавать сообщения. Сообщения могут быть асинхронными и синхронными. В первом случае до ставка сообщений задаче производится после того, как она в плановом порядке получит управление, а во втором случае циркуляция сообщений оказывает не посредственное влияние на планирова ние задач. Например, задача, пославшая какоелибо сообщение, немедленно блокируется, если для продолжения ра боты ей необходимо дождаться ответа, или если низкоприоритетная задача шлет высокоприоритетной задаче со общение, которого последняя ожидает, то высокоприоритетная задача, если, конечно, используется приоритетная многозадачность с вытеснением, не медленно получит управление. Иногда сообщения передаются через отведенный для этого буфер опреде ленного размера («почтовый ящик»). При этом, как правило, новое сообще ние затирает старое, даже если послед нее не было обработано. Однако наиболее часто используется принцип, когда каждая задача имеет свою очередь сообщений, в конец ко торой ставится всякое вновь получен ное сообщение. Стандартный принцип обработки очереди сообщений по принципу «первым вошел, первым вы шел» (FIFO) не всегда оптимально со ответствует поставленной задаче. В не которых ОС РВ предусматривается та кая возможность, когда сообщение от высокоприоритетной задачи обраба тывается в первую очередь (в этом слу чае говорят, что сообщение наследует приоритет пославшей его задачи). Иногда полезным оказывается не посредственное управление приорите том сообщений. Представим, что зада ча послала серверу (драйверу) принте ра несколько сообщений, содержащих данные для печати. Если теперь задача хочет отменить всю печать, ей надо послать соответствующее сообщение с более высоким приоритетом, чтобы оно встало в очередь впереди всех по сланных ранее заданий на печать. Сообщение может содержать как са ми данные, предназначенные для пере дачи, так и указатель на такие данные. В последнем случае обмен может произво диться с помощью разделяемых облас тей памяти, разделяемых файлов и т. п. Общие ресурсы Трудно переоценить важность пра вильной организации взаимодействия различных задач при доступе к общим ресурсам. Хорошей аналогией может служить обед в многодетной крестьян ской семье прошлого века. Едокам (за дачам) не разрешалось одновременно лезть ложками в общую миску (ресурс). Нарушители порядка могли получить от отца семейства (супервизора) лож кой по лбу. Ресурс – это общий термин, описы вающий физическое устройство или область памяти, которые могут одно временно использоваться только од ной задачей. Процессорное время тоже представляет собой своеобразный кон курентно используемый ресурс вычис лительной системы. Примером физи ОБЗОР Программное обеспечение 2/97 26 (C) 1997 CTA Тел.: (095) 2340635 Факс: (095) 3303650 http://www.cta.ru ческих устройств могут служить кла виатура, дисплей, дисковый накоп итель, принтер и т. п. Представим, на пример, что несколько задач пытаются одновременно выводить данные на принтер. На распечатке в результате ничего, кроме странной мешанины символов, мы не увидим. В качестве другого примера рассмотрим ситуа цию, когда в бортовом компьютере мирно летящего самолета МИГ29 сре ди прочих работают две задачи. Одна из них, взаимодействуя с радиолокаци онной системой, выдает удаление и на правление до цели, а другая задача ис пользует эти данные для пуска ракет класса «воздухвоздух». Не исключено, что первая задача, записав в глобаль ную структуру данных удаление до це ли, будет прервана второй задачей, не успев записать туда направление до це ли. В результате вторая задача считает из этой структуры ошибочные данные, что может привести к неудачному пус ку со всеми вытекающими отсюда не приятными последствиями. Прервись первая задача чуть позже, и все было бы нормально. Упомянутые здесь пробле мы обусловлены времязависимыми ошибками (time dependent error), или «гонками» и характерны для многоза дачных ОС, применяющих алгоритмы планирования с вытеснением (кстати, системы с разделением времени также относятся к категории «вытесняю щих»). Приведенный пример показывает, что ошибки, обусловленные «гонками», а) характерны для работы с любыми ресурсами, доступ к которым имеют несколько задач, и б) происходят толь ко в результате совпадения определен ных условий, а потому с трудом обна руживаются на этапе отладки. Вот возможные пути решения проб лемы. 1. Не использовать алгоритмы плани рования задач с вытеснением. Это ре шение, правда, не всегда приемлемо. 2. Использовать специальный сервер ресурса, то есть задачу, ответствен ную за упорядочивание доступа к ре сурсу. В этом случае запрос на изме нение значения глобальных данных посылается этому серверу в виде со общения. Аналогичный подход при меним и для физических устройств. Так, например, задача может послать данные на печать в виде сообщения, направленного к серверу принтера. 3. Запретить прерывания на время до ступа к разделяемым данным. Карди нальное решение, которое, впрочем, не приветствуется в системах реаль ного времени. 4. Использовать для упорядочивания доступа к глобальным данным сема форы. Наиболее часто применяемое решение, которое, впрочем, может привести в некоторых случаях к «ин версии приоритетов». Последний пункт стоит прокоммен тировать подробнее, поскольку поня тие «семафор» встречается первый раз. Семафор – это как раз то средство, которое часто используется для син хронизации доступа к ресурсам. В про стейшем случае семафор представляет собой байтовую переменную, прини мающую значение 0 или 1. Задача, пе ред тем как использовать ресурс, захва тывает семафор, после чего остальные задачи, желающие использовать тот же ресурс, должны ждать, пока семафор (ресурс) освободится. Существуют так же так называемые счетные семафоры, где семафор представляет собой счет чик. Пусть к системе подключено три принтера. Семафор, отвечающий за до ступ к функциям печати, инициализи руется со значением 3, а затем каждый раз, когда какаялибо задача запраши вает семафор для осуществления печа ти, его значение уменьшается на 1. После завершения печати задача осво бождает семафор, в результате чего значение последнего увеличивается на 1. Если текущее значение семафора равно 0, то ресурс считается недоступ ным, и задачи, запрашивающие печать, должны ждать, пока не освободится хо тя бы один принтер. Таким образом мо жет производиться синхронизация до ступа множества задач к группе из 3 принтеров. Так как по своей сути сема фор также представляет собой гло бальную переменную, все неприятнос ти, которые упоминались ранее в связи с самолетом МИГ29, по идее, должны поджидать нас и здесь. Однако, так как работа с семафорами происходит на уровне системных вызовов, програм мист может быть уверен, что разработ чики операционной системы обо всем заранее позаботились. Проникнувшись сознанием того, на сколько опасно изменять глобальные переменные в условиях, когда все во круг так и норовят друг друга вытес нить, читатель, наверно, не удивится, что участки кода программ, где проис ходит обращение к разделяемым ре сурсам, называются критическими секциями. Так как процессы обычно не имеют доступа к данным друг друга, а ресурсы физических устройств, как правило, управляются специальными задачами серверами (драйверами), наиболее ти пична ситуация, когда «гонки» за до ступ к глобальным переменным устра ивают различные потоки, исполняе мые в рамках одного программного модуля. Для того чтобы гарантировать, что критическая секция кода исполня ется в каждый момент времени только одним потоком, используют механизм взаимоисключающего доступа, или попросту мутексов (Mutual Exclusion Locks, Mutex). Практически мутекс представляет собой разновидность се мафора, который сигнализирует дру гим потокам, что критическая секция кода кемто уже выполняется. Критическая секция, использующая мутекс, должна иметь определенные суффиксную и префиксную части. На пример: int global_counter; void main (void) { mutex_t mutex; ( /* И все это лишь для того, чтобы увеличить глобальную переменную на единицу.*/ mutex_init (& mutex, USYNC, NULL); mutex_lock (& mutex); global_counter++; mutex_unlock (& mutex); } Если мутекс захвачен, то поток, пыта ющийся войти в критическую секцию, блокируется. После того как мутекс ос вобождается, один из стоящих в очере ди потоков (если таковые накопились) разблокируется и получает возмож ность доступа к глобальному ресурсу. Думаю, на этом рассмотрение средств синхронизации доступа к об щим ресурсам можно закончить, хотя, разумеется, множество тем осталось за скобками. Например, в WIN32 исполь зуется, в числе прочего, специальная разновидность мутексов под названи ем Critical Section Object. Необходимо также помнить, что, кроме ОС, имею щих WIN32 или POSIX API, существует большое число ни с чем не совмести мых ОС, поэтому наличие средств синхронизации и особенности их ре ализации должны рассматриваться от дельно для каждой конкретной ОС РВ. А вот возможные неприятности в борьбе за ресурсы. |