Механизмы межзадачных связей

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

Реализация механизмов межзадачных связей возлагается на операционную систему: информационные объекты, связанные с функционированием таких механизмов, контролируются операционной системой. Доступ к ним (как и к любым системным объектам) со стороны приложений возможен через системные вызовы (т.е., через интерфейс прикладных программ). Операционные системы реального времени реализуют разнообразные типы таких механизмов. Доступ к этим механизмам со стороны прикладных задач обеспечивается предоставляемыми операционной системой элементами интерфейса прикладных программ.

7.1. Установочные сообщения. Примером механизмов, обеспечивающих обмен чисто знаковой информацией, являются механизмы приема/передачи установочных сообщений (state messages). Операции приема/передачи установочных сообщений не оказывают непосредственного влияния на синхронизацию исполнения действующих заданий. Установочные сообщения представляют собой системные объекты, предназначенные для хранения таких данных, как определяемые приложениями коды текущих режимов работы прикладных подсистем, цифровые значения параметров состояний контролируемых приложениями процессов (например, таких, как температура, давление, высота, скорость). В общем случае формат данных, фиксируемых в объекте типа установочного сообщения (число, текст, указатель и т.п.), определяется при его создании. Формат каждого из установочных сообщений неизменен в ходе работы системы, память для его размещения выделяется статически. Доступ к установочным сообщениям открыт как по чтению, так и по записи данных.

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

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

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

7.2. Очереди сообщений. Другую разновидность межзадачных интерфейсов, ориентированных на обмен чисто знаковой информацией, составляют механизмы доступа к очередям сообщений (queued messages). Как и другие системные объекты, служащие для реализации межзадачных интерфейсов, очереди сообщений контролируются операционной системой и доступны прикладным задачам через интерфейс прикладных программ.

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

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

Если задание _jt _i пытается принять сообщение из очереди, которая в данный момент оказалась пустой (все ранее размещенные сообщения уже выданы по запросам приема сообщений из этой очереди), то ОС извещает _jt _i об отсутствии затребованного сообщения. Операции приема/передачи, выполняемые с очередями сообщений, не оказывают непосредственного влияния на синхронизацию действующих заданий.

7.3. Сигналы. Как отмечалось в подразделе 3.4, в ходе приема/передачи чисто сигнальной информации задания не обмениваются знаковыми информационными элементами – весь смысл приема/передачи сигналов заключается в синхронизации операций, выполняемых взаимодействующими заданиями. Соответствующий механизм называется механизмом передачи сигналов. Синхронизация действий, выполняемых заданием, передающим сигнал и заданием, принимающим этот сигнал, обеспечивается тем, что операция приема сигнала совмещается во времени с парной ей операцией передачи этого сигнала. Такое возможно только в том случае, если к моменту передачи сигнала принимающее задание настроено на прием этого сигнала, если оно находится в состоянии ожидания момента возникновения этого сигнала, момента генерации этого сигнала передающим заданием.

Операция приема сигнала разделяется на две стадии (рис. 26). Первая стадия начинается в момент t (e _ожд(_it ₁), s) вызова заданием _it ₁ сервисной функции приема сигнала s. Результатом выполнения первой стадии является приостановка задания _it ₁, перевод его в состояние ожидания момента поступления сигнала s. В этом состоянии задание пребывает до тех пор, пока ожидаемый сигнал не будет генерирован и направлен ожидающему его заданию _it ₁. На диаграмме рис. 26 генерация сигнала s выполняется заданием _jt ₂ в момент t (e _пос(_jt ₂), s), что приводит к выполнению второй стадии операции приема сигнала s – принимающее сигнал задание _it ₁ освобождается из состояния ожидания и либо становится текущим (вытесняет _jt ₂), либо пополняет список ожидающих предоставления CPU.

Рис. 26. Выполнение операции приема сигнала

Операция приема сигнала является приостанавливающей операцией – ее выполнение непременно переводит текущее задание в состояние ожидания. Операция передачи сигнала является освобождающей операцией – ее выполнение освобождает принимающее сигнал задание из состояния ожидания.

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

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

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

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

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

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

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

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

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

Рис. 27. Прием/передача синхронизирующих сообщений

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

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

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

· перечень ожидающих заданий,

· счетчик состояния.

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

Взаимодействие заданий через считающие семафоры осуществляется посредством использования двух основных типов сервисных функций – вызовами условно приостанавливающей операции “закрыть” (down), и условно освобождающей операции “открыть” (up). Операция “закрыть” для считающего семафора эквивалентна операции “прием сообщения” для синхронизирующих сообщений. Операция “открыть” эквивалентна операции “передача сообщения”.

