c - 原子计数器，达到 0 时可以禁用

Question

我想实现以下支持以下操作的原子对象:

inc_and_get(X)              - increment the counter and return the previous value
dec(X)                      - decrement the counter
inc_and_disable_if_zero (x) - increment the counter, but if the value is zero, disable it
                              disable means it returns -1 for every operation

inc_and_get(X) 和 dec(X) 可以使用基本硬件原语实现

我感兴趣的是:

inc_and_disable_if_zero

递增对应于进入临界区，递减对应于离开。

进入临界区的线程可以决定定期进入(通过执行 inc_and_get)或尝试通过调用 inc_and_disable_if_zero 进入并禁用计数器(如果可能的话)(没有其他人在那里)

我认为可以用 CAS(X) 解决这个问题:

inc_and_disable_if_zero(X)
do {
    value = READ(X)
    if (value == 0) {
        next_value = -1;
        disable = TRUE;

    } else if (value > 0) {
        next_value = value + 1; // no good, :( , just increment
        disable = FALSE;

    } else {
        return (TRUE); // someone else disabled it

    }
} while (!CAS(value, next_value));

return (disable);

但我想知道是否有一种更优雅的方法来解决这个问题(使用一个简洁的原子操作)？

例如，如果计数器为零，则递增并设置 MSB ？

Answer 1

JFYI:CAS 有三个参数，指向原子变量的指针、旧值和新值。

您可以通过双重检查锁定(在自旋锁上)解决此问题:

int inc_and_disable_if_zero(Counter* X) {
    // fast path
    if (X->value == -1) {
        return -1;
    }
    lock(X->spinlock);
    if (X->value == -1) {
        unlock(X->spinlock);
        return -1;
    }
    if (X->value == 0) {
        X->value = -1;
        unlock(X->spinlock);
        return -1;
    }
    X->value++;
    int res = X->value;
    unlock(X->spinlock);
    return res;
}

在这种情况下，所有对计数器的更新都必须在自旋锁下执行。

int inc(Counter* X) {
    // fast path
    if (X->value == -1) { return -1; } // this value couldn't change so
                                       // there is no need for synchronization
    lock(X->spinlock);
    if (X->value == -1) { return -1; }
    X->value++;
    int res = X->value;
    unlock(X->spinlock);
    return res;
}

这种情况下性能会很好，spinlock加锁/解锁只是一个RMW操作，和CAS一样。

for example, increment and set MSB if counter is zero ?

我相信这在使用 TSX(事务同步扩展)的现代英特尔“Haswell”处理器上是可能的。我相信，对于常规 CAS 操作，这是不可能的。