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

систем реального времени.
2. Базовые концепции построения операционных систем реального времени.
3.

Монолитная архитектура.
4. Модульная архитектура на основе микроядра.
5. Объектная архитектура на основе объектов – микроядер.

отличий систем реального времени от систем общего назначения - четкое

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

Большинство современных ведущих операционных систем реального времени поддерживают целый спектр аппаратных архитектур, на которых работают системы исполнения (Intel, Motorola, RISC,MIPS, PowerPC, и другие). Это объясняется тем, что набор аппаратных средств является частью комплекса реального времени и аппаратура должна быть также адекватна решаемой задаче. Поэтому ведущие операционные системы реального времени перекрывают целый ряд наиболее популярных архитектур, чтобы удовлетворить самым разным требованиям по части аппаратуры. Систему исполнения операционных системах реального времени и компьютер, на котором она исполняется называют "целевой" (target) системой. Система разработки – это набор средств, обеспечивающих создание и отладку приложения реального времени.
Системы разработки работают, как правило, в популярных и распространенных ОС, таких, как UNIX. Кроме того, многие операционные системы реального времени имеют и так называемые резидентные средства разработки, исполняющиеся в среде самой операционной системы реального времени - особенно это относится к операционным системам реального времени класса "ядра".

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

параметр, как время реакции системы на прерывание (interrupt latency). Если

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

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

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

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

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

Размеры системы. Для систем реального времени важным параметром является размер системы исполнения, а именно суммарный размер минимально необходимого для работы приложения системного набора (ядро, системные модули, драйверы и т. д.). С течением времени значение этого параметра уменьшается, тем не менее, он остается важным, и производители систем реального времени стремятся к тому, чтобы размеры ядра и обслуживающих модулей системы были невелики.
Возможность исполнения системы из ПЗУ (ROM). Это свойство операционных систем реального времени - одно из базовых. Оно позволяет создавать компактные встроенные СРВ повышенной надёжности, с ограниченным энергопотреблением, без внешних накопителей.
Механизмы систем реального времени. Процесс проектирования конкретной системы реального времени начинается с тщательного изучения объекта. Разработчики проекта исследуют объект, изучают возможные события на нем, определяют критические сроки реакции системы на каждое событие и разрабатывают алгоритмы обработки этих событий. Затем следует процесс проектирования и разработки программных приложений.
У разработчиков СРВ введено понятие «идеальная операционная система реального времени», в которой приложения реального времени разрабатываются на языке событий объекта. Такая система имеет свое название, хотя и существует только в теории. Называется она: "система, управляемая критическими сроками". Разработка приложений реального времени в этой системе сводится к описанию возможных событий на объекте. В каждом описателе события указывается два параметра:
• временной интервал - критическое время обслуживания данного события;
• адрес подпрограммы его обработки.

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

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

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

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

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

К базовым концепциям относятся: Способы построения ядра системы - монолитное ядро или микроядерный подход.

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

а затем связать их в единый объектный файл с помощью

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

Однако даже такие монолитные системы могут иметь некоторую структуру. При обращении к системным вызовам, поддерживаемым операционной системой, параметры помещаются в строго определенные места - регистры или стек, после чего выполняется специальная команда прерывания, известная как вызов ядра или вызов супервизора. Эта команда переключает машину из режима пользователя в режим ядра и передает управление операционной системе. Затем операционная система проверяет параметры вызова, чтобы определить, какой системный вызов должен быть выполнен. После этого операционная система обращается к таблице как к массиву с номером системного вызова в качестве индекса. В k-м элементе таблицы содержится ссылка на процедуру обработки системного вызова. Такая организация операционной системы предполагает следующую структуру:1. Главная программа, которая вызывает требуемую служебную процедуру. 2. Набор служебных процедур, выполняющих системные вызовы. 3. Набор утилит, обслуживающих служебные процедуры. В этой модели для каждого системного вызова имеется одна служебная процедура. Утилиты выполняют функции, которые нужны нескольким служебным процедурам. Деление процедур на три уровня показано на рис.

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

