CMPXCHG 和关键部分实现

Question

CMPXCHG 语句的工作原理如下:

CMPXCHG (common, old, new):
    int temp
    temp <- common
    if common = old then
           common <- new
    return temp    

实现一个最简单的算法是什么？临界区，CMPXCHG 原子指令是否可用？

Answer 1

如果您想创建一个简单的关键部分(使用 Windows definition of a CRITICAL_SECTION )，您可以查看以下伪代码:

EnterCS(cs):
    If CMPXCHG(cs,0,1) = 0 
        Return True
    Return False

ExitCS:
    If CMPXCHG(cs,1,0) = 1 
        Return True
    Return False

然后使用它就变成了一个简单的例子:

If EnterCS(cs)
    SomeValue <- SomeValue + 10 
    ExitCS(cs)

这次的获取其实更像是一次尝试获取，为了延伸到CS更常见的获取方案，我们把方法改成这样

EnterCS(cs):
    While CMPXCHG(cs,0,1) != 0
        SpinOneCycle()
    Return True

这个简单的锁有其各种问题，例如无法处理递归，为此您需要保留递归锁计数。我建议使用操作系统提供的东西。如果您确实需要编写自己的锁，Intel 有一些关于编写高性能和可扩展自旋锁的出版物，您可以阅读其中一本针对 Xeon 处理器的出版物 here另一个用于 x86 here 。 Lockless Inc 也有一篇关于自旋锁的文章 here .