petri网在操作系统课程学习过程中的应用研究

《petri网在操作系统课程学习过程中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据科技教育剑额中国科技信息2006年第11期CHINASCIENCEANDTECHNOLOGYINFORMATIONJun2006Petri翘在攥作蒸笺课程学习过程中的应用研究郭长友周智刚郑文艳德g,11学院计算机系255023摘要使用pe_cri网来提高操作系统课程的学习是一种有效的方法。利用这种普通的图形化工具，使得一些难懂的概念譬如进程的并发执行以及相关联的通信和同步可以很好的解释和理解。另外．一些自动和半自动软件工具可以帮助学生分析得到的Petr『网模型．．裳键词操作系统的学习；Petri网；并发性：通信；同步‘简

2、介在操作系统课程的发展过程中，进程的同步和通信是最重要的也是最难理解的概念之一【3I。我们可以发现与此相关的一些基本的经典问题：如避免死锁，公平性等。操作系统课程的学习需要有如下预备知识：并发进程的基本概念。在本文中，我们需要一些简单的工具，这些工具有如下作用：1)很好地理解基本的并发概念2)很容易地发现不同3)同步／通信机制直接翻译成某种目标编程语言4)使用自动或半自动软件工具来探索这些机制的性质Petri网是这种工具之一，在学习这些问题时，可以给我们极大的帮助。一方面，它给我们一种最初的图形化来表示操作系统的并发行为。这种方

3、式对学生来说可以很容易地理解概念，另一方面加固了这种理解。1petri网的应用在petri网中有四种基本的元素141，库所(place)，变迁(transition)，弧(arc)和标识(mark)。库所可以表示前提或程序常量的值，每个变迁处理一个程序指令的执行。标识通过从一个变迁的输入库所到它的输出库所所通过的弧模拟了程序的执行，并且也可以模拟进程所使用的资源情况。库所Placeo变迁Transition口标汉MarkinplaceU变迁根据以下的并发原则使得库所包含的托肯(token)的数目上发生变化：我们说一个变迁是能够发

4、生的当且仅当该变迁的所有输入库所至少包含一个托肯。最简单的方式下，能够发生的变迁发生时，从输入库所去掉一个托肯，并在输出库所中加入一个托肯。用petri网模拟的进程称为状态机，在这种网中，一个变迁只有一个输入库所和一个输出库所。普通的程序结构可以很容易的用petri网来模拟，如下列方式：用petri网来模拟三种基本的控制结构，如图一所示。在这种方式下，我们可以模拟进程Pl和P2基本的并发机制，如图二所示。我们首先说明在petri网中怎样模拟有界缓冲器问题⋯。第二个例子改进了很著名的Peterson互斥算法，该算法是关于两个进程P

5、i和Pj的。每一个进程的算法都有如下的结构：RepeatFlag[il：=tureITurn=j；While(flag[j】andturn=j)doNo—opICriticalsectionFla斟i】：=false；RemaindersectionUntilfalseI272但是，如果我们想要对这两个进程的并发行为进行全局观察并且与这个互斥算法进行交互，此时Petri网展示了它的优点：可以对上述要求进行图示并加深对它的理解，如图三所示。我们可以看到对进程PO；}NPl，‘我们可以把先前的有界缓冲问题简单地转化成使善芰Q匿柒觥图

6、二POflaglOlffal∞盘_霉￡l】鼍IM”plIVt轧畸蛳T10ND}ATARGet期KIG慕^b豁《I}00L^j哪孔撕￡图三万方数据用信号作为一种同步机制的命令式程序设计语言(一些基本的工作参考[2】)。以上做法的基本思想是：1)所Data和holes是常量信号；2)从这些库所到一个变迁的弧代表的是等待操作；3)从一个变迁到这些库所的弧代表的是信号操作，这些可以被实现，因为petri网中变迁的并发性这种语义可以被认为是一种原子性操作。Holes：countersemaphore：一5Data：countersemap

7、hore：-0,ProcessPRODUCERWhileturedoWait(Holes)；Signal(Data)；EndwhfieProcessCONSUMERWhileturedoWait(Data)；Signal(Holes)；Endwhile正如刚才我们所说的，petri网可以作为一种证明方法来分析和证明操作系统的并发机制行为⋯，包括死锁和饥饿检测、资源的最优使用等等。但是学生可以发现，在使用复杂petri网来模拟复杂并发情况时，很难来分析它们。最后希望，petri网的一些分析和证明的自动化和半自动化工具可以帮助学生来

8、处理操作系统的复杂部分。这样我们在本文中所提到的这些解决方法上可以给学生更多的信心。2结语操作系统中进程管理方面的并发性很难去讲解，我们发现petri网很适合帮助学生理解这种问题。就像我们举的几个例子，任何同步／通信机制都可以用这种方式来表示和操纵。相对来说pe