How to you solve the problem of implicit locking and parallel execution?

Question

Where the code is:

function A()
{
    lock()
    doSomething()
    unlock()
}

We can call A safely from multiple threads, but it never be executed in parallel . For parallel execution, we have to evade all of this code.

But the problem is we never know the A is getting lock or not. If we have source code (maybe lucky case), we have to decode all code to know locking is happening or not. This sucks. But even worse is we normally have no source code. And about the case of the lock is exist on base library?

It's obvious this kind of hidden locks will become bottleneck of parallel execution even all the other parts are designed for parallel.

And also, (1) With locks, execution cannot be parallel. (2) And I can't know whether the locks are used or not in any code. (3) Defensively saying, I can't make parallel anything!

This facts drives me crazy. How do you solve this problem?

Answer 1

First, A is not locked but rather threads become locked at the call of "lock()". There's no hidden locking mechanism here. A simple check is done which verifies that no other thread is currently holding the lock. If it is locked, it waits until it is unlocked, otherwise it continues executing the code.

You're right that generally speaking, locking code should be avoided unless absolutely necessary and when you do lock, it must hold a lock for as little time as possible to avoid potential bottlenecks. A good rule of thumb for knowing when code should be locked is to ask yourself the following questions:

• At any step in this process, would I care if it got interrupted? (imagine the power to the computer failing and not all your code gets executed.. would it be a problem?)
• If my program kept re-executing code due to some processor error, local variables aside, would there be some sort of risk of tampering with the end result in the previous execution?

If you answer yes to either, congratulations! You've found code you need to lock.

Typically there are two types of locks: read and write locks. If you just see "lock()" and "unlock()", what you're seeing is a write lock. A write lock is the most severe form of lock and it blocks threads regardless of what you're executing. Sometimes you may not even need to perform an operation, just simply check to see if you need to, yet you don't want to read data that may have since been modified by another thread, so you have to keep it in a lock. For this, you need a read lock. Read locks are always used in combination with a write lock. Typically you see a read lock immediately and some sort of check. If the check passes, you place a write lock to ensure that no thread can enter the read lock section until you're sure that it is in a consistent state.

If you write it correctly, you need not know whether or not a thread is locked just like you don't know when writing to a file will cause a program to block while it's being used by another program.

If that didn't answer your question, then perhaps I didn't quite follow what you were asking.

Answer 2

If you call A concurrently from multiple threads, one of three things will happen:

1) The threads will not actually block each other because they won't try to acquire the lock at the same time. In this case, they will still run concurrently and there will be no problem.

2) The threads will conflict on the lock and one of the threads will no longer be ready to run. In this case, the operating system will schedule some other thread that doesn't require that lock, in which case those threads will still run concurrently and there will be no problem.

3) Once all the threads that don't need the lock are scheduled, there are still idle cores. Only a thread that requires the lock can be scheduled on that core. But this only happens when everything you need to do required calling that function.

In other words, you only need to worry about this in the 5%-10% of your code that's performance critical. And you have to know that code inside out anyway, for obvious reasons.

Answer 3

It's obvious this kind of hidden locks will become bottleneck of parallel execution even all the other parts are designed for parallel.

False. All false.

(1) With locks, execution cannot be parallel.

In a one-core machine nothing is actually parallel, instruction streams from two or more threads are interleaved.

On a two-core machine, then you have exactly two parallel, interleaved instruction streams for all the running threads.

Cores are the only actual parallel execution. Threads are interleaved.

The threads appear to be executing in parallel.

(2) And I can't know whether the locks are used or not in any code.

What?

(3) Defensively, I can't make parallel anything!

False.