Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 59
Текст из файла (страница 59)
Однако это, какУже знаем, приведет к тому, что система не сможет реагировать на внешниесобытия.эт e^T° Т 0 Г ° ч т о ^ ы связывать с каждым процессом собственную переменную, какЬ1ло в рассмотренных нами решениях, можно со всем множеством конкури-224Глава 7. Организация параллельных взаимодействующих вычисленарующих критических секций связать одну переменную, которую Дейкстра предложил рассматривать как некоторый «ключ». Вначале доступ к критической секции открыт. Однако перед входом в свою критическую секцию процесс забираетключ и тем самым блокирует другие процессы.
Покидая критическую секцию, процесс открывает доступ, возвращая ключ на место. Если процесс, который хочетвойти в свою критическую секцию, обнаруживает отсутствие ключа, он долженбыть переведен в состояние блокирования до тех пор, пока процесс, имеющий ключне вернет его. Таким образом, каждый процесс, входящий в критическую секциюдолжен вначале проверить, доступен ли ключ, и если это так, то сделать его недоступным для других процессов. Причем самым главным должно быть то, что этидва действия должны быть неделимыми, чтобы два или более процессов не моглиодновременно получить доступ к ключу.
Более того, проверку возможности входав критическую секцию лучше всего выполнять не самим конкурирующим процессам, так как это приводит к активному ожиданию, а возложить эту функцию наоперационную систему. Таким образом, мы подошли к одному из самых главныхмеханизмов решения проблемы взаимного исключения — семафорам Дейкстры.Семафорные примитивы ДейкстрыПонятие семафорных механизмов было введено Дейкстрой [10]. Семафор (semaphore) — это переменная специального типа, которая доступна параллельным процессам только для двух операций — закрытия и открытия, названных соответственнооперациями Р и V1. Эти операции являются примитивами относительно семафора,который указывается в качестве параметра операций. Здесь семафор играет рольвспомогательного критического ресурса, так как операции Р и V неделимы при своем выполнении и взаимно исключают друг друга.Семафорный механизм работает по схеме, в которой сначала исследуется состояние критического ресурса, идентифицируемое значением семафора, а затем ужеосуществляется допуск к критическому ресурсу или отказ от него на некотороевремя.
При отказе доступа к критическому ресурсу используется режим пассивного ожидания. Поэтому в состав механизма включаются средства формирования иобслуживания очереди ожидающих процессов. Эти средства реализуются супервизором операционной системы. Необходимо отметить, что в силу взаимного исключения примитивов попытка в различных параллельных процессах одновременно выполнить примитив над одним и тем же семафором приведет к тому, что онаокажется успешной только для одного процесса. Все остальные процессы на время выполнения примитива будут взаимно исключены.Основным достоинством семафорных операций является отсутствие состояв!активного ожидания, что может существенно повысить эффективность работмультизадачной системы.В настоящее время на практике используется много различных видов семафорных механизмов [41].
Варьируемыми параметрами, которые отличают различивиды примитивов, являются начальное значение и диапазон изменения значен!• голландского Proberen (проверить), V — от голландского Verhogen (увеличить).ррйпства синхронизации и связи взаимодействующих процессов225мафора, логика действий семафорных операций, количество семафоров, доступных для обработки при исполнении отдельного примитива.Обобщенный смысл примитива P(S) состоит в проверке текущего значения семафора S. Если оно не меньше нуля, то осуществляется переход к следующей за примитивом операции.
В противном случае процесс снимается на некоторое время свыполнения и переводится в состояние пассивного ожидания. Находясь в спискезаблокированных, ожидающий процесс не проверяет семафор непрерывно, как вслучае активного ожидания. Вместо него процессор может исполнять другой процесс, реально выполняющий какую-то полезную работу.Операция V(S) связана с увеличением значения семафора на единицу и переводомодного или нескольких процессов в состояние готовности к исполнению центральным процессором.Отметим еще раз, что операции Р и V выполняются операционной системой в ответна запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра.Рассмотрим первый вариант алгоритма работы семафорных операций (листинг 7.7).Допустимыми значениями семафоров являются только целые числа.
Двоичнымсемафором будем называть семафор, максимально возможное значение которогоравно единице. Двоичный семафор 1 либо открыт, либо закрыт. В случае, когда семафор может принимать более двух значений, его называют N-ичным. Есть реализации, в которых семафорные переменные не могут быть отрицательными, а есть итакие, где отрицательное значение указывает на длину очереди процессов, стоящихв состоянии ожидания открытия семафора.Листинг 7.7. Вариант реализации семафорных примитивовP(S): S:-S-l:if S<0 then { остановить процесс и поместить его в очередь ожидания к семафору S };V(s): if S<0 then { поместить один из ожидающих процессов очереди семафора S в очередьготовности };S:-S+l:Заметим, что для работы с семафорными переменными необходимо еще иметь операцию инициализации самого семафора, то есть задания ему начального значения.Обычно эту операцию называют InitSem; как правило, она имеет два параметра —имя семафорной переменной и ее начальное значение, то есть обращение имеет видInitSem ( Имя_семафора.
Начальное_значение_семафора ):Попытаемся на нашем примере двух конкурирующих процессов ПР1 и ПР2 проанализировать использование данных семафорных примитивов для решения проблемы критической секции. Программа, иллюстрирующая это решение, представлена в листинге 7.8.•истинг 7.8. Взаимное исключение с помощью семафорных операций* i r S:semafor;begin InitSem(S.l);' дИчные семафоры иногда называют мыотексами (см. далее).продолжениеJ226Глава 7, Организация параллельных взаимодействующих вычислены,-.Листинг 7.8 (продолжение)parbeginПР1: while true dobeginPCS);CS1 : { критическая секция процесса ПР1 }V(S)endandПР2: while true dobeginPCS):CS2 ;{ критическая секция процесса ПР2 }V(S)endparendend.Семафор S имеет начальное значение, равное 1.
Если процессы ПР1 и ПР2 попытаются одновременно выполнить примитив P(S), то это удастся успешно сделатьтолько одному из них. Предположим, это сделал процесс ПР2, тогда он закрываетсемафор S, после чего выполняется его критическая секция. Процесс ПР1 в рассматриваемой ситуации будет заблокирован на семафоре S. Тем самым гарантируется взаимное исключение.После выполнения примитива V(S) процессом ПР2 семафор S открывается, указывая на возможность захвата каким-либо процессом освободившегося критического ресурса. При этом производится перевод процесса ПР1 из заблокированногосостояния в состояние готовности.На уровне реализации возможно одно из двух решений в отношении процессов,которые переводятся из очереди ожидания в очередь готовности при выполнениипримитива V:Q процесс при его активизации (выборка из очереди готовности) вновь пытаетсявыполнить примитив Р, считая предыдущую попытку неуспешной;Q процесс при помещении его в очередь готовности отмечается как успешно выполнивший примитив Р, тогда при его активизации управление будет переданоне на повторное выполнение примитива Р, а на команду, следующую за ним.Рассмотрим первый способ реализации.
Пусть процесс ПР2 в некоторый моментвремени выполняет операцию P(S). Тогда семафор S становится равным нулю. Пустьдалее процесс ПР1 пытается выполнить операцию P(S). Процесс ПР1 в этом случае блокируется на семафоре S, так как значение семафора S равнялось нулю, а теперь станет равным - 1 . После выполнения критической секции процесс ПР2 выполняет операцию V(S), при этом значение семафора S становится равным пула процесс ПР1 переводится в очередь готовности. Пусть через некоторое времпроцесс ПР1 будет активизирован, то есть выведен из состояния ожидания, и CNжет продолжить свое исполнение.
Он повторно попытается выполнить операниP(S), однако это ему не удастся, так как S=0. Процесс ПР1 блокируется на семафоруа его значение становится равным - 1 . Если через некоторое время процесспопытается выполнить P(S), то он тоже заблокируется. Таким образом, возник227ррйдства синхронизации и связи взаимодействующих процессоваК называемая тупиковая ситуация, так как разблокировать процессы ПР1 и ПР2некомуПри втором способе реализации тупика не будет. Действительно, пусть все проис•одит так же до момента окончания исполнения процессом ПР2 примитива V(S).Пусть примитив V(S) выполнен, и S=0.
Через некоторое время процесс ПР1 активизируется. Согласно данному способу реализации он сразу же попадет в свою критическую секцию. При этом никакой другой процесс не попадет в свою критическуюсекцию, так как семафор остается закрытым. После исполнения своей критическойсекции процесс ПР1 выполнит V(S). Если за время выполнения критической секциипроцесса ПР1 процесс ПР2 не сделает попыток выполнить операцию P(S), семафор Sустановится в единицу. В противном случае значение семафора будет не большенуля. Но в любом варианте после завершения операции V(S) процессом ПР1 доступк критическому ресурсу со стороны процесса ПР2 будет разрешен.Заметим, что возникновение тупиков возможно в случае несогласованного выбора механизма извлечения процессов из очереди, с одной стороны, и выбора алгоритмов семафорных операций, с другой.Возможен другой алгоритм работы семафорных операций:P(S):if S>-1 then S:=S-1else WAIT(S){ остановить процесс и поместить в очередь ожидания к семафору S }V(S): if S<0 then RELEASE(S){ поместить один из ожидающих процессов очереди семафора Sв очередь готовности };S:=S+1.Здесь вызов WAIT(S) означает, что супервизор ОС должен перевести задачу в состояние ожидания, причем очередь процессов связана с семафором S.
Вызов RELEASE(S)означает обращение к диспетчеру задач с просьбой перевести первый из процессов, стоящих в очереди S, в состояние готовности к исполнению.Использование семафорных операций, выполненных подобным образом, позволяет решать проблему критических секций на основе первого способа реализации, причем без опасности возникновения тупиков. Действительно, пусть ПР2 в некоторыймомент времени выполнит операцию P(S).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
