将无锁线性分配改进为无等待

Question

给出以下简单的无锁线性分配算法:

bool allocate(size_type size, size_type& offset)
{
size_type pos;
size_type new_pos;

pos = m_pos.load(std::memory_order_acquire);
do
{
new_pos = pos + size;
if (new_pos > m_end)
return false;
}
while (!m_pos.compare_exchange_weak(pos, new_pos, std::memory_order_acq_rel, std::memory_order_acquire));
offset = pos;
return true;
}

我想进一步改进它，使其在快速路径上无等待，完全丢弃cas循环，最好使用fetch_add，但是我不确定如何处理分配失败的情况，因为请求的大小大于可用的大小-当检测到这一点时，fetch_add已经增加了现在超过有效范围的位置，可以同时由其他线程加载。这将进一步增加它，并产生没有空间分配的错误错觉。在这条路径中仍然需要某种自旋等待循环，但是我不能想出一个有效的解决方案。

任何想法?

Answer 1

假设我们有256MB的空间。第一个线程尝试分配257MB的空间，显然返回false。

为了处理这个问题，可以存储两个int型:

• 一个原子，带有current_pos
• 一个非原子，容量

:

// first attempt, atomic load current_pos
// to early exit when the allocation would certainly fail,
// which will reduce wasting memory
current := atomic_load(current_pos)
if ( current + required > capacity) { return error }
// second attempt, atomic fetch_and_add current_pos
// it can still fail, since other threads may advanced current_pos
// in the background since the previous load
current := fetch_and_add(current_pos, required)
if ( current + required > capacity) {return error}

这是无等待的，可以处理OOM错误。