ВУЗ: Пермский национальный исследовательский политехнический университет
Категория: Лекция
Дисциплина: Системы реального времени
Добавлен: 15.11.2018
Просмотров: 5821
Скачиваний: 11
16
t
Рис.7.
Чем реже вызывается задача, тем выше у нее приоритет.
EDF
(алгоритм с динамическим планированием задач)
Приоритет назначается согласно следующему принципу: чем
меньше срок выполнения, тем выше приоритет.
В каждый цикл задачи последовательности выстраиваются
заново в зависимости от критического
срока выполнения.
Реализованный алгоритм зависит от количества задач в
определенный момент времени.
LSTF
(алгоритм планирования)
Приоритет задачи назначается согласно следующему принципу:
чем меньше время связывания задачи, тем выше приоритет.
t
p
t
D
t
t
– физическая величина, время выполнения задачи, задается
пользователем.
Свойства задач:
Задача – объект, который имеет метод, выполняемый в системе
реального времени.
Задача – это единица измерения объектов системы исполнения
реального времени.
1.
Тип задачи (P, A, S, F, O).
P
периодические
17
A
апериодические
S
спорадические
F
фоновые
O
аппендиксы
2.
T
– период.
3.
t
– время выполнения.
4.
Критический крайний срок D исполнения.
5.
t
в – время начала функционирования задачи; определяет
такт времени, в который задача начинает функционировать каждый
цикл.
Приоритет зависит от алгоритма планирования и является
произвольным.
Время связывания зависит от периода, типа задачи, крайнего
критического срока исполнения.
Алгоритмы планирования спорадических и апериодических
задач
Существует
пять
основных
алгоритмов
планирования
спорадических задач:
1.
а) Планирование спорадической задачи, как фоновой
задачи.
Выделяется отдельная фоновая задача, которая отвечает за
выполнение всех спорадических запросов. Поэтому все спорадические
апериодические задачи исполняются тогда, когда не исполняются
периодические задачи.
18
t
M0
M1
M2
M3
П
1
П
3
П
2
Спорадическая задача
M4
Рис.8.
Создание отдельной задачи не является обязательным.
б) Спорадическая задача как фоновая (без создания
дополнительного процесса).
В а) – выделяют фиксированное время, а не любое свободное.
В б) – задача будет иметь приоритет общий с другими фоновыми
задачами и ставится в очередь фоновых задач.
2.
«Политика выбора».
Заключается
в
создании
периодического
процесса,
характеризующегося установленным приоритетом. Данный процесс
отвечает за обслуживание всех запросов от спорадических и
апериодических задач.
t
M0
M1
M2
M3
П
2
Спорадическая задача
П
1
П
1
П
2
Т2
Т3
Рис.9.
Данная задача должна запускаться в строго установленное время
запуска (T
з
).
Недостатки: несовместимость циклического характера алгоритма
и случайного характера спорадических задач.
19
Достоинства: позволяет четко спланировать время исполнения
всех задач (самый определяющий алгоритм).
3.
Обмен приоритетом.
Заключается в создании отдельного процесса обслуживания
спорадической задачи с динамическим приоритетом.
Динамическое назначение приоритета позволяет изменять его в
процессе функционирования системы.
В данном алгоритме для процесса, исполняющего спорадические
задачи, устанавливается самый высокий приоритет (динамический).
Система обменивает приоритеты между самым высокоприоритетным
периодическим
процессом
и
процессом,
обслуживающим
спорадические задачи. Обмен производится в начале цикла
функционирования системы.
З4
З1
З2
З3
Зс3
Q1
Q2
Q3
Q4
ЗС3
з1
з2
з3
з4
з1 (р:1)
з4 (р:4)
з3 (р:3)
з2 (р:2)
Зсз
Q1
U
M1
Рис.10.
Зсз – задача спорадических задач
з1…з4 – задачи
р – приоритет
М1 – метка (Q1)
1
1
Q
(1 цикл)
2
1
Q
(2 цикл)
20
Если в систему поступает периодическая задача с более высоким
приоритетом во время между
1
1
Q
и
2
1
Q
, то обмен приоритетом не
производится, и данная задача может быть выполнена раньше, чем
задача, обрабатывающая спорадические запросы.
4.
Деферабельный сервер.
Основан на создании процесса обработки спорадических задач с
четко
установленным
заданным
приоритетом.
Приоритет
устанавливается на самом высоком уровне до запуска системы. Перед
повторным запуском данный приоритет может изменить приоритет на
самый высокий в текущей системе (см. рис.10.).
Зсз (p:max(p)+1)
В данном алгоритме процесс сохраняет ресурс, выделенный для
обслуживания спорадических задач, и приостанавливает выполнение
спорадических задач в случае, если этот ресурс исчерпан.
t
сз
с31
с32
с33
Рис.11.
t
сз =
0
3
2
1
t
t
t
t
сз
cз
сз
Пока t
0
>0 производится запуск спорадической задачи, иначе
спорадическая задача не запускается. В процессе функционирования
системы данная задача может прерывать периодические задачи
несколько раз в зависимости от получения спорадических запросов.
5.
Спорадический сервер.
Алгоритм заключается в создании периодического процесса
исполнения спорадических задач, но приоритет этого процесса
устанавливается на уровне приоритета спорадической задачи. При