Операционни системи

4 (5). Конкуренция: взаимно изключване и синхронизация

    Централни теми при изграждане на ОС:
  - многопрограмна работа;
  - многопроцесорна работа;
  - разпределени процеси.
    Конкуренция на процеси - 3 различни аспекта:
  - много на брой активни приложения едновременно;
  - структурирани приложения - за повишаване на ефективността някои приложения се програмират като множества от конкурентни процеси;
  - структурата на ОС - често като множество от конкурентни процеси.

5.1 Принципи на конкуренцията.
    Пример.
    Процесите P1 и P2 използват обща "ехо" функция (напр. за отпечатване на екрана на натиснат клавиш) - без и със защита на функцията. ОС може да прекъсва изпълнението на функцията след всеки оператор.
char chin, chout;
void echo()
{
  getchar(chin);
  chout = chin;
  putchar(chout);
}
    От клавиатурата на  P1 се въвежда 'A', а от клавиатурата на P2 - 'B'. Възможни са следните сценарии за изпълнение на процесите P1 и P2, които използват функцията "ехо".

  А. Без защита : ОС може да прекъсва изпълнението на функцията след всеки оператор.
 

// PROCESS P1
void echo()
{
  getchar(chin);
................
................
  chout = chin;
  putchar(chout);
.................
} 		// PROCESS P2
void echo()
{
...............
  getchar(chin);
  chout = chin;
...............
...............
  putchar(chout);
} 		value of chin
...
...
...
A
B
B
B
B 		value of chout
...
...
...
...
B
B
B
B

т.е. P1(getchar)-> P2(getchar)-> P2(=)-> P1(=)-> P1(putchar)-> P2(putchar)-> и двата процеса извеждат 'B' -> BAD.
      Б. Със защита: ОС не може да прекъсва изпълнението на функцията.
P1(getchar)-> P2(echo, недостъпна!)-> P1(=)-> P1(putchar)-> P2(=)-> P2(putchar)-> и процесът P1 извежда 'A', а процесът P2 - 'B' -> OK.
    Извод - управление на достъпа до съвместно използвана функция!

** Задължения на ОС.
    1. Следене на активните прцеси.
    2. Отпускане на ресурси за активните процеси:
          - процесорно време;
          - памет;
          - файлове;
          - I/O устройства.
    3. Предпазване на данни и ресурси на всеки процес от неправомерна намеса на друг процес.
    4. Резултатът от работата на един процес трябва да е независим от скоростта на изпълнението му, както и от скоростта на изпълнение на другите процеси.

** Взаимодействие на процеси.
* Състезание между процесите за ресурси.
    Взаимно изключване (ВИ) - mutual exclusion: критичен ресурс (КР) и критична секция (КС).
    Пример: ресурс принтер.
/* program mutual_exclusion */
const int n; /* number of processes */
void P(int i)
{ while (true)
  { enter_critical(i);
    <critical section>
    exit_critical(i);
    <remainder>
  }
}
void main( )
{ parbegin(P(1), P(2), ..., P(n)); }

    Какво лошо може да се случи?
    Мъртва хватка (МХ) - deadlock.
    Дадени са процеси P1 и P2 и ресурси R1 и R2. За да завършат, двата процеса трябва да използват и двата ресурса. Ако процесът P1 заеме ресурс R1 и процес P2 заеме ресурс R2,  тогава нито един от процесите не може да завърши - P1 чака да бъде освободен ресурс R2, а P2 чака да бъде освободен ресурс R1 - МХ.
    Гладна смърт (ГС) - starvation.
    Дадени са процеси P1, P2 и P3 и ресурс R. И трите процеса използват дадения ресурс. Нека P1 и P2 да се изпълняват периодично, т.е. заемат ресурса за определено време, след което го освобождават. При сценарии
P1(R)-> P2(R)-> P1(R)-> P2(R)-> P1(R)-> ...
P3 чака да бъде освободен ресурса и това чакане може да продължи неопределено време - ГС.

*  Кооперация между процеси чрез поделяне, съгласуване на данните.
    Два процеса, като използват общи променливи a и b, поддържат връзката a = b.
int a=1, b=1;

PROCESS P1
...
    a = a + 1;
    b = b + 1;
... 		PROCESS P2
...
    b = 2 * b;
    a = 2 * a;
...
    При сценарии (без защита):
        P1(a = a + 1)-> P2(b = 2 * b)-> P2(a = 2 * a)-> P1(b = b + 1)
стойностите на двете променливи са съответно
(1,1) ->  (2,1)      ->   (2,2)      ->   (4,2)      ->    (4,3)
и връзката a = b е нарушена. Отново възниква необходимост от защита - от ВИ.

