17. Семафорные примитивы Дейкстры. Решение задачи производителя и потребителя с помощью семафоров.

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

a) probieren P(s): if (s==0) –> блок, s=s-1

уменьшение семафора на 1 если он был больше нуля, в противном случае блокирует процесс до тех пор, пока семафор не увеличится, после чего процесс выводится из состояния блокировки, а семафор уменьшается. Увеличен семафор может быть любым другим процессом, выполнившим операцию V(s).

b) verhogen V(s): s=s+1

Мьютекс – двоичный семафор. Обычно мьютекс связан с критическим ресурсом, если ресурс свободен, то мьютекс равен 1, если ресурс занят – мьютекс равен 0.

Задача: В системе есть несколько процессов производителей данных размещающих эти данные в буфере объемом N и несколько процессов потребителей читающих данные из этого буфера. Требуется организовать совместную работу всех процессов, удовлетворяющую следующим условиям:

a) никакие два процесса не могут одновременно работать с буфером;

b) нельзя читать из пустого буфера;

c) нельзя писать в полный буфер.

Решение:

Semaphore mutex=1; semaphore empty=N; semaphore full=0;

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

while (true) { while (true) {

P (empty); P (full);

P (mutex); P (mutex);

write; read;

V (mutex); V (mutex);

V (full); V (empty);

remainder; } remainder; }

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

18. Монитор Хоара как примитив синхронизации высокого уровня.

Мониторы Хоара – структура ЯВУ схожа с классом ООП. Он может содержать переменные, которые являются критическим ресурсом, и функции-методы, которые могут использовать только свои входные аргументы и переменные монитора. Внутри монитора в конкретный момент может находиться только один процесс, т.е. для процесса вызвавшего метод монитора обеспечивается взаимное исключение. При компиляции функции-методы монитора дополняются прологом и эпилогом из семафоров.

Переменные состояния – переменные монитора, над которыми доступно две примитивных операции:

a) wait – блокирует процесс на данной переменной состояния до тех пор, пока другой процесс не произведет на данной переменной состояния операцию signal;

b) signal.

В отличии от семафора переменные состояния не имею памяти, поэтому если операция signal будет проведена на переменной состояния, на которую не заблокирован ни один процесс, то этот сигнал будет потерян.

Решение задачи производителя и потребителя с помощью мониторов.

Monitor M

{ state full;

state empty;

void get ()

{ read; }

void put ()

{ write; }}

M m; int count=0;

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

while (true) { while (true) {

if (count ==N) if (count ==N)

m.empty.wait; m.full.wait;

m.put(); m.get();

count++; count--;

m.full.signal; m.empty.signal;

remainder; } remainder; }