Распределенные вычисления и параллелизм во встроенных вычислительных системах

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

Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский университет "Московский институт электронной техники"

Кафедра Вычислительной техники

Реферат

по дисциплине: "Микроконтроллеры и встраиваемые системы"

на тему: "Распределенные вычисления и параллелизм во встроенных вычислительных системах"

Выполнил:

Студент 1 курса, гр. ВТ-12

Хисамов В.Т.

Проверил:

Тельминов О.А.



Введение

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

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



1. Данные, поток данных, информация, процесс

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

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

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

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

распределения ресурсов ЦП на несколько потребителей;

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

упрощение алгоритмов, обслуживающих несколько устройств (объектов) одновременно.

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

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

процесс или поток операционной системы;

работа какой-либо программы;

проектирование;

жизнедеятельность организма.

Потоковая модель

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

В рамках нотации потоковых диаграмм DFD (Data Flow Diagram) и CFD (Control Flow Diagram) процессы изображают кружком. В DFD процессы взаимодействуют посредством передачи данных (сплошные стрелки), а в CFD - посредством передачи управления (пунктирные стрелки). Стрелки показывают направление и способ передачи данных или управления (синхронный или асинхронный). Очень часто при проектировании встраиваемых систем смешивают DFD и CFD в рамках одного рисунка.

Диаграмма потоков управления (CFD, Control Flow Diagram) - разновидность потоковой модели, передающей в своей семантике только аспект управления процессами.

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

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

общая память (хранилище данных). Используется в диаграммах потоков данных Йордона и в стратегии проектирования систем реального времени Пирбхая и Хатли;

очереди (сообщения, поток данных). Используется в сетях процессов Кана.

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

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

2. История развития

Потоковые модели вычислений получили толчок в развитии в начале 60-х годов 20 века. На данном этапе развития вычислительной техники разработчики столкнулись с новой для себя проблемой - созданием сложных, распределенных цифровых систем. Появление насущной необходимости в одновременной обработке нескольких (двух и более) потоков данных в рамках одной вычислительной системы привело к тому, что старые подходы к синтезу и анализу систем не давали существенных результатов и проекты стали слишком сложными для понимания и реализации. В 1962 году для описания распределенных систем были придуманы сети Петри. В 1963 г. Естрином и Турном (Estrin and Turn) были предложены первые потоковые модели. Карп и Миллер (Karp and Miller) предложили в 1966 году графы без переходов. Формализация и расширение модели Эстрина была произведена Родригесом в 1969 г. Чемберлен (Chamberlain) предложил потоковый язык в 1971 г. В 1974 Каном (Kahn) были предложены сети процессов с бесконечными очередями. В этом же году Денисом (Dennis) создана потоковая модель с буферами на один элемент. Арвинд и Гостелов (Arvind and Gostelow), а также независимо Гард и Ватсон (Gurd and Watson) предложили потоковую модель с тегированными элементами. В 1975 году Йордон и Константайн (Yourdon and Constantine) предложили методику структурного проектирования программного обеспечения с декомпозицией системы на процессы и потоки данных.

3. Применение потоковых моделей на практике

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

В этой модели есть три процесса:

контроллер последовательного канала UART;

обработчик прерывания;

пользовательский процесс.

Информация, полученная от UART, записывается процессом "обработчик прерываний" в очередь RFIFO. Пользовательский процесс может забрать байт из FIFO тогда, когда у него для этого будет возможность (т.е. очередь не будет пуста).

После записи байт в WFIFO пользовательский процесс может заниматься своими делами. Обработчик прерывания заберет байт из WFIFO тогда, когда буфер передатчика UART опустеет (при этом обработчик будет вызван). Как мы видим, не все аспекты работы потоковой модели драйвера последовательного канала для MCS51 описываются с помощью потоковой модели. Непонятно, когда происходит то или иное событие и что приводит к запуску того или иного процесса.



4. Проблемы реализации потоковых моделей

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

критическая секция;

гонки;

взаимное исключение;

блокировка процессов.

5. Модель вычислений Кана

Рисунок 9. DFD модель драйвера последовательного канала

Process Network (PN), сеть процессов, сеть потоков данных - модель вычислений, в которой система представляется в виде ориентированного графа, вершины которого представляют собой процессы (вычисления), а дуги - упорядоченные последовательности элементов данных. Граф обычно имеет иерархичную структуру, так что вершина одного графа сама по себе является другим ориентированным графом.

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

