Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Операционные системы реального времени

1.1 Описание и общие требования к системам реального времени

1.2 Параметры ОСРВ

1.3 Механизмы реального времени

1.4 Классы систем реального времени

Выводы к главе 1

Глава 2. Поддержка отказоустойчивости вычислительных систем средствами операционных систем реального времени

2.1 Понятие отказоустойчивости ВС

2.2 Причины и классификация отказов и сбоев

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

2.4 Концепция построения и работы системы с рангом отказоустойчивости N-1

2.4.1 Инициализация

Глава 3. Программное обеспечение модели отказоустойчивой ВС

3.1 Программное обеспечение модели узла ВС

3.2 Программное обеспечение подсистемы проверки

3.3 Портирование ОСРВ на платформу TMS320C30

3.4 Обзор базовых ОСРВ для платформы TMS320C30

Заключение

Список источников

Введение

реальный отказоустойчивость вычислительный операционный

В течение многих лет приложения на базе ОС реального времени использовались во встроенных системах специального назначения, а с недавнего времени они стали применяться повсюду, от бортовых систем управления ЛА, до бытовых приборов.

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

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

Таким образом, объектом исследования в рамках сетевой отказоустойчивой технологии становится ОСРВ -- управляющее программное обеспечение особого типа, которое используется для организации работы встроенных приложений, для которых характерны ограниченность ресурсов памяти, невысокая производительность, а также требования гарантированного времени отклика, высокого уровня готовности и наличия средств автомониторинга.

Данная дипломная работа посвящена разработке специализированной распределенной операционной системы реального времени для отказоустойчивых ВС с рангом отказоустойчивости N(N-1), что означает способность системы функционировать даже в том случае, если произойдут отказы всех элементов системы за исключением одного. Для полного освещения выбранной темы были поставлены следующие задачи:

Провести анализ существующих операционных систем реального времени, выделить основные функциональные требования к ним, дать сравнительную характеристику.

Раскрыть концепцию построения ОСРВ с рангом отказоустойчивости N-1, выделить основные модули операционной системы, функциональные требования к ним и алгоритмы работы.

Раскрыть логику организации отказоустойчивых вычислений на примере конкретной реализации.

Провести анализ надежности отказоустойчивой ВС и дать рекомендации по организации ВС.

Создать программную модель вычислительной системы с распределенной операционной системой реального времени и отработать на ней различные режимы работы.

Рассмотреть возможность портирования (переноса) ОСРВ на платформу TMS320c30, рассмотреть специфические проблемы и сложности при осуществлении портации.

В первой части работы дано краткое описание известных ОСРВ, описаны их функциональные возможности, структура, их направленность (специфические особенности). Также приведена сравнительная характеристика и отмечены те решения, которые можно было бы использовать для разработки собственной специализированной ОСРВ.

Во второй главе описана концепция построения распределенной ОСРВ, были сформулированы основные принципы функционирования перспективной вычислительной системы, включающие в себя многопроцессорность, обеспечение живучести, адаптацию к изменениям внутренних условий среды, поддержку реального масштаба времени, мобильность и открытость программного обеспечения. Предложен пример организации отказоустойчивых вычислений на примере пяти-узловой полносвязной сети ПЭ в условиях постоянной деградации системы.

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

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

Глава 1. Операционные системы реального времени

ОС общего назначения, особенно многопользовательские, ориентированы на оптимальное распределение ресурсов компьютера между пользователями и задачами (системы разделения времени), В операционных системах реального времени (ОСРВ), подобная задача отходит на второй план - все отступает перед главной задачей - успеть среагировать на события, происходящие на объекте.

1.1 Описание и общие требования к системам реального времени

Применение операционной системы реального времени всегда связано с аппаратурой, с объектом, с событиями, происходящими на объекте. Система реального времени, как аппаратно-программный комплекс, включает в себя датчики, регистрирующие события на объекте, модули ввода-вывода, преобразующие показания датчиков в цифровой вид, пригодный для обработки этих показаний на компьютере, и, наконец, компьютер с программой, реагирующей на события, происходящие на объекте. ОСРВ ориентирована на обработку внешних событий. Именно это приводит к коренным отличиям (по сравнению с ОС общего назначения) в структуре системы, в функциях ядра, в построении системы ввода-вывода. ОСРВ может быть похожа по пользовательскому интерфейсу на ОС общего назначения, однако устроена она совершенно иначе - об этом речь впереди.

