Системы реального времени Real-time systems

1. Системы реального времени Real-time systems

Institute of Computer Systems
Системы реального времени
Real-time systems
Тема 2 – Управление локальными ресурсами в СРВ
§ 2.1 Управление процессами (диспетчеризация)
§ 2.2 Алгоритмы планирования задач
§ 2.3 Планирование периодических процессов. Особенности управления
процессами
§ 2.4 Синхронизация задач и межпроцессорное взаимодействие
§ 2.5 Управление памятью в ОС РВ
§ 2.6 Управление вводом/выводом ОС РВ
Вытесняющие и невытесняющие алгоритмы планирования. Средства синхронизации и взаимодействия процессов.
Критические секции. Блокирующие переменные, семафоры. Тупики. Нити.
Управление памятью в ОС РВ. Типы адресов. Методы распределения памяти без использования дискового пространства:
фиксированными разделами; динамическими разделами; перемещающимися разделами. Методы распределения памяти с
использованием дискового пространства: страничное распределение; сегментное распределение; странично - сегментное
распределение. Свопинг. Принцип кэширования данных.
Управление вводом выводом. Физическая организация устройств ввода-вывода. Организация программного обеспечения вводавывода. Обработка прерываний. Драйверы устройств. Независимый от устройств слой ОС. Пользовательский слой ПО.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

2. § 2.1 Управление процессами (диспетчеризация)

Institute of Computer Systems
§ 2.1 Управление процессами (диспетчеризация)
Общие принципы
управления
процессам.
Уровни планирования
Для
организации
управления процессами
необходимо учесть по
меньшей
мере
два
основных
аспекта:
определение уровня, на
котором выполняется
планирование процессов
и
выбор
алгоритма
планирования
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

3.

Institute of Computer Systems
Система может присваивать процессам приоритеты автоматически или
извне.
Приоритеты могут быть:
- заслуженными или купленными.
- статическими или динамическими.
назначаться по какому-то рациональному принципу или присваиваться в
ситуациях, когда системе просто необходимо каким-либо образом различать
процессы.
Статические приоритеты не изменяются, такой механизм установки
приоритетов достаточно прост и не сопряжен с большими издержками. Однако
следует учитывать, что такой механизм недостаточно гибок, т.к. не реагирует на
изменение окружающей ситуации.
Динамические приоритеты позволяют повысить реактивность системы, т.к.
реагируют на изменения ситуации, и начальное значение приоритета процесса
может быть изменено на новое, более подходящее значение.
Покупаемые приоритеты дают возможность пользователю повысить
приоритет задания и получить более высокий уровень обслуживания за
"дополнительную плату" (например, уменьшение кванта времени).
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

4.

Institute of Computer Systems
Важной частью любой ОС РВ является планировщик задач (диспетчер задач, супервизор).
Функции планировщика : определить, какая из задач должна выполняться в
системе в каждый конкретный момент времени.
Планировщик задач - это модуль (программа), отвечающий за разделение
времени имеющихся процессоров между выполняющимися задачами, отвечает за
коммутацию задач из состояния блокировки в состояние готовности, и за выбор
задачи (задач - по числу процессоров) из числа готовых для исполнения
процессором.
Ключевым вопросом планирования - выбор момента принятия решения:
1. когда создается новый процесс, необходимо решить, какой процесс запустить,
родительский или дочерний.
2. планирование необходимо, когда процесс завершает работу. Этот процесс уже не
существует, следовательно, необходимо из набора готовых процессов выбрать и
запустить следующий.
3. когда процесс блокируется по какой-либо причине, необходимо выбрать и
запустить другой процесс.
4. решение по диспетчеризации должно приниматься после разблокировки
процесса.
5. планировщик может принимать решение по истечении кванта времени,
отпущенному процессу.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

5.

