1024cores

Search this site

 
Home‎ > ‎Lockfree Algorithms‎ > ‎

Object Life-time Management

Object life-time management is one of the fundamental problems in concurrent algorithms, to understand the problem consider the following simple lockfree stack algorithm:
struct node_t
{
    std::atomic<node_t*> next;
    T data;
};

struct stack_t
{
    std::atomic<node_t*> head;
};

void push(stack_t* stack, node_t* node)
{
    node_t* cmp = stack->head.load(std::memory_order_relaxed);
    do node->next.store(cmp, std::memory_order_relaxed);
    while (!stack->head.compare_exchange_weak(cmp, node, std::memory_order_release));
}

node_t* pop(stack_t* stack)
{
    node_t* node = stack->head.load(std::memory_order_consume);
    for (;;)
    {
        if (node == 0)
            break;
        // (***)
        node_t* next = node->next.load(std::memory_order_relaxed);
        if (stack->head.compare_exchange_weak(node, next, std::memory_order_release))
            break;
    }
    return node;
}

The article is not yet completed, however you can check out one of the solutions: Differential Reference Counting

Subpages (1): Differential Reference Counting
Comments