How to detect and find out that a program is at an impasse?

Question

This is an interview question.

How to detect and find out that a program is at a dead end?

Are there any tools that can be used for Linux / Unix?

My idea:

If the program does not perform any actions and its status is running, it is blocked.

But other causes can also cause this problem.

Open source tools - valgrind (halgrind) can do this.

right?

thanks

Answer 1

I would suggest you look at Helgrind: a stream error detector .

The simplest example of such a problem is as follows.

Imagine some common resource R, which for some reason is guarded by two locks L1 and L2, which must be preserved at access R.

Suppose a thread receives L1, then L2, and goes to access R. The implication of this is that all threads in the program must acquire two locks in the order of the first L1, and then L2. Not doing this risks a dead end.

A deadlock can occur if two threads — call them T1 and T2 — both want to access R. Suppose that T1 first receives L1 and T2 first receives L2. Then T1 tries to get L2, and T2 tries to get L1, but these locks are already saved. Thus, T1 and T2 are at an impasse. "

Answer 2

If you suspect a dead end, do ps aux | grep <exe name> ps aux | grep <exe name> , if the output of PROCESS STATE CODE is D (Uninterrupted sleep) means that it is a dead end. Because, as @daijo explained, let's say you have two streams T1 and T2 and two critical sections, each of which is protected by semaphores S1 & S2 , then if T1 gets S1 and T2 gets S2 , and after that they try to get another the lock, before abandoning what they have already completed, this will lead to a deadlock, and when ps aux | grep <exe name> ps aux | grep <exe name> PROCESS STATE CODE will be D (i.e. Uninterrupted sleep).

Instruments:

Valgrind, Lockdep (Linux kernel utility)

Check this link for deadlock types and how to avoid them: http://cmdlinelinux.blogspot.com/2014/01/linux-kernel-deadlocks-and-how-to-avoid.html