Institute of Computer Systems
Алгоритмы планирования можно разделить на две категории.
- без переключений - неприоритетное планирование - выбирают процесс и
позволяют ему работать вплоть до блокировки либо вплоть до того момента,
когда процесс сам не отдаст процессор.
Процесс не будет прерван, даже если он работает часами. Соответственно, решения
планирования не принимаются по прерываниям от таймера. После обработки прерывания
таймера управление всегда возвращается приостановленному процессу.
- с переключениями - приоритетное планирование - выбирают процесс и
позволяют ему работать некоторое максимально возможное время. Если к концу
заданного интервала времени процесс все еще работает, он приостанавливается и
управление переходит к другому процессу.
Приоритетное планирование требует прерываний по таймеру, происходящих в конце
отведенного периода времени чтобы передать управление планировщику.
Приоритет - число, приписанное операционной системой (а именно,
планировщиком задач) каждому процессу и задаче.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

6.

Institute of Computer Systems
Схемы назначения приоритетов:
Фиксированные
приоритеты - приоритет
задаче назначается при ее
создании и не меняется в
течение ее жизни.
Применяется в большинстве систем
реального
времени.
В
схемах
планирования ОСРВ часто требуется,
чтобы приоритет каждой задачи был
уникальным, поэтому часто ОСРВ
имеют большое число приоритетов
(обычно 255 и более).
Турнирное
определение
приоритета - приоритет последней
исполнявшейся задачи понижается.
Определение приоритета по циклическому алгоритму (round robin) - приоритет
задачи определяется ее начальным приоритетом и временем ее обслуживания. Чем
больше задача обслуживается процессором, тем меньше ее приоритет. Эта схема в
том или ином виде применяется в большинстве UNIX систем.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

7.

Institute of Computer Systems
§ 2.2 Алгоритмы планирования задач
«Первым пришел – первым обслужен» (алгоритм FIFO). (без переключений).
Процессам предоставляется доступ к процессору в том порядке, в котором они
его запрашивают.
*После того, как процесс получает ЦП в свое распоряжение, он выполняется до завершения,
поэтому его не рекомендуют использовать в системах с разделением времени.
Т. О. процесс продолжает выполнение, пока не
наступит момент, когда он:
- добровольно уступает управление
(заканчивается, блокируется);
- вытесняется процессом с более высоким
приоритетом.
Не самостоятельный, комбинируется с
другими алгоритмами.
*например, диспетчеризация процессов
может выполняться согласно их
* при отсутствии второго условия возможен случай, когда приоритетам, однако процессы с
одинаковыми приоритетами планируются
высокоприоритетная задача будет ожидать окончания
по принципу FIFO.
работы низкоприоритетной.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

8.

Institute of Computer Systems
«Циклический алгоритм (round robin)»
Процесс A выполняется до
тех пор, пока он не
использовал
свой
квант
времени;
затем
выполняется
следующий
процесс,
находящийся в состоянии
готовности (процесс B)
Каждая «задача» явл.
подпрограммой (пп) и
выполняется
циклически.
Правила:
1. (пп) не должны
содержать циклов
ожидания.
2. (пп) должны
выполнять свою работу
как можно быстрее,
чтобы дать возможность
работать следующей (пп).
3. При необходимости
(пп) может сохранять
свое окружение и
текущие результаты,
чтобы в следующем
цикле возобновить
работу с того же места.
Т. О., процесс продолжает выполнение,
пока не наступит момент, когда он:
- добровольно уступает управление (т.е.
блокируется);
- вытесняется процессом с более высоким
приоритетом;
- использовал свой квант времени
(timeslice).
После того, как процесс использовал свой
квант времени, управление передается
следующему процессу, который
находится в состоянии готовности и
имеет такой же уровень приоритета.
*Планирование процессов
по принципу FIFO, но
каждый процесс получает
временной
квант,
в
течение которого он
может
использовать
ресурсы
ЦП.
Если
завершения процесса не
происходит по истечении
кванта времени, то этот
процесс переводится в
конец списка готовых к
выполнению процессов, а
ресурсы
ЦП
предоставляются
следующему процессу из
списка.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

9.

