Lock-freeとWait-freeアルゴリズム
ノンブロッキングデータ構造の中には、特別なアトミックプリミティブを使用しなくても実装できるほど「弱い」ものもある。このような例外は以下の通りである。
シングルリーダー・シングルライターのリングバッファFIFOは、利用可能な符号なし整数型のオーバーフローを均等に分割するサイズであれば、無条件にメモリバリアのみで安全に実装することができる。
一人のライターと任意の数のリーダーによる Read-copy-update。(リーダーは待ち時間がなく、ライターは通常、メモリの再利用が必要になるまでロックフリーである)
複数のライターと任意の数のリーダーによる Read-copy-update。(リーダーは待ち時間なし。複数のライターは一般的にロック付きでシリアル化され obstruction-free ではない)
いくつかのライブラリが内部的にロックフリー技術を使用しているが、正しくロックフリーのコードを書くことは困難である 。