Происходит разрыв парадигмы программирования: в едином работающем комплексе (приложение +

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

Возникает идея строить саму СРВ, используя объектно-ориентированный подход. При этом: как приложение, так и операционная система полностью объектно-ориентированны и используют все преимущества этого подхода; приложение и ОСРВ могут быть полностью интегрированы, поскольку используют один объектно-ориентированный язык программирования; обеспечивается согласование интерфейсов ОСРВ и приложения; приложение может «моделировать» ОСРВ для своих потребностей, заказывая нужные ему объекты; единый комплекс (приложение + ОСРВ) является модульным и легко модернизируемым. Идея реализована в ОСРВ SoftKernel, целиком написанной на C++. ОСРВ с монолитной архитектурой можно представить в виде:
прикладного уровня: состоящего из работающих прикладных процессов;
системного уровня: состоящего из монолитного ядра операционной системы, в котором можно выделить следующие части:
а) интерфейс между приложениями и ядром (API);
b) собственно ядро системы;
c)интерфейс между ядром и оборудованием (драйверы устройств). API в таких системах играет двойную роль:
управляет взаимодействием прикладных процессов и системы;
обеспечивает непрерывность выполнения кода системы (отсутствие переключения задач во время исполнения кода системы).

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

основном, за счет написания значительных частей системы на ассемблере. Недостатки:

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

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

SoftKernel) API отсутствует вообще. Взаимодействие между компонентами системы (микроядрами) и

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

Микроядра по своим характеристикам напоминают структуры, используемые в других операционных системах, однако есть и свои различия.
Микроядра и модули. Многие ОС поддерживают динамическую загрузку компонент системы, называемых модулями. Но модули не поддерживают объектно-ориентированный подход ввиду того, что микроядро является фактически представителем некоторого класса. Далее, обмен информацией с модулями происходит посредством системных вызовов, что достаточно дорого.
Микроядра и драйверы. Многие ОС поддерживают возможность расширения посредством драйверов, которые однако часто должны быть статически связаны с ядром (образовывать с ним связанный загрузочный образ еще до загрузки) и работать в привилегированном режиме. Как и модули, они не поддерживают объектно-ориентированный подход и доступны приложениям только посредством системных вызовов.
Микроядра и DLL (Dynamically Linked Libraries, динамически связываемые библиотеки). Многие системы оформляют библиотеки, из которых берутся функции при динамическом связывании, в виде специальных модулей, называемых DLL. DLL обеспечивает разделение своего кода и данных для всех работающих приложений, в то время, как для микроядер можно управлять доступом для каждого конкретного приложения. DLL не поддерживает объектно-ориентированный подход, код DLL не является позиционно-независимым, и потому не может быть записан в ПЗУ.

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

реального времени.
2. Критические секции.
3. Семафоры.
4. События.

синхронизацией (synchronization). Синхронизация процессов является основной функцией многозадачных операционных систем

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

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

связано ли это взаимодействие с разделением ресурсов или с обменом

данными. При совместном использовании аппаратных ресурсов синхронизация также совершенно необходима. Когда, например, активному потоку требуется доступ к последовательному порту, а с этим портом в монопольном режиме работает другой поток, находящийся в состоянии ожидания, то операционная система (ОС) приостанавливает активный поток и не активизирует его до тех пор, пока нужный ему порт не освободится. Часто нужна также синхронизация с событиями, внешними по отношению к вычислительной системе, например реакции на нажатие комбинации клавиш Сtгl+С.
Ежесекундно в системе происходят сотни событий, связанных с распределением и освобождением ресурсов, и операционная система должна иметь надежные и производительные средства, которые бы позволяли ей синхронизировать потоки с происходящими в системе событиями.
Для синхронизации потоков прикладных программ программист может использовать как собственные средства и приемы синхронизации, так и средства операционной системы. Например, два потока одного прикладного процесса могут координировать свою работу с помощью доступной для них обоих глобальной логической переменной, которая устанавливается в единицу при осуществлении некоторого события, например выработки одним потоком данных, нужных для продолжения работы другого. Однако во многих случаях более эффективными или даже единственно возможными являются средства синхронизации, предоставляемые операционной системой в форме системных вызовов. Так, потоки, принадлежащие разным процессам, не имеют возможности вмешиваться каким-либо образом в работу друг друга. Без посредничества операционной системы они не могут приостановить друг друга или оповестить о произошедшем событии. Средства синхронизации используются операционной системой не только для синхронизации прикладных процессов, но и для ее внутренних нужд.
Обычно разработчики операционных систем предоставляют в распоряжение прикладных и системных программистов широкий спектр средств синхронизации. Эти средства могут образовывать иерархию, когда на основе более простых средств строятся более сложные, быть функционально специализированными. Например, средства для синхронизации потоков одного процесса, средства для синхронизации потоков разных процессов при обмене данными и т. д. Часто функциональные возможности разных системных вызовов синхронизации перекрываются, так что для решения одной задачи программист может воспользоваться несколькими вызовами в зависимости от своих личных предпочтений.

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

