Операционные Системы Реального Времени

часов)

время (hard)
2.2 Реальное время с допусками (soft)
2.3 Комбинированное реальное время

(семафоры)
5.4 сообщения
5.5 события (флаги, сигналы)
5.6 таймеры и счетчики
6. Планирование и

сервиса ОС
10.3 задержанное выполнения сервисов ОС
10.4 отложенное выполнение сервисов ОС
10.5

(RMA)
12.2 Приоритетное планирование с учетом ближайших сроков (EDF)
13. Приоритетное планирование

Programming, ESP)
C. http://www.dedicated-systems.com (including Dedicated Systems Magazine)
D. “Deadline Monotonic Analysis”,

1. Real-Time Systems. Design Principles for Distributed Embedded Applications, by Hermann Kopetz, 1997, ISBN 0-7923-9894-7
2. A Practitioner’s Handbook for Real-Time Analysis, by Mark H. Klein, Thomas Ralya, Bill Pollak, Ray Obenza, 1993, ISBN 0-7923-9361-9
3. Real-Time Systems, The International Journal of Time-Critical Computing Systems, ISSN 0922-6443
4. Программирование для вычислительных систем реального времени, Дж. Мартин, «Наука», 1975, УДК 519.95
5. Проектирование операционных систем для малых ЭВМ, С.Кейслер, «Мир», 1986, УДК 681.142.2
6. Разработка програмных средств для встроенных систем, Никифоров В. В., Учеб. пособие. СПб.: Изд-во СПбГЭТУ "ЛЭТИ", 2000, УДК 681.325.5-181.4, ISBN 5-7629-0340-0

Библиография

системы, встраиваемые в оборудование (автомобили, бытовую технику, аудио и видео

Встроенные системы

Не использующие ОС

Использующие ОС

Приложение

Операционная Система

смеси
Температура двигателя
Угол поворота коленвала
Обороты двигателя
Зажигание в

Обогащение смеси

Открытие

Угол открытия

Подача выхлопа

Периферийные устройства (АЦП/ЦАП, цифровой ввод/вывод, и т.п.)

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

Таймер

времени - программная система, в которой корректность работы зависит не

Отклики (Responses)

Responses = F( Events,T )

Система должна завершить обработку события (выработать отклик) не позднее заранее определенного момента времени.

Система управляет обработкой большого количества разных событий.

Time, R)
Срок исполнения (Deadline, D)
Реальное время определяется соотношением срока исполнения

Время обработки (Computation Time, C)

Задержка (Jitter, J)

Обработка “в реальном времени” означает “вовремя”

срок исполнения (Hard Deadline, D)
событие
Время обработки (Computation Time, C)
Жесткое реальное