Кроме того, применение ОСРВ всегда конкретно. Если ОС общего назначения обычно воспринимается пользователями (не разработчиками) как уже готовый набор приложений, то ОСРВ служит только инструментом для создания конкретного аппаратно - программного комплекса реального времени. И поэтому наиболее широкий класс пользователей ОСРВ - разработчики комплексов реального времени, люди проектирующие системы управления и сбора данных. Проектируя и разрабатывая конкретную систему реального времени, программист всегда знает точно, какие события могут произойти на объекте, знает критические сроки обслуживания каждого из этих событий.

Назовем системой реального времени (СРВ) аппаратно-программный комплекс, реагирующий в предсказуемые времена на непредсказуемый поток внешних событий.

Это определение означает, что:

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

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

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

Системы жесткого реального времени не допускают никаких задержек реакции системы ни при каких условиях, так как:

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

· может произойти катастрофа в случае задержки реакции,

· стоимость опоздания может оказаться бесконечно велика.

Примеры систем жесткого реального времени - бортовые системы управления, системы аварийной защиты, регистраторы аварийных событий.

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

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

Тогда операционная система реального времени - это такая ОС, которая может быть использована для построения систем жесткого реального времени. Это определение выражает отношение к ОСРВ как к объекту, содержащему необходимые инструменты, но также означает, что этими инструментами еще необходимо правильно воспользоваться.

1.2 Параметры ОСРВ

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

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

События, происходящие на объекте, регистрируются датчиками, данные с датчиков передаются в модули ввода-вывода (интерфейсы) системы. Модули ввода-вывода, получив информацию от датчиков и преобразовав ее, генерируют запрос на прерывание в управляющем компьютере, подавая ему тем самым сигнал о том, что на объекте произошло событие. Получив сигнал от модуля ввода-вывода, система должна запустить программу обработки этого события.

Интервал времени - от события на объекте и до выполнения первой инструкции в программе обработки этого события и является временем реакции системы на события.

Обычно время реакции систем на прерывание составляет порядка 4-10 мкс.

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

Контекст задачи это набор данных, задающих состояние процессора при выполнении задачи. Обычно совпадает с набором регистров, доступных для изменения прикладной задаче.

При переключении задач (процессов) необходимо:

1. корректно остановить работающую задачу;

для этого

а) выполнить инструкции текущей задачи, уже загруженные в процессор, но еще не выполненные;

б) сохранить в оперативной памяти регистры текущей задачи;

2. найти, подготовить и загрузить затребованную задачу;

3. запустить новую задачу, для этого

а) восстановить из оперативной памяти регистры новой задачи (сохраненные ранее,

если она до этого уже работала);

б) загрузить в процессор инструкции новой задачи.

Каждая из этих стадий вносит свой вклад в задержку при переключении контекста. Поскольку любое приложение реального времени должно обеспечить выдачу результата в заданное время, то эта задержка должна быть мала, детерминирована и известна. Это число является одной из важнейших характеристик ОСРВ. Обычно время переключения контекста в ОСРВ составляет 10-20 мкс.

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

1.3 Механизмы реального времени

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

Базовыми инструментами разработки сценария работы системы являются система приоритетов процессов (задач) и алгоритмы планирования (диспетчеризации) ОСРВ.

В многозадачных ОС общего назначения используются, как правило, различные модификации алгоритма круговой диспетчеризации, основанные на понятии непрерывного кванта времени ("time slice"), предоставляемого процессу для работы. Планировщик по истечении каждого кванта времени просматривает очередь активных процессов и принимает решение, кому передать управление, основываясь на приоритетах процессов (численных значениях, им присвоенных). Приоритеты могут быть фиксированными или меняться со временем - это зависит от алгоритмов планирования в данной ОС, но рано или поздно процессорное время получат все процессы в системе.

Алгоритмы круговой диспетчеризации неприменимы в чистом виде в ОСРВ. Основной недостаток - непрерывный квант времени, в течение которого процессором владеет только один процесс. Планировщики же ОСРВ имеют возможность сменить процесс до истечения "time slice", если в этом возникла необходимость. Один из возможных алгоритмов планирования при этом "приоритетный с вытеснением". Мир ОСРВ отличается богатством различных алгоритмов планирования: динамические, приоритетные, монотонные, адаптивные и пр., цель же всегда преследуется одна - предоставить инструмент, позволяющий в нужный момент времени исполнять именно тот процесс, который необходим.

