Основная задача системы реального масштаба времени (RT) - получение правильных результатов за определенный крайний срок. Следовательно, вычислительная правильность системы зависит от двух составляющих: логической правильности результатов, и правильности выбора времени, то есть способности выполнения вычислений за крайние сроки. О жестких системах реального масштабе времени (HRT) можно думать как о специфическом подклассе RT систем, в котором неспособность удовлетворять вышеупомянутым крайним срокам может окончиться катастрофическим отказом системы. В дальнейшем мы будем использовать фразу "мягкая система реального масштаба времени (SRTT)" для определения тех RT систем, в которых способность встречать крайние сроки действительно требуется; однако, отказ выполнения не приводит к отказу системы. Для проектов HRT и SRT систем могут встретиться такие сложности, как выбор времени применения и требования к ресурсам, и пригодность ресурсов системы. В частности в проекте HRT системы, которая поддерживает критические процессы ( например система управления полетами, система управления атомной электростанции, железнодорожные системы управления ), эта сложность может быть усилена такими противоречивыми прикладными требованиями, как требованием на высоко надежные и высоко доступные услуги, и потребностью обеспечить эти услуги при удовлетворении строгих ограничений выбора времени. В частности, поскольку HRT система должна обеспечить услуги, которые, должны быть и своевременными и высоко доступными, проект любой такой системы требует, чтобы соответствующие методы разрешения ошибок, способные к встрече с жесткими требованиями в реальном масштабе времени, были развернуты в пределах этой системы. Текущая технология позволяет проектировщику системы HRT осуществлять рентабельные методы разрешения ошибок, основанные на использовании избыточных компонентов системы. Однако, развитию политики управления избыточности, которая выполняет требования в реальном масштабе времени, может препятствовать дальнейшее усложнение проекта системы. Таким образом, в сущности, проект HRT системы нуждается в тщательной оценке требований выполнения / надежности. И HRT и SRT системы могут быть построены из географически рассеянных ресурсов, связанных некоторой сетью, чтобы формировать распределенную RT систему.(распределенные HRT системы могут классифицироваться как отзывчивые системы, то есть распределеные, ошибко-устойчивые,в реальном масштабе времени ) В этом руководстве, мы сосредоточимся на проблемах выполнения распределенных RT систем, и опишем пять эксплуатационных примеров этих систем.В частности мы обсудим ключевые парадигмы для разработки своевременных и доступ ных RT услуг системы, и исследуем методы планирования процесса, управления временем, и взаимодействия по локальным и глобальным сетям. Это руководство структурировано следующим образом. В последующей секции, мы обсуждаем основные проблемы, возникающие при проектировании RT систем. В секции 3, мы исследуем возможные политики планирования, которые обычно развертывается в этих системах. Секция 4 рассказывает о распределенных RTOS, упомянутых выше. Наконец, Секция 5 предлагает некоторые замечания и выводы.
Любая система реального масштаба времени может быть описана как состоящая из трех основных подсистем.
Управляемая подсистема (например индустриальный завод, управляемое компьютером транспортное средство), диктует требования в реальном масштабе времени; подсистема контроля управляет некоторыми вычислениями и связью с оборудованием для использования от управляемой подсистемы; подсистема оператора контролирует полную деятельность системы. Интерфейс между управляемыми и подсистемами контроля состоит из таких устройств как датчики и приводы. Интерфейс между управляющей подсистемой, и оператором связывает человека с машинной.
Управляемая подсистема представлена задачами (в дальнейшем называемыми прикладными задачами) которые используют оборудование, управляемое подсистемой контроля. Эта последняя подсистема может быть построена из очень большого количества процессоров, управляющими такими местными ресурсами, как память и устройства хранения, и доступ к локальной сети в реальном масштабе времени (то есть локальная сеть, которая обеспечивает ограничение на максимальную задержку обмена сообщениями - смотри подраздел 2.4). Эти процессоры и ресурсы управляются системой программного обеспечения, так мы называем операционную систему реального масштаба времени (RTOS).
Развертывание RTOS в критической окружающей среде (например, руководство и навигационные системы) налагает серьезные требования надежности на проект и функционирование этих RTOS . Эти требования могут быть определены из соображений максимальной приемлемой вероятности отказа системы. Таким образом, например, системы управления полетом, типа используемого в Аэробусе A-320, требуют вероятности отказа в полете 10^(-10) за час. В системах управления транспортными средствами, в которых стоимость отказа может быть определенный количество в терминах экономического штрафа (например системы для спутникового руководства, беспилотные подводные навигационные системы), требуют вероятности отказа порядка 10^(-6) - 10^(-7) в час.
Методы разрешения ошибок, основанные на управлении избыточными аппаратными средствами ЭВМ и компонентов системы программного обеспечения, обычно используются, чтобы выполнить эти требования надежности. Однако, выполнение этих методов, действительно оп ределяющих надежность системы, требуют, чтобы частью ресурсов системы были отданы для обеспечения надежности.
Основные проблемы проектирования RTOS представлены ниже, по отдельности. В частности в дальнейшем мы обсудим :
(I) необходимые качества RT приложений, которые могут использоваться в RTOS,
(II) две общих парадигмы, которые могут быть применены к проекту RTOS, управление
(III) временем, и
(IV) межпроцессные связи в распределенных RT системах.
RT приложение может быть оформлено как набор сотрудничающих задач. Эти задачи могут классифицироваться, согласно их требованиям выбора времени, как задачи жесткие в режиме реального времени (HRT), мягкие в режиме реального времени (SRT), и не в режиме реального времени (NRT). HRT задача - задача, чье своевременное (и логически правильное) выполнение считают критическим для действия полной системы. Предельный срок, HRT задачи традиционно называют жестким крайним сроком, вследствие критического характер а этой задачи. Неспособность системы удовлетворить жесткому крайнему сроку может окончиться крахом системы. SRT задача, так же, характеризуется крайним сроком, удовлетворение которому действительно желательна, хотя не критично, для функционирования систе мы (таким образом, крайний срок SRТ задачи - обычно называемый мягким крайним сроком). NRT задачи - те задачи, которые не показывают никакие требования в реальном масштабе времени (например задачи обслуживания системы, которые могут иногда выполняться в "фоне"). Прикладные задачи могут далее классифицироваться как периодические, апериодические (или асинхронные ), и спорадические задачи. Периодические задачи - те задачи, которые входят в состояние выполнения периодически. Эти задачи, обычно используются в таких задачах как обработка сигнала и контроль , типично характеризуются жестким крайним сроком. Апериодические задачи - те задачи, чье выполнение, не может ожидаться, так как их выполнение, определено возникновением некоторых внутренних или внешних факторов (например задача, отвечающая на запрос от оператора). Эти задачи обычно характеризуются мягким крайним сроком. Наконец, апериодические задачи, характеризованные к жестким крайним срокам названы спорадическими задачами (например задачи в критическом положении запрашивающие некоторые действия от оператора). RTOS должна гарантировать, что каждое индивидуальное выполнение каждой прикладной задачи выполняет требования выбора времени этой задачи. Однако, для выполнения этого условия нельзя поступиться временем среднего отклика каждой прикладной задачи. Фундаментальное свойство RTOS - системы предсказуемость, то есть функциональное и рассчитывающее поведение RTOS должно быть так детерминированный по мере необходимости, чтобы выполнить эту RTOS спецификация. Таким образом, бы стрые аппаратные средства ЭВМ и эффективные алгоритмы действительно полезны, чтобы строить RTOS, которые выполняют требования в реальном масштабе времени; однако, они не достаточны для гарантирования предсказуемого поведения, требуемого от системы.
Две общих парадигмы для проекта предсказуемого RTOS могут быть найдены в литературе. Эти парадигмы вели к развитию двух различных RTOS архитектур, их назвали вызванной случаем (ET) и вызванной временем (TT) архитектурами . В сущности, и в RTOS , любая деятельность системы начинается в ответ на возникновение специфического случая, вызвана окружающей средой системы. Вместо этого, в TT RTOS , действия системы начинаются в определенный момент глобально синхронизированного времени (см., следующий Подраздел). В обеих архитектурах RTOS предсказуемость достигнута, использованием стратегии оценки, до выполнения каждой прикладной задачи, потребности ресурса этой задачи, и готовности ресурса удовлетворить эти потребности. Однако эти потребности ресурса и готов ность могут измениться в архитектуру (ET) во время выполнения, и, должны быть оценены динамически. Таким образом, оценка потребности ресурса в архитектуру ET обычно основана на параметрических моделях . Вместо этого, в TT архитектуре эти потребности могут быть вычислены автономно, основывая их на предстартовом анализе времени определенного применения, которое требует использования TT архитектуры; если эти задачи не могут о жидать расчета оценки, то исходят из самого плохого случая. Защитники TT архитектуры критикуют (ET) архитектурный подход, так как эта модель в следствии ее природы, может быть характеризован чрезмерным числом возможных вариантов поведения, каждый из которых должен быть тщательно проанализирован, чтобы предсказ ать потребность в ресурсах . Напротив, защитники ET архитектуры утверждают, что эта архитектура гибче чем TT архитектура, и идеал для большого класса применений, которые не позволяют предопределять требования ресурса. В частности они утверждают, что TT архитектура, в случае самой грубой оценки, упомянутой выше, склонна, тратить впустую ресурсы, чтобы обеспечивает предсказуемое поведения. В обоих ET и TT архитектурах проверка потребности ресурса и оценка готовности должны быть выполнены при принятии во внимание требований выбора времени. Следовательно, проблемы управления временем, которые характеризуют временное поведение системы, име ют критическую важность в проекте любой RT системы.
Одна из основных проблем, в области управления времени в RT системах, состоит в обеспечении адекватных механизмов для измерения (I) временных моментов, в которые должны произойти специфические события, и (II) продолжительности интервалов времени между событиями.
В распределенной RT системе, эти проблемы станут особенно критическими, поскольку возникновение того же самого случая может наблюдаться от такого неотъемлемо асинхронные устройства как множество различных процессоров. Однако, справиться с этой пробле мой можно обеспечивая RT процессы ссылкой на время указанной точности. Ссылка может быть построена, синхронизируя точность местных часов в реальном масштабе времени, включен в каждом процессоре системы, чтобы получить глобальное время в пределах системы.
Большое разнообразие алгоритмов синхронизации часов , основанных на обмене сообщениями синхронизации часов среди узлов системы. Мы не будем описывать эти алгоритмы здесь, поскольку они - обс уждаются подробно в уже цитируемых ссылках. Однако, мы желаем упомянуть, что, как указано в , любой такой алгоритм должен отвечать следующим четырем требованиям:
1. Алгоритм синхронизации часов должен быть способен к ограничению максимальным различием значений времени между наблюдением того же самого случая от любых двух различных узлов системы (измеренных согласно значению местных часов каждого из этих двух узлов);
2. Понятие глобального времени, построенного алгоритма синхронизации должно быть достаточно точным что бы позволить тому измерять маленькие интервалы ;
3. Алгоритм синхронизации часов должен быть способен обрабатывать возможные ошибки местных RT часов, или потерю сообщения синхронизации часов;
4. Работа системы не должно замедляться выполнением алгоритма синхронизации часов.
Для выполнения этих требований есть два подхода. Централизованный подход может быть осуществлен посредством центральной единицы синхронизации, например "сервера времени" узл а, ответственного за распределение сообщений синхронизации времени другим узлам в системе; такой подход очень уязвим к отказам единицы синхронизации непосредственно. Децентрализованный подход, вследствие избыточности в распределенной инфраструктуре, кото рая может использоваться для выполнения, может предлагать лучшие гарантии относительно защиты от ошибок.
Как уже упомянуто, алгоритмы синхронизации часов в распределенных RT системах могут быть осуществлены обменами сообщения. Однако такие алгоритмы могут затрагивать производительность системы, таким образом нарушая требование 4 выше. Для этой проблемы, практическое и эффективное решение было предложено и развито в пределах контекста проекта МАРСА.
Ввиду требования предсказуемости, упомянутого ранее, распределенные RT системы требуют прежде всего, чтобы поддержка связи, которую они используют, обеспечила их детерминированным поведением инфраструктуры связи. Это поведение может быть достигнута Архитектурой протокола связи, характеризованным такими детерминированными свойствами как ограниченная задержка доступа канала, и ограниченная задержка сообщения. Задержка доступа канала определена как интервал времени между моментом, в котором задача делает запрос о посылке сообщения, и моментом, в котором локальному узлу где эта задача выполняется, фактически передается, что сообщение на канале связи. Задержка сообщения определена как интервал времени между моментом, в котором задача запрашивает передачу сообщения, и моментом, в котором то сообщение успешно доставлено; следовательно, сообщение задерживает включает задержку доступа канала. Если сооб щение доставлено с задержкой, которая превышает текущее время, то сообщение рассматривается как потерянное. Как указано в в распределенных RT задачах, основанных на передаче не интерактивной звуковой и видео информации требуются, условия ограниченной задержки сообщения, Jitter; этот jitter - абсолютная значение разницы между фактической задержкой сообщ ения переданного сообщения, и целевой задержки сообщения. Проблемы задержки jitter контроля протоколы характеризуемые ограниченной задержкой jitter свойства, для использования для коммуникаций по тем сетям, описаны в . Дальнейшие общие свойства, которые могут требоваться от RT протокола, включают стабильность, и корректную обработку ошибок. Первое свойство относится к способности протокола, продолжать эффективную работу в не смотря на временные перегрузки сети. Втор ое свойство относится к способности протокола пережить отказы канала связи Обзор основных методов для построения проекта протоколов для распределенных RT систем обсужден в . В этом руководстве, авторы исследуют время ограничивающее протоколы, которые могут быть развернуты в распределенных RT системах, основанных на ради опередаче. В частности они классифицируют эти протоколы. Первый класс включает разделяющие время п ротоколы многократного доступа; последний, включает символические схемы. Кроме того, в этой работе отражены многие вопросы исполнительности и надежности, возникшие при разработке этих протоколов. Рассмотрены соотношения между вероятностью потери сообщений, скоростью передачи сообщений и временными ограничениями на передачу сообщений. Дальнейшие работы над проблемой коммуникации в режиме реального времени, включая коммуникацию в режиме жесткого реального времени.Описывается коммуникационный протокол для работы в режиме жесткого реального времени для локальных сетей, поддерживающий задержку доступа к каналу. В авторы обсуждают четыре протокола для коммуникаций в режиме жесткого реального времени, называемые протоколами Virtual Time CSMA. Для них приводятся зависимости процента не доставленных в срок сообщений от степени загруженности канала. Наконец, интересный коммуникационный протокол для управляющих систем жесткого реального времени недавно. Этот протокол, разработанный для поддержки управляемых архитектур реального времени поддерживает: предсказуемую задержку сообщений, групповые коммуникации и членство , менеджмент перезагруженной сети и точную синхронизацию часов. Привлекательная особенность этого протокола заключается в том, что у него есть широкие возможности к масштабированию, то есть он может эффективно работать на различной коммуникационной аппаратуре (например, на сдвоенной паре так же хорошо, как и на оптоволокне).
В системах реального времени на алгоритм планировки возлагается задача определения последовательности выполнения заданий в соответствии с их требованиями к ресурсам и ко времени исполнения. При проектировании системы реального времени выбор приемлемого алгоритма планирования может зависеть от нескольких факторов: количества процессоров в системе, их гомогенности или гетерогенности, отношения предшествования между заданиями, метода синхронизации заданий. Кроме того, программно-зависимые характеристики заданий могут определять выбор алгоритма планирования. Например, задания могут быть прерываемыми и не прерываемыми. Выполнение прерываемого задания может быть прервано другим и продолжено позднее; непрерываемые задания выполняются до завершения и не могут быть прерваны. Приложению предлагаются обе возможности. (В этой работе мы не будем рассматривать непрерываемое планирование. Алгоритмы планирования заданий могут быть разделены на статические и динамические. Статические алгоритмы определяют приемлемый план выполнения заданий по их априорным характеристикам, динамический алгоритм модифицирует план во время исполнения заданий. Издержки на статическое планирование низки, но оно крайне нечувствительно и требует полной предсказуемости той системы реального времени, на которой оно установлено. Динамическое планирование связано с большими издержками, но способно адаптироваться к меняющемуся окружению. Литература по алгоритмам планирования заданий очень обширна в этой работе мы не можем дать описание всех алгоритмов. Вместо этого мы ограничимся описанием наиболее употребительных алгоритмов, применяемых в системах реального времени, и представим результаты проведенного нами недавно исследования этих алгоритмов.
Планирование периодических задач на одном процессоре - классическая проблема планирования в системах РВ [34].Имеются два альтернативных подхода решения этой проблемы, основанные на фиксированном или динамическом назначении приоритета каждой задачи. В первом приоритет каждой задачи вычислен однажды и остается неизменным в течение жизни задачи. В динамическом подходе (также называемом управление крайними сроками), приоритет вычисляется динамически, и может быть изменен во время выполнения. Эти подходы вели к развитию разнообразия вытесняющих политик планирования (Вытесняющая политика подразумевает возможность прерывания обработки задачи, если поступил запрос задачи с более высоким приоритетом). Они включают "Монотонизирующую нормуЭ (RM), "самый ранний крайний срок сначала" (EDF), и "наименеьшее время cначала" (LSTF) - политики, разобранные ниже. RM политика назначает приоритет каждой задачи согласно следующему принципу: чем короче период задачи , тем выше приоритет задачи. Эта политика оптимальна среди политик фиксированного приоритета (то есть эта политика всегда получит подходящий график выполнения задач, если это возможно в принципе). EDF и LSTF политика работают с динамическими приоритетами. В политике EDF, чем меньше крайний срок задачи, тем выше приоритет назначается на эту задачу. Вместо этого, с LSTF политикой(полисом), чем меньший слабое время (см. ниже) задачи, тем выше приоритет, назначается на эту задачу. Cлабое время задачи определено как разница между оставшимся временем до крайнего срока задачи, и количеством времени, которое требует задача. Для планирования апериодических задач были предложены следующие, пять различных политик. Первая политика состоит в планирования апериодической задачи как задачи фона, то есть апериодическим задачам позволяют делать их вычисления только тогда, когда никакие периодические задачи не активны. Вторая политика, названная Выбором, заключается в создании периодического процесса, характеризованного установленным приоритетом, который обслуживает апериодические запросы задач. Главная проблема этой политики - несовместимость между циклическим характером политики, и случайным характером апериодических задач. Третья и четвертая политика - Обмен Приоритета (PE) и Деферабельный Сервер (DS). Обе политики направлены на повышение эффективности выполнения апериодических задач используя высокий приоритет периодического сервера, который выполняет запросы апериодических задач. И в PE и DS политике, сервер сохраняет отведенное время выполнения, если никакие апериодические запросы не поступают. (Эта политика также названа сохранением ресурса, поскольку они обеспечивают механизм для сохранения ресурса выделенным для апериодических услуг, если, когда этот ресурс становится доступным, это не необходимо.) Различие между этими двумя политикой заключается в способе управления высоким приоритетом их периодического сервера. В DS политике, сервер поддерживает приоритет на продолжительности полного периода; таким образом, апериодические задачи могут обслуживаться в высоком приоритете сервера, при условии, что время выполнения сервера в течение текущегм периоде не было истощено. Напротив, в PE политике, сервер обменивает приоритет с самым высоким приоритетом периодической задачи, если никакие апериодические запросы не происходят в начале периода сервера. DS и PE политика были развиты, чтобы работать со спорадическими задачами (то есть апериодическими HRT задачами, описаными в разделе 2.1). Пятая политика, которую мы рассматриваем, то есть политика Спорадического Сервера (SS), была разработана для того, чтобы осуществлять с планирование апериодических (SRT) задач. Эта политика, хотя и основана на создании периодического сервера апериодических запросов, характеризуется производительностью по времени отклика, сопоставимой с политикой DS и PE, и более низкой сложностью выполнения. Планирование задач в сильно связанных распределенных системах, типа мультипроцессоров с распределенной памятью, может управляться отдельным планировщиком, ответственным за распределение обработчиков между прикладными задачами. Мак-Нафтон , предложил оптимальный алгоритм приоритетного планирования для независимых задач. Этот алгоритм был расширен, чтобы работать с такими различными проблемами как задачи, имеющие графы предшествования DAG, и периодическое выполнение . В слабо связанных распределенных RT-системах, вследствие высокой стоимости перемещения процесса между процессорами, и потери предсказуемости, которую это может повлечь за собой, задачи могут быть статически назначены на процессоры системы. В этих системах планировщик обычно разбивается на две отдельные компоненты, а именно, диспетчер процессоров, и местный планировщик. Диспетчер ответственен за назначение задач на распределенные процессоры системы, местный планировщик (один для каждого процессора) осуществляет планировочную политику данного процессора, аналогично представленным ранее, для распределения местных запросов на выполнение. Следует отметить, что алгоритмы распределения обычно основаны на некотором эвристическом подходе, поскольку проблема распределения задач на процессоры может быть очень сложна. (Например, нахождение оптимального назначения задач, характеризуемая произвольным графом соединений, для четырех или большего количества процессоров с различными скоростями - проблема NP-сложности.) Подсистема ввода - вывода системы реального времени может требовать собственного планировщика. Самый простой путь доступа к ресурсу ввода - вывода - использование не-приоритетной политики FIFO. Однако, приоритетные методы планирования, представленные выше для распределения процессоров (то есть RM, EDF, LSTF) могут быть применены для планирования запросов ввода - вывода. Хорошие оценки качества, которые могут использоваться для характеристики эффективности планирования, включают загрузку на отказ (Breakdown utilisation,BU), нормализованное среднее время ответа (Normalised Mean Response Time, NMRT), и Гарантируемая часть (Guaranteed Ratio, GR), представленные ниже. BU, является степенью использования ресурсов при которой или ниже которой RT OS может гарантировать, что все задачи будут выполнены в заданные сроки. Это число обеспечивает оценку эффективности политики планирования, как чем больше BU, тем больше время cpu, посвященное выполнению задач. NMRT - отношение между интервалом времени, от готовности задачи к выполнению до ее окончания,к фактическому времени процессора, использованному для выполнения задачи. Это число также обеспечивает оценку эффективности избранной политики планирования, так как чем больше NMRT, тем больше время простоя задачи. Наконец, для динамических алгоритмов, хорошей оценкой производительности является GR, то есть число задач, выполнение которых можно гарантировать, отнесенное к общему количеству задач ожидающих выполнения.
Чтобы оценивать эффективность вышеупомянутых алгоритмов, мы развили модель распределенной системы РВ, которая включает большинство описанных алгоритмов, подходящих для планирования периодических, апериодических, и спорадических задач [43]. В частности наша модель реализует алгоритмы RM, EDF, и LSTF для планирования периодических задач.
1. Производительность RM, EDF, LSTF по числу задач.
2. Производительность RM при различных распределениях задач по периодам
3. Производительность алгоритмов распределения по процессорам
4. Фон, Выбор, производительность DS, SS.
5. Производительность планировщика ввода - вывода
6. Вытесняющий и не вытесняющий диспетчер ( случай однородного распределения)
7. Вытесняющий и не вытесняющий диспетчер ( неоднородное распределение)
8. Производительность протоколов управления с приоритетами
9. Сравнение между BPI и протоколом предотвращения приоритета
Планирование апериодической задачи может быть поддержано в нашей модели посредством фона (BG), выбора (PL), алгоритмов DS, SS. Алгоритм планирования BG, выполняет апериодические задачи в те интервалы времени, когда нет активных периодических задач. PL, DS, и SS алгоритмы реализованы в виде периодических серверов, которые размещают апериодические задачи через равномерные промежутки времени, при условии, что никакая периодическая задача не выполняется. Планирование спорадических задач моделируется реализацией периодического сервера, посвященного планированию этих задач, который включается достаточно часто, и это гарантирует, что сроки выполнения спорадических задач не будут нарушены. Кроме того, в нашей модели, планирование задач, обращающихся к ресурсам Ввода - вывода может управляться одним из вытесняющих алгоритмов планирования, упомянутых выше (то есть RM, EDF, и LSTF алгоритмов). Кроме того, наша модель позволяет пользователю выбирать дисциплину FIFO для управления ресурсами ввода - вывода, и определить произвольные задержки сети. Наконец, наша модель реализует ряд протоколов синхронизации задач, которые осуществляют механизмы параллельного управления, и решают . Фраза " инверсия приоритетов ' используется, чтобы указать ситуацию, в которой выполнение задачи с более высоким приоритетом задержано задачами с более низким приоритетом . С планировщиками РВ, , которые управляются приоритетами, эта проблема может возникать, когда есть конфликт за разделяемые ресурсы среди задач с различными приоритетами. Чтобы моделировать mastering и контроль этой проблемы, наша модель реализует протоколы основного наследования Приоритета (BPI), Потолка Приоритета (PC), Предела Приоритета (PL), и управления семафорами (SC) [51]. Основная цель каждого из этих четырех протоколов -- минимизировать так называемое время блокировки в наихудшем случае, то есть интервал времени, в течение которого выполнение задачи с более высоким приоритетом может быть отсрочено задачами с более низким приоритетом. Альтернативный подход к решению проблемы инверсии приоритета был предложен, и основан на предотвращении возникновения этой проблемы. Чтобы оценивать эффективность этого подхода, наша модель включает особый протокол предотвращения конфликта приоритетов. Наша модель была осуществлена, с использованием языка программирования C, так, чтобы принимая на входе описание распределенной РВ системы, на выходе выдавала статистические результаты экспериментов по моделированию. Входное описание DRTS состоит из спецификации как загрузки системы, так и параметров операционной системы. Параметры загрузки системы включают следующие случайные величины: число периодических (PT) и апериодических задач (АT) которые могут запрашивать выполнение, период задачи (P), запрос CPU (CR) и крайний срок (D) каждой задачи, и их распределения вероятностей. Параметры операционной системы включают политику планирования и синхронизации задач, которые операционная система должна использовать, и две случайные переменные: затраты на смену задачи (PrC), сетевые затраты (NO). Выходные результаты предназначены для оценки эффективности различных алгоритмов, упомянутых выше. Таким образом, наша модель обеспечивает пользователей оценками качества BU и NMRT представленными ранее.
В наших модельных экспериментах мы исследовали работу алгоритмов, упомянутых выше, при разнообразных условиях загрузки различных систем, и характеристик операционной системы. Результаты, которые мы получили, представлены ниже.
Прежде всего, BU, полученная с RM, EDF и LSTF алгоритмами, для планирования периодических задач, была исследована как функция стоимости смены задач. Далее, мы предположим, что крайний срок выполнения задачи совпадает с периодом задачи, и что запрос cpu некоторой задачи I характеризуется однородным распределением в интервале [0, pi], где pi обозначает период I-ой задачи. Результаты моделирования, обсужденные в этом подразделе были получены с использованием метода независимых повторений (300 независимый прогонов для каждого эксперимента), и доверительные интервалы 95%, были построены для показателей производительности.
В предположении, что:
1. PrC - одинаков для каждого из этих трех алгоритмов,
2. РТ постоянна, равна 10,
3. P однородно распределена в интервале [1, 100],
наши результаты показывали, что динамические алгоритмы EDF и LSTF работают лучше чем RM статический алгоритм. Однако, практически, предположение 1 может быть нереалистично, поскольку динамические алгоритмы должны вычислить и назначать приоритеты задачи во время выполнения, таким образом добавляя дополнительные накладные расходы к стоимости смены задач; следовательно, использование RM алгоритма может быть предпочтительно для таких динамических алгоритмов, поскольку его реализация проще, и стоимость смены задач ниже.
Это наблюдение заставило нас уделить большее внимание исследованию RM алгоритма с точки зрения планирования периодических задач. Таким образом, мы исследовали поведение алгоритма при росте числа задач. Кроме того, мы рассмотрели следующим четыре различных распределений вероятности случайной переменной P:
1. Однородное распределение в [1, 100] (S = 816.8),
2. Бета распределение с параметрами а = 15 и b = 15 (S = 79.4), и параметры a = 0.5 и b = 0.5 (S = 1862.2),
3. Нормальное распределение с параметрами означает = 50.5 и S = 78.4,
4. Экспоненциальное распределение с параметром = 0.5, Бета, Нормальные и Экспоненциальные распределения вычислены в интервале [1,100]. (За S обозначен корень из дисперсии)
RM алгоритм чрезвычайно чувствителен к S случайной переменной P. В частности низкая S может особенно снизить эффективность RM. В сущности, этому можно дать следующее обьяснение. Алгоритм RM назначает более высокий приоритет задачам с более короткими периодами. Таким образом, если P имеет низкую S, периоды различных задач характеризуются короткими интервалами времени между их завершениями. Опираясь на это наблюдение, мы развили алгоритм, который размещает независимые задачи по процессорам распределенной РВ системы, чтобы обеспечить высокую разницу для P на каждом из этих CPU.
Рис. 4 изображает результат, полученной нашей моделью как функцию числа CPU. Этот рисунок иллюстрирует обычный алгоритм распределения задач (например, перебирая все CPU в системе, пока это не найдет подходящий для выполнения задачи. Алгоритм имеет низкий параметр BU, по сравнению с нашим алгоритмом распределения .
Относительно апериодических задач, NMRT - наиболее уместная оценка качества, когда эти задачи представлены в распределенной системе РВ, и сосуществуют с периодическими задачами. Эксперимент, который мы выполнили, состоял из моделирования присутствия (на том же самом CPU) и периодических и aperiodic задач. Мы принимаем что:
* Используемый алгоритм планирования - RM алгоритм,
* Загрузка периодической задачи - около 69\045, и число периодических задач - 10, с периодом, однородно распределенным в интервале [1,100] ,
* Время между последовательными активациями каждой апериодической задачи распределено по экспоненте с средним значением равным 20,
* Сервер апериодических задач - задача с самым высоким приоритетом.
Результаты моделирования NMRT, которые мы получили как функция загрузки апериодической задачи, показывают, что алгоритмы DS,SS и IS работают лучше чем такие традиционные алгоритмы как голосование и фон.
По существу, это позволяет начинать выполнение апериодической задачи в любое время в течение периода сервера. Таким образом сложные алгоритмы, типа DS, SS, позволяют планировщику быстро начинать выполнение апериодических задач. По сравнению с более простыми методами, типа голосования, эти алгоритмы эффективны для выполнения тех апериодических задач, которые запрашивают короткие сроки выполнение (даже если эти запросы очень часты). Однако, мы наблюдали(соблюдали), что, когда апериодические задачи требуют много машинного времени, различия между разными методами исчезают.
Запросы Ввода - вывода распределяются, вообще, согласно дисциплине FIFO; это может вести к низкому использованию ресурса.
Результаты, представленные на этом Рисунке были получены при моделировании следующей системы:
1. Переменное число периодических задач, с периодом P однородно распределенным в интервале [1,100] , одновременно выполняются в системе,
2. Каждая задача разделена на три части: вход, обработка, и выпуск. Мы предполагаем, что время, потраченное в течение ввода - вывода равно времени, которое потрачено при обработке данных.
Мы рассмотрели и вытесняющие и не вытесняющие диспетчеры ввода - вывода. Не вытесняющий диспетчер - тот, который не может прерывать ввод - вывод. При вытесняющем диспетчере задача с высоким приоритетом ввода - вывода может вытеснять задачу с более низким приоритетом. Следовательно, использование вытесняющего диспетчера предпочтительнее для систем реального времени. Однако, если осуществлен алгоритм RM, при назначении приоритетов на задачи (и следовательно, на запросы ввода - вывода) могут наблюдаться нижеописанные неочевидные результаты.
Мы выполнили множество моделирований, которые показывают различия работы (в терминах BU) между вытесняющими и не вытесняющими диспетчерами.
Мы исследовали поведение этих двух диспетчеров, когда периоды задачимеют разнообразные распределения. Рис.7 демонстрирует полученные значения BU, когда периоды задач однородно распределены в интервале [1, B]. Заметим, что вытесняющий диспетчер может вести к увеличению BU при ограниченном числе B. Использование распределений с малой дисперсией (то есть нормальное распределение с S=78.4) для периода случайной переменной P, мы получили, чтоBU, достигнутый невытесняющим диспетчером всегда больше чем вытесняющим. Напротив, используя высокую дисперсию распределения (Бета распределение с S=1862.2) приоритетный диспетчер выигрывает. Кроме того, мы отметили, что различие между двумя видами диспетчеров исчезает с ростом числа задач. Таким образом, преимущество вытесняющего диспетчера, не является абсолютным, поскольку эти зависит от загруженности системы.
Типичный случай проблем инверсии приоритета - когда задачи РВ используют общие данные. Параллельные доступы данным могут быть осуществлены посредством механизмов контроля параллизма типа семафоров. Однако, если задача с низким приоритета опускает семафор, задачи с более высокими приоритетами вынуждены ждать его поднятия, что получило название "blocking time overhead". Протоколы контроля приоритетов, которые ограничивают возможности блокировки в системах РВ, были развиты, чтобы гарантировать задачам выполнение в заданные сроки (то есть BPI, SC, PL, и протоколы PC, выше упомянутые). Эти протоколы обеспечивают различную эффективность; в частности, когда время блокирования растет, BPI особенно не справляется. Напротив, эффективности PC, SC, и PL очень близки друг к другу( результаты работы протокола PL опущены).SC протокол оптимален, но трудно осуществим; Поэтому множество последних систем РВ (например MACH ) используют протокол PC.
Наконец, наша модель реализует недавно предложенный протокол предотвращения приоритетов. Этот протокол отличается от протоколов контроля приоритетов, ранее исследованных тем, что способствует устранению проблемы инверсии приоритета. При использовании этого протокола, анализ системы РВ действительно более прост, поскольку требуется меньшее количество усилий для построения распределения для этой системы. Однако, эффективность этого протокола ниже, чем у протоколов контроля приоритетов.
В этой главе мы представим пять систем РВ: the SPRING kernel, HARTS, MARS, MARUTI, и CHAOS. Эти системы будут разобраны отдельно.
SPRING - распределенный RT OS ядро, развитое в Университете Штата Массачусетс.Проектировщики SPRING утверждают, что при развитии обычных систем РВ часто присутствовало множество непониманий и недостатков, что разобрано в анализе прикладного процессора NODE
Ядро SPRING нацелено на преодоление тех недостатков. В частности ключевые моменты, в подходе проекта SPRING включают гибкость и предсказуемость, в пределах контекста распределенной системы РВ.
В SPRING задачи классифицируются по последствиям при неукладываемости в крайние сроки:
* Критические задачи (или HRT задачи) - те, которые должны быть выполнены в их крайние сроки, иначе последствия будут катастрофическими;
* Существенные(необходимые) задачи - те, которые действительно требуют выполнения в срок, но, в случае ошибки, они не могут привести к опасным ситуациям.
* Несущественные задачи могут иметь или не иметь РВ ограничения. Однако, несущественная задача, пропустившая крайний срок, может причинить только небольшие неудобства, поскольку их временные ограничения имеют некоторую свободу (то есть эти ограничения определяют только предпочтительное время получения результата).
Каждая существенная и несущественная задача характеризована параметром критичности. Этот параметр используется, чтобы определить степень необходимости задачи. Ядро SPRING выполняет существенные и несущественные задачи, максимизируя ценность, которая может быть получена как сумма параметров критичности этих задач. (Критические задачи не учавствуют в этом процессе максимизации, поскольку они выполняются с самым высоким приоритетом.)
Модель аппаратных средств ЭВМ для ядра SPRING - мультипроцессорная распределенная система. Каждый узел составлен одним (или больше) прикладным процессором, одним (или больше) процессором системы и подсистемой ввода - вывода. Прикладные процессоры выполняют критические и существенные задачи; процессоры системы управляют операционной системой, также как задачами, которые не имеют крайних сроков. Подсистема ввода - вывода обращается с некритическим вводом - выводом, медленными устройствами ввода - вывода и быстрыми датчиками.
Ядро SPRING способно планировать группы задач. Группа - множество задач, имеющих ограниченное взаимодействие между собой, но общий срок выполнения. Кроме того, SPRING поддерживает инкрементальные задачи, то есть задачи, которые вычисляют ответ как можно скорее, и продолжают увеличивать его точность, пока есть время. (Полное обсуждение по инкрементальным задачам может быть найдено в).
В слабо связанной окружающей среде процессоров, типа используемой SPRING, оптимальный алгоритм планирования, в самом плохом случае, может выполнять полный перебор по всем возможным разделениям задач; это тяжелая проблема в вычислительном отношении.
SPRING реализует проблему планирования, используя эвристический подход. В сущности, всякий раз, когда требуется выполнение задачи , SPRING пытается обеспечить выполнение в местном масштабе, то есть пробует строить график выполнения задачи на том же самом узле, где произошел запрос выполнения. Если попытка терпит неудачу, SPRING выбирает другой узел для запроса. Наконец, стоит упоминуть, что в проекте ядра SPRING было уделено мало внимания проблемам устойчивости к ошибкам.
Распределенная РВ архитектура проекта HARTS (гексагональная Архитектура для систем реального времени ) основана на общей памяти мультипроцессорных узлов, связанных развернутой гексагональной сетью . Эта архитектура направлена на выполнение РВ задач с высокой скоростью, надежностью, и предсказуемостью. Сеть HARTS может быть удобно осуществлена на аппаратных средствах ЭВМ (например посредством VLSI чипа), поскольку она плоская, и характеризуется фиксированным числом связей. Эта сеть - масштабируемая, и обеспечивает поддержку устойчивости к ошибкам. Один из главных моментов исследования проекта HARTS направлен на архитектурные проблемы низкого уровня, типа направления сообщения и буферизации, планирования и набора комманд. Кроме того, поскольку HARTS реализуют и распределенную систему и мультипроцессорные архитектурные особенности, это позволяет оценивать поведение РВ программ и в распределенной и в окружающей среде мультипроцессора. HARTS OS - операционная система, разработанная для HARTS.Цели ядра HARTS OS - обеспечение однородного интерфейса для коммуникаций в реальном масштабе времени между процессами, независимо от их физического местоположения. В частности,в HARTS OS протокол уровня связи поддерживает сосуществование, в сети связей, соединения нормальных задач и задач реального времени. Прикладной интерфейс обеспечивает система запросы к РВ коммуникациям, также как запросам к удаленным процедурам и получению информации, . Кроме того, HARTS OS поддерживает устойчивость к ошибкам, очередь сообщений, внеочередные сигналы событий, и общую память (между процессорами в одном узле).
Надежность обеспечивается на двух абстрактных уровнях: сетевом и уровне задания. На уровне задания HARTOS поддерживает репликацию и многонаправленные коммуникации; на сетевом уровне ( схему перенаправления сообщений, обрабатывающую ошибки при установлении связи. Ранняя версия HARTOS базировалась на ядре pSOS, операционной системы для однопроцессорных систем реального времени; настоящая версия базируется на x-kernel.
MARS (Maintainable Real-time System) ( надежная поставляемая архитектура систем реального времени для контроля над процессами, разработанная в Венском Техническом Университете. Она предназначена для использования в промышленности, что предполагает режим жесткого реального времени. MARS разработан так, что его действия останутся детерминированными даже тогда, когда электрические параметры сети достигают экстремально допустимых значений. MARS гарантирует, что скачки этих параметров не повлияют на режим работы сети. В MARS все действия синхронизированы по глобальным часам (в частности, единственное доступное в системе прерывание ( прерывание таймера, маркирующее одновременно центральный процессор и шину данных; это обеспечивает предсказуемость системы.
Текущая версия может быть установлена на кластере одноплатных монопроцессорных узлов . С физической точки зрения аппаратура кластера представляет собой стандартный ethernet; но протокол доступа к каналам данных базируется на TDMA (так как стандартный протокол ethernet CSMA(CD (IEEE 802.3) не может гарантировать корректную обработку пиковых ситуаций). Как уже упоминалось, отдельный чип отвечает за синхронизацию часов.
Ключевые направления этого проекта включают:
(надежность: реплицированная аппаратура и механизм сообщений;
(MARS имеет статическую, создаваемую до запуска на исполнение таблицу заданий;
(неисправные компоненты кластера могут быть заменены во время работы, что не должно повлиять на режим работы системы;
(поддержка неисправной сети (работа ведется в настоящее время).
В заключение, важное достижение этого проекта, заслуживающее упоминания: среда программирования MARS'а , графически-ориентированный CASE для разработки приложений реального времени.
Система поддерживает два класса объектов: объекты уровня приложений и объекты уровня ядра. На уровне ядра MARUTI предоставляет объект ( дескриптор прерывания, с помощью которого можно определить для любого прерывания системы объект-обработчик, а также объект-обработчик таймера, используемый для синхронизации и сообщения о событиях, и диспетчер заданий. На уровне приложений эта система включает в себя распределитель, поставляющий задания (исполняемые в оффлайновом режиме) процессорам и управляющий файловой системой. Объекты могут общаться либо используя разделяемые буферы (если они исполняются на одном узле), либо с помощью механизма сообщений.
CHAOS [17,53] (Concurrent Hierarhical Adaptable Object System) ( программная среда и операционная система для приложений реального времени. Как и MARUTI, CHAOS ( объектно-ориентирован. Система CHAOS предлагает примитивы уровня ядра, поддерживающие разработку программного обеспечения структурированного в виде набора интерактивных объектов. CHAOS особенно удобен при разработке больших, комплексных приложений реального времени со строгими ограничениями на время исполнения. Задача системы ( поддержка программирования адаптивных, эффективных, предсказуемых и надежно работающих приложений. Эффективность важна из-за временных ограничений; следовательно, системные издержки должны быть сведены до минимума. В этой системе удалось добиться высокой эффективности без ущерба для ее надежности. Надежность может быть обеспечена двумя путями: либо ядро исправляет уже сделанные ошибки, либо оно обнаруживает возможную опасность до прихода системы в аварийное состояние (Например, в CHAOS непредвиденное изменение системного окружения, замеченное ядром, приведет к тому, что выполнение задание будет приостановлено и ядро сообщит приложению об ошибке). Таким образом, одна из задач обеспечения надежности ( дать программисту возможность описать в приложении методы для избежания ошибок. Приложения реального времени для CHAOS можно сконструировать с использованием системных примитивов, приспособляя готовые примитивы для нужд приложения или определяя новые. CHAOS гарантирует предсказуемость работы всех синтезированных примитивов. Кроме того, CHAOS предоставляет механизмы мониторинга программного обеспечения, помогающие удовлетворить предъявленным к программе требованиям. CHAOS может быть применена к конструированию роботов (CHAOS тестировалась на шестиногом шагающем роботе). Что касается диспетчеризации заданий, CHAOS использует двухуровневую модель. Высший уровень состоит из диспетчера объектов, который получает запросы и определяет режим их исполнения в зависимости от атрибутов запроса и загруженности процессора. Этот диспетчер базируется на эвристическом алгоритме жадности. На процессорном уровне диспетчеризация происходит по принципу "самое раннее из срочных заданий выполняется первым". CHAOS наследует концепцию атомности операций. Атомность повышает корректность работы, так как действия по восстановлению системы после ошибки могут быть предприняты при ошибке таймера.
В завершение этого параграфа мы хотим сказать, что пять различных систем, описанных в нем, были подобраны с целью показать широкий спектр технологических решений, которые могут быть выбраны при проектировании систем реального времени. Например, SPRING, предназначенная для предсказуемых инфраструктур реального времени, игнорирует проблемы исправления ошибок; но ее авторы разработали гибкую архитектуру, которая может быть приспособлена к заданиям с различными требованиями (критическим, существенным и несущественным заданиям). В разработке HARTS большое внимание уделено низкоуровневой архитектуре и введена сеть с особой топологией. MARS ( предсказуемая, синхронизированная архитектура, использующая преимущества синхронной системы, чтобы доставить пользователю инфраструктуру для работы приложений жесткого реального времени. Наконец, в системах MARUTI и CHAOS исследовано применение объектно-ориентированного подхода к разработке высоконадежных операционных систем реального времени. MARUTI предоставляет возможность интегрированного исполнения как обычных задач, так и задач реального времени. CHAOS поддерживает возможность исправления ошибок и предоставляет возможность самим приложениям исправить сделанные ими ошибки.
В этом введении мы обсудили многие технические решения в разработке систем реального времени и кратко описали пять примеров управляющих систем реального времени, которые были недавно разработаны. В заключение мы приведем основные особенности систем реального времени в целом и управляющих систем реального времени в частности. Начнем с того, что "времязависимость" есть непременный атрибут системы реального времени. Но выполнение этого требования еще недостаточно для эффективной работы системы, так как в первую очередь система реального времени должна быть "предсказуемой". Мы описали две архитектуры, обеспечивающие предсказуемость системы: либо все действия в системе синхронизированы по времени, либо каждому действию предшествует определенное событие. Цель этих двух типов архитектур ( удовлетворить требованию предсказуемости, применяя статическую или динамическую стратегии соответственно, чтобы выдержать требования к ресурсам и временные требования, предъявляемые к заданиям. Далее была представлена синхронизация часов в применении к управляющим системам реального времени. В этом тексте мы предполагали, что обмен сообщениями синхронизации часов позволяет достичь эффективности алгоритмов синхронизации, которые могут быть использованы в этих системах. Далее мы обсудили проблемы межпроцессного взаимодействия в системах реального времени. Были представлены принципиальные требования к коммуникационной инфраструктуре для поддержки приложений реального времени (а именно: задержка доступа к каналу связи, задержка сообщений связи и нерв задержки связи). Важнейшими характеристиками коммуникационного механизма, как мы выяснили в ходе обсуждения, являются: процент потери сообщений, скорость передачи сообщений, процент потери экстренных сообщений, эффективность использования канала передачи данных и масштабируемость механизма. Наконец, мы рассмотрели диспетчеризацию в системах реального времени и обсудили важнейшие влияющие факторы: обработка обращения к недоступным ресурсам, среднее время ответа на запрос, гарантированный процент вовремя обработанных запросов.