Deadlock occuring after multiple iterations of queries in threads (multithreading)

Question

I encounter deadlocks while executing the code snippet below as a thread.

void thread_lifecycle(
Queue<std::tuple<int64_t, int64_t, uint8_t>, QUEUE_SIZE>& query, 
Queue<std::string, QUEUE_SIZE>& output_queue,
std::vector<Object>& pgs,
bool* pgs_executed, // Initialized to array false-values
std::mutex& pgs_executed_mutex,
std::atomic<uint32_t>& atomic_pgs_finished
){
    bool iter_bool = false;
    std::tuple<int64_t, int64_t, uint8_t> next_query;
    std::string output = "";
    int64_t lower, upper;

    while(true) {
        // Get next query
        next_query = query.pop_front();

        // Stop Condition reached terminate thread
        if (std::get<2>(next_query) == uint8_t(-1)) break;

        //Set query params
        lower = std::get<0>(next_query);
        upper = std::get<1>(next_query);


        // Scan bool array
        for (uint32_t i = 0; i < pgs.size(); i++){
            // first lock for reading
            pgs_executed_mutex.lock();
            if (pgs_executed[i] == iter_bool) {
                pgs_executed[i] = !pgs_executed[i];
                // Unlock and execute the query
                pgs_executed_mutex.unlock();
                output = pgs.at(i).get_result(lower,  upper);

                // If query yielded a result, then add it to the output
                if (output.length() != 0) {
                    output_queue.push_back(output);
                }

                // Inform main thread in case of last result
                if (++atomic_pgs_finished >= pgs.size()) {
                    output_queue.push_back("LAST_RESULT_IDENTIFIER");
                    atomic_pgs_finished.exchange(0);
                }
            } else {
                pgs_executed_mutex.unlock();
                continue;
            }
        }
        //finally flip for next query
        iter_bool = !iter_bool;
    }
}

Explained:

I have a vector of objects containing information which can be queried (similar to as a table in a database). Each thread can access the objects and all of them iterate the vector ONCE to query the objects which have not been queried and return results, if any.

In the next query it goes through the vector again, and so on... I use the bool* array to denote the entries which are currently queried, so that the processes can synchronize and determine which query should be executed next.

If all have been executed, the last thread having possibly the last results will also return an identifier for the main thread in order to inform that all objects have been queried.

My Question:

Regarding the bool* as well as atomic-pgs_finished, can there be a scenario, in-which a deadlock can occur. As far as i can think, i cannot see a deadlock in this snippet. However, executing this and running this for a while results into a deadlock.

I am seriously considering that a bit (byte?) has randomly flipped causing this deadlock (on ECC-RAM), so that 1 or more objects actually were not executed. Is this even possible?

Maybe another implementation could help?

---

Edit, Implementation of the Queue:

template<class T, size_t MaxQueueSize>
class Queue
{
    std::condition_variable consumer_, producer_;
    std::mutex mutex_;
    using unique_lock = std::unique_lock<std::mutex>;

    std::queue<T> queue_;

public:
    template<class U>
    void push_back(U&& item) {
        unique_lock lock(mutex_);
        while(MaxQueueSize == queue_.size())
            producer_.wait(lock);
        queue_.push(std::forward<U>(item));
        consumer_.notify_one();
    }

    T pop_front() {
        unique_lock lock(mutex_);
        while(queue_.empty())
            consumer_.wait(lock);
        auto full = MaxQueueSize == queue_.size();
        auto item = queue_.front();
        queue_.pop();
        if(full)
            producer_.notify_all();
        return item;
    }
};

Answer 1

Thanks to @Ulrich Eckhardt (, @PaulMcKenzie and all the other comments, thank you for the brainstorming!). I probably have found the cause of the deadlock. I tried to reduce this example even more and thought on removing atomic_pgs_finished, a variable indicating whether all pgs have been queried. Interestingly: ++atomic_pgs_finished >= pgs.size() returns not only once but multiple times true, so that multiple threads are in this specific if-clause.

I simply fixed it by using another mutex around this if-clause. Maybe someone can explain why ++atomic_pgs_finished >= pgs.size() is not atomic and causes true for multiple threads.

Below i have updated the code (mostly the same as in the question) with comments, so that it might be more understandable.

void thread_lifecycle(
Queue<std::tuple<int64_t, int64_t, uint8_t>, QUEUE_SIZE>& query, // The input queue containing queries, in my case triples
Queue<std::string, QUEUE_SIZE>& output_queue, // The Output Queue of results
std::vector<Object>& pgs, // Objects which should be queried
bool* pgs_executed, // Initialized to an array of false-values
std::mutex& pgs_executed_mutex, // a mutex, protecting pgs_executed
std::atomic<uint32_t>& atomic_pgs_finished // atomic counter to count how many have been executed (to send a end signal)
){
    // Initialize variables
    std::tuple<int64_t, int64_t, uint8_t> next_query;
    std::string output = "";
    int64_t lower, upper;

    // Set the first iteration to false for the very first query
    // This flips on the second iteration to reuse pgs_executed with true values and so on...
    bool iter_bool = false;

    // Execute as long as valid queries are received
    while(true) {
        // Get next query
        next_query = query.pop_front();

        // Stop Condition reached terminate thread
        if (std::get<2>(next_query) == uint8_t(-1)) break;

        // "Parse query" to query the objects in pgs
        lower = std::get<0>(next_query);
        upper = std::get<1>(next_query);


        // Now iterate through the pgs and pgs_executed (once)
        for (uint32_t i = 0; i < pgs.size(); i++){
            // Lock to read and write into pgs_executed
            pgs_executed_mutex.lock();
            if (pgs_executed[i] == iter_bool) {
                pgs_executed[i] = !pgs_executed[i];
                // Unlock since we now execute the query on the object (which was not queried before)
                pgs_executed_mutex.unlock();

                // Query Execution
                output = pgs.at(i).get_result(lower,  upper);

                // If the query yielded a result, then add it to the output for the main thread to read
                if (output.length() != 0) {
                    output_queue.push_back(output);
                }

                // HERE THE ROOT CAUSE OF THE DEADLOCK HAPPENS
                // Here i would like to inform the main thread that we exexuted the query on 
                // every object in pgs, so that it should no longer wait for other results
                if (++atomic_pgs_finished >= pgs.size()) {
                    // In this if-clause multiple threads are present at once!
                    // This is not intended and causes a deadlock,  push_back-ing
                    // multiple times "LAST_RESULT_IDENTIFIER" in-which the main-thread 
                    // assumed that a query has finished. The main thread then simply added the next query, while the 
                    // previous one was not finished causing threads to race each other on two queries simultaneously
                    // and not having the same iter_bool!
                    output_queue.push_back("LAST_RESULT_IDENTIFIER");
                    atomic_pgs_finished.exchange(0);
                }
                // END: HERE THE ROOT CAUSE OF THE DEADLOCK HAPPENS
            } else {
                // This case happens when the next element in the list was already executed (by another process), 
                // simply unlock pgs_executed and continue with the next element in pgs
                pgs_executed_mutex.unlock();
                continue; // This is uneccessary and could be removed
            }
        }
        //finally flip for the next query in order to reuse bool* (which now has trues if a second query is incoming)
        iter_bool = !iter_bool;
    }
}