2

コンペアとスワップだけがあれば、ロックを実装する方法を知っています。

ただし、スピンロックを実装するにはどうすればよいですか

1）複数のスレッドがロックしようとしているときにブロックすることができます 2）その後、スレッドはブロックされた順序でブロック解除されます（そしてロックを取得します）？

それは可能ですか？そうでない場合、他にどのようなプリミティブが必要ですか?

もしそうなら、どうすればいいですか？

ありがとう！

4

1 に答える 1

0

待機中のスレッドのリストが必要になります。スレッドセーフな方法でリストに項目を追加および削除する必要があります。ロックの取得に失敗したスレッドをスリープできる必要があります。ロックが使用可能になったときに、1 つのスレッドをウェイクできる必要があります。Linuxでは、スレッドにシグナルを待機させることで、スリープして待機することができます。

現在、これを行うための怠惰な方法があります。ウェイク中のスレッドを気にする必要はないかもしれません。これがスキップリストの疑似コードです。これは、アイテムを追加するために行うことです。

cFails = 0
while (1) {
  NewState = OldState = State;
  if (cFails > 3 || OldState.Lock) {
    sleep();  // not too sophisticated, because they cant be awoken
    cFails = 0;
    continue;
  }

  Look for item in skiplist
  return item if we found it

  // to add the item to the list we need to lock it

  // ABA lock uses a version number
  NewState.Lock=1;
  NewState.nVer++;
  if (!CAS(&State,OldState, NewState)) {
    ++cFails;
    continue; 
  }

  // if the thread gets preempted right here, the lock is left on, and other threads
  // spinning would waste their entire time slice.

  // unlock
  OldState = NewState;
  NewState.Lock = 0;
  NewState.nVer++;
  CAS(&State, OldState,NewState);  
}

通常、skiplist はアイテムを見つけ、追加する必要はほとんどないと考えています。多くのスレッドがあっても、競合することはめったにありません。これは、1 つのリストに何百万ものアイテムを追加および検索する多数のスレッドで構成される最悪のシナリオでテストされました。その結果、スレッドがロックの取得に失敗することはほとんどありませんでした。したがって、予想されるケースに対して高性能である単純なアプローチが機能します。発生する可能性のある悪いことが 1 つあります。ロックを保持しているスレッドがプリエンプトされます。それは、cFails > 3 がこれをキャッチし、待機中のスレッドをスリープ状態にして、100 万回の無駄なスピンでタイムスライスを無駄にしないようにするときです。したがって、cFails は、ロックの所有者がアクティブでないことを検出するのに十分な高さに設定されます。

于 2012-04-09T17:21:43.827 に答える