Критическая секция - это часть программы, результат выполнения которой может

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

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

глобальные блокирующие переменные. С этими переменными, к которым все потоки

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

Каждому набору критических данных ставится в соответствие двоичная переменная, которой поток присваивает значение 0, когда он входит в критическую секцию, и значение 1, когда он ее покидает.
Блокирующие переменные могут использоваться не только при доступе к разделяемым данным, но и при доступе к разделяемым ресурсам любого вида.
Если все потоки написаны с учетом вышеописанных соглашений, то взаимное исключение гарантируется. При этом потоки могут быть прерваны операционной системой в любой момент и в любом месте, в том числе в критической секции.
Однако следует заметить, что одно ограничение на прерывания все же имеется. Нельзя прерывать поток между выполнением операций проверки и установки блокирующей переменной. Поясним это. Пусть в результате проверки переменной поток определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой поток занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому потоку, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом, был нарушен принцип взаимного исключения, что потенциально может привести к нежелательным последствиям. Во избежание таких ситуаций в системе команд многих компьютеров предусмотрена единая, неделимая команда анализа и присвоения значения логической переменной (например, команды ВТС, ВТК и ВТ5 процессора Реntium). При отсутствии такой команды в процессоре соответствующие действия должны реализовываться специальными системными примитивами (примитив - базовая функция ОС), которые бы запрещали прерывания на протяжении всей операции проверки и установки.
Реализация взаимного исключения описанным выше способом имеет существенный недостаток: в течение времени, когда один поток находится в критической секции, другой поток, которому требуется тот же ресурс, получив доступ к процессору, будет непрерывно опрашивать блокирующую переменную, бесполезно тратя выделяемое ему процессорное время, которое могло бы быть использовано для выполнения какого-нибудь другого потока. Для устранения этого недостатка во многих ОС предусматриваются специальные системные вызовы для работы с критическими секциями.

больше нуля, то есть просто счетчик. Обычно семафор инициализируется в

начале программы 0 или 1. Семафоры, которые могут принимать лишь значения 0 и 1, называются двоичными. Над семафорами определены две операции - signal и wait. Операция signal увеличивает значение семафора на 1, а вызвавший ее процесс продолжает свою работу. Операция wait приводит к различным результатам, в зависимости от текущего значения семафора. Если его значение больше 0, оно уменьшается на 1, и процесс, вызвавший операцию wait, может продолжаться. Если семафор имеет значение 0, то процесс, вызвавший операцию wait, приостанавливается (ставится в очередь к семафору) до тех пор, пока значение соответствующего семафора не увеличится другим процессом с помощью операции signal. Только после этого операция wait приостановленного процесса завершается (с уменьшением значения семафора), а приостановленный процесс продолжается.
Важно, что проверка и уменьшение значения семафора в операции wait выполняются за один шаг. Операционная система не может прервать выполнение операции wait между проверкой и уменьшением значения. Операция wait для семафора имеет такое же функциональное значение, что и инструкция test_and_set.
Если несколько процессов ждут одного и того же семафора, то после выполнения операции signal только один из них может продолжить свое развитие. В зависимости от реализации процессы могут ждать в очереди, упорядоченной либо по принципу FIFO (Firstln, FirstOut - первым вошел, первым вышел), либо в соответствии с приоритетами, или выбираться случайным образом.
Названия управляющей структуры "семафор" и операций signal и wait имеют очевидное мнемоническое значение. В литературе вместо signal и wait применяются и другие названия с тем же самым функциональным смыслом.
С помощью семафоров проблема защиты ресурсов решается следующим образом:

