满足无锁进程保证的编写算法或数据结构的困难之一是动态内存分配:调用类似malloc
或new
的调用不保证以便携方式无锁。然而,存在许多无锁实现malloc
或new
,并且还有各种可用于实现无锁算法/数据结构的无锁内存分配器。动态锁定内存分配器
但是,我仍然不明白如何实际上完全满足无锁进度保证,除非你特别限制你的数据结构或算法到一些预先分配的静态内存池。但是,如果你需要动态内存分配,我不明白如何任何指称的无锁内存分配器永远真正无锁的长期。问题是无论您的无锁malloc
或new
可能有多惊人,最终可能会导致内存不足,此时您必须要求操作系统提供更多内存。这意味着最终你必须调用brk()
或mmap()
或者一些这样的低级别等价物,以实际获得更多的内存。并且不能保证任何这些低级调用都是以无锁方式实现的。 (除非您使用的是像MS-DOS这样的不提供内存保护的古老操作系统,或者您自己编写了完全无锁的操作系统 - 两种不实用的方案或者可能)。那么,怎样才能使任何动态内存分配器真正无锁?
你说的没错,但是......由于分配只能从OS请求大块,并且不需要及时发布它们,对“sbrk()”或任何其他语言的调用总数可以严格限制到无关紧要的程度。当然,这并不能满足硬实时要求,但我认为即使动态分配完全无锁,也不会满足这些要求。 –
您是否担心延迟,或者您是否担心使用https://en.wikipedia.org/wiki/Non-blocking_algorithm?如果是后者,我认为最好的操作系统使得线程无法在内核中睡眠,同时持有一个会阻止其他线程使用mmap的锁。所以就编写一个非阻塞算法而言,我认为使用'mmap'并不是一个问题,因为如果一个线程可以在保持一个线程的同时睡眠,那么锁只是一个问题。临界区内的一对CPU高速缓存未命中可能是你得到的最差的。 –
在真实系统上运行的所有分配器在某个时刻不得不耗尽内存;在分配静态池时运行的无锁分配器在操作系统认为你已经拥有足够的时间的情况下与正常的分配器没什么质的区别。 –