R)
Срок исполнения c допуском (Soft Deadline, D)
событие
Время обработки (Computation Time,

Реальное время с допусками (soft real time) допускает флуктуации времени отклика при условии, что среднее время отклика равно сроку исполнения (т.е. R в среднем равно D).

Система работает хуже (деградирует), но сохраняет работоспособность даже если срок исполнения иногда просрочен.

Примеры:
экранный редактор
сеть передачи данных
сервер базы данных

исполнения с допуском (Soft Deadline, Dsoft)
событие
Время обработки (Computation Time, C)
Комбинированное

Жесткий срок исполнения (Hard Deadline, Dhard)

возникновения
Периодические
(periodic)
Спорадические
(sporadic)
Апериодические
(aperiodic)
t
T
T
t


t
Внешние события - изменения состояния внешней среды
(environmental)
Внутренние события - изменения состояния внутри

Временные события
(timed)

Фиксированный период возникновения T

Миниальный интервал между возникновением ограничен некоторым значением 

Миниальный интервал между возникновением может быть любым

Системный таймер

Одновременное истечение тайм-аутов передачи нескольких сетевых сообщений

Коррекция курса самолета в случае предсказания коллизии (результат вычислений)

Нажатие клавиши на клавиатуре (аппаратная защита от слишком частого нажатия)

Периодическое поступление сетевого сообщения (напр. t° двигателя)

Сбой аппаратуры - генерация прерывания (Appolo-11)
Атака хакеров на Web-сервер

Программная защита от зацикливания - периодический опрос состояния задач

Ошибка программы - бит события задачи не сбрасывается (всегда установлен)

Программируеиый интервальный таймер

(great executive loop)
Система, построенная на обработчиках прерываний (interrupt-driven executive)
Временной

Приоритетный планировщик с вытесненяемым диспетчированием (prioritized preemptive scheduler)

1960

1980

2000

Для того, чтобы ОС могла использоваться как основа приложения реального времени, она должна удовлетворять требованиям:

исполнимость: предсказуемость работы приложения жесткого реального времени при любой (допустимой) нагрузке

одновременная обработка событий различного типа и времени возникновения, и сроками исполнения (в том числе c существенно различными периодами и сроками исполнения)

относительная простота модификации приложения при добавлении событий или изменении параметров событий (например, при уменьшении периода событий)

надежность (отсутствие сбоев и крахов)

минимально возможное потребление ресурсов - памяти и процессорного времени

циклический исполнитель
(cyclic executive).

Обработка событий привязана к временным промежуткам

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

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

(interrupt-driven executive).

Обработка событий выполняется вложенными обработчиками прерываний.
Преимущества:
- управляется событиями;
-

running

e1 */ Response( r1 );
}
void Task2( void )
{
/* processing e2 */ Response(

Событие e1
T1 = 5
D1 = 5
C1 = 2

Отклик r1

Отклик r2

Для каждого события создается обработчик - например, функция на языке С.

Эта функция называется задачей (task).

Задачи не связаны друг с другом.

Задачи активизируются событиями, поддерживая концепцию «система управляется событиями» (event-driven).

Событие e2
T2 = 2
D2 = 2
C2 = 1

Пример обработки события e1

Пример обработки события e2

Для обработки каждого события можно построить пример временной диаграммы.

Task1

D1

Task2

D2

Обработка событий независимо друг от друга

Пример приложения реального времени с двумя периодическими событиями

e1

e1

e2

Task1 : все сроки исполнения выдерживаюся
Task2
r2
e2
e1
Task1
r1
Task2 «случайно» начинается позже, чем

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

Примитивный Планировщик

нарушение срока исполнения или пропуск обработки события

все сроки исполнения выдерживаюся
Приоритетный вытесняющий планировщик для задач с

Task2

r2

e2

Приоритетный Вытесняющий Планировщик

e1

Task1

r1

Приоритеты должны назначаться правильно. Приоритет Task1 выше приоритета Task2: срок исполнения D2 нарушается, и даже может быть пропущена обработка события.

вытеснение

высокий

низкий

and situations)
Использовать приоритетный планировщик ?
Проверка исполнимости приложения (schedulability analysis)
Назначение приоритетов задач
Приложение
исполнимо ?
Да
Да
Нет
Преимущества:
- математически доказанные

Анализ характеристик событий.
Анализ сроков исполнения.
Проектирование обработчиков событий (задач).
Оценка времен обработки событий.

Оценка накладных расходов.
Прогноз модификаций приложения.
Анализ стоимости.

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

Нет

(Real-Time Kernel)
Операционная система реального времени - программа, распределяющая вычислительные ресурсы

Файловая система

Система ввода-вывода

назначения (ОСОН) (Windows NT, Unix)
Встроенные ОС реального времени
“Равные” условия для

“Привилегированные” условия для срочных задач

Реактивность

“Быстрый” усредненный отклик

Обеспечение ответа реального времени

Планирование

Разделение времени; нестрого-“приоритетное”; приоритет коротким задачам

Обычно приоритетное вытесняющее с большим количеством приоритетов

Объем занимаемой памяти

Несколько мегабайт кода, около мегабайта данных

Несколько килобайт кода, около сотни байт данных

Время исполнения сервисов

Сотни микросекунд

Единицы и десятки микросекунд

Предсказуемость

“Отсутствует” (при перегрузке)

Гарантируется всегда

Инверсия приоритетов задач

Возможна; в том числе неограниченная по времени (P/V семафоры)

Исключена (кроме ограниченной при доступе к разделяемым ресурсам)

приоритета t2): приложение всегда исполнимо
t1: T1=D1=4, C1=3; t2: T2=D2=8,

t2

t1

Short Job First (приоритет t1 ниже приоритета t2): не выдерживается срок исполнения D1

Приоритетное вытесняющее планирование в ОСРВ и планирование «приоритет коротким задачам» в ОСОН