Семафоры (semaphore) - это основной метод синхронизации. Он, в сущности, является наиболее общим методом синхронизации процессов.

true do (* бесконечный цикл *)
begin (* процесс А *)
wait(P1);
(*

защищенный ресурс *)
signal(P1);
…
end; (* процесс А *)
while true do (* бесконечный цикл *)
begin (* процесс В *)
wait(Pl);
(* защищенный ресурс *)
signal(Pl);
…
end; (* процесс В *)
coend;
end. (* sem_example *)

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

wait(Pl) wait(P2)
wait(P2) wait(Pl)
… …
(* защищенный ресурс *) (* защищенный ресурс *)
… …
signal(Pl) signal(P2)
signal(P2) signal(Pl)

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

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

Process "Чтение данных" Process "Обработка данных"
while true do while true do
begin begin
(* чтение новых данных *) wait(data_available);
signal(data_available); (*обработка данных *)
end; end;

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

должны работать с ними только при выполнении некоторых условий, необязательно

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

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

begin
wait until condition;
modify data; end

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

var mutex: semaphore; change: event;
begin
while not condition do await(change); wait(mutex);
(* обработка общих переменных *) signal(mutex); cause(change);
end;

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

операционных систем.
4. Сигналы.

к защите ресурсов основан на взаимном исключении (mutual exclusion). Никакой

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

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

program protect_example (* защита ресурса *)
var fl: boolean;
begin
f1 : = true;
cobegin
while true do (* бесконечный цикл *)
begin (* процесс А *)
repeat until f1 = true;
(* защищенный ресурс *)
f1 := false;
…
end; (* процесс А *)
while true do (* бесконечный цикл *)
begin (* процесс В *) repeat until f 1 = false;
(* защищенный ресурс *)
f1: = true;
…
end; (* процесс В *)
coend;
end (* protect_example *)

Корректная защита ресурсов предполагает следующее:
1. В любой момент времени доступ к защищенному ресурсу имеет только один процесс.
2. Процессы остаются взаимно независимыми. Остановка одного из процессов не должна препятствовать продолжению других.
Сформулированные требования соответствуют двум характеристикам -безопасности и живучести. Безопасность (safety) означает, что доступ к защищенному ресурсу в любой момент времени возможен только со стороны одного из процессов. Живучесть (liveness) означает, что программа когда-нибудь обязательно будет выполнена, иными словами, что она не остановится, и не будет ждать бесконечно. Безопасность - это статическое свойство, а живучесть - динамическое. Безопасности можно добиться за счет частичного или полного отказа от параллельного исполнения процессов. В действительности наиболее надежными являются строго последовательные программы, поскольку в этом случае вообще невозможен параллельный доступ к ресурсу из различных частей программы.
Распространенный метод управления доступом к ресурсам - применение переменных защиты. Простейший метод защиты основан на одной двоичной переменной f1. Эта переменная изменяется обоими процессами таким образом, что один из них имеет доступ к защищенному ресурсу, когда f1 = true, а другой - когда f1 = false.

ее значения и перед доступом к защищенному ресурсу т.е. все

процессы должны иметь следующий вид

В этом случае процессы не связаны, и условие живучести выполнено, но решение не является корректным. Если прерывание для переключения процесса останавливает процесс А после контроля f1 = true, но перед присваиванием f1 = false, а процесс В выполняет аналогичную проверку f1, то оба процесса получают доступ к защищенному ресурсу, что противоречит требованию безопасности.

repeat until f1 = true;
f1 := false;
(* защищенный ресурс *)
f1 := true;
…

