Multithreading in n-ary tree

Question

I have tried to use multithreading in n-ary tree in the lock_it() function. Saw all the tutorials present. But i am unable to come up the code. I only able to remove the deadlocks but i want to maximize the parallel running of lock_it() function.

Read at this link to know what lock_it() does. https://www.geeksforgeeks.org/locking-and-unlocking-of-resources-in-the-form-of-n-ary-tree/

How to improve it?

#include <bits/stdc++.h>
#include <thread>
#include <mutex>

using namespace std;
class Node {
public:
    char key;
    bool locked;
    int cnt_locked_desc;
    Node* parent;
    vector<Node*> child;
};
Node* root = NULL;
mutex mtx;

class LockUnlock {
public:
Node* newNode(char node_key, Node* prt) {
        Node* tmp = new Node;
        (*tmp).key = node_key;
        (*tmp).locked = (*tmp).cnt_locked_desc = 0;
        (*tmp).parent = prt;
        return tmp;
    }
    bool lock_it(Node* node) {  //O(h)
        if ((*node).cnt_locked_desc > 0 || node == NULL)
            return 0;
        for (Node* curr = node; curr != NULL; curr = (*curr).parent)
            if ((*curr).locked)
                return 0;
        mtx.lock();
        for (Node* curr = node; curr != NULL; curr = (*curr).parent) {
            (*curr).cnt_locked_desc++;
        }
        mtx.unlock();
        (*node).locked = 1;
        return 1;
    }
};

Save yourself some typing and instead of `(*t).` just do `t->`. — Fureeish, Sep 18 '20 at 21:34
Concurrency is a tough subject. If you're interested in learning more on it, I really enjoyed this book: https://www.manning.com/books/c-plus-plus-concurrency-in-action-second-edition — Homer6, Sep 18 '20 at 21:37
And this course: https://www.udemy.com/course/modern-cpp-concurrency-in-depth/ — Homer6, Sep 18 '20 at 21:39
It's unclear from the code what `mtx` is. Is that a per-tree mutex or a per-node mutex or a global mutex or what? — Jeremy Friesner, Sep 18 '20 at 21:41
Maybe describe what the lock_it function actually does so it's easier to reason about — Yamahari, Sep 18 '20 at 21:41
Why do you set `locked` *outside* of the mutex lock? That seems risky. You may want to look into [`std::atomic`](https://en.cppreference.com/w/cpp/atomic/atomic). — tadman, Sep 18 '20 at 21:42
Looks like you are traversing the tree bottom to top but top down seems to be way better as there is 0 shared data except the root if you split each child of the root into a seperate thread — Yamahari, Sep 18 '20 at 21:57
@Yamahari how to do that? Whenever i am at a node i have create a thread? — RUSS, Sep 18 '20 at 22:00
Please don't make more work for others by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under a [CC BY-SA license](//creativecommons.org/licenses/by-sa/4.0), for SE to distribute the content (i.e. regardless of your future choices). By SE policy, the non-vandalized version is distributed. Thus, any vandalism will be reverted. Please see: [How does deleting work? …](//meta.stackexchange.com/q/5221). If permitted to delete, there's a "delete" button below the post, on the left, but it's only in browsers, not the mobile app. — Makyen, Sep 18 '20 at 22:28

score 2 · Answer 1 · answered Sep 18 '20 at 21:43

2

Please consider using a scoped_lock index of directly using the mutex.

std::lock_guard or std::scoped_lock?

Concurrency is a tough subject. If you're interested in learning more on it, I really enjoyed this book: https://www.manning.com/books/c-plus-plus-concurrency-in-action-second-edition

And this course: https://www.udemy.com/course/modern-cpp-concurrency-in-depth/

I also highly recommend this course: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/

answered Sep 18 '20 at 21:43

Homer6

15,034
11
61
81

for now can you answer some approach to the question – RUSS Sep 18 '20 at 22:13
1

Unfortunately, my answer is that there's no short answer for concurrency. It takes a lot of study to undertand and use well. There are a lot places where you can hang yourself and, unfortunately, it requires serious study to get right. If you're interested in using concurrency in c++ effectively, I encourage you to invest the time in reading that book (and MIT course if you're open to going further). – Homer6 Sep 18 '20 at 22:16

Multithreading in n-ary tree

1 Answers1