ОЦЕНКА ВРЕМЕНИ ДОСТАВКИ СООБЩЕНИЙ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ С CAN-ИНТЕРФЕЙСОМ
ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
УДК 681.3
В. В. НИКИФОРОВ, В. И. ШКИРТИЛЬ
ОЦЕНКА ВРЕМЕНИ ДОСТАВКИ СООБЩЕНИЙ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ
С CAN-ИНТЕРФЕЙСОМ
Предложен подход к оценке верхней границы времени доставки сообщений между узлами распределенных систем реального времени, построенных на базе CAN-интерфейса. Показано, что для проверки гарантий своевременности доставки сообщений между узлами таких систем могут использоваться методы, аналогичные методам проверки гарантий своевременности выполнения задач в однопроцессорных системах реального времени.
Ключевые слова: системы реального времени, распределенные программные комплексы, CAN-интерфейс, выполнимость задач.
Введение. В ряду ключевых требований к реализации целевых функций систем реального времени (СРВ) выделяются такие, как надежное, предсказуемое поведение, эффективное использование аппаратных средств, обеспечение гарантий своевременного выполнения возлагаемых на СРВ задач. Методы построения и реализации программных приложений для СРВ и методы анализа соответствующих вычислительных моделей, направленные на обеспечение этих требований, развиваются с 1970-х гг. по настоящее время [1—4]. Были разработаны рациональные методы построения программных комплексов с использованием независимых задач реального времени, а также комплексов взаимосвязанных задач, разделяющих общие аппаратные и информационные ресурсы.
В многозадачной системе длительность временного интервала выполнения задачей возлагаемых на нее функций (время отклика) зависит не только от объема исполняемых действий, но и от продолжительности ожидания требуемых ресурсов. Этим обусловлено взаимное влияние (интерференция) задач, приводящее к более или менее значительному увеличению времени их отклика. Для различных архитектур комплексов прикладных задач СРВ найдены методы обеспечения гарантий своевременности выполнения функций системы в условиях такой интерференции.
В частности, для произвольного статического назначения приоритетов невытесняемых задач τ1, τ2 ,…, τn , обслуживаемых одним процессором, определен способ вычисления времени отклика Ri для каждой из задач τi . Удовлетворительный результат сравнения величины Ri с допустимым для нее значением Di гарантирует своевременность выполнения задачи τi .
В распределенных СРВ прикладные программы рассредоточены по узлам, соединяемым коммуникационными каналами. В последнее время для локальных распределенных СРВ широко используется сетевой интерфейс CAN (Controller Area Network) [5—6], обеспечивающий связь узлов сети путем доступа к общей шине. Очередность передачи сообщений, генерируемых в узлах сети, определяется статически присваиваемыми сообщениям значениями
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
34 В. В. Никифоров, В. И. Шкиртиль
приоритетов. Приоритеты сообщений характеризуют отношение порядка предоставления коммуникационного ресурса. Порожденное в одном из узлов сети с CAN-интерфейсом сообщение с низким приоритетом ожидает момента, когда коммуникационная система окажется свободной от передачи сообщений с более высоким приоритетом. Таким образом, при заданном быстродействии коммуникационной системы время доставки сообщения зависит не только от его длины, но и от загруженности сети более приоритетными сообщениями, т.е. имеет место интерференция передаваемых по сети сообщений, аналогичная интерференции задач многозадачного приложения, исполняемого одним процессором. Для оценки продолжительности выполнения распределенных функций СРВ актуальна разработка методов оценки времени доставки сообщений в условиях такой интерференции.
В настоящей статье показано, как известные методы оценки своевременности выполнения прикладных задач СРВ могут быть адаптированы к оценке своевременности доставки сообщений по сети с CAN-интерфейсом; приводятся метод оценки времени отклика невытесняемых задач с произвольным назначением статических приоритетов и необходимые сведения о CAN-интерфейсе; рассматривается подход к адаптации метода оценки времени отклика невытесняемых задач, который обеспечивает проверку гарантий своевременности доставки сообщений по сети с CAN-интерфейсом.
Оценка выполнимости независимых задач. Согласно принципу структурного соответствия асинхронный характер поступления внешних данных приводит к построению программного приложения СРВ в виде десятков асинхронно исполняемых программных компонентов. Действие каждого из асинхронных компонентов должно завершиться своевременно, в рамках фиксированного временного интервала.
Как правило, число таких компонентов значительно превышает число имеющихся в системе процессоров. Это означает, что асинхронные программные компоненты исполняются в квазипараллельном режиме, предполагающем попеременное переключение процессора между обслуживаемыми им программными компонентами. Возникает интерференция программных компонентов: продолжительность исполнения отдельного компонента зависит не только от необходимого ему объема процессорного времени, но и от того, как часто и как надолго процессор будет переключаться на исполнение других компонентов.
Для проверки гарантий своевременности завершения выполнения программных компонентов строятся вычислительные модели приложений в формате, допускающем использование алгоритмов оценки выполнимости приложений и составляющих их задач. Применение допустимых форматов предполагает наложение ряда ограничений на методы планирования и структуру взаимодействия программных компонентов.
Задачи и задания. Программное приложение СРВ строится в виде комплекса задач τ1, τ2 ,…, τn — программных модулей, каждый из которых представляет собой внутренне замкнутую по передачам управления последовательную программу [5]. Составляющие комплекс задачи являются кооперативными: они ориентированы на совместное функционирование для достижения общих целей, стоящих перед системой.
Вычислительные модели, предназначенные для анализа выполнимости задач, представляются в виде, отвлеченном от содержательной составляющей обрабатываемых данных. Назначение таких моделей состоит в демонстрации ограничений, накладываемых на порядок следования системных событий, возникающих в ходе работы СРВ. При этом под системным событием понимается изменение условий распределения системных ресурсов (в первую очередь — ресурса процессорного времени). При рассмотрении вопросов функционирования СРВ различают два понятия:
— задача (task) — статический объект τi , элемент статической структуры программного приложения;
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
Оценка времени доставки сообщений в распределенных СРВ с CAN-интерфейсом
35
— задание (job) — динамический объект τi( j) , j =1, ∞ , процесс исполнения задачи τi .
Символами τi(1) , τi(2) , τi(3) , … обозначаются последовательно возникающие (порождае-
мые) задания на выполнение задачи τi .
В простейших вычислительных моделях каждая задача характеризуется следующими
параметрами:
Ti — период активизации задачи τi ,
Ci — максимальный объем процессорного времени для выполнения задани τi( j) ,
Di — допустимая продолжительность выполнения каждого из заданий τi( j) ,
prio(τi ) — приоритет задачи τi .
( ) ( )Пусть tв τi( j) и tз τi( j) — соответственно моменты времени возникновения и завер-
шения задания τi( j) . Задание τi( j) существует (является действующим) в рамках интервала
( ) ( )времени ⎡⎣tв τi( j) , tз τi( j) ⎦⎤ . Продолжительность интервала существования
( ) ( )ri( j) = tз τi( j) −tв τi( j)
называется временем отклика задания τi( j) .
Время отклика однотипных заданий может варьироваться: при j ≠ k значения ri( j) и
ri(k) могут существенно различаться. Такое различие возникает по двум причинам. Во-
первых, вследствие различий в объемах вычислений, выполняемых в рамках заданий τi( j) и
τi(k) . Если обозначить символом ci( j) требуемый для выполнения задания τi( j) объем процес-
сорного времени (суммарную продолжительность непосредственного облуживания задания
центральным процессором), то при j ≠ k значения ci( j) и ci(k) могут не совпадать. Другая воз-
можная причина различий величин ri( j) и ri(k) состоит в том, что аппаратные и информаци-
онные ресурсы, требуемые для выполнения задачи τi (в частности, ресурс процессора), мо-
гут, в рамках интервалов существования τi( j) и τi(k) , быть привлечены к выполнению других
заданий. Введенная выше величина Ri (время отклика задачи) формально определяется как
максимально возможное значение времени отклика экземпляров задачи τi :
Ri = max{ j =1, 2, ...| ri( j)}.
(1)
Задачу τi называют асинхронной задачей, если ее задания τi( j) следуют не строго пе-
риодически, при этом не чаще, чем с интервалом Ti :
( ) ( )tв τi( j+1) −tв τi( j) ≥Ti .
Спецификации функций СРВ содержат ограничения на время отклика заданий: для всех
заданий типа τi допустимая продолжительность интервала существования ограничена вели-
чиной Di , т.е.
( ) ( )tз τi( j) −tв τi( j) ≤ Di .
В условиях перекрытия интервалов существования заданий решение о том, какому из
заданий следует предоставить процессор, принимается в соответствии с используемым по-
рядком назначения приоритетов — дисциплиной планирования.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
36 В. В. Никифоров, В. И. Шкиртиль
Дисциплина планирования определяется способом назначения целочисленных приори-
( ) ( ) ( )тетов prio τi(k) действующих заданий: если prio τ(xk) < prio τ(yl) , то задание τ(xk) считается
более приоритетным, чем τ(yl) . Ниже рассматриваются системы со статическими приоритета-
ми задач: значения prio(τi ) определяются для каждой из задач при конструировании системы и являются основными параметрами планирования.
Одна из особенностей дисциплины планирования — возможность вытеснения текущего задания. Механизм вытеснения действует следующим образом: если в момент времени
( ) ( )tв τ(xk) текущим является задание типа τ(yl) , приоритет которого ниже, чем prio τ(xk) , то
процессор переключается на исполнение задания τ(xk) (оно становится текущим), а задание
τ(yl) переводится в состояние „вытеснено“ (контекст задания τ(yl) консервируется, с тем что-
бы через какое-то время в соответствии с принятой дисциплиной планирования его исполнение было продолжено).
В ряду составляющих приложение задач могут быть выделены невытесняемые задачи, отличающиеся тем, что соответствующие им задания не переводятся в состояние „вытеснено“, даже если на интервале их существования активизируются более приоритетные задачи.
Пусть в системе независимых задач все задачи τ1 , τ2 , τ3 , … являются невытесняемыми. Из-
вестно, что в таком случае время отклика [2] каждой из задач определяется методом последовательных приближений:
∑Ri = Ci +
prio(τ j )
prio(τi
)|C
j},
(2)
где суммирование осуществляется по всем задачам τ j , более приоритетным по отношению к
задачам τi ; символом ⎡⎢x⎥⎤ обозначается ближайшее к x сверху целое число.
CAN-интерфейс. Многие микроконтроллеры имеют в своем составе интерфейсные модули, реализующие коммуникационный интерфейс CAN [5, 6]. Такие микроконтроллеры используются в автомобилях, системах автоматизации технологических процессов, медицинской аппаратуре и других системах реального времени.
При использовании локальной сети, оснащенной CAN-интерфейсом, элементарные сообщения, передаваемые в однопроводную коммуникационную линию, разделяются интервалами пассивного состояния линии (логический нуль). Структура стандартного сообщения в упрощенном виде представлена на рис. 1. Сообщение начинается стартовым фреймом, за которым следуют информационные поля и стоповый фрейм.
Длина сообщения = 44 + 8N
Поле арбитража
N Поле длины
Поле данных
Поле CRC
Стоповый фр ейм
С тар товый фр ейм
Поле управления
Поле AАSСKК
Рис. 1
Узлы сети могут начинать передачу сообщения только тогда, когда линия находится в пассивном состоянии. При появлении в линии стартового фрейма все узлы синхронизируются его фронтом. Может оказаться, что два и более узла одновременно генерировали старто-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
Оценка времени доставки сообщений в распределенных СРВ с CAN-интерфейсом
37
вый фрейм, — возникает конфликт по запросу на использование коммуникационной линии. Этот конфликт должен быть устранен в ходе формирования поля арбитража.
Поле арбитража длиной 11 бит имеет двоякое назначение. Во-первых, код, размещаемый в поле арбитража, идентифицирует тип передаваемого сообщения. Во-вторых, значение этого кода определяет приоритет сообщения: нулевой код соответствует наиболее приоритетным сообщениям; чем больше значение двоичного числа, размещаемого в поле арбитража, тем ниже приоритет передаваемого сообщения. Типы передаваемых сообщений распределены между узлами сети, так что если два узла сети одновременно начали передавать сообщения, то это сообщения различных типов.
Пассивное состояние коммуникационной линии соответствует символу „1“ (рецессивный бит), активное состояние — символу „0“ (доминантный бит). В рамках поля арбитража несколько узлов осуществляют попытку передачи очередного сообщения. Каждый передающий узел контролирует состояние коммуникационной линии в ходе передачи каждого бита. Узел, передающий пассивный бит, прекращает попытку передачи сообщения, если он обнаруживает, что существует конкурирующий узел, который в этот момент передает активный бит. К моменту, когда завершается передача битов поля арбитража, только один узел продолжает передачу. Таким образом, в ходе дальнейшей передачи наиболее приоритетного сообщения предотвращается одновременная передача сообщений, генерируемых другими узлами.
Четырехбитовый код поля длины задает число байт (от 0 до 15), размещаемых в поле данных. За полями длины, данных и контрольной суммы (CRC) следует поле ACK — поле подтверждения приема. Это означает, что принимающий узел сети, обнаружив адресованное ему сообщение, помечает его как принятое в рамках формата передаваемого сообщения, а не последующих сообщений. Такое решение повышает оперативность обмена данными.
Задачи ii-го узла
Задачи (i+1)-го узла
Интерфейсный модуль i-го узла Буфер
передачи сообщений
Буфер приема сообщений
Интерфейсный модуль
(i+1)-го узла Буфер
передачи сообщений
Буфер приема сообщений
Коммуникационная линия
Рис. 2
Порядок доставки сообщений через сеть иллюстрируется схемой, представленной на рис. 2. Отдельный узел сети содержит ряд прикладных задач, которые генерируют сообщения, адресуемые либо соседним задачам, либо задачам, содержащимся в других узлах. В последнем случае сгенерированное сообщение направляется в интерфейсный модуль и размещается в его буфере. В буфере интерфейсного модуля сообщения упорядочиваются по приоритетам. В момент, когда линия переходит в пассивное состояние, интерфейсный модуль приступает к передаче самого приоритетного из сообщений, находящихся в его буфере. Эта попытка окажется удачной, если одновременно интерфейсный модуль какого-либо другого узла не пытается передать более приоритетное сообщение.
Проверка гарантий своевременности доставки сообщений. Определим время доставки сообщения как длительность временного интервала, в течение которого сообщение
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
38 В. В. Никифоров, В. И. Шкиртиль
конкретного типа, порожденное прикладной задачей, гарантированно доставляется в узел се-
ти с задачей-адресатом. Как следует из вышерассмотренного порядка доставки сообщения
через сеть с CAN-интерфейсом, при заданной частоте передачи битов по коммуникационной
линии время доставки определяется не только длиной поля данных, но и продолжительно-
стью ожидания момента освобождения коммуникационной линии от передачи более приори-
тетных сообщений. Иными словами, сформированные задачами сообщения конкурируют за
возможность получения ресурса коммуникационной линии аналогично тому, как невытес-
няемые задания в каждом из узлов системы конкурируют за предоставление ресурса процес-
сора. Наличие такой аналогии позволяет распространить рассмотренный выше метод оценки
времени отклика невытесняемых задач на время доставки сообщений по сети с CAN-
интерфейсом.
Пусть mi — тип сообщений, передаваемых по сети; mi( j) — очередное сообщение этого
( ) ( )типа; tв mi( j) и tз mi( j) — моменты поступления mi( j) в интерфейсные модули соответст-
венно передающего и приемного узлов; продолжительность ri( j) доставки экземпляра mi( j)
( ) ( )сообщения типа mi определяется разностью tз mi( j) – tв mi( j) . Период Ti следования сооб-
щений mi равен минимально возможному интервалу между поступлениями однотипных со-
общений в интерфейсный модуль передающего узла. Приоритет сообщений типа mi опреде-
ляется кодом типа сообщения, размещаемым в поле арбитража. Величиной, аналогичной ве-
личине Ci объема процессорного времени для выполнения заданий τi( j) , является длитель-
ность временного интервала, в течение которого коммуникационная линия передает сообще-
ния типа mi :
Ci
=
(44
+ 8Ni v
)
,
где vi — скорость передачи данных по коммуникационной линии (число бит в секунду),
Ni — число байт в поле данных сообщений типа mi .
Тогда время доставки Ri сообщений типа mi формально определяется выражением (1),
а его значение — решением уравнения (2). Иными словами, уравнение (2), используемое для
оценки времени отклика в системе невытесняемых задач, может быть применено и для оцен-
ки времени доставки сообщений в сетях с CAN-интерфейсом.
Заключение. Использование предложенного метода вычисления максимального време-
ни доставки сообщений в локальных сетях с CAN-интерфейсом позволяет строить программ-
ные приложения для таких сетей с проверкой гарантий своевременной реализации приклад-
ных функций, исполнение которых разнесено по различным узлам системы. Таким образом
может быть достигнуто надежное, предсказуемое поведение программных приложений ре-
ального времени, распределенных по узлам локальной сети, а также эффективное использо-
вание аппаратных средств, обеспечивающих не только своевременную обработку актуальной
информации в узлах сети, но и своевременный обмен данными между компонентами, связан-
ными коммуникационными линиями с CAN интерфейсом.
СПИСОК ЛИТЕРАТУРЫ
1. Liu C. L., Layland J. W. Scheduling algorithms for multiprogramming in hard real-time environment // J. of the ACM. 1973. Vol. 20. P. 46—61.
2. Liu J. W. S. Real-Time Systems. NJ: Prentice Hall, 2000. 590 p.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
Использование нелинейных последовательностей при построении двухдорожечных кодовых шкал 39
3. Данилов М. В. Методы планирования задач в системах реального времени // Программные продукты и системы. 2001. № 4. С. 28—35.
4. Никифоров В. В. Выполнимость приложений реального времени на многоядерных процессорах // Тр. СПИИРАН; Под общ. ред. Р. М. Юсупова. 2009. Вып. 8. С. 255—284.
5. Никифоров В. В. Разработка программных средств для встроенных систем. СПб: СПбГЭТУ, 2000. 74 с.
6. Введение в CAN 2.0B интерфейс. М.: ООО Микро-Чип, 2001: [Электронный ресурс]: .
Сведения об авторах Виктор Викентьевич Никифоров — д-р техн. наук, профессор; Санкт-Петербургский институт информа-
тики и автоматизации РАН, лаборатория технологий и систем программирования; E-mail: nik@iias.spb.su Вячеслав Иванович Шкиртиль — канд. техн. наук, доцент; Санкт-Петербургский институт информатики и автоматизации РАН, лаборатория технологий и систем программирования; E-mail: jvatlas@mail.rcom.ru
Рекомендована СПИИРАН
Поступила в редакцию 08.02.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
УДК 681.3
В. В. НИКИФОРОВ, В. И. ШКИРТИЛЬ
ОЦЕНКА ВРЕМЕНИ ДОСТАВКИ СООБЩЕНИЙ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ
С CAN-ИНТЕРФЕЙСОМ
Предложен подход к оценке верхней границы времени доставки сообщений между узлами распределенных систем реального времени, построенных на базе CAN-интерфейса. Показано, что для проверки гарантий своевременности доставки сообщений между узлами таких систем могут использоваться методы, аналогичные методам проверки гарантий своевременности выполнения задач в однопроцессорных системах реального времени.
Ключевые слова: системы реального времени, распределенные программные комплексы, CAN-интерфейс, выполнимость задач.
Введение. В ряду ключевых требований к реализации целевых функций систем реального времени (СРВ) выделяются такие, как надежное, предсказуемое поведение, эффективное использование аппаратных средств, обеспечение гарантий своевременного выполнения возлагаемых на СРВ задач. Методы построения и реализации программных приложений для СРВ и методы анализа соответствующих вычислительных моделей, направленные на обеспечение этих требований, развиваются с 1970-х гг. по настоящее время [1—4]. Были разработаны рациональные методы построения программных комплексов с использованием независимых задач реального времени, а также комплексов взаимосвязанных задач, разделяющих общие аппаратные и информационные ресурсы.
В многозадачной системе длительность временного интервала выполнения задачей возлагаемых на нее функций (время отклика) зависит не только от объема исполняемых действий, но и от продолжительности ожидания требуемых ресурсов. Этим обусловлено взаимное влияние (интерференция) задач, приводящее к более или менее значительному увеличению времени их отклика. Для различных архитектур комплексов прикладных задач СРВ найдены методы обеспечения гарантий своевременности выполнения функций системы в условиях такой интерференции.
В частности, для произвольного статического назначения приоритетов невытесняемых задач τ1, τ2 ,…, τn , обслуживаемых одним процессором, определен способ вычисления времени отклика Ri для каждой из задач τi . Удовлетворительный результат сравнения величины Ri с допустимым для нее значением Di гарантирует своевременность выполнения задачи τi .
В распределенных СРВ прикладные программы рассредоточены по узлам, соединяемым коммуникационными каналами. В последнее время для локальных распределенных СРВ широко используется сетевой интерфейс CAN (Controller Area Network) [5—6], обеспечивающий связь узлов сети путем доступа к общей шине. Очередность передачи сообщений, генерируемых в узлах сети, определяется статически присваиваемыми сообщениям значениями
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
34 В. В. Никифоров, В. И. Шкиртиль
приоритетов. Приоритеты сообщений характеризуют отношение порядка предоставления коммуникационного ресурса. Порожденное в одном из узлов сети с CAN-интерфейсом сообщение с низким приоритетом ожидает момента, когда коммуникационная система окажется свободной от передачи сообщений с более высоким приоритетом. Таким образом, при заданном быстродействии коммуникационной системы время доставки сообщения зависит не только от его длины, но и от загруженности сети более приоритетными сообщениями, т.е. имеет место интерференция передаваемых по сети сообщений, аналогичная интерференции задач многозадачного приложения, исполняемого одним процессором. Для оценки продолжительности выполнения распределенных функций СРВ актуальна разработка методов оценки времени доставки сообщений в условиях такой интерференции.
В настоящей статье показано, как известные методы оценки своевременности выполнения прикладных задач СРВ могут быть адаптированы к оценке своевременности доставки сообщений по сети с CAN-интерфейсом; приводятся метод оценки времени отклика невытесняемых задач с произвольным назначением статических приоритетов и необходимые сведения о CAN-интерфейсе; рассматривается подход к адаптации метода оценки времени отклика невытесняемых задач, который обеспечивает проверку гарантий своевременности доставки сообщений по сети с CAN-интерфейсом.
Оценка выполнимости независимых задач. Согласно принципу структурного соответствия асинхронный характер поступления внешних данных приводит к построению программного приложения СРВ в виде десятков асинхронно исполняемых программных компонентов. Действие каждого из асинхронных компонентов должно завершиться своевременно, в рамках фиксированного временного интервала.
Как правило, число таких компонентов значительно превышает число имеющихся в системе процессоров. Это означает, что асинхронные программные компоненты исполняются в квазипараллельном режиме, предполагающем попеременное переключение процессора между обслуживаемыми им программными компонентами. Возникает интерференция программных компонентов: продолжительность исполнения отдельного компонента зависит не только от необходимого ему объема процессорного времени, но и от того, как часто и как надолго процессор будет переключаться на исполнение других компонентов.
Для проверки гарантий своевременности завершения выполнения программных компонентов строятся вычислительные модели приложений в формате, допускающем использование алгоритмов оценки выполнимости приложений и составляющих их задач. Применение допустимых форматов предполагает наложение ряда ограничений на методы планирования и структуру взаимодействия программных компонентов.
Задачи и задания. Программное приложение СРВ строится в виде комплекса задач τ1, τ2 ,…, τn — программных модулей, каждый из которых представляет собой внутренне замкнутую по передачам управления последовательную программу [5]. Составляющие комплекс задачи являются кооперативными: они ориентированы на совместное функционирование для достижения общих целей, стоящих перед системой.
Вычислительные модели, предназначенные для анализа выполнимости задач, представляются в виде, отвлеченном от содержательной составляющей обрабатываемых данных. Назначение таких моделей состоит в демонстрации ограничений, накладываемых на порядок следования системных событий, возникающих в ходе работы СРВ. При этом под системным событием понимается изменение условий распределения системных ресурсов (в первую очередь — ресурса процессорного времени). При рассмотрении вопросов функционирования СРВ различают два понятия:
— задача (task) — статический объект τi , элемент статической структуры программного приложения;
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
Оценка времени доставки сообщений в распределенных СРВ с CAN-интерфейсом
35
— задание (job) — динамический объект τi( j) , j =1, ∞ , процесс исполнения задачи τi .
Символами τi(1) , τi(2) , τi(3) , … обозначаются последовательно возникающие (порождае-
мые) задания на выполнение задачи τi .
В простейших вычислительных моделях каждая задача характеризуется следующими
параметрами:
Ti — период активизации задачи τi ,
Ci — максимальный объем процессорного времени для выполнения задани τi( j) ,
Di — допустимая продолжительность выполнения каждого из заданий τi( j) ,
prio(τi ) — приоритет задачи τi .
( ) ( )Пусть tв τi( j) и tз τi( j) — соответственно моменты времени возникновения и завер-
шения задания τi( j) . Задание τi( j) существует (является действующим) в рамках интервала
( ) ( )времени ⎡⎣tв τi( j) , tз τi( j) ⎦⎤ . Продолжительность интервала существования
( ) ( )ri( j) = tз τi( j) −tв τi( j)
называется временем отклика задания τi( j) .
Время отклика однотипных заданий может варьироваться: при j ≠ k значения ri( j) и
ri(k) могут существенно различаться. Такое различие возникает по двум причинам. Во-
первых, вследствие различий в объемах вычислений, выполняемых в рамках заданий τi( j) и
τi(k) . Если обозначить символом ci( j) требуемый для выполнения задания τi( j) объем процес-
сорного времени (суммарную продолжительность непосредственного облуживания задания
центральным процессором), то при j ≠ k значения ci( j) и ci(k) могут не совпадать. Другая воз-
можная причина различий величин ri( j) и ri(k) состоит в том, что аппаратные и информаци-
онные ресурсы, требуемые для выполнения задачи τi (в частности, ресурс процессора), мо-
гут, в рамках интервалов существования τi( j) и τi(k) , быть привлечены к выполнению других
заданий. Введенная выше величина Ri (время отклика задачи) формально определяется как
максимально возможное значение времени отклика экземпляров задачи τi :
Ri = max{ j =1, 2, ...| ri( j)}.
(1)
Задачу τi называют асинхронной задачей, если ее задания τi( j) следуют не строго пе-
риодически, при этом не чаще, чем с интервалом Ti :
( ) ( )tв τi( j+1) −tв τi( j) ≥Ti .
Спецификации функций СРВ содержат ограничения на время отклика заданий: для всех
заданий типа τi допустимая продолжительность интервала существования ограничена вели-
чиной Di , т.е.
( ) ( )tз τi( j) −tв τi( j) ≤ Di .
В условиях перекрытия интервалов существования заданий решение о том, какому из
заданий следует предоставить процессор, принимается в соответствии с используемым по-
рядком назначения приоритетов — дисциплиной планирования.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
36 В. В. Никифоров, В. И. Шкиртиль
Дисциплина планирования определяется способом назначения целочисленных приори-
( ) ( ) ( )тетов prio τi(k) действующих заданий: если prio τ(xk) < prio τ(yl) , то задание τ(xk) считается
более приоритетным, чем τ(yl) . Ниже рассматриваются системы со статическими приоритета-
ми задач: значения prio(τi ) определяются для каждой из задач при конструировании системы и являются основными параметрами планирования.
Одна из особенностей дисциплины планирования — возможность вытеснения текущего задания. Механизм вытеснения действует следующим образом: если в момент времени
( ) ( )tв τ(xk) текущим является задание типа τ(yl) , приоритет которого ниже, чем prio τ(xk) , то
процессор переключается на исполнение задания τ(xk) (оно становится текущим), а задание
τ(yl) переводится в состояние „вытеснено“ (контекст задания τ(yl) консервируется, с тем что-
бы через какое-то время в соответствии с принятой дисциплиной планирования его исполнение было продолжено).
В ряду составляющих приложение задач могут быть выделены невытесняемые задачи, отличающиеся тем, что соответствующие им задания не переводятся в состояние „вытеснено“, даже если на интервале их существования активизируются более приоритетные задачи.
Пусть в системе независимых задач все задачи τ1 , τ2 , τ3 , … являются невытесняемыми. Из-
вестно, что в таком случае время отклика [2] каждой из задач определяется методом последовательных приближений:
∑Ri = Ci +
prio(τ j )
prio(τi
)|C
j},
(2)
где суммирование осуществляется по всем задачам τ j , более приоритетным по отношению к
задачам τi ; символом ⎡⎢x⎥⎤ обозначается ближайшее к x сверху целое число.
CAN-интерфейс. Многие микроконтроллеры имеют в своем составе интерфейсные модули, реализующие коммуникационный интерфейс CAN [5, 6]. Такие микроконтроллеры используются в автомобилях, системах автоматизации технологических процессов, медицинской аппаратуре и других системах реального времени.
При использовании локальной сети, оснащенной CAN-интерфейсом, элементарные сообщения, передаваемые в однопроводную коммуникационную линию, разделяются интервалами пассивного состояния линии (логический нуль). Структура стандартного сообщения в упрощенном виде представлена на рис. 1. Сообщение начинается стартовым фреймом, за которым следуют информационные поля и стоповый фрейм.
Длина сообщения = 44 + 8N
Поле арбитража
N Поле длины
Поле данных
Поле CRC
Стоповый фр ейм
С тар товый фр ейм
Поле управления
Поле AАSСKК
Рис. 1
Узлы сети могут начинать передачу сообщения только тогда, когда линия находится в пассивном состоянии. При появлении в линии стартового фрейма все узлы синхронизируются его фронтом. Может оказаться, что два и более узла одновременно генерировали старто-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
Оценка времени доставки сообщений в распределенных СРВ с CAN-интерфейсом
37
вый фрейм, — возникает конфликт по запросу на использование коммуникационной линии. Этот конфликт должен быть устранен в ходе формирования поля арбитража.
Поле арбитража длиной 11 бит имеет двоякое назначение. Во-первых, код, размещаемый в поле арбитража, идентифицирует тип передаваемого сообщения. Во-вторых, значение этого кода определяет приоритет сообщения: нулевой код соответствует наиболее приоритетным сообщениям; чем больше значение двоичного числа, размещаемого в поле арбитража, тем ниже приоритет передаваемого сообщения. Типы передаваемых сообщений распределены между узлами сети, так что если два узла сети одновременно начали передавать сообщения, то это сообщения различных типов.
Пассивное состояние коммуникационной линии соответствует символу „1“ (рецессивный бит), активное состояние — символу „0“ (доминантный бит). В рамках поля арбитража несколько узлов осуществляют попытку передачи очередного сообщения. Каждый передающий узел контролирует состояние коммуникационной линии в ходе передачи каждого бита. Узел, передающий пассивный бит, прекращает попытку передачи сообщения, если он обнаруживает, что существует конкурирующий узел, который в этот момент передает активный бит. К моменту, когда завершается передача битов поля арбитража, только один узел продолжает передачу. Таким образом, в ходе дальнейшей передачи наиболее приоритетного сообщения предотвращается одновременная передача сообщений, генерируемых другими узлами.
Четырехбитовый код поля длины задает число байт (от 0 до 15), размещаемых в поле данных. За полями длины, данных и контрольной суммы (CRC) следует поле ACK — поле подтверждения приема. Это означает, что принимающий узел сети, обнаружив адресованное ему сообщение, помечает его как принятое в рамках формата передаваемого сообщения, а не последующих сообщений. Такое решение повышает оперативность обмена данными.
Задачи ii-го узла
Задачи (i+1)-го узла
Интерфейсный модуль i-го узла Буфер
передачи сообщений
Буфер приема сообщений
Интерфейсный модуль
(i+1)-го узла Буфер
передачи сообщений
Буфер приема сообщений
Коммуникационная линия
Рис. 2
Порядок доставки сообщений через сеть иллюстрируется схемой, представленной на рис. 2. Отдельный узел сети содержит ряд прикладных задач, которые генерируют сообщения, адресуемые либо соседним задачам, либо задачам, содержащимся в других узлах. В последнем случае сгенерированное сообщение направляется в интерфейсный модуль и размещается в его буфере. В буфере интерфейсного модуля сообщения упорядочиваются по приоритетам. В момент, когда линия переходит в пассивное состояние, интерфейсный модуль приступает к передаче самого приоритетного из сообщений, находящихся в его буфере. Эта попытка окажется удачной, если одновременно интерфейсный модуль какого-либо другого узла не пытается передать более приоритетное сообщение.
Проверка гарантий своевременности доставки сообщений. Определим время доставки сообщения как длительность временного интервала, в течение которого сообщение
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
38 В. В. Никифоров, В. И. Шкиртиль
конкретного типа, порожденное прикладной задачей, гарантированно доставляется в узел се-
ти с задачей-адресатом. Как следует из вышерассмотренного порядка доставки сообщения
через сеть с CAN-интерфейсом, при заданной частоте передачи битов по коммуникационной
линии время доставки определяется не только длиной поля данных, но и продолжительно-
стью ожидания момента освобождения коммуникационной линии от передачи более приори-
тетных сообщений. Иными словами, сформированные задачами сообщения конкурируют за
возможность получения ресурса коммуникационной линии аналогично тому, как невытес-
няемые задания в каждом из узлов системы конкурируют за предоставление ресурса процес-
сора. Наличие такой аналогии позволяет распространить рассмотренный выше метод оценки
времени отклика невытесняемых задач на время доставки сообщений по сети с CAN-
интерфейсом.
Пусть mi — тип сообщений, передаваемых по сети; mi( j) — очередное сообщение этого
( ) ( )типа; tв mi( j) и tз mi( j) — моменты поступления mi( j) в интерфейсные модули соответст-
венно передающего и приемного узлов; продолжительность ri( j) доставки экземпляра mi( j)
( ) ( )сообщения типа mi определяется разностью tз mi( j) – tв mi( j) . Период Ti следования сооб-
щений mi равен минимально возможному интервалу между поступлениями однотипных со-
общений в интерфейсный модуль передающего узла. Приоритет сообщений типа mi опреде-
ляется кодом типа сообщения, размещаемым в поле арбитража. Величиной, аналогичной ве-
личине Ci объема процессорного времени для выполнения заданий τi( j) , является длитель-
ность временного интервала, в течение которого коммуникационная линия передает сообще-
ния типа mi :
Ci
=
(44
+ 8Ni v
)
,
где vi — скорость передачи данных по коммуникационной линии (число бит в секунду),
Ni — число байт в поле данных сообщений типа mi .
Тогда время доставки Ri сообщений типа mi формально определяется выражением (1),
а его значение — решением уравнения (2). Иными словами, уравнение (2), используемое для
оценки времени отклика в системе невытесняемых задач, может быть применено и для оцен-
ки времени доставки сообщений в сетях с CAN-интерфейсом.
Заключение. Использование предложенного метода вычисления максимального време-
ни доставки сообщений в локальных сетях с CAN-интерфейсом позволяет строить программ-
ные приложения для таких сетей с проверкой гарантий своевременной реализации приклад-
ных функций, исполнение которых разнесено по различным узлам системы. Таким образом
может быть достигнуто надежное, предсказуемое поведение программных приложений ре-
ального времени, распределенных по узлам локальной сети, а также эффективное использо-
вание аппаратных средств, обеспечивающих не только своевременную обработку актуальной
информации в узлах сети, но и своевременный обмен данными между компонентами, связан-
ными коммуникационными линиями с CAN интерфейсом.
СПИСОК ЛИТЕРАТУРЫ
1. Liu C. L., Layland J. W. Scheduling algorithms for multiprogramming in hard real-time environment // J. of the ACM. 1973. Vol. 20. P. 46—61.
2. Liu J. W. S. Real-Time Systems. NJ: Prentice Hall, 2000. 590 p.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7
Использование нелинейных последовательностей при построении двухдорожечных кодовых шкал 39
3. Данилов М. В. Методы планирования задач в системах реального времени // Программные продукты и системы. 2001. № 4. С. 28—35.
4. Никифоров В. В. Выполнимость приложений реального времени на многоядерных процессорах // Тр. СПИИРАН; Под общ. ред. Р. М. Юсупова. 2009. Вып. 8. С. 255—284.
5. Никифоров В. В. Разработка программных средств для встроенных систем. СПб: СПбГЭТУ, 2000. 74 с.
6. Введение в CAN 2.0B интерфейс. М.: ООО Микро-Чип, 2001: [Электронный ресурс]: .
Сведения об авторах Виктор Викентьевич Никифоров — д-р техн. наук, профессор; Санкт-Петербургский институт информа-
тики и автоматизации РАН, лаборатория технологий и систем программирования; E-mail: nik@iias.spb.su Вячеслав Иванович Шкиртиль — канд. техн. наук, доцент; Санкт-Петербургский институт информатики и автоматизации РАН, лаборатория технологий и систем программирования; E-mail: jvatlas@mail.rcom.ru
Рекомендована СПИИРАН
Поступила в редакцию 08.02.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 7