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

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 aq. B, A - Q rel. B, A - P ex.
 2. Q aq. B, A - P bl. A - Q rel. B, A - P  ex.
 3. Q aq. B - P aq. A - deadlock !
 4. P aq. A - Q aq. B - deadlock !
 5. P aq. A, B - Q bl. B - P rel. A, B - Q ex.
 6. P aq. A, B - P rel. A, B - Q ex.
Възможен сценарии за избягване на МХ:
PROCESS  P
...
Get A
...
Release A
...
Get B
...
Release B
...
--- FIGURE 6.3 ---
** Reusable Resources (RR)
Примери на RR: процесори, 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 (CR)
Примери за CR: прекъсвания, сигнали, съобщения, данни в I/O буферите.
Пример:
P1 P2
...
Receive (P2)
...
Send (P2) 		...
Receive (P1)
...
Send (P1)
МХ се получава, ако ОС работи с blocking receive.
** Условия за МХ
  1. Взаимно изключване - само един процес може да владее ресурс в даден момент
  2. Владея и чакам (очакване на ресурси) - един процес блокира (владее) един ресурс, докато чака за друг
  3. Няма отстъпки (непреразпределение) - един ресурс не може да бъде насилствено освободен от владението на процес
    МХ може да се появи при тези 3 условия, но може и да не се появи. Следващото условие е достатъчно за поява на МХ.
  4. Циклично чакане -  затворена верига от процеси, като всеки процес владее пони един ресурс, за който чака следващият процес от веригата.
--- FIGURE 6.5 ---

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

6.3 Избягване на МХ
Два подхода при избягване на МХ:
  -- да не се стартира процес, който води до МХ
  -- да не се дава ресурс на процес, ако това води до МХ
Изисква се предварителна информация за необходимите расурси на всеки процес.
** Отказ за стартиране на процес
Дадени са:
 R  -- вектор на всички налични ресурси (m)
 V -- вектор на свободните ресурси (m)
 C -- матрица на исканията на всеки процес за всеки ресурс (m x n)
 A -- матрица на дадени на всеки процес ресурси (m x n)
Имаме следните равенства и неравенства:
    Ri = Vi + sumk(Aki), за всяко i
    Cki <= Ri, за всяко i
    Aki <= Cki, за всяко i
Процесът P(n+1) се стартира само ако
     Ri >= C(n+1)i + sumk(Cki), за всяко 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 Откриване на МХ
Дадена е:
Q -- матрица на исканията на всеки процес за всеки ресурс в даден момент (m x n)
** Алгоритъм за откриване на МХ:
   1. Маркираме процесите, които в A имат само 0;
   2. W = V;
   3. Намираме немаркиран процес, за който елементите на реда на Q са по-малки или равни на елементите на вектора W. Ако няма такъв, стоп.
   4. Wk = Wk + Aik, където 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;
var fork: array[0..4] of semaphore (:=1);
    i: integer;
procedure philosopher(i: integer);
begin
   repeat
     think;
     wait(fork[i]);
     wait(fork[(i+1) mod 5]);
     eat;
     signal(fork[(i+1) mod 5]);
     signal(fork[i]);
   forever
end;
begin
   parbegin
     philosopher(0);philosopher(1);
     philosopher(2);philosopher(3);
     philosopher(4)
   parend
end.
Решение със семафори:
program diningphilosophers;
var fork: array[0..4] of semaphore (:=1);
    room: semaphore (:=4);
    i: integer;
procedure philosopher(i: integer);
begin
   repeat
     think;
     wait(room);
     wait(fork[i]);
     wait(fork[(i+1) mod 5]);
     eat;
     signal(fork[(i+1) mod 5]);
     signal(fork[i]);
     signal(room);
   forever
end;
begin
   parbegin
     philosopher(0);philosopher(1);
     philosopher(2);philosopher(3);
     philosopher(4)
   parend
end.

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