Модель вычислений с потоками данных (Dataow Process Networks) была предложена Каном в 1974 году для описания программных систем обработки потоков данных, отличающихся параллелизмом и независимостью отдельных ее этапов. В дальнейшем, эта модель была развита и получила распространение в области систем потоковой обработки данных (реализация аудио- и видеоприложений, обработки изображений и сигналов).

Были предложены многочисленные варианты и ограничения модели, такие как Synchronous Dataflow, Structured Dataflow, Well-behaved dataflow, Boolean Dataflow, Multidimensional SDF, Integer Dataflow, Heterogeneous Dataflow и т.д., дающие те или иные дополнительные полезные свойства вычислительного процесса.

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

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

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

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

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

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

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

Перечислим свойства очередей для данной модели:

очереди являются однопотоковыми;

очереди являются однонаправленными;

чтение токена из очереди всегда приводит к его удалению из очереди;

глубина очередей равна бесконечности.

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

нельзя проверять наличие данных в очереди;

только один процесс может записывать данные в очередь;

только один процесс может считывать данные из очереди;

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

Достоинства модели: детерминизм. Недостатки: Невозможность статического планирования.

Реализация потоковой модели в ОС РВ

Операционная система реального времени - это средство распределения и выделения ресурсов информационно-управляющей системы. Рассмотрим несколько определений термина "ресурсы".

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

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

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

удешевление элементной базы, в том числе оперативной памяти, FLASH, микропроцессоров, микроконтроллеров и т.д.;

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

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

6. Обобщенная модель ОС РВ

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

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

время процессора (процессоров);

память различных запоминающих устройств;

сервисы устройств ввода-вывода;

сервисы сети.

Классификация ОС РВ

По наличию в ОС РВ инструментальных средств для разработки различают два варианта:

исполнительская ОС РВ;

инструментальная ОС РВ.

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

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

Основополагающие компоненты ОС РВ

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

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

переключатель задач;

планировщик;

средства IPC.

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



7. Ядро ОС РВ

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

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

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

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

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

При использовании монолитного ядра (monolithic kernel) вся система является единой программой, в которой можно использовать общие структуры данных и организовывать взаимодействие путем простых вызовов процедур [1].

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

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

В своей книге "Just for fun" Линус Торвальс так отзывается о особенностях микроядра. "Теоретически необходимость микроядра обосновывается следующим образом. Операционные системы сложны. Для их упрощения применяется модульный подход. Вся соль микроядра в том, чтобы оставить у ядра, которое является основой основ, как можно меньше функций. Его главная задача - обмен информацией. А все возможности компьютера реализуются в виде сервисов, которые обеспечивают коммуникационные каналы микроядра. Предполагается, что вы разбиваете проблемы на такие мелкие части, что вся сложность пропадает.

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

Это самое главное возражение против микроядра. Простота, обеспечиваемая микроядром, является мнимой."

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

8. Обзор компонентов ядра ОС РВ

Переключатель задач ОС РВ

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

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

Причин переключения всего две: время (time triggered) или наличие события (event triggered). Первый вариант переключения осуществляется по специально созданному расписанию. Второй позволяет вызывать задачи как ответ на возникающее событие.

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

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

В контроллер прерываний приходит запрос на прерывание.

Контроллер прерываний прекращает выполнение текущей последовательности команд. На стеке сохраняется адрес следующей, еще не исполненной команды.

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

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

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

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

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

Таймер переполняется и выставляет запрос на прерывание.

Контроллер прерываний прерывает работу текущей программы.

Адрес следующей невыполненной команды и содержимое регистров сохраняется в стеке.

Переключатель задач запоминает указатель стека в контексте i-го процесса.

Далее, переключатель задач выбирает из массива значение указателя стека для процесса i+1 и устанавливает его.

Выполняется команда возврата из прерывания. Мы попали в другой процесс.

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

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

Приведенный пример переключателя задач принадлежит FreeRTOS версии 5.0.3 и взят из следующего каталога исходных текстов: FreeRTOS\Source\portable\SDCC\Cygnal

// ------------------------------------------------------------

// Переключатель задач FreeRTOS

// (порт для ядра MCS51, компилятор SDCC)

// ------------------------------------------------------------

void vTimer2ISR( void ) interrupt 5 _naked

