Alex Rivera | Logout

What happens if two process in different processors try to acquire the lock at EXACTLY same time

Asked 2011-10-23T00:54:55.577
18

Ok, so I am reading about synchronization, and I read through various algorithms such as spinlocks, semaphores, and mutex to avoid race condition.

However, these algorithms can't prevent race condition in SMP when multiple proceses access the data exactly at the same time.

For example, suppose thread 1 in processor A runs lock(mutex1); withdraw(1000); unlock(mutex1);

and thread 2 in processor B runs lock(mutex1); deposit(1000); deposit(1000); unlock(mutex1);

When both threads run EXACTLY AT THE SAME TIME, both threads will be in critical section simultaneously.

The only solution (should be in hardware level) would be making each processors run slightly off to each other, but it defeats the purpose of parallelism.

Is there any hardware level support to avoid these situation where multiple processors try to acquire the lock at the exactly same time?

(this is not a problem of atomicity, but rather problem of exact parallelism, and I wonder how SMP deals with it).

synchronization locking smp multiprocessor
Edit
Report

1 Answer

3

You might want to look into memory barriers.

http://en.wikipedia.org/wiki/Memory_barrier

In this case the locks would use memory barriers so that the internal value used in the lock cannot be accessed by multiple processors at once.

Some architectures also allow locking of all cores except 1 to allow for this. For example x86 sports a LOCK prefix that when added to instructions will lock access to memory during that instruction. (e.g: LOCK ADD EAX, 1 for an atomic increment to a register)

Architectures that don't support LOCK or atomic instructions use compare and exchange or test and set/swap. Usually it involves a small instruction loop that in high level may look like 

while (target != value) target = value;

This may not look like it will execute more than once but it ensures that in between the instructions the value is not change from underneath it. The downside to this approach is if there is high contention on target then it may eat up more clock cycles than you would like but it tends to happen fast enough so it's never really noticeable.

answered 2011-10-23T00:58:07.433

Your Answer