Реализовать атомарный инкремент, используя атомный своп?

Question

Предположим, я пишу код (сборку) для процессора, единственной атомарной операцией которого является безусловный обмен - без LL / SC, без сравнения и обмена, просто простой обмен. (Примером такого зверя может быть ARM9.) Есть ли способ выполнить атомарные операции увеличения / уменьшения, используя операцию подкачки?

Существует относительно простой ответ: использовать своп для построения спин-блокировки и использовать его для обеспечения критического сечения вокруг обычного увеличения и уменьшения. Но это кажется неуклюжим, и я знаю, что это можно сделать без блокировки, если доступны CAS или LL / SC. Так что мне действительно интересно, есть ли способ сделать это без использования блокировки.

Answer 1

Я не могу придумать другого способа сделать это просто потому, что вам нужно и поменять местами, и сравнить, чтобы определить, разрешено ли вам продолжать. Если у вас нет команды сравнения и обмена, вам придется реализовать ее с помощью циклического обмена и сравнения, что-то вроде:

; Emulate atomic add/sub with atomic swap.
; On entry:
;   r0 contains address of variable
;   r1 contains value to add or subtract.

mutex:    defw    0           ; mutual exclusion semaphore (0=free, 1=busy).

chng:     push    r2          ; save variables.
          ld      r2,1        ; claiming value.
spin:     swap    r2,(mutex)  ; atomic swap (sounds like a good name for a band).
          bnz     spin        ; loop until you have it.
          add     (r0),r1     ; emulated atomic change.
          swap    r2,(mutex)  ; free mutex for everyone else.
          pop     r2          ; restore registers.
          ret

Это действительно глупо, если вы делаете это во многих местах своего кода. Я часто обнаруживал, что изоляция кода «klunky» от функции (как выше) делает его гораздо менее хитрым, поскольку в результате вы получаете множество сегментов кода, которые выглядят намного проще:

myvar:    defw    0
          : : : : :
          ld      r0,myvar
          ld      r1,1        ; increment
          call    chng

или, если вы хотите, чтобы ваш код был еще проще, предоставьте отдельные функции incr и decr:

; Emulate atomic incr/decr with emulated atomic change.
; On entry:
;   r0 contains address of variable

incr:     push    r1          ; save registers.
          ld      r1,1        ; increment.
          call    chng        ; do it.
          pop     r1          ; restore registers.
          ret
decr:     push    r1          ; save registers.
          ld      r1,-1       ; decrement.
          call    chng        ; do it.
          pop     r1          ; restore registers.
          ret

Тогда ваши кодовые последовательности станут:

          ld      r0,myvar
          call    incr

или, если вы можете делать макросы, еще проще:

atincr:   defm                ; do this once to define macro
          ld      r0,&1
          call    incr
          endm

          atincr  myvar       ; do this in your code, as much as you like.

Answer 2

Если ваш ЦП одноядерный, то вы можете использовать этот способ, конечно, без замены, но вы должны быть осторожны. Вот простой случай:

//incrementing of variable
cli        //disable interrupts if we aren't on high priviliegied code execution level
//perform non atomic increment of variable
sti        //enable interrupts if we aren't on high priviliegied code execution level

//reading variable
cli        //disable interrupts if we aren't on high priviliegied code execution level
//perform non atomic read operation
sti        //enable interrupts if we aren't on high priviliegied code execution level

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