锁定MCS算法

Question

我想在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(锁定变量)，但它们在访问之前没有被锁定。我是不是漏掉了什么？

Answer 1

诚然，这些并发访问可能会竞争，但算法被设计为能够容忍这种情况。

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

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