C中的原子递减和测试

Question

我正在用 C 语言实现一个引用计数系统，它需要使用多线程。因此，我需要一种方法来减少整数引用计数并通过一个原子操作测试结果是否为零。我可以使用C11和stdatomic.h，但似乎没有递减和测试操作。

解决此问题的最佳（即最便携）方法是什么？我可以使用 stdatomic.h 函数来实现吗？

这是引用计数的核心（伪代码）：

retain(object) {
    ++object.ref_count;  // pretty easy to make this atomic
} 

release(object) {
    if (--object.ref_count == 0)  // need this to be atomic also
        free(object)
}

Answer 1

你好像对C11的原子有误解。原子限定一种类型，而不是单个操作。

如果您使用 _Atomic 声明您的变量，则对它的所有操作都是原子的。因此，如果您对原子操作的默认 "sequential consistency" 感到满意（您应该这样做），那么您只需要一个额外的 _Atomic 限定即可。前缀 -- 运算符应该可以很好地满足您的需求。

如果你想处理不同类型的一致性，你可以使用 atomic_fetch_sub，例如只有这样，您才能获得修改前的值，而不是修改后的值。因此，与其与 0 进行比较，不如将其与 1.

进行比较

Answer 2

抱歉打扰了游行，但这可以不能使用上述机制完成，无论使用原子increment/decrement原语。

release 执行 free 的瞬间，对象变得无效 [我们必须假设另一个线程立即执行 malloc 并重新调整内存用途] 和 no 可以通过 any 线程进一步访问它。

在 free 之后，不能为该对象调用 retain 和 release。甚至不仅仅是探测 ref_count 值。简单的 ref_count inc/dec [原子与否] 不足以 handle/prevent

(1) 线程间锁必须驻留在对象外部并且它不能受制于任何 alloc/free.

(2) 必须通过某种列表遍历来访问对象。即有活动对象列表。

(3) 对列表的访问由互斥体控制。因此，实际的 inc/dec [可能] 而不是 需要是原子的 [但可能是为了额外的安全]

(4) 使用列表确保一旦一个对象被销毁，没有线程会试图访问它，因为它已经从活动对象列表中移除并且线程不能再"see"它.

retain 和 release 必须做如下事情：

int
retain(List *list,Object *object)
{
    int match = 0;

    lock_list(list);

    for (objnow in list) {
        if (objnow is object) {
            ++objnow.ref_count;
            match = 1;
            break;
        }
    }

    unlock_list(list);

    return match;
}

int
release(List *list,Object *object)
{
    int match = 0;

    lock_list(list);

    for (objnow in list) {
        if (objnow is object) {
            match = 1;
            if (--objnow.ref_count == 0) {
                unlink_from_list(list,objnow);
                free(objnow);
                match = -1;
                break;
            }
        }
    }

    unlock_list(list);

    return match;
}

上面列表中的 mutex/lock 方法也可以用 RCU 来完成，但是有点复杂。

当然，这里的"list"不一定是简单的链表。它可以是 B 树或其他类型的容器。

一个概念： 实际上，当考虑它时，如果一个对象不依附于某种global/interthread列表中，ref_count 往往会失去其意义。或者更重要的是，为什么 ref_count 上会有线程间争用？

如果我们只有一些 "floating" 对象不在列表中 [或在本地每线程列表中]，为什么多个线程会尝试到 up/down ref_count 因为在那个时候单个线程更有可能 "own" 对象。

否则，重新构建系统可能是为了使其更加predictable/stable。

更新：

A thread may not bump the reference count unless it already has a reference, since a reference is needed to access the object.

通过引用，在这里，我假设你的意思是线程已经完成了一个 retain，将做一些事情，然后再做一个 release。

Thus if the ref count hits zero, no thread is currently accessing the object nor can any thread do so in the future. Thus it's safe to destroy it.

销毁它可能是安全的，但没有防止多个线程访问对象内的数据[非锁定]单元格并发生碰撞的互锁。

问题是让子线程执行 free。

假设我们有一个主线程，它创建了一个对象 obj1，然后将其传递给两个线程 tA 和 tB，这两个线程在内部将其称为 objA 和 objB 分别。

主线程以零引用计数开始 obj1。

考虑以下时间轴：

tA: retain(objA)
tA: // do stuff ...
tA: release(objA)

对象引用计数现在为零，内存区域已被释放。任何进一步的访问都是无效的。 tB 不能以任何方式访问 obj1 的内存区域。

现在，[如果我们选择忽略]：

tB: retain(objB)
tB: // do stuff ...
tB: release(objB)

tB 的版本将看到引用计数变为零，并将执行 free。这是 double free of obj1

但是，tB 甚至不能执行 retain，因为 obj1 的内存可能已被另一个线程重新分配：(1) [= 的主线程45=] 或 (2) 另一个线程 tX 将内存用于完全不相关的目的

在 (1) 的情况下，tB 的 objB 现在更改为 obj2 而不是 obj1

在(2)的情况下，objB在tX的无关内存区域上乱写。即使是一瞬间的inc/dec也是灾难性的

因此，在上面，存在竞争条件、访问已释放的内存、双重释放以及写入（例如）objtype_x，就好像它是 objtype_a。

那么，如果我们用 1 而不是 0 来初始化主线程呢？

现在，事情变得更好了。竞争条件被消除。但是，tA 和 tB 将 永远不会 看到引用计数下降到低于 1，因此他们中的任何一个都不会做 free。因此，让各个线程执行 free 是一个有争议的问题。

主线程必须执行 free，这将是安全的。但是，main 无法知道 obj1 处于什么状态。也就是说，它是否已被 tA、tB 或两者处理过？

所以，也许对象需要一个 done 掩码，它与 1 << tA 和 1 << tB [原子地] 进行或运算，main 将查看它以了解它何时可以执行free

或者，主线程，如果它知道只有 tA 和 tB 这两个线程会访问该对象，它可以将引用计数初始化为 2，并且这两个线程可以只做一个release 当他们完成对象时。

如果 tB 决定在完成自己的处理后需要将对象发送到 tC。

仅使用引用计数，如果给定对象必须在tA 之前 tB处理，则无法确保这一点。

在架构上，如果每个线程都有一个输入 queue/list [即互斥锁]，整个系统可能会工作得更好。主线程创建一个对象，将其排队到 tA。 tA 将其出列，确实有效，然后将其入列到 tB。每个线程都可能执行 "Y" 分叉。也就是说，tA 查看对象并决定将其发送到 tC，完全绕过 tB。最终，其中一个线程会将对象排回主线程（即已用对象的空闲列表或 post 主线程的结果（例如 map/reduce 的形式）。

将对象放在[可重用]空闲列表中（相对于free）会稍微简化一些事情，因为我们没有 "rug pull" 执行 free 的效果[with immediate malloc]，所以我们可以在对象中存储一些状态信息，即使对象是 "idle".

这样，我们就有了线程间管道系统的效果。

这种方法的优点之一[我已经成功地用于运输生产系统]是一旦对象排队到线程，线程"owns"对象和大部分访问需要'是原子的。

C中的原子递减和测试

Atomic decrement-and-test in C

c

atomic

c11

stdatomic