2

想象一下这样的结构：

struct my_struct {
    uint32_t refs
    ...
}

通过查找表获取指针：

struct my_struct** table;

my_struct* my_struct_lookup(const char* name)
{
    my_struct* s = table[hash(name)];

    /* EDIT: Race condition here. */

    atomic_inc(&s->refs);

    return s;
}

在多线程模型中，取消引用和原子增量之间存在竞争。鉴于这是对性能非常关键的代码，我想知道解引用和原子增量之间的这种竞争通常是如何解决或解决的？

编辑：通过查找表获取指向my_struct结构的指针时，有必要首先取消对结构的引用以增加其引用计数。当其他线程可能正在更改引用计数并可能释放对象本身时，这会在多线程代码中产生问题，而另一个线程随后会取消引用指向不存在内存的指针。再加上先发制人和一些坏运气，这可能是灾难的根源。

4

3 回答 3

1

一种解决方案是使用 freelist，而不是 malloc() 和 free()。这有明显的缺点。

另一种是实现无锁垃圾回收（也称为安全内存回收）。

这个领域有很多专利，但是基于epoch的LFGC似乎是不受限制的。

使用此方法的结果是元素仅在没有线程指向它们时才被释放。

前一种解决方案很容易实现。当然，您需要一个无锁空闲列表，或者您的整个系统不再是无锁的。

后者确实不复杂，但需要学习有问题的算法，这需要一些时间和研究。

于 2012-04-26T22:51:42.400 回答
1

正如上面有人所说，您可以稍后释放内存链表，因此您的指针永远不会无效。在某些情况下，这是一种方便的方法。

或者....你可以用你的 32 位指针创建一个 64 位结构，并有 32 位用于引用计数和其他标志。如果将结构包装在联合中，则可以在结构上使用 64 位原子操作：

union my_struct_ref {
    struct { 
      unsigned int       cUse     : 16,
                         fDeleted : 1;    // etc 
      struct my_struct  *s;
    } Data;
    unsigned long n64;
}

您可以以可读的方式使用结构的数据部分，并且可以在 n64 位部分上使用 CAS。

my_struct* my_struct_lookup(const char* name)
{
    struct my_struct_ref Old, New;
    int iHash = hash(name);

    // concurrency loop
    while (1) {
      Old.n64 = table[iHash].n64;
      if (Old.Data.fDeleted)
        return NULL;
      New.n64 = Old.n64;
      New.Data.cRef++;
      if (CAS(&table[iHash].n64, Old.n64, New.n64)) // CAS = atomic compare and swap
        return New.Data.s; // success
      // we get here if some other thread changed the count or deleted our pointer
      // in between when we got a copy of it int old.  Just loop to try again.
    } 
}

如果您使用 64 位指针，则需要执行 128 位 CAS。

于 2012-05-07T17:45:36.067 回答
0

除了您确定的种族之外，您还有一个普遍的内存一致性问题。

即使您可以以无锁方式使表修改原子化，my_struct*与上次修改它的线程相比，从不同线程看到的内存块仍然可能是“陈旧的”。这不适用于my_struct.refs（前提是您始终使用原子访问它），但适用于所有其他字段。这是每个 CPU 内核“私有”的写入缓冲区和高速缓存的结果。

保证您看到正确的内存内容的唯一方法是使用内存屏障。然而，一个典型的锁也是一个内存屏障，那么为什么不首先使用锁呢？

无锁编程比最初看起来要复杂得多，OTOH 锁可以非常快，尤其是在很少发生争用时。您是否真的对基于锁的实现进行了基准测试并确认锁定确实是您的瓶颈？

于 2012-04-26T23:08:28.830 回答