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

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

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) Поток, нормально работающий вне своей КС, не должен блокировать другой поток при вхождении последнего в свою КС.

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

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

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

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

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.

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

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

Program Variant2;

Var CS1_in, CS2_in: Boolean;

Procedure process_1;

Begin

While true Do

Begin

While CS2_in Do; {активное ожидание}

CS1_in:=true; CS1; CS1_in:=false;

program_1;

End;

End;

Procedure process_2;

Begin

While true Do

Begin

While CS1_in Do; {активное ожидание}

CS2_in:=true; CS2; CS2_in:=false;

program_2;

End;

End;

Begin

CS1_in:=false;

CS2_in:=false;

Parbegin

process_1;

process_2;

Parend

End.

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

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

Существует ещё ряд вариантов взаимоисключения, но все они не свободны от недостатков.

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

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

Рассмотрим, как работает такой вариант. Первый процесс сообщает о своём желании войти в критическую секцию, устанавливая свой флаг (p1_wants_to_come:=true). Затем он переходит к циклу, в котором проверяет, не хочет ли и другой процесс войти в свою критическую секцию, т.е. каково значение переменной p2_wants_to_come. Если нет (переменная имеет значение "ложь"), то он пропускает тело цикла ожидания и успешно входит в свою критическую секцию. Если же первый процесс обнаруживает, что флаг второго процесса тоже установлен, то он входит в цикл ожидания. Здесь он проверяет, какой процесс выбран – анализирует значение переменной turn. Если turn=1, т.е. его очередь выполняться, он пропускает тело своего цикла и снова выполняет цикл проверки в ожидании того момента, когда второй процесс сбросит свой флаг. Если же выбран второй процесс (turn=2), то первый процесс сбрасывает свой флаг и блокируется в цикле ожидания, пока избранным остается второй процесс. Сбрасыванием своего флага он даёт возможность второму процессу войти в свой критический интервал.

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

Program Variant_Dekker;

Var turn: 1,2;

p1_wants_to_come, p2_wants_to_come: Boolean;

Procedure process_1;

Begin

While true Do

Begin

p1_wants_to_come:=true; {претендует на вход в КС}

While p2_wants_to_come Do {второй тоже}

If turn=2 Then

Begin

p1_wants_to_come:=false; {отказ от входа в КС}

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

p1_wants_to_come:=true; {снова претендует на КС}

End

CS1;

turn:=2;

p1_wants_to_come:=false; {отказ от входа в КС}

program_1;

End;

End;

Procedure process_2;

Begin

While true Do

Begin

p2_wants_to_come:=true; {претендует на вход в КС}

While p1_wants_to_come Do {второй тоже}

If turn=1 Then

Begin

p2_wants_to_come:=false; {отказ от входа в КС}

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

p2_wants_to_come:=true; {снова претендует на КС}

End

CS2;

turn:=1;

p2_wants_to_come:=false; {отказ от входа в КС}

program_2;

End;

End;

Begin

p1_wants_to_come:=false;

p2_wants_to_come:=false;

turn:=1;

Parbegin

process_1; process_2;

Parend

End.

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

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

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

Понятия, относящиеся к проблеме взаимоисключения, Дейкстра обобщил в своей концепции семафоров. Семафор – это переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: "закрытия" и "открытия", названных соответственно 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 также являются одним неделимым действием.

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

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

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

Program example_semaphore1;

Var S: semaphore;

Procedure process_1;

Begin

While true Do

Begin

P(S);

CS1;

V(S);

program_1;

End;

End;

Procedure process_2;

Begin

While true Do

Begin

P(S);

CS2;

V(S);

program_2;

End;

End;

Begin

InitSem(S,1);

Parbegin

process_1; process_2;

Parend

End.

Семафор имеет начальное значение, равное 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 -операцию, т.е. сделал заявку на КС. Таким образом, тупик не возникнет, а взаимоисключение гарантировано.

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

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

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

Program semaphore_release;

Type Semaphore = Record

счетчик: Integer;

указатель: Pointer;

end;

Var S: Semaphore;

Procedure P(Var S:Semaphore);

Begin

Запретить прерывания;

S.счетчик:= S.счетчик-1;

If S.счетчик<0 Then

WAIT(S); {Поставить обратившийся процесс в список по S.указатель и установить на процессорр готовый к выполнению процесс}

Разрешить прерывания;

End;

Procedure V(Var S:Semaphore);

Begin

Запретить прерывания;

S.счетчик:= S.счетчик+1;

If S.счетчик<=0 Then

RELEASE(S); {Деблокировать первый процесс из списка по S.указатель}

Разрешить прерывания;

End;

Procedure InitSem(Var S:Semaphore, n:Integer);

Begin

S.счетчик:=n;

S.указатель:=nil;

End;