Семафоры

Семафор – реализуемая ядром операционной системы специальная переменная, которая доступна параллельным процессам для выполнения двух операций – закрытия и открытия (P и V операции). Операции неделимы и взаимно исключают друг друга. Терминология железнодорожная. Процесс устанавливает семафор на время критической секции. Другие процессы в это время приостановлены и ждут освобождения семафора.

Значение семафора – неотрицательное целое число.

Операция V(s): <s = s +1> увеличивает значение семафора.

Операция P(s) <await (s>0) s = s – 1>. Проверяет значение s и ждет, пока оно не станет положительным, после чего уменьшает его на 1. Ожидание является пассивным, то есть процесс приостанавливается. Операция V переводит один из ожидающих процессов в состояние работы.

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

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

Применение семафоров.

1. Критические секции. Можно использовать двоичный семафор.

sem s = 1

….

P(s)

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

V(s)

….

1. Барьерная синхронизация. – синхронизация по времени окончания опреаций в разных процессах.

Требования – ни один из процессов не должен перейти барьер, пока к нему не подошли все процессы. Например для двух процессов

Sem arrive1 = 0; arrive 2 = 1;

//1 процесс

….

V(arrive1); //сигнал о прибытии

P(arrive2); // ожидание другого процесса

…

//2 процесс

….

V(arrive2);

P(arrive1);

Для n процессов нужен массив семафоров. Каждый процесс выполняет операцию V для своего элемента массива, а затем выполняет P для всех остальных семафоров.

1. Задача о производителе и потребителе. Производитель производит данные, помещая их в кольцевой буфер из n записей. Потребитель их обрабатывает, выбирая из буфера. Если буфер заполняется, то производитель должен подождать. Если буфер пуст, то ждет потребитель

Var Buf: array [ 0..N-1] of Type;

Var head, tail: integer;

empty, full: sem;

head:=0; tail:=0; empty:=n; full =0;

//производитель

While true do

Begin

//создать data

P(empty);

Buf[tail]:=data; tail:=(tail+1) mod n;

V(full);

End

//потребитель

While true do

Begin

P(full);

Result:=Buf[head]; head:=(head+1) mod n;

V(empty);

End

Семафоры играю роль счетчиков ресурсов. Empty считает количество пустых ячеек, Full – заполненных.

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

1. Задача об обедающих философах.

Пять философов сидят за круглым столом. Между ними по вилке. Каждый ест двумя вилками. Каждый некоторе время думает, затем пытается поесть. Нужно смоделировать их поведение. Программа должна избегать ситуации, когда все голодны, но каждый взял по вилке – сл-но ни один не может взять обе вилки.

Цикл будет такой

While True do

Begin

// думаем

sleep(random(1000));

//берем вилки

// едим

sleep(random(1000));

//отдаем вилки

end;

Каждая вилка – семафор (или критическая секция).можно завести массив семафоров. Чтобы не было взаимной блокировки, нужно чтобы были философы которые сначала берут правую вилку и были, которые берут левую. Например, четные и нечетные.

1. Задача о читателях и писателях. Есть БД. Есть процессы читатели, которые могут одновременно читать данные. Есть писатели, которые имеют искл. доступ к данным. Читатели конкурируют с писателями, писатели – между собой.

Есть два способа решения этой задачи. Первый – как задачи взаимного исключения.

Для этого заведем переменные nr – число читателей, семафоры rw – для исключения доступа к БД читателей и писателей, m – для блокировки доступа читателей к nr.

// Writer

…

P(rw);

//пишем

V(rw)

…

//reader

P(m)

nr: = nr +1;

if nr =1 then P(rw); //первый читатель – блокировать доступ

V(m)

Читать

P(m);

Nr:=nr-1;

if nr = 0 then V(rw); // последний читатель – снять доступ.

V(m)

Преимущество будет у читателей. Пока они читают, писатели не смогут писать. Новый читатель получает преимущество перед писателем. Это несправедливо.

Рассмотрим решение с помощью условной синхронизации.

Будем подсчитывать число писателей nw и читателей nr. Множество хороших состояний параллельной программы будет описываться следующим условием

((nr = 0) or (nw =0)) and (nw<=1)

Отсюда получается код для читателей и писателей

//reader

<await (nw=0) nr:=nr+1>

чтение

< nr:=nr-1>

//writer

<await (nw=0 and nr=0) nw:=nw+1>

чтение

< nw:=nw-1>

Для реализации await используем метод передачи эстафеты. Этот метод позволяет реализовать любую условную синхронизацию.

С каждым условием свяжем семафор и счетчик с нулевыми нач значениями. Семафор будем использовать для приостановки процесса пока условие защиты не станет истинным. Счетчик будет хранить число приостановленных процессов. Для нашей задачи нужно два семафора r и w, а также два счетчика dr и dw – количество ожидающих писателей и читателей. Семафор е используется для входа в неделимые блоки (кр.секции).

Для выход используется следующий код (Signal). Он сбрасывает один из трех семафоров – если нет писателей, но есть ожидающий читатель – семафор r, если нет писателей и читателей – w, иначе – e.

If (nw=0) and (dr >0)

Begin dec(dr); V(r) end

Else

If (nr=0) and (nw=0) and (dw >0)

Begin dec(dw); V(w) end

Else

V(e)

//reader

p(e);

if (nw>0)

begin

dr:=dr+1;

v(e);

p(r)

End;

Nr=Nr+1;

Signal;

//читаем

P(e);

Nr:=Nr-1;

Signal;

//writer

p(e);

if (nr>0 or nw>0)

begin

dw:=dw+1;

v(e);

p(w)

End;

Nw=Nw+1;

V(e);

//пишем

P(e);

Nw:=Nw-1;

Signal;

Из трех семафоров в листинге только один может иметь значение 1. Каждый код начинается с P и заканчивается V - сл-но код выполняется со взаимным исключением.

Метод называется метод передачи эстафеты из-за способа выработки сигнала семафорами. Процесс внутри кр секции получил эстафету. При выходе из кр секции он передает эстафету следующему ожидающему процессу. Если ни один из процессов не ожидает, то эстафету получает следующий процесс, взывавший P(e).

Сигнальный код можно упростить, учитывая неравенства для dr,dw,nr,nw в каждом месте программы. Получим код

//reader

p(e);

if (nw>0) // or (dw>0)

begin

dr:=dr+1;

v(e);

p(r)

End;

Nr=Nr+1;

if dr>0 then begin dr = dr-1; V(r) end

else v(e);

//читаем

P(e);

Nr:=Nr-1;

If (nr=0) and (dw >0)

Begin dec(dw); V(w) end

Else V(e)

//writer

p(e);

if (nr>0 or nw>0)

begin

dw:=dw+1;

v(e);

p(w)

End;

Nw=Nw+1;

V(e);

//пишем

P(e);

Nw:=Nw-1;

If (dr >0)

Begin dec(dr); V(r) end

Else

If (dw >0)

Begin dec(dw); V(w) end

Else

V(e)

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

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