• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 420
  • Last Modified:

Synchronizing threads

Hi!
I'm trying to synchronize between 2 threads.
I want them to run alternately. When thread A runs, thread B waits and vice versa.

In order to do so, I'm using mutexes like this:

Thread A               |     Thread B
=================================
Lock Mutex A1      |     Lock Mutex B1
                              |     Wait on A1
Do stuff                 |
Lock Mutex A2      |
Release A1            |
Wait on B1             |     Do Stuff
                              |     Lock Mutex B2
                              |     Release Mutex B1
Do stuff                 |     Wait on mutex A2
Lock Mutex A1      |
Release  A2          |
                              |     Do stuff
                              |     Lock Mutex B1
                              |     Release Mutex B2

and so on...

But I'm getting a deadlock.
Can anybody tell me why I'm getting it, how can I fix it, or if there's a known algorithm for this - attach a link?

thanks :)        
0
UltraDog
Asked:
UltraDog
  • 15
  • 9
  • 5
  • +4
3 Solutions
 
sarabandeCommented:
you should use only one mutex. both threads will try to get exclusive access locking the mutex. only one wins. the second will run when the first winner will release the mutex.

Sara
0
 
sarabandeCommented:
thread1:

- try to lock mutex
- get exclusive access
- run exclusively
- release lock
- lock mutex again
- wait for mutex cause locked by thread2

thread2:

- try to lock mutex
- wait for mutex cause locked by thread1
- get exclusive access after thread1 has released
- run exclusively
- ...

Sara


0
 
UltraDogAuthor Commented:
But:
I don't want the threads racing towards the mutex control.
I want to determine *excatly* when and where each thread is running.  
Using the algorithm you provided, I can't be sure that when I release a mutex in thread A, the other thread will take control of the critical section ( I can't know when a context switch happens) and the current  thread might regain control over the critical section
 
   
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
phoffricCommented:
From your pseudo-code, it is clear that you need more than one synchronization entity. You want to guarantee that Thread A does stuff Item A1 before Thread B does any stuff.

What isn't clear are the functions you are using for:
Lock Mutex - is it pthread_mutex_lock
Release A1             - ??
Wait on Thread A1 - ??
Release Mutex - is it pthread_mutex_unlock

You appear to be making a distinction between:
Release A1 and Release Mutex B1
or did you mean
Release A1 == Release Mutex A1 ?

Or, are you using a signalling system (e.g., a signal, a counting semaphore, a condition variable)?

I'll be back tonight. If you post code, I will check for deadlock condition. But, you have to let us know if this is for an academic assignment so that we can answer properly.
0
 
sarabandeCommented:
if you want to control execution it is much easier to have only one thread :)

you easily could enhance the above scenario so that you know absolutely which thread is running to a time.

main-thread:

- starts thread1
- waits for event1
- event1 was fired by thread1
- starts thread2

thread1:

- lock mutex
- get exclusive access
- run exclusively
- fire event1 for main thread
- release lock
- lock mutex again
- wait for mutex cause locked by thread2

thread2:

- try to lock mutex
- wait for mutex cause locked by thread1
- get exclusive access after thread1 has released
- run exclusively
- ...


Sara
0
 
UltraDogAuthor Commented:
phoffric:
It's not acedmic, just a little private project i'm working on :)
I extracted some thin light-weight sample code from my project that does the thing.

DuelSync.cpp
Mutex.cpp
Mutex.h
DuelSync.h
0
 
UltraDogAuthor Commented:
sarabande:
I wish I could use events, but I need this to run pretty fast and events can pop in intervals of a millisecond... :/
0
 
phoffricCommented:
Do you have the main function that drives this?
0
 
UltraDogAuthor Commented:
Yep. :)

#include ".\DuelSync.h"

int main()
{
	DuelSync d;
	d.Start();
	return 0;
}

Open in new window

0
 
JIEXACommented:
Mutex is not designed for making alternate runs; they're designed to stop running.

Deadlocks are broken by getting locks in a specific order, same for all threads. For example, if order is 1,2,3,4,5, then it's OK to lock 1,3,4, but not OK to lock 1,3,4,2.

I suppose you need 2 semaphores (or events in the case of Windows).
Thread #i:
  down-semaphore #(i)
  do some job
  up-semaphore #(1-i)
  down-semaphore #(i)
At the start the semaphore values are 1 (1st) and 0 (2nd).
0
 
HooKooDooKuCommented:
First of all, are the two threads running under different processes?  If not... if they are two threads running under the same process, you should use Critical Section instead of Mutex because Critical Sections are faster.

