Операционные системы. Управление ресурсами


Команда testAndSet и блокировки



8.4. Команда 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, обладают, следовательно, такими свойствами:

  • они применимы для любого числа процессов и любого числа процессоров;
  • они просты для понимания и для верификации;
  • они либеральны, так как не запрещают другим процессам выполняться и даже одновременно входить в неконфликтующие критические секции;
  • они допускают бесконечное откладывание, так как выбор процесса, допускаемого к замку, определяется оборудованием, а мы ничего не знаем о его критериях арбитража;
  • они используют занятое ожидание.









Начало  Назад  Вперед