Синхронизация задач
Архитектура ОСРВ. Классы ОСРВ
При появлении вычислительных устройств, программное обеспечение (ПО) для них создавалось на машинном коде. Каждая из программ была узко специализированной для работы на том устройстве, для которого она была разработана. Любые изменения в аппаратной конфигурации устройства требовали адаптации ПО. Постепенно пришло осознание того, что необходимо разработать универсальный подход к созданию ПО, в основу которого положен принцип изоляции (абстракции) ПО от аппаратных решений. Первым шагом в этом направлении стала реализация стандартного набора функций ввода/вывода в виде библиотек подпрограмм. Этот набор подпрограмм известен как BIOS. В дальнейшем возникла необходимость в наборе программ регламентирующих и стандартизирующих методы доступа к запоминающим устройствам (оперативная память, дисковые и прочие устройства долговременной памяти). Возникло понятие файла (абстрактный массив данных с уникальным дескриптором). Этот набор функций реализуют программы менеджера памяти и файловой системы. Помимо этого возникла необходимость в более гибкой подсистеме ввода/вывода, и были сделаны первые шаги к стандартизации интерфейса пользователя. Комплекс программ, состоящих из менеджера памяти, файловой системы, библиотек расширенного ввода/вывода получил название ОС. Затем этот комплекс программ был дополнен планировщиком.
Основу ОС составляет ядро, которое обеспечивает сервис пяти типов:
· синхронизация ресурсов;
· межзадачный обмен (это обеспечение передачи данных между программами внутри одной и той же системы и взаимодействие с другими системами через сеть);
· разделение данных;
· обработка запросов внешних устройств;
· обработка особых ситуаций, возникающих во время выполнения программы, которая должна быть синхронной, если ее возникновение предсказуемо, или асинхронной, если возникает непредсказуемо.
Первые ОС были сделаны в виде единого, монолитного комплекса и получили название – системы с монолитным ядром. Затем, для увеличения гибкости, стабильности, архитектура претерпела изменения; необходимый минимальный набор подпрограмм по-прежнему реализовывался в виде монолитного модуля – микроядра (как правило, включает в себя планировщик и менеджер памяти). Прочие функции реализовались в виде отдельных модулей и библиотек. Такая архитектура получила название – микроядерной.
Четкой границы между ядром (KERNEL) и ОС нет. Различают их по набору функциональных возможностей. Ядра предоставляют пользователю такие функции, как планирование, синхронизация задач, межзадачная коммуникация, управление памятью и т. д. ОС в дополнение имеют файловую систему, сетевую поддержку, интерфейс с оператором и другие средства высокого уровня. Они обеспечивают взаимодействие системы и управляющего/управляемого оборудования.
Для дальнейшего повышения защищенности и надежности систем разработана объектно-ориентированная архитектура системы.
Различия в этих подходах иллюстрируются рис. 1.5, 1.6, 1.7.
ОСРВ с монолитной архитектурой можно представить в виде:
· прикладного уровня, состоящего из работающих прикладных процессов;
· системного уровня, состоящего из монолитного ядра ОС, в котором можно выделить следующие части:
o интерфейс между приложениями и ядром (API);
o собственно ядро системы;
o интерфейс между ядром и оборудованием (драйверы устройств).
Рис. 1.5. ОСРВ с монолитной архитектурой
| 
|
| Рис. 1.6. ОСРВ на основе микроядра |
API в таких системах играет двойную роль:
1) управление взаимодействием прикладных процессов и системы;
2) обеспечение непрерывности выполнения кода системы (т.е. отсутствие переключения задач во время исполнения кода системы).
|
| Рис. 1.7. Объектно-ориентированная ОСРВ |
Преимуществом монолитной архитектуры является быстрота работы по сравнению с другими архитектурами. Это достигается за счет написания значительных частей системы на ассемблере.
Недостатки монолитной архитектуры:
1) системные вызовы, требующие переключения уровней привилегий (от пользовательской задачи к ядру), должны реализовывать API как прерывания или ловушки, что увеличивает время их работы;
2) ядро не может быть прервано пользовательской задачей (non-preemptable) и высокоприоритетная задача может не получить управление из-за работы низкоприоритетной;
3) сложность переноса на новую архитектуру процессора из-за значительных ассемблерных вставок;
4) негибкость и сложность развития: изменение части ядра системы требует его полной перекомпиляции.
Модульная архитектура (на основе микроядра) появилась как попытка убрать узкое место – API и облегчить модернизацию системы и перенос ее на новые процессоры. API в модульной архитектуре играет только одну роль: обеспечивает связь прикладных процессов и специального модуля – менеджера процессов. Однако теперь микроядро играет двойную роль:
1) управление взаимодействием частей системы (например, менеджеров процессов и файлов);
2) обеспечение непрерывности выполнения кода системы (т.е. отсутствие переключения задач во время исполнения микроядра).
Недостатки модульной архитектуры те же, что и у монолитной. Проблемы перешли с уровня API на уровень микроядра. Системный интерфейс не допускает переключения задач во время работы микроядра, только сократилось время пребывания в этом состоянии. API реализован на ассемблере, проблемы с переносимостью микроядра уменьшились (в связи с сокращением его размера), но остались.
Данные архитектуры относятся к классической архитектуре ОСРВ и используют традиционный процедурный подход к программированию. В силу преимуществ объектно-ориентированного подхода приложения создаются на его основе. Сочетание объекно-ориентированных приложений и процедурных ОС имеет ряд недостатков:
– в едином работающем комплексе (приложение + ОСРВ) разные компоненты используют разные подходы к разработке программного обеспечения;
– не используются все возможности объектно – ориентированного подхода;
– возникают некоторые потери производительности из-за разного типа интерфейсов в ОСРВ и приложений.
Объектная архитектура на основе объектов-микроядер. В этой архитектуре API отсутствует вообще. Взаимодействие между компонентами системы (микроядрами) и пользовательскими процессами осуществляется посредством обычного вызова функций, поскольку и система, и приложения написаны на одном языке (для ОСРВ SoftKernel это C++). Это обеспечивает максимальную скорость системных вызовов. Фактическое равноправие всех компонент системы обеспечивает возможность переключения задач в любое время, т.е. система полностью preemptible. Объектно-ориентированный подход обеспечивает модульность, безопасность, легкость модернизации и повторного использования кода.
Роль API играет компилятор и динамический редактор объектных связей (linker). При старте приложения динамический linker загружает нужные ему микроядра (т.е., в отличие от предыдущих систем, не все компоненты самой ОС должны быть загружены в оперативную память). Если микроядро уже загружено для другого приложения, оно повторно не загружается, а использует код и данные уже имеющегося ядра. Это позволяет уменьшить объем требуемой памяти.
Поскольку разные приложения разделяют одни микроядра, то они должны работать в одном адресном пространстве, а система не может использовать виртуальную память и тем самым работает быстрее (так как исключаются задержки на трансляцию виртуального адреса в физический). Поскольку все приложения и сами микроядра работают в одном адресном пространстве, то они загружаются в память, начиная с неизвестного на момент компиляции адреса, причем приложения и микроядра не должны зависеть от начального адреса (как по коду, так и по данным (последнее обеспечить значительно сложнее)). Это свойство автоматически обеспечивает возможность записи приложений и модулей в ПЗУ, с их последующим исполнением как в самом ПЗУ, так и оперативной памяти.
Микроядра по своим характеристикам напоминают структуры, используемые в других ОС. Однако есть и свои различия:
· Микроядра и модули. Многие ОС поддерживают динамическую загрузку компонент системы, называемых модулями, которые не поддерживают объектно-ориентированный подход. Обмен информацией с модулями происходит через системные вызовы, что дорого.
· Микроядра и драйверы. Многие ОС поддерживают возможность своего расширения посредством драйверов (специальных модулей служащих для поддержки оборудования). Драйверы статически связаны с ядром, образуя с ним связанный загрузочный образ еще до загрузки, и работают в привилегированном (суперпользовательском) режиме. Как модули они не поддерживают объектно-ориентированный подход и доступны приложению посредством системных вызовов.
· Микроядра и DLL. Многие системы оформляют библиотеки, из которых берутся функции при динамическом связывании, в виде специальных модулей, называемых DLL (Dynamically Linked Libraries – динамически связываемые библиотеки). DLL обеспечивает разделение своего кода и данных для всех работающих приложений, в то время как для микроядер можно управлять доступом для каждого конкретного приложения. DLL не поддерживает объектно-ориентированный подход, код DLL не является позиционно-независимым и не может быть записан в ПЗУ.
Системы реального времени можно разделить на 4 класса:
1. Исполнительные СРВ включает программы для программируемых микропроцессоров, встраиваемых в различные устройства, небольшие и написаны на языке низкого уровня типа ассемблера или PLM. Внутрисхемные эмуляторы пригодны для отладки, но высокоуровневые средства разработки и отладки программ не применимы. ОС обычно недоступна. Признаки систем этого типа – различные платформы для систем разработки и исполнения. Приложение реального времени разрабатывается на host – компьютере (компьютере системы разработки), затем компонуется с ядром и загружается в целевую систему для исполнения. Приложение реального времени – это одна задача, и параллелизм здесь достигается с помощью нитей (threads).
Системы данного типа обладают высокой скоростью и реактивностью, поскольку в системе имеются только потоки, требующие малого времени на переключение контекста. Этим свойством определяется и ряд недостатков: зависание всей системы при зависании потока, проблемы с динамической подгрузкой новых приложений. Системы разработки для продуктов этого класса традиционно дороги (до 20000 долл.).
Как наиболее яркого представителя здесь можно назвать ОС VxWorks – компактную СРВ с хорошими временами реакций.
2. Минимальное ядро системы реального времени предусматривает основные функции, а управление памятью и диспетчер часто недоступны. Ядро представляет собой набор программ, выполняющих типичные, необходимые для встроенных систем низкого уровня функции и минимальный сервис ввода/вывода. Прикладная программа разрабатывается в инструментальной среде, а выполняется на встроенных системах.
В этот класс входят системы с монолитным ядром, где и содержится реализация всех механизмов реального времени этих ОС. Системы этого класса модульны, хорошо структурированы, имеют развитый набор специфических механизмов реального времени, компактны и предсказуемы. Одна из особенностей систем этого класса – высокая степень масштабируемости. На базе этих ОС можно построить как компактные СРВ, так и большие системы серверного класса. Наиболее популярные системы этого класса: OS9, QNX.
3. Ядро системы реального времени и инструментальная среда обладает многими чертами ОС с полным сервисом. Разработка ведется в инструментальной среде, а исполнение – на целевых системах. Этот тип систем обеспечивает высокий уровень сервиса для разработчика прикладной программы и включает такие средства, как дистанционный символьный отладчик, протокол ошибок и другие средства CASE. Часто доступно параллельное выполнение программ.
4. ОС с полным сервисом применяют для любых приложений реального времени. Разработка и исполнение прикладных программ ведутся в рамках одной и той же системы. Область применения расширений реального времени – большие СРВ, где требуется визуализация, работа с базами данных, доступ в интернет и пр. К таким системам относится ОСРВ на основе UNIX и расширения Windows.
Хотя каждая задача в системе выполняет какую-либо отдельную функцию, часто возникает необходимость в согласовании (синхронизации) действий, выполняемых различными задачами. Механизм, обеспечивающий процесс синхронизации, называется ограничением доступа. При этом имеется два общих состояния, в которых может находиться задача. Во-первых, задача может выполняться (или быть готовой к выполнению, как только получит доступ к ресурсам процессора). Во-вторых, задача может быть блокирована. В этом случае ее выполнение приостановлено до тех пор, пока не освободится нужный ей ресурс или не произойдет определенное событие. Такая синхронизация необходима в следующих случаях:
1. Функции, выполняемые задачами, связаны друг с другом.
2. Необходимо упорядочить доступ нескольких задач к разделяемому ресурсу[2].
3. Необходима синхронизация задачи с внешними событиями, для чего используется механизм прерываний.
4. Необходима синхронизация задачи по времени, для чего используются специальные аппаратные средства – таймеры.
Рассмотрим все четыре случая более подробно.
Связные задачи. Межпроцессное взаимодействие – это тот или иной способ передачи информации из одного процесса в другой. Наиболее распространенными формами взаимодействия являются:
1. Разделяемая память – два или более процесса могут иметь доступ к одному и тому же блоку памяти. В системах с виртуальной памятью организация такого вида взаимодействия требует поддержки со стороны ОС, поскольку необходимо отобразить соответствующие блоки виртуальной памяти на один и тот же блок физической памяти.
2. Семафоры – это объекты синхронизации, задающие количество пользователей (задач, процессов), имеющих одновременный доступ к некоторому ресурсу.
3. Сигналы (signal) – это сообщения, доставляемые посредством ОС процессу. Процесс должен зарегистрировать обработчик этого сообщения у ОС, чтобы получить возможность реагировать на него. Часто ОС извещает процесс сигналом о наступлении какого-либо сбоя.
4. Почтовые ящики (mail box) – это очередь сообщений (обычно – тех или иных структур данных), которые помещаются в почтовый ящик процессами и/или ОС. Несколько процессов могут ждать поступления сообщения в почтовый ящик и активизироваться по поступлению сообщения. Требует поддержки со стороны ОС.
5. Событие (event) – это логический сигнал (оповещение), приходящий асинхронно по отношению к процессу со стороны ОС о той или иной форме межпроцессного взаимодействия, например, о принятии семафором нужного значения, наличии сигнала, о поступлении сообщения в почтовый ящик. Можно выделить:
· События, переводимые в несигнальное состояние автоматически (автосброс). Такое событие переключается в несигнальное состояние ОС, когда один из ожидающих его потоков завершится (wait-функция вернула управление потоку).
· События, переводимые в несигнальное состояние вручную. Такое событие, будучи установленным в сигнальное состояние, остается в нем пока не будет явно переключено вызовом функции ResetEvent (очистить). Причем «сигнальное состояние» соответствует значению 1 для переменной события, «несигнальное состояние» – 0. Так как события являются объектами синхронизации ядра, то перед использованием событие должно быть создано.
· Управление периодическим процессом с помощью событий.
6. Прокси (proxy) – это форма неблокирующего сообщения, когда посылающий процесс не нуждается в диалоге с получателем. Единственная функция прокси состоит в посылке фиксированного сообщения определенному процессу, который является владельцем прокси.
Взаимное согласование задач с помощью сообщений[3] является важнейшим принципов ОСРВ. Объем информации, передаваемой в сообщении, может меняться от одного бита до всей свободной емкости памяти системы. Компоненты ОС как и пользовательские задачи способны принимать и передавать сообщения. Сообщения бывают асинхронными и синхронными. В первом случае доставка сообщений задаче производится после того, как она в плановом порядке получит управление, а во втором случае циркуляция сообщений оказывает непосредственное влияние на планирование задач. Иногда сообщения передаются через буфер определенного размера (почтовый ящик). При этом новое сообщение затирает старое, даже если последнее не было обработано. Сообщение может содержать как сами данные, предназначенные для передачи, так и указатель на такие данные. При этом обмен производится с помощью разделяемых областей памяти, разделяемых файлов и т.п.
Общие ресурсы. Ресурс – это общий термин, описывающий физическое устройство или область памяти, которые могут одновременно использоваться только одной задачей. Ресурсы разделяют на:
· активные – способны изменить информацию (процессор);
· пассивные – способны хранить информацию;
· локальные – принадлежат одному процессу; время жизни совпадает с временем жизни процесса;
· разделяемые – используются несколькими процессами и существуют, пока есть хоть один процесс, который их использует;
· постоянные – используются посредством операций «захватить» и «освободить»;
· временные – используются посредством «создать» и «удалить».
Разделяемые ресурсы бывают:
· не критичные – используются одновременно несколькими процессами;
· критичные – используются одним процессом, и пока этот процесс не завершит работу с ресурсом, последний не доступен другим процессам (разделяемая память, доступная на запись).
По типу взаимодействия различают:
· сотрудничающие процессы:
процессы, разделяющие только коммуникационный канал, по которому один передает данные, а другой получает их;
процессы, осуществляющие взаимную синхронизацию: когда работает один, другой ждет окончания его работы.
· конкурирующие процессы:
использующие совместно разделяемый ресурс;
использующие критические секции;
использующие взаимные исключения.
Иногда может возникнуть ситуация, когда одна задача не вовремя прерывает другую, от которой зависит правильность выполнения исходной задачи (например, вытесняемая задача собирает информацию, которую использует вытесняющая задача). Упомянутые проблемы обусловлены времязависимыми ошибками (time dependent error), или гонками, и характерны для многозадачных ОС, применяющих алгоритмы планирования с вытеснением (кстати, системы с разделением времени также относятся к категории вытесняющих). Ошибки, обусловленные гонками: а) характерны для работы с любыми ресурсами, доступ к которым имеют несколько задач; б) происходят только в результате совпадения определенных условий, а потому с трудом обнаруживаются на этапе отладки.
Возможные пути решения этой проблемы:
· Не использовать алгоритм планирования задач с вытеснением, что не всегда приемлемо.
· Использовать специальный сервер ресурса, ответственный за упорядочивание доступа к ресурсу, а запрос на изменение значения глобальных данных посылается этому серверу в виде сообщения.
· Запретить прерывания на время доступа к разделяемым данным.
· Использовать для упорядочивание доступа к глобальным данным семафоры.
Синхронизация с внешними событиями. Применение аппарата прерываний является более эффективным методом взаимодействия с внешним миром, чем метод опроса. При этом можно проследить следующие тенденции:
· попытка обеспечить максимально быструю и детерминированную реакцию системы на внешнее событие;
· стремление добиться минимально возможных периодов времени, когда в системе запрещены прерывания;
· подпрограммы обработки прерываний выполняют минимальный объем функций за максимально короткое время. Это обусловлено несколькими причинами. Во-первых, не все ОСРВ обеспечивают возможность “вытеснения” во время обработки подпрограмм прерывания. Во-вторых, приоритеты аппаратных прерываний не всегда соответствуют приоритетам задач, с которыми они связаны. В-третьих, задержки с обработкой прерываний могут привести к потере данных.
Закончив необходимые действия, подпрограмма обработки прерываний генерирует сообщение для задачи, с которой это прерывание связано, и немедленно возвращает управление. Если это сообщение привело задачу в разряд готовых к исполнению, планировщик в зависимости от используемого алгоритма и приоритета задачи принимает решение о том, необходимо или нет немедленно передать управление получившей сообщение задаче.
Синхронизация по времени. В ОСРВ задается эталонный интервал (квант) времени (тик (Tick)), который используется в качестве базовой единицы измерения времени. Размерность этой единицы для разных ОСРВ может быть разной, как разными могут быть набор функций и механизмы взаимодействия с таймером. Функции по работе с таймером используют для приостановки выполнения задачи на какое-то время, для запуска задачи в определенное время, для относительной синхронизации нескольких задач по времени и т.п. Для точной синхронизации таймера вычислительной системы с астрономическим временем могут применяться специальные часы с подстройкой по радиосигналам точного времени или навигационные приемники GPS.