portSAVE_CONTEXT(); // Сохранение контекста в стеке (push regs)

portCOPY_STACK_TO_XRAM(); // Копирование стека во внешнее ОЗУ

vTaskIncrementTick(); // Инкремент системных часов

vTaskSwitchContext(); // Выбор очередной задачи из списка

portCLEAR_INTERRUPT_FLAG(); // Корректное завершение прерывания,сброс флагов

portCOPY_XRAM_TO_STACK(); // Перенос контекста из внешнего ОЗУ в стек

portRESTORE_CONTEXT(); // Восстановление контекста // (pop regs)

Функция переключателя задач vTimer2ISR реализована как обработчик прерывания от таймера. Исходный текст функции в полном виде можно посмотреть в файле port.c. В файле task.h можно посмотреть описания системных вызовов.

Реализация планирования задач в ОС РВ

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

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

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

В ОС РВ планировщик не является монопольным распределителем ресурсов. Кроме планировщика, к вопросам управления ресурсом процессорного времени (процессами) относятся:

средства IPC;

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

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

9. Межпроцессное взаимодействие

Межпроцессное взаимодействие, IPC (Inter-process communication) - набор механизмов для взаимодействия между процессами, работающих в рамках потоковой модели вычислений.

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

Механизмы обмена данными предназначены только для передачи данных от одного процесса к другому. Управления состоянием процесса в таких каналах нет. Для примера можно рассмотреть сети процессов Кана.

1. Каналы без блокировки.

2. Очереди (FIFO), потоковый обмен данными, сокеты.

3. Пакетная пересылка, почтовые ящики (mail box).

4. Общая память.

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

Семафоры.

Мониторы.

Критические секции.

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

Каналы c блокировкой.

Сигналы.

Взаимное исключение

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

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

2. Переключатель процессов может прервать процесс на любой команде.

3. Процесс 1 проверил флаг критической секции. Флаг свободен.

4. Процесс 1 начал модифицировать флаг. Процесс 1 может считать, что он модифицировал флаг критической секции. На самом деле его прервал процесс 2.

5. Процесс 2 изменяет флаг критической секции и начинает работать с данными.

6. Процесс 1 прерывает процесс 2. Он уже проверил флаг и считает, что он свободен. Процесс 1 модифицирует флаг и начинает работать с критическими данными. Возникает конфликт.

7. Для получения атомарности, используют два основных метода: реализация неделимых операций TEST_AND_SET и CLEAR_TEST_AND_SET (реализация двоичного семафора Дейкстры на уровне системы команд ЦП).

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

Взаимное исключение относится к синхронизации конкуренции.

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

арбитр системной шины;

мьютекс для организации IPC между процессорами NIOS в среде Quartus.

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

Методы реализации взаимного исключения, классификация

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

внешние;

внутренние (пользовательские).

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

Первый вариант управления обычно реализуют в виде планировщика, второй - в виде монитора.

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

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

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

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

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

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

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

Функции входа и выхода их критической секции делаются поэтапными (в критической секции используется больше одной переменной, используется активное ожидание):

алгоритм Деккера;

алгоритм Петерсона;

алгоритм пекарня;

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

организация критической секции за счет запрета и разрешения прерываний (переключения процессов);

семафоры Дейкстры.

Алгоритм Петерсона - программная реализация механизма взаимного исключения без запрещения прерываний. Алгоритм Петерсона имеет смысл в системах на базе модели вычислений Фон-Неймана. Алгоритм Петерсона предложен в 1981 году Гарри Петерсоном из университета Рочестер (США). В основу алгоритма Петерсона лег алгоритм Деккера.

Алгоритм имеет следующие ограничения.

Алгоритм рассчитан только на 2 процесса (от этого ограничения свободен алгоритм пекарня (Bakery algorithm)).

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

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

Алгоритм работает на использовании двух переменных: у каждого процесса есть собственная переменная flag[i] и общая переменная turn. Все переменные хранятся в общей для обоих процессов памяти. В переменной flag запоминается факт захвата ресурса, в переменной turn - номер захватившего ресурс процесса.

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

flag[0] = 0

flag[1] = 0

turn = 0

turn = 1 turn = 0

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

void mut_excl(int me /* 0 or 1 */)

static int loser;

static int interested[2] = {0, 0};

int other; /* local variable */

other = 1 - me;

interested[me] = 1;

loser = me;

while (loser == me && interested[other])

