6

This is an interview question . In general the deadlock between 2 threads is generated when thread1 locks mutex1,and a moment before it tries to lock mutex2 ,thread 2 locks mutex2.After that tread 2 wants to lock mutex1.So they wait for each other forever.

The question was "Can you gave a scenario of deadlock with one mutex and any number of threads?"

8 Answers 8

9

It depends on how you define "deadlock" I guess, but I could see one possibility:

  1. Thread A grabs the mutex
  2. Thread B waits for mutex
  3. Thread A dies without releasing mutex

Thread B never runs.

2
  • 1
    That's just a bad program. But it is a good interview answer! Commented Nov 18, 2013 at 21:51
  • 1
    Right, and Thread A may not even need to die to cause a deadlock: if the code between the mutex acquire and release were to throw an exception (in a language supporting exceptions), and the release were not in some sort of finally block, no thread would ever be able to acquire that lock again. This sounds like a perfectly valid possibility to me and, as James points out, a great interview question. Commented Nov 18, 2013 at 21:55
7

A deadlock requires 4 things:

Mutual Exclusion - refers to the idea of having a resource (a lock) that can be owned by a single thread.
No pre-emption - locks cannot be acquired forcefully
Circular Wait - refers to one thread waiting on another, that is waiting on itself (or a chain)
Hold and Wait - a thread is able to take one lock and wait for another

In an interview, it's usually more important to show them your thought processes and if you bring up these rules, they'll probably do more for you than trying to give a 'technically correct' trick answer.

You could do it this way, though:
Master thread locks a resource, then sends some tasks to the thread pool. These tasks wait for the resource. The master thread waits for the tasks.

1
  • 3
    "waits for the tasks", "wait for the resource". I think this better exposes a flaw in Yakov's understanding: it isn't locks that cause deadlocks, it is waiting for something (be it a lock or anything else). Commented Nov 18, 2013 at 22:33
3

Something like this? Get a deadlock with 1 mutex and 1 thread:

#define LOCK(std_mutex)    std::lock_guard<std::mutex> LOCK_GUARD(std_mutex)
std::mutex lock;

int main ()
{
    LOCK(lock);

    {
        LOCK(lock); //deadlock...
    }

    std::cout<<"end"; //never goes here

    return 0;
}
1

Yes, you lock the mutex or critical section but forget to unlock it (say in a certain exit code path). The next thread that tries to access this code is a deadlock. I just faced this scenario.

1
  • That's why it is better to use something like the C++ std::lock_guard() if the language allows it.
    – jav
    Commented Mar 14 at 10:33
0

When you think about deadlock (and most threading topics) you don't consider thread synchronization mechanisms but resource acquiring. You can do a deadlock without any mutex, event or semafor by just waiting for correct resource state in loop, if this situation happened for all thread that can modify your resource you have got a deadlock. In this light I think that correct answer should be that question is badly asked.

0

Suppose your program work with interrupt handler. The normal program lock a resource. And an interrupt happens before the lock is released. And the interrupt handler wants to lock that resource, too. This could cause the interrupt handler never returns and your program will not resume.

It's basically still 2 parties trying to use the same resource. But you cannot prevent an interrupt from happening even in a single-thread environment.

-1

I don't think you can have a deadlock with only one lock held. However, you can have a timeout if a lock is held longer than the timeout threshold of other processes/threads waiting for it.

1
  • Unfortunately have to give -1 for "I don't think you can have a deadlock with only one lock...". Believes should not be given as answers. We either know or we don't know.
    – jav
    Commented Mar 14 at 10:27
-1

If you have two processes, even without any lock you can have deadlock situations: https://stackoverflow.com/a/17320443/145757

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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