Алгоритмы синхронизации

колбасу на хлеб

Активность - последовательное выполнение ряда действий, направленных на достижение определенной цели

Активность : приготовление бутерброда

Атомарные или неделимые операции

a b c d e f

Псевдопараллельное выполнение (режим разделения времени) :

?

a b c d e f

a b d c e f

a b d e c f

a b d e f c

. . .

d e f a b c

данных возможны разные результаты
Детерминированный набор – при одинаковых начальных данных всегда один результат

P:

x=2

y=x-1

Q:

x=3

y=x+1

(x, y):

(2, )

(2, 1)

(3, 1)

(3, 4)

(2, )

(3, )

(3, 4)

(3, 2)

(2, 3)

(2, 1)

= {x, w}

Выходные переменные W1 = {x}
W2 = {y}

R(P)={u, v, x, w}

W(P)={x, y}

Если:

W(P) ∩ W(Q) = {ø}

2) W(P) ∩ R(Q) = {ø}

3) R(P) ∩ W(Q) = {ø}

то набор активностей {P, Q} является детерминированным

состязание процессов за использование переменной x

В недетерминированных наборах всегда встречается race condition (состояние гонки, состояние состязания)

Избежать недетерминированного поведения при неважности очередности доступа можно с помощью взаимоисключения (mutual exclusion)

за пивом

Уходит за пивом

Покупает 6 бут. пива

Покупает 6 бут. пива

Покупает 6 бут. пива

Приносит пиво

Приносит пиво

Приносит пиво

Достает 6 бут. пива

Приходит в комнату

Приходит в комнату

section

remainder section

}

предположений об относительных скоростях выполнения и числе процессоров
Выполняется условие взаимоисключения (mutual exclusion) для критических участков
Выполняется условие прогресса (progress)
Выполняется условие ограниченного ожидания (bound waiting)

все прерывания

remainder section

}

Обычно используется внутри ОС

section

}

Нарушается условие взаимоисключения

Shared int lock = 0;

lock = 1;

while (some condition) {

while (lock);

critical section

lock = 0;

remainder section

}

lock = 1;

|

section

turn = 1-i;

remainder section

}

Нарушается условие прогресса

Shared int turn = 0;

while (some condition) {

while (turn != 1);

critical section

turn = 0;

remainder section

}

while (turn != 0);

turn = 1;

Pi

P1

P0

Shared int turn = 1;

Условие взаимоисключения выполняется

0;

remainder section

}

1-я часть условия прогресса выполняется

Shared int ready[2] = {0, 0};

while (ready [1]);

ready[0] = 0;

Pi

P1

P0

Условие взаимоисключения выполняется

ready[i] = 1;

2-я часть условия прогресса нарушается

while (some condition) {

critical section

remainder section

}

while (ready [0]);

ready[1] = 0;

ready[1] = 1;

ready[0] = 1;

Shared int ready[2] = {1, 0};

Shared int ready[2] = {1, 1};

== 1-i);

critical section

ready[i] = 0;

remainder section

}

Shared int ready[2] = {0, 0};

while (ready [1] && turn == 1);

ready[0] = 0;

Pi

P1

P0

Все 5 условий выполняются

ready[i] = 1;

while (some condition) {

critical section

remainder section

}

while (ready [0] && turn == 0);

ready[1] = 0;

ready[1] = 1;

ready[0] = 1;

Shared int turn;

turn = 0;

turn = 1 - i;

turn = 1;

*a;

*a = 1;

return tmp;

}

Нарушается условие ограниченного ожидания

Shared int lock = 0;

while (some condition) {

while (Test-And-Set (&lock));

critical section

lock = 0;

remainder section

}