** Изисквания за ВИ:
    1. Само един процес е в КС секция относно даден КР.
    2. Процес извън КС може да прекъсва, без това да влияе на останалите процеси.
    3. Всеки процес, чакащ за влизане в КС, трябва да може да влезе в КС (с крайно време за чакане).
    4. Ако няма процес в КС (относно КР), всеки процес, който иска този КР, трябва да може да влезе в КС незабавно.
    5. Няма ограничения за брой процеси, чакащи за КР и няма ограничения за времето и честотата на използване на този ресурс.
    6. Един процес може да остане в КС за крайно време.

5.2 Взаимно изключване: софтуерен подход.
** Алгоритъм на Декер.
        Първи опит:
int turn; /* =0 or =1 */

// PROCESS P0
...
while(turn!=0) nothing();
 <critical section>
turn = 1;
... 		// PROCESS P1
...
while(turn!=1) nothing();
 <critical section>
turn = 0;
...
    Щастлив сценарии - последователно влизане в КС:
P0 -> P1 -> P0 -> P1 -> P0 -> P1 -> ...
    Проблем - когато единия процес няма интерес за влизане в КС, т.е. P1 иска 2 пъти последователно да влезе в КС.
P0 -> P1 -> P1(чака, turn има стойност 1) -   P1 се блокира.
Това се случва и при грешка в единия процес

        Втори опит:
bool flag[2] = {false, false};

// PROCESS P0
...
while(flag[1]) nothing();
flag[0] = true;
 <critical section>
flag[0] = false;
... 		// PROCESS P1
...
while(flag[0]) nothing();
flag[1] = true;
 <critical section>
flag[1] = false;
...
    Щастлив сценарии:
P0(while)-> P0(=)-> P0(КС)-> P0(=)-> P0(while)-> P0(=)-> P0(КС)-> P0(=)->
P1(while)-> P1(=)-> P1(КС)-> P1(=)-> ...
    Проблем при следния сценарии:
P0(while(flag[1]) намира го false)->
P1(while(flag[0]) намира го false)->
P0(flag[0]=true и влиза в КС) ->
P1(flag[1]=true и влиза в КС) -> BAD.
И двата процеса са в КС - няма ВИ.

    Трети опит:
bool flag[2];

// PROCESS P0
...
flag[0] = true;
while(flag[1]) nothing();
 <critical section>
flag[0] = false;
... 		// PROCESS P1
...
flag[1] = true;
while(flag[0]) nothing();
 <critical section>
flag[1] = false;
...
    Щастливи сценарии:
P0(=t)-> P0(while)-> P0(КС)-> P1(=t)-> P1(while,чака)-> P0(=f)-> P1(КС)-> P1(=f)-> P1(=t)-> P1(while)-> P0(КС)-> P0(=t,чака)-> P1(=f)-> P0(КС)-> ...
ВИ е гарантирано.

    Проблем - възможно e МХ при следния сценарии:
P0(flag[0] = true)-> P1(flag[1] = true)-> P1(while)-> P0(while)-> MX.

** Алгоритъм на Петерсон - решение на задачата за ВИ.
bool flag[2] = {false,false};
int turn;

void P0()
{
 while (true)
 {
  flag[0] = true;
  turn = 1;
  while (flag[1] && turn==1)
                   nothing();
  <critical section>
  flag[0] = false;
  <remainder>
 }
} 		void P1()
{
 while (true)
 {
  flag[1] = true;
  turn = 0;
  while (flag[0] && turn==0)
                   nothing();
  <critical section>
  flag[1] = false;
  <remainder>
 }
}
void main()
{ flag[0] = false;
  flag[1] = false;
  parbegin(P0, P1);
}
    Масивът flag  показва заявка (интерес) за КС, променливата turn - кой в момента е в КС.  Ето и всички възможности за стойности на тези променлива:
flag[0] flag[1] turn
false false 0, 1 Няма интерес за КС.
false true 0, 1 P0 няма интерес за КС, P1 в КС.
true false 0, 1 P0 в КС, P1 няма интерес за КС.
true true 0 P0 в КС, P1 чака за КС.
true true 1 P1 в КС, P0 чака за КС.

5.3 Взаимно изключване: хардуера поддръжка.
** Непозволяване на прекъсвания - проблеми при многопроцесорни системи и неефективно използване на ресурси..