Другой набор механизмов реального времени относится к средствам синхронизации процессов и передачи данных между ними. Для ОСРВ характерна развитость этих механизмов. К таким механизмам относятся: семафоры, мьютексы, события, сигналы, средства для работы с разделяемой памятью, каналы данных (pipes), очереди сообщений. Многие из подобных механизмов используются и в ОС общего назначения, но их реализация в ОСРВ имеет свои особенности - время исполнения системных вызовов почти не зависит от состояния системы, и в каждой ОСРВ есть по крайней мере один быстрый механизм передачи данных от процесса к процессу.

Такие инструменты, как средства работы с таймерами, необходимы для систем с жестким временным регламентом, поэтому развитость средств работы с таймерами - необходимый атрибут ОСРВ. Эти средства, как правило, позволяют:

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

· генерировать прерывания по истечении временных интервалов,

· создавать разовые и циклические будильники

Здесь описаны только базовые, обязательные механизмы, использующиеся в ОСРВ. Кроме того, почти в каждой ОСРВ можно найти целый набор дополнительных, специфических только для нее механизмов, касающийся системы ввода-вывода, управления прерываниями, работы с памятью. Каждая система содержит также ряд средств, обеспечивающих ее надежность: встроенные механизмы контроля целостности кодов, инструменты для работы с таймерами.

1.4 Классы систем реального времени

Монолитная архитектура

ОСРВ с монолитной архитектурой можно представить в виде (рис. 1.1)

прикладного уровня: состоит из работающих прикладных процессов;

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

Рис. 1.1. ОСРВ с монолитной архитектурой

Интерфейс в таких системах играет двойную роль:

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

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

Основным преимуществом монолитной архитектуры является ее относительная быстрота работы по сравнению с другими архитектурами. Однако, достигается это, в основном, за счет написания значительных частей системы на ассемблере.

Недостатки монолитной архитектуры.

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

2. Ядро не может быть прервано пользовательской задачей (non-preemptable). Это может приводить к тому, что высокоприоритетная задача может не получить управления из-за работы низкоприоритетной.

3. Сложность переноса на новые архитектуры процессора из-за значительных ассемблерных вставок.

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

Модульная архитектура (на основе микроядра)

Модульная архитектура появилась, как попытка убрать интерфейс между приложениями и ядром и облегчить модернизацию системы и перенос ее на новые процессоры.

Теперь микроядро играет двойную роль(рис 1.2):

1. управление взаимодействием частей системы (например, менеджеров процессов и файлов),

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



Рис. 1.2. ОСРВ на основе микроядра

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

Объектная архитектура на основе объектов-микроядер

В этой архитектуре интерфейс между приложениями и ядром отсутствует вообще (рис. 1.3). Взаимодействие между компонентами системы (микроядрами) и пользовательскими процессами осуществляется посредством обычного вызова функций, поскольку и система, и приложения написаны на одном языке (обычно C++). Это обеспечивает максимальную скорость системных вызовов.



Рис. 1.3. Пример объектно-ориентированной ОСРВ

Фактическое равноправие всех компонент системы обеспечивает возможность переключения задач в любое время. Объектно-ориентированный подход обеспечивает модульность, безопасность, легкость модернизации и повторного использования кода.

В отличие от предыдущих систем, не все компоненты самой операционной системы должны быть загружены в оперативную память. Если микроядро уже загружено для другого приложения, то оно повторно не загружается, а используется код и данные уже имеющегося микроядра. Все эти приемы позволяют сократить объем требуемой памяти. Поскольку разные приложения разделяют одни микроядра, то они должны работать в одном адресном пространстве. Следовательно, система не может использовать виртуальную память и тем самым работает быстрее (так как исключаются задержки на трансляцию виртуального адреса в физический).

Обзор некоторых коммерческих ОСРВ

Операционная система OS-9

