Операционные системы. Управление ресурсами
Команда testAndSet и блокировки
Взаимное исключение при помощи переменных-переключателей базируется на атомарности обращений к памяти. Как мы показали выше, это делает решение универсальным как для одно-, так и для многопроцессорных систем. Но большинство архитектур компьютеров имеет в составе своей системы команд специальные команды с расширенной атомарностью обращений к памяти, при помощи которых можно реализовать взаимное исключение и быстрее, и проще. Общее название таких команд - testAndSet - проверить и установить. Действия такой команды могут быть описаны функцией:
int atomic testAndSet ( char *lock ) { char var; var = *lock; *lock = 1; return var; }
(Здесь и далее мы, следуя правилам языка С, в котором параметры передаются по значению, вынуждены передавать в функции указатели, чтобы функции могли изменять значения параметров).
Команда проверяет (возвращает) значение некоторой переменной, а затем устанавливает ее значение в 1. Введенный нами описатель функции atomic показывает, что функция непрерываемая, во время ее выполнения никакой другой процесс не имеет доступа к той памяти, с которой работает функция (к переменной lock). Функция, как мы видим, выполняет два обращения к переменной lock, но оба они выполняются как одна транзакция.
Возможно, первые включения команд типа testAndSet в системы команд диктовались иными соображениями, но сейчас возможность выполнения подобных команд является обязательной для процессоров, претендующих на возможность использования в многопроцессорных комплексах. В микропроцессорах Intel-Pentium, например, имеются следующие команды, которые представляют собой "вариации на тему" testAndSet:
- XCHG - перестановка;
- BTS - проверка и установка бита;
- BTR - проверка и сброс бита;
- BTC - проверка бита и установка противоположного значения;
- CMPXCHG - сравнить и заменить;
- XADD - заменить и сложить.
Так, для реализации "канонической" функции testAndSet при помощи команды XCHG нужны две команды:
MOV al,1 XCHG al,lock
Переменная lock устанавливается в 1, а ее прежнее значение сохраняется в регистре AL.
Непрерываемость операций с памятью при использовании этих команд в многопроцессорных системах обеспечивается сигналом LOCK#, появляющимся на выходе микропроцессора. Причем команда XCHG, когда она использует операнд, расположенный в памяти, активизирует сигнал LOCK# автоматически. Для других названных команд активизация этого сигнала может явным образом задаваться программистом - при помощи префикса LOCK.
Наличие в арсенале программиста команды testAndSet позволяет ему организовать простую и надежную защиту критической секции при помощи переменной-замка:
1 void csBegin ( char *lock ) { 2 while ( testAndSet( lock ) ); 3 } 4 void csEnd ( char *lock ) { 5 *lock = 0; 6 }
Команда testAndSet (строка 2) будет возвращать 1 до тех пор, пока другой процесс находится в критической секции, защищенной замком. Как только этот другой процесс выйдет из критической секции и установит замок в 0 (строка 5), наш процесс тут же вновь установит его в 1 и выйдет из цикла. Вследствие атомарности testAndSet никакой другой процесс не сможет изменить состояние замка между теми моментами, когда наш процесс считает его нулевое значение и установит его значение в 1.
Каждый ресурс (например, каждая разделяемая переменная), к которому происходит совместный доступ, может быть защищен своим замком. Это обеспечит запрет только конфликтующих критических секций, позволяя разным процессам одновременно использовать разные разделяемые ресурсы.
При наличии двух и более групп ресурсов, со своим замком каждая, возможны тупики. Как мы помним из главы 5, наиболее либеральной политикой их предотвращения, не требующей априорной информации, является иерархическая - ее рекомендуется применять и в данном случае.
Замки, обеспечиваемые командой testAndSet, обладают, следовательно, такими свойствами:
- они применимы для любого числа процессов и любого числа процессоров;
- они просты для понимания и для верификации;
- они либеральны, так как не запрещают другим процессам выполняться и даже одновременно входить в неконфликтующие критические секции;
- они допускают бесконечное откладывание, так как выбор процесса, допускаемого к замку, определяется оборудованием, а мы ничего не знаем о его критериях арбитража;
- они используют занятое ожидание.
