Parallelism and Synchronization

Question

Imagine you are utilizing Parallelism in a multi-core system.

Is it not completely possible that the same instructions may be executed simultaneously?

Take the following code:

int i = 0;

if( blockingCondition )
{
  lock( objLock )
  {
    i++;
  }
}

In my head, it seems that it is very possible on a system with multiple cores and parallelism that the blockingCondition could be checked at precisely the same moment, leading to the lock being attempted at the same moment, and so on...Is this true?

If so, how can you ensure synchronization across processors?

Also, does the .net TPL handle this type of synchronization? What about other languages?

EDIT Please note that this is not about threads, but Tasks and Parallel-Processisng.

EDIT 2 OK, thanks for the information everyone. So is it true that the OS will ensure that writing to memory is serialized, ensuring multi-core synchronization via volatile reads?

Answer 1

A lock like you have described here is a "Monitor" style lock on the objLock. As you've noted, it is entirely possible, under a multi-core system, for the two "lock" calls to begin simultaneously. However, any high level application environment which uses monitors will have translated the monitor into semaphore requests (or, depending on your OS and language particulars, mutex requests) in the compiled byte code.

Semaphores are implemented at the operating system and/or hardware level, and higher level languages bind to them. At the OS level, they are "guaranteed" to be atomic. That is, any program acquiring a semaphore is guaranteed to be the only one doing so at that point in time. If two programs, or two threads within a program attempt to acquire the lock at the same time, one will go first (and succeed), and the other will go second (and fail).

At this point, the "how do you ensure synchronisation" stops being a problem for the application programmer to worry about, and starts being a problem for the operating system designer and the hardware designer.

The upshot of it is, as an application coder, you can safely assume that "lock(objLock)" will be an atomic call no matter how many CPUs you plug into your system.

Answer 2

To understand why this works, bear in mind:

1. Locking a lock (i.e. incrementing a lock semaphore on the object) is an operation that blocks if the object is already locked.

2. The two steps of lock, a) checking the lock semaphore is free, b) and actually locking the object, are performed 'simultaneously' - i.e. they are a monolithic or atomic operation as far as relationship between CPU and memory is concerned.

Therefore, you can see that, if 2 threads enter your if-block, one of the two threads will acquire the lock, and the other will block until the first one has finished the if.

Answer 3

Your concern is precisely why we need a special mechanism like lock and cannot simply use a boolean flag.

The solution to your 'simultaneous' problem is in the algorithm that lock (which calls Monitor.Enter()) uses. It involves memory barriers and knowledge of the very lowlevel memory mechanics to ensure that no 2 threads can acquire the lock at the same time.

Note: I'm talking about .NET only, not Java.