How to test my blocking queue actually blocks

user_1395740 0
Viewed 1001

I have a blocking queue (it would be really hard for me to change its implementation), and I want to test that it actually blocks. In particular, the pop methods must block if the queue is empty and unblock as soon as a push is performed. See the following pseudo C++11 code for the test:

BlockingQueue queue; // empty queue

thread pushThread([] 
{ 
    sleep(large_delay);
    queue.push(); 
});

queue.pop();

Obviously it is not perfect, because it may happen that the whole thread pushThread is executed and terminates before pop is called, even if the delay is large, and the larger the delay the more I have to wait for the test being over.

How can I properly ensure that pop is executed before push is called and that is blocks until push returns?

c++11 blocking multithreading unit-testing c++
3 Answers

I do not believe this is possible without adding some extra state and interfaces to your BlockingQueue.

Proof goes something like this. You want to wait until the reading thread is blocked on pop. But there is no way to distinguish between that and the thread being about to execute the pop. This remains true no matter what you put just before or after the call to pop itself.

If you really want to fix this with 100% reliability, you need to add some state inside the queue, guarded by the queue's mutex, that means "someone is waiting". The pop call then has to update that state just before it atomically releases the mutex and goes to sleep on the internal condition variable. The push thread can obtain the mutex and wait until "someone is waiting". To avoid a busy loop here, you will want to use the condition variable again.

All of this machinery is nearly as complicated as the queue itself, so maybe you will want to test it, too... This sort of multi-threaded code is where concepts like "code coverage" -- and arguably even unit testing itself -- break down a bit. There are just too many possible interleavings of operations.

In practice, I would probably go with your original approach of sleeping.

user_7684690 
template<class T>
struct async_queue {
  T pop() {
    auto l = lock();
    ++wait_count;
    cv.wait( l, [&]{ return !data.empty(); } );
    --wait_count;
    auto r = std::move(data.front());
    data.pop_front();
    return r;
  }
  void push(T in) {
    {
      auto l = lock();
      data.push_back( std::move(in) );
    }
    cv.notify_one();
  }
  void push_many(std::initializer_list<T> in) {
    {
      auto l = lock();
      for (auto&& x: in) 
        data.push_back( x );
    }
    cv.notify_all();
  }
  std::size_t readers_waiting() {
    return wait_count;
  }
  std::size_t data_waiting() const {
    auto l = lock();
    return data.size();
  }
private:
  std::queue<T> data;
  std::condition_variable cv;
  mutable std::mutex m;
  std::atomic<std::size_t> wait_count{0};
  auto lock() const { return std::unique_lock<std::mutex>(m); }

};

or somesuch.

In the push thread, busy wait on readers_waiting until it passes 1.

At which point you have the lock and are within cv.wait before the lock is unlocked. Do a push.

In theory an infinitely slow reader thread could have gotten into cv.wait and still be evaluating the first lambda by the time you call push, but an infinitely slow reader thread is no different than a blocked one...

This does, however, deal with slow thread startup and the like.

Using readers_waiting and data_waiting for anything other than debugging is usually code smell.

user_17746670
user_49521370
Related