Планирование «приоритет коротким задачам» не учитывает сроки исполнения задач, и поэтому не применяется в ОСРВ.

Немедленное вытеснение: приложение всегда исполнимо

Планирование с немедленным вытеснением в ОСРВ и планирование по таймеру в ОСОН

t2

t1

t1: T1=D1=4, C1=3; t2: T2=D2=16, C2=4;

Планирование по таймеру с периодом равным 3: не выдерживается срок исполнения D1

t2

t1

Планирование по таймеру приводит к инверсии приоритетов, и, как следствие, к нарушению сроков исполнения. Обычно не применяется в ОСРВ.

разделяемым ресурсам

Сообщения

События (флаги, сигналы)

Таймеры и счетчики

другими задачами.

Задачи являются основным средством обработки внутренних событий.

Задача имеет

5.1 Задачи

void TaskA_Entry( void )
{
/* processing */

Activate( TaskB );

Terminate();
}

void TaskB_Entry( void )
{
/* processing */

Terminate();
}

- единица обработки, инициированная аппаратным прерыванием асинхронно по отношению к

5.2 Обработчики прерываний

void interrupt Isr1( void )
{
ISREntry();

/* processing */

ISRActivate( TaskB );

ISRExit();
}

Int 08h

Int 09h

Addr. Of Isr1

Таблица векторов прерываний

прерываний) к критическим секциям кода, т.е. к разделяемым ресурсам.

Специальные

5.3 Ресурсы

Задача

Задача

Ресурс

I/O

Сообщения (messages) предназначены для обмена данными любого типа между задачами и обработчиками прерываний.

Сообщения обычно копируются в системную область.

5.4 Сообщения

Задача

Задача

Сообщение

Задача

Сообщение

задачами и обработчиками прерываний.

