Циклический (круговой) алгоритм
Каждая задача выполняется циклически. Можно отметить основные преимущества циклического алгоритма:
· Простота использования и прозрачность понимания.
· Задачи всегда вызываются в одной и той же последовательности, что позволяет достаточно просто произвести анализ «наихудшего» случая и вычислить максимальную временную задержку.
К недостаткам этого алгоритма относят:
· Отсутствие приоритетности и очередей.
· К тому же задачи вызываются независимо от того, должны они в данный момент что-то делать или нет.
Разделение времени
Как правило, данный алгоритм реализуется следующим образом: каждой задаче отводится определенное количество квантов времени, например, 1 миллисекунды, в течение которого задача монопольно занимает процессорное время. После того как заданный интервал времени истекает, управление передается следующей готовой к выполнению задаче с наивысшим приоритетом. Та, в свою очередь, выполняется в течение отведенного для нее промежутка времени, после чего указанные действия повторяются.
Следует отметить, что такой алгоритм работы может привести к серьезной проблеме, а именно к тому, что низкоприоритетные задачи могут вообще никогда не получить управление, т.к. высокоприоритетные задачи будут делить все процессорное время между собой. Единственная возможность для низкоприоритетных задач получить управление предоставляет ситуация, когда все высокоприоритетные задачи находятся в блокированном состоянии.
|
|
|
Для решения этой проблемы применяется прием, называемый равнодоступностью. При этом реализуется принцип адаптивной (динамической) приоритетности, когда приоритет задачи, которая выполняется слишком долго, постепенно уменьшается, позволяя менее приоритетным задачам получить свою долю процессорного времени.
Равнодоступность применяется главным образом в многопользовательских системах (системах «мягкого» РВ), а многорежимность применяются собственно в СРВ (системах «жесткого» РВ).
Кооперативная многозадачность
При использовании этого алгоритма задача, получающая управление, выполняется до тех пор, пока она сама, по своей инициативе, не передаст управление другой задаче. В чистом виде кооперативная многозадачность применяется в СРВ достаточно редко.
Приоритетная многозадачность с вытеснением
Наиболее часто используемый в ОСРВ принцип планирования задач. Суть алгоритма в том, что высокоприоритетная задача, как только для нее появляется работа, прерывает (вытесняет) низкоприоритетную задачу, т.е. если какая-либо задача переходит в состояние готовности, она немедленно получает управление. Если текущая активная задача имеет более низкий приоритет, следовательно, происходит «вытеснение», в частности, когда высокоприоритетная задача получила ожидаемое сообщение, освободился запрошенный ею ресурс, произошло связанное с ней внешнее событие, исчерпался заданный интервал времени.
|
|
|
Рис. 3.2.1. Основные варианты планирования задач в СРВ
Диапазон СРВ весьма широк, начиная от полностью статических систем, где все задачи и их приоритеты заранее определены, до динамических систем, где набор выполняемых задач, их приоритеты и режимы планирования может меняться в процессе планирования.
Существуют, в частности, системы, где каждая отдельная задача может участвовать в любом из двух или более алгоритмов планирования, например, вытеснение, разделение времени и кооперативность.
В общем случае режимы планирования задач должны соответствовать критериям оптимальности функционирования системы. Однако, если для систем «жесткого» РВ такой критерий очевиден, т.е. всегда и все делать во время, то для системы «мягкого» РВ этот критерий, как правило, размыт и имеет, например, вид: минимальное «максимальное запаздывание» или средневзвешенная своевременность завершения операций.
|
|
|
В зависимости от критериев оптимальности может применяться более изощренные (сложные) алгоритмы (режимы) планирования задач, которые могут существенно отличаться от рассмотренных. Например, планировщик может анализировать момент выдачи критичных по времени управляющих воздействий и запускать на выполнение ту задачу, которая отвечает за ближайшие из них.
Необходимо отметить, что в одной СРВ могут одновременно сосуществовать задачи «жесткого» и «мягкого» РВ, и что только одна из этих задач, обладающая наивысшим приоритетом, может быть по-настоящему детерминированной.
Не рекомендуется увлекаться приоритетами. Если СРВ нормально работает, когда все задачи имеют одинаковый приоритет, то этот режим можно обосновано считать вполне приемлемым. Если нет (СРВ не работает нормально), то можно присвоить высокий приоритет «критической» задаче и низкий приоритет – всем остальным.
Если у вас больше одной критической задачи при недостаточном быстродействии системы, имеет смысл рассмотреть вариант использования более быстродействующего оборудования или вариант использования многопроцессорной конфигурации, либо, отказавшись от ОСРВ, перейти к простому циклическому режиму (алгоритму) планирования.
|
|
|
Часто разработчики стараются свести СРВ, а точнее ПО СРВ, к наиболее простым конфигурациям, иногда даже в ущерб эффективности использования вычислительных ресурсов. Причина понятна, поскольку сложные динамические (с изменяющимися приоритетами) системы весьма трудно анализировать и отлаживать. Поэтому предпочтительнее использовать более мощный процессор, чем иметь в будущем проблемы из-за непредвиденного поведения системы.
В связи с этим большинство существующих СРВ представляют собой статические системы с фиксированным приоритетом. Часто в системах реализуется несколько режимов работы, каждый из которых имеет свой набор выполняемых задач с заранее заданными приоритетами.
Значительная часть особо ответственных систем реализуется вообще без использования ОСРВ.
Синхронизация задач в ОСРВ
Хотя каждая задача в СРВ, как правило, выполняет отдельную функцию, часто возникает необходимость согласованности или синхронизации действий, выполняемых различными задачами.
Причины, требующие подобной синхронизации можно свести к следующим:
1.Функции, выполняемые различными задачами связаны друг с другом, в частности, одна задача готовит исходные данные для другой, которая не выполняется до тех пор, пока не получит соответствующего сообщения. (Краткое название причины – связанные задачи).
2.Необходимо упорядочить доступ нескольких задач к общему ресурсу (Общие ресурсы).
3.Необходима синхронизация задачи с внешним событием.
4.Необходима синхронизация задач по времени. Диапазон различных вариантов в этом случае достаточно широк: от привязки момента выдачи управляющего воздействия к точному астрономическому времени до простой задержки выполнения задачи на определенный интервал времени.
Связанные задачи
Взаимное согласие задач с помощью сообщений является одним из важнейших принципов ОСРВ. Способы реализации межзадачного обмена отличаются большим разнообразием, что, в свою очередь, привело к обилию терминов, связанных с этой проблемой, а именно используются такие понятия, как сообщение, почтовый ящик, сигнал, событие, прокси.
Объем информации, передаваемый в сообщении, может меняться от одного бита до всей свободной емкости памяти системы.
В большинстве ОСРВ ее компоненты также как и пользовательские задачи способны принимать и передавать синхронные и асинхронные сообщения. При этом в первом случае циркуляция сообщений оказывает непосредственное влияние на планирование задач. А во втором случае, доставка сообщений задаче производится после того, как она в плановом порядке получит управление. Иногда сообщения передаются через отведенный для этого буфер определенного размера, т.е. почтовый ящик. При этом новое сообщение либо затирает старое, даже не смотря на то, что оно не обработанное, либо (что наиболее часто) используется другой принцип, когда каждая задача имеет свою очередь сообщений, в конец которой ставится всякое вновь полученное сообщение. Стандартный принцип обработки очереди сообщений – первым вошел, первым вышел; хотя этот принцип далеко не всегда оптимально соответствует поставленной задаче. Поэтому в некоторых ОСРВ предусматривается возможность, когда сообщение от высокоприоритетной задачи обрабатывается в первую очередь, т.е. сообщение наследует приоритет пославшей его задачи.
Сообщение может содержать как сами данные, предназначенные для передачи, так и указатель на такие данные. В последнем случае обмен данными может производиться с помощью разделенных областей памяти, разделенных файлов и т.п.
Общие ресурсы
Ресурс – общий термин, описывающий техническое устройство или область памяти, которая может одновременно использоваться только одной задачей (потоком).
Процессорное время тоже представляет собой своеобразный конкурентно используемый ресурс СРВ.
Трудно переоценить важность правильной организации взаимодействия различных задач в СРВ при доступе к общим ресурсам.
Для многозадачных СРВ применяющих алгоритмы планирования с вытеснением, характерны и весьма опасны время-зависимые ошибки или «гонки».
Например, в бортовом компьютере самолета МИГ-29 среди прочих работают две задачи. Первая задача, взаимодействуя с радиолокационной системой (РЛС) определяет удаление и направление до цели. Вторая задача использует эти данные при пуске ракет класса «воздух – воздух». Если первая задача, записав в глобальную структуру данных только удаление до цели, будет прервана второй задачей, не успев записать туда направление до цели, то вторая задача считает из этой структуры ошибочные данные, что, в свою очередь, приведет к неудачному пуску ракеты.
Ошибки, обусловленные «гонками», во-первых, характерны для работы с любыми ресурсами, доступ к которым имеет несколько задач и, во-вторых, происходят только в результате совпадения определенных условий, а поэтому с трудом обнаруживаются на этапе отладки (тестирования) СРВ.
Возможные пути решения проблемы:
1.Не использовать алгоритмы планирования задач с вытеснением.
2.Использовать специальный сервер ресурсов, т.е. задачу, ответственную за упорядочивание доступа к ресурсу. В этом случае запрос на изменение значений глобальных данных посылается этому серверу в виде сообщения. Аналогичный подход приемлем и для физических устройств.
3.Запретить прерывание на время доступа к разделяемым данным.
4.Использовать для упорядочивания доступа к разделяемым ресурсам так называемые «семафоры».
Семафоры – средство (механизм ОСРВ), который часто используется для синхронизации доступа к ресурсам.
В простейшем случае, семафор представляет собой байтовую переменную, принимающую значения 0 или 1.
Существуют более сложные семафоры («счетные»), представляющие собой счетчики.
Участки программ, где происходит обращение к разделяемым ресурсам, называются критическими секциями.
Т.к. процессы обычно не имеют доступа к данным друг друга, а ресурсы физических устройств, как правило, управляются задачами – серверами (драйверами), наиболее типична ситуация, когда «гонки» за доступ к глобальным переменным устраивают различные потоки. Для того чтобы гарантировать, что критическая секция исполняется в каждый момент времени только одним потоком, используют механизм, подобный семафорам, который называют mutex.
Практически mutex представляет собой разновидность семафора, который сигнализирует другим потокам, что критическая секция уже кем-то выполняется.
Другой возможной неприятностью в борьбе за ресурсы является «смертельный захват» (тупик, клинч, зацикливание, зависание и т.д.). Причина подобной ситуации достаточно проста – задачи не поделили ресурсы.
Например, одна задача захватила ресурс клавиатуры и ждет, когда освободится ресурс дисплея, вторая задача, напротив, захватила ресурс дисплея и ждет, пока освободится клавиатура.
Подобная ситуация может длиться бесконечно долго, а захват в этом случае называется взаимным.
Бывают более сложные ситуации, когда в захват включаются 3 и более задач, тогда захват называют циркулярным.
В подобных ситуациях рекомендуется придерживаться тактики «или все, или ничего», т.е. когда задача не может получить все необходимые для дальнейшей работы ресурсы, она должна освободить все ранее захваченные ресурсы и запуститься несколько позже.
Еще одной проблемой СРВ является инверсия (девальвация) приоритетов.
Алгоритмы (режимы) планирования задач в СРВ должны находится в соответствии с методами управления доступа ко всем ресурсам, а все вместе соответствовать критериям оптимального функционирования системы. Эффект инверсии приоритетов следует рассматривать грубым нарушением выше описанной гармонии. Эффект инверсии приоритетов несколько похож на «смертельный захват». Однако он более сложен.
Например, в СРВ работают: первая высокоприоритетная задача, вторая среднеприоритетная задача и третья низкоприоритетная задача. Пусть в определенный момент времени первая и вторая задачи блокированы в ожидании какого-либо внешнего события. Допустим, получившая в результате этого управление, третья задача захватила семафор А и не успела его отдать, т.к. была прервана первой задачей. В свою очередь, первая задача при попытке захватить семафор А была блокирована, т.к. он (семафор) уже захвачен третьей задачей. Если к этому моменту вторая задача находится в состоянии готовности, то управление после этого будет передано именно ей, поскольку ее приоритет более высокий, чем у третьей задачи. В сложившейся ситуации вторая задача может использовать процессорное время бесконечно долго. При этом самая высокоприоритетная первая задача не может функционировать.
Дата добавления: 2018-08-06; просмотров: 1271; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!