我很想知道使用默认 new 运算符分配内存是否是非阻塞操作。

例如

struct Node {
    int a,b;
};

...

Node foo = new Node();

如果多个线程尝试创建一个新节点，并且其中一个在分配过程中被操作系统挂起，它会阻止其他线程继续进行吗？

我问的原因是因为我有一个创建新节点的并发数据结构。然后我修改了算法以回收节点。这两种算法的吞吐量性能在 24 核机器上几乎相同。但是，我随后创建了一个在所有系统内核上运行的干扰程序，以便尽可能多地抢占操作系统。创建新节点的算法的吞吐量性能相对于回收节点的算法下降了 5 倍。

我很想知道为什么会发生这种情况。

谢谢。

*编辑:将我指向 linux 的 c++ 内存分配器的代码也会很有帮助。我在发布此问题之前尝试查看，但找不到它。

最佳答案

在我看来，如果您的干扰应用程序正在使用新/删除(malloc/free)，那么干扰应用程序会更多地干扰非回收测试。但我不知道你的干扰测试是如何实现的。

根据您的回收方式(即，如果您使用 pthread 互斥锁，上帝禁止)，您的回收代码可能会很慢(gcc atomic ops 在实现回收时会快 40 倍)。

Malloc，至少在某些平台上的某些变体中，已经知道线程了。使用 gcc 上的编译器开关来确保你得到它。较新的算法为 每个 线程维护小内存块池，因此如果您的线程有可用的小项目，则没有或几乎没有阻塞。我对此进行了过度简化，这取决于您的系统使用的是什么 malloc。另外，如果你去分配数百万个项目来进行测试......那么你不会看到这种效果，因为小项目池的大小是有限的。或者也许你会。我不知道。如果您在分配后立即释放该项目，您将更有可能看到它。释放的小项目返回到小项目列表而不是共享堆。尽管“当线程 B 释放由线程 A 分配的项目时会发生什么”是一个问题，可能会或可能不会在您的 malloc 版本上处理，并且可能不会以非阻塞方式处理。当然，如果您在大型测试期间没有立即释放，那么线程将不得不多次重新填充其小项目列表。如果有多个线程尝试，这可能会阻塞。最后，在某些时候，您的进程的堆会向系统请求堆内存，这显然会阻塞。

那么你在使用小内存项目吗？对于您的 malloc，我不知道什么是小，但是如果您 < 1k，那肯定是小了。您是一个接一个地分配和释放，还是分配数千个节点然后释放数千个节点？您的干扰应用程序分配了吗？所有这些都会影响结果。="">

如何使用原子操作进行回收(CAS = 比较和交换):

首先将 pNextFreeNode 添加到您的节点对象。我使用了 void*，你可以使用你的类型。此代码适用于 32 位指针，但也适用于 64 位。然后做一个全局回收堆。

void *_pRecycleHead; // global head of recycle list. 

加入回收堆:

void *Old;
while (1) { // concurrency loop
  Old = _pRecycleHead;  // copy the state of the world. We operate on the copy
  pFreedNode->pNextFreeNode = Old; // chain the new node to the current head of recycled items
  if (CAS(&_pRecycleHead, Old, pFreedNode))  // switch head of recycled items to new node
    break; // success
}

从堆中移除:

void *Old;
while (Old = _pRecycleHead) { // concurrency loop, only look for recycled items if the head aint null
  if (CAS(&_pRecycleHead, Old, Old->pNextFreeNode))  // switch head to head->next.
    break; // success
}
pNodeYoucanUseNow = Old;

使用 CAS 意味着只有当您更改的项目是您传入的旧值时，操作才会成功。如果有竞争并且另一个线程先到达那里，那么旧​​值将不同。在现实生活中，这种比赛很少发生。 CAS 只比实际设置一个值慢一点，所以与互斥锁相比......它摇摆不定。

如果您快速添加和删除相同的项目，则上面的从堆中删除具有竞争条件。我们通过向 CAS'able 数据添加版本号来解决这个问题。如果你在指向回收堆头部的指针的同时执行版本#，你就赢了。使用 union 。 CAS 64 位无需额外费用。

union TRecycle {
  struct {
    int iVersion;
    void *pRecycleHead;
  } ;  // we can set these.  Note, i didn't name this struct.  You may have to if you want ANSI
  unsigned long long n64;  // we cas this
}

注意，对于 64 位操作系统，您必须使用 128 位结构。所以现在全局回收堆是这样的:

TRecycle _RecycleHead;

加入回收堆:

while (1) { // concurrency loop
  TRecycle New,Old;
  Old.n64 = _RecycleHead.n64;  // copy state
  New.n64 = Old.n64;  // new state starts as a copy
  pFreedNode->pNextFreeNode = Old.pRecycleHead;  // link item to be recycled into recycle pile
  New.pRecycleHead = pFreedNode;  // make the new state
  New.iVersion++;  // adding item to list increments the version.
  if (CAS(&_RecycleHead.n64, Old.n64, New.n64))  // now if version changed...we fail
    break; // success
}

从堆中移除:

while (1) { // concurrency loop
  TRecycle New,Old;
  Old.n64 = _RecycleHead.n64;  // copy state
  New.n64 = Old.n64;  // new state starts as a copy
  New.pRecycleHead = New.pRecycledHead.pNextFreeNode;  // new will skip over first item in recycle list so we can have that item.
  New.iVersion++;  // taking an item off the list increments the version.
  if (CAS(&_RecycleHead.n64, Old.n64, New.n64))  // we fail if version is different.
    break; // success
}
pNodeYouCanUseNow = Old.pRecycledHead;

我敢打赌，如果您以这种方式回收利用，您会看到性能提升。

关于c++ - linux中的内存分配是非阻塞的吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4600208/