Синхронизация задач

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

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

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

Модель «поставщик-потребитель» - самая простая и наиболее часто встречающаяся модель задач, конкурирующих за общий ресурс. Задача-«поставщик» способна выполнять операции: 1) «произвести»; 2) «передать». Задача-«потребитель» способна выполнять операции: 1) «принять»; 2) «употребить». Передача данных осуществляется через буфер, который является критическим ресурсом, причем:

• запрещен одновременный доступ к буферу со стороны разных задач;

• запрещена попытка чтения из пустого буфера;

• запрещена попытка записи в заполненный буфер.

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

Рис. 8. Алгоритм с блокирующим флагом

Доказано, что это решение некорректно для случая, когда параллельно работающие задачи выполняются с разными скоростями. Удовлетворительное решение проблемы синхронизации конкурирующих задач с использованием флагов занятости выглядит следующим образом («алгоритм Деккера-Холта», см. рис. 9).

Рис.9. Алгоритм Деккера-Холта

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

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

1. Операция «оградить» («lock»):

• S:=S-1;

• если S> 0, то текущая задача продолжает работу, иначе встает в конец

очереди ожидания.

2. Операция «освободить» («unlock»):

• если S<=0, то запускается первая в очереди задача;

• S:=S+1;

• первая в очереди задача продолжает работу.

Для обеспечения невозможности одновременного доступа достаточно всего одного семафора S1: операция «оградить» используется как «открывающая скобка» перед критической секцией, а операция «освободить» используется как «закрывающая скобка» после критической секции. Для невозможности чтения из пустого буфера и записи в заполненный буфер используются еще два семафора – S2 и S3 (см. рис. 10).

Рис.10. Решение задачи «поставщик-потребитель» с использованием семафоров

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

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

Итак, сформулируем расширенные требования к операционным системам с точки зрения пригодности для использования в АСУ и СРВ:

1) масштабируемость;

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

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

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

5) предсказуемость поведения (особенно, во временной области);

6) соответствие стандартам прежде всего, стандарту POSIX, определяющему интерфейсы доступа прикладных программ к ядру ОС);

7) открытость и документированность.

Примерами операционных систем, удовлетворяющих этим требованиям, являются OS-9/9000, QNX (см. рис. 3.11), WxWorks, OS Lynx. Благодаря хорошей масштабируемости, эти ОС работают и на «больших» ЭВМ и на промышленных контроллерах.

Рис. 11. Внешний вид рабочего стола QNX Neutrino

Операционные системы семейства MS Windows не удовлетворяют почти ни одному из этих требований, но достаточно широко используются для построения систем мягкого реального времени на базе промышленных ЭВМ – благодаря своим развитым графическим средствам. Существуют решения, позволяющие модифицировать MS Windows таким образом, чтобы часть перечисленных требований были удовлетворены (например, пакет RTX фирмы VenturCom, модифицирующий менеджер задач Windows). Также имеются разработки самой фирмы Microsoft: Windows Embedded, обладающие свойствами масштабируемости и конфигурируемости.

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