分享
 
 
 

多线程WIN32程序如何检查死锁(三)-使用Petri网络来表示多线程应用程序

王朝system·作者佚名  2006-02-01
窄屏简体版  字體: |||超大  

根据1993版的《计算机百科全数》,Carl Adam Petri一个在德国波恩为Gesellschaft fuer Mathematik und Datenverarbeitung工作,我花了很长时间猜测为什么他的理论并没有引起当时学术和工商界的本来应得的注意。Petri网络早在19世纪70年代就已经深入的研究过,以我浅见,他们提供了一个分析和研究并发系统优秀的架构,对于Petri网络的最好的和更广泛的讨论在T.Murata的Petri Nets: Properties, Analysis and Applications论文中阐述,IEEE第77次(1989年4月)会议录的541-580。本节主要讲述Petri网络的最主要方面,在下一节我们可以看到怎么样在编写WIN32 API应用程序的时候使用他们。

Petri网络非常的通用,并不仅仅用来模拟多线程应用程序,例如:计算机硬件和工作过程也可以用Petri网络来描述。本文将限定Petri网络的讨论范围为多线程应用程序。

Petri网络是一个有向图,它的节点可以是位置,或转换,前者被画作一个圆,它粗略地描述一个线程的当前状态,后者被画作一个矩形,它粗略的描绘从一个状态到另一个状态变换的行为。边存在于位置和转换之间,也就是说两个状态或位置不能直接彼此互相连接,然而,两个到多个位置能够连接到同一个转换(对于模拟同步来说很重要),一个转换可以连接一到多个位置(模拟非确定的系统很重要)。

为了模拟一个应用程序的动态行为,个别的位置能够标住(在Petri网络中通常在圆圈中画一个黑点来表示)来表示线程当前执行代码处于对应的状态。有一个简单的激活原则:如果所有转换的导入位置(前驱或输入)被标记并且所有转换连接的位置(后继或输出)没有被标记,那么该转换被激活。如果一个转换能被激活,那么它可以删除所有前驱节点的位置标记并标记所有后继的位置。注意,通常架构的Petri网络具有相当的弹性:在自由的Petri网络中,每个位置都有描述一个位置同时至多可以描述多少个标记的能力,并且每个边都关联一个数字,该数字来表示当边被旋转的时候多少个标记被删除或插入到某个位置。本文我们仅仅讨论所谓的1-conservative 的Petri网络,这种Petri网络中每个位置的容量假定为1并且在边连接位置到转换的时候删除一个标记,连接转换到一个位置时增加一个标记。

在上面的优点枯燥的讨论之后,我们来看一个例子-怎么样将GOOFY转换成一个Petri网络。

图1,GOOFY的Petri的网络图

这个网络仅仅描述了两个线程都能访问的while循环部分。网络由10个位置组成,每个线程由四个位置组成,相应对应的有四个状态:

1. 等待两个关键段(p11或p21)

2. 都声明了各自的关键段,但正在等待另一个(p12,p22)

3. 都声明了两个关键段(p13,p23)

4. 释放了第二个声明的关键段,而不是第一个(p14,p24)

剩下的两个位置表示关键段1和关键段2。相对于线程状态的位置指示了线程执行的代码段,而关键段对应的位置标记暗示该关键段是自由的。

就像图2所示,当状态”es1”激活时,从p11到cs2的标记被删除同时一个标记被插入p12。

图2,一个转换被激活后的GOOFY网络图

----未完待续

----未完待续

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有