在linux中的内存分配是否无阻塞?

我很好奇,知道是否使用默认的新运算符分配内存是一个非阻塞操作。

例如

struct Node { int a,b; }; 

 Node foo = new Node(); 

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

我问的原因是因为我有一个并发的数据结构,创build新的节点。 然后我修改了algorithm来回收节点。 这两种algorithm的吞吐量性能在24核心机器上几乎是相同的。 然后,我创build了一个在所有系统内核上运行的干扰程序,以便尽可能多地创build操作系统。 创build新节点的algorithm的吞吐量性能相对于再循环节点的algorithm减less了5倍。

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

谢谢。

*编辑:指向我的Linux内存分配器的代码也将有所帮助。 我试图在发布这个问题之前寻找,但无法find它。

Solutions Collecting From Web of "在linux中的内存分配是否无阻塞?"

在我看来,如果你的干扰应用程序使用新的/删除(malloc / free),那么干扰应用程序会干扰非循环测试更多。 但是我不知道你的干扰测试是如何实施的。

根据你如何回收(即如果你使用pthread mutexes god禁用),你的回收代码可能会很慢(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 } 

注意,你将不得不去128位结构的64位操作系统。 所以全球回收堆现在看起来像这样:

 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; 

我敢打赌,如果你以这种方式回收,你会看到perf的增加。

在多线程系统中, malloc()free() (以及new / delete )通常使用同步原语来使它们安全地从多个线程调用。

这种同步还会影响某些应用程序的性能,尤其是在高度并行环境中执行大量分配和重新分配的应用程序。 更高效的多线程内存分配器是一个活跃的研究领域 – 请参阅两个知名的jemalloctcmalloc

这真的和这个问题差不多 。

基本上, malloc没有被定义为线程安全的,但是实现者可以自由地添加实现来使线程安全。 从你的描述来看,这听起来像你的特定版本。

可以肯定的是,用欧比旺的话来说就是“使用源泉,卢克”。 malloc源代码将在周围,通常是非常简单的阅读。

@Mark,你可以通过获取标准的GNU libc源码

 $ git clone git://sourceware.org/git/glibc.git $ cd glibc $ git checkout --track -b glibc-2_11-branch origin/release/2.11/master 

另见这里 。 请记住, malloc是在手册第3节 – 这是一个库函数,所以它不会在你的内核源码。 但是,您可能需要读入brksbrkgetrlimitsetrlimit之类的内容来查找内核的功能。

还有一个环节: GCC项目 。

好的,还有一个(我可以随时停止): 这里有一个页面 ,您可以从中下载源代码。 解压文件,你应该在./malloc/malloc.c找到它。

这个问题有很多好的反应: 在多线程的C / C ++中,malloc / new在分配内存的时候锁定了堆。

有共识就是锁定。 因此,一个大的分配或一个需要交换的分配可能会阻塞另一个线程中较小的分配,即使较小的分配可能完成,如果不是正在进行的较大分配。

海湾合作委员会的新是线程安全的,如果你用pthreads支持编译,但这不是你真正要求的。

我知道在Windows中,你可以创建自己的堆,可以用来在程序开始时设置内存。 我不知道任何Linux / Unix调用做类似的事情。

简短的回答:不。

一个线程可以位于new node()的中间,另一个线程也可以执行new node() 。 第一个线程可以暂停,第二个线程可以先完成。 没关系。 (假设你的构造函数中没有使用互斥体)

较长的答案:多线程是一个丛林。 线程不安全的代码可能会正常工作十年,然后每天都会失败一周。 竞争条件可能不会在您的机器上引起任何麻烦,但会炸毁客户的机器。 多线程应用程序引入了一定程度的不确定性,这需要额外的努力来编写和理解。

那么,为什么这两个程序有一天运行几乎一样,并与CPU争夺大不相同呢? 我不知道。 new不阻止其他线程做new事情,所以不是这样。 我怀疑,由于新增/删除的额外开销,操作系统有更多的机会抢占你的程序(甚至更有可能这样做)。 因此,在没有任何干扰的情况下,两个程序就可以随心所欲地获得CPU,并且运行良好 – 但是当CPU是稀缺资源时,新的/删除程序比回收程序更频繁地被碰撞。 看到? 它支付回收;-)