The proper use of atomism

Question

I wrote a small, lightweight vector-based push / pop queue (figured it should be fast) as follows:

template <typename T> class MyVectorQueue{

public:

    MyVectorQueue (size_t sz):my_queue(sz),start(0),end(0){}

    void push(const T& val){
       size_t idx=atomic_fetch_add(&end,1UL);
       if (idx==my_queue.size())
          throw std::runtime_error("Limit reached, initialize to larger vector");
       my_queue[idx]=val;
    }

    const T& pop(){
        if (start==end) 
           return end__;
        return my_queue[start.fetch_add(1UL)];
    }

    size_t empty()
    {
        return end==start;
    }

    const T& end() {
        return end__;
    }

private:
    T end__;
    std::atomic<size_t> start,end;
    std::vector<T> my_queue;    
}; 

The size of the vector must be known and I wonder why this is not thread safe? In what circumstances does this destroy my structure?

Answer 1

Your start, and endare atomic variables, but the use std::vector::operator[]is not an atomic operation, which makes it unsafe for the flows.

---

Suppose you have 10 threads and the size vectoris 5. Now suppose all of them are executed, say push.

, 10 , , , if (end==my_queue.size()) false, as end , - vector .

, end std::vector::operator[]. , 5 "" .

Answer 2

operator[] , , . , , undefined (, , ).

, start end, vector . , , push, end, operator[], . std:: deque:

std::mutex mutex;
std::deque<T> my_queue;

void push(const T& val){
   std::lock_guard<std::mutex> guard(mutex);
   //..code to check if full 
   my_queue.push_back(val);
}

const T& pop(){
    std::lock_guard<std::mutex> guard(mutex);
    //code to check if empty and that start index does not pass end index
    T item=my_queue.front();
    my_queue.pop_front();
    return item;
}

Answer 3

, . , .

vector, , , . " ", , , .

vector::operator[] , , . , vector::operator[] , , . - , concurrency ( , - LEA).
fetch_add , , , . , , , . , (.. "" ). , push.

pop, ( push) fetch_add (, , ) operator[].
, if(start==end) , operator[] . , - . :

• ( ) start, end ( ), , .
• The next thread may increase startafter this check, but before it is displayed fetch_addinside the call operator[], which will lead to indexing outside the bounds and invoke undefined behavior.

The non-intuitive thing to note here is that although you are doing the “right thing” with atomic operations, the program will still behave differently, since not only individual operations must be atomic.