Алгоритмы и механизмы синхронизации процессов в операционных системах
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?бновить исполнение. Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо него на процессоре может исполняться другой процесс.
Рис. 5. Обращение процессов к семафору.
Операции Р и V выполняются операционной системой в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра. По операциям Р и V выполняются следующие действия:
P(S): if S=1
then S=S-1 /*закрыть семафор*/
else БЛОКИРОВАТЬ обратившийся процесс по S
V(S): if список процессов, ожидающих S, не пуст
then ДЕБЛОКИРОВАТЬ процесс, ожидающий S
else S=1 /*открыть семафор*/
При этом не определяется, какой из нескольких ожидающих процессов будет деблокирован.
Для реализации взаимного исключения, например, предотвращения возможности одновременного изменения двумя или более процессами общих данных, создается двоичный семафор S. Начальное значение этого семафора устанавливается равным 1. Критические секции кода (секции, которые могут одновременно выполняться только одним процессом) обрамляются операциями P(S) (в начале секции) и V(S) (в конце секции).
P(S)
критическая секция
V(S)
Процесс, входящий в критическую секцию, выполняет операцию P(S) и переводит семафор в 0. Если в критической секции уже находится другой процесс, то значение семафора уже равно 0. Тогда второй процесс, желающий войти в критическую секцию, блокируется своей P-операцией до тех пор, пока процесс, находящийся в критической секции сейчас, не выйдет из нее, выполнив на выходе операцию V(S).
Если начальное значение семафора равно единице, то взаимное исключение действительно гарантировано, так как процесс может выполнить P-операцию до того, как другой выполнит V-операцию. Кроме того, процесс без необходимости не перекрывает входы внутрь своей критической секции. Вход задерживается только тогда, когда некоторый другой процесс уже находится внутри своей собственной критической секции. Процесс отменяет вход, только, если значение семафора равно 0.
Таким образом, в каждый момент времени процесс, желающий получить доступ к разделяемой переменной или разделяемым ресурсам, должен сделать это посредством критической секции, защищенной семафором.
В качестве примера, предположим, что операционная система выполняет два процесса A и B, один из которых (процесс А) добавляет элемент в очередь, а другой (процесс В) удаляет элемент из очереди. Чтобы указатели очереди не стали перепутанными, необходимо ограничить доступ к очереди до одного процесса одновременно. Таким образом, добавление и удаление элементов могут быть закодированы как критические секции.
Программа для процесса А Программа для процесса В
код программы код программы
P(S) P(S)
добавить элемент в очередь удалить элемент из очереди
V(S) V(S)
код программы код программы
Это простое решение, использующее двоичные семафоры, применимо точно также и в случае большого числа процессов. В этом главное достоинство подхода с применением семафора.
Рис. 6. Использование двоичного семафора.
1.13 Семафоры в Windows
Семафоры и операции над ними, как правило, реализуются в ядре операционной системы, где осуществляется управление сменой состояния процессов.
Создание семафора
Для создания семафора приложение должно вызвать функцию CreateSemaphore. Синтаксис функции CreateSemaphore:
HANDLE CreateSemaphore(lpsa: LPSECURITY_ATTRIBUTES; cSemInitial: LONG; cSemMax: LONG; lpszSemName: LPTSTR);
Параметр lpsa задаёт дескриптор защиты, отличный от стандартного дескриптора. Значение параметра lpsa NULL указывает на стандартные атрибуты защиты.
Через параметры cSemInitial и cSemMax передаются, соответственно, начальное и максимальное значение счетчика, связанного с создаваемым семафором. Начальное значение счетчика cSemInitial должно быть больше или равно нулю и не должно превосходить максимальное значение счетчика, передаваемое через параметр cSemMax.
Параметр lpszSemName присваивает имя в виде строки. В дальнейшем это имя используется для получения описателя семафора из других процессов. Если семафор используется только для синхронизации задач, созданных в рамках одного приложения, можно создать безымянный семафор, указав в качестве параметра lpszSemName функции CreateSemaphore значение NULL. В том случае, когда необходимо синхронизовать задачи разных процессов, следует определить имя семафора.
В случае удачного создания семафора функция CreateSemaphore возвращает его идентификатор. В случае возникновения ошибки возвращается значение NULL, при этом код ошибки можно узнать при помощи функции GetLastError.
Так как имена семафоров доступны всем приложениям в системе, возможно возникновение ситуации, когда приложение пытается создать семафор с уже использованным именем. При этом новый семафор не создается, а приложение получает идентификатор для уже существующего семафора. Если возникла такая ситуация, функция GetLastError, вызванная сразу после функции CreateSemaphore, возвращает значение ERROR_ALREADY_EXISTS.
Уничтожение семафора
Для уничтожения семафора необходимо передать его идентификатор функции CloseHandle. Заметим, что при завершении процесса все созданные им семафоры уничтожаютс?/p>