l05

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.