** Специални машинни команди. Функцията testset не реализирана хардуерно и връща стойност за един такт на процесора, т.е. не може да се прекъсва.
bool testset(int &i)
{ if (i == 0)
  { i = 1; return true; }
           return false;
}
const int n; /* number of processes */
int bolt;
void P(int k)
{ while(true)
  {
   do nothing(); while (!testset(bolt));
   <critical section>
   bolt = 0;
   <remainder>
  }
}
void main()
{ parbegin(P(1),P(2),...,P(n)); }
    Когато променливата bolt има стойност 1, има процес в КС и функцията testset връща стойност false - т.е. всички процеси, които имат интерес за КС, чакат. Когато променливата bolt има стойност 0, няма процес в КС, функцията testset връща стойност false , като стойността на bolt става 1. Процес, който излиза от КС, променя стойността на bolt на 0. Гарантирано е ВИ, няма опасност от МХ.

5.4 Семафори
   Основен принцип: два или повече процеса се кооперират в смисъл на прости сигнали така, че един процес може да бъде спрян на определено място и да остане в това състояние, докато не получи съответен сигнал.
   За да изпрати сигнал чрез семафора  s, процесът трябва да изпълни примитива (процедурата) signal(s). За да получи сигнал от семафор s, процесът трябва да изпълни wait(s)  и ако съответният сигнал още не е изпратен, да остане в състояние на чакане (блокиран).

    Дефинирани са 3 действия с променливата семафор:
      1. Инициализира се с неотрицателно число.
      2. Примитива wait(s) намалява стойността на s с 1. Ако стойността стане отрицателна, процесът (изпълняващ wait) се блокира.
      3. Операцията signal(s) увеличава стойността на s с 1. Ако стойността не е положителна, процесът (блокиран с wait) се разблокира.
    Примитивите wait и signal се предполат неделими, т.е. те не могат да бъдат прекъсвани.

struct semaphore {
 int count;
 queueType queue;
};

void wait(semaphore s)
{
 s.count--;
 if (s.count < 0)
 {
  place_this_process_in_s.queue;
  block_this_process;
 }
} 		void signal(semaphore s)
{
 s.count++;
 if (s.count <= 0)
 {
  remove_a_process_from_s.queue(P);
  place_the_process_on_ready_list(P);
 }
}

    Пример ???.

Ако s.count е отрицателно число (3, 6 и 7), -s.count е броят на чакащите на семафора  s процеси, т.е. броят на процесите в опашката s.queue.  Ако s.count е положително число (1), s.count е броят на процесите, които могат да минат през семафора, преди той да се затвори. Опашката s.queue е празна. Ако s.count е 1 (1), то един процес минава и затваря семафора. Ако s.count е 0 (2, 4 и 5), то идващ процес се блокира и отива на опашката.

   Двоични семафори - семафорът има две състояния - отворен (1) и затворен (0):
struct binary_semaphore {
int value; /* = 0, 1 */
queueType queue;
};

void waitB(binary_semaphore s)
{
 if (s.value==1) s.value=0;
 else
 {
  place_this_process_in_s.queue;
  block_this_process;
 }
} 		void signalB(binary_semaphore s)
{
 if (s.queue.is_empty()) s.value=1;
 else
 {
  remove_a_process_from s.queue(P);
  place_process_on_ready_list(P);
 }
}

** Взаимно изключване - решение на задачата за ВИ със семафори.
/* program mutual_exclusion */
const int n; /* number of processes */
semaphore s = 1;
void P(int i)
{
 while (true)
 {
  wait(s);
  <critical section>
  signal(s);
  <remainder>
 }
}
void main()
{
 parbegin(P(1), P(2),..., P(n));
}
    Стойността на променливата s.count има следния смисъл:
- s.count >= 0 е броят на процесите, които могат да изпълнят примитива wait(s)без да бъдат блокирани (и няма изпълнение на signal(s));
- s.count < 0 е броят на процесите, чакащи в s.queue.


5.5 Задача за производител/потребител.
    Един или няколко производители генерират данни (записи, символи) и ги поставят в един буфер. Един потребител взема по една данна от буфера. Само един агент (производител или потребител) има достъп да буфера в даден момент.
* Първи опит за решение със семафори:
/* program producer_consumer */
int n;
binary_semaphore s = 1;
binary_semaphore delay = 0;
     void producer()
     {
      while (true)
      {
/*p1*/ produce();
/*p2*/ waitB(s);
/*p3*/ append(); /*КС*/ 
/*p4*/ n++;
/*p5*/ if (n==1) signalB(delay);
/*p6*/ signalB(s);
      }
     } 		     void consumer()
     {
      waitB(delay);
      while (true)
      {
/*c1*/ waitB(s);
/*c2*/ take();    /*КС*/
/*c3*/ n--;
/*c4*/ signalB(s);
/*c5*/ consume();
/*c6*/ if (n==0) waitB(delay);
      }
     }
void main()
{ n = 0;
  parbegin(producer, consumer);
}
    Семафорът s служи за взаимно изключване, семафорът delay - за чакане на потребителя, когато буферът е празен.