События также реализуются в виде флагов (masks,

5.5 События (флаги, сигналы)

Задача

Задача

Задача

Таймеры (timers) предназначены для задания временных интервалов для задач, а также подсчета абсолютного значения времени.

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

5.6 Таймеры и счетчики

Событие

Событие

Задача

Тайм-аут

Таймер

HW

Request
Wait Print Flag
End of Request
Init ScanCode Queue Init Character Queue Init Timer
Read

Print Flag

Enter

PrntScrn

Other

Put CR, LF into Character Queue

Activate Screen Task

Put Char into Character Queue

Activate Screen Task

Activate Print Task

Wait ScanCode or Timeout Flag

Алгоритм Driver Task

Пример драйвера терминала

состоит из двух шагов, выполняющихся друг за другом:
1. Собственно планирование

void TaskA_Entry(void)
{
Activate( TaskB );
}

Dispatcher

1

2

Scheduler

TaskA

TaskB

Запуск более приоритетной задачи

TaskA

TaskB

TaskA

TaskB

Уменьшение приоритета

running

running

running

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

системах реального времени должно удовлетворять следующим требованиям:

строгое соблюдение дисциплины

задач, упорядоченных
по убыванию приоритета
(+) простота реализации
(+) универсальность
(+) малый

TaskA

Prio = 0

TaskA

Prio = 5

TaskB

Prio = 5

TaskC

NULL

running

TaskB

TaskC

0


1


2


3

NULL

TaskB

NULL

TaskH

NULL

TaskA

TaskB

TaskA

TaskB

NULL

NULL

TaskD

TaskD

TaskF

TaskH

TaskD

TaskF

TaskH

«POSIX» планировщик поддерживает
списки задач для каждого приоритета
(+) быстрая постановка в очередь
(+) время постановки в очередь всегда одинаково
(-) большой расход ОЗУ
(-) требуется цикл сканирования очередей

Priority level

вытесняется
Prio=low
TaskA
context
Контекст задачи A

TaskA стек
1. Сохранение
регистров
2. Сохранение указателя стека
3.Восстановление указателя стека
4.

TaskB запускается

context

Prio=low

Переключение контекста задач при запуске высокоприоритетной задачи из низкоприоритетной задачи (вытеснение).

Prio=high

TaskB

context

Контекст задачи B

TaskB стек

context

void TaskB_Entry(void)
{

}

«Кажущийся» вызов задачи В из задачи А осуществляется с помощью:
1. сохранения значений регистров процессора на стеке выполняющейся задачи А,
2. запоминания указателя стека в описателе задачи А (для того, чтобы впоследствии продолжить выполнение задачи А),
3. загрузки указателя стека процессора из описателя задачи B,
4. восстановления значений регистров процессора со стека задачи B.

status
Compiler Reg 2
Accumulator A
Compiler Reg 1
Контекст задачи для
типичного 8-битного
процессора

Аппаратный
фрейм
прерывания

Scratch General Purpose Registers

Preserved General Purpose Registers

Scratch Floating Point Registers

Preserved Floating Point Registers

Special Registers

Контекст задачи для
типичного 32-битного
процессора (~64+ байта)

Preserved General Purpose Registers

Preserved Floating Point Registers

Return Address

Оптимизированный контекст задачи для
вызова задачи как
функции (~2+ байта). Применяется в случае использования «общего стека» для всех задач.

Контекст задачи обычно сохраняется на стеке задачи
Указатель на контекст (вершина стека) заносится в описатель задачи
Переключение контекста часто выполняется с помощью команд процессора, предназначенных для обработки прерываний («программное прерывание», «возврат из прерывания»)

or yield
Latency time
TaskB (high)
TaskA (low)
running
inactive
inactive
running
ready
activate
terminate
TaskB (high)
TaskA (low)
running
running
inactive
inactive
running
activate
ready
TaskA is pre-empted due to higher priority task

Основной тип планирования в системах жесткого реального времени

7.2 Вытесняющее (full pre-emptive) планирование

TaskC (high)
TaskD (low)
running
inactive
A
activate
7.4 Планирование с квантованием (time-sliced)
B
C
A
B
A
A
terminate
terminate
ready
Round-Robin tasks
terminate
TaskA, TaskB, TaskC (high)
TaskD (low)
running
inactive
A
activate
B
C
A
B
A
A
terminate
terminate
ready
Time-sliced tasks
quantums
yield
yield
yield
yield
Обычно

Похоже на round-robin, но вытеснение задач происходит принудительно по истечении кванта времени (таким образом, ОС влияет на время выполнения задач)

планирования:
1. Детерминированность (replica determinism).
2. Двойное и тройное исполнение задачи для

Но: построение оптимального off-line графика выполнения в общем случае относится к классу NP-complete задач, и, следовательно, практически неосуществимо.
Европейский проект реализации в различных областях: http://www.setta.org

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

List
Activate создает в ОЗУ управляющий блок задачи пользуясь описателем, находящимся

Dispatch To переводит выбранную задачу в состояние running (текущая), переключая контекст задачи (состояние процессора).

Terminate (itself) переводит текущую задачу в состояние неактивности, освобождая области ОЗУ.

Blocked

Ready

управления
задачами
Activate( TaskID ) - планирует задачу (inactive -> ready),

Сервисы для управления задачами

Stack / Context pointer

Context

Tactivation latency
Ttermination latency
Tcontext switch
Базовые временные
характеристики управления задачами
running
ready
ready

Time)
SetFlags(Flags)
Waiting означает, что задача ждет какого-то события (флага или момента

Blocked

Ready

для управления ждущими задачами
WaitFlags( Flags ) - сравнивает состояние установленных

Дополнительные сервисы для управления ждущими задачами

(TimeLink)

(Time-out)

Link

timer

= 5
C1 = 2
Внутреннее событие e2
T2 = 2
D2 = 2
C2

Приложение неисполнимо, так как обработчик прерывания аппаратно вытесняет задачу с процессора, хотя и обрабатывает событие с большим сроком исполнения.

Task2

r2

ISR1, C1 = 1

r1

highest

high

Внешнее событие e1
T1 = 5
D1 = 5
C = 2 = (C1=1) + (C3=1)

Внутреннее событие e2
T2 = 2
D2 = 2
C2 = 1

Task3, С3 = 1

low

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

activate

activate

priority levels Планируются программно
Interrupt Service Routines
Tasks
Схема приоритетов, не поддерживающая перекрытие приоритетов задач и обработчиков прерывания

Interrupts’
priority levels

Tasks’
priority levels

Interrupt Service Routines

Tasks

Схема приоритетов, поддерживающая перекрытие приоритетов задач и обработчиков прерывания (например, ERCOS)

Overlapping

Highest priority

Lowest priority

Назначение приоритетов в соответствии со сроками исполнения может приводить к перекрытию приоритетов задач и обработчиков прерываний.

и таймерных событий выполнялась в реальном времени, механизмы обслуживания прерываний

ISREntry();



ISRActivate( TaskB );



ISRExit();

“Return

TaskA прерывается

Prio=low

TaskA

context

Аппаратный
фрейм
прерывания (контекст задачи)

TaskA стек

Prio=high

TaskB

context

Аппаратный
фрейм
прерывания (контекст задачи)

TaskB стек

Сохранение
регистров

Сохранение указателя стека

Восстановление указателя стека

Восстановление
регистров

TaskB запускается

context

Prio=low

Переключение контекста задач при запуске высокоприоритетной задачи из обработчика прерывания.

switch latency
Tinterrupt entry latency
Tinterrupt switch latency
Базовые временные
характеристики обслуживания прерываний

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

сервиса ОС необходимо в ОС, где поддерживается схема приоритетов, которая

activation

interrupted

ready

выполнение сервиса ОС обычно означает, что планирование задачи выполняется во

Activation (dispatching)

ready

Activation (scheduling)

задержанного выполнения сервиса состоит из двух раздельных шагов:

1. Собственно планирование,

Dispatcher

1

2

Scheduler

TaskA

TaskB

Запуск более приоритетной задачи из обработчика прерывания

TaskA

TaskB

TaskA

TaskB

Уменьшение приоритета

running

running

running

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

void interrupt Isr1()
{

ISREntry();



ISRActivate( TaskB );



ISRExit();


}

выполнение сервиса ОС обычно означает, что вызов сервиса ОС откладывается

Activation (unstacking)

ready

Activation (stacking)

OS

executing

executing

interrupted

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

10.6 Атомарные операции в ОС

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

void Activate( TASK task )
{
DisableInterrupts();

Schedule( task );


Dispatch();

EnableInterrupts();

}

void Activate( TASK task )
{

DisableInterrupts();
Schedule( task );
EnableInterrupts();

DisableInterrupts();
Dispatch();
EnableInterrupts();

}


В то же время для улучшения реактивности ядра желательно уменьшить время исполнения атомарных операций - например, разделив их на две операции.

Critical Section */
RequestResource( ResX );
/* write

void TaskB_Entry(void)
{

/* Entry Critical Section */
RequestResource( ResX );
/* read shared variable */
if( X == 1 ) Y = 0;

/* Exit Critical Section */
ReleaseResource( ResX );
}

