yohhoyの日記

技術的メモをしていきたい日記

C++ atomic_flag実装のための最低要件

C++11標準ライブラリ atomic_flag 型について標準規格の要求*1通りロックフリー(lock-free)実装を行うにあたり、対象プロセッサに要求される命令セット・アーキテクチャ(ISA; Instruction Set Architecture)についてメモ。

atomic_flag型を実装するためには「アトミックなTest-And-Setロック命令(TSL)」または「アトミックな値交換命令」が存在すればよい。下記は仮想ISAアセンブラによるclear/test_and_set操作の実装例。*2

; m = atomic_flagのstate(0:クリア状態/1:セット状態)
;;; void atomic_flag::clear()
  load  r1, 0    ; r1 <- 0
  swap  r1, [m]  ; r1(値0)とアトミックに値交換
  ret

;;; bool atomic_flag::test_and_set()
  load  r1, 1    ; r1 <- 1
  swap  r1, [m]  ; r1(値1)とアトミックに値交換
  ret   r1       ; 戻り値 <- r1(以前の[m]格納値)

なお、atomic_flag以外のatomic変数(atomic_intなど)については、C++11標準ライブラリではロックフリー実装を要求しない。(とはいえ、可能な限りロックフリー実装がなされるはず)

関連URL

*1:N3337 29.7/2:"Operations on an object of type atomic_flag shall be lock-free."

*2:ここでは値交換命令"swap"がSequential Consistencyなメモリバリア効果を持つ(memory_order_seq_cst相当)ことを前提とする。この場合、clear/test_and_set操作に対してmemory_order_seq_cst以外を指定しても、事実上無視してmemory_order_seq_cst動作をする実装になる。