What prevents a race condition on a lock?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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 ).