Операция “открыть” увеличивает значение счетчика состояния накопителя на единицу аналогично тому, как в случае механизма синхронизирующих сообщений операция “ передача сообщения” пополняет (на единицу) состав поступивших в накопитель сообщений. Операция “закрыть” уменьшает значение счетчика состояния накопителя на единицу аналогично тому, как в случае механизма синхронизирующих сообщений операция “прием сообщения” сокращает (на единицу) состав поступивших в накопитель сообщений.

В ситуации, когда задание _jt _i пытается принять выполнить операцию “закрыть” при нулевом или отрицательном значении счетчика состояния накопителя, задание _jt _i приостанавливается, переводится в состояние ожидания. В состоянии ожидания _jt _i остается до тех пор, пока оно не будет освобождено выполнением очередной операции ”открыть”.

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

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

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

7.5. Логические шкалы. Логические шкалы (шкалы событий) представляют собой наборы двоичных признаков, служащие для синхронизации исполнения заданий. Каждый из входящих в набор признаков может принимать оно из двух значений: “установлен” или “снят”. Присвоение признаку значения “установлен” рассматривается как синхронизирующее событие. Содержательное значение признаков (событий) определяется разработчиками приложений, ОС при установке события лишь анализирует наличие заданий, ожидающих возникновения этого синхронизирующего события. Действующее задание может обратиться к ОС с запросом на приостановку своего исполнения до тех пор, пока не возникнет требуемая для продолжения задания комбинация синхронизирующих событий (признаков). Задание будет оставаться в состоянии ожидания до тех пор, пока другие действующие задания не установят требуемую комбинацию признаков.

7.6. Мьютексы. Чтобы исключить одновременный доступ к разделяемым ресурсам со стороны различных заданий, для каждого из разделяемых ресурсов g формируется синхронизирующий объект, контролирующий доступ к ресурсу g и называемый мьютексом. Для обеспечения такого контроля перед входом в критический интервал по ресурсу g над соответствующим мьютексом выполняется операция “захват” (lock). После этого задание, выполнившее операцию “захват”, приступает в выполнению действий в рамках критического интервала по ресурсу g. При выходе из критического интервала по ресурсу g выполняется операция “освобождение” (unlock) над соответствующим мьютексом.

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

· при инициализации мьютекса счетчику его состояния присваивается значение единица (доступ к защищаемому ресурсу открыт),

· при инициализации мьютекса ни одно из заданий не находится в рамках критического интервала по ресурсу, доступ к которому контролируется данным мьютексом,

· после выполнения над мьютексом операции захвата заданием _jt _i только задание _jt _i может выполнить операцию освобождения над этим мьютексом.

При выполнении заданием _jt _i операции ”захват” для мьютекса со значением счетчика единица (контролируемый мьютексом ресурс g свободен) счетчик состояния обнуляется, задание _jt _i занимает ресурс g, выполняя действия своего критического интервала по доступу к этому ресурсу. На выходе из критического интервала _jt _i выполняет операцию “освобождение”, значение счетчика состояния увеличивается на единицу.

При выполнении заданием _jt _i операции ”захват” для мьютекса с нулевым или отрицательным значением счетчика накопителя (контролируемый мьютексом ресурс g занят) эта операция выполняется в две стадии. Результатом выполнения первой стадии является приостановка задания _jt _i, перевод его в состояние ожидания, задание _jt _i пополняет перечень заданий, ожидающих освобождения ресурса g; значение счетчика состояний уменьшается на единицу. Вторая стадия выполняется в момент, когда задание, занимавшее ресурс g, освобождает этот ресурс и доступ к нему предоставляется заданию _jt _i (задание _jt _i изымается из соответствующего перечня и само занимает ресурс g, выполняя действия своего критического интервала по доступу к этому ресурсу); значение счетчика состояния увеличивается на единицу.

Анализ приведенных ограничений на инициализацию мьютекса и выполнение операций над ним показывает, что счетчик состояния мьютекса может принимать значения n_g, не превышающие единицы. В случае, если n_g = 1, контролируемый ресурс свободен. Если n_g < 0, то это означает, что освобождения ресурса g ожидают | n_g | заданий.