Institute of Computer Systems
«Циклический алгоритм (round robin)»
Преимущества:
1. Простота использования и прозрачность для понимания.
2. Если исключить из рассмотрения прерывания, система полностью
детерминирована. Задачи всегда вызываются в одной и той же последовательности,
что позволяет достаточно просто произвести анализ «наихудшего случая» и
вычислить максимальную задержку.
3. Минимальные размеры кода и данных. Кроме того, в отличие от алгоритмов с
вытеснением, для всех задач необходим только один стек.
4. Отсутствуют ошибки, обусловленные «гонками».
Недостатки:
- отсутствие приоритетности и очередей.
- задачи вызываются независимо от того, должны ли они в данный момент чтолибо делать или нет.
определении размера кванта времени! фиксированный или переменный!
если квант времени выбирается слишком большим, то система RR фактически вырождается в FIFO, т.к.
каждому процессу выделяется достаточно времени для завершения. Если же квант времени выбирается
слишком малым, то контекстные переключения начинают играть доминирующую роль, что в итоге
ухудшает характеристики системы.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

10.

Institute of Computer Systems
«Разделение времени»
Каждой задаче отводится определенное количество квантов времени
(обычно кратно 1 мс), в течение которых задача может монопольно занимать
процессорное время. После того как заданный интервал времени истекает,
управление передается следующей готовой к выполнению задаче, имеющей
наивысший приоритет. Та, в свою очередь, выполняется в течение отведенного
для нее промежутка времени, после чего все повторяется в стиле циклического
алгоритма.
*Представим, что в системе работают 7 задач, 3 из которых имеют высокий приоритет, а 4 – низкий.
Низкоприоритетные задачи могут никогда не получить управление, так как три высокоприоритетные
задачи будут делить все процессорное время между собой. Единственную возможность для
низкоприоритетных задач получить управление предоставляет ситуация, когда все высокоприоритетные
задачи находятся в блокированном состоянии. Для решения этой проблемы применяется прием,
получивший название равнодоступность (fairness). При этом реализуется принцип адаптивной
приоритетности, когда приоритет задачи, которая выполняется слишком долго, постепенно
уменьшается, позволяя менее приоритетным задачам получить свою долю процессорного времени.
Равнодоступность применяется главным образом в многопользовательских системах и редко
применяется в системах реального времени.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

11.

Institute of Computer Systems
«Кратчайшая задача – первая». (без переключений)
Временные отрезки работы известны заранее, первой выбирается не самая
первая, а самая короткая задача.
A
B
C
B
C
D
A
D
Требуется одновременное наличие задач
«Наименьшее оставшееся время выполнения» (с переключениями)
планировщик каждый раз выбирает процесс с наименьшим оставшимся
временем выполнения.
Необходимо знать заранее время выполнения каждого процесса.
Когда поступает новый процесс, его полное время выполнения сравнивается с
оставшимся временем выполнения текущего процесса. Если время выполнения
нового процесса меньше, текущий процесс приостанавливается и управление
передается новому процессу. Эта схема позволяет быстро обслуживать
короткие процессы.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

12.