OS-9 фирмы Microware относится к классу UNIX-подобных операционных систем реального времени. По своей сути OS-9 является многозадачной ОС с вытесняющей приоритетной диспетчеризацией, допускающая возможность многопользовательской работы. Объектно-ориентированный модульный дизайн системы позволяет конфигурировать систему в очень широком диапазоне от встраиваемых систем до больших сетевых приложений. Согласно этой концепции все функциональные компоненты OS-9, включая ядро, иерархические файловые менеджеры, драйвера устройств и т. д., реализованы в виде независимых модулей. Все модули операционной системы позиционно-независимы и могут быть размещены в ПЗУ, а также могут удаляться из системы в процессе ее функционирования без какой-либо повторной инсталляции или перекомпоновки. На рисунке 1.4 приведена упрощенная структурная схема операционной системы.

Структура операционной системы OS-9

Рис. 1.4. Структура операционной системы OS-9

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

Основные характеристики:

1. Архитектура: на основе микроядра

2. Стандарт: собственный, вызовы похожи на UNIX

Свойства как ОСРВ:

Многозадачность: многопроцессность

Многопроцессорность: да

Уровней приоритетов: 65535

Время реакции: 3 мкс

Планирование: приоритетное, FIFO, специальный механизм планирования; preemptive ядро

3. ОС разработки (host): UNIX/Windows

4. Процессоры (target): Motorola 68xxx, Intel 80x86, ARM, MIPS, PowerPC

5. Линии связи host-target: последовательный канал и ethernet

6. Минимальный размер: 16Kb

7. Средства синхронизации и взаимодействия: разделяемая память, сигналы, семафоры, события.

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

VxWorks относится к операционным системам «жесткого» реального времени. Характерной чертой этой ОС является то, благодаря ее развитым сетевым возможностям, вся разработка ПО ведется на инструментальном компьютере (хост-системе) с использованием кросс-средств для последующего исполнения на целевой машине под управлением VxWorks.

Отличительная черта системы - возможность управлять работой сложных комплексов реального времени и бортовых устройств, использующих процессорные элементы различных поставщиков. Три основных компонента данной ОС РВ образуют единую интегрированную среду: собственно ядро системы, управляющее процессором; набор средств межпроцессорного взаимодействия; комплект коммуникационных программ для работы с Ethernet или последовательными каналами связи.

Основные характеристики:

1. Архитектура: монолитная

2. Стандарт: собственный и POSIX 1003

3. Свойства как ОСРВ:

Многозадачность: многопроцессность и многозадачность

Многопроцессорность: да

Уровней приоритетов: 256

Время реакции: 4 мкс

Время переключения контекста: 15 мкс

Планирование: приоритетное; preemptive ядро

4. ОС разработки (host): UNIX/Windows

5. Процессоры (target): Motorola 68xxx, Intel 80x86, Intel 80960, PowerPC, SPARC, Alpha, MIPS, ARM

6. Линии связи host-target: последовательный канал, ethernet, шина VME

7. Минимальный размер: 22Kb

8. Средства синхронизации и взаимодействия: семафоры POSIX 1003, очереди, сигналы…

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

Операционная система QNX канадской компании QNX Software System Ltd. построена на основе иерархической микроядерной архитектуры. Упрощенная структурная схема этой ОС приведена на рисунке 1.5.

Рис. 1.5. Микроядерная структура QNX

Микроядро QNX выполняет следующие функции:

межпроцессорный обмен;

низкоуровневый сетевой обмен;

диспетчеризация задач;

низкоуровневая обработка прерываний.

Основные характеристики:

1. Архитектура: на основе микроядра

2. Стандарт: POSIX 1003

3. Свойства как ОСРВ:

Многозадачность: POSIX 1003 (многопроцессность и многозадачность)

Многопроцессорность: да

Уровней приоритетов: 32

Время реакции: 4,3 мкс

Время переключения контекста: 13 мкс

Планирование: FIFO, round robin, адаптивное; preemptive ядро

4. Процессоры (target): Intel 80x86

5. Минимальный размер: 60Kb

6. Средства синхронизации и взаимодействия: POSIX 1003 (семафоры, mutex, condvar)

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

Система LynxOS выпускается фирмой Lynx Real Time Systems (Los Gatos, USA). ОСРВ из клона UNIX-систем, обеспечивающая детерминированное время отклика по запросам.

Основные характеристики:

1. Архитектура: на основе микроядра

2. Стандарт: POSIX 1003

