Общие и двоичные семафоры

Семафоры как общее средство синхронизации

Реализация семафоров

Синхронизация на основе общих семафоров

Мы уже начали рассматривать семафоры Дейкстры как средство синхронизации в обзорной части курса. Здесь мы рассмотрим их более подробно в общем виде. Общий семафор (counting semaphore), по Э. Дейкстре, - это целая переменная S, над которой определены две атомарных семафорных операции wait (S) и signal (S) со следующей семантикой:

wait (S):

while (S <= 0) do no-op;

S--;

signal (S):

S++;

Фактически, если начальное значение общего семафора равно n (> 0), то это число задает количество процессов, которые могут беспрепятственно выполнить над семафором операцию wait.

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

/* общие данные */

semaphore mutex = 1;

do {

wait (mutex);

критическая секция

signal (mutex);

остальная часть кода

} while (1)

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

typedef struct {

int value;

struct process * L;

} semaphore;

При реализации операций над семафором будем предполагать наличие в системе следующих простейших примитивов и использовать их:

block - задерживает исполнение процесса, выполнившего эту операцию;

wakeup (P) – возобновляет исполнение приостановленного процесса P.

Определим семафорные операции следующим образом:

wait (S):

S.value--;

if (S.value < 0) {

добавление текущего процесса к S.L;

block;

}

signal (S):

S.value++;

if (S.value <= 0) {

удаление процесса P из S.L;

wakeup (P);

}

Наиболее простой вид синхронизации действий, выполняемых в двух процессах, - это исполнение действия B в процессе Pj после того, как действие A исполнено в процессе Pi. Рассмотрим, как такую синхронизацию осуществить с помощью семафоров.

Используем семафор flag, инициализированный 0.

Код процесса Pi:

...

A;

signal (flag);

Код процесса Pj:

...

wait (flag);

B;

Из рассмотренного ясно, что имеется два вида семафоров: общий - целая переменная с теоретически неограниченным значением - и двоичный - целая переменная, значениями которой могут быть только 0 или 1. Преимуществом двоичного семафора является его возможная более простая аппаратная реализация. Например, в системах "Эльбрус" и Burroughs 5000 реализованы команды атомарного семафорного считывания с проверкой семафорного бита.

Очевидно, что общий семафор может быть реализован с помощью двоичного семафора.

Вариант операции wait (S) для системных процессов ("Эльбрус")

Для системного процесса лишние прерывания нежелательны, и может оказаться важным удерживать процессор за собой некоторое время (например, для быстрого выполнения планирования и диспетчеризации процессов). С этой целью в системе "Эльбрус" реализованаа, в дополнение к операции ждать (S) русифицированной версии wait(S), операция жуж(S) - "жужжать" на процессоре, т.е. ждать на закрытом семафоре, но не прерываться и не отдавать процессор, пока семафор не будет открыт операцией открыть(S)

Дата добавления: 2014-01-20