l06

6. Конкуренция: "мъртва хватка" и "гладна смърт" (deadlock and starvation)

6.1 Принцини на "мъртва хватка" (МХ).

PROCESS P
...
Get A
...
Get B
...
Release A
...
Release B
... PROCESS Q
...
Get B
...
Get A
...
Release B
...
Release A
...

--- FIGURE 6.2 ---
    Възможни са следните последователности на изпълнение:
1. Q aquires B,A -- Q releases B,A -- P executes
2. Q aquires B,A -- P blocks A    -- Q releases B,A -- P executes
3. Q aquires B   -- P aquires A    -- deadlock !
4. P aquires A   -- Q aquires B    -- deadlock !
5. P aquires A,B -- Q blocks B    -- P releases A,B -- Q executes
6. P aquires A,B -- P releases A,B -- Q executes
    Възможен сценарии за избягване на МХ:
PROCESS P
...
Get A
...
Release A
...
Get B
...
Release B
...
--- FIGURE 6.3 ---
** Многократно използваеми ресурси (Reusable Resources).
    Примери: процесори, I/O канали, основна и допълнителна памет, устройства, структури от данни като файлове, бази данни и семафори.
    Пример 1: Два процеса P и Q използват ресурси магнитен диск D и магнитна лента T.

Process P

Step	Action
p0	Request (D)
p1	Lock (D)
p2	Request (T)
p3	Lock (T)
p4	Perform function
p5	Unlock (D)
p6	Unlock (T)

Process Q

Step	Action
q0	Request (T)
q1	Lock (T)
q2	Request (D)
q3	Lock (D)
q4	Perform function
q5	Unlock (T)
q6	Unlock (D)

    МХ се получава при следната редица:
    p0 p1 q0 q1 p2 q2
    Пример 2: При ресурс 200КB памет, два процеса.

P1	P2
... Request 80 KB ... Request 60 KB	... Request 70 KB ... Request 80 KB

се конкурират за нея. При страртиране и на двата процеса се получава МХ при второто искане за памет.
** Еднократно използваеми ресурси (Consumable Resources).
Примери: прекъсвания, сигнали, съобщения, данни в I/O буферите.
Пример: Два процеса си обменят съобщения.

P1	P2
... Receive (P2) ... Send (P2)	... Receive (P1) ... Send (P1)

МХ се получава, ако ОС работи с blocking receive.
** Условия за МХ.
1. Взаимно изключване (mutual exclusion) - само един процес може да владее ресурс в даден момент.
2. Владея и чакам (очакване на ресурси, hold and wait) - един процес блокира (владее) един ресурс, докато чака за друг.
3. Няма отстъпки (непреразпределение, no preemtion) - един ресурс не може да бъде насилствено освободен от владението на процес.
МХ може да се появи при тези 3 условия, но може и да не се появи. Следващото условие е достатъчно за поява на МХ.
4. Циклично чакане (circular wait) - затворена верига от процеси, като всеки процес владее пони един ресурс, за който чака следващият процес от веригата.
--- FIGURE 6.5 ---

6.2 Предпазване (prevention) от МХ.
** Взаимно изключване.
Не може да бъде избягнато.
** Владея и чакам.
Процесът чака за всички необходими ресурси - неефективно
** Няма отстъпки (no preemtion).
** Циклично чакане.

6.3 Избягване (avoidance) на МХ.
    Два подхода при избягване на МХ:
-- да не се стартира процес, който води до МХ;
-- да не се дава ресурс на процес, ако това води до МХ.
    Изисква се предварителна информация за необходимите расурси на всеки процес.
** Отказ за стартиране на процес.
    Дадени са:
R -- вектор на всички налични ресурси (m);
V -- вектор на свободните ресурси (m);
C -- матрица на исканията на всеки процес за всеки ресурс (m x n);
A -- матрица на дадени на всеки процес ресурси (m x n).
    Имаме следните равенства и неравенства:
R_i = V_i + sum_k(A_ki), за всяко i;
C_ki <= R_i, за всяко i;
A_ki <= C_ki, за всяко i.
    Процесът P_n+1 се стартира само ако R_i >= C_n+1,i + sum_k(C_ki), за всяко i.
    Тази стратегия е твърде песимистична - предполага се, че всички процеси ще искат всички необходими им ресурси едновременно.
