Multithreading in multi cpu multithreading

Question

Suppose I have an undirected graph.

A small portion of the graph :

A -----\
        C
B -----/

Now the node A and B proceeds to modify parallely node C. // Node A and Node B process Node C in parallel thread.

I want the thread for Node B will wait for thread for Node A to complete processing. It has to be this way. No other way possible.

I also don't want other thread that are processing other Nodes to wait for the above condition, ie, I don't want to use mutex.

I have created a class member boolean flag and want to use that as a condition. // let that flag be d_flag

MT here uses multiple CPUs.

Solution that I think doesn't works :

CPU1 : Thread 1

while (d_flag) {
    // busy waiting
}
d_flag = true;

// Critical Section

d_flag = false;

CPU2 : Thread 1

while (d_flag) {
   // busy waiting
}

d_flag = true;

// Critical Section

d_flag = false;

My understanding is that if in multiple CPU, Node A thread is running on CPU1 and Node B thread on CPU 2, the spin lock is defeated.

There may be a condition where both the while loop evaluates to false as the test in the while loop is no longer atomic.

Is my understanding correct????? If yes, is there is a solution without using overall mutex.

You solution might work most of the time, but will sooner or later have deadlocks. If you don't want to use locks, then read about lock-free programming. — Some programmer dude
– Some programmer dude, Commented Jul 21, 2014 at 12:48
Read a good pthread tutorial. You need to use some exclusive locks (mutexes). — Basile Starynkevitch
– Basile Starynkevitch, Commented Jul 21, 2014 at 12:49
@Joachim Pileborg, yes that I understand. I want thread for node B to wait for thread for node A, but I don't want other threads for nodes that are not connected to node C to wait. — Soumya Palit
– Soumya Palit, Commented Jul 21, 2014 at 12:57
Are there other threads waiting for node A and B? If not then why not use a normal mutex and lock? The mutex and lock have to be only for node C and used by the threads for node A and B. No other thread have to use the mutex or lock. — Some programmer dude
– Some programmer dude, Commented Jul 21, 2014 at 13:08
Does thread A has to wait for thread B to complete? If yes, then a mutex works. Other threads (e.g Node D, E, ...) can simply ignore the mutex if you don't want to sync them with both thread A and B. — GuLearn
– GuLearn, Commented Jul 21, 2014 at 13:53

Brandon Kohn · Accepted Answer · 2014-07-21 13:25:46Z

1

I would suggest creating a conditional branch which executes only when the node being processed is C. In that branch you could setup a condition variable for the node B thread to wait until the node A thread has finished processing node C. Assuming you know the thread IDs associated to the nodes, I would imagine this to be fairly easy to implement (at least naively.) You would probably want to implement a conditional variable with a timeout if you aren't certain node A's thread would ever complete processing node C.

If I may make a suggestion, your use case having constraints on the ordering of operations on nodes for specific threads suggests you might want to consider a parallel programming paradigm which allows you to express these ideas at a higher level of abstraction. Perhaps using the actor pattern would help?

Here's an implementation which I think it pretty good for C++:

https://github.com/Neverlord/libcppa

http://libcppa.blogspot.com/

Using a pattern like that, you could have your actors (threads) communicate about which nodes they have processed and control their flow based on those communications. So for example, you could have the node A actor inform the node B actor when it has finished processing node C. This allows the node B actor to do other things while waiting for the message from A.

answered Jul 21, 2014 at 13:25

Brandon Kohn

1,6218 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

neverlord Over a year ago

libcppa has been revamped and is now named "CAF: C++ Actor Framework". The repository has been moved to github.com/actor-framework/actor-framework, but GitHub forwards you automatically to the repository when using the old URL. Just to avoid confusion. :)

Collectives™ on Stack Overflow

Multithreading in multi cpu multithreading

CPU1 : Thread 1

CPU2 : Thread 1

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

CPU1 : Thread 1

CPU2 : Thread 1

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related