Silberschatz 原子增量说明

Question

比较和交换函数的 Silberschatz 实现如下

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

可用于实现原子自增函数

void increment(atomic_int *v)
{
    int temp;
    do {
        temp = *v;
    }
    while (temp != compare_and_swap(v, temp, temp+1));
}

我的问题是：在什么情况下 do-while 条件为真以触发第二个循环并因此触发第二个 compare_and_swap 调用？

根据我的理解，compare_and_swap总是returns旧的v但是，在调用它之前，temp值是用v值初始化的，并且所以首先 compare_and_swap returns temp 条件失败导致退出循环。

我是不是漏掉了什么？

Answer 1

在increment函数实现中，如果自增操作成功，do-while循环的测试条件将失败。

因此，您对 compare_and_swap 函数总是 returns 同一个变量的理解是绝对正确的，因为函数的执行没有任何中断。

但是对于多个线程试图访问同一个变量，情况可能并非如此。在这些情况下，我们得到 do-while 循环的测试条件为真，因此尝试在第二个循环中增加变量，依此类推。

例如：假设有两个线程写入同一个变量v=0。第一个线程正在执行 increment 函数，并在指令 temp = *v; 之后被中断。在此之后，第二个线程获得控制权并完成增量功能，之后仅将控制权返回给线程 1。

所以，在这种情况下，作为控件returns，变量的状态如下：

v = 1 \ Got incremented after the thread-2 execution completed
temp = 0 \ Was set before thread-1 was interrupted

所以现在，当while测试条件执行时，compare_and_swap returns 1，但是temp为0。因此测试失败并重新执行循环体。

Silberschatz 原子增量说明

Silberschatz atomic increment clarification

c

concurrency

atomic

compare-and-swap