Serving the Quantitative Finance Community

 
User avatar
JackBryan
Topic Author
Posts: 1
Joined: August 15th, 2010, 6:15 pm

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

May 26th, 2012, 9:05 pm

This is an interview question, the interview has been done. How to make thread synchronization without using mutex, semorphore, spinLock and futex ?Given 5 threads, how to make 4 of them wait for a signal from the left thread at the same point ? it means that when all threads (1,2,3,4) execute at a point in their thread function, they stop and wait for signal from thread 5 send a signal otherwise they will not proceed. My idea:Use global bool variable as a flag, if thread 5 does not set it true, all other threads wait at one point and also set theirflag variable true. After the thread 5 find all threads' flag variables are true, it will set it flag var true. It is a busy-wait. Any better ideas ? Thanks
 
User avatar
lexington
Posts: 0
Joined: November 16th, 2008, 5:04 am

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

May 27th, 2012, 6:43 am

lock free programming
 
User avatar
CluelessCpp
Posts: 0
Joined: April 7th, 2012, 11:45 am

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

May 27th, 2012, 7:35 am

But wouldn't the "busy-wait" or "lock-free programming" be essentially a spin-lock in this case?
 
User avatar
lexington
Posts: 0
Joined: November 16th, 2008, 5:04 am

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

May 27th, 2012, 7:56 am

QuoteOriginally posted by: CluelessCppBut wouldn't the "busy-wait" or "lock-free programming" be essentially a spin-lock in this case?i don't have experience in this, but i think are based on compare-and-swap(CAS) instruction
 
User avatar
CluelessCpp
Posts: 0
Joined: April 7th, 2012, 11:45 am

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

May 27th, 2012, 9:13 am

QuoteOriginally posted by: lexingtoni don't have experience in this, but i think are based on compare-and-swap(CAS) instructionYes, you usually have CAS inside a loop. But in the context of waiting for another thread you would end up using the CAS inside the loop as a spin-lock.
 
User avatar
CluelessCpp
Posts: 0
Joined: April 7th, 2012, 11:45 am

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

May 27th, 2012, 9:29 am

I think the main question is what are we allowed to use. Is "signal" used as an abstract concept or does it specifically refer to the signal set of functions? In the latter case it should be quite easy to just use it in combination with atomic counters and sigwait to implement the synchronisation.
 
User avatar
JackBryan
Topic Author
Posts: 1
Joined: August 15th, 2010, 6:15 pm

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

May 27th, 2012, 1:45 pm

QuoteOriginally posted by: CluelessCppI think the main question is what are we allowed to use. Is "signal" used as an abstract concept or does it specifically refer to the signal set of functions? In the latter case it should be quite easy to just use it in combination with atomic counters and sigwait to implement the synchronisation.Here, the signal can be any kinds of user-defined events or UNIX signal as long as the performance overhead is minimized. Any commnets are wlecome. thanks !
 
User avatar
CluelessCpp
Posts: 0
Joined: April 7th, 2012, 11:45 am

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

May 28th, 2012, 11:49 am

Here is a signal-based approach:
 
User avatar
JackBryan
Topic Author
Posts: 1
Joined: August 15th, 2010, 6:15 pm

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

May 28th, 2012, 4:25 pm

QuoteOriginally posted by: CluelessCppHere is a signal-based approach:Thanks for your code, it works well. This signal synchronization is faster than mutex/semaphore/futex ? signal synchronization also need to make system calls ? Any comments are appreciated !thanks
 
User avatar
CluelessCpp
Posts: 0
Joined: April 7th, 2012, 11:45 am

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

May 28th, 2012, 5:18 pm

QuoteOriginally posted by: JackBryanThanks for your code, it works well. This signal synchronization is faster than mutex/semaphore/futex ? signal synchronization also need to make system calls ? It's unlikely to be faster than mutex/semaphore/futex - as these are likely highly optimised (but it's probably quite similar to how mutexes were implemented in LinuxThreads). And it does use system calls - but you have to use system calls to wait for something (unless you do a busy-wait).
 
User avatar
yuryr
Posts: 0
Joined: November 5th, 2007, 12:47 pm

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

June 8th, 2012, 9:03 am

What you describe is called "barier synchronization". Your 5 threads are waiting for a barier to open. It is usually additionally specified how you want the barier to open - all at once or one-by-one after a short time-slice. This distinction might/might not be important for the choice of syncronization method.Now, spinlock is always faster that unix signals/mutexes/semaphores! It is just what we mean by "faster". Lower latency vs throughput. Spinlock will occupy CPU time because of constant polling, but will react faster in general. However, when you have too many threads spinlocking and polling then thread contention will increase the latency and decrease throughput. There is also memory bus contention consideration. So, in practice, high-performant multithreading is non-trivial. You may want to invent more complex synchronization tailored to your needs.For example, you might want to use thread pools. You split the code for all your 5 execution paths into 2 partsne is for pre-suspended state (you suspend them by serializing their states somewhere then exiting completely), 5 threads are then free to do other less important jobs that periodically check for some condition (like global volatile integer variable as in spinlock), then 2nd part (post-barier) execution is started. This scenario leads to larger latency but higher throughput. And no synchronization needed!
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

June 9th, 2012, 12:15 pm

QuoteHow to make thread synchronization without using mutex, semorphore, spinLock and futex ?Once way is to design your application to be embarassingly parallel i.e. no shared data. You can use domain decomposition, replication, pipes/filters etc. If it is possible; if not, you can't. Then you need shared data patterns, e.g. reader/writer locks or even upgradeable locks.QuoteUse global bool variable as a flag, if thread 5 does not set it true, all other threads wait at one point and also set theirflag variable true. After the thread 5 find all threads' flag variables are true, it will set it flag var true. Very bad idea. beware compiler optimisations, non-atomic operations and cache misses.
Last edited by Cuchulainn on June 8th, 2012, 10:00 pm, edited 1 time in total.