But whether you use Critical Section or Mutex, the 1st thing that comes to my mind that could be causing your deadlock is the initial condition.  Basically, how to you make sure Thread A gets a lock on A1 before Thread B gets a lock on B1 and attempts to lock A1.  And if you do get Thread A to get a lock on A1, how do you make sure Thread B gets a lock on B1 before Thread A can Lock A1, Lock A2, and then try to gain a lock on B1.  It's possible as your threads start that Thread A gets to the point that it has locked A1, A2, and B1 before Thread B can simply lock B1.

It would seem that at least for the starting condition, you have either a third thread (or the main thread that spawns A and B) to first get a lock on everything, then start Thread A and B.  This main thread could then release the lock on B1.  But you need some way of having Thread B signal back to this third (or main) thread that the lock has been established so that the locks on A1 and A2 can be released.  Then you need a way for Thread A to signal it has a lock on A1 before the lock on B2 is released.  Then you have to make sure Thread A has a lock that will block B before proceeding.
0
 
UltraDogAuthor Commented:
HooKooDooKu:
I also noticed it, but I temporarly solve it like so:
#include ".\DuelSync.h"

int main()
{
	DuelSync d;
       Sleep(1000);
	d.Start();
	return 0;
}

Open in new window


That's not what causes the deadlock...
0
 
UltraDogAuthor Commented:
JIEXA:
Isn't a semaphore just a mutex which allows more than one  thread into the critical section?
why is it more suitable here than using a mutex?


  down-semaphore #(i)
  do some job
  up-semaphore #(1-i)
  down-semaphore #(i)
down-semaphrore = release ?
up-semaphore = lock ?
and why do you "down" a semaphore twice?
0
 
JIEXACommented:
Semaphore can be seen like a counter-with-mutex. But the main difference is that raising semaphore signals threads that they may run. For mutex this does not happen: when the unlocked thread is scheduled to run, it -- surprisingly -- finds that mutex is not locked, locks it and runs. So, the delay after awaking thread via unlocking mutex might be huge.

Semaphore have a counter. On down, if it's 0, thread waits; otherwise it's decremented. On up, it's incremented and threads waiting on it are awaken. So, down is more like a lock, and up is like an unlock.
0
 
phoffricCommented:
In DuelSync::SecondaryThread, you have:
>>       sync->m_primary[sync->m_primaryWait].Lock();         //        Wait on A1
But, here you expect sync->m_primaryWait to be 0. However, sync->m_primaryWait is shared between the two threads since there is one instance of DuelSync.

The main thread does
>> Lock Mutex A1
>> Lock Mutex A2
In this last step, sync->m_primaryWait is 1; so the secondary thread could be waiting on A2 rather than A1 as designed.

Perhaps you use an indexes: A1=0, A2=1, B1=0, B2=1, and use these explicit names instead.
0
 
UltraDogAuthor Commented:
Yes, I've seen that just minutes ago,I lock a mutex but then its index is changed in the other thread and I try to release the wrong mutex.
I fix this by holding the "m_***wait" index in a local index so I don't care if it changes in between the lock and release.

It still goes into a deadlock but only after a few thousands loops.
I think I'll close this question now and I hope I won't bother you again with the new deadlock.
Thanks everbody :)
0
 
evilrixSenior Software Engineer (Avast)Commented:
Hmmm... one thing I don't really understand; if you never want thread A and B to run at the same time why bother with threads? Why not just do everything in one thread and save yourself all the grief? The whole point of using threads is for parallelisation. Making each thread mutually exclusive prevents this.
0
 
UltraDogAuthor Commented:
evilrix:
I'm trying to create extremely short periods of time in which my main thread sleeps :)

phoffric:
Eventually I did  use names for the mutex. It really helped :)
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> I'm trying to create extremely short periods of time in which my main thread sleeps :)
Ok, but the point is why can't you do all this in your main thread? I'm really not seeing the point of using threads if only one is active at any one time. It kinda defeats the purpose because each thread contends the other so you gain nothing other than extra complexity.

Maybe if you could explain what you are trying to do and why it might make more sense to me but it also might allow me to suggest a simpler way to do what you're doing.

It's up to you, just trying to be helpful :)
0
 
UltraDogAuthor Commented:
following my question here:
http://www.experts-exchange.com/Programming/Languages/C/Q_26987087.html

I was trying to avoid using a busy loop while sleeping for a few microsec by forcing the main thread to "sleep" by waiting for a mutex many times for short periods and meanwhile checking if we've slept enough.

but it didn't help, it is still using almost 100% of the cpu.
0
 
evilrixSenior Software Engineer (Avast)Commented:
Ok, but I'm still not sure I see why you need two threads. Since they don't run at the same time why can't you just do all the work in one thread either the main thread or, if you need to do something without blocking main, in another single thread? As long as there is no time-slice overlap with your two threads there is just no need to have two threads.
0
 