Аналогично механизмам синхронизирующих сообщений и считающих семафоров механизм на базе использования мьютексов является одной из разновидностей механизмов взаимодействия заданий, сочетающих передачу сигнальной и знаковой информации. Так, операция “освобождение” над мьютексом со значением счетчика состояния n_g = 0 выполняет лишь знаковую роль. Если же n_g < 0, то операция освобождения выполняет истинно сигнальную роль. В этом случае перечень ожидающих заданий не пуст, одно из этих заданий принимает ожидаемый сигнал – выводится из состояния ожидания (т.е., для него выполняется вторая стадия операции “закрыть”); операция ”освобождение” и вторая стадия операции “захват” для ожидавшего задания выполняются нераздельно.

7.7. Услуги ОС для прикладных обработчиков прерываний. Состав услуг (и, соответственно, состав элементов интерфейса прикладных программ), предоставляемых операционной системой обработчикам прерываний отличается от состава услуг, предоставляемых программно контролируемым задачам. Так, например, рассмотренные в разделе 5 системные вызовы EnterISR() и LeaveISR() должны быть доступны только из обработчиков прерываний, обращения к ним из программно-контролируемых заданий недопустимы. Выполнение системных вызовов EnterISR() и LeaveISR() в рамках программно контролируемых заданий чревато непредсказуемыми последствиями.

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

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

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

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

Контрольные вопросы.

1. Какого рода информацией (знаковой или сигнальной) обмениваются задания по линиям межзадачных связей?

2. Какого рода информация (знаковая или сигнальная) передается через установочные сообщения?

3. Почему использование очередей сообщений не сопровождается обменом сигнальной информацией между действующими заданиями?

4. В каком состоянии при передаче сигнала должно находиться принимающее задание, чтобы передаваемый сигнал был им воспринят?

5. Какие условия должны быть выполнены, чтобы передача синхронизирующего сообщения выполнило сигнальную роль?

6. Что общего и в чем состоят различия между считающими семафорами и синхронизирующими сообщениями?

7. В чем состоит основное назначение синхронизирующих механизмов типа мьютексов?

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

9. Почему для обработчиков прерываний запрещен переход в состояние ожидания?

Планирование заданий

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

8.1. Варианты дисциплины планирования. Выше был рассмотрен пример (рис. 9, табл. 4), показывающий, как выбор дисциплины планирования влияет на своевременность выполнения заданий. В табл. 6 приведены используемые в различных системах реального времени варианты дисциплины планирования.

Каждый из представленных вариантов дисциплины планирования по-своему определяет порядок предоставления ресурса процессора действующим заданиям. Этот порядок может быть представлен отображением на числовую ось, что означает пополнение состава характеристик заданий специальным числовым параметром “приоритет задания”. Значения приоритетов pr (_jt _i) задают порядок обслуживания процессором действующих заданий, в ходе функционирования системы этот порядок определяет очередность предоставления ресурса процессора действующим заданиям: процессор предоставляется заданию, имеющему наивысший приоритет. В подразделе 4.2 порядок облуживания заданий при использовании дисциплин FIFO, LIFO и SPT был представлен в терминах приоритетов заданий.

Таблица 6. Варианты порядка обслуживания заданий процессором.

Отметим, что для дисциплин планирования RMS (частотно-монотонное) и DMS (монотонное по срочностям) распределение приоритетов зависит от значений параметров задач, а для остальных дисциплин планирования в табл. 6 оно определяется текущими значениями параметров заданий. То есть, для RMS и DMS дисциплин планирования приоритеты всех однотипных заданий совпадают (pr (_xt _i)≡ pr (_yt _i) = pr (t _i)), определяются статически. И, напротив, для остальных дисциплин планирования из табл. 6 приоритеты заданий определяются динамически, различные экземпляры одной и той же задачи в различных ситуациях могут попасть как в число относительно высокоприоритетных, так и в число относительно низкоприоритетных.

При разработке СРВ принципы распределения значений статических приоритетов между задачами могут диктоваться различными обстоятельствами. Например, если в системе есть две группы задач – с жесткими и с мягкими требованиями реального времени, то задачи первой группы целесообразно определить как сравнительно более приоритетные. Так или иначе, при использовании дисциплин со статическими приоритетами шкала приоритетов задач строится в ходе разработки системы.

Вновь возникшее задание _j t _i начинает исполняться с приоритетом, равным статическому значению приоритета задачи t _i. В дальнейшем в ходе исполнения _j t _{i ,} допускается более или менее кратковременное повышение значения его действующего приоритета. Это может происходить как по инициативе самой задачи (например, для выполнения неделимых действий), так и по инициативе ядра ОС (например, при реализации механизмов доступа к разделяемым ресурсам). Таким образом, динамический приоритет задания _{, j} t _i не всегда совпадает со статическим значением приоритета, назначаемым для задачи t _i на этапе разработки системы.

