Creating a Blocking Queue

Question

Sometimes this implementation and execution of BlockingQueue just works. Sometimes it segfaults. Any idea why?

#include <thread>
using std::thread;
#include <mutex>
using std::mutex;
#include <iostream>
using std::cout;
using std::endl;
#include <queue>
using std::queue;
#include <string>
using std::string;
using std::to_string;
#include <functional>
using std::ref;

template <typename T>
class BlockingQueue {
private:
    mutex mutex_;
    queue<T> queue_;
public:
    T pop() {
        this->mutex_.lock();
        T value = this->queue_.front();
        this->queue_.pop();
        this->mutex_.unlock();
        return value;
    }

    void push(T value) {
        this->mutex_.lock();
        this->queue_.push(value);
        this->mutex_.unlock();
    }

    bool empty() {
        this->mutex_.lock();
        bool check = this->queue_.empty();
        this->mutex_.unlock();
        return check;
    }
};

void fillWorkQueue(BlockingQueue<string>& workQueue) {
    int size = 40000;
    for(int i = 0; i < size; i++)
        workQueue.push(to_string(i));
}

void doWork(BlockingQueue<string>& workQueue) {
    while(!workQueue.empty()) {
        workQueue.pop();
    }   
}

void multiThreaded() {
    BlockingQueue<string> workQueue;
    fillWorkQueue(workQueue);
    thread t1(doWork, ref(workQueue));
    thread t2(doWork, ref(workQueue));
    t1.join();
    t2.join();
    cout << "done\n";
}

int main() {
    cout << endl;

    // Multi Threaded
    cout << "multiThreaded\n";
    multiThreaded();
    cout << endl;
}

Solution 1

See here:

What do I get from front() of empty std container?

Bad things happen if you call .front() on an empty container, better check .empty() first.

Try:

T pop() {
    this->mutex_.lock();
    T value;
    if( !this->queue_.empty() )
    {
        value = this->queue_.front();  // undefined behavior if queue_ is empty
                                       // may segfault, may throw, etc.
        this->queue_.pop();
    }
    this->mutex_.unlock();
    return value;
}

Note: Since atomic operations are important on this kind of queue, I'd recommend API changes:

bool pop(T &t);  // returns false if there was nothing to read.

Better yet, if you're actually using this where it matters, you probably want to mark items in use before deleting in case of failure.

bool peekAndMark(T &t);  // allows one "marked" item per thread
void deleteMarked();     // if an item is marked correctly, pops it.
void unmark();           // abandons the mark. (rollback)

Solution 2

The problem should lay here:

while(!itemQueue.empty()) {
    itemQueue.pop();
}

You reserve the mutex when checking of a value is left, then you release the mutex and it might happen that another thread is executed, finds out that a value is left and pops it. In the worst case no item is left afterwards and the first thread tries to pop while no element is left.

The solution is to make the front/pop calls on the internal queue in the same section than the check for empty in the same locked section, then the behavior would always be defined.

Another suggestion would be to use std::lock_guard when working with mutex because it improves the readability and does ensure that the mutex is released no matter what happens.

Considering the fact those two advice, your pop method could look like:

T pop() {
    std::lock_guard lock(this->mutex_); //mutex_ is locked
    T value;
    if( !this->queue_.empty() )
    {
        value = this->queue_.front();
        this->queue_.pop();
    }
    return value;
} //mutex_ is freed

Comments

[Admin]

If it segfaults, I assume you could get the line of code where it happens? Might just be helpful to know...

[UldisK]

What happens if you check if the itemQueue is empty, then let other thread do some work and then pop() an item?

[Flexo]

This question has enough code that anyone can try it out and see for themselves where the problem is. There isn't much superfluous code either, so it's not far off a textbook SSCCE and certainly answerable.

[Casey]

@Flexo I have a hard time believing that "Where is the bug in this program?" could ever be a good question.

[Flexo]

Happy to explain my thinking on this one further on meta or in chat if you like, but please let's avoid chatting in comments.

[Admin]

@πάνταῥεῖ Actually, I just eschew std:: and C++ myself. Far rather work with C++/CLI, C#, C, Java, anything really except for vanilla C++ and STL. Any language defining exception as an unsafe misfeature deserves a miss in my book. I mean who implements an empty queue read as segfault?!

[πάντα ῥεῖ]

To implement Lock/Unlock sequences this way in c++ is error prone (and may be in other languages), since it's not exception safe. You can either use one of the std:lock_guard idioms provided by the c++ standard, or roll you own, if necessary easily!

[Chris Redford]

@ebyrob I agree on the API change. It is a good solution to avoiding the "what to use as the default value" problem.

[πάντα ῥεῖ]

+1 Just mention a standard or custom auto locker mechanism, and your answer should be perfect, though of the low quality question!

[Admin]

And what happens if itemQueue is empty? segfault, or exception, or undefined behavior. I believe the std::queue.front() behavior is the surprise here not that threads preempt each other. If you had mentioned it explicitly I wouldn't have bothered with an answer.

[πάντα ῥεῖ]

@ebyrob this->mutex_.lock()/this->mutex_.unlock(); You shouldn't do this directly! Use an appropriate scoped construction/destruction idiom instead!

[Chris Redford]

Okay @πάνταῥεῖ. I do agree that using unique_lock<mutex> lock(this->mutex_) results in more readable code.

[Theolodis]

@ebyrob I am talking about the pop method he implemented.

[Admin]

@Theolodis T value; Seriously? It seems like you copy-pasted my code.

[Admin]

@πάνταῥεῖ Sorry for being slow, I had to think about this a bit. You seem to attribute those 2 lines of code to me just because I kept them in my answer. I, very clearly, copy-pasted them from the question. Being a bit of an outsider to C++, it was very clear to me the misunderstanding about how .front() works. So, I chose to highlight pitfalls I am familiar with. I don't really know enough about lock_guard to comment. So I won't. Really, with std::string the only exception possible is out of memory. That should probably be fatal in most simple programs anyway.

[Killzone Kid]

did you mean std::lock_guard<std::mutex> lock(this->mutex_);?

[Theolodis]

@KillzoneKid depends on the mutex type you use.