アトミック、ときどきロックフリー

C/C++標準ライブラリ提供のアトミック変数atomic<T>, atomic_Tでは、ロックフリー(lock-free)性判定マクロATOMIC_*_LOCK_FREE*1 が3状態 Never／Sometimes／Always を取りうる。

C++11策定当時の提案文書N2427によれば、“ロックリーに振る舞う可能性あり”（ATOMIC_*_LOCK_FREE == 1）選択肢の提供根拠は下記の通り：

• 動的リンクライブラリのバージョンアップなどで、将来的にはロックフリーに振る舞う可能性を考慮する。
• やむを得ない “不適切なアライメントをもつアトミック変数” の存在を許容する。
  • 型レベルでのロックフリー保証を諦めることで、適正アライメントのアトミック変数のみを考慮とした効率的な実装が可能となる。

Lock-Free Property

The proposal provides run-time lock-free query functions rather than compile-time constants because subsequent implementations of a platform may upgrade locking operations with lock-free operations, so it is common for systems to abstract such facilities behind dynamic libraries, and we wish to leave that possibility open. Furthermore, we recommend that implementations without hardware atomic support use that technique.

The proposal provides lock-free query functions on individual objects rather than whole types to permit unavoidably misaligned atomic variables without penalizing the performance of aligned atomic variables.

Because consistent use of operations requires that all operations on a type must use the same protocol, all operations are lock-free or none of them are. That is, the lock-free property applies to whole objects, not individual operations.

N2427 C++ Atomic Types and Operations

C++標準規格では、ロックフリー実行(lock-free executions)が定義されている。C++17 4.7.2/2より引用。

Executions of atomic functions that are either defined to be lock-free (32.8) or indicated as lock-free (32.5) are lock-free executions.

• If there is only one thread that is not blocked (3.6) in a standard library function, a lock-free execution in that thread shall complete. [Note: Concurrently executing threads may prevent progress of a lock-free execution. For example, this situation can occur with load-locked store-conditional implementations. This property is sometimes termed obstruction-free. -- end note]
• When one or more lock-free executions run concurrently, at least one should complete. [Note: It is diffcult for some implementations to provide absolute guarantees to this effect, since repeated and particularly inopportune interference from other threads may prevent forward progress, e.g., by repeatedly stealing a cache line for unrelated purposes between load-locked and store-conditional instructions. Implementations should ensure that such effects cannot indefinitely delay progress under expected operating conditions, and that such anomalies can therefore safely be ignored by programmers. Outside this document, this property is sometimes termed lock-free. -- end note]

関連URL

• c++ - Why is is_lock_free a member function? - Stack Overflow
• multithreading - Is the meaning of "lock-free" even defined by the C++ standard? - Stack Overflow
• cppreference ATOMIC_*_LOCK_FREE, cpprefjp ロックフリープロパティ
• C++14 ロックフリーの定義 - Faith and Brave - C++で遊ぼう
• wait-free/lock-free/obstruction-freeの定義について
• C++ atomic_flag実装のための最低要件 - yohhoyの日記
• lock-freeとaddress-free - yohhoyの日記
• C++11 atomic_flagプリミティブ - yohhoyの日記

*1:*＝BOOL, CHAR, CHAR16_T, CHAR32_T, WCHAR_T, INT, LONG, LLONG, POINTERのいずれか。例：atomic<int>, atomic_int 型にはマクロ ATOMIC_INT_LOCK_FREE が対応。