- •ОперационныеЛекция 8. системы
- •Ситуация гонок (race condition)
- •Ситуация гонок (race condition)
- •Ситуация гонок (race condition)
- •Понятие критической секции и
- •Понятие критической секции и
- •Требования к механизмам
- •Взаимоисключение через
- •Взаимоисключение через
- •Требования к механизмам
- •Требования к механизмам
- •Взаимоисключение через
- •Требования к механизмам
- •Требования к механизмам
- •Алгоритм Петерсона
- •Требования к механизмам
- •Требования к механизмам
ОперационныеЛекция 8. системы
Ситуация гонок. Взаимоисключен ие. Критические секции
Ситуация гонок (race condition)
int a = 0;
for (int i = 0; i < 100; i+ +) {
a++;
}
…
MOV EAX, [a] INC EAX MOV [a], EAX
…
Ситуация гонок (race condition)
INST |
REG |
MEM |
MOV |
0 |
0 |
INC |
1 |
0 |
MOV |
1 |
1 |
a = 0 |
INST |
REG |
MEM |
MOV EAX, [a] |
|||
INC EAX |
MOV |
0 |
0 |
MOV [a], EAX |
INC |
1 |
0 |
MOV 1 1
Ситуация гонок (race condition)
INST |
REG |
MEM |
MOV |
0 |
0 |
INC |
1 |
0 |
MOV |
1 |
1 |
a = 0 |
INST |
REG |
MEM |
MOV EAX, [a] |
|||
INC EAX |
MOV |
0 |
0 |
MOV [a], EAX |
INC |
1 |
0 |
MOV 1 1
0 + 1 + 1 = 1?
Понятие критической секции и
взаимного исключения
Под критической секцией понимается такая часть программы, в которой производятся логически связанные манипуляции с разделяемыми данными.
Понятие критической секции и
взаимного исключения
Под критической секцией понимается такая часть программы, в которой производятся логически связанные манипуляции с разделяемыми данными.
Организация работы процессов, при которой два и более процесса не могут одновременно находиться в критических секциях, конфликтующих между собой, называется
взаимным исключением (mutual exclusion).
Требования к механизмам
взаимного исключения
Два и более процесса не должны ни при каких условиях находиться одновременно в критических секциях, конфликтующих между собой.
В программе не должно быть никаких предположений о скорости выполнения процессов и о количестве процессоров в системе.
Процесс, находящийся вне критических секций, не должен при этом быть причиной блокировки других процессов.
Недопустима ситуация «вечного ожидания», при которой некоторый процесс никогда не получит доступ в нужную ему критическую секцию (ресурсное голодание – resource starvation).
Процесс, заблокированный в ожидании разрешения на вход в критическую секцию, не должен расходовать
Взаимоисключение через
«блокировочную переменную»
while (isFree == 0) {}
isFree = 0; section(); isFree = 1;
Взаимоисключение через
«блокировочную переменную»
while (isFree == 0) {}
isFree = 0; section(); isFree = 1;
next:
mov eax, [isFree] cmp eax, 0
je next
mov [isFree], 0
…
Требования к механизмам
взаимного исключения
Два и более процесса не должны ни при каких условиях находиться одновременно в критических секциях, конфликтующих между собой.
В программе не должно быть никаких предположений о скорости выполнения процессов и о количестве процессоров в системе.
Процесс, находящийся вне критических секций, не должен при этом быть причиной блокировки других процессов.
Недопустима ситуация «вечного ожидания», при которой некоторый процесс никогда не получит доступ в нужную ему критическую секцию (ресурсное голодание – resource starvation).
Процесс, заблокированный в ожидании разрешения на вход в критическую секцию, не должен расходовать