3. Свойства как ОСРВ:

Многозадачность: POSIX 1003 (многопроцессность и многозадачность)

Многопроцессорность: да

Уровней приоритетов: 255

Время реакции: 7 мкс

Время переключения контекста: 17 мкс

Планирование: FIFO, round robin, Quantum, preemptive ядро

4. Процессоры (target): Intel 80x86, Motorola 68xxx, SPARC, PowerPC

5. Минимальный размер:

полной системы: 256Kb

усеченной системы: 124Kb

только ядра: 33Kb

Систему можно записать в ROM.

6. Средства синхронизации и взаимодействия: POSIX 1003 (семафоры, mutex, condvar)

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

Система pSOS выпускается Integrated Systems (Santa Clara, USA).

Основные характеристики:

1. Архитектура: на основе микроядра

2. Стандарт: собственный

3. Свойства как ОСРВ:

Многозадачность: многопроцессность и многозадачность

Многопроцессорность: да

Уровней приоритетов: 255

Время реакции: 4 мкс

Время переключения контекста: 12мкс

Планирование: приоритетное; preemptive ядро

4. ОС разработки (host): UNIX/Windows

5. Процессоры (target): Motorola 68xxx, Intel 80x86, Intel 80960, ARM, MIPS, PowerPC

6. Минимальный размер: 15Kb

8. Средства синхронизации и взаимодействия: семафоры, mutex, события, и тд.

Выводы к главе 1

Основными отличиями ОСРВ от ОС общего назначения являются:

Ориентация на обработку внешних событий;

Детерминированное время реакции на внешнее событие;

Модульная организация;

Небольшой размер системы.

В главе были рассмотрены важнейшие параметры и механизмы ОСРВ, такие как:

Время реакции системы;

Время переключения контекста;

Виды диспетчеризации;

Механизмы синхронизации и межзадачного взаимодействия

Классификация ОСРВ позволяет выделить наиболее оптимальную структуру построения ОСРВ. Очевидно, что операционные системы с монолитной архитектурой, вследствие их направленности на конкретные процессорные платформы и характера взаимодействия с ядром, вряд ли могут быть использованы в качестве относительно универсальных ОСРВ для систем высокой готовности. ОСРВ на основе микроядра обладает рядом преимуществ по сравнению с монолитной архитектурой, а комбинация с объектно-ориентированным подходом, позволит системе стать аппаратно-независимой и обеспечить быструю реакцию на внешние события.

В заключении были перечислены основные свойства некоторых распространенных ОСРВ. К сожалению, ни одну из рассмотренных операционных систем нельзя назвать сетевой в широком смысле этого слова, так как уровень сетевого обмена, заложенный в многих из них соответствует уровню локальной сети. Многопроцессорная поддержка, введенная в VxWorks ориентирована только на системы с общей памятью. Отсутствие механизма отказоустойчивости, допускающего как отказы соединений (зачатки этого есть в QNX), так и отказы процессорных элементов, необходимого для отказоустойчивых специализированных вычислительных систем, нет ни в одной из этих операционных систем. Таким образом, задачей разработчиков является добавление таких модулей существующим ОСРВ, которые позволили бы обеспечить отказоустойчивость распределенных вычислительных систем.

Глава 2. Поддержка отказоустойчивости вычислительных систем средствами операционных систем реального времени

Специфика применения некоторых систем обусловливает особые требования, предъявляемые к надежности их функционирования. Отказ или сбой в их работе, повлекшие за собой неправильные результаты вычислений (или полное их отсутствие), могут привести к катастрофическим последствиям. Преимущества использования отказоустойчивых вычислительных систем непосредственно вытекают из необходимости продолжительной работы системы в условиях, когда техническое обслуживание (ремонт, замена и тд.) невозможны, труднореализуемы или сопряжены с большими экономическими затратами. Поэтому ВС и специализированные операционные системы разрабатываются таким образом, чтобы система была толерантна (терпима) к возникающим отказам. Особенно это актуально для автономных ЛА (например, космических аппаратов).

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

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

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

