ЛЕКЦИЯ №6 Организация параллельных взаимодействующих процессов

1 Взаимодействие процессов

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

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

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

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

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

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

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

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

При отсутствии синхронизации возможны следующие проблемы:

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

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

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

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

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

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

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

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

В данном примере критической секцией потока A являются A₁, A₂, A₃, а потока B – B₁, B₂, B₃.

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

Более точно проблема формулируется так.

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

Относительно системы сделаны следующие предположения:

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

Критические секции не могут иметь связанных с ними приоритетов.

Относительные скорости процессов неизвестны.

Программа может останавливаться вне критической секции (КС).

Требования к критическим секциям:

– в любой момент времени только один процесс может находиться в своей критической секции;

– ни один процесс не должен находиться в своей критической секции бесконечно долго;

– ни один процесс не должен ждать бесконечно долго входа в свой критический интервал;

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

3. Способы реализации взаимного исключения

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

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

parbegin

P1: while true do

Begin CS1; program_1; end;

P2: while true do

Begin CS2; program_2; end;

...

Pn: while true do

Begin CSn; program_n; end;

parend

Здесь управляющая конструкция parbegin... parend используется для указания на то, что часть программы, заключенная между этими операторами, должна выполняться параллельно. Через идентификатор CS с номером обозначены критические секции каждого потока, program_1, program_2, …, program_n представляют собой те части потоков, которые не обращаются к общим данным и могут работать параллельно без каких бы то ни было ограничений.

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

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

Два потока, готовые войти в свои КС, не должны откладывать неопределенно долго решение вопроса о том, который из них войдет в свою КС первым.

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

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

Program Variant1;

Var turn: integer; {общая переменная}

Procedure process_1;

Begin

While true Do

Begin

While turn=2 Do; {активное ожидание}

CS1;

turn:=2;

program_1;

End;

End;

Procedure process_2;

Begin

While true Do

Begin

While turn=1 Do; {активное ожидание}

CS2;

turn:=1;

program_2;

End;

End;

Begin

turn:=1;

Parbegin

process_1; {процессы работают параллельно}

process_2;

Parend

End.

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

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

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

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

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

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

4. Семафоры и их применение

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

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

Пусть S – семафор. Операция V над семафором S записывается как V(S) и увеличивает переменную S на единицу одним неделимым действием, т.е. выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время операции V(S). Операция P над семафором S записывается как P(S) и уменьшает переменную S на единицу, если это возможно. Если было S=0, то уменьшение S невозможно и процесс, вызвавший P-операцию, ждет, пока значение S не увеличится. Проверка и уменьшение значения S также являются одним неделимым действием.

Рассмотрим вариант реализации семафорных примитивов:

P(S): S:=S-1;

If S<0 Then {остановить процесс и поместить его в очередь ожидания к семафору S}

V(S): If S<0 Then {поместить один из ожидающих процессов очереди семафора S в очередь готовности};

S:=S+1;

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

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

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

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

Семафорные операции дают простое решение проблемы КС. Пусть S – семафор, используемый для защиты КС. Тогда примитив P(S) представляет собой вход взаимоисключения, а примитив V(S) – выход взаимоисключения. Рассмотрим пример программы, обеспечивающей взаимоисключение при помощи семафора.

Семафор имеет начальное значение, равное 1. Если первый и второй процессы попытаются одновременно выполнить примитив P(S), то это удастся успешно сделать только одному из них. Предположим, что это сделал первый процесс. Он закрыл семафор, т.е. значение семафора стало S = 0, после чего данный процесс вошел в свой критический интервал. Второй процесс при этом оказывается заблокированным на семафоре – при попытке выполнения операции P(S) он "засыпает". Взаимное исключение гарантировано, т.к. только один процесс может уменьшить значение S до нуля с помощью P-операции. Очевидным образом это решение распространяется на случай n процессов – тогда все другие процессы, пытающиеся войти в свои КС при S = 0, будут вынуждены ожидать по P(S). Взаимное блокирование невозможно, т.к. одновременные попытки войти в свои КС при S = 0 должны, по определению, преобразовываться в последовательные P-операции. После выхода из своей КС процесс выполняет V-операцию, тем самым открывая семафор и предоставляя возможность "пробуждения" блокированным процессам. Тогда один из блокированных процессов переводится в очередь готовности.

При реализации возможно одно из двух решений в отношении процессов, которые переводятся из очереди ожидания в очередь готовности при выполнении примитива V(S):

– процесс при его активизации вновь пытается выполнить примитив P, считая предыдущую попытку неуспешной;

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

При первом способе возможна следующая последовательность событий. Предположим, что начальное значение семафора было равно единице. Пусть процесс2 в какой-то момент времени выполнит операцию P(S), семафор S станет равным нулю, а процесс2 войдет в свою КС. Далее процесс1 тоже попытается выполнить операцию P(S) и "заснет" на семафоре, поскольку значение семафора теперь станет равным –1. После выхода из КС процесс2 выполнит V(S), при этом значение семафора станет равным 0, а процесс1 переведется в очередь готовности. После активизации процесс1 снова выполнит P(S) и опять "уснет", то же самое произойдет с процессом2, если он пожелает войти в свою КС. "Пробуждать" процессы станет некому. Таким образом, возможно возникновение тупиковой ситуации.

При втором способе реализации тупиковой ситуации не будет. Действительно, при аналогичном варианте развития событий отличие начнется с момента активизации процесса1. Он сразу войдет в свою КС. При этом никакой другой процесс не попадет в критическую секцию, т.к. семафор остается закрытым (его значение равно 0). После окончания работы процесса1 в КС в результате выполнения им операции V(S) значение семафора установится в единицу, если другие процессы не совершали попыток попасть в КС. Если процесс2, а также и другие процессы в случае их большего количества, во время работы процесса1 в КС также выполнят примитив P(S), то после выполнения процессом1 V-операции семафор установится в 0. Следовательно, он будет закрыт для всех процессов кроме того, который успел выполнить P-операцию, т.е. сделал заявку на КС. Таким образом, тупик не возникнет, а взаимоисключение гарантировано.

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

5. Мьютексы

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

Для того, чтобы мьютекс был доступен потокам разных процессов, при создании ему необходимо присвоить имя, которое потом должно быть передано "по наследству" другим задачам для использования при их взаимодействии. Для этого существуют специальные системные вызовы (CreateMutex), в которых указывается начальное значение мьютекса, его имя и, возможно, атрибуты защиты. Если начальное значение мьютекса равно true, то считается, что задача, создавшая этот объект, будет сразу им владеть. При начальном значении false мьютекс не принадлежит ни одной из задач и его состояние можно изменить только специальным обращением.

Для работы с мьютексом имеется ряд функций: создание (CreateMutex), открытие (OpenMutex), ожидание событий (WaitForSingleObject и WaitForMultipleObjects), освобождение (ReleaseMutex). Конкретные обращения к этим функциям и перечни их параметров приводятся в документации на соответствующую ОС.

6.Мониторы Хоара

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

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

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