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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Institute of Computer Systems
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
§ 3.1 Взаимоблокировки
§ 3.2 Избежание взаимоблокировок

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

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