При рассмотрении надёжности вычислительной системы следует иметь ввиду, что она определяется надёжностью аппаратной части и надёжностью программного обеспечения. Однако, понятие надёжности программного обеспечения неконструктивно, это означает, что на этапе тестирования программы не были выявлены все ошибки. В данной работе считается, что программа не содержит ошибок, и получение результата, отличных от ожидаемого зависит от сбоев или отказов аппаратной части или иных факторов (например, влияние ЭМИ на содержание оперативной памяти), а потому вопрос о надёжности программного обеспечения не ставится. Таким образом, надёжность вычислительной системы определяется надёжностью аппаратуры и влиянием отказов в ней на отказы в вычислительной системе в целом.

Предварительные исследования показали, что для элементной базы среднего качества (надежность 0.999 - “три девятки после запятой”) при оптимальном сочетании скорости получения результата на его надежность в вычислительной среде теоретически достижима достоверность получения правильных результатов машинного счета в “двести девяток после запятой” при замедлении темпа их получения в 300-400 раз [1], что эквивалентно увеличению надежности до 200 порядков величины при введении сравнительно небольшой вычислительной избыточности, приводящей к потере производительности не более чем на 2-3 порядка, что уже на современном уровне может компенсироваться подбором компьютеров требуемой производительности.

2.1 Понятие отказоустойчивости ВС

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

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

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

2.2 Причины и классификация отказов и сбоев

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

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

- отказ процессора (центральной части ПЭ);

- отказ линка - связи между ПЭ;

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

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

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

нарушения кодов записи программ в памяти команд;

стирания или искажения данных в оперативной или долговременной памяти;

нарушения нормального хода вычислительного процесса.

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

Основная особенность (и достоинство) сетевой отказоустойчивой технологии - отсутствие какого-либо (даже самого незначительного) единственного компонента (ресурса), выход из строя которого приводит к фатальному отказу всей системы. Такая система не может содержать какого-либо "центрального" (главного) узла, размещенного в одном из процессорных элементов системы, она может состоять только из "равноправных" частей, размещенных в каждом узле сети. Таким образом можно говорить лишь о деградации качества системы при отказе одного или более ее элементов. В такой системе полный отказ наступает после выхода из строя только определенного количества ресурсов, определенного на этапе проектирования.

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

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

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

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

При возвратном восстановлении происходит возврат процесса (или системы) из некорректного состояния в некоторое из предшествующих корректных состояний. При этом возникают следующие проблемы:

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

Нет гарантии, что сбой снова не повторится после восстановления.

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

Для восстановления состояния в традиционных ЭВМ применяются два метода (и их комбинация), основанные на промежуточной фиксации состояния либо ведении журнала выполняемых операций. Они различаются объемом запоминаемой информацией и временем, требуемым для восстановления.

Применение подобных методов в распределенных системах наталкивается на следующие трудности:

Для распределенных систем запоминание согласованного глобального состояния является серьезной теоретической проблемой;

методы восстановления после отказов для некоторых систем непригодны из-за прерывания нормального функционирования и др;

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

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

Обеспечение живучести - это использование специальных средств, позволяющих системе продолжать правильное функционирование при возникновении отказов ее программных и аппаратных компонентов с возможностью деградации качества функционирования [2]. В отличие от отказоустойчивости, где с отказом не связано качество работы ВС, сравнительно сложные средства обеспечения живучести позволяют более рационально расходовать вычислительные ресурсы и увеличивать среднее время наработки до наступления фатального отказа. Обеспечение живучести обычно включает три основные функции: диагностика возникновения отказа, локализация неисправности и перестройка системы. В основе толерантности лежит избыточность как аппаратного, так и программного обеспечения. Поэтому многопроцессорные системы с присущей им аппаратной избыточностью потенциально позволяют создавать не только высокопроизводительные, но и высоконадежные системы.

Другим основополагающим требованием является наличие механизма, позволяющего агентам в каждом устройстве обмениваться топологической информацией со своими соседями посредством эффективных протоколов, не перегружающих сеть широковещательным управляющим трафиком. Каждый управляющий агент должен поддерживать таблицу с локальной топологической информацией. Кроме того, должен предоставляться механизм, практически в реальном времени модифицирующий содержимое базы данных и обеспечивающий правильное отображение топологических изменений, вызванных установкой новых устройств либо реконфигурацией или отказом существующих узлов сети.

Для обеспечения защиты вычислительного процесса программными методами используется программная, информационная и временная избыточности.

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

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

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

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

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

функциональный контроль вычислений с помощью специальных контрольных операторов и нескольких версий программ;

