2014-02-24
1629
Решение проблемы взаимного исключения. Алгоритм Петерсона.
Решение проблемы взаимного исключения. Строгое чередование.
3. Строгое чередование.
while(TRUE)
{
while(turn);
critical_region();
turn = 1;
noncritical_region();
}
while(TRUE)
{
while(!turn); //активное ожидание
critical_region();
turn = 0;
noncritical_region();
}
Переменная turn, изначально равная 0, отслеживает, чья очередь входить в критическую область. Постоянная проверка значения переменной, в ожидании некоторого значения, называется активным ожиданием и является бесцельной тратой процессорного времени. Используется только в случае небольшого времени ожидания. Блокировка, использующая активное ожидание, называется спин-блокировкой. Недостаток: допустим, процесс 1 вышел из критической области и выполняет работу вне ее. Процесс 0 попадает в критическую область, быстро выполняет ее, передает очередь процессу 1, быстро выполняет свою некритическую секцию и возвращается к активному ожиданию. В этот момент оба процесса находятся в некритической области и процесс 1 блокирует процесс 0, что нарушает условие №3.
int turn;
int interested[2];
void enter_region(int process)
{
int other;
other = 1 - process;
interested[process] = TRUE;
turn = process;
while (turn == process && interested[other] == TRUE); // активное ожидание
}
void leave_region(process)
{
interested[process] = FALSE;
}
Прежде чем войти в критическую область, процесс вызывает процедуру enter_region со своим номером в качестве параметра. После выхода из критической области процесс вызывает процедуру leave_region и разрешает другому процессу войти в критическую область. Этот алгоритм является достаточно надежным, но использует активное ожидание.
Команда TSL (Test and Set lock) - это решение требуют части аппаратного обеспечения. Некоторые компьютеры могут иметь команду tsl rg, lock. Команда считывает в регистр содержимое переменной lock, а в переменную lock сохраняет некоторое ненулевое значение. При этом гарантируется, что операция считывания и сохранения слова неделима (атомарная операция). Это означает, что во время выполнения команды не может произойти переключение контекста и другой процесс не сможет обратиться к слову lock, пока команда не выполнена до конца.
enter_ko:
tsl rg, lock
cmp rg, 0
jne enter_region
ret
leave_ko:
mov lock, 0
ret
Прежде чем попасть в критическую область, процесс вызывает процедуру enter_region, которая выполняет активное ожидание до снятия блокировки, устанавливает новую блокировку и возвращает управление. Алгоритм надежен, однако использует активное ожидание.
