Презентация на тему Синхронизация и взаимоисключения. (Тема 9)

атомарна, неделима

P: a b c
Q: d e

f

Псевдопараллельное выполнение PQ:
a b c d e f
а b c d e f
a b d c e f
a b d e c f
a b d e f c
a d b c e f
......
d e f a b c

(3, 4), (2, 1), (2, 3) и (3, 2)

Набор

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

Q:
пересечение W(P) и W(Q) пусто,
пересечение W(P) с R(Q) пусто,

пересечение R(P) и W(Q) пусто,
тогда выполнение P и Q детерминировано.

+: детерминированность выполнения
-: слишком жёсткие условия ? фактически невзаимодействующие активности

что он имеет race condition (состояние гонки , состояние

состязания)
Устранение race condition = эксклюзивное право доступа к данным для каждого процесса
Каждый процесс, обращающийся к разделяемым ресурсам, исключает для всех других процессов возможность одновременного общения с этими ресурсами, если это может привести к недетерминированному поведению набора процессов. Такой прием называется взаимоисключением (mutual exclusion).

которой может привести к возникновению race condition для определенного

набора программ.
Чтобы исключить эффект гонок по отношению к некоторому ресурсу (критическому ресурсу), необходимо организовать работу так, чтобы в каждый момент времени только один процесс мог находиться в своей критической секции, связанной с этим ресурсом.

section пролог критической секции
critical section

критическая секция
exit section эпилог критической секции
remainder section остальная часть программы
}

чисто программным способом на обычной машине, не имеющей специальных

команд взаимоисключения.
Не должно существовать никаких предположений об относительных скоростях выполняющихся процессов или числе процессоров, на которых они исполняются.
Если процесс Pi исполняется в своем критическом участке, то не существует никаких других процессов, которые исполняются в соответствующих критических секциях - Условие взаимоисключения
Процессы, которые находятся вне своих критических участков и не собираются входить в них, не могут препятствовать другим процессам входить в их собственные критические участки. Если нет процессов в критических секциях и имеются процессы, желающие войти в них, то только те процессы, которые не исполняются в remainder section, должны принимать решение о том, какой процесс войдет в свою критическую секцию. Такое решение не должно приниматься бесконечно долго -Условие прогресса
Не должно возникать неограниченно долгого ожидания для входа одного из процессов в свой критический участок. От того момента, когда процесс запросил разрешение на вход в критическую секцию, и до того момента, когда он это разрешение получил, другие процессы могут пройти через свои критические участки лишь ограниченное число раз - Условие ограниченного ожидания

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

разрешить все прерывания
remainder section
}

Сбой в критической секции приведет к неработоспособности системы (с запрещёнными прерываниями)
Применяется как пролог и эпилог к критическим секциям внутри самой операционной системы

{
while(lock); lock = 1;
critical

section
lock = 0;
remainder section
}

Нарушено условие взаимоисключения: неатомарный пролог приводит к попаданию в критическую секцию двух процессов

condition) {
while(turn != i);

critical section
turn = 1-i;
remainder section
}
Взаимоисключение гарантируется, процессы входят в критическую секцию строго по очереди: P0, P1, P0, P1, P0, ...
Не удовлетворяет условию прогресса. Например, если значение turn равно 1, и процесс P0 готов войти в критический участок, он не может сделать этого, даже если процесс P1 находится в remainder section

condition) {
ready[i] = 1;

while(ready[1-i]);
critical section
ready[i] = 0;
remainder section
}
Нарушает условие прогресса: при одновременном выполнении неатомарного пролога с чередованием оба процесса бесконечно ждут друг друга на входе в критическую секцию.

{0, 0};
shared int turn;
while (some condition) {

ready[i] = 1;
turn =1-i;
while(ready[1-i] && turn == 1-i);
critical section
ready[i] = 0;
remainder section
}

Удовлетворяет всем условиям

while (some condition) {
choosing[i] = true;

number[i] = max(number[0], ..., number[n-1]) + 1;
choosing[i] = false;
for(j = 0; j < n; j++){
while(choosing[j]);
while(number[j] != 0 && (number[j],j) < (number[i],i));
}
critical section
number[i] = 0;
remainder section
}

(a,b) < (c,d), если a < c
или если a == c и b < d
max(a0, a1, ...., an) – это число k такое, что
k >= ai для всех i = 0, ...,n

int tmp = *target;
*target = 1;

return tmp;
}

shared int lock = 0;

while (some condition) {
while(Test_and_Set(&lock));
critical section
lock = 0;
remainder section
}

int tmp = *a;
*a

= *b;
*b = tmp;
}

shared int lock = 0;
int key;

while (some condition) {
key = 1;
do Swap(&lock,&key);
while (key);
critical section
lock = 0;
remainder section
}