Во многих системах допускается совпадение значений статических приоритетов для различных задач. То есть, все множество задач расслаивается на приоритетные уровни, k -му уровню соответствует множество задач { t _i | pr (t _i) = k } с совпадающими значениями приоритетов. В этом случае должен быть определен порядок предоставления ресурса процессора для заданий, соответствующих одному и тому же приоритетному уровню.

Стандарт POSIX предусматривает использование двух вариантов порядка обслуживания заданий в рамках одного приоритетного уровня: FIFO (first in first out) и RR (round robin). Оба варианта предусматривают, что для каждого из приоритетных уровней строится очередь заданий, принадлежащих этому приоритетному уровню и готовых использовать ресурс процессора. Вновь возникающее задание ставится в конец очереди. В рамках одного уровня наиболее приоритетным является задание в начале очереди.

Различие между FIFO и RR дисциплинами состоит в следующем. В случае FIFO дисциплины задание _jt _i, продвинувшееся в начало очереди, остается там вплоть до момента завершения t (e _зав(_jt _i)). При RR дисциплине заданию _jt _i, продвинувшемуся в начало очереди, выделяется фиксированный лимит процессорного времени. Если этот лимит израсходован прежде, чем наступит момент t (e _зав(_jt _i)) завершения задания, то _jt _i, перемещается в конец очереди. Исполнение t (e _зав(_jt _i)) будет продолжено тогда, когда _jt _i вновь продвинется в начало очереди.

Выделение приоритетных уровней с RR дисциплиной обслуживания внутри уровня дает пример сочетания статических и динамических элементов планирования заданий в рамках одной системы.

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

Входными данными для проведения анализа выполнимости служат формальные модели задач и системы в целом. Для анализа выполнимости модель системы должна содержать:

· описание состава системы (перечень задач и разделяемых ресурсов),

· формальные модели для каждой из задач,

· указание используемой дисциплины планирования.

Формальная модель каждой задачи t _i представляется набором характеристик, в числе которых присутствуют:

· характеристики последовательности моментов возникновения заданий _jt _i (например, синхронный или асинхронный порядок возникновения заданий, период P _i, а для синхронных задач – значение j(t _i) фазы возникновения заданий),

· объем C_i процессорного времени, требуемый для выполнения задачи t _i,

· значение D _i предельного срока выполнения для задачи t _i,

· характеристики планирования (например, статический приоритет pr (t _i), вытесняемость задачи).

Принадлежность формальной модели системы к тому или иному классу моделей определяется составом характеристик задач. Интерес представляют те классы моделей, для которых разработаны эффективные методы анализа выполнимости. При этом задача t _i считается выполнимой, если при любых возможных сценариях работы системы для всех экземпляров задачи t _i время отклика r (_jt _i) не превышает D _i. Комплекс задач в целом считается выполнимым, если выполнима каждая из составляющих его задач.

8.3. Плотность загрузки процессора. Простейшие методы анализа выполнимости программных приложений реального времен основаны на использовании данных о плотности загрузки (utilization) процессора каждой из составляющих приложение задач t _i. Плотность загрузки u _i процессора задачей t _i это та часть производительности процессора, которая должна выделяться для выполнения заданий типа t _i. Величина u (t _i) является производным параметром модели задачи, она равна отношению объема C_i процессорного времени, требуемого для выполнения задачи t _i, к величине периода P_i:

u _i = C_i / P_i.

Для некоторых классов программных приложений проверка выполнимости может быть сведена к простому суммированию значений u _i. Рассмотрим класс программных приложений, удовлетворяющих следующим условиям:

а) приложение состоит из периодических или апериодических задач со статически назначаемыми приоритетами,

б) все задачи являются вытесняемыми и независимыми,

в) предельный срок выполнения для каждой из задач t _i совпадает со значением ее периода D _i = P_i,

г) приложения содержит только задачи с кратными значениями периодов (для любой пары задач t _i и t _j при P_i > P_j величина P_i кратна P_j.).

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

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

Приложения, удовлетворяющее условию г), называют приложениями с гармоническими периодами задач.

Можно показать, что если для приложения, отвечающего условиям а - г используется частотно-монотонная дисциплина планирования (RMS), то выполнимость приложения гарантируется в случае соблюдения неравенства:

