Parbegin

Begin

End

Begin

While (true) do

Begin

End

Begin

While (true) do

Begin

Семафоры

Синхронизация параллельных процессов на низком уровне.

Лекция 6

Глава 5. Синхронизация параллельных процессов на низком

уровне (продолжение)

3. Семафоры. Реализация взаимоисключения при помощи семафоров.

Синхронизация блокирования/возобновления процессов при помощи семафоров. Реализация взаимодействия в паре “производитель-потребитель” при помощи семафоров.

Дополнительный материал

Механизмы межпроцессных взаимодействий в UNIX. Семафоры.

Литература

· [Гордеев01] Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. СПб.: Питер, 2001.

· [Дейтел 87] Дейтел Г., Введение в операционные системы. М."Мир",1987.

· [Кейлингерт 85] Кейлингерт П., Элементы операционных систем, М."Мир", 1985.

· [Кейслер 86] Кейслер С., Проектирование операционных систем для малых ЭВМ, М."Мир", 1986.

· [Цикритзис 77] Цикритзис Д., Бернстайн Ф., Операционные системы, М."Мир", 1977.

Концепция использования семафоров для реализации взаимоисключений предложена Дейкстрой3.

Семафор или общий семафор (semaphore) - это целая переменная, значение которой можно опрашивать и менять только при помощи специальных неделимых (как команда testandset) операций P и V.

Двоичный семафор может принимать только значения 0 или 1. Считающий семафор может принимать целые неотрицательные значения.

Операция Р над семафором S записывается как P(S), алгоритм ее выполненения следующий:

if S>0 then S:=S-1 else <ожидать на S>

if <один или несколько процессов ожидают на S>

then <разрешить одному из этих процессов продолжить работу>

else S:=S+1

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

Приведем пример алгоритма обеспечения взаимоисключения при помощи семафора. Инициализацию семафора будем производить с помощью операции, условно обозначенной Инициализация_S(S,1),котораяустанавливает для семафора начальное значение1илиИницилизация_S(S,0),

- соответственно, 0.

var S : семафор;

procedure Процесс_Х;

{Предшествующая критическому участку

часть процесса_Х}

P(S);{если в семафоре 1, то S:=S-1, иначе ожидать}

{Критический участок процесса_Х}

V(S);{если процесс ожидает на S, то разрешить работу, иначе S:=S+1}

{Остальная часть процесса_Х}

end;

procedure Процесс_Y;

{Предшествующая критическому участку

часть процесса_Y}

P(S);{вход взаимоисключения, процесс ожидает выполнения операции V(S) процессом_Х }

{Критический участок процесса_Y}

V(S);{выход взаимоисключения}

{Остальная часть процесса_Y}

end;

Инициализация_S(S,1);

Процесс_Х;

Процесс_Y;