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 正在访问同一个变量（前任->下一个 & I->下一个）以及 C & D（锁定变量），但它们在访问之前没有被锁定。我在这里错过了什么吗？

4

1 回答 1

1

确实，这些并发访问可以竞争，但该算法旨在容忍这种情况。

在 B 处旋转实际上是为了防止与 A 比赛。在 D 处，我们需要I->next非零。I->next（此处称为predecessor->next）由 A 设置为非零。正如您所注意到的，这可能会竞争，因此 B 处有一个旋转循环以等待另一个线程设置I->next为有效的值。

让我们看看C&D。repeat while I->locked线是锁的实际“旋转”部分；如果一个线程试图获取锁必须等待另一个线程释放它，它会在这个循环中旋转。如果释放锁的线程在获取线程到达之前设置I->next->locked为，则循环将永远不会开始。falserepeat while I->locked

于 2013-05-03T16:06:07.230 回答