1

I'm trying to write implementation of thread safe bounded on both sides stack without blocking.
In push operation I need to compare size with capacity and, if they not equal then set new head element for stack.
What is true way for do it?
If I write 

if (size == cap) {
   return;
}

// append element

I won't be sure then other thread won't push last value inside stack immediately after comparing. 

#include <atomic>
#include <boost/next_prior.hpp>
#include <boost/lockfree/spsc_queue.hpp>
#include <boost/function.hpp>

template<typename T>
struct Node
{
    Node(const T& data)
        :data(data), next(nullptr) {}

public:
    T data;

    Node* next;
};

template <typename T>
class Stack {
    using WriteCallback = typename std::function<void (const T&)>;
    using ReadCallback  = typename std::function<void (T&&)>;

    template<typename T1>
    using queue = boost::lockfree::spsc_queue<T1>;

public:
    Stack(int cap)
        :head(nullptr),
         size(0),
         cap(cap),
         onWrite(0),
         onRead(0)
    {}

    void push(const T& val, WriteCallback cb)
    {
        if (size == cap) {
            onWrite.push(cb);
            return;
        }
        // insertion will be here
    }

private:
    Node* head;

    std::atomic<int> size;
    std::atomic<int> cap;

    queue<WriteCallback> onWrite;
    queue<ReadCallback>  onRead;
};
sm4ll_3gg
  • 217
  • 4
  • 10
  • `size == cap` isn't an atomic operation. You have to use `std::atomic` values to guarantee that. – πάντα ῥεῖ Nov 11 '18 at 17:42
  • @πάνταῥεῖ I'm using it. `size` and `cap` is `std::atomic`. I'm worried about synchronizing comparing and inserting operations without blocking – sm4ll_3gg Nov 11 '18 at 17:47
  • Please put that (the variable definitions) into your code example, that's important. – πάντα ῥεῖ Nov 11 '18 at 17:52
  • @πάνταῥεῖ I've appended current version of code – sm4ll_3gg Nov 11 '18 at 17:59
  • Atomicity depends on the processor. Many processors require two instructions: compare, then branch depending on the result, e.g. branch if equal. Some processors have the capability to conditionally execute instructions, so there may be a possibility of an atomic operation. – Thomas Matthews Nov 11 '18 at 18:03
  • In the embedded systems world, if you want to prevent task swapping, you would disable interrupts before the comparison and enable afterwards. You may want to look up *mutexes*. – Thomas Matthews Nov 11 '18 at 18:05
  • Does `std::atomic` guarantee atomic `==`? There is no `==` overload. – user4581301 Nov 11 '18 at 18:07
  • 2
    It doesn't care if `size == cap` is atomic or not. After determining the result of the comparison more code follows. Also this code must be synchronized with the comparison. Use a mutex or any synchronization object of your OS, e.g. Critical Section for Windows. – harper Nov 11 '18 at 18:09
  • That's kind of what I was thinking. It's like [the big failing of Java's `vector`](https://stackoverflow.com/questions/1386275/why-is-java-vector-and-stack-class-considered-obsolete-or-deprecated). Yeah, it's synchronized, but so what? Nothing else around it is. – user4581301 Nov 11 '18 at 18:11
  • @ThomasMatthews Than you very much, but it's just university project and I have to write it without using mutexes. And I really don't understand how I can do it because after `size` and `cap` comparing I need take element from `onWrite` queue or take `cp` parameter if it empty and there operation won't guarantee thread safe – sm4ll_3gg Nov 11 '18 at 18:11
  • If you're already using a boost queue... consider using `boost::lockfree::fixed_sized` as per `https://www.boost.org/doc/libs/1_68_0/doc/html/boost/lockfree/queue.html` – Lawrence Nov 12 '18 at 01:25

1 Answers1

0

Are you looking for the atomic compare and swap?

You may use either the atomic_compare_exchange from C11, if it's available for your compiler, or look for system-dependent and compiler-dependent lock cmpxchg intrinsic.

For example, for msvc: https://msdn.microsoft.com/en-us/library/ttk2z1ws.aspx

Edit: just found this in C++ 11: std::atomic::compare_exchange_weak / std::atomic::compare_exchange_strong?

Victor Istomin
  • 1,107
  • 8
  • 14