UltraDogAuthor Commented:
I need the 2 treads for the sole reason of producong "wait"s at the mutexes. :)
0
 
evilrixSenior Software Engineer (Avast)Commented:
And what are you specifically waiting on that requires two thread that couldn't be done it one? Looking at your original proposal the thread are just waiting on each other but one blocks whilst the other works and when the working thread finishes it blocks so the other can work. This could all be done in one thread. Even if thread A was waiting on something else giving thread B a time slice thread A would still be blocked until thread B releases so you still gain nothing.

Am I missing something?

The point of using threads is they can pre-empt. Either or both can run in parallel. If that can never happen there is little point in using threads - you are just making your design unnecessarily complex. Nothing you've said so far suggests to me that there is a need for this.
0
 
sarabandeCommented:
a mutex is not suitable to get a 'waits on mutex' message. you try to lock the mutex and if it was unlocked the lock was granted and if it already was locked you are waiting until it was released. no chance to output a message. if using pthread mutexes you could call the pthread_mutex_trylock but in my opinion such calls are making an easy thing unnecessarily complicated (and slow) and are little reliable cause after the call the lock immediately could have been released.

Sara
0
 
UltraDogAuthor Commented:
But when a thread is waiting on a mutex, it's going into a Wating-state, isn't it?
I thought it would be easier on the CPU...
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> But when a thread is waiting on a mutex, it's going into a Wating-state, isn't it?
But what is it waiting for? At some point something has to release the locked mutex... so this implies that there is always at least one active thread so what are you gaining?

Look at it like this...

thread A does work and waits for thread B, thread B does some work and waits for thread A, thread A does work and waits for thread B, thread B does some work and waits for thread A

How is this any different from

thread X does work and then more work, and then more work and then more work

?

At no time do thread A or B overlap, they are just always waiting for each other so what are you gaining?
0
 
UltraDogAuthor Commented:
It was supposed to replace a "busy loop".
It would do stuff AND sleep sometimes instead of just using the CPU.
0
 
evilrixSenior Software Engineer (Avast)Commented:
But when thread A is sleeping (and assuming you've release the mutex) thread B is then doing stuff, right? So, you still have at least one active thread. So, again, I ask what is it you are actually gaining other than extra complexity?

How about, instead of us going around in circles, you briefly explain what it is you are trying to achieve and maybe we can figure out a better way for you?
0
 
UltraDogAuthor Commented:
That is what I was trying to acheive :)
I was looking for a way to sleep for less than 1 millisecond without a busy loop.
0
 
evilrixSenior Software Engineer (Avast)Commented:
Ok, but how does using 2 thread allow you to achieve that?
0
 
UltraDogAuthor Commented:
I thought that threads going in and out waiting-mode will ease the work on the CPU (because they would sleep for a bit on one hand and do cpu unrelated(?) = thread-state-changing work on the other hand.
0
 
Infinity08Commented:
>> I was looking for a way to sleep for less than 1 millisecond without a busy loop.

What's so bad about a process using as much CPU as it can get ? If it's not I/O bound, it'll do that, and that's something you generally want, because the more CPU the process can use, the faster it'll finish whatever it's doing.

If you're worried about other pocesses, then don't : that's the OS's job. The scheduler ensures that all running processes get fair time slices (according to their needs and priority).

If you're worried about other threads in the same process, then the thread scheduler will again take care of that. You can facilitate it by adding regular explicit thread yields at strategic locations - but that's not necessary.
0
 
evilrixSenior Software Engineer (Avast)Commented:
Yup, completely agree.

Again, I can only say that unless I have misunderstood something you are trying to crack a walnut with a sledgehammer here. There is almost definitely a better way to do what you are trying to achieve (and even then, as Infinity08 has pointed out, it's unlikely you need to achieve anything here) but without having a better idea of what you are actually trying to do it's hard to say for sure.

Feel free to elaborate and we can try and guide you or, if you are happy with your currently solution, don't and we can leave it at that. Ultimately, I just want to ensure you actually have a good solution to your problem. I really don't think what you are proposing to do is but that, of course, is really your decision.
0
 
sarabandeCommented:
you should try a Sleep(0) if you are at windows. it would stop the thread from execution what makes that other threads could get scheduled, but does it for a minimum cycle.

Sara
0
 
UltraDogAuthor Commented:
I think I'll let it go for now.
Maybe i'll check out this Boost thingy :)
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> Maybe i'll check out this Boost thingy :)
We'll it's about the best collection of tools for C++; so good that some of it is mooted for the next C++ standard.
http://en.wikipedia.org/wiki/Boost_C%2B%2B_Libraries
http://en.wikipedia.org/wiki/C%2B%2B0x
0

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

  • 15
  • 9
  • 5
  • +4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now