Проверка и установка

Классическим параллельным примитивом является проверка и установка. Операция проверки и установки атомарно читает значение из какого-то места в памяти и записывает в него новое значение, возвращая старое. Как правило, в этом месте может находиться 0 или 1, и новым значением, которое записывает операция проверки и установки является 1, то есть «установка». Противоположностью операции проверки и установки является операция проверки и очистки, которая выполняет то же, за исключением того, что записывает 0 вместо 1. Некоторые варианты операции проверки и установки могут записывать либо 1, либо 0, поэтому две операции, проверка и установка или проверка и очистка, сводятся к одной операции только с разными операндами.

Примитив проверки и установки позволяет реализовать любые другие операции, предназначенные для параллельного выполнения. (И действительно, на некоторых процессорах в качестве параллельного примитива предусмотрена только проверка и установка.) Например, проверка и установка может применяться для защиты счетчика ссылок в предыдущем примере. Мы пытались применить аналогичный метод: прочитать значение из места в памяти, проверить, равняется ли оно 0 и если да, записать 1 и перейти на этап доступа к защищенному значению. Эта попытка оказалось неудачной не потому, что была логически не обоснована, а потому, что не было способа реализовать ее атомарно. При наличии атомарного примитива проверки и установки мы можем превратить decl в атомарную команду без применения команды lock.

Однако проверка и установка имеет свои недостатки:

• Это примитив низкого уровня. Если предусмотрен только он, на его основе придется реализовать все другие примитивы.
• Он приводит к ненужному расходу ресурсов. Что произойдет, если компьютер проверит значение и обнаружит, что оно уже равно 1? Значение в памяти не изменится, поскольку оно будет просто перекрыто тем же значением. Но тот факт, что оно уже было установлено, означает, что к защищенному объекту уже обращается какой-то другой процесс, поэтому выполнение пока нельзя продолжить. Требуется дополнительная логика (проверка и переход по циклу), которая бесполезно расходует время процессора и немного увеличивает объем программы (что, в свою очередь, приводит к потере места в кэше).

Команда lock процессора х86 позволяет упростить реализацию примитивов более высокого уровня, но в архитектуре х86 можно также применять атомарную проверку и установку. Самый прямолинейный способ состоит в применении команды lock в сочетании с btsl (bit-test-and-set — поразрядная проверка и установка). Такой подход применяется в блокировках в цикле, которые рассматриваются далее в этой главе.

Еще одним способом реализации проверки и установки в архитектуре х86 является применение предусмотренной в ней команды xchg (exchange — обмен), которая автоматически трактуется процессором х86, как если бы ей предшествовала команда lock, во всяком случае, когда один из ее операндов находится в памяти.

Команда xchg является более универсальной по сравнению с сочетанием lock/btsl, поскольку она позволяет обменивать одновременно 8, 16 или 32 бита, а не просто 1 бит.

Кроме одного применения в коде arch/i386/kernel/entry.S, в ядре команда xchg скрыта за макрокомандой xchg (строка 13052), которая, в свою очередь, реализована на основе функции __xchg (строка 13061). Это сделано для того, чтобы в коде ядра макрокоманду xchg можно было использовать в части кода, независимой от архитектуры; на каждой платформе предусмотрена собственная эквивалентная реализация этой макрокоманды.

Интересно, что макрокоманда xchg является основой еще одной макрокоманды, tas (test-and-set, проверка и установка, строка 13054). Однако эта макрокоманда в коде ядра нигде не используется.

В ядре макрокоманда xchg иногда применяется для выполнения простой проверки и установки (но не обязательно для повторного прохода по циклу до тех пор, пока блокировка не станет доступной, как в строке 22770), а также применяется для других целей (как в строке 27427).