線形化可能性
多くのシステムでは、アトミックな比較スワップ命令が用意されている。これはメモリーロケーションから値を読み取り、その値とユーザーが指定した「期待値」を比較し、両者が一致した場合に「新しい」値を書き出し、更新が成功したかどうかを返すものである。これを利用してノンアトミックカウンターのアルゴリズムを以下のように修正することができる。
メモリーロケーションの値を読み取る
その値に1を加える
比較スワップ機能を使って、増加した値を書き戻す
比較スワップによって読み込まれた値が、最初に読み込んだ値と一致しない場合は再試行する
比較スワップは瞬時に行われる(ように見える)ので、進行中に他のプロセスがその場所を更新した場合、比較スワップは確実に失敗する。
線形化可能性は、1987年にハーリー(Maurice Peter Herlihy)とWingによって初めて一貫性モデルとして紹介された。このモデルは「アトミックな操作とは、同時実行される操作によって割り込みされることがない操作である」といった、より限定的なアトミックの定義を含んでおり、操作の開始と終了がいつであるかについては通常曖昧である。
アトミックなオブジェクトは、逐次的・直列的な定義から即座に完全に理解することができる。並列に実行される一連の操作が常に次々と発生しているように見えることであり、矛盾が生じることはない。具体的には、線形性は、システムの不変性がすべての操作によって観察され、保存されることを保証する。すべての処理が個々に不変性を保持していれば、システム全体としても不変性を保持していることになる。