Institute of Computer Systems
«Адаптивная диспетчеризация».
-- Если процесс использовал свой квант
времени (т.е. он не блокировался), то его
приоритет уменьшается на 1 (снижение
приоритета (priority decay).
Процесс A использовал свой
квант времени; его
приоритет снизился на 1.
Выполняется следующий
процесс в состоянии
готовности (процесс B)
"Пониженный" процесс не будет продолжать
"снижаться", даже если он использовал еще
один квант времени и не блокировался - он
снизится только на один уровень ниже
своего исходного приоритета.
-- Если процесс блокируется, то ему
возвращается первоначальное значение
приоритета.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

13.

Institute of Computer Systems
«Многоуровневые очереди с обратными связями».
-- Предпочтение коротким
заданиям с лимитируемым
вводом-выводом,
чтобы
обеспечить
хороший
коэффициент
использования устройств
ввода-вывода;
-- как можно быстрее
определять
характер
задания,
чтобы
соответствующим образом
планировать
его
выполнение.
Многоуровневые очереди с
обратными
связями
позволяют достичь этих
целей.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

14.

Institute of Computer Systems
«Кооперативная многозадачность» (алгоритм переключения задач)
/ОС Windows/ Задача, получившая управление, выполняется до тех пор, пока она
сама по своей инициативе не передаст управление другой задаче.
~циклического алгоритма; мало применяется в СРВ.
Приоритетная многозадачность с вытеснением
Высокоприоритетная задача, как только для нее появляется работа, немедленно
прерывает (вытесняет) низкоприоритетную. (чаще всего используется в ОС РВ)
*если какая-либо задача переходит в состояние готовности, она немедленно
получает управление, если текущая активная задача имеет более низкий
приоритет.
**Такое «вытеснение» происходит, например, когда высокоприоритетная задача
получила ожидаемое сообщение, освободился запрошенный ею ресурс, произошло
связанное с ней внешнее событие, исчерпался заданный интервал времени и т. п.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

15.

Institute of Computer Systems
Алгоритмы
планирования
должны
соответствовать
критериям
оптимальности функционирования системы.
Однако, если для систем «жесткого» реального времени такой критерий очевиден:
«ВСЕГДА и ВСЁ делать вовремя», то для систем «мягкого» реального времени это
может быть, например, минимальное «максимальное запаздывание» или
средневзвешенная своевременность завершения операций.
*В зависимости от критериев оптимальности могут применяться
алгоритмы планирования задач, отличные от рассмотренных.
В одной вычислительной системе могут одновременно сосуществовать задачи и
«жесткого», и «мягкого» реального времени, и что только одна из этих задач,
обладающая
наивысшим
приоритетом,
может
быть
по-настоящему
детерминированной.
*Разработчики стараются свести свою СРВ к наиболее простым конфигурациям,
характерным для систем «жесткого» реального времени, иногда даже в ущерб
эффективности использования вычислительных ресурсов.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

16.

Institute of Computer Systems
§ 2.3 Планирование периодических процессов.
Особенности управления процессами
Внешние события:
периодические (возникающие через регулярные промежутки времени)
непериодические (возникающие непредсказуемо).
В зависимости от времени, затрачиваемого на обработку каждого из событий,
может оказаться, что система не в состоянии своевременно обработать все
m
события.
Ci
Все потоки могут быть своевременно обработаны, если
1
Pi
i 1
Если в систему поступает m периодических событий, событие с номером i
поступает с периодом Pi и на его обработку уходит Ci секунд работы процессора
СРВ удовлетворяющая этому условию, называется планируемой.
Алгоритмы планирования:
• Статические (определяют приемлемый план выполнения заданий по их
априорным характеристикам)
• Динамические (модифицирует план во время исполнения заданий)
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

17.

Institute of Computer Systems
Время, мс
A
A1
B
A2
A3
B1
C
B2
C1
0
A4
B3
C2
10
Начальный
момент для A1,
B1, C1
20
30
40
A5
50
B4
C3
60
70
80
90
100
110
Крайний
Крайний
Крайний
срок для A1 срок для B1 срок для C1
E.L. Shaporina – Department of Computer Intelligent Systems and Networks
120
130
140

18.

Institute of Computer Systems
Время, мс
A
A1
B
A2
A3
B1
B2
C C1
B4
C2
C3
A1
B1
C1
A2
B2
C2
A3
EDF
A1
B1
C1
A2
B2
C2
A3
10
20
30
40
A5
B3
RMS
0
A4
50
60
B3
A4
B3
70
80
90
B3 C3
A4
100
C3
110
120
E.L. Shaporina – Department of Computer Intelligent Systems and Networks
A5
B4
A5
B4
130
140

19.

Institute of Computer Systems
Время, мс
A
A1
B
B1
A2
A3
B2
C C1
A1
B1
EDF
A1
B1
10
20
A2
C1
30
B4
C3
Неудача
B2
A2
40
A5
B3
C2
RMS
0
A4
B2
50
60
A3
70
C2
80
B3
90
A4
100
110
C3
120
E.L. Shaporina – Department of Computer Intelligent Systems and Networks
A5
130
B4
140

20.

Institute of Computer Systems
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

21.

Institute of Computer Systems
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

22.

Institute of Computer Systems
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

23. Тема 3 – Взаимоблокировки

Institute of Computer Systems
Тема 3 – Взаимоблокировки
§ 3.1 Взаимоблокировки
§ 3.2 Избежание взаимоблокировок
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

24. Тема 4 – ОС РВ QNX

Institute of Computer Systems
Тема 4 – ОС РВ QNX
Место ОС РВ QNX в ряду систем реального времени. Архитектура ядра ОС РВ QNX. Системные процессы и процессы
пользователя. Драйверы устройств.
Связь между процессами в ОС РВ QNX. Операционная система с передачей сообщений. ОС РВ QNX как сеть. Микроядро ОС
РВ QNX. Синхронное и асинхронное взаимодействие. Связь между процессами посредством сообщений, Proxy, сигналов.
Синхронизация процессов. Функции Send(), Receive(), Reply(). Связь между процессами в сети. Виртуальные процессы.
Планирование процессов.
Приоритеты процессов. Методы планирования: планирование по методу простой очереди; круговой метод
планирования; адаптивное планирование. Приоритет, управляемый клиентом. Задержка прерывания, Задержка
планирования. Вложенные прерывания.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

25. Тема 5 – Организация устройств ввода/вывода

Institute of Computer Systems
Тема 5 – Организация устройств ввода/вывода
Принципы построения и технические средства ввода-вывода дискретных сигналов.
Аналоговые, дискретные и цифровые сигналы. Виды дискретных и цифровых сигналов. Принципы построения и
основные схемы ввода/вывода однобитовых и многобитовых дискретных сигналов.
Принципы построения и технические средства ввода-вывода аналоговых сигналов.
Характеристики и особенности аналоговых сигналов. Дискретизация и квантование аналоговых сигналов.
Погрешности, возникающие при дискретизации и квантовании. Цифро-аналоговые преобразователи (ЦАП):
назначение, классификация, характеристики и принципы построения. Аналого-цифровые преобразователи (АЦП):
назначение, классификация, характеристики и принципы построения.
E.L. Shaporina – Department of Computer Intelligent Systems and Networks

26.

Institute of Computer Systems
7.1.2. Управление ресурсами в ОСРВ
7.1.2.1. Управление процессами
Контекст и дескриптор процесса.
Алгоритмы планирования процессов. Вытесняющие и невытесняющие алгоритмы планирования.
Алгоритмы планирования процессов. Абсолютные и относительные приоритеты.
Средства синхронизации и взаимодействия процессов. Критические секции.
Средства синхронизации и взаимодействия процессов. Тупики.
7.1.3. QNX
7.1.3.1. Архитектура
Архитектура и функции ядра.
Виды IPC. Связь между процессами посредством сообщений.
Виды IPC. Связь между процессами посредством сигналов.
Виды IPC. Связь между процессами посредством Proxy.
Особенности построения системы.
Микроядро. Связь между процессами.
7.1.3.2. Методы планирования
Методы планирования процессов.
Приоритет, управляемый клиентом.
7.1.4. Устройства ввода/вывода в СРВ
7.1.4.1 Классификация УВВ
Классификация и способы передачи электрических сигналов. Цифровые сигналы.
Устройства ввода/вывода в СРВ. Логические элементы ввода/вывода.
7.1.4.2. ЦАП и АЦП в устройствах ввода/вывода СРВ
Преобразование информации в устройствах ввода/вывода. ЦАП и АЦП. Назначение и основные показатели
E.L. преобразователей.
Shaporina – Department of Computer Intelligent Systems and Networks