** Отказ от даване на ресурс - алгоритъм на банкера.
    Състояние на системата - матрицата A.
    Безопасно (сигурно) състояние - съществува такава последователност от изпълнение на процесите, при която всички процеси завършват успешно (няма МХ). Опасно (несигурно) състояние - всяко друго.
    Пример на безопасно състояние и изпълнение на процесите:
Начално състояние

`Матрица C` `R1 R2 R3` `P1 3 2 2` `P2 6 1 3` `P3 3 1 4` `P4 4 2 2`	`Матрица A` `R1 R2 R3` `P1 1 0 0` `P2 6 1 2` `P3 2 1 1` `P4 0 0 2`
`Вектор R` `R1 R2 R3` `9 3 6`	`Вектор V` `R1 R2 R3` `0 1 1`

P2 е завършил

`Матрица C` `R1 R2 R3` `P1 3 2 2` `P2 0 0 0` `P3 3 1 4` `P4 4 2 2`	`Матрица A` `R1 R2 R3` `P1 1 0 0` `P2 0 0 0` `P3 2 1 1` `P4 0 0 2`
	`Вектор V` `R1 R2 R3` `0 1 1`

P1 е завършил

`Матрица C` `R1 R2 R3` `P1 0 0 0` `P2 0 0 0` `P3 3 1 4` `P4 4 2 2`	`Матрица A` `R1 R2 R3` `P1 0 0 0` `P2 0 0 0` `P3 2 1 1` `P4 0 0 2`
	`Вектор V` `R1 R2 R3` `7 2 3`

P3 е завършил

`Матрица C` `R1 R2 R3` `P1 0 0 0` `P2 0 0 0` `P3 0 0 0` `P4 4 2 2`	`Матрица A` `R1 R2 R3` `P1 0 0 0` `P2 0 0 0` `P3 0 0 0` `P4 0 0 2`
	`Вектор V` `R1 R2 R3` `9 3 4`

Пример на опасно състояние и изпълнение на процесите:
Начално състояние

`Матрица C` `R1 R2 R3` `P1 3 2 2` `P2 6 1 3` `P3 3 1 4` `P4 4 2 2`	`Матрица A` `R1 R2 R3` `P1 1 0 0` `P2 5 1 1` `P3 2 1 1` `P4 0 0 2`
`Вектор R` `R1 R2 R3` `9 3 6`	`Вектор V` `R1 R2 R3` `1 1 2`

На P1 се дават R1 и R3

`Матрица C` `R1 R2 R3` `P1 3 2 2` `P2 6 1 3` `P3 3 1 4` `P4 4 2 2`	`Матрица A` `R1 R2 R3` `P1 2 0 1` `P2 5 1 1` `P3 2 1 1` `P4 0 0 2`
`Вектор R` `R1 R2 R3` `9 3 6`	`Вектор V` `R1 R2 R3` `0 1 1`

На всеки процес му трябва R1 за да завърши, а такъв няма. Това не е МХ, но може да се появи МХ. Ако някой процес освободи R1, МХ се избягва.
* Алгоритъм за избягване на МХ.

6.4 Откриване (detection) на МХ
    Дадено е:
R -- вектор на всички налични ресурси (m);
V -- вектор на свободните ресурси (m);
Q -- матрица на исканията на всеки процес за всеки ресурс в даден момент (m x n);
A -- матрица на дадени на всеки процес ресурси (m x n).
** Алгоритъм за откриване на МХ:
   1. Маркираме процесите, които в A имат само 0;
   2. Създаваме но вектор W = V;
   3. Намираме немаркиран процес, за който елементите на реда на Q са по-малки или равни на елементите на вектора W. Ако няма такъв, стоп.
   4. W_k = W_k + A_ik, където i е индекса на намерения в т. 3 процес. Изпълнява се т. 3.
МХ: при завършване на алгоритъма има немаркирани процеси.
Пример:

`Матрица Q` `R1 R2 R3 R4 R5` `P1 0 1 0 0 1` `P2 0 0 1 0 1` `P3 0 0 0 0 1` `P4 1 0 1 0 1`	`Матрица A` `R1 R2 R3 R4 R5` `P1 1 0 1 1 0` `P2 1 1 0 0 0` `P3 0 0 0 1 0` `P4 0 0 0 0 0`
`Вектор R` `R1 R2 R3 R4 R5` `2 1 1 2 1`	`Вектор V` `R1 R2 R3 R4 R5` `0 0 0 0 1`