функциональный контроль входной и выходной информации;

контроль входной информации по специальным признакам и контрольным суммам;

контроль выходной информации по квитанции от приемника - абонента системного интерфейса;

контрольный тест аппаратуры процессора;

контрольные тесты аппаратуры внешнего и внутреннего интерфейсов.

встроенные аппаратные средства контроля процессорных элементов и контроллеров системного интерфейса.

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

Часто для обнаружения состояния отказа используются тайм-ауты. В обычных системах исполнения предусматривается три различных вида обслуживания. Неблокирующее обслуживание всегда возвращает управление немедленно вместе с достоверным кодом возврата (успех или неудача), однако, в случае отсутствия данного вида обслуживания, обратившаяся к нему задача может попасть в бесконечный цикл опроса. Блокирующее обслуживание избегает такого опроса путём исключения вызывающей задачи из процесса диспетчеризации до тех пор, пока данный сервис не станет доступным. Если этого не произойдет, то задача рискует навсегда остаться заблокированной. Механизм же таймаутов позволяет возвращать управление задаче, даже в случае, если указанный сервис не предоставляется ей в течение определенного периода времени.

2.4 Концепция построения и работы системы с рангом отказоустойчивости N-1

В отказоустойчивых системах, построенных на N процессорных элементах, рангом отказоустойчивости будем называть максимальное количество отказов функциональных элементов (ПЭ), после возникновения которых система продолжает свое функционирование. Введем обозначение - N(m), которое означает, что система содержит N узлов (ПЭ) и «держит» m отказов, т.е. нормально функционируют до тех пор, пока остаются исправными (N-m) узлов. Следует заметить, что системы класса N(0) - относятся к самым быстродействующим системам, а N(N-1) - к самым отказоустойчивым.

В дальнейшем в работе будем рассматривать концепции построения и работы именно отказоустойчивых систем класса N(N-1). Данное ограничение означает, что в каждом ПЭ системы должен присутствовать весь набор функционального программного обеспечения, то есть каждый цикл ПЭ осуществляет полную обработку входных данных без участия других ПЭ.

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

1. ОС представляет собой совокупность информационно взаимосвязанных и согласовано функционирующих операционных систем каждого отдельного узла сети ВС.

Информационная взаимосвязанность операционных систем узлов между собой обеспечивается за счет передачи каждой ОС всем остальным следующей информации:

результатов «голосования» (сравнения) поступающей в данный ПЭ функциональной информации;

результатов оценки поступившей от других ОС узлов;

«результатов голосования» (т.е. «вывод» данного ПЭ о состоянии других ПЭ).

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

2. Внутренняя структура распределенной ОСРВ представляет собой иерархию уровней в которой каждый уровень использует функциональные возможности предыдущего. Добавление или удаление модулей позволяет создавать системы различных конфигураций. Кроме того, данный принцип построения ОСРВ позволяет осуществлять ее расширение путем добавления новых модулей, а расширение с минимальными изменениями подразумевает открытость системы.

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

4. ОС должна обладать свойством масштабируемости, что в узком смысле означает обеспечение ее настраиваемости на поддержку функционирования сетевых ВС различной размерности N (для реальных систем в пределах 3 N 10). Причем правая граница изменения N (Nmax = 10) выбрана из практических соображений построения ВС с высокой степенью связности узлов сети при использовании конкретных процессорных модулей количеством линков (L) не более шести (L6). При L=6 семиузловая сеть является полносвязанной и по мере увеличения N степень связности узлов сети уменьшается.

5. Времени для выполнения всех необходимых действий должно хватать с запасом 20-30% с учетом производительности аппаратной платформы.

С учетом этого факта (достаточности ресурса производительности) диспетчеризация вычислений сводится к поддержке следующих процедур:

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

полная обработка функциональной задачи в пределах одного цикла;

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

разделение цикла работы системы на следующие периоды: ввод данных, решение ФЗ, обмен функциональными данными (ФД), обмен результатами голосования ФД, обмен предварительными выводами о состоянии системы, принятие консолидированного решения (КР) о состоянии системы, реконфигурация системы при обнаружении в рамках КР отказа части системы.

В дальнейшем этот перечень требований к ОСРВ будет продолжен и детализирован.

