Способы взаимодействия процессов потоков

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

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

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

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

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

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

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

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

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

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

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

Простейшей разновидностью семафоров являются двоичные семафоры, которые могут принимать только 2 возможных значения – 0 и 1. Именно на двоичных семафорах построены такие важные системные объекты, как критические секции и мьютексы (mutex, сокращение от mutual exclusion, т.е. взаимное исключение). Общим у них является то, что они применяются для синхронизации доступа потоков к разделяемым данным (общим файлам, общим структурам данных), а отличаются они тем, что первые используются для потоков внутри одно процесса, а вторые – для разных процессов. Как следствие, реализация мьютексов со стороны системы требует существенно больших затрат. Для прикладного программиста использование этих объектов практически не отличается, приходится лишь использовать разные системные вызовы.

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

Когда выполнение кода потока доходит до системного вызова “Начало КС”, система отрабатывает этот вызов следующим образом:

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

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

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

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

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

При организации взаимодействия потоков есть одна весьма серьезная опасность: попадание двух или нескольких потоков в состояние взаимной блокировки или тупика (deadlock). Эту ситуацию можно показать на следующем примере.

Пусть в соответствии со своей внутренней логикой поток 1 должен начать работу сначала с файлом А, а потом (не завершив эту работу) – с файлом В. Пусть поток 2, наоборот, сначала начинает работу с файлом В, а потом – с файлом А. При этом возможна следующая последовательность действий:

поток 1 начал работу с файлом А и блокировал его, после чего поток 1 был прерван;
поток 2 начал свою работу с файлом В и блокировал его, после чего был прерван;
поток 1 возобновляет свою работу, запрашивает файл В, но тот занят потоком 2 и поэтому поток 1 переводится в состояние ожидания;
поток 2 возобновляет свою работу, запрашивает файл А, но тот занят потоком 1, и поэтому поток 2 тоже переводится в состояние ожидания.

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

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

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

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

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

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

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

Автор этого материала — я — Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML — то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

статьи IT, теория программирования, потоки, лекции по программированию, лекции

Источник

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

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

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

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

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

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

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

Влияние одного процесса на другой

Процессы не осведомлены друг о друге

Результат работы одного процесса не зависит от действий других.

Возможно влияние одного процесса на время работы другого

Процессы косвенно осведомлены о наличии друг друга

Сотрудничество с использованием разделения

Результат работы одного процесса может зависеть от информации, полученной от других.

Возможно влияние одного процесса на время работы другого

Процессы непосредственно осведомлены о наличии друг друга

Сотрудничество с использованием связи

Результат работы одного процесса зависит от информации, полученной от других процессов.

Возможно влияние одного процесса на время работы другого

Взаимоблокировки (расходуемые ресурсы)

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

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

В случае конкурирующих процессов (потоков) возможно возникновение трех проблем. Первая из них – необходимость взаимных исключений (mutual exclusion). Предположим, что два или большее количество процессов требуют доступ к одному неразделяемому ресурсу, как например принтер (рис. 5.12). О таком ресурсе будем говорить как о критическом ресурсе, а о части программы, которая его использует, – как о критическом разделе (critical section) программы. Крайне важно, чтобы в критической ситуации в любой момент могла находиться только одна программа. Например, во время печати файла требуется, чтобы отдельный процесс имел полный контроль над принтером, иначе на бумаге можно получить чередование строк двух файлов.

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

Осуществление взаимных исключений создает две дополнительные проблемы. Одна из них – взаимоблокировки (deadlock) или тупики. Рассмотрим, например, два процесса – P1 и P2, и два ресурса – R1 и R2. Предположим, что каждому процессу для выполнения части своих функций требуется доступ к общим ресурсам. Тогда возможно возникновение следующей ситуации: ОС выделяет ресурс R1 процессу Р2, а ресурс R2 – процессу Р1. В результате каждый процесс ожидает получения одного из двух ресурсов. При этом ни один из них не освобождает уже имеющийся ресурс, ожидая получения второго ресурса для выполнения функций, требующих наличие двух ресурсов. В результате процессы оказываются взаимно заблокированными.

