9. Конкуренция: взаимно изключване и синхронизация
Принципи на конкуренцията.

Централни теми при изграждане на ОС:
  - многопрограмна работа;
  - многопроцесорна работа;
  - разпределени процеси.
    Конкуренция на процеси - 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. Един процес може да остане в КС за крайно време.