Доступ к критической секции управляется
семафором ресурса
ResX

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

to semaphore S1 denied
P(S1) semaphore S1 occupied
activation
inactive
waiting
Тупик при взаимном захвате

P(S2) semaphore S2 occupied

P(S2) access to semaphore S2 denied

waiting

Deadlock - both tasks are waiting forever

http://www.embedded.com/2000/0006/0006feat1.htm
Исправление дефектов на Марсе.

4 Июля 1997 года Mars Pathfinder приземлился

1 (med)
running
running
running
running
running
inactive
ready
inactive
ready
P(S1) access to semaphore S1 denied
P(S1) semaphore S1 occupied
activation
inactive
V(S1) semaphore S1 released
ready
waiting
activation
Затяжная

Unbounded priority inversion

Bounded inversion

семафоры могли использоваться во встроенных приложениях реального времени, механизм поддержки

Протокол маскирования прерываний (IMP)

Протокол наследования приоритетов (PIP)

Протокол потолка приоритетов (PCP)

Протокол высшего приоритета (HLP)

Механизм

Требование

Тупики

Затяжная инверсия приоритетов

Влияние на «другие» задачи

Потребление ресурсов

Предотвращает

Предотвращает

Значительное

Минимальное

Не предотвращает

Предотвращает

Незначительное

Незначительное

Предотвращает

Предотвращает

Умеренное

Значительное (сложный)

Предотвращает

Предотвращает

Умеренное

Незначительное

interrupts
Task 1
activate (event)
running
enable interrupts
Task 0
running
disable interrupts
activation
В некоторых операционных системах вместо

(+) нет затяжной инверсии приоритетов
(+) нет тупиков
(+) простота реализации
(+) минимальные накладные расходы
(-) ухудшается реакция на возникновение прерывания (увеличивается latency)
(-) критическая секция распространяется на все задачи!

latency