Очень удобно моделировать условия возникновения тупиков, используя направленные графы [17] (предложено Holt, 1972). Графы имеют 2 вида узлов: процессы-кружочки и ресурсы-квадратики. Ребро, направленное от квадрата (ресурса) к кружку (процессу), означает, что ресурс был запрошен, получен и используется. В нашем примере это будет изображено так, как показано на рис. 5.13 а).

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

Существует еще одна проблема у конкурирующих процессов – голодание. Предположим, что имеется 3 процесса ( Р1, Р2, Р3 ), каждому из которых периодически требуется доступ к ресурсам R. Представим ситуацию, в которой Р1 обладает ресурсом, а Р2 и Р3 приостановлены в ожидании освобождения ресурса R. После выхода Р1 из критического раздела доступ к ресурсу будет получен одним из процессов Р2 или Р3.

Рис. 5.13. Тупиковая ситуация

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

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

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

Пусть имеются два процесса, представленные последовательностью неделимых (атомарных) операций:

P: a; b; c; и Q: d; e; f;

где a, b, c, d, e, f – атомарные операции.

При последовательном выполнении активностей мы получаем следующую последовательность атомарных действий:

Что произойдет при исполнении этих процессов псевдопараллельно, в режиме разделения времени? Процессы могут расслоиться на неделимые операции с различным их чередованием, то есть может произойти то, что на английском языке принято называть словом interleaving. Возможные варианты чередования:

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

P: x=2; y=x-1; Q: x=3; y=x+1

Что мы получим в результате их псевдопараллельного выполнения, если переменные x и y являются общими для процессов? Легко видеть, что возможны четыре разных набора значений для пары (x, y): (3, 4), (2, 1), (2, 3) и (3, 2). Будем говорить, что набор процессов детерминирован, если всякий раз при псевдопараллельном исполнении для одного и того же набора входных данных он дает одинаковые выходные данные. В противном случае он недетерминирован. Выше приведен пример недетерминированного набора программ. Понятно, что детерминированный набор активностей можно безбоязненно выполнять в режиме разделения времени. Для недетерминированного набора такое исполнение нежелательно.

Можно ли до получения результатов, заранее, определить, является ли набор активностей детерминированным или нет? Для этого существуют достаточные условия Бернстайна [17]. Изложим их применительно к программам с разделяемыми переменными.

Введем наборы входных и выходных переменных программы. Для каждой атомарной операции наборы входных и выходных переменных – это наборы переменных, которые атомарная операция считывает и записывает. Набор входных переменных программы R(P) ( R от слова read ) суть объединение наборов входных переменных для всех ее неделимых действий. Аналогично, набор выходных переменных программы W(P) ( W от слова write ) суть объединение наборов выходных переменных для всех ее неделимых действий. Например, для программы

P: x = u + v; y = x * w;

получаем R(P) = , W(P) = . Заметим, что переменная x присутствует как в R(P), так и в W(P).

Теперь сформулируем условия Бернстайна.

Если для двух данных процессов P и Q:

пересечение W(P) и W(Q) пусто,

пересечение W(P) с R(Q) пусто,

пересечение R(P) и W(Q) пусто,

тогда выполнение P и Q детерминировано.

Если эти условия не соблюдены, возможно, что параллельное выполнение P и Q детерминировано, но возможно, что и нет. Случай двух процессов естественным образом обобщается на их большее количество.

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

Про недетерминированный набор программ говорят, что он имеет race condition (состояние гонки, состояние состязания). В приведенном выше примере процессы состязаются за вычисление значений переменных x и y.

Задачу упорядоченного доступа к разделяемым данным (устранение race condition), в том случае, если нам не важна его очередность, можно решить, если обеспечить каждому процессу эксклюзивное право доступа к этим данным. Каждый процесс, обращающийся к разделяемым ресурсам, исключает для всех других процессов возможность одновременного с ним общения с этими ресурсами, если это может привести к недетерминированному поведению набора процессов. Такой прием называется взаимоисключением (mutual exclusion). Если очередность доступа к разделяемым ресурсам важна для получения правильных результатов, то одними взаимоисключениями уже не обойтись.

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

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

Источник