7

特に pthread の場合、それらはどのように実装されますか。彼らは内部でどのようなpthread同期 API を使用していますか? 少しの疑似コードをいただければ幸いです。

4

2 に答える 2

10

私はしばらくの間、pthreads プログラミングを行っていませんでしたが、行ったときは、POSIX 読み取り/書き込みロックを使用したことはありませんでした。問題は、ほとんどの場合ミューテックスで十分であることです。クリティカル セクションが小さく、リージョンがパフォーマンス クリティカルではないため、二重バリアを気にする必要がない場合。

パフォーマンスが問題になる場合は、通常、アトミック操作 (一般にコンパイラ拡張機能として利用可能) を使用する方が適切です (つまり、クリティカル セクションのサイズではなく、追加のバリアが問題です)。

これらすべてのケースを排除するまでに、真の rw-lock を必要とする特定のパフォーマンス/公平性/rw-bias 要件があるケースが残ります。それは、POSIX rw-lock のすべての関連するパフォーマンス/公平性パラメーターが未定義であり、実装固有であることを発見したときです。この時点で、適切な公平性/rw-bias 要件が確実に満たされるように、独自の実装を行う方が一般的です。

基本的なアルゴリズムは、それぞれがクリティカル セクションにある数をカウントし、スレッドがまだアクセスを許可されていない場合は、スレッドを適切なキューに移して待機させることです。あなたの努力のほとんどは、2 つのキューにサービスを提供する間に適切な公平性/バイアスを実装することになります。

次の C ライクな pthreads ライクな疑似コードは、私が言おうとしていることを示しています。

struct rwlock {
  mutex admin; // used to serialize access to other admin fields, NOT the critical section.
  int count; // threads in critical section +ve for readers, -ve for writers.
  fifoDequeue dequeue; // acts like a cond_var with fifo behaviour and both append and prepend operations.
  void *data; // represents the data covered by the critical section.
}

void read(struct rwlock *rw, void (*readAction)(void *)) {
  lock(rw->admin);
  if (rw->count < 0) {
    append(rw->dequeue, rw->admin);
  }
  while (rw->count < 0) {
    prepend(rw->dequeue, rw->admin); // Used to avoid starvation.
  }
  rw->count++;
  // Wake the new head of the dequeue, which may be a reader.
  // If it is a writer it will put itself back on the head of the queue and wait for us to exit.
  signal(rw->dequeue); 
  unlock(rw->admin);

  readAction(rw->data);

  lock(rw->admin);
  rw->count--;
  signal(rw->dequeue); // Wake the new head of the dequeue, which is probably a writer.
  unlock(rw->admin);
}

void write(struct rwlock *rw, void *(*writeAction)(void *)) {
  lock(rw->admin);
  if (rw->count != 0) {
    append(rw->dequeue, rw->admin);
  }
  while (rw->count != 0) {
    prepend(rw->dequeue, rw->admin);
  }
  rw->count--;
  // As we only allow one writer in at a time, we don't bother signaling here.
  unlock(rw->admin);

  // NOTE: This is the critical section, but it is not covered by the mutex!
  //       The critical section is rather, covered by the rw-lock itself.
  rw->data = writeAction(rw->data);

  lock(rw->admin);
  rw->count++;
  signal(rw->dequeue);
  unlock(rw->admin);
}

上記のコードのようなものは、あらゆる rwlock 実装の出発点です。問題の性質を考えて、デキューを、次に起動する必要があるスレッドのクラスを決定する適切なロジックに置き換えます。アプリケーションに応じて、制限された数/期間のリーダーがライターを飛び越えたり、その逆を許可したりするのが一般的です。

もちろん、私の一般的な好みは、rw ロックを完全に避けることです。一般に、アトミック操作、ミューテックス、STM、メッセージパッシング、および永続的なデータ構造を組み合わせて使用​​します。しかし、本当に rw-lock が必要な場合があり、その場合、それらがどのように機能するかを知っておくと役に立ちます。

編集 - (非常に合理的な) 質問への回答として、上記の疑似コードのどこで待機しますか:

デキューの実装には待機が含まれていると想定しているため、次の行に沿ってコードのブロックがどこappend(dequeue, mutex)かにあるか、そこにあります。prepend(dequeue, mutex)

while(!readyToLeaveQueue()) {
  wait(dequeue->cond_var, mutex);
}

これが、関連するミューテックスをキュー操作に渡した理由です。

于 2012-06-15T05:12:55.470 に答える
0

各実装は異なる場合がありますが、スレッドが rwlock で読み取りロックを複数回取得できるという POSIX の要件により、通常はデフォルトでリーダーを優先する必要があります。彼らがライターを支持した場合、ライターが待機している時はいつでも、実装がリーダーが既に読み取りロックを持っていると判断できない限り、リーダーは 2 回目の読み取りロック試行でデッドロックしますが、それを判断する唯一の方法はすべてのスレッドのリストを保存することですこれは、時間とスペースの要件において非常に非効率的です。

于 2012-06-14T13:47:14.097 に答える