Ловушка

Если фишка попадает в такой участок сети, то выйти из него самостоятельно система не сможет (произойдет зацикливание).

Ловушка в сети Петри

Подобным образом в сетях Петри моделируется ситуация зацикливания вычислительного процесса.

Клинч или «deadlock»

а б

Клинч

Клинч – ошибка, возникающая при синхронизации легковесных процессов, когда между двумя легковесными процессами существует кольцевая зависимость от пары синхронизированных объектов. Предположим, что один процесс получает управление объектом А, а другой процесс - объектом Б. Если А пытается вызвать любой синхронизированный метод объекта Б, то этот вызов блокируется. Если при этом и Б попытается вызвать метод объекта А, то задача окажется заблокированной навсегда.

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

Предотвращение взаимоблокировок является существенной трудностью, возникающей при проектировании взаимодействующих систем.

Лекция7 Объекты ядра ос, предназначенные для решения задач синхронизации

Операционной системой предусмотрен ряд объектов ядра, применяемых для решения задач синхронизации.

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

События. Событие (event) является самым примитивным способом синхронизации и генерируется в системе при изменении состояния окна или некоторого устройства (например, нажатия клавиши клавиатуры или перемещения мыши).

В общем случае событие в многозадачных системах соответствует понятию «прерывание», с той разницей, что в случае генерации прерывания приостанавливается выполнение всех задач на период обработки прерывания, а события могут по-своему обрабатываться различными задачами или не обрабатываться вовсе.

Семафоры. Семафор – это системное средство для синхронизации выполнения процессов. Семафоры могут применяться наряду с критическими секциями и объектами mutex для обеспечения синхронизации и поддержки межпроцессного взаимодействия.

Семафор отвечает за разграничение доступа к системному ресурсу между несколькими процессами. Согласование доступа производится следующим образом: при обращении процесса к системному ресурсу семафор, в случае, если ресурс занят, переводит обращающийся процесс в состояние ожидания.

Алгоритм Дейкстры, описывающий состояния семафора:

Семафоры реализуются как целочисленные объекты, для которых определены операции увеличения и уменьшения значения на единицу. Если процесс получает ресурс в свою собственность, он уменьшает значение семафора на единицу. При освобождении ресурса счетчик значений семафора увеличивается на единицу.

Итак, семафор – целая переменная, над которой определены операции P и V. Обозначим семафор через S.

Операция P(S):S-1,т.е уменьшает S на 1.

Операция V(S):S+1, т.е увеличивает S на 1.

Действия при P(S):

1. если S0, то процесс продолжает работу;

2. если S<0, то процесс останавливается и встает в очередь ожидания, связанную с S (он остается заблокированным до тех пор, пока операция V(S), выполненная другим процессом, не освободит его).

Действия при V(S):

1. Если S>0, то процесс продолжает работу;

2. Если S0, то один процесс удаляется из очереди ожидания и получает разрешение продолжить работу (процесс, обратившийся к операции V(S), также может продолжить работу).

Семафор может находиться в трех состояниях: открыт, закрыт монопольно и закрыт со счетчиком некоторого количества операций.

Взаимодействие с семафором в монопольном режиме: если семафор открыт, то при обращении процесса к ресурсу семафор переводится в состояние «закрыт монопольно». Если семафор закрыт, текущий процесс переводится в состояние ожидания и становится в очередь к данному семафору.

Естественно, что возможно заведомое задание некоторого «контрольного» времени ожидания. Например, в Win32 такое время в миллисекундах передается в функцию ожидания в качестве параметра. Процесс, ожидающий открытия семафора, активизируется либо в случае открытия семафора, либо по истечении времени ожидания.

Отметим, что:

• операции P и V неделимы;

• в каждый момент только один процесс может выполнять операцию P или V над семафором S;

• операции P и V можно реализовать внутри ядра, поскольку ему разрешено запускать и останавливать процессы;

• вводя операции P и V над семафором, можно решить проблему критического участка без активного ожидания.

Двоичный семафор – семафор, максимальное значение которого равно 1.

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

1. P(S)

2. критический участок i

3. V(S)

Для 2-х процессов S принимает значения 1,0 или -1:

• если S=1, это значит, что ни один из процессов не находится в своем критическом участке;

• если S=0, это значит, что один процесс находится в своем критическом участке;

• если S=-1, это значит, что один процесс находится в своем критическом участке и один, – в очереди к семафору S, где он ждет разрешения войти в свой критический участок.

Семафоры в Win32. Семафором в ОС платформы Win32 называется объект ядра, отвечающий за разграничение доступа к общим ресурсам системы при одновременном исполнении нескольких задач. Фактически семафор сообщает процессам, пытающимся получить доступ к ресурсу, о готовности данного ресурса.

Создание семафора производится вызовом функции

HANDLE CreateSemaphore(LPSECURITY_ATTRIBUTES sa,

LONG InitialCount,

LONG MaximumCount,

LPCTSTR Name);

Параметр InitialCount определяет начальное значение семафора, параметр MaximumCount определяет максимальное значение, которое может принять счетчик семафора. В параметре Name передается имя семафора.

Доступ к уже существующему семафору производится вызовом функции

HANDLE OpenSemaphore(DWORD DesiredAccess,

BOOL InheritHandle,

LPCTSTR Name);

Где параметром DesiredAccess определяется характер доступа к семафору (SEMAPHORE_ALL_ACCESS или SYNCHRONIZE).

Освобождение семафора производится функцией

BOOL ReleaseSemaphore(HANDLE Semaphore,

LONG ReleaseCount,

LPLONG lpPreviousCount);

Вызов данной функции увеличивает счетчик семафора на величину, переданную в ReleaseCount. То есть если семафор был установлен в 0, что соответствует состоянию занятости ресурса, вызов функции ReleaseSemaphore() с параметром ReleaseCount, равным 1, освобождает ресурс, то есть переводит семафор в свободное (signaled) состояние.

В синхронизированную программу добавляется фрагмент кода:

…

HANDLE MySem=OpenSemaphore(SYNCHRONIZE,

FALSE,

“Semaphore1”);

if (WaitForSingleObject(MySem,

INFINITE)==WAIT_OBJECT_0)

{

cout << “Семафор освободился…” << endl;

}

…

Маленький совет: при открытии семафора под Windows NT используйте комбинацию флагов SYNCHRONIZE or EVENT_MODIFY_STATE. Открывая объект ядра в своей программе, вы получаете его копию. Модифицируя состояние объекта, укажите системе на необходимость модификации исходного объекта.

Пример.

Программа-отправитель создает семафор в «занятом» состоянии и по нажатию клавиши освобождает его.

#include <windows.h>

#include <conio.h>

void main()

{

HANDLE Sem=CreateSemaphore(NULL,0,1,"Semaphore1");

while(!kbhit())

{ }

ReleaseSemaphore(Sem,1,NULL);

return;

}

Программа-получатель синхронизирует свое выполнение с семафором посредством функции ожидания (wait function). При нажатии клавиши в консоли программы отправителя программа-получатель выбрасывает на экран соответствующее сообщение.

#include <windows.h>

#include <iostream.h>

void main()

{

HANDLE Sem=OpenSemaphore(SYNCHRONIZE,

FALSE,"Semaphore1");

if(Sem!=NULL)

{

if(WaitForSingleObject(Sem,INFINITE)==WAIT_OBJECT_0)

{

cout << "Семафор открыт " << endl;

}

}

else

{ cout << “Семафор не найден” << endl;

return;

}

return;

}