技术宅的结界

 找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 258|回复: 2
收起左侧

【C】Deadlock detecting

[复制链接]

13

主题

31

帖子

403

积分

用户组: 中·技术宅

UID
6266
精华
5
威望
37 点
宅币
243 个
贡献
30 次
宅之契约
0 份
在线时间
18 小时
注册时间
2020-9-26
发表于 2022-11-23 04:45:59 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

x
本帖最后由 usr 于 2022-11-23 04:50 编辑

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.
[C] 纯文本查看 复制代码
#include <stdio.h>
#include "StoneValley/src/svgraph.h"

P_GRAPH_L pWaitingGrp = NULL;

/*    (B)
 *    ^ \  
 *   /   v
 * (A)<-(C)
 *       |
 *       v
 *      (D)
 *
 */

int main()
{
	pWaitingGrp = grpCreateL();
	if (NULL != pWaitingGrp)
	{
		P_ARRAY_Z parr;
		grpInsertVertexL(pWaitingGrp, 'A');
		grpInsertVertexL(pWaitingGrp, 'B');
		grpInsertVertexL(pWaitingGrp, 'C');
		grpInsertVertexL(pWaitingGrp, 'D');

		grpInsertEdgeL(pWaitingGrp, 'A', 'B', 0);
		grpInsertEdgeL(pWaitingGrp, 'B', 'C', 0);
		grpInsertEdgeL(pWaitingGrp, 'C', 'D', 0);
		grpInsertEdgeL(pWaitingGrp, 'C', 'A', 0);

		parr = grpTopologicalSortL(pWaitingGrp);
		if (NULL != parr && grpVerticesCountL(pWaitingGrp) == parr->num)
			printf("No deadlock.\n");
		else
			printf("deadlocked.\n");

		if (parr)
			strDeleteArrayZ(parr);
		grpDeleteL(pWaitingGrp);
	}
	return 0;
}

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

使用道具 举报

52

主题

278

帖子

8938

积分

用户组: 管理员

UID
77
精华
16
威望
237 点
宅币
7860 个
贡献
246 次
宅之契约
0 份
在线时间
226 小时
注册时间
2014-2-22
发表于 2022-11-23 11:33:11 | 显示全部楼层
话说如果WINDOWS上的线程死锁了,可以通过调用KeForceResumeThread来唤醒。。。
它的工作原理就是把线程的Semaphore设置为有信号。
  1. ULONG KeForceResumeThread        (         IN PKTHREAD         Thread         )        
  2. {

  3.     ULONG OldCount;
  4.     KIRQL OldIrql;

  5.     ASSERT_THREAD(Thread);
  6.     ASSERT(KeGetCurrentIrql() <= DISPATCH_LEVEL);

  7.     //
  8.     // Raise IRQL to dispatcher level and lock dispatcher database.
  9.     //

  10.     KiLockDispatcherDatabase(&OldIrql);

  11.     //
  12.     // Capture the current suspend count.
  13.     //

  14.     OldCount = Thread->SuspendCount + Thread->FreezeCount;

  15.     //
  16.     // If the thread is currently suspended, then force resumption of
  17.     // thread execution.
  18.     //

  19.     if (OldCount != 0) {
  20.         Thread->FreezeCount = 0;
  21.         Thread->SuspendCount = 0;
  22.         Thread->SuspendSemaphore.Header.SignalState += 1;
  23.         KiWaitTest(&Thread->SuspendSemaphore, RESUME_INCREMENT);
  24.     }

  25.     //
  26.     // Unlock dispatcher database and lower IRQL to its previous
  27.     // value.
  28.     //

  29.     KiUnlockDispatcherDatabase(OldIrql);

  30.     //
  31.     // Return the previous suspend count.
  32.     //

  33.     return OldCount;
  34. }
复制代码

13

主题

31

帖子

403

积分

用户组: 中·技术宅

UID
6266
精华
5
威望
37 点
宅币
243 个
贡献
30 次
宅之契约
0 份
在线时间
18 小时
注册时间
2020-9-26
 楼主| 发表于 2022-11-23 23:24:59 | 显示全部楼层
Golden Blonde 发表于 2022-11-23 11:33
话说如果WINDOWS上的线程死锁了,可以通过调用KeForceResumeThread来唤醒。。。
它的工作原理就是把线程的S ...

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

本版积分规则

QQ|申请友链||Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2022-12-9 04:28 , Processed in 0.030474 second(s), 29 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表