MemoSTM関係のことをメモっていこうと思います。この広告は、90日以上更新していないブログに表示しています。Herlihy先生が連名している最近の論文を流し読み。99-108「トランザクショナルメモリのパワーでメモリ管理を簡略化する」という感じ。GCを使わない環境下においてメモリ管理は鬼門になってて、そのせいでC++のロックフリーなマルチスレッド対応ライブラリ数はJavaに大きな遅れを取っている。HTMを使ってメモリ管理を上手く行えるようになればC++のライブラリもゆくゆくは充実していくんじゃね?というのを起点にしている。ここでいうメモリ管理は例えばABA問題回避策の一つであるスタンプ技法を使っても解決しない。共有されているデータがいつどの瞬間に消されるかわからないのできちんとした対策はかなり厳しい。実を言うとJavaでもGCのコストを避けるためにメモリプールを自前管理している場合にはこの問題にぶち当たる場合がある。Problem一派、RCU。何のこっちゃという人が多いと思うので簡単に説明するとGCは言わずもがなマルチスレッド環境に対応してくれるGCが必要。実質Lock-freeなコードを書くのにJVMが適している最大の理由。shared_ptrのような参照カウンタ式のGCはカウントのup/downの為にアトミック命令を使う必要があって速度ペナルティが酷い事になるのでこのような場面では使い物にならない。使い物にしていただきたい...。n回のアトミック命令...。Pointerは各スレッドが他のスレッドから見える場所にスレッドローカルストレージを置いて、その中に「俺が見てるからな!捨てるなよ!どうしても捨てるなら後にしろよ!」と、庇護して欲しいポインタを明示する物。データを解放したくなったら他のスレッドのスレッドローカルストレージも全て見て回って、自分の捨てたいデータが存在しない事を確かめてから解放する。他のスレッドのスレッドローカルストレージに置かれている場合には、自スレッドの他者から見れない場所に「あとで消す」リストとして保持しておいて、次回の調査時にそれらが解放できるかどうかもついでにチェックしてから解放する。スレッドローカルストレージを並べる分、移植性のある実装が難しいしスレッドを動的に作ったり壊したりする場合の動作はどうなるのかよくわからない(まだ論文読み込んでない)。局所的なGCを実装しているという見方もできる。Pointerのように自分のアクセスしている最中のポインタを削除対象にさせないように庇護する目的は一緒。スレッドローカルストレージではなくて、グローバル変数として一本の配列を用意して、各スレッドは必要な処理の間その配列の一部分を自分用として予約してから使う。配列の各要素が警備員であり、スレッドはその警備員一人にポインタ(再犯者)を割り当てて監視させる。最初の警備員獲得時にはアトミック命令を使う必要はあるけれど監視対象変更はメモリバリアさえきちんとしていれば良い。メモリを解放するときは自分の雇った警備員を全て解任(グローバルな配列に返す)して、他の警備員が自分の開放したい対象を監視していないかを調べさせて、監視されていない物をLiberateする。RepeatOffenderProbrem一派と書いているのは、その警備員の確保から監視、解放までの間でどこに最適化するかでバリエーションが考えられるので一言には言えないから。Buck(なすり付け法)という手法が紹介されていた。論文無しに実装できる気がしない。RCUはOS側の機能を利用して「1回の操作の間(クリティカルセクション)にプリエンプションを禁じる」「自分が捨てようと思ってポインタを外部から不可視に書き換えてから、自分以外のスレッドが最低1回プリエンプションしてたら少なくとも全員操作の外に居るので自分以外のスレッドからは絶対にそのデータが見えるはずがない」という前提に立ってデータの削除タイミングを見極める物。具体的には捨てたいと思ってから自分の今居るプロセッサに自分以外の全てのスレッドが1度でもマイグレーションされたら、マイグレーション≒プリエンプションなので数え上げれる、などが簡単な判定方法の例。クリティカルセクションの中でロックを取る事ができるバリエーションなどがあるという噂もあって全く理解できない。OSの機能を使っているので移植性が不味い上、カーネル内部以外で利用されている姿を見たことがない。rcuというライブラリも出ているけれど全くわからない。一言で言うと今回の範囲外。PointerやROP一派はメモリの解放時の安全確認のため「自分以外のスレッドが現在使っているデータのリスト」を作成する必要があるのだけれど、そのコストがあまりに高く速度面で大きな足かせとなっていたので、そこにHTM使う事でとても簡単で高速にできるよ。いうのがこの論文最大の趣旨。HazardPointerというよりはROPに近いので「ROPのHTM版」というのが近いような気がする。Bufferのサイズなので大きさが32などと書いてあったけれど単位がわからない)が、それでも解決可能であることを示している。Sizeが動的に変わるという鬼畜な想定でもHTMの力で無理やりねじ伏せれるという物。論文には動的なArrayの場合の擬似コードがかかれいている。HTMは細かいトランザクションが得意だけど、O(n)回のトランザクションを行うスキャンは本当に大丈夫なのかわからない。メモリを守りたい時には、「このポインタを庇護してください」という関数(register)を呼ぶ、その関数では新しくポインタを作って、そのポインタがglobalな配列の一要素を指すような状態を作り、その指している先の1要素の中に保護対象のポインタを保存し、作ったポインタを返す。ユーザーは保護を解除させる場合にはポインタを引数に渡しながら解放させる関数を呼ぶ(deregister)、配列は常に先頭から順に使い、解放するときには対象を配列の利用済み分の末尾とスワップした上で末尾を消去する。スキャン操作は1要素ずつ1トランザクションで舐めていくけれど、この際に配列を末尾から舐めていく事が最大のポイント、スキャン操作は実は擬陽性が有っても問題ないし、同じ要素を2回以上登録しても問題ないので、deregster操作と厳密な線形化ポイントが取れなくても実用上問題ない。それよりもregister操作との一貫性の為のトランザクションがどうなっているのか気になったけれど書いていないので困る。Problemの段階から既にそこの問題は無かったのかも知れない。結論から言うと、HTM版のROPのような手法で、トランザクションをふんだんに使って、局所的に「捨ててもOK」なスレッド間共有メモリを簡単に洗い出せる手法を考えました。Spanner」の実力は?』についてこんな記事が目に入った。月別アーカイブはてなブログをはじめよう!kumagiさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。