CODEWITHSUNDEEP
c++cwindowsmultithreading
loopuntil
loopuntil

Reputation: 11

Is atomicity really needed when implementing a thread lock?

Suppose I have a piece of code that must not be executed concurrently. My (presumed naive) approach at attempting a thread lock would look something like this:

int lock = 0;

DWORD WINAPI ThreadProc(LPVOID lpParam)
{
    if (lock)
        return 1;

    lock = 1;

    /* code goes here */

    lock = 0;

    return 0;
}

When testing with the following:

for (i = 0; i < 2; i++)
    thandle[i] = CreateThread(NULL, 0, ThreadProc, NULL, 0, &tid[i]);

WaitForMultipleObjects(2, thandle, TRUE, INFINITE);

I always get the desired effect that only the first thread to be created actually gets to the code and returns 0. However, I keep coming across the suggestion that this method may fail because the lock is not implemented using atomic operations.

I cannot see a way of creating the threads simultaneously, so, in practical terms, is atomicity really needed here? Can someone provide an example that would cause the above to fail?

Upvotes: 0

Views: 105

Answers (5)

rcgldr
rcgldr

Reputation: 28951

Since the code is using Windows functions like CreateThread() , WaitForMultipleObjects(), might as well use Windows mutex or semaphore and use WaitForSingleObject() in the threads, assuming you want the threads to wait instead of aborting.

Upvotes: 0

illeyezur
illeyezur

Reputation: 451

You need to be able to atomically check the lock and acquire the lock at the same time.

The following situation can occur:

  1. Thread 1 checks the lock:

    if (lock) // lock = 0 so skips the body of the if statement

  2. Thread 2 checks the lock at the same time:

    if (lock) // lock = 0 so skips the body of the if statement

  3. Thread 1 assigns the lock:

    lock = 1

  4. Thread 2 assigns the lock:

    lock = 1

  5. Thread 1 runs its code:

    /* code goes here */ // Thread 1 starts running the critical section code

  6. Thread 2 runs its code at the same time:

    /* code goes here */ // Thread 2 starts running the critical section code

As there is no atomic "test and acquire lock" being used, between the time where Thread 1 checks the lock and sets the lock, Thread 2 is able to check the lock, and hence both threads can be in the critical section at the same time.

On a single-core system, this can happen if a task-switch to Thread 2 occurs between the time that Thread 1 checks the lock and the time it sets the lock.

On a multi-core system, this can happen if both threads are on the same core and a task-switch to Thread 2 occurs, and it can happen if the threads are running on different cores.

Upvotes: 4

Tony Delroy
Tony Delroy

Reputation: 106254

Your code's riddled with problems:

  • lock is not volatile, so the compiler's free to read it into a register and keep using/updating it in the register without writing the change back towards memory (where there's at least the chance of other thread's noticing, though on many CPUs an explicit memory barrier (synchronisation opcode) is needed to guarantee other-thread visibility)

    • note that when you use proper synchronisation mechanisms - a mutex or atomic op - there's no need to use volatile as well.

  • the instructions may be reordered, such that some of the /* code [that] goes here */ is executed before you attempt to lock or after you attempt to unlock

  • there's still a race condition between the if (lock) test and the lock = 1; code... even if threads were writing to an atomic variable, you'd need a Compare-and-Swap / Compare-and-Exchange style operation to guarantee safety for this, and if that failed you'd need to spin waiting - burning CPU - or yield after a number of tries and retry later (guess what - by then you've reimplemented mutex instead of using the system's one)

Upvotes: 1

Didier Poulain
Didier Poulain

Reputation: 41

Most of the time, your code will be OK, but in some case, it will fail and two or more threads may execute at the same time the code protected by your lock.

Image that two threads starts executing your function at quite the same time. They will both execute

if (lock)
    return 1;

before reaching

lock = 1;

and thus both enter the protected code. This why lock must be atomic.

The solution is very easy, just create a critical section with the Win32 function InitializeCriticalSection, and use it with EnterCriticalSection and LeaveCriticalSection.

Upvotes: 3

Jerry Coffin
Jerry Coffin

Reputation: 490808

Yes, I can see how this could fail.

If you're running it on a single-core/single-processor machine, you can probably run it forever, and never see a failure.

On a machine with multiple cores, seeing a failure could be fairly routine.

The obvious way it would fail would be if all the cores on the machine were busy. The one thread creating your new threads would create a number of threads, none of which started running immediately, because the cores were all busy.

Then a number of other threads finish processing simultaneously, and a number of your threads all start simultaneously. All of them are now executing in lock-step, so they all read the same value, all attempt to write the same value (producing undefined behavior), all execute the code simultaneously, all set the lock to 0, and all return 0.

The chances of this happening on a given run are probably fairly low unless you have a lot of threads and cores. There's virtually on question that it can and will happen eventually--and the more threads and cores involved, the sooner and more often it'll happen.

Upvotes: 3

Related Questions