0 (high)
running
running
running
running
inactive
ready (blocked)
ready
release resource
request resource
Task 1
activation
request resource (denied)
ready
Is
equal to Task 0
(+) нет затяжной

Inheritance of Task 0 priority by Task 1

Release resource вызывает диспетчирование задач!

resource S1
Task 1
activation
request resource S1 (denied)
ready
Is
equal to Task 0
Inheritance of Task

request resource S2

request resource S2 denied

ready

Тупик при взаимном захвате двух семафоров (ресурсов) в случае протокола наследования приоритетов

Deadlock - both tasks are ready forever

1 (med)
inactive
inactive
running
running
running
running
running
running
running
running
inactive
ready (blocked)
inactive
ready
release resource
release resource
request resource
request resource
ready
Task 2
Task 1
activation
activation
Task 0 (high)
(+) нет затяжной

(-) требуется вычисление приоритетов до выполнения (т.е. off-line обработка).
(-) ограниченная инверсия приоритетов

При освобождении ресурса должна выполняться диспетчеризация задач!

resource low
request resource low
Task 2
activation
Ceiling priority (high)
running
release resource high
request resource high
Task

running

Task 1

release resource low

release resource low

При освобождении ресурса high задача Task2 ошибочно попадает в конец подсписка задач приоритета low

Эта ошибка приводит к повторному захвату ресурса low задачей Task1

Для корректной реализации протокола при захвате и освобождении вложенных ресурсов необходимо, чтобы при освобождении ресурса «высокого» приоритета задача помещалась в голову подсписка задач «низкого» приоритета - для того, чтобы она не вытеснялась задачей «низкого» приоритета, которая может захватить неосвобожденный ресурс низкого приоритета!

Ошибка реализации HLP при работе с вложенными ресурсами

HLP имеет много синонимов: Priority Protect Protocol (POSIX), Priority Ceiling Emulation Protocol, Immediate Priority Ceiling Protocol, OSEK Priority Ceiling Protocol.

Ho: Highest Locker Protocol - это не то же самое, что Priority Ceiling Protocol!

