linux中的内存分配是非阻塞的吗？

Question

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

例如

struct Node {
    int a,b;
};

...

Node foo = new Node();

如果多个线程试图创建一个新节点,并且如果其中一个线程在分配过程中被操作系统暂停,它是否会阻止其他线程进展？

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

我很想知道为什么会这样.

谢谢.

*编辑:指向我的Linux的c ++内存分配器的代码也会有所帮助.在发布这个问题之前我试过了,但是找不到它.

Answer 1

在我看来,如果您的干扰应用程序使用new/delete(malloc/free),那么干扰应用程序将更多地干扰非循环测试.但我不知道你的干扰测试是如何实现的.

根据您的回收方式(例如,如果您使用pthread互斥体上帝禁止),您的回收代码可能会很慢(gcc原子操作在实施回收时会快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数据中添加版本#来解决这个问题.如果您在获得循环桩头部的指针的同时执行#版本.使用工会.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;

我敢打赌,如果你以这种方式回收,你会看到一个性能增加.