Взаимодействие и синхронизация процессов и потоков

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

Способы взаимодействия процессов (потоков) можно классифицировать по степени осведомленности одного процесса о существовании другого [10].

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

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

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

Методы взаимоисключений

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

1. Задача должна быть решена чисто программным способом на обычной машине, не имеющей специальных команд взаимоисключения. При этом предполагается, что основные инструкции языка программирования (такие примитивные инструкции, как load, store, test) являются атомарными операциями.
2. Не должно существовать никаких предположений об относительных скоростях выполняющихся процессов или числе процессоров, на которых они исполняются.
3. Если процесс Pi исполняется в своем критическом участке, то не существует никаких других процессов, которые исполняются в своих соответствующих критических секциях. Это условие получило название условия взаимоисключения (mutual exclusion).
4. Процессы, которые находятся вне своих критических участков и не собираются входить в них, не могут препятствовать другим процессам входить в их собственные критические участки. Если нет процессов в критических секциях и имеются процессы, желающие войти в них, то только те процессы, которые не исполняются в remainder section, должны принимать решение о том, какой процесс войдет в свою критическую секцию. Такое решение не должно приниматься бесконечно долго. Это условие получило название условия прогресса (progress).
5. Hе должно возникать бесконечного ожидания для входа процесса в свой критический участок. От того момента, когда процесс запросил разрешение на вход в критическую секцию, и до того момента, когда он это разрешение получил, другие процессы могут пройти через свои критические участки лишь ограниченное число раз. Это условие получило название условия ограниченного ожидания (bound waiting).

Семафоры и мониторы

Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году. Семафор представляет собой целую переменную, принимающую неотрицательные значения, доступ любого процесса к которой, за исключением момента ее инициализации, может осуществляться только через две атомарные операции: P (от датского слова proberen – проверять) и V (от verhogen – увеличивать).

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

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

Взаимоблокировки (тупики)

Коффман и другие исследователи доказали, что для возникновения тупиковой ситуации должны выполняться четыре условия [37].

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

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

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

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

Синхронизирующие объекты ОС

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

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

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

Мьютекс (mutex – сокращение от mutual exclusion – взаимное исключение) – упрощенный семафор, не способный считать; он может управлять лишь взаимным исключением доступа к совместно используемым ресурсам или кодам. Реализация мьютекса полезна в случае потоков, действующих только в пространстве пользователя.

Объект "событие" обычно используется не для доступа к данным, а для того, чтобы оповестить другие потоки о том, что некоторые действия завершены.

Другим средством взаимодействия процессов является канал (труба) – псевдофайл, который может использоваться для связи двух процессов. Когда процесс А хочет отправить данные процессу В, он пишет их канал, как если бы это был выходной файл. Процесс В читает данные из канала, как если бы он был входным файлом. Подобное средство взаимодействия используется в операционной системе UNIX.

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

Сокеты (ОС Windows 2000) подобны каналам с тем отличием, что они при нормальном использовании соединяют процессы на разных компьютерах. Например, один процесс пишет в сокет, а другой на удаленной машине читает из него. В принципе, сокеты можно использовать для соединения процессов на одной машине, но это связано с большими накладными расходами.

Вызов удаленной процедуры (Remote Procedure Call, RPC) представляет собой способ, которым процесс А просит процесс В вызвать процедуру в адресном пространстве процесса В от имени процесса А и вернуть результат процессу А.