基于petri网的计算机软件系统建模

来源 :电脑知识与技术 | 被引量 : 0次 | 上传用户:hua50776007
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘要: 现实中的许多系统,尤其是计算机软件系统可以使用Petri网来为它们建立模型。在该文中对计算机软件系统中几个典型问题:生产者—消费者问题、哲学家进餐问题、读者—写者问题、PV 操作等的petri网建模进行了分析。
  关键词:petri网;建模;计算机软件系统
  中图分类号:TP302 文献标识码:A 文章编号:1009-3044(2017)31-0222-02
  1 概述
  Petri网作为一个新型的建模工具,已在计算机科学的各个领域得到了应用。除了计算机硬件之外,计算机软件也可以由petri网来建模。这可能是petri网最普遍的用处, 并且有巨大的潜力,产生有用的结果。对于计算机硬件的描述和建,许多系统已经开发了数年,但是应用petri网对计算机软件建模研究的较晚。 本文主要对生产者—消费者问题、哲学家进餐问题、读者—写者问题、PV 操作等操作系统中的著名问题的petri网建模进行分析。
  2 生产者—消费者问题
  2.1 基本的生产者—消费者问题
  生产—消费问题中包括共享数据对象,但这个例子中共享对象是一个缓冲区。生产者进程(producer process)生产一个对象,将它放入缓冲区中;消费者进程(consumer process)等待生产者将这个对象放入缓冲区之后,将它取走并消费、生产者—消费者问题可以用图1所示建模。位置B表示缓冲区,每个token表示一个已经产生但没有被消费的项(item)。
  2.2 多生产者—多消费者问题
  基本的生产者—消费者问题的一种变化形式是多生产者—多消费者问题。在这种变化形式中,多个生产者生产多个项,这些项放入公共缓冲区中,以便多个消费者消费在图2中用Petri网描述这个问题。与图2不同的是描述了s个生产者,t个消费者。系统起始于从有s个token的生产者进程的初始位置和有t个token的消费者进程的初始位置。这表示有s个生产者和t个消费者执行可重入程序,共享代码。有一种可能的方法是为生产者和消费者进程复制代码,但这会导致具有相同行为的比较大的Petri网的产生。
  2.3 采用约速性缓冲区的生产者—消费者问题
  生产者—消费者问题的另一种变化形式是采用约束缓冲区(bounded buffer)的生产者—消费者问题。这种形式中,认为生产者与消费者之间的缓冲区有限制,也就是说,仅有n个格来放置项。这样生产者不能一直以期望的速度生产,它需要在消费者消费慢且缓冲区满的时候等待。图3是这个问题的Petri网模型,受约束的缓冲区用两个位置来表示:B表示已被生产但未被消费的项的数目(既满格的数目),B’表示缓冲区中空格的数目。初始时B’有n个token,B为空。如果缓冲区满了, B’为空,B有n个token.这时,生产者如果试图将另外一个项放入缓冲区,这个操作将会被中止,因为B’中没有token可让变迁点火。
  3 哲学家进餐问题
  哲学家进餐问题是Dijkstra在1968年提出的。问题中描述了五位哲学家,他们或者思考或者进餐,坐在一个摆满中餐的圆桌前。每两个哲学家之间放着一只筷子。然而,一个人必须有两只筷子才能吃中餐;因此每个哲学家必须同时拿起他左右侧的两只筷子,才能进餐。这里存在一个问题就是如果所有哲学家都拿起左边的筷子,等待右边的筷子,那么将陷入无限等待状态,既死锁状态。
  图4是这个问题的Petri网模型。位置C1、C2、C3、C4、C5表示筷子,因为最初每只筷子都空闲,所以每个位置有一个token.对于每个哲学家用两个位置Mi和Ei代表其思考和进餐状态。对每个哲学家来说,当从思考状态转变到进餐状态时,他两边的筷子,只能由他一个人使用,别人就不能再用了。这个问题很容易用Petri网来描述。
  4 读者—写者问题
  读者—写者问题有几种变化形式,但基本结构相同。有两种进程:读者进程和写者进程。所有进程共享一个公共文件、变量或数据对象。读者进程不能修改共享对象,而写者进程可以进行修改。所以写进程对所有其他读进程和写进程互斥,但多个读进程能够同时访问共享数据。在这个问题的关键在于定义一个控制结构,使得不产生死锁或者说不违背互斥原则。图4描述了当读者进程的数目限定为n的Petri网模型。
  5 P V 操作
  多数同步问题不能直接用Petri网解决,而更适合用已有的同步机制来解决。基于信号量的P、V操作是一种典型的同步机制,由Dijkstra提出。信号量是一个取非负整数的数据项。V操作对信号量加1,P操作对信号量减1,P操作只能在信号量非负的时候进行;如果信号量为零,不能进行P操作,只有等其他进程执行V操作后,才能进行P操作。P、V操作用原语实现;没有其他的操作能够同时修改信号量的值。
  这些操作很容易用来模型化,图6是PV操作的Petri网模型。每个信号量用一個位置表示,位置中Token的个数表示信号量的值。一个P操作将信号量位置作为输入;一个V操作将信号量位置作为输出。这种能够对PV操作模型化的能力优势使得很多系统用PV操作来实现或设计。例如,Venus操作系统将PV操作作为基本的内部进程通讯机制。这些系统可以用Petri网来建模。
  6 结论
  Petri网作为一种建模工具,已在计算机科学的各个领域得到了应用。操作系统是计算机系统中最重要的系统软件,而操作系统又是最复杂的大型系统软件,如何解决操作系统中的经典问题,减小操作系统的规模,对于开放操作系统乃至大型软件系统十分必要。本文中对计算机软件系统中几个典型问题的petri网建模进行了分析。通过使用petri网建模,可以对操作系统中资源共享及引起的竞争、可能产生的死锁一目了然,为描述其他类似的问题开辟了一条新路。
  参考文献:
  [1] 舒远仲,刘炎培,彭晓红,等.面向对象Petri网建模技术综述[J].计算机工程与设计,2010(15).
  [2] 汤小丹.计算机操作系统[M].4版.西安:西安电子科技大学出版社,2014.
  [3] 秦江涛. 基于Petri网的生产系统建模与分析研究[J].上海理工大学学报,2017(4).
