mardi 2 mars 2021

Why is mutex lock not working for thread-safe queue class implemented by linked list?

I implemented a queue with linked list, and I want multiple threads to push elements in the correct order. I used mutex to lock my member functions, but the numbers printed to terminal is still not in correct order, which should be 1,2,3,4,5,6. Insteads it prints a wrong order, such as 3,1,4,2,5,6. This means the mutex lock DIDNT work. Can someone please tell me why? And how to fix this?

// Implement a queue<int>,need functions: push_front, back, pop_back, and print
#include <iostream>
#include <thread>
#include <mutex>
using namespace std;

struct ListNode { 
    ListNode* next;
    int val;
    ListNode(int x) {
        val = x;
        this->next = nullptr;
    }
};

class Queue {
    
public:
    Queue() {
        head = new ListNode(0); // dummy head
        tail = head;
    }

    
    void push_front(int x) { // add node at then end of linked list
        lock_guard<mutex> lock(m);
        tail->next = new ListNode(x);
        tail = tail->next;
        
    }

    int pop_back() { // remove the first node of the linked list
        lock_guard<mutex> lock(m);
        ListNode* back = head->next;
        if (back == nullptr) {
            throw invalid_argument("empty queue");
        }
        head->next = back->next;
        back->next = nullptr;
        return back->val;
    }

    void print() {
        lock_guard<mutex> lock(m);
        ListNode* p = head->next;
        while (p != nullptr) {
            cout << p->val << endl;
            p = p->next;
        }
    }

private:
    mutable mutex m;
    // Implement with linked list
    ListNode* head;
    ListNode* tail;
};


int main() {
    Queue* queue = new Queue();

    // Multiple threads push at the same time --> order is wrong
    thread t1 = thread(&Queue::push_front, queue, 1);
    thread t2 = thread(&Queue::push_front, queue, 2);
    thread t3 = thread(&Queue::push_front, queue, 3);
    thread t4 = thread(&Queue::push_front, queue, 4);
    thread t5 = thread(&Queue::push_front, queue, 5);
    thread t6 = thread(&Queue::push_front, queue, 6);
    t1.join();
    t2.join();
    t3.join();
    t4.join();
    t5.join();
    t6.join();

    queue->print();
}

Aucun commentaire:

Enregistrer un commentaire