Unix - статьи


         

в голову) можно описать схематически


Неатомарность спин-блокировок

Простейший алгоритм разделения доступа (который сразу приходит в голову) можно описать схематически с помощью следующей конструкции:

while (spin_lock == TRUE); spin_lock = TRUE; ... // Доступ к разделяемому ресурсу spin_lock = FALSE;

Проблема заключается в том, что этот алгоритм простых спин-блокировок (spin locks) не только прожорлив, но и не гарантирует надежного разграничения доступа. Допустим, что один процесс начал проверять значение переменной spin_lock, дождался того момента, когда оно станет равно FALSE и переходит к строке

spin_lock = TRUE;

В многозадачной и системе (особенно на нескольких процессорах) другой процесс, ожидающий доступа к разделяемому ресурсу, может «вклиниться» в тот момент, когда первый процесс уже проверил, но еще не изменил значение spin_lock. Второй процесс проверит значение, все еще равное FALSE и. В результате оба процесса окажутся в критической области и получат доступ к разделяемому ресурсу. Описанная проблема вызвана тем, что операция «проверить значение – изменить значение» неатомарна, то есть, ее выполнение может быть прервано другим процессом. Первый алгоритм, гарантирующий синхронизацию при использовании неатомарных операций, придумал Т. Деккер, а применил Э. Дейкстра в 1965 году. В 1981 году Г. Петерсон предложил более простой алгоритм.

Простейший алгоритм разделения доступа (который сразу приходит в голову) можно описать схематически с помощью следующей конструкции:

while (spin_lock == TRUE); spin_lock = TRUE; ... // Доступ к разделяемому ресурсу spin_lock = FALSE;

Проблема заключается в том, что этот алгоритм простых спин-блокировок (spin locks) не только прожорлив, но и не гарантирует надежного разграничения доступа. Допустим, что один процесс начал проверять значение переменной spin_lock, дождался того момента, когда оно станет равно FALSE и переходит к строке spin_lock = TRUE;

В многозадачной и системе (особенно на нескольких процессорах) другой процесс, ожидающий доступа к разделяемому ресурсу, может «вклиниться» в тот момент, когда первый процесс уже проверил, но еще не изменил значение spin_lock. Второй процесс проверит значение, все еще равное FALSE и. В результате оба процесса окажутся в критической области и получат доступ к разделяемому ресурсу. Описанная проблема вызвана тем, что операция «проверить значение – изменить значение» неатомарна, то есть, ее выполнение может быть прервано другим процессом. Первый алгоритм, гарантирующий синхронизацию при использовании неатомарных операций, придумал Т. Деккер, а применил Э. Дейкстра в 1965 году. В 1981 году Г. Петерсон предложил более простой алгоритм.


Содержание  Назад  Вперед