mercredi 16 octobre 2019

A lock-free queue's push operation using compare_exchange_weak

I've come across a lock-free queue that supports multi-producer and a consumer, the push operation of the queue goes like this

inline void push(LT* item)
{

    LT *old = pushlist.load(std::memory_order_relaxed);
    do {
        item->next = old;
    } while (!pushlist.compare_exchange_weak(old, item, 
                                             std::memory_order_release));
}

pushlist is an atomic pointer-variable and I am thinking about a scenario where two threads are on this code

Thread1 :

  • T1# Loads the pointer (won't LOCK# anything)
  • T2# Goes to loop and hook the head (old) into new item
  • T3# Now in the cmpxchg(LOCK#); it expects head (old) to be * this-- which is true, so swap will be successful

Thread2:

  • T2# Loads the pointer (won't LOCK# anything)
  • T3# Goes to loop and hook the head (old) into its new item
  • T4# Now cmpxchg will expect head (old) to be * this-- which is not I guess, because Thread1 already changed it, so old isn't the head anymore, operation will be unsuccessful......now, will it not going to spin?

I tested it, works fine, yet I am not clear how it does.

auto work = [&p](auto name){
    int i{0};
    linked_item<int> dummy{};
    for(; i < 100 ; ++i){
        p.push(&dummy);
    }
    std::cout<<name<<" finished"<< i << "\n";
};
std::thread t1{work, "t1"}, t2{work, "t2"};
t1.join(); t2.join();

Aucun commentaire:

Enregistrer un commentaire