Использование для защиты ресурса только одной переменной приводит к необходимости ее защищать, поскольку она сама становится общим ресурсом. Чтобы обойти эту проблему, некоторые процессоры имеют команду test_and_set ("проверить_и_установить"), выполняющую проверку значения булевой переменной и ее переустановку в ходе одной операции, которую нельзя прервать. Смысл команды test_and_set в том, что на ее базе можно построить процедуры синхронизации и защиты ресурсов. Объединения в одной операции проверки переменной и ее модификации достаточно для обеспечения защиты. Команда test_and_set функционально эквивалентна циклу read-modify-write на шине VMEbus. В обоих случаях гарантируется неразрывность двух операций - чтения и записи. Если команда test_and_set отсутствует в используемом языке программирования или в наборе команд процессора, то ее можно смоделировать другими средствами при условии, что допустим запрет прерываний на короткое время. Реализация критических секций и взаимного исключения в распределенной системе сама по себе представляет проблему. Прямого эквивалента команды test_and_set нет , поскольку в этом случае имеется более одного процессора. В принципе, для каждого ресурса можно установить единого координатора. Любой процесс, желающий получить доступ к ресурсу, сначала запрашивает координатора, который дает разрешение только одному из запрашивающих процессов. Но это решение не является простым, как кажется. Единый координатор процессов - узкое место и при его отказе ресурс остается либо заблокированным, либо незащищенным. А если ресурс является просто переменной в памяти, то строить целый алгоритм для его защиты нерационально. Координатор сам является ресурсом, за доступ к которому будет происходить конкуренция, не говоря уже о том, что в распределенной системе для посылки запроса нужно еще получить и доступ к каналу связи.
Возможной альтернативой является использование маркера, который перемещается между процессами. При этом в критическую секцию может войти только владелец маркера. Здесь возникают те же проблемы, что и в сетях: в случае сбоя в процессе, являющемся владельцем маркера, должен существовать механизм регенерации маркера. Поэтому для защиты небольшого числа переменных в памяти этот метод может оказаться громоздким и трудно реализуемым.

приостановлены и ожидают каких-нибудь событий, которые могут быть инициированы только

другим ожидающим процессом, то все процессы окажутся в состоянии бесконечного ожидания. Такая ситуация называется тупиком (deadlock)

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

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

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

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

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

Для возникновения тупика должны выполниться одновременно несколько условий. Если хотя бы одно из них не выполнено, тупик не может возникнуть.

1. Взаимное исключение. Существуют системные ресурсы, к которым разрешен монопольный доступ.
2. Невытесняющее распределение ресурсов. Ресурс может быть освобожден только тем процессом, который его захватил, или, иначе говоря, ресурс не может быть освобожден извне захватившего его процесса.
3. Последовательный захват ресурсов. Процесс запрашивает ресурсы по одному, т. е. по мере необходимости.
4. Захват ресурсов в обратном порядке.

предусматривается оперативное снятие процесса с выполнения. Для этого пользователь может

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

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

Каналы.
4. Удаленный вызов процедур.
5. Сравнение методов синхронизации и обмена данными.

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

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

копируется в указанный почтовый ящик. Может случиться, что в почтовом

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

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

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

