Операционные системы
Самостоятельная работа №3A
Исследование методов синхронизации процессов с помощью семафоров
Цель работы: знакомство с методами синхронизации процессов на основе семафоров.
Общие сведения
Синхронизацией называется обеспечение заданной очередности прохождения процессов через определенные состояния.
Наиболее часто синхронизация требуется для координации доступа нескольких процессов к одному разделяемому ресурсу.
Рассмотрим простейший пример. Предположим, что два процесса выводят информацию в виде символа в разные точки экрана.
Фрагмент текста процедур, соответствующих процессам, выглядит следующим образом:
Процесс 1 Процесс 2
(1) GoTo(X,Y); (3) GoTo(X,Y);
(2) Write(Ch); (4) Write(Ch);
При выполнении процессов в режиме разделения времени возможна следующая ситуация, когда оператором GoTo(X,Y) курсор устанавливается в нужную точку экрана одним процессом, затем под действием диспетчера происходит передача управления другому процессу, который в это время выполняет оператор вывода символа. То есть очередность выполнения действий такова: 1, 3, 2, 4 или 3, 1, 4, 2.Очевидно, что в этом случае один из процессов выведет информацию не в то место экрана, куда планировал.
Суть исправления ошибки состоит в обеспечении неделимости выполнения последовательности действий GoTo(X,Y) и Write(Ch).
В более общем смысле ситуация представляется следующим образом. Экран в данном случае выступает в роли разделяемого ресурса, который два процесса используют совместно и одновременно. Ошибка возникает при отсутствии регламентации доступа к разделяемому ресурсу, а регламентация доступа заключается в том, что если один процесс работает с общим ресурсом, то другой процесс не должен в это же время работать с ним.
Используемый совместно несколькими процессами ресурс называется критическим, участок программы процесса, реализующий работу с критическим ресурсом, называется критическим участком, а режим, при котором только один процесс в произвольный момент времени может работать с критическим ресурсом (или находиться в критическом участке), называется режимом взаимного исключения.
В системах реального времени пренебрежение регламентацией доступа нескольких процессов к критическому ресурсу может приводить к катастрофическим последствиям.
Методы обеспечения режима взаимного исключения
Можно выделить три принципиальных пути обеспечения режима взаимного исключения.
1) Запрет прерываний на входе в критический участок и разрешение прерываний на выходе из него.
То есть фрагмент программы работы с критическим участком выглядит следующим образом:
Запрет прерываний:
Критический участок;
Разрешение прерываний.
Первым и единственным войдет в свой критический участок войдет тот процесс, который первым доберется до инструкции CLI в функции Запрет прерываний. Прерывания будут запрещены, диспетчер прекратит работу и все другие процессы естественным образом будут приостановлены. После выхода из критического участка прерывания будут разрешены и какой-то другой процесс сможет войти в свой критический участок.
Такой способ организации взаимного исключения обладает существенными недостатками:
- при запрете прерываний система становится слепой и глухой к внешним воздействиям окружающей среды, которые формируются, как правило, через систему прерываний;
- приостанавливаются даже те процессы, которые вообще не работают с данным ресурсом.
Поэтому данный способ организации взаимного исключения применяется в тех случаях, когда критический участок очень короткий, например, несколько инструкций.
2) Активное ожидание.
В этом случае вводится некоторый флаг занятости ресурса, который проверяется процессом перед тем, как войти в критический участок. Если флаг, который в начале устанавливается в состояние СВОБОДЕН, находится в состоянии СВОБОДЕН, то процесс переводит флаг в состояние ЗАНЯТ, и входит в критический участок. При выходе из критического участка процесс устанавливает флаг в состояние СВОБОДЕН. Если при подходе к критическому участку флаг оказывается в состоянии ЗАНЯТ, то процесс начинает проверять состояние флага в цикле до тех пор пока флаг не будет установлен в состояние СВОБОДЕН другим процессом.
То есть фрагменты процедуры, описывающие процесс на этапах входа в критический участок и выхода из него, выглядят следующим образом:
Инициализация: FLAG := СВОБОДЕН;
While FLAG = ЗАНЯТ Do Begin
End {While};
FLAG := ЗАНЯТ;
Критический участок;
FLAG := СВОБОДЕН;
В данном случае сам флаг является критическим ресурсом и доступ к нему должен производиться в режиме взаимного исключения. Фрагмент входа в критический участок с проверкой и установкой флага в режиме взаимного исключения выглядит следующим образом (состояние ЗАНЯТ соответствует FLAG = 1):
LBL : STI
CLI
CMP FLAG, 1
JZ LBL
MOV FLAG, 1
STI
Если чтение и установку флага выполнять за одну инструкцию, которая является неделимым действием, то вход в критический участок можно выполнить более элегантно, а именно,
MOV AX, 1
LBL : XCHG AX, FLAG
CMP AX, 1
JZ LBL
Недостатком приведенного метода реализации взаимного исключения является активное ожидание, то есть процесс, который ждет освобождения ресурса, занимает процессор в отводимые ему диспетчером кванты времени, хотя и не выполняет никаких полезных действий.
Поэтому в случае необходимости ожидания освобождения ресурса целесообразно снять процесс из очереди готовых процессов и не предоставлять ему бесполезно используемых квантов времени. На этом положении основано использование семафоров как средств взаимного исключения при доступе к критическому ресурсу.
3) Семафоры.
Семафор представляет собой объект, включающий счетчик и очередь. В очередь помещаются процессы, ждущие наступления некоторого события, например, освобождения ресурса. Условия помещения процесса в очередь и извлечения из очереди с целью активизации определяются состоянием счетчика и проверяются двумя операциями над семафором, которые называются P и V операции.
Принципы работы с семафором можно описать следующим образом. В исходном состоянии семафор открыт. Процесс проходит через открытый семафор в критический участок и закрывает за собой семафор. Другой процесс, подходя к критическому участку, натыкается на закрытый семафор и вынужден ждать его открытия в очереди семафора. Процесс, выходя из критического участка, открывает семафор и активизирует первый в очереди семафора процесс, так что теперь этот процесс может войти в критический участок и также закрыть за собой семафор.
Состояние счетчика семафора играет роль индикатора занятости ресурса. Принято инициализировать счетчик в 1, декрементировать при подходе к критическому участку (Р-операция) и инкрементировать при выходе из критического участка (V-операция). Таким образом равенство нулю счетчика свидетельствует о возможности входа в критический участок, а отрицательное значение счетчика свидетельствует о наличии процесса в критическом участке и необходимости блокировки, то есть переводе в очередь семафора с передачей управления другим процессам.
Технология реализации семафора
Технология реализации семафора представлена в виде описания семафора как объекта языка программирования.
Type
PSemaphore = ^TSemaphore;
TSemaphore = Object
Счетчик : Целое;
Очередь_семафора : Очередь процессов;
Constructor Init(С : Целое);
Destructor Done; Virtual;
Procedure P;
Procedure V;
End {TSemaphore}.
Constructor TSemaphore.Init(Целое);
Begin
Счетчик := С;
Создать Очередь_семафора;
End {TSemaphore.Init};
Destructor TSemphore.Done;
Begin
Разрушить Очередь_семафора;
End {TSemaphore.Done};
Procedure TSemaphore.P;
Var
Предыдущий : Процесс;
Begin
Запретить_прерывания;
Счетчик := Счетчик - 1;
If Счетчик < 0 Then Begin {блокировать процесс}
Предыдущий := Текущий;
Очередь_семафора.Включить(Предыдущий);
Текущий := Очерередь_готовых.Первый;
Очередь_готовых.Извлечь(Текущий);
Передать_управление(Предыдущий, Текущий);
End {If};
Разрешить_прерывания;
End {TSemaphore.P};
Procedure TSemaphore.V;
Var
Предыдущий : Процесс;
Begin
Запретить_прерывания;
Счетчик := Счетчик + 1;
If Счетчик <= 0 Then Begin {активизировать процесс}
Предыдущий := Текущий;
Очередь_готовых.Включить(Предыдущий);
Текущий := Очередь_семафора.Первый;
Очередь_семафора.Извлечь(Текущий);
Передать_управление(Предыдущий, Текущий);
End {If};
Разрешить_прерывания;
End {TSemaphore.V}.
Здесь процесс, вызвавший метод TSemaphore.V, переводится в очередь готовых и активизирует процесс, стоящий первым в очереди семафора.
Технология использования семафоров
В первую очередь семафоры используются как средства взаимного исключения при доступе к критическому ресурсу. Правило использования семафора в этом случае представлено в виде фрагмента процедуры, описывающей процесс при входе в критический участок и выходе из него.
Раздел описания:
Var Semaphore : TSemaphore;
Раздел инициализации:
Semaphore.Init(1);
Процесс при работе с критическим участком:
Semaphore.P;
Критический участок;
Semaphore.V;
Завершение работы с семафором:
Semaphore.Done;
Семафоры могут быть использованы не только для координации доступа к критическому ресурсу нескольких процессов, но и для установления требуемой очередности прохождения процессами определенных состояний. Пусть, например, необходимо, чтобы процесс Р1 прошел через состояние, отмеченное меткой М_Р1, например, чтение из ячейки памяти П, только после того, как процесс Р2 пройдет через состояние, отмеченное меткой М_Р2, например, запись в ячейку памяти П. То есть запись должна произойти раньше чтения.
С помощью семафора данная задача решается следующим образом:
Инициализация семафора: Semaphore.Init(0);
Процесс Р1 Процесс Р2
Semaphore.P;
М_Р1 : Чтение из П; М_Р2 : Запись в П;
Semaphore.V;
Если процесс Р1 подойдет к метке М_Р1 раньше, чем процесс Р2 подойдет к метке М_Р2, то он будет вынужден блокироваться в очереди семафора. Процесс Р2, выполнив запись в ячейку П, вызовет Semaphore.V и тем самым активизирует процесс Р1, позволив ему выполнить чтение только после того как осуществлена запись.
Часто процессы реализуются в виде бесконечных циклов, поэтому чтобы не произошло нескольких записей в ячейку П одним процессом до того как произойдет чтение из ячейки П другим процессом, необходимо последующие записи осуществлять только после очередного чтения. Указанная схема реализуется следующим образом:
Инициализация семафора: Semaphore1.Init(0);
Инициализация семафора: Semaphore2.Init(0);
Процесс Р1 Процесс Р2
While True Do Begin While True Do Begin
. . . . . .
Semaphore1.P;
М_Р1 : Чтение из П; М_Р2 : Запись в П;
Semaphore2.V; Semaphore1.V;
Semaphore2.P;
. . . . . .
End {While}; End {While}.
Теперь процесс Р2, выполнив запись, и сигнализировав об этом вызовом Semaphore1.V, ожидает, приостановленный вызовом Semaphore2.P, чтения процессом Р1, о чем Р1 будет сигнализировать вызовом Semaphore2.V. В этой схеме методы семафора Semaphore2 выполняют роль ожидания и посылки квитанции, подтверждающей чтение.
Задание
- Реализовать объект – семафор.
- Написать демонстрационную программу, иллюстрирующую координацию доступа к критическому ресурсу с помощью реализованного семафора.
- Написать демонстрационную программу, иллюстрирующую синхронизацию прохождения процессов через определенные состояния с помощью реализованного объекта-семафора.
- Отчет должен содержать текст библиотечного модуля, включающего описание и реализацию объекта-семафора, тексты демонстрационных программ с комментариями, таблицы состояний счетчиков семафоров при различных вариантах очередности прохождения процессов (для числа процессов, большего, чем 2) через вызовы P и V используемых семафоров.