Параллельными называются процессы, у которых интервалы времени выполнения перекрываются за счет использования разных ресурсов одной и той же вычислительной системы или за счет перераспределения одного и того же набора ресурсов. Процессы, работающие в большинстве современных ОС, являются слабо связанными. Это означает, что за исключением достаточно редких моментов явной связи процессы выполняются независимо друг от друга. Поскольку параллельные процессы разделяют ресурсы вычислительной системы, задачи управления параллельным выполнением есть задачи управления ресурсами. Методы решения этих задач составляют широкий спектр от самых консервативных (требующих значительного снижения уровня мультипрограммирования), до самых либеральных (допускающих параллельное выполнение большого числа процессов).
Основной задачей управления параллельным выполнением является задача взаимного исключения: два процесса не могут выполнять одновременный доступ к разделяемым ресурсам.
В некоторых случаях возникает необходимость в приостановке выполнения процесса до наступления некоторого внешнего по отношению к нему события - такая задача называется задачей синхронизации. Если рассматривать события как ресурсы (потребляемые), то задача синхронизации является частным случаем задачи взаимного исключения. Как частный случай, она допускает частные решения.
Ниже рассматриваются средства, которые предоставляются для решения этих задач практически всеми современными ОС.
Критические секции
Критической секцией называется такой участок кода процесса, во время выполнения которого процесс не может быть прерван. Участок кода, на котором процесс осуществляет доступ к совместно используемому ресурсу, берется в «скобки критической секции». На время прохождения процесса через критическую секцию все остальные процессы блокируются, что снижает уровень мультипрограммирования в системе. Поэтому это средство широко применяются только для потоков - параллельно выполняющихся частей одного и того же процесса: они все принадлежат одному процессу - одному пользователю и разделяют почти все ресурсы этого процесса. Блокировка затрагивает только другие потоки того же процесса и не затрагивает другие процессы и их потоки.
Виртуальные прерывания или сигналы
Для того, чтобы выдавать синхронизирующий сигнал из одного процесса в другой может использоваться виртуальное прерывание. ОС может предоставлять в распоряжение процессов системный вызов посылки виртуального прерывания от одного процесса к другому. Когда процессу посылается сигнал, выполнение процесса-получателя прерывается и управление передается на процедуру - обработчик этого сигнала в составе процесса. Процесс должен предварительно установить адрес обработчика при помощи специального системного вызова, в котором указывается адрес обработчика, тип сигнала и реакция на сигнал (передать управление на обработчик, игнорировать, установить реакцию по умолчанию). По умолчанию реакция на сигнал, обработка которого не установлена – завершение процесса-получателя.
В ОС определены допустимые типы сигналов. Сигналы могут генерироваться системой автоматически в следующих случаях:
· завершение или другое изменение статуса процесса-потомка;
· программные ошибки (прерывания-ловушки);
· ошибки в выполнении системных вызовов или неправильные обращения к системным вызовам;
· терминальные воздействия (например, нажатие клавиши "Внимание" или Ctrl+Break);
· при необходимости завершения процесса (системный вызов kill);
· сигнал от таймера;
· и т.д.
Большинство допустимых сигналов генерируется в аварийных или исключительных случаях. Однако резервируются и несколько типов сигналов, которыми процессы обмениваются друг с другом и интерпретируют их по взаимной договоренности.
Общие области памяти
Два и более процессов могут использовать одну и ту же физическую область памяти. Наиболее просто это достигается в тех моделях памяти, которые обеспечивают динамическую трансляцию адресов. Напомним, что каждый процесс имеет собственную таблицу сегментов или страниц, в которой содержится помимо прочего базовый адрес сегмента/страницы в физической памяти. Для разделяемой области памяти создается по элементу в таблице для каждого процесса, ее использующего. Поскольку для каждого процесса разделяемый сегмент описывается своим дескриптором, права доступа к сегменту могут быть установлены различными для разных процессов.
Разделяемые сегменты памяти, однако, порождают ряд проблем как для программистов, так и для ОС. Проблемы программистов - взаимное исключение процессов при доступе к общей памяти. Программисты могут дифференцировать права доступа для процессов или организовать взаимное исключение, используя семафоры (см. ниже). Проблемы ОС - организация свопинга. Очевидно, что вероятность вытеснения разделяемого сегмента или страницы должна быть тем меньше, чем больше процессов разделяют этот сегмент/страницу.
Семафоры
Семафоры являются базовым средством для обеспечения взаимодействия между процессами и наличествуют во всех многозадачных ОС явно (в составе API) или неявно (как средства, реализующие другие формы взаимодействия).
Семафор является целочисленной переменной, которая в простейшем случае (двоичный семафор) может принимать значения 0 или 1. Над семафорами определены 2 операции:
V-операция есть операция с одним операндом, который должен быть семафором. Выполнение операции состоит в увеличении значения на 1, это действие должно быть атомарным.
P-операция есть операция с одним операндом, который должен быть семафором. Выполнение операции состоит в уменьшении значения аргумента на 1, если только это действие не приведет к отрицательному значению операнда. Выполнение P-операции, т.е., принятие решение о том, что момент является подходящим для уменьшения аргумента, и последующее его уменьшение должно быть атомарным.
Атомарность P-операции и является потенциальной задержкой: если процесс пытается выполнить P-операцию над семафором, значение которого в данный момент нулевое, данная P-операция не может завершиться пока другой процесс не выполнит V-операцию над этим семафором. Несколько процессов могут начать одновременно P-операцию над одним и тем же семафором. Тогда при установке семафора в 1 только одна из P-операций завершится.
Защита разделяемых ресурсов теперь выглядит следующим образом. Каждый ресурс защищается своим семафором, значение которого может быть 1 - свободен или 0 - занят. Процесс, выполняющий доступ к ресурсу, инициирует P-операцию. Если ресурс занят - процесс задерживается в своей P-операции до освобождения ресурса. Когда ресурс освобождается, P-операция процесса завершается и процесс занимает ресурс. При освобождении ресурса процесс выполняет V-операцию
Для решения задачи взаимного исключения достаточно двоичных семафоров. Семафор, который может принимать неотрицательные значения, большие 1, называется общим семафором. Такой семафор может быть очень удобен, например, при управлении не единичным ресурсом, а классом ресурсов. Начальное значение семафора устанавливается равным числу единиц ресурса в классе. Каждое выделение единицы ресурса процессу сопровождается P-операцией, уменьшающей значение семафора. Семафор, таким образом, играет роль счетчика ресурсов. Когда этот счетчик достигнет нулевого значения, процесс, выдавший следующий запрос на ресурс, будет заблокирован в своей P-операции. Освобождение ресурса сопровождается V-операцией, которая разблокирует процесс, ожидающий ресурс или наращивает счетчик ресурсов.
Общие семафоры могут быть использованы и для простого решения задачи синхронизации. В этом случае семафор связывается с каким-либо событием и имеет начальное значение 0. (Событие может рассматриваться как ресурс, и до наступления события этот ресурс недоступен). Процесс, ожидающий события, выполняет P-операцию и блокируется до установки семафора в 1. Процесс, сигнализирующий о событии, выполняет над семафором V-операцию.
Каналы-трубопроводы
Для процесса канал практически аналогичен файлу. Специальные системные вызовы используются для создания канала и получения доступа к каналу, а для работы с каналом используются те же вызовы read и write, что и для файлов, и закрытие канала выполняется вызовом close. Канал, однако, представляет собой не внешние данные, а область памяти, доступ к которой осуществляется по дисциплине FIFO - первый вошел – первый вышел. Для канала выделяется память в системной области, что может ограничивать емкость канала. В связи с этим процесс, обращающийся к каналу, может блокироваться: при попытке чтения из пустого канала и при попытке записи в переполненный канал.
Наиболее часто используются неименованные каналы, как средство связи между родителем и потомком. Операция создания неименованного канала возвращает два файловых манипулятора: для чтения и для записи. Процесс-предок передает эти манипуляторы процессу-потомку. Если связь между предком и потомком однонаправленная, то каждый из них закрывает канал по одному из манипуляторов.
Именованные каналы ориентированы, прежде всего, на взаимодействие процессов в сетевой среде. Такой канал двунаправленный, то есть, к нему возможны обращения и для чтения, и для записи. Данные в канале могут передаваться как потоком байт, так и сообщениями. В последнем случае каждое сообщение снабжается заголовком, в котором указывается его длина. К одному концу канала постоянно подключен процесс, его создавший - владелец или сервер, к другому концу могут подключаться различные процессы-клиенты, таким образом, обмен данными по именованному каналу между процессами, ни один из которых не является владельцем канала, невозможен. По логике использования именованные каналы ближе к очередям (см. ниже).
Очереди сообщений
Очереди воплощают модель взаимодействия процессов "много отправителей - один получатель". Эту модель часто называют почтовым ящиком из-за сходства с таковым, висящим на дверях каждой квартиры. Процесс-получатель является владельцем очереди, он создает очередь, а остальные процессы получают к ней доступ, "открывая" ее. Очередь обычно имеет внешнее имя. Передача данных в очереди происходит всегда сообщениями, причем каждое сообщение имеет заголовок и тело. Заголовок всегда имеет фиксированный для данной системы формат. В него обязательно входит длина сообщения, а другая информация зависит от спецификаций конкретной системы: это может быть приоритет сообщения, тип сообщения, идентификатор процесса-отправителя и т.п. Тело сообщения интерпретируется по правилам, устанавливаемым самими процессами – отправителем и получателем. Заголовок и тело представляют собой существенно разные структуры данных и располагаются в разных местах в памяти. Собственно очередь (чаще всего - линейный список) ОС составляет из заголовков сообщений. В элементы очереди включаются указатели на тела сообщений, располагающиеся в памяти системы или процессов.
Как правило, возможности процесса-получателя сообщений не ограничиваются чтением по дисциплине FIFO, ему предоставляется более богатый выбор дисциплин: LIFO, по приоритету, по типам, по идентификаторам отправителя и т.п. В распоряжении владельца имеются также средства определения размера очереди, а возможно, и просмотра очереди - неразрушающего чтения из нее. В распоряжении процесса-отправителя имеется только вызов посылки сообщения в очередь.
Очереди реализуют асинхронный механизм взаимодействия: процесс, отправивший сообщение, продолжает свое выполнение, не заботясь о судьбе посланного сообщения. Если ему для продолжения выполнения необходим ответ на сообщение, он ожидает ответа в своем почтовом ящике. Очереди, таким образом, являются наиболее гибким и универсальным средством взаимодействия, и в некоторых системах они являются единственным средством взаимодействия между процессами - как пользовательскими, так и системными.
