1

アプリケーションの 1 つに C++ でキュー ロックを実装したいと考えています。次の論文のアルゴリズムを調べていました: http://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCUQFjAA&url=http%3A%2F%2Fwww .cs.rice.edu%2F~johnmc%2Fpapers%2Ftocs91.pdf&ei=HpRfUKCZFsfWrQfpgIGACQ&usg=AFQjCNF_QamPWhJrq5dSjJjFjO7W3WzJ5Q&sig2=3TU1vo_aAYbM2fmLxeiZ0A

type qnode = record
next : ^qnode
locked : Boolean

type lock = ^qnode

// parameter I, below, points to a qnode record allocated
// (in an enclosing scope) in shared memory locally-accessible
// to the invoking processor

procedure acquire_lock (L : ^lock, I : ^qnode)
  I->next := nil
  predecessor : ^qnode := fetch_and_store (L, I)
  if predecessor != nil  // queue was non-empty
    I->locked := true
    predecessor->next := I ---A
    repeat while I->locked   // spin ---C

procedure release_lock (L : ^lock, I: ^qnode)
 if I->next = nil  // no known successor
   if compare_and_swap (L, I, nil)  // compare_and_swap returns true iff it swapped
     return

   repeat while I->next = nil // spin --B
 I->next->locked := false ---D

A & B は同じ変数 ( predecessor->next & I->next ) と C & D ( locked variable ) にアクセスしていますが、アクセスする前にロックされていません。ここで何か不足していますか？

4

1 に答える 1

1

これらの同時アクセスが競合する可能性があるのは事実ですが、アルゴリズムはそれを許容するように設計されています。

B でのスピンは、実際には A との競合を防ぐためのものです。D では、I->next非 nil である必要があります。I->next(ここで知られてpredecessor->nextいる) は A によって非 nil に設定されています。お気づきのように、これは競合する可能性があるため、B には回転ループがあり、他のスレッドがI->next有効なものに設定されるのを待ちます。

C と D を見てみましょう。repeat while I->locked線は、ロックの実際の「回転」部分です。ロックを取得しようとしているスレッドが、別のスレッドがロックを解放するのを待たなければならない場合、そのスレッドはこのループでスピンします。取得スレッドが に到達する前にI->next->locked、ロックを解放するスレッドが に設定されている場合、ループはまったく開始されません。falserepeat while I->locked

于 2013-05-03T16:06:07.230 に答える