再帰読み書き

超スマートポインタの話の続き。
今回の条件をより正確に書くと

• 循環検出と循環検出は排他する。
• ポインタaの参照上げ下げとaの参照上げ下げは排他する。
• 異なるポインタa, bについて、aの参照上げ下げとbの参照上げ下げは排他しない。
• スレッドXが循環検出中の場合、Xが行うポインタaの参照上げ下げは許可する。
• スレッドXが循環検出中の場合、Xと異なるスレッドYが行うポインタaの参照上げ下げは許可しない。

というのが正しいようだ。各ポインタについては単なるmutexで良い。循環検出を守るには単なるread-write lockではダメで、recursive read-write lockとでも呼ぶべきものが必要だ。
しかし、pthreadにはそのようなものはない。他のライブラリでも見付からなかった。そのような需要自体が少ないのかも知れない。
それでは普通のread-write lockとrecursive mutexを組み合わせてrecursive read-write lockとして振舞うようにすれば良さそうだ。

rwlock_t rw;
rec_mutex_t m;
void write() {
  wrlock(&rw);
  lock(&m);
  //排他でのwrite作業
  unlock(&m);
  unlock(&rw);
}
void read() {
  const int rdlockerr = tryrdlock(&rw);
  if (rdlockerr) {
    lock(&m);
  }
  //排他でのread作業
  if (rdlockerr) {
    unlock(&m);
  } else {
    unlock(&rw);
  }
}

フラグ判定を二箇所に書いているのはちょっと不格好かも。wrlock中のread作業は一つずつしか処理出来ないようになっているが、wrlockを通るスレッドが一つであるうちは問題ない(もちろん拡張性は低い)。
これで参照カウントがマルチスレッド対応になる。循環検出の間はほぼ全スレッドが停止してしまうのが欠点か。それでもMark&Sweepよりは停止時間が短いはず。
http://www.research.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdfの論文のConcurrent版を実装すれば停止時間は減るかもしれない。でも、そのまま書いたら循環検出してくれなかったのだよな。scan()中でscan_black()を呼ぶ条件がおかしい気がする。