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;
}

If it segfaults, I assume you could get the line of code where it happens? Might just be helpful to know... — , May 14 '14 at 17:59
What happens if you check if the `itemQueue` is empty, then let other thread do some work and then `pop()` an item? — UldisK, May 14 '14 at 17:59
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](http://www.sscce.org/) and certainly answerable. — Flexo, May 14 '14 at 20:05
@Flexo I have a hard time believing that "Where is the bug in this program?" could ever be a good question. — Casey, May 14 '14 at 20:37
Happy to explain my thinking on this one further on [meta](http://meta.stackoverflow.com) or in [chat](http://chat.stackexchange.com/rooms/2691/the-assembly) if you like, but please let's avoid chatting in comments. — Flexo, May 14 '14 at 20:49

score 5 · Accepted Answer · edited May 23 '17 at 12:23

5

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)

edited May 23 '17 at 12:23

Community

1
1

answered May 14 '14 at 18:03

@πάνταῥεῖ 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?! – May 14 '14 at 18:23
3

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`](http://en.cppreference.com/w/cpp/thread/lock_guard) idioms provided by the c++ standard, or roll you own, if necessary easily! – πάντα ῥεῖ May 14 '14 at 18:30
@ebyrob I agree on the API change. It is a good solution to avoiding the "what to use as the default value" problem. – Chris Redford May 14 '14 at 18:39
1

@ebyrob `this->mutex_.lock()`/`this->mutex_.unlock();` You shouldn't do this directly! Use an appropriate scoped construction/destruction idiom instead! – πάντα ῥεῖ May 14 '14 at 19:15
Okay @πάνταῥεῖ. I do agree that using `unique_lock lock(this->mutex_)` results in more readable code. – Chris Redford May 14 '14 at 22:22
@πάνταῥεῖ 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. – May 20 '14 at 13:23

Theolodis · Answer 2 · 2014-05-15T04:44:42.227

4

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

edited May 15 '14 at 04:44

answered May 14 '14 at 18:00

Theolodis

4,977
3
34
53

1

+1 Just mention a standard or custom auto locker mechanism, and your answer should be perfect, though of the low quality question! – πάντα ῥεῖ May 14 '14 at 18:42
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. – May 14 '14 at 19:08
@ebyrob I am talking about the `pop` method he implemented. – Theolodis May 15 '14 at 04:46
@Theolodis `T value;` Seriously? It seems like you copy-pasted my code. – May 19 '14 at 21:09
did you mean `std::lock_guard lock(this->mutex_);`? – Killzone Kid Dec 31 '17 at 18:17
@KillzoneKid depends on the mutex type you use. – Theolodis Dec 31 '17 at 19:38

Creating a Blocking Queue

2 Answers2

Linked