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

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

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

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

PQ: 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)

v}
R2 = {x, w}
Выходные переменные W1 = {x}
W2 = {y}
R(P)={u,

W(P)={x, y}

Если:

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

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

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

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

– состязание процессов за использование переменной x
В недетерминированных наборах всегда

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

пивом
Уходит за пивом
Уходит за пивом
Покупает 6 бут. пива
Покупает 6 бут.

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

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

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

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

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

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

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

section
exit section
remainder section
}

программным
Нет предположений об относительных скоростях выполнения и числе процессоров
Выполняется условие

section
разрешить все прерывания
remainder section
}
Обычно используется внутри ОС

0;
remainder section
}
Нарушается условие взаимоисключения
Shared int lock = 0;
lock = 1;
while

while (lock);

critical section

lock = 0;

remainder section

}

lock = 1;

|

i);
critical section
turn = 1-i;
remainder section
}
Нарушается условие прогресса
Shared int turn =

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] =

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};

turn == 1-i);
critical section
ready[i] = 0;
remainder section
}
Shared int ready[2] =

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

while (some condition) {

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

critical section

lock = 0;

remainder section

}

tmp = *a;
*a = *b;
*b = tmp;
}
Нарушается условие ограниченного ожидания
Shared

while (some condition) {

do Swap (&lock, &key);

critical section

lock = 0;

remainder section

}

int key = 0;

key = 1;

while (key);