1) Семафоры

Дейкстра, 1965

Тип данных; число, выражающее количество отложенных сигналов активации или их отсутствие

down() - уменьшить количество сигналов активации, если S = 0, то заблокировать

up() - увеличить количество сигналов активации

Решение ППП с помощью семафоров

#define N 10

int mutex = 1;

int empty = N;

int full = 0;

void producer(void)

{

int item;

while (TRUE) {

item = produce_item();

down(&empty);

down(&mutex);

insert_item();

up(&mutex);

up(&full);

};}

void consumer(void)

{

int item;

while (TRUE) {

down(&full);

down(&mutex);

item = remove_item();

up(&mutex);

up(&empty);

consume_item(item);

};}

2) Мьютексы (mutex)

mutual exclusion

Упрощённый семафор с 2 состояниями

mutex_lock()

mutex_unlock()

3) Мониторы

Хоар, Хансен, 1974

Набор процедур, переменных и других структур данных, объединённых в особый пакет

Нет прямого доступа к данным внутри монитора

При обращении к монитору активным может быть только один процесс

Являются частью ЯП и должны поддерживаться компилятором

Синхронизация достигается переменными состояния и операциями wait() и signal()

wait(с) — блокирует вызывающий процесс

signal(c) — пробуждает процесс, заблокировавшийся на переменной состояния

Действие после signal(c):

Запустить разбуженный процесс и заблокировать вызвавший signal() (Хоар)

Процесс, вызвавший signal(), должен немедленно покинуть монитор (Хансен)

Запустить разбуженный процесс после того, как процесс, вызвавший signal(), отработает до конца

Если с переменной состояния не связано ни одного процесса, сигнал теряется

Решение ППП с помощью мониторов

monitor ProdCons

condition full, empty;

integer count;

procedure put(item:

integer);

begin

if count = N then

wait(full);

insert_item(item);

count := count + 1;

if count = 1 then

signal(empty);

end;

procedure get: integer;

begin

if count = 0 then wait(empty);

get := remove_item;

count := count-1;

if count = N-1 then signal(full);

end;

count:=0;

end monitor;

integer item;

procedure producer;

begin

while true do begin

item := produce_item;

ProdCons.put(item);

end;

end;

procedure consumer;

begin

while true do begin

item := ProdCons.get;

consume_item(item);

end;

end;

4) Очереди сообщений

send(destination, &message) — отправить сообщение указанному адресату

receive(source, &message) — получить сообщение из указанного источника. В случае отсутствия сообщения либо блокирует вызвавший процесс до получения сообщения, либо возвращает код ошибки

source/destination — либо PID процессов, либо адрес «почтового ящика»

Решение ППП с помощью очередей сообщений

#define N 100

void producer(void)

{

int item;

msg m;

while (TRUE) {

item = produce_item();

receive(consumer, &m);

build_msg(&m, item);

send(consumer, &m);

};

}

void consumer(void)

{

int item;

msg m;

for (int i=0; i<N; i++)

send(producer, &m);

while (TRUE) {

receive(producer, &msg);

item = extract_item(&m);

send(producer, &m);

consume_item(item);

};

}