Обеспечить исполнимость (schedulability) приложения на протяжении всего времени выполнения (до

Методы

Для динамических приоритетов

Для фиксированных приоритетов

Rate Monotonic Scheduling (RMS) (задачам с более короткими периодами исполнения назначается более
высокий приоритет)

Deadline Monotonic Scheduling
(задачам с более короткими сроками исполнения назначается более
высокий приоритет)

Earliest Deadline
First (EDF) (задаче с более близким сроком исполнения назначается высший приоритет)

Least Laxity (задаче, которой нужно больше времени чтобы завершить работу до истечения срока исполнения, назначается высший приоритет)

(RMS) оптимален для независимых периодических задач имеющих срок исполнения равным

t1: T1=D1=3, C1=1; t2: T2=D2=2, C2=1; U = 1/3 + 1/2 = 0.83(3)

t1
high

t2
low

t2
high

t1
low

Не-RMS: приложение исполнимо

RMS: приложение исполнимо

t2
low

t1
high

RMS: приложение исполнимо

t1: T1=D1=5, C1=2; t2: T2=D2=2, C2=1; U = 2/5 + 1/2 = 0.9

t2
high

t1
low

Не-RMS: приложение неисполнимо!

RMS лучше, чем не-RMS!

нарушение срока исполнения

T2

... +


Cn ——
Tn

U() = 0,693 = ln(2)

(+) простая реализация
(назначение
фиксированных
приоритетов)
(-) плохое использование процессора
(-) ОС должна
поддерживать много
уровней приоритетов
(на практике достаточно 32 уровня)

Utilization Bound

t2
high

t1
low

t1: T1=D1=5, C1=2; t2: T2=D2=2, C2=1; U = 2/5 + 1/2 = 0.9

Для t1 доступно только 40%!

Для t1 доступно 60%

В среднем задаче t1 доступно 50%, но с учетом срока исполнения - только 40%

для независимых периодических задач имеющих срок исполнения равным периоду (т.е.

(+) полное использование процессора
(-) сложная реализация (динамическое назначение приоритетов)

t2
low

t1
high

t1: T1=D1=5, C1=2; t2: T2=D2=7, C2=4; U=2/5+4/7= 0.9714

RMS: приложение неисполнимо

t2

t1

EDF: приложение исполнимо!

перепланирование

нарушение срока исполнения

t2: приложение исполнимо! (показано только для двух периодов Т2)
RMS: приложение

Можно заметить, что пример для EDF также исполним при невытесняющем планировании.
Следовательно, можно добиться улучшения планируемости, группируя задачи во взаимо-невытесняемые группы. Такие группы образуются с помощью назначения задачам группы порогового приоритета времени выполнения.
Задача из группы планируется с исходным приоритетом, а выполняется с пороговым приоритетом, исключая вытеснение задачи другой задачей группы.
Этот метод называется Preemptive Threshold™, и впервые был использован в ОСРВ ThreadX.
В реализации метод подобен HLP с критической секцией на все тело задачи.

t0: T0=D0=2, C1=1; t1: T1=D1=10, C1=2; t2: T2=D2=14, C2=4; U=1/2+2/10+4/14= 0.9857

(+) более полное использование процессора, чем в RMS
(+) реализация проще, чем EDF
(-) необходимость вычисления порогового значения приоритета (NP-полная задача)

нарушение срока исполнения

пороговое невытеснение

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

Полная версия: http://www.tech2.volvo.se/reportage/9811electrical/main.htm
http://www.tech2.volvo.se/reportage/9811electrical/anim.htm

Transport
3. Network
2. Data Link
1. Physical
ISO/OSI Reference Model
Реальные встроенные сетевые системы

Применяются аппаратные решения - сетевые контроллеры.
(Например, CAN)

Применяется, если необходимо передавать «длинные» данные, или обеспечить постоянное соединение (OSEK/VDX COM). Часто отсутствует во встроенных сетях.

Применяется, если необходимо обеспечить удобный прикладной программный интерфейс, или переносимость кода на другие платформы (OSEK/VDX COM).

Встроенные системы обычно не поддерживают все уровни сетевой модели, так как требуется надежная быстрая передача «коротких» данных и минимальные накладные расходы.

CAN (1)
CAN - Controller Area Network - протокол, предназначенный для

t

Коллизия (столкновение)

Бракованный кадр (пакет)

Кадр (пакет)

Повторный кадр (пакет)

CSMA («ALOHA», ~1950), нет обнаружения коллизий; повтор обеспечивается транспортными протоколами

t

CSMA/CD (Ethernet, ~1980), есть обнаружение коллизий, нет разрешения коллизий; повтор через псевдо-случайный интервал времени

jam

jam

T

T

t

CSMA/CD+CR (CAN), есть обнаружение и разрешение коллизий

Отказ от передачи

CAN реализует метод доступа CSMA/CD+CR (Carrier Sense, Multiple Access/Collision Detection + Collision Resolution), т.е. CAN корректно разрешает конфликты множественного доступа.

CAN (2)
Узел #1
Узел #2
0
0
0
1
0
1
1
...
0
0
1
0
0
0
1
0
1
1
...
ID (идентификатор сообщения) определяет приоритет сообщения («0»

Каждый узел «слушает» шину в процессе передачи заголовка сообщения. Если узел передал «1», а принял «0», то узел отказывается от дальнейшей передачи, так как это означает, что другой узел в этот же момент времени передает более приоритетное сообщение. Так реализуется разрешение конфликтов.

«1»

+V

R

Все выходные ключи закрыты - на шине +V (“1”)

«0»

«1»

«0»

«1»

+V

R

Один выходной ключ открыт - на шине 0 (“0”) (Схема «Wired-AND» - «монтажное И»)

«1»

«1»

«1»

«1»

«1»

i

CAN (3)
Так как каждый узел должен прослушивать передачу сообщения от

Длина 40 m - Скорость 1 Mbit/s
Длина 400 m - Скорость 0.1 Mbit/s (100 Kbit/s)
Длина 1000 m - Скорость 0.04 Mbit/s (40 Kbit/s)

S
O
F

1

Identifier (Priority)

11 (29)

Control (Length)

6

Data

0 - 8 bytes

CRC

16

A C
K

2

E O F

7

Примерный формат кадра (frame) CAN.

(2/3)*Tbit > 2* ( Tline + Treceiver + Ttransceiver ),
где Tbit = 1 / (Скорость bit/s) Treceiver = Ttransceiver = 25E-9 s
Tline = (Длина m) / (2E+8 m/s)

Start Of Frame

End Of Frame

Acknowledgment

bits

отслеживания состояний всех узлов сети. Это необходимо для принятия решений

Узел #1

Узел #4

Узел #2

Узел #3

1 => 2

4 <= 3

2 => 3

4 => 1

Логическое кольцо (поддерживаются алгоритмы установки и восстановления кольца).

#4 #3 #2 #1

1/0 1/0 1/0 1/0

Состояние узлов (1-доступен, 0-не доступен) Копия хранится в каждом узле

Узел #1

Узел #4

Узел #2

Узел #3

1 <=> 2

4 <=> 1

Логическая звезда (один из узлов отслеживает состояние остальных узлов).

1 <=> 3

ресурсов,
сообщений
(текстовый файл на специальном языке)
Генератор объектов системы
Конфигурация приложения

Характеристики задач, ресурсов,
сообщений
[*.c *.h]
Код Операционной

Компилятор с языка C

Компоновщик

Перемещаемые объектные файлы
(машинный код)
[*.obj]

Библиотека модулей ОС
(При поставке без исходного кода)
[*.lib *.obj]

Исполняемый файл приложения вместе с ОС
[*.exe *.hex]

Упрощенная схема создания встроенного приложения с использованием ОС

реального времени (OSEK/VDX OS), коммуникационная подсистема (OSEK/VDX COM) и управление

Real-Time Linux
Модификации ОС общего назначения для применения в приложениях реального времени.

Существует несколько совершенно различных решений, в частности:

Архитектура со интегрированным ядром реального времени (dual-kernel architecture).
Архитектура с модифицированным планировщиком реального времени (single-kernel architecture).

The Real-time Linux Software Quick Reference Guide: http://www.linuxdevices.com/articles/AT8073314981.html

Schnittstellen für die Elektronik im Kraftfahrzeug” (Open systems and the

Приложение

Коммуникационная подсистема

Управление сетью

Операционная Система

Электронное управляющее устройство (ECU)

Приложение

Коммуникационная подсистема

Управление сетью

Операционная Система

Электронное управляющее устройство (ECU)

Шина передачи данных (например, CAN)

Планирование с фиксированными приоритетами
Вытесняемое, невытесняемое, и смешанное диспетчирование задач

2
1 task/prio,
no multiple activation requests
>1 task/prio,
multiple activation requests
for Basic Tasks
Basic Tasks only
Basic Tasks and Extended Tasks
Basic

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

highest priority

lowest priority

Interrupts’
priority levels

Tasks’
priority levels

Interrupt Service Routines

Tasks

Overlapping

Overlapping possible as a result of
Resource Allocation

Схема приоритетов поддерживает перекрытие приоритетов задач и обработчиков только во время исполнения задачи.
Задача всегда стартует с приоритетом ниже приоритета обработчиков прерывания.

TerminateTask();
}
ActivateTask
TASK( TaskB )
{
WaitEvent( Event1 );

TerminateTask();
}
SetEvent
Hardware Timer
IncrementCounter
Механизм алармов

одном узле, и также между задачами, находящимися в разных узлах.

Message

TaskA

TaskB

SendMessage

ReceiveMessage

OS

Msg

Msg

COM

Message’

TaskC

ReceiveMessage

OS

Msg

COM

Notification on arrival
TaskC

ActivateTask

Msg

task
“Conventional” Linux
(idle task of real-time kernel)
Linux process
Linux process
Linux process
I/O
I/O
Interrupt
Interrupt
Drivers
Non real
time
real
time
(+) поддерживается

(-) не поддерживается реальное время для процессов Linux

(+) поддерживается жесткое реальное время для RT задач (+) сроки исполнения в микросекундном диапазоне
(+) используется (почти) немодифицированное ядро Linux

Dual-kernel architecture (Embedix from Lineo, RTLinux from FSMLabs)

Linux kernel
Linux process
Linux process
Linux process
I/O
Interrupt
Drivers
(-) требуется модификация ядра
(-) системные

(+) поддерживается жесткое реальное время для Linux задач
(+) возможна интеграция планировщиков (+) сроки исполнения в диапазоне десятков микросекунд (+) используется механизмы защиты Linux

Single-kernel architecture (HardHat from MontaVista, KURT)

RT scheduler

RT API