【C】Deadlock detecting

usr

Although semaphore is a powerful tool to synchronize, using semaphore can cause problems such as deadlock.
Deadlock can be defined as a set of processes is deadlocked if each process in the set is waiting for an
event that only another process in the set can cause.
A simplest deadlock module can be process P1 is using resource R1 and acquiring R2, meanwhile process P2 is using R2 and requiring R1.
When we inquire deeper inside deadlock problem, we can find that deadlock can occur when there is a cycle in a wait for graph.
To detect deadlock needs us to determine whether there is a cycle in the graph.
Therefor the problem can be easy that we need some algorithms to find cycles.
Here is a simple way to do this.
First, we do a topological sorting on a graph.
The result of topological sorting is a sequence of vertices.
Then we compare the number of vertices after topological sorting to the number of vertices that has already in the graph.
If we cannot get an equal value of these two parameters, it is sure that the graph has a cycle.
Here is the code to detect deadlocks in C.
Caution that this following code needs StoneValley library.

1. 
   
2. #include <stdio.h>
   
3. #include "StoneValley/src/svgraph.h"
   
4. 
   
5. P_GRAPH_L pWaitingGrp = NULL;
   
6. 
   
7. /*    (B)
   
8. *    ^ \  
   
9. *   /   v
   
10. * (A)<-(C)
    
11. *       |
    
12. *       v
    
13. *      (D)
    
14. *
    
15. */
    
16. 
    
17. int main()
    
18. {
    
19.         pWaitingGrp = grpCreateL();
    
20.         if (NULL != pWaitingGrp)
    
21.         {
    
22.                 P_ARRAY_Z parr;
    
23.                 grpInsertVertexL(pWaitingGrp, 'A');
    
24.                 grpInsertVertexL(pWaitingGrp, 'B');
    
25.                 grpInsertVertexL(pWaitingGrp, 'C');
    
26.                 grpInsertVertexL(pWaitingGrp, 'D');
    
27. 
    
28.                 grpInsertEdgeL(pWaitingGrp, 'A', 'B', 0);
    
29.                 grpInsertEdgeL(pWaitingGrp, 'B', 'C', 0);
    
30.                 grpInsertEdgeL(pWaitingGrp, 'C', 'D', 0);
    
31.                 grpInsertEdgeL(pWaitingGrp, 'C', 'A', 0);
    
32. 
    
33.                 parr = grpTopologicalSortL(pWaitingGrp);
    
34.                 if (NULL != parr && grpVerticesCountL(pWaitingGrp) == parr->num)
    
35.                         printf("No deadlock.\n");
    
36.                 else
    
37.                         printf("deadlocked.\n");
    
38. 
    
39.                 if (parr)
    
40.                         strDeleteArrayZ(parr);
    
41.                 grpDeleteL(pWaitingGrp);
    
42.         }
    
43.         return 0;
    
44. }
    

复制代码

BIBLIOGRAPHY:
MODERN OPERATING SYSTEMS FOURTH EDITIO by ANDREW S. TANENBAUM HERBERT BOS
EMBEDDED AND REAL-TIME OPERATING SYSTEMS by K.C.WANG

Golden Blonde

话说如果WINDOWS上的线程死锁了，可以通过调用KeForceResumeThread来唤醒。。。
它的工作原理就是把线程的Semaphore设置为有信号。

1. ULONG KeForceResumeThread        (         IN PKTHREAD         Thread         )        
   
2. {
   
3. 
   
4.     ULONG OldCount;
   
5.     KIRQL OldIrql;
   
6. 
   
7.     ASSERT_THREAD(Thread);
   
8.     ASSERT(KeGetCurrentIrql() <= DISPATCH_LEVEL);
   
9. 
   
10.     //
    
11.     // Raise IRQL to dispatcher level and lock dispatcher database.
    
12.     //
    
13. 
    
14.     KiLockDispatcherDatabase(&OldIrql);
    
15. 
    
16.     //
    
17.     // Capture the current suspend count.
    
18.     //
    
19. 
    
20.     OldCount = Thread->SuspendCount + Thread->FreezeCount;
    
21. 
    
22.     //
    
23.     // If the thread is currently suspended, then force resumption of
    
24.     // thread execution.
    
25.     //
    
26. 
    
27.     if (OldCount != 0) {
    
28.         Thread->FreezeCount = 0;
    
29.         Thread->SuspendCount = 0;
    
30.         Thread->SuspendSemaphore.Header.SignalState += 1;
    
31.         KiWaitTest(&Thread->SuspendSemaphore, RESUME_INCREMENT);
    
32.     }
    
33. 
    
34.     //
    
35.     // Unlock dispatcher database and lower IRQL to its previous
    
36.     // value.
    
37.     //
    
38. 
    
39.     KiUnlockDispatcherDatabase(OldIrql);
    
40. 
    
41.     //
    
42.     // Return the previous suspend count.
    
43.     //
    
44. 
    
45.     return OldCount;
    
46. }

复制代码

usr

Golden Blonde 发表于 2022-11-23 11:33
话说如果WINDOWS上的线程死锁了，可以通过调用KeForceResumeThread来唤醒。。。
它的工作原理就是把线程的S ...

感谢科普。请问WINDOWS是怎样检测出有死锁的呢？