В некоторых системах поддерживаются дополнительные служебные функции, например счетчик сообщений в почтовом ящике или чтение сообщения без удаления его из ящика. Почтовые ящики размещаются в оперативной памяти или на диске и существуют лишь до выключения питания или перезагрузки. Если они физически расположены на диске, то считаются временными файлами, уничтожаемыми после выключения системы. Почтовые ящики не имеют имен подобно реальным файлам - при создании им присваиваются логические идентификаторы, которые используются процессами при обращении. Для создания почтового ящика операционная система определяет указатели на область памяти для операций чтения/записи и соответствующие переменные для защиты доступа. Основными методами реализации являются либо буфер, размер которого задается при создании ящика, либо связанный список, который, в принципе, не накладывает никаких ограничений на число сообщений в почтовом ящике. В наиболее распространенных реализациях процесс, посылающий сообщение, записывает его в почтовый ящик с помощью оператора, похожего на оператор записи в файл put_mailbox ( # 1, message)
Аналогично, для получения сообщения процесс считывает его из почтового ящика с помощью оператора вида get _mailbox (# 1, message)

каждая программа имеет стандартное устройство ввода (вход) и стандартное устройство

вывода (выход), клавиатуру и экран монитора - можно переопределить, например, с помощью файлов. Когда выход одной программы перенаправляется на вход другой, создается механизм, называемый каналом (в операционных системах для обозначения канала используется символ "|"). Каналы применяются в операционных системах UNIX, OS/9 и Windows NT в качестве средства связи между процессами (программами).
Каналы можно рассматривать как частный случай почтового ящика. Различие между ними заключается в организации потока данных - почтовые ящики работают с сообщениями, то есть данными, для которых известны формат и длина, а каналы принципиально ориентированы на неструктурированные потоки символов. В некоторых операционных системах, однако, возможно определить структуру передаваемых по каналу данных. Обычно процесс, выполняющий операцию чтения из канала, ждет, пока в нем не появятся данные. В настоящее время операционные системы включают методы, позволяющие избежать блокировки программы, если это нежелательно с точки зрения ее логики.
Операции над каналами эквивалентны чтению/записи физических файлов. Они включают функции, как определить, открыть, читать, записать, закрыть, удалить. Дополнительные операции могут устанавливать флаги режима доступа, определять размер буфера и т.д.
Благодаря тому, что ввод/вывод в файл и на физические устройства и вход/выход процессов трактуются одинаково, каналы являются естественным средством взаимодействия между процессами в системах "клиент-сервер". Механизм каналов в UNIX может в некоторых случаях зависеть от протокола TCP/IP, а в Windows NT каналы работают с любым транспортным протоколом. Следует иметь в виду, что внешне простой механизм каналов может требовать больших накладных расходов при реализации, особенно в сетевых системах.

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

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

данными и синхронизации в среде "клиент-сервер" является удаленный вызов процедур (Remote Procedure Call - RPC). Последний может рассматриваться как вызов подпрограммы, при котором операционная система отвечает за маршрутизацию и доставку вызова к узлу, где находится эта подпрограмма. Нотация обращения к процедуре не зависит от того, является ли она локальной или удаленной по отношению к вызывающей программе. Это существенно облегчает программирование.
В системе реального времени существенно, является RPC блокирующим или нет. Блокирующий RPC не возвращает управление вызывающему процессу, пока не закончит свою работу, например, пока не подготовит данные для ответа. Неблокирующие RPC возвращают управление вызывающей процедуре по истечении некоторого времени (time out) независимо от того, завершила ли работу вызываемая процедура; в любом случае вызывающая программа получает код, идентифицирующий результат выполнения вызова, - код возврата. Таким образом, неблокирующие RPC имеют важное значение, с точки зрения гарантии живучести системы.

в котором накапливаются сообщения нулевой длины, - операции signal и

wait эквивалентны операциям put и get почтового ящика, а текущее значение семафора эквивалентно числу помещенных в почтовый ящик сообщений. Аналогично можно организовать взаимное исключение и защиту ресурсов с помощью почтовых ящиков. В этом случае сообщение выполняет функцию "маркера". Процесс, получивший этот "маркер", приобретает право входить в критическую секцию или распоряжаться ресурсами системы. При выходе из секции или освобождении ресурса процесс помещает "маркер" в почтовый ящик. Следующий процесс читает из почтового ящика, получает "маркер" и может войти в критическую секцию.
Связь между разными подходами имеет практическое значение в том случае, если в системе применяется только один из них, а все остальные нужно строить на его основе. Современные ОС применяют все упомянутые методы. Если есть выбор между различными методами синхронизации и взаимодействия, следует использовать тот из них, который лучше решает конкретную проблему - результирующая программа будет понятнее и, возможно, быстрее работать. Кроме того, весьма важно оценить, насколько эффективно в имеющейся программной среде реализуются конкретные решения.
В распределенных системах всегда существует риск потерять сообщение в сети. Если сетевая система сконфигурирована так, что она контролирует правильность передачи сообщения, и имеются средства для повторной передачи утраченных сообщений, то прикладная программа не должна осуществлять дополнительные проверки. Обычно нижний уровень операционной системы и процедуры сетевого интерфейса передают на более высокий уровень код возврата, который прикладная программа должна проверить, чтобы убедиться, была ли попытка успешной или нет, и при необходимости повторить ее.
Если контроль не предусмотрен, например, используется служба IP без транспортного протокола TCP, то прикладная программа несет ответственность за проверку результата передачи. Эта операция сложнее, чем это кажется. Можно использовать сообщение, подтверждающее прием, но нет гарантии, что оно само, в свою очередь, не будет потеряно и отправитель не начнет новую передачу. Эта проблема не имеет общего решения - стратегии передачи сообщений должны в каждом случае рассматриваться индивидуально. Возможным решением является помечать и нумеровать каждое сообщение таким образом, чтобы отправитель и получатель могли следить за порядком передачи. Этот метод используется в некоторых типах коммуникационных протоколов.

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