Как реализована спин-блокировка под капотом? - PullRequest
Новая
       13

Как реализована спин-блокировка под капотом?

3 голосов
/ 23 мая 2010

Это замок, который может быть удержан только один поток исполнения на время. Попытка получить замок другим потоком исполнения делает последний цикл до блокировки освобожден.

Как он справляется со случаем, когда два потока пытаются получить блокировку в одно и то же время ?

Я думаю, что этот вопрос также относится к различным мьютексам.

Ответы [ 2 ]

7 голосов
/ 25 мая 2010

Как показывает предыдущий плакат, у каждого современного типа машины есть специальный класс инструкций, известный как «атомика», которые работают так, как предыдущий плакат указывает ... они сериализуют выполнение по крайней мере с указанной ячейкой памяти.

На x86 существует префикс ассемблера LOCK, который указывает машине, что следующая инструкция должна обрабатываться атомарно. Когда инструкция встречается, на x86 происходит несколько вещей.

  1. Ожидающие предварительные выборки чтения отменяются (это означает, что ЦП не предоставит программе данные, которые могут быть устаревшими через атомарный элемент).
  2. Ждущие записи в память сбрасываются.
  3. Операция выполняется, гарантированно атомарно и сериализовано против других процессоров. В этом контексте «сериализованный» означает «они происходят по одному». Атомно означает, что «все части этой инструкции выполняются без какого-либо вмешательства».

Для x86 есть две часто используемые инструкции, которые используются для реализации блокировок.

  1. CMPXCHG. Условный обмен. Псевдокод: 
uint32 cmpxchg(uint32 *memory_location, uint32 old_value, uint32 new_value) {
    atomically {
        if (*memory_location == old_value) 
            *memory_location = new_value;
        return old_value;
    }
}
  1. XCHG. Псевдокод: 
uint32 xchg(uint32 *memory_location, uint32 new_value) {
    atomically {
        uint32 old_value = *memory_location;
        *memory_location = new_value;
        return *old_value;
    }
}

Итак, вы можете реализовать блокировку следующим образом: 

uint32 mylock = 0;
while (cmpxchg(&mylock, 0, 1) != 0)
    ;

Мы вращаемся, ожидая блокировки, следовательно, спинлок.

Теперь, разблокированные инструкции не демонстрируют такое хорошее поведение . В зависимости от того, на какой машине вы находитесь, с разблокированными инструкциями, можно наблюдать все виды нарушений согласованности. Например, даже на x86, который имеет очень дружественную модель согласованности памяти, можно наблюдать следующее: 

    Thread 1      Thread 2
    mov [w], 0    mov [x], 0
    mov [w], 1    mov [x], 2
    mov eax, w    mov eax, x
    mov [y], eax  mov [z], eax

В конце этой программы y и z оба могут иметь значение 0! .

В любом случае, последнее замечание: LOCK в x86 может применяться к ADD, OR и AND, чтобы получить согласованную и атомарную семантику чтения-изменения-записи для инструкции. Это важно, скажем, для установки переменных-флагов и обеспечения того, чтобы они не потерялись. Без этого у вас есть эта проблема: 

   Thread 1       Thread 2
   AND [x], 0x1   AND [x], 0x2

В конце этой программы возможные значения x равны 1, 2 и 0x1 | 0x2 (3). Чтобы получить правильную программу, вам необходимо: 

   Thread 1           Thread 2
   LOCK AND [x], 0x1  LOCK AND [x], 0x2

Надеюсь, это поможет.

2 голосов
/ 23 мая 2010

Зависит от процессора и реализации потоков. У большинства процессоров есть инструкции, которые могут быть выполнены атомарно, поверх которых вы можете создавать такие вещи, как спин-блокировки. Например, IA-32 имеет инструкцию xchg, которая выполняет атомный обмен. Затем вы можете реализовать наивный спинлок: 

  eax = 1;
  while( xchg(eax, lock_address) != 0 );
  // now I have the lock
  ... code ...
  *lock_address = 0; // release the lock
...