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成功