Лекция №7. При ассемблировании возможно незапланированное переключение контекста:

При ассемблировании возможно незапланированное переключение контекста:

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 работают в пользовательском режиме.

Варианты реализаций:

1. Блокирование прерываний;
2. Блокирование шины;
3. В системе команд используется специальная инструкция 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-х условий:

1. Процессы не должны находиться одновременно в критических областях;
2. Не должно быть предположений о скорости выполнения процесса;
3. Процесс вне критической секции не должен блокировать другие процессы;
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; }

Этот способ обеспечивает соблюдение всех условий.

Идея алгоритма:

1. модификацию условий нужно выполнять до проверки, а не после;
2. для каждого из процессов нужно завести по флагу (массив Interested[]); ненулевое значение флага свидетельствует о том, что соответствующий процесс готов войти в критический участок, поэтому каждый из процессов перед входом в критический участок должен выполнять проверку while (Interested = = TRUE) и ждать;
3. если два процесса одновременно начинают выполнять проверку, то возникает тупик. Для разрешения тупика («разрыва узла») вводится вспомогательная переменная turn, которая в случае конфликта разрешает ввод в критическую секцию только одному процессу.

Так же известен алгоритм Lamport.

Дата добавления: 2014-12-07