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

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



5.1 Принципи на конкуренцията
*Трудности при "изчакване" и "застъпване":
  1. Съвместно използане на общи ресурси, напр. глобална променлива
  2. Оптимално разпределяне на ресурси, напр. след искане (и даване) на ресурс, процесът влиза в състояние прекъснат.
  3. Откриване на грешки - неповторяеми резултати
* Пример с 1 и 2 процесора, без и със защита на функцията
char a;
void echo()
{
  cin >> a;
  cout << a;
}
procedure echo;
var out, in: character;
begin
   input(in, keyboard);
   out := in;
   output(out, display);
end.
Възможни са следните сценарии за процеси P1 и P2:
  А. без защита
P1(input) - P2(input) - P2(:=) - P1(:=) - P1(output) - P2 (output)
  Б. със защита
P1(input) - P2(echo, недостъпна!) - P1(:=) - P1(output) - P2 (echo, OK!) - ...
Извод - управление на достъпа до съвместно използвана функция!
** Грижи на ОС
ОС трябва да има следните грижи:
    1. Следене на активните прцеси
    2. Отпускане на ресурси за активните процеси:
          - процесорно време;
          - памет;
          - файлове;
          - I/O устройства
    3. Предпазване на данни и ресурси на всеки процес от неправомерна намеса на друг процес
    4. Резултатът от работата на един процес трябва да е независим от ...
** Взаимодействие на процеси
--  Състезание между процесите за ресурси
Взаимно изключване (ВИ): критичен ресурс и критична секция (КС)
пример: принтер
Program mutualexclusion;
const n = ...; (* number of processes *)
procedure P(i: integer);
begin
   repeat
     entercritical(R);
     <critical section>
     exitcritical(R);
     <remainder>
   forever
end;
begin (*main program*)
   parbegin
      P(1);
      P(2);
      ...
      P(n);
   parend
end.
Мъртва хватка (МХ): процеси P1 и P2  и ресурси R1 и R2
Гладна смърт (ГС): процеси P1, P2 и P3 периодично използват ресурс R
--  Кооперация между процеси чрез поделяне, съгласуване на данните
 2 процеса поддържат връзката a=b
P1: a := a + 1;
    b := b + 1;
P2: b := 2*b;
    a := 2*a;
необходимост от ВИ
--  Кооперация между процеси чрез комуникация
ВИ не е актуално, МХ и ГС не са изключени!
** Изисквания за взаимно изключване


5.2 Взаимно изключване: софтуерен подход
** Алгоритъм на Декер
--- Първи опит
var turn: 0..1;
PROCESS 0
.
.
while (turn != 0) do {nothing}; 
 <critical section>
turn := 1;
.
PROCESS 1
.
.
while (turn != 1) do {nothing}; 
 <critical section>
turn := 0;
.
Проблеми:
-- последователно влизане в КС;
-- при грешка в единия процес и другия се блокира
--- Втори опит
var flag: array[0..1] of boolean;
PROCESS 0
.
.
while (flag[1]) do {nothing};
flag[0] := true;
 <critical section>
flag[0] := false;
.
PROCESS 1
.
.
while (flag[0]) do {nothing};
flag[1] := true;
 <critical section>
flag[1] := false;
.
Проблеми:
-- P0 проверява flag[1] намира го false и прекъсва;
-- P1 проверява flag[0] намира го false и прекъсва;
-- P0 превключва flag[0] на true и влиза в КС;
-- P0 превключва flag[1] на true и влиза в КС !!!! -- няма ВИ
--- Трети опит
var flag: array[0..1] of boolean;
PROCESS 0
.
.
flag[0] := true;
while (flag[1]) do {nothing};
 <critical section>
flag[0] := false;
.
PROCESS 1
.
.
flag[1] := true;
while (flag[0]) do {nothing};
 <critical section>
flag[1] := false;
.
ВИ е гарантирано, но е възможно МХ
--- Четвърти опит
var flag: array[0..1] of boolean;
PROCESS 0
.
.
flag[0] := true;
while (flag[1]) do 
begin
   flag[0] := false; 
   <delay for a short time> 
   flag[0] := true;
end;
 <critical section>
flag[0] := false;
.
PROCESS 1
.
.
flag[1] := true;
while (flag[0]) do 
begin
   flag[1] := false; 
   <delay for a short time> 
   flag[1] := true;
end;
 <critical section>
flag[1] := false;
.
ВИ е гарантирано, но е възможен следния сценарии:
-- P0 превключва flag[0] на true
-- P1 превключва flag[1] на true
-- P0 проверява flag[1]
-- P1 проверява flag[0]
-- P0 превключва flag[0] на false
-- P1 превключва flag[1] на false
-- P0 превключва flag[0] на true
-- P1 превключва flag[1] на true
... нито един от двата процеса може да влезе в критична секция
** Алгоритъм на Петерсон
var flag: array[0..1] of boolean;
    turn: 0..1;
procdure P0;
begin
  repeat
     tlag[0] := true;
     turn := 1;
     while (flag[1] and turn==1)
                 do { nothing };
     <critical section>
     flag[0] := false;
     <remainder>
  forever
end;
procdure P1;
begin
  repeat
     tlag[1] := true;
     turn := 0;
     while (flag[0] and turn==0)
                 do { nothing };
     <critical section>
     flag[1] := false;
     <remainder>
  forever
end;
begin
   flag[0] := false;
   flag[1] := false;
   turn := 1;
   parbegin
      P0; P1;
   parend;
end.


5.3 Взаимно изключване: хардуера поддръжка
** Непозволяване на прекъсвания
** Специални машинни команди
function testset(var i: integer): boolean;
begin
   if i = 0 then
   begin
      i := 1;
      testset := true;
   end else testset:=false;
end;
bool testset(int & i)

 if (i==0) 
 { 
  i = 1; return true;
 }
 return false;
}
program mutualexclusion;
const n = ...; (* number of processes *)
var bolt: integer;
procedure P(i: integer);
begin
   repeat
     repeat { nothing } until testset(bolt);
     <critical section>
     bolt := 0;
     <remainder>
   forever
end;
begin (*main program*)
   parbegin
      P(1);   P(2);   ...   P(n);
   parend
end.