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.