其他文献
2001年8月,对我院住院患者进行粪常规检查时,发现一种类似寄生虫虫卵样的物质.介绍如下.
目的:观察72例三叉神经痛中医辨证治疗的临床疗效.方法:采用中医辨证论治为主治疗,共分为外感风邪、阳明胃热、肝风内动、痰火上攻、瘀血阻络5型.治疗2周为一疗程.结果:根据
糖尿病神经病变是糖尿病(DM)最常见的慢性并发症,发病率达60%~90%,可累及全身神经系统的任何部分,以多发性周围神经病变(DPN)居多;若以周围神经传导速度或临床症状判断,DM性多发神经
目的:确定胆石清片中主要药味牛羊胆膏的精制工艺条件。方法:正交试验法。结果:确定最佳工艺条件为3倍量乙醇,使含醇浓度达到60%,胆膏比重在1.07-1.10之间。结论:精制后胆膏中胆酸含量
TOPS模式是临近空间慢速平台SAR的一种新的工作模式,这种模式由于在方位向的主动扫描,会引入多普勒频谱和方位输出时间的混叠。该文在对TOPS模式回波特性分析的基础上,提出了
针对目前城镇化进程中由于征地拆迁而引发的矛盾纠纷问题,通过文献查阅和实证考察的方法,我们分析了征地拆迁过程中的四个利益相关者的角色定位,分别是当地政府、开发商、村
在清炒中就难以达到.温度过高药材容易焦化,温度过低又使药材僵化,达不到炮制的目的,影响了药物的临床疗效,而砂炒鸡内金则避免了焦化与僵化的现象.所以,笔者在工作中常用砂
随着科学技术与社会体系的不断发展对电能的使用将越来越细化,因此电能的安全监管任务将会面临严峻的考验和挑战,更加完善的设计方法会不断地提高电能的使用安全。基于RFID的电力参数测量控制模块的设计与实现对传统的用电方式进行了改进,加入了更加人性化的设计思想,通过实践证明设计成果完成了预期的功能实现,降低了安全事故的发生几率。
在城固县进行马铃薯品种比较试验,结果表明:早大白和中薯5号综合性状好,适合大面积示范推广;荷兰15总薯和商品薯产量及商品薯率都较高,但抗病性较差,在生产中应注意防治病害;
1992年以来,笔者采用中西医结合治疗30例扁平苔藓,经随访,临床疗效满意。总结如下。 1 临床资料 病例中,男12例,女18例;年龄最小24岁,最大58岁;发生部位以颊部最多(20例),次为舌