lock-free stackと並行アルゴリズムの区分
この記事は
カーネル／VM Advent Calendar http://atnd.org/events/10701
のために書かれました。
これまで複数回に渡ってlock-freeデータ構造を紹介して来ましたが
そもそもの前提を話していなかったり目的も不明だったりと不備だった点があったので
根元から一度おさらいしてみたいと思います。
まずロックを用いる事の欠点から
上図のような構図でロックによる相互排他を行うと様々な問題が発生します。
具体的に言うと排他に成功したスレッドに様々な災難が降りかかります。
主な事例として
↑ロック確保できたのにOSによってプリエンプションされる。
↑物理メモリに乗ってない仮想メモリにアクセスしてしまった。
↑キャッシュミスヒットによるメモリ待ち。
そんなに気にするほどのパフォーマンス低下ではないと思うかも知れませんが
マルチコアの方向へ舵を切った新世代CPUを使いこなすに当たっては重大なスループット低下を招きます。
ロック内のスレッドが無駄にした1クロックは
ロック外のすべてのスレッドにとっての1クロックでもあるのです。
至高のパフォーマンスを目指す近代のアルゴリズマー達はこの問題を決して野放しにはしませんでした。
その対策の一部がこれから紹介するnon-blockingデータ構造の数々です。
non-blockingの意味するところ
海外の文献を読み漁っていると気づくのですが
2003年を境にこの文脈で使われる言葉の定義が変わります。
↑2003年ごろまでの構図
↑現在の構図。*1
non-blocking = obstruction-free という理解でもおおよそ間違いではないとは思いますが
論文を読むに当たって
non-blocking = ロックを使わないアルゴリズム全般
obstruction-free = 非lock-freeだけどロックだけはしない
というニュアンスの違いを感じます。
以後、現在の構図の方を前提に話します。ご注意ください。
まずは3つの分類の違いから
wait-free
操作が「他のスレッドの動向に関わらず有限ステップで完了できる」場合、そのアルゴリズムはwait-freeと呼ばれます。starvation-freeと呼んだりもします。
実際には初めからここに分類されるアルゴリズムは多くありませんが、例えばスレッド数に制約をつけたりすることでこちらに分類される場合もあります。
一見パフォーマンスが高そうに見えますが、必ずしもそうとは限りません。
少ないコア数の場合にはロックによる排他よりもスループットが低い場合も有り得ます。
実際にこの保証のあるアルゴリズムの必要性がある場面は私の知る限りではリアルタイム動作を保証したい場合のみで
・ロボットの操作（関節の操作が遅れると転んじゃう！）
・音響ソフトウェア（音が遅れて聞こえちゃう！）
などです。
ですがLinuxなどの非リアルタイムOS上でどうしてもwait-freeじゃないと…という状況は思いつきません。*2
また誤解が多いのですが「一定ステップで終了する事」ではなく「ステップ数の上限が固定できること」が条件なので
例えば「さすがに20スレッドに追い越される前には動作を必ず完了できる」場合などにもwait-freeの名前が付きます。
lock-free
操作が「いつも必ずどれかのスレッドで有効に行われている」場合、そのアルゴリズムはlock-freeと呼ばれます。進行保証が付いているとも言います。
歴史的な経緯からか意味と名前がいまいちぴったり来なくて、個人的にはwaste-freeとか呼べばいいのにと思っているけれど他に気にしてる人は居ないようです。
wait-freeと比べてstarvationが発生する危険があります。具体的に言うといつまで経っても他のスレッドに邪魔されて動作を完了できないスレッドが発生し得ます。*3
しかし前述したようにそれは必ずしもパフォーマンスの低下を意味しておらず、強いて言えば「レイテンシ保証を犠牲にスループットを手に入れた」という形容が適切な場合もあります。
obstruction-free
操作が「他のスレッドに邪魔さえされなければ終わる」場合、そのアルゴリズムはobstruction-freeと呼ばれます。lock-freeと比べて進行保証が付いていない特徴があります。
進行保証が無いと、複数のスレッドが走っていても「どのスレッドも全体での進行に寄与しない」瞬間が存在してしまいます。
lockを用いて居ないのになぜこのような事態になるかというと、複数のスレッドがお互いを邪魔しないよう動作した結果です。
詳しくはSTMの実装などを読んでください*4
一見性能が悪そうに見えますが、そもそも成そうとしている事が複雑なため必要なコストでしょう。
Nir Shavit先生も「STMをwait-freeもしくはlock-freeになるよう設計する事は可能だが満足のいくパフォーマンスは得られないだろう」と断言しています。*5
Lock-free Stack
ではLock-free Stackについて図とプログラムを交えながら説明します。C++ではなくCを使います。
これは複数スレッドからロックによる排他無しで共有できるスタックで、外部には
node* top; void push(const T*, node** top); bool pop(T*, node** top);
を提供します。*1
このスタックはbottomへと繋がる線形リストをベースとして動作するため、配列ベースのスタックにパフォーマンスで劣ることもあります。*2
その線形リストを構成するノードのデータ構造から見てみましょう。
struct node{
T data;
node* next;
};
ごく典型的な線形リストのノードと同じです。
道具の紹介
lock-freeデータ構造を構成する場合に頻出のCompare And Swap。
C言語の擬似コードで書くと以下のような動作をします
bool compare_and_swap(void* address, int expected, int to_swap){ if(*address == expected){ // addressの中身が期待通りだったら *address = to_swap; // 上書きしてtrueを返す return true; }else{ return false; // 違ったらfalseを返す } }
上記の関数と同じ事をアトミックに実行してくれるCompare And Swap(以後CASと略)というCPU命令があります。
x86のCPUではcmpxchgという名前です。*3
push操作
void push(const T* data, node** top){ // ノードをコピーして node* newnode = (node*)malloc(sizeof(node)); newnode->data = *data; newnode->next = NULL; node* oldtop; // スレッドの作業用ローカルデータ do{ newnode->next = oldtop = *top; // ターゲットを定めて }while(!__sync_bool_compare_and_swap(top, oldtop, newnode)); // topの更新に成功するまで続ける }
プログラムではピンと来ないと思うので図に書くと
こんな感じの動作を目的としています。
・CASの動作前に既に下準備が全て終わっている事
・CASがアトミックな操作であること
がポイントです。このようにする事で
どのような競合があってもCASによりtopが自分を指すよう更新成功するのは1スレッドのみなので、正常なスタックを構成できます。
pop操作
bool pop(T* data, node** top){ node *nexttop, *oldtop; do{ oldtop = *top; if(oldtop == NULL){return false;} nexttop = oldtop->next; }while(!__sync_bool_compare_and_swap(top, oldtop, nexttop)); *data = oldtop->data; // 戻り値を用意 free(oldtop); // dataは退避済みなので消してよし return true; // pop成功
ルールとしてはこちらも「CASに成功した奴が正義」という点で同じです。
CASの成功を排他成功と見なし、自分が取り出しに成功したnodeの中身を返します。
