无锁并发队列

Question

这段代码片段来自这里给出的ConcurrentQueue实现。

internal bool TryPeek(out T result) 
{
    result = default(T); 
    int lowLocal = Low;
    if (lowLocal > High)
        return false;
    SpinWait spin = new SpinWait(); 
    while (m_state[lowLocal] == 0)
    { 
        spin.SpinOnce(); 
    }
    result = m_array[lowLocal]; 
    return true;
}

这是一个关于锁的问题，是否真的是无锁而不是自旋锁？

- Hamlet Hakobyan

---

旋转不等同于锁定。你认为有哪些地方会锁定？ - Jon Skeet

仅供参考，在许多学术文献中，自旋锁被认为是锁定。锁定的实现方式并不重要，重要的是它是否保证仅延迟有限时间的进展。您可以编写仅使用自旋的算法，但这些算法仍然不被视为无锁定算法。 - jalf

虽然我理解代码示例与所提问的问题有关，但需要注意的是，该代码不是基于自由软件许可证MS-RSL。发布此代码会永久地使任何查看它的人无法在其他.NET实现的代码区域上工作。 请在将来发布代码时记住这一点。 - cdhowie

根据MS-RSL许可证，“该许可证禁止除了查看代码以供参考之外的所有源代码使用。”我认为这篇文章没有违反任何许可限制。 - Hamlet Hakobyan

@axe 在现实世界中这非常重要。 - John

Answer 1

旋转锁是一种锁。这在MSDN，Wikipedia和许多其他资源中都有说明。 它不是关于单词的问题。无锁是一种保证。这并不意味着代码不应该使用锁语句。如果有系统范围内的进展保证，则算法是无锁。我没有看到这段代码与使用锁的代码之间有任何区别。唯一的区别是旋转使用忙等待和线程让渡而不是将线程置于睡眠模式。 我不明白这如何保证系统范围内的进程，所以我个人认为这不是无锁实现。至少不是此函数。

- axe

---

无锁并不保证系统整体进展；这是无等待的。无锁表示至少有一个线程将会前进，而不管其他线程如何。 - Tamas Ionut

@TamasIonut 如果至少有一个线程保证可以前进，那不是系统范围内的进展吗？ - ftfish

Answer 2

无锁编程是指不使用锁。自旋等待不是锁定操作。有许多同步数据访问的方法可以不使用锁。执行自旋等待是其中之一（众多选项之一）。并非所有无锁代码都会使用自旋等待。

- Servy

---

不，它并不会。无锁意味着保证系统范围内的进展。当状态未设置时，10个线程调用此函数将永远不会有任何进展。你甚至可能在这里遇到活锁。在无锁算法中不能同时存在死锁和活锁，这就是无锁保证的全部意义所在。 - axe

Answer 3

旋转是将CPU置于紧密循环中，而不放弃其当前的处理器时间片，避免了用户提供的循环可能创建的问题。如果已知状态更改即将发生，则此方法非常有用。对于普通代码来说，这很少是最佳选项，并且对于这种专业情况来说，代表着锁定的替代选择。

因此，是的，根据.NET Framework中使用的术语，该代码是无锁的。

http://msdn.microsoft.com/en-us/library/hh228603.aspx

- Eric J.