CASSANDRA-5062でCAS (Compare and Swap) を入れようという話になっているらしく、一体どんなすごいアトミックブロードキャストを使うのか気になっていた。どういうことなのだろうとスレッドをナナメ読みしてみたのだが…議論の流れとしては カウンターだけじゃなくてCASほしいよねAPIとして ZooKeeperのロック使うのがシンプルでいんじゃね? いやいやサーバーの種類増やすとかあり得ないし 基本方針は、コーディネーターみたいなのをレプリカセット毎に決めてそこから Chain Replication ぽく コーディネーターどうやって決める やっぱPaxosじゃね? 再実装ヤダよZAB使おうよZKの実装あるよ (なんかプロトコル上の理由があって)やっぱPaxos実装するしかないか… となって、結局 Jonathan Ellis が Paxos を素で実装してしまった模
もう、マルチスレッド飽きてきた・・・・ 気を取り直して、前回お話したLOCK FREEの概念を使って スタックを作り直してみましょう。 基本的な内容は変わりません。 構造体もまるっきし同じです。 template <class T> class lock_free_stack : protected boost::noncopyable { protected: struct snode_type{ T* value; snode_type* next; snode_type(T* nin_value,snode_type* nin_next) : value( nin_value ) , next( nin_next ) {} }; snode_type* tail; snode_type* dummy; unsigned int counter; public: //constract
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズム
コンペア・アンド・スワップ(Compare-and-Swap、CAS)は、CPUの特別な命令の一種。不可分操作として、あるメモリ位置の内容と指定された値を比較し、等しければそのメモリ位置に別の指定された値を格納する。この操作の結果、置換が行われたかどうかを示す必要があり、単純な真理値を返すか、そのメモリ位置から読み込んだ内容(書き込んだ内容ではない)を返す。 CAS命令は、マルチプロセッサシステムでセマフォなどを実装するのに使われる。マルチプロセッサシステムでLock-freeとWait-freeアルゴリズムを実装するのにも使われる。 Maurice Herlihy (1993年) は、CAS命令が単なるリード、ライトやテスト・アンド・セットでは実装できないことを示した[1]。 応用[編集] CAS命令を利用したアルゴリズムは、一般にあるキーとなるメモリ位置を読み取り、その古い値を記憶して
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く