Семафоры и их применение - Независимые и взаимодействующие вычислительные процессы

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

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

Похожие статьи




Семафоры и их применение - Независимые и взаимодействующие вычислительные процессы

Предыдущая | Следующая