∑u _i £ 1,

где суммирование ведется по всем задачам. В крайнем случае, когда ∑u _i =1, приложение использует производительность CPU на все 100%.

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

8.4. Приложения с негармоническими периодами задач (UB-тест). Величина ∑u _i суммарной плотности загрузки CPU может быть использована не только для оценки выполнимости приложений с гармоническими периодами задач. Так, в начале 1970-х годов был получен следующий результат: если для приложения, содержащего n задач, и отвечающего лишь трем из перечисленных выше условий, а именно, условиям а) – в) используется частотно-монотонная дисциплина планирования (RMS), то выполнимость приложения гарантируется в случае соблюдения неравенства:

∑u _i £ n (2^{1/ n} – 1).

Правую часть приведенного неравенства, функцию UB(n) = n (2^{1/ n} – 1), называют граничным значением загрузки (utilization bond) для приложения, состоящего из n задач. С ростом n от единицы до бесконечности величина UB(n) монотонно убывает от единицы до ln2 ≈ 0.693. Проверка соответствия приложения приведенному неравенству называют UB-тестом. Таким образом, выполнимость приложения, отвечающего условиям а) – в), гарантирована при положительном результате UB-теста и использовании RMS дисциплины планирования. Доказано, что для приложений, отвечающих условиям а) – в), RMS дисциплина планирования является оптимальной.

8.5. Оценка времени отклика заданий. Следующие шаги по развитию методов анализа выполнимости для более широкого класса моделей приложений связаны с изменениями формулировок условия в.

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

в ^*) для каждой из задач t _i значение D _i предельного срока выполнения отвечает неравенствам C_i < D _i и D _i £ P_i.

Замена условия в условием в ^* приводит к расширению рассматриваемого класса моделей приложений. Для такого расширенного класса, то есть, для класса приложений, отвечающих требованиям а, б, и в ^*, оптимальной является DMS дисциплина планирования. Но UB-тест в этом случае непригоден для проверки выполнимости приложения. Для таких моделей используются методы анализа выполнимости, опирающиеся на вычисление верхней оценки R _i величины r (_xt _i) времени отклика для каждого типа t _i заданий, возникающих в ходе работы приложения.

В рассматриваемой модели время отклика r (_xt _i) складывается из двух составляющих:

· объема процессорного времени, требуемого для выполнения самого _xt _i,

· продолжительности вытеснения задания _xt _i более приоритетными заданиями.

Максимальное значение первой составляющей по определению равно C_i. Максимальное число вытеснений задания _xt _i экземплярами более приоритетной задачи t _j равно ближайшему (сверху) целому é r (_xt _i)/ P_j ù от деления длины интервала r (_xt _i) существования задания на величину P_j периода задачи t _j. Исходя из этого максимальное время отклика задания типа t _i определяется выражением

R _i = C_i + ∑ C_j é R _i / P_j ù

где суммирование ведется по всем более приоритетным по отношению к t _i задачам. Полученное выражение рекурсивно, поскольку искомая величина R _i входит как в левую, так и в правую его часть. Решение для R _i находится методом последовательных приближений с использованием рекуррентного соотношения:

^{n+ 1} R _i = C_i + ∑ C_j é ⁿR _i / P_j ù

с начальным значением ⁰R _i = 0 и остановкой процесса рекуррентных вычислений при достижении равенства ^{n+ 1} R _i = ⁿR _i.

Методы анализа выполнимости на основе оценки максимального времени отклика заданий развиваются в направлении расширения классов моделей программных приложений.

Контрольные вопросы.

1. Привести примеры дисциплин предоставления заданиям ресурса процессора.

2. Для каких дисциплин обслуживания приоритеты заданий определяются статически?

3. Чем различаются FIFO и RR дисциплины планирования?

4. Что понимается под выполнимостью задач и приложений СРВ? В чем состоит анализ выполнимости?

5. Какие параметры задач должна содержать модель СРВ для проведения анализа выполнимости?

6. Как определяется термин «плотность загрузки процессора» в отношении отдельной задачи СРВ и в отношении приложения в целом?

7. Какая дисциплина планирования считается оптимальной для определенного класса моделей СРВ? Для каких классов моделей RMS дисциплина планирования является оптимальной?

8. Какие модели приложений позволяют проводить анализ выполнимости с использованием UB-теста (функции граничных значений загрузки процессора)?

9. Указать класс моделей приложений, для которых разработаны алгоритмы вычисления максимального времени отклика задач.

Поиск по сайту: