13) Задача о критической секции. Алгоритм Петерсона для двух процессов. (условия задачи, объяснение принципа алгоритма)

Алгоритм разрыва узла через обмен через файлы.

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;

w hile (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, которая в случае конфликта разрешает ввод в критическую секцию только одному процессу.

14) Эффект отталкивания (голодания). (пример, модификатор volatile)

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

Особенности:

• volatile BOOL g_fFinished = FALSE;

/*volatile – загружаем значение из памяти при каждом обращении к переменной (отключает оптимизации компилятора).*/

int main( ) {

CreateThread (…, CalcFunc,…);

While (g_fFinished = = FALSE);

}

DWORD WINAPI CalcFunc (PVOID) {

…

g_fFinished = TRUE;

}

Если не будем использовать ключевое слово volatile, то возникнет риск того, что значения флага загрузятся в регистр процессора перед вычислением while, и в дальнейшем проверяться будет значение из регистра, т.е. ждущий процесс никогда не увидит окончания вычислений.

• Thr1 Thr2

При реализации спин-блокировки возможна ситуация, когда поток длительное время опрашивает условие входа E, периодически это условие оказывается истинным, тем не менее, поток не может войти в критический участок. Происходит «отталкивание» (starvation, голодание). Можно решить, добавив Sleep(0) в конец Thr1.