Рассмотрим общую концепцию работы такой системы. После получения результатов расчета на очередном цикле, система должна получить информацию о своем состоянии, для чего осуществляется обмен результатами с остальными ПЭ системы. При этом следует отметить, что обмен результатами счета со всеми узлами ВС в некоторой мере избыточен, так как для выявления некорректного результата достаточно двух верных (в предположении об ординарности потока отказов). Таким образом, протокол голосования может быть построен так, что результаты счета отдельного ПЭ в ВС троируются, т.е. могут не присутствовать в некоторых узлах системы.

Во время сравнения ПЭ делает вывод о нормальном или неправильном функционировании доступной ей подсистемы и выявляет ее причину. Результатами сравнения ПЭ обменивается со всеми узлами системы, и они принимают консолидированное решение об отказе того или иного элемента или делают заключение о нормальной работе системы.

В случае обнаружения отказа, на выход выдаются результаты, признанные верными при голосовании. Отказавшему элементу предоставляется возможность «исправиться» в течение следующих трех циклов. При этом сбойному ПЭ передается контекст верно функционирующей задачи. Тройная попытка самоустранить сбой этого узла, должна практически исключать возможность отключения работоспособного ресурса системы. Если сбои в этом элементе повторились, система считает элемент отказавшим, после чего производится подключение к работе резервного ПЭ (если он предусмотрен изначальной топологией сети) с передачей текущего контекста функциональных задач. При отказе связей передача данных производится через транзитные связи. Если элемент утратил все свои связи (линки), то он изолируется на логическом или, если это возможно - на физическом уровне (отключение питания).

В настоящее время существуют различные ОСРВ, призванные решать задачи организации вычислений в системах РВ. Однако ни одна из них не удовлетворяет поставленным требованиям в полной мере. Поэтому встает вопрос о необходимости расширения существующих ОСРВ или разработки новой ОС, удовлетворяющей им. Поскольку создание ОС с удобными средствами создания и отладки прикладного программного обеспечения - длительный и трудоемкий процесс, единственным выходом является доработка существующих ОС.

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

дополнение ОС высокоуровневыми функциями обмена. Используемые в большинстве ОС стандартные средства обмена данными, определенные стандартом POSIX (каналы, сигналы, разделяемая память, семафоры), имеют ограниченные возможности при взаимодействии процессов, не имеющих родственных связей. Организация межпроцессного взаимодействия с помощью механизма сокетов неудобна из-за необходимости привязки к конкретной сетевой информации (IP- адрес узла, номер порта приложения) и своей ориентированностью на модель клиент-сервер.

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

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

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

Основная информация о функционировании операционной системы на данном ПЭ размещена в системных таблицах.

Граф информационной связности процессорных элементов задаётся в виде модифицированной матрицы связности. Отличие от стандартной матрицы связности заключается в том, что в рамках одной строки, описывающей связность данного ПЭ с другими, используется число «-1» в случае, если этот процессорный элемент не связан с ПЭ, задаваемом столбцом, и номер канала связи (линка) по которому осуществляется эта связность в противном случае, причем нумерацию линков для удобства можно начинать c m+1 узла, то есть для узла m связь с узлом m+1 будет осуществляться линком с наименьшим номером.

Таблица 2.1. Пример таблицы связности для полносвязной сети ПЭ

№/№	1	2	3	4	…	N
1	-1	0	1	2	…	N-2
2	N-2	-1	0	1	…	N-3
3	N-3	N-2	-1	1	…	N-4
4	N-4	N-3	N-2	-1	…	N-5
…	…	…	…	…	…	…
N	0	1	2	3	…	-1

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

Приведем пример таблиц рассылки. Для наглядности возьмем сеть из четырех ПЭ, представленную на рисунке 2.1.

Рис. 2.1. Пример неполносвязной сети

Цифры в окружностях - номера процессорных элементов, вне - номера линков (физических каналов связи). Таким образом таблица связности имеет вид (таблица 2.2).

Таблица 2.2 Таблица связности для примера на рисунке 2.1

№/№	1	2	3	4
1	-1	0	-1	1
2	1	-1	0	-1
3	1	-1	-1	0
4	0	-1	1	-1

Таблицы рассылки для каждого ПЭ могут иметь вид (см. Таблицу 2.3, 2.4, 2.5, 2.6).

...