5b. Конкуренция: взаимно изключване и синхронизация
5.4 Семафори
Основен принцип: два или повече процеса се кооперират
в смисъл на прости сигнали така, че един процес може да бъде прекъснат
на определено място и да остане в това състояние докато не получи
специален сигнал.
За да изпрати сигнал чрез семафора s,
процесът трябва да изпълни примитива (процедурата) signal(s).
За да получи сигнал от семафор s,
процесът трябва да изпълни wait(s)
и ако съответният сигнал още не е изпратен, да остане в състояние на чакане
(прекъснат).
Дефинирани са 3 действия с променливата семафор:
1. Инициализира се с 0;
2. Операцията wait намалява
стойността на s с 1. Ако стойността
стане отрицателна, процесът се блокира.
3. Операцията signal увеличава
стойността на s с 1. Ако стойността
не е положителна, процесът се разблокира.
type semaphore = record
count: integer;
queue: list of process
end;
var s: semaphore;
wait(s):
s.count := s.count - 1;
if (s.count < 0) then
begin
place
this process in s.queue;
block
this process
end;
|
signal(s):
s.count := s.count + 1;
if (s.count <= 0) then
begin
remove
a process P form
s.queue;
place
process P on
ready list
end;
|
Двоични семафори:
type semaphore = record
value: (0,1);
queue: list of process
end;
var s: semaphore;
waitB(s):
if (s.value==1) then
s.value:=0
else begin
place
this process in s.queue;
block
this process
end;
|
signalB(s):
if (s.queue is empty) then
s.value:=1
else begin
remove
a process P form
s.queue;
place
process P on
ready list
end;
|
** Взаимно изключване
Решение на задачата за ВИ със семафори:
Program mutualexclusion;
const n =
...; (* number of processes *)
var s: semaphore (:=1);
procedure
P(i: integer);
begin
repeat
wait(s);
<critical
section>
signal(s);
<remainder>
forever
end;
begin (*main
program*)
parbegin
P(1); P(2); ... P(n);
parend
end.
** Задачата за производител/потребител
Един или няколко производители генерират данни (записи, символи) и
ги поставят в един буфер. Един потребител взема по една данна от буфера.
Само един агент (производител или потребител) има достъп да буфера в даден
момент.
producer:
repeat
produce item v;
b[in] := v;
in := in + 1;
forever;
|
consumer:
repeat
while in <= out do { nothing
};
w:=b[out];
out := out + 1;
consume item w;
forever;
|
--- FIGURE 5.12
---
** Приложение на семафорите
program producerconsumer;
var n: integer;
s: (*binary*) semaphor
(:=1);
delay: (*binary*) semaphor
(:=0);
procedure producer;
begin
repeat
produce;
waitB(s);
append;
n := n + 1;
if (n==1) then signalB(delay);
signalB(s);
forever;
end;
|
procedure consumer;
begin
waitB(delay);
repeat
waitB(s);
take;
n := n - 1;
signalB(s);
consume;
if (n==0) then waitB(delay)
forever;
end;
|
procedure consumer;
var m: integer; (* local var*)
begin
waitB(delay);
repeat
waitB(s);
take;
n := n - 1;
m := n;
signalB(s);
consume;
if (m==0) then waitB(delay)
forever;
end;
|
begin
n:=0;
parbegin
producer;
consumer;
parend
end.
Семафорът s
служи за взаимно изключване, семафорът delay
- за чакане на потребителя когато буферът е празен.
--- FIGURE
5.16 ---
** Задачата на бръснаря
--- FIGURE
5.19 ---
5.5 Монитори
** Монитор със сигнал
Мониторите са програмни модули, състоящи се от една или повече процедури,
инициализация и локални данни. Главни характеристики:
1. Локалните данни са достъпни само от процедурите на
монитора.
2. Един процес "влиза в монитора" като извика някоя от
процедурите му.
3. Само един процес може да се изпълнява в монитора, всеки
друг процес чака да се "освободи" монитора.
Променливи на условия (condition variables). Функции с тези променливи:
cwait(c): Прекратяване
изпълнението на процеса с условие c. Мониторът е достъпен за дрег
процес
csignal(c): Въобновяване
на изпълнението на процеса, прекратени с cwait
със същото условие.Ако има няколко такива процеса се избира един от тях,
ако няма - нищо не се прави.
Разлика със семафорите - сигналът се "загубва", ако няма чакащи процеси
за този сигнал.
--- FIGURE
5.22 ---
program producerconsumer;
monitor boundede
buffer;
buffer: array[0..N]
of
char; {space
for N items}
nextin, nextout: integer;
{buffer pointers}
count: integer;
{number of items in buffer}
notfull, notempty: condition;
{for synchronization}
procedure append
(x: char);
begin
if count
= N then cwait(notfull);{buffer
is full; avoid overflow}
buffer[nextin] := x;
nextin := nextin +
1 mod N;
count
:= count + 1;
{onemore item in buffer}
csignal(notempty);
{resume any waiting consumer}
end;
procedure take
(x: char);
begin
if count
= 0 then cwait(notempty);{buffer
is empty; avoid underflow}
x := buffer[nextout];
nextout := nextout + 1
mod N;
count := count - 1;
{one fewer item in buffer}
csignal(notfull);
{resume any waiting producer}
end;
begin {monitor body}
nextin:=0;
nextout:=0; count:=0; {buffer
initially empty}
end;
procedure producer;
var x: char;
begin
repeat
produce(x);
append(x);
forever
end;
procedure cosumer;
var x: char;
begin
repeat
take(x);
consume(x);
forever
end;
begin (* main program *)
parbegin
producer;
consumer;
parend
end.
** Монитори със съобщения и разпространение
5.6 Предаване на съобщения
Синхронизация и комуникация са двата проблема на взаимодействащи си
процеси - взаимно изключване и обмен на информация. Двете задачи се решават
с обмен на съобщения. Дефинират се два примитива (процедури):
send (destination, message)
receive (source, message)
Съществуват различини възможности за реализация на тези 2 процидури:
| Synchronization |
Addressing |
Format |
| Send |
Direct |
Content |
| blocking |
send |
Length |
| nonblocking |
receive |
fixed |
| Receive |
explicit |
variable |
| blocking |
implicit |
|
| nonblocking |
Indirect |
|
| test for arrival |
static |
Queuing Discipline |
|
dynamic |
FIFO |
|
ownership |
Priority |
** Синхронизация
Send - или процесът се блокира, докато събощението бъде получено, или
не
Receive - ако съобщението е изпратено, то се получава и процесът продължава,
ако не е или
процесът се блокира да получавене на съобщението или продължава, изоставяйки
опитите за получаването му.
3 комбинации са възможни:
--- Blocking send, blocking receive
--- Nonblocking send, blocking receive - най-често срещане, при грешка,
могат де се генерират много съобщения
--- Nonblocking send, nonblocking receive
** Адресиране
--- FIGURE
5.24 ---
** Формат на съобщенията
--- FIGURE
5.25 ---
** Дисциплина на опашките
5.7 Задачата на писатели/читатели
Данни (файл, блок от паметта) се използват от няколко процеса. Някои
от процесите само четат тези данни - читетили, а други само променят данните
- писатели. Следните условия трябва де се спазват:
1. Произволен брой читатели могат да четат едновременно
данните;
2. Само един писател може да пише във файла;
3. Ако писател пише, никой читател не може да чете.
Ако всеки процес може и да пише и да чете, общото решение за ВИ работи.
Ако един процес може или само да чете, или само да пише - общото решение
е неприемливо, а съществуват и много по-ефективни решения.
** Предимство на читателите
program readersandwriters;
var readcount: integer;
x, wsem: semaphore
(:=1);
procedure reader;
begin
repeat
wait(x);
readcount
:= readcount + 1;
if
(readcount == 1) then wait(wsem);
signal(x);
READUNIT;
whait(x);
readcount
:= readcount - 1;
if
(readcount == 0) then signal(wsem);
signal(x);
forever
end;
procedure writer;
begin
repeat
wait(wsem);
WRITEUNIT;
signal(wsem);
forever
end;
begin
readcount := 0;
parbegin
reader;
writer;
parend
end.
** Предимство на писателите
program readersandwriters;
var readcount, writecount: integer;
x,y,z, wsem, rsem:
semaphore (:=1);
procedure reader;
begin
repeat
wait(z);
wait(rsem); wait(x);
readcount
:= readcount + 1;
if
(readcount == 1) then wait(wsem);
signal(x);
signal(rsem); signal(z);
READUNIT;
whait(x);
readcount
:= readcount - 1;
if
(readcount == 0) then signal(wsem);
signal(x);
forever
end;
procedure writer;
begin
repeat
wait(y);
writecount
:= writecount + 1;
if
(writecont == 1) then wait(rsem);
signal(y);
wait(wsem);
WRITEUNIT;
signal(wsem);
wait(y);
writecount
:= writecount - 1;
if
(writecont == 0) then signal(rsem);
signal(y);
forever
end;
begin
readcount, writecount :=
0;
parbegin
reader;
writer;
parend
end.
---- Решение на задачата с размяна на съобщения
procedure readri;
var rmsg: message;
begin
repeat
rmsg :=
i;
send(readrequest,
rmsg);
receive(mboxi,
rmsg);
READUNIT;
rmsg :=
i;
send(finished,
rmsg);
forever
end;
procedure writerj;
var rmsg: message;
begin
repeat
rmsg :=
i;
send(writerequest,
rmsg);
receive(mboxj,
rmsg);
WRITEUNIT;
rmsg :=
i;
send(finished,
rmsg);
forever
end;
procedure controller;
begin
repeat
if (count
> 0) do
begin
if (not empty (finished)) then
begin
receive(finished, msg);
count := count + 1;
end else
if (not empty (writerequest)then
begin
receive(writerequest, msg);
writer.id := msg.id;
count := count - 100;
end else
if (not empty (readrequest)then
begin
receive(readrequest, msg);
count := count - 1;
send(msg.id, "OK");
end;
end;
if (count==0)
do
begin
send(writer.id, "OK");
receive(finished, msg);
count := 100
end;
while (count<0)
do
begin
receive(finished, msg);
count := count + 1;
end;
forever
end.