Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I understand the basics of what data races are, and how locks/mutexes/semaphores help prevent them. But what happens if you have a "race condition" on the lock itself? For example, two different threads, perhaps in the same application, but running on different processors, try to acquire a lock at the exact same time.

What happens then? What is done to prevent that? Is it impossible, or just plain unlikely? Or is it a real race condition waiting to happen?

share|improve this question
    
This question was asked before on SO: stackoverflow.com/questions/980521/… –  Doc Brown Jun 17 at 6:11
    
and a related question here on P.SE: programmers.stackexchange.com/questions/228827/… –  ratchet freak Jun 17 at 10:13
    
You acquire a lock to acquire the lock ;) (in other words, if your lock has a race condition, it isn't implemented correctly - a lock is pretty much defined to be a construct that implements mutual exclusion) –  Tangrs Jun 17 at 11:40
    
You missed an important point in how locks work. They are constructed such that it is not possible to have a race on a lock, otherwise they are completely useless. –  Zane Jun 17 at 13:46

4 Answers 4

up vote 32 down vote accepted

Is it impossible, or just plain unlikely?

Impossible. It can be implemented in different ways, e.g., via the Compare-and-swap where the hardware guarantees sequential execution. It can get a bit complicated in presence of multiple cores or even multiple sockets and needs a complicated protocol between the cores, but this is all taken care of.

share|improve this answer
2  
Thank... God... it's handled in hardware... (or at least a level lower than we touch.) –  corsiKa Jun 17 at 14:38
    
Accepted as the answer because of your links. –  gdhoward Jun 17 at 19:36
2  
@gdhoward I can't believe it... this answer took me less than 5 minutes and it's the third highest voted out of my four hundreds answers (mainly SO). And also probably the shortest one. –  maaartinus Jun 17 at 19:59
    
@maaartinus - Short and sweet sometimes does it. –  Bobson Jun 17 at 20:06

Study the concept of atomic "Test and Set" operations.

Essentially the operation cannot be divided - it is not possible for two things to do it at exactly the same time. It will check a value, set it if it is clear, and return the value as it was when test. In a lock operation, the result will always be "lock == TRUE" after a test-and-set, the only difference is was it set or not at the start.

At the micro code level in a single core processor, this is one indivisible instruction, and is easy to implement. With multiple and multicore processors, it becomes harder, but as programmers we have no need to worry about it, as it is designed to work by the really smart guys who do the silicon. Essentially they do the same thing - make an atomic instruction that a fancy version of test-and-set

share|improve this answer
2  
Basically, if the hardware isn't intrinsically sequential at some level, it will have a mechanism that allows it to break ties that might otherwise occur. –  Bill Michell Jun 17 at 8:31
    
@BillMichell, I should have thought of that. Actually, I did; I just didn't know if my assumption was correct. –  gdhoward Jun 17 at 19:37

Simply put the code to get into the critical section is specially designed so a race condition won't violate the mutual exclusion.

Most of the time atomic compare and set loops are used that execute at the hardware level

while(!CompareAndSet(&lock, false, true));//busy loop won't continue until THIS thread has set the lock to true
//critical section
CompareAndSet(&lock, true, false);

In absence of that there are well studied software solutions to enable mutual exclusion.

share|improve this answer

It is not possible that two (or more) threads acquire lock on the same time. There are few types of synchronization methods for instance:

Active waiting - spin lock

Pseudocode:

1. while ( xchg(lock, 1) == 1); - entry protocole

XCHG is an example of atomic operation (exists on x86 architecture) which first sets new value for a "lock" variable and then returns old value. Atomic means that it can't be interrupt - in above example between setting new value and returning old. Atomic - deterministic result no matter what.

2. Your code
3. lock = 0; - exit protocol

When lock is equal to 0 another thread can enter to critical section - while loop ends.

Thread suspending - for example counting semaphore

There exists two atomic operation .Wait() and .Signal() and we have integer variable lets call it int currentValue.

Wait():
if (currentValue > 0) currentValue -= 1;
else suspend current thread;

Signal():
If there exists thread suspended by semaphore wake up one of them
Else currentValue += 1;

Now solving critical section problem is really easy:

Pseudocode:

mySemaphore.Wait();
do some operations - critical section
mySemaphore.Signal();

Usually your programming thread API should give you ability to specify maximal concurrent threads in semaphore critical section. Obviously there are more types of synchronization in multithreaded systems (mutex, monitors, binary semaphore etc.) but they base on above ideas. One could argue that methods which use thread suspending should be preferred to active waiting (so cpu is not wasted) - it's not always the truth. When thread is being suspended - expensive operation called context switch takes it place. However it's reasonable when waiting time is short ( number of threads ~ number of cores ).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.