The King's Museum

ソフトウェアエンジニアのブログ。

『Javaの理論と実践: ノンブロッキング・アルゴリズムの紹介』を読んで

Javaの理論と実践 Java

記事： Javaの理論と実践: ノンブロッキング・アルゴリズムの紹介

メモ：

  • Java5 でノンブロッキングアルゴリズムの開発が可能になった
  • ノンブロッキングカウンター
  • ノンブロッキング・スタック
    • 先頭の Node への参照を AtomicReference で保持しておく。
    • push()
      • ノンブロッキングで先頭へ挿入する
        • head への代入は compareAndSet() で投機的に試み、失敗したらもう一度。
    • pop()
      • ノンブロッキングで先頭から Node 取りだす
        • 先頭を次のノードへの参照置き換える。ただし、compareAndSet で投機的に試み、失敗したらもう一度。
  • パフォーマンスの考慮事項
    • 『競合ないロックのパフォーマンス ＜ 競合のない CASのパフォーマンス』
    • ほとんどの場合『競合のあるロックのパフォーマンス ＜ 競合のある CAS のパフォーマンス』
    • 競合が激しい場合、スレッドが一つのメモリ位置に殺到するため『CAS のパフォーマンス < ロックのパフォーマンス』となる場合がある
      • ロックの場合は、メモリアクセスが単一のスレッドだけになるためロックの方がはやい
      • ただし、これほどの競合が発生するのはまれである
  • ノンブロッキング・リンク・リスト
    • リンクリスト、ツリー、ハッシュなどの高度なデータ構造は複数のポインタが絡む
    • アトミック変数ではあくまで一つ参照の更新を CAS で行う
      • => 高度なデータ構造の場合は CAS を使って複数のポインタを同時に更新する必要があり、実装が難しい
    • リンクリストの実装上、二つのポインタが必要
      • tail：常にリストの最後の要素を参照する
      • next：次の要素を参照する
  • 二つのポインタを CAS で操作する際の問題
    • 最初の CAS が成功したが、二番目の CAS が失敗した場合
    • 最初の CAS と二番目の CAS の間に別のスレッドがリストへのアクセスを試みた場合
  • Michael-Scott のノンブロッキング・キュー・アルゴリズムの挿入
    • 複数のスレッドが協調して CAS 操作を行って整合状態（不変条件）を維持する
    • 詳細はメモのレベルを大幅に超えるので省略…
  • ノンブロッキングアルゴリズム

感想

「Michael-Scott のノンブロッキング・キュー・アルゴリズムの挿入」に関しては、書かれていることは理解したけど、自分で実装しろって言われたら絶対無理だな。。。

(c) The King's Museum