При ассемблировании возможно незапланированное переключение контекста:
Thr1 Thr2
MOV EAX, [g_x]
ADD EAX, 1
MOV [g_x], EAX
Из-за “расщепления” команды inc возможно возникновение “условия гонки” (race condition). Нужно, чтобы эти три ассемблерные команды выполнялись как единое целое.
Для того, чтобы достичь неделимости арифметических операций в WinAPI имеется функция Interlock.
DWORD WinAPI Thr1(PVOID) {
InterlockExchangeAdd (&g_x, 1);
return 0;
}
Эта функция и другие функции семейства Interlock работают в пользовательском режиме.
Варианты реализаций:
- Блокирование прерываний;
- Блокирование шины;
- В системе команд используется специальная инструкция TestAndSetLock (TSL), при помощи которой можно реализовать обобщенную критическую секцию.
enter: TSL Reg, [Lock]
CMP Reg, #0;;0 значит, что текущий поток выполнил блокировку
JNE enter;и ему можно войти в критическую секцию
RET
…
leave: MOV [Lock], #0
RET
TSL неразрывным образом изменяет значение по адресу Lock на ненулевое число, при этом в регистр помещается старое значение. Такой метод называется Спин-Блокировка.
|
|
Еще один вариант Спин-Блокировки:
BOOL g_ResInUse = FALSE;
вход: while (InterlockedExchange(&g_ResInUse, TRUE) = = TRUE) sleep(0);
выход: InterlockedExchange(&g_ResInUse, FALSE);
Эти протоколы входа/выхода присваивают значение, переданное во втором параметре InterlockedExchange(), переменной, адрес которой указан в первом, и возвращают значение до модификации.
PVOID InterlockedExchangePointer(PVOID * pvTarget, PVOID * pvValue);
Long InterlockedComparePointer(PLONG plDest, LONG lExchange, Long
lComparand)
Алгоритм Петерсона для Спин-Блокировки
Peterson, 1981г.
Алгоритм разрыва узла через обмен через файлы.
white (True) {
< протокол входа //enter() >;
< вход в критической секции >;
< протокол выхода //leave() >;
< код вне критической секции >;
}
Для обеспечения работоспособности требуется выполнение 4-х условий:
- Процессы не должны находиться одновременно в критических областях;
- Не должно быть предположений о скорости выполнения процесса;
- Процесс вне критической секции не должен блокировать другие процессы;
- Ели процесс начал выполнять протокол входа, то он рано или поздно должен войти в критическую секцию.
Проанализируем это:
int lock = 0
void enter() {
while (lock!= 0) /*ждем*/;
lock = 1;
}
void leave() { lock = 0; }
Гарантируют ли такие протоколы условия взаимного исключения? Нет. Введем переменную, которая определяет, чья очередь входа в критическую секцию.
int turn = 0;
while (TRUE) { -//-
while (turn!= 0) /*ждем*/; while (turn!= 1) -//-
< критическая секция > -//-
turn = 1; turn = 0;
< вне критической секции >; -//-
} -//-
Этим способом обеспечивается условие взаимного исключения (1 условие). Не выполняется 3 условие: застряв вне критической секции, процесс 0 блокирует процесс 1.
int turn = 0;
int interested[2] = { FALSE, FALSE };
|
|
void enter(int process) {
int other = 1–process;
interested[process] = TRUE;
turn = process;
while (turn = = process && interested[other] = = TRUE) /*ждем*/;
}
void leave(int process) { interested [process] = FALSE; }
Этот способ обеспечивает соблюдение всех условий.
Идея алгоритма:
- модификацию условий нужно выполнять до проверки, а не после;
- для каждого из процессов нужно завести по флагу (массив Interested[]); ненулевое значение флага свидетельствует о том, что соответствующий процесс готов войти в критический участок, поэтому каждый из процессов перед входом в критический участок должен выполнять проверку while (Interested = = TRUE) и ждать;
- если два процесса одновременно начинают выполнять проверку, то возникает тупик. Для разрешения тупика («разрыва узла») вводится вспомогательная переменная turn, которая в случае конфликта разрешает ввод в критическую секцию только одному процессу.
Так же известен алгоритм Lamport.