1. Маркираме P4.
2. W = (0 0 0 0 1)
3. Маркираме P3.
4. W = (0 0 0 1 1)
3. P1 и P2 не отговарят на условията. Стоп.
Има немаркирани процеси - МХ.
** Възстановяване.
След като МХ е открита е необходимо възстановяване на системата.
   1. Прекъсване (завършване, kill) на всички процеси, участващи в МХ.
   2. Връщане на всички МХ-процеси в предишно състояние и стартирането им отново.
   3. Последователно прекъсване на МХ-процесите, докато алгоритъмът даде липса на МХ.
   4. Последователно преразпределение на ресурси, докато алгоритъмът даде липса на МХ.

6.5 Интегрирана стратегия
-- Групиране на ресурсите в класове от различни ресурси.
-- Използване на наредба на ресурсите във всеки клас.
-- Използване на подходящи алгоритми за всеки клас
Например:
-- Swapping space: предпазване от МХ с вземане на всички необходими ресурси
-- Processor resources: избягване на МХ с обявяване на необходимите ресурси
-- Main memory: преразпределение на ресурси

6.6 Задачата за обядващите философи
Пет философа прекарват живота си в мислене и ядене. Те седят около кръгла маса, на която има 5 чинии със спагети и 5 вилици. Когато мисли, философ не контактува с колегите си. От време на време огладнява и се опитва да вземе (последователно!) двете вилици, които са от двете стране на чинията му. Ако успее, той започва да яде с двете вилици, а след като свърши с яденето, връща вилиците и започва да мисли отново.
Първи опит за тривиално решение със семафори.
// program diningphilosophers
semaphore fork[5] = {1,1,1,1,1};
int i;
void philosopher(int i)
{
while(true)
{
think;
wait(fork[i]);
wait(fork[(i+1)%5]);
eat;
signal(fork[(i+1)%5]);
signal(fork[i]);
}
{

void main()
{
parbegin(philosopher(0), philosopher(1),
philosopher(2), philosopher(3),
philosopher(4));
}
Втори опит - решение със семафори:
// program diningphilosophers;
semaphore fork[5] = {1,1,1,1,1};
semaphore room = 4;
int i;
void philosopher(int i)
{
while(true)
{
think;
wait(room);
wait(fork[i]);
wait(fork[(i+1)%5]);
eat;
signal(fork[(i+1)%5]);
signal(fork[i]);
signal(room);
}
}

void main()
{
parbegin(philosopher(0), philosopher(1),
philosopher(2), philosopher(3),
philosopher(4));
}

6.7 Механизми на UNIX за конкуренция.
    Най-важните механизми за междупроцесорна комуникация и синхронизация са: pipes, съобщения и обща памет.
** Pipes.
    Краен (кръгов) буфер позволяващ на два процеса да комуникират помежду си, използвайки модала производител-потребител.
** Съобщения.
    Двете функции (system calls) msgsnd и msgrcv осигуряват размяна на съобщения между процесите. Всеки процес поддържа крайна опашка, подобна на пощенска кутия.
** Обща памет.
** Семафори.
    Един семафор се състои от следните елементи:
- текуща стойност на семафора;
- ID на процеса, последен използвал семафора;
- брой процеси, чакащи за стойност на семафора, по-голяма от текущата;
- брой процеси, чакащи за стойност на семафора 0.
    Със всеки семафор се създава и опашка от процеси, чакащи за този семафор.
    Семафорите се създават в множества, като едно множество се състои от един или повече семафора. Функцията (system call) semctlвдига семафорите от зададено множество
** Сигнали.
    Софтуерен механизъм за информиране на процесите за асинхронни събития. Както прекъсване, но без приоритети (всички сигнали са равни).
    Някои по-важни сигнали в SVR4:

Value	Name	Description
02	SIGINT	прекъсване
03	SIGQUIT	спиране на процес от потребителя и core dump
04	SIGILL	невалидна инструкция
09	SIGKILL	kill, спиране на процес
10	SIGBUS	bus error
11	SIGSEGV	segmentation violation, адрес извън виртуалната памет
19	SIGPWR	power failure