论文部分内容阅读
摘要： 现实中的许多系统，尤其是计算机软件系统可以使用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）.
关键词：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）.