l05a

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

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

5.1 Принципи на конкуренцията
* Трудности при "изчакване" и "застъпване":
1. Съвместно използане на общи ресурси, напр. глобална променлива.
2. Оптимално разпределяне на ресурси, напр. след искане (и даване) на ресурс и процесът влязъл (по някаквоа причина) в състояние преустановен.
3. Откриване на грешки - неповторяеми резултати, зависят от конкретната работа на ОС.
* Пример с 2 процеса, използващи обща "ехо" функция - без и със защита на функцията:
void echo()
{
getchar(chin);
chout = chin;
putchar(chout);
}

void echo()
{
getchar(chin);
................
................
chout = chin;
putchar(chout);
.................
} void echo()
{
...............
getchar(chin);
chout = chin;
...............
...............
putchar(chout);
}

Възможни са следните сценарии за процеси 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. Резултатът от работата на един процес трябва да е независим от скоростта на изпълнението му, както и от скоростта на изпълнение на другите процеси.
** Взаимодействие на процеси.
-- Състезание между процесите за ресурси.
Взаимно изключване (ВИ) - mutual exclusion: критичен ресурс (КР) и критична секция (КС)
Пример: принтер
/* program mutualexclusion */
const int n = /* number of processes */ ;
void P(int i)
{
while (true)
{
entercritical(i);
/* critical section */;
exitcritical(i);
/* remainder */;
}
}
void main( )
{ parbegin(P(R1), P(R2), . . ., P(Rn));
}
Мъртва хватка (МХ) - deadlock: процеси P1 и P2 и ресурси R1 и R2.
Гладна смърт (ГС) - starvation: процеси P1, P2 и P3 периодично използват ресурс R.
-- Кооперация между процеси чрез поделяне, съгласуване на данните
2 процеса поддържат връзката a=b
P1: a = a + 1;
    b = b + 1;
P2: b = 2*b;
    a = 2*a;
необходимост от ВИ.
-- Кооперация между процеси чрез комуникация.
ВИ не е актуално, МХ и ГС не са изключени!
** Изисквания за ВИ:
1. Само един процес е в КС секция относно даден КР.
2. Процес извън КС може да прекъсва, без това да влияе на останалите процеси.
3. Всеки процес, чакащ за влизане в КС, трябва да може да влезе в КС (с крайно време за чакане).
4. Ако няма процес в КС (относно КР), всеки процес, който иска този КР, трябва да може да влезе в КС незабавно.
5. Няма ограничения за брой процеси, чакащи за КР и няма ограничения за времето и честотата на използване на този ресурс.
6. Един процес може да остане в КС за крайно време.

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

// PROCESS P0
.
.
while (turn != 0) {nothing};
<critical section>
turn = 1;
. // PROCESS P1
.
.
while (turn != 1) {nothing};
<critical section>
turn = 0;
.

Проблеми:
-- последователно влизане в КС;
-- при грешка в единия процес и другия се блокира
--- Втори опит
bool flag[2];

// 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 проверява flag[1] намира го false и прекъсва;
-- P1 проверява flag[0] намира го false и прекъсва;
-- P0 превключва flag[0] на true и влиза в КС;
-- P1 превключва flag[1] на true и влиза в КС ! -- няма ВИ
--- Трети опит
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;
.

Проблеми:
-- ВИ е гарантирано, но е възможно МХ.
--- Четвърти опит
bool flag[2];

// PROCESS P0
.
.
flag[0] = true;
while (flag[1])
{
flag[0] = false;
<delay for a short time>
flag[0] = true;
}
<critical section>
flag[0] = false;
. // PROCESS P1
.
.
flag[1] = true;
while (flag[0])
{
flag[1] = false;
<delay for a short time>
flag[1] = true;
}
<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
...
нито един от двата процеса може да влезе в критична секция.
--- Пети опит - решение
bool flag[2];
int turn;

void P0()
{
while (true)
{
flag[0] = true;
while (flag [1])
if (turn == 1)
{
flag[0] = false;
while (turn == 1)
/* do nothing */;
flag[0] = true;
}
/* critical section */;
turn = 1;
flag[0] = false;
/* remainder */;
}
} void P1()
{
while (true)
{
flag [1] = true;
while (flag[0])
if (turn == 0)
{
flag[1] = false;
while (turn == 0)
/* do nothing */;
flag[1] = true;
}
/* critical section */;
turn = 0;
flag[1] = false;
/* remainder */;
}
}

void main ()
{ flag[0] = false;
flag[1] = false;
turn = 1;
parbegin(P0, P1);
}
** Алгоритъм на Петерсон.
bool flag [2];
int turn;

void P0()
{
while (true)
{
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1)
/* do nothing */;
/* critical section */;
flag[0] = false;
/* remainder */;
}
} void P1()
{
while (true)
{
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0)
/* do nothing */;
/* critical section */;
flag[1] = false;
/* remainder */
}
}

void main()
{ flag [0] = false;
flag [1] = false;
parbegin(P0, P1);
}

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