Проблем:
 
     
n
delay
1
Init
  
0
0
2
Producer
КС
0->1
0->1
 p1->p2->p3->p4->p5->p6
3
Consumer
waitB(delay)
1
1->0
4
Consumer
КС
1->0
0
 c1->c2->c3->c4->c5->
5
Producer
КС
0->1
0->1
 p1->p2->p3->p4->
6
Consumer
if (n==0) waitB(delay)
1
1
 ->c6
7
Consumer
КС
1->0
1
 c1->c2->c3->c4->c5->
8
Consumer
if (n==0) waitB(delay)
0
1->0
 ->c6
9
Consumer
КС
-1
0
 c1->c2-> !!!

* Втори опит - решение:
int n;
binary_semaphore s = 1;
binary_semaphore delay = 0;

void producer()
{
 while (true)
 {
  produce();
  waitB(s);
  append();n++;
  if (n==1) signalB(delay);
  signalB(s);
 }
} 		void consumer()
{ int m;  /* a local variable */
  waitB(delay);
  while (true)
  {
   waitB(s);
   take(); n--;  m = n;
   signalB(s);
   consume();
   if (m==0) waitB(delay);
  }
}
void main()
{ n = 0;
  parbegin (producer, consumer);
}
    Варианти на задачата - безкраен буфер и краен кръгов буфер.

5.6 Задачата на бръснаря.

5.7 Задачата на писатели/читатели.
    Данни (файл, блок от паметта) се използват от няколко процеса. Някои от процесите само четат тези данни - читатили, а други само променят данните - писатели. Следните условия трябва да се спазват:
   1. Произволен брой читатели могат да четат едновременно данните;
   2. Само един писател може да пише данни;
   3. Ако писател пише, никой читател не може да чете.
    Ако всеки процес може и да пише и да чете, общото решение за ВИ работи.
    Ако един процес може или само да чете, или само да пише - общото решение е неприемливо, а съществуват и по-ефективни решения.

** Предимство на читателите.
/* program readers_and_writers */
int readcount;
semaphore x = 1, wsem = 1;

void reader()
{ while (true)
  {
   wait(x);
   readcount++;
   if (readcount==1) wait(wsem);
   signal(x);
   READUNIT();
   wait(x);
   readcount--;
   if (readcount==0) signal(wsem);
   signal(x);
  }
} 		void writer()
{
 while (true)
 {
  wait(wsem);
  WRITEUNIT();
  signal(wsem);
 }
}
 
 

 
void main()
{ readcount = 0;
  parbegin(reader, writer);
}

** Предимство на писателите.
/* program readers_and_writers */
int readcount, writecount;
semaphore x = 1, y = 1, z = 1, wsem = 1, rsem = 1;
 

void reader()
{ while (true)
  {
   wait(z);
   wait(rsem);
   wait(x);
   readcount++;
   if (readcount==1) wait(wsem);
   signal(x);
   signal(rsem);
   signal(z);
   READUNIT();   /* {КС} */
   wait(x);
   readcount--;
   if (readcount==0) signal(wsem);
   signal(x);
  }
} 		void writer()
{
 while (true)
 {
  wait(y);
  writecount++;
  if (writecount==1) wait(rsem);
  signal(y);
  wait(wsem);
  WRITEUNIT();  /* КС */
  signal(wsem);
  wait(y);
  writecount--;
  if (writecount==0) signal(rsem);
  signal(y);
 }
}
void main()
{
 readcount = writecount = 0;
 parbegin (reader, writer);
}
    Общо предназначение на семафорите:
- x - коректната работа с обща глобална променлива readcount;
- y - коректната работа с обща глобална променлива writecount;
- z - осигурява предимство на писателите;
- rsem - свободно за четене (няма писател в КС);
- wsem - свободно за писане (няма читатели в КС).
    Двойката семафори z и rsem осигуряват най-много един читател на опашка за семафора rsem, което позволява преминаването на първият писател през този семафор. Така се дава предимството на писателите.
 
Състояния на системата: Състояния на семафорите wsem, rsem и z:
Само читатели в системата - wsem - 1
- няма опашки
Само писатели в системата - rsem - 1
- опашка от писатели на wsem
Много читатели четат, идва писател - wsem е затворен (от първия читател); rsem е отворен;
- писателят минава и затваря rsem;
- писателят чака на wsem;
- следващият идващ читател затваря z и чака на rsem;
- всички други идващи читатели чакат на z;
- последният читател, завършил четенето, отваря wsem;
Последен писател пише, чакат читатели - wsem е затворен (от пишещия писател);
- опашките са както в предишния случай;
- писателят свършва и отваря wsem;
- писателят отваря rsem;
- читателят, чакащ на rsem минава, отваря z и чете;