/* critical section */

interested[me] = 0;

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

Алгоритм имеет следующие ограничения.

Алгоритм рассчитан только на 2 процесса (от этого ограничения свободен алгоритм пекарня (Bakery algorithm)).

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

Принцип работы аналогичен используемому в алгоритме Петерсона.

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

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

f0 := false

f1 := false

turn := 0 // or 1

Алгоритм пекарня - программная реализация механизма взаимного исключения без запрещения прерываний. Алгоритм пекарня имеет смысл в системах на базе модели вычислений Фон-Неймана. В отличии от алгоритма Деккера и Петерсона отсутствует ограничение на число процессов.

Изобретен Лесли Лампортом (Leslie Lamport). Приоритет процессов задается случайным образом, алгоритм плохо предсказуем и практически не применим для решения задач реального времени. Кроме того, при ожидании ресурса процессы не снимаются с очереди на обслуживание и впустую тратят процессорное время (активное ожидание).

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

// Определение и начальная инициализация глобальных переменных

// Переменные доступны всем процессам

Entering: array [1..N] of bool = {false};

Number: array [1..N] of integer = {0};

// ==============================

// Вход в критическую секцию

// i - номер процесса

// ==============================

lock(integer i)

Entering[i] = true;

Number[i] = 1 + max(Number[1], ..., Number[N]);

Entering[i] = false;

for (j = 1; j <= N; j++)

// Ждем

while (Entering[j]);

// Ждем

// while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i)));

// ==============================

// Выход из критической секции

// i - номер процесса

// ==============================

unlock(integer i)

Number[i] = 0;

// ==============================

// Пример использования

// i - номер процесса

// ==============================

Process_example(integer i)

while (true)

lock(i);

// Критическая секция

unlock(i);

// Выход из критической секции

10. Критическая секция

Критическая секция (Critical section) - это часть программы, в работу которой не может вмешаться другой процесс. Понятие "критическая секция" имеет смысл в тех системах, где возможно прерывание какого либо действия. Как правило, критические секции используются в системах, сделанных на базе модели вычислений Фон-Неймана и Process Network. Другими словами, критические секции используются при программировании классических микроконтроллеров и микропроцессоров, при использовании ОС РВ или прерываний.

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

В ОС РВ к процессам, использующим взаимное исключение, предъявляются следующие требования:

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

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



11. Семафор

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

взаимная блокировка;

утечка семафоров;

проблема синхронизации процедур семафоров.

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

Рассмотрим пример взаимной блокировки. Пусть имеются 2 процесса A и B, которым перед началом работы предоставлены ресурсы P1 и P2, соответственно. В какой-то момент времени процессу A понадобился P2, а процессу B - P1, но они их не получат, т.к. удерживаются предыдущими 97 процессами.

Предотвращение взаимной блокировки.

1. Прежде чем процесс начнет свою работу, ему должны быть предоставлены все требуемые ресурсы.

2. В том случае, если во время работы ему понадобился дополнительный ресурс, ему необходимо возвратить все ранее выделенные ресурсы ОС и затем запросить все требуемые ресурсы с этим дополнительным ресурсом.

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

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

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

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

В процессе инициализации в семафор записывается начальное значение.

s = init_value;

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

Функция P(s):

if( s == 0)

Заблокировать_текущий_процесс();

else

s--;

Функция V(s):

if( s == 0)

разблокировать_один_из_процессов();

else

s++;

В сетях Ethernet, имеющих способ доступа CSMA/CD, семафором является сама шина. Этот семафор может хранить только один бит информации, так как шина либо занята, либо нет. Таким образом, можно сказать, что в Ethernet для разделения ресурса шины используется бинарный семафор или мьютекс.

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

программный системный вычислительный кан

Список литературы

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

2. Микропроцессоры. Т3. Средства отладки, лабораторный практикум и задачник. под ред. Преснухина.

3. Hatley D.J., Pirbhai I.A. Strategies for Real-Time System Specification. N.Y. Dorset House Publishing, 1988.

4. Фредерик Брукс. Мифический человеко-месяц, или Как создаются программные системы. - СПб.: Символ-Плюс, 2007. - 304 с.

5. Лукичев А.Н. Денотативно-объектная модель вычислений для встроенных систем: дис... канд. техн. Наук: 05.13.12. - Санкт-Петербург, 2008

Размещено на Allbest.ru

...