圖雅　青松

摘要： 現(xiàn)實(shí)中的許多系統(tǒng)，尤其是計(jì)算機(jī)軟件系統(tǒng)可以使用Petri網(wǎng)來為它們建立模型。在該文中對計(jì)算機(jī)軟件系統(tǒng)中幾個典型問題：生產(chǎn)者—消費(fèi)者問題、哲學(xué)家進(jìn)餐問題、讀者—寫者問題、PV 操作等的petri網(wǎng)建模進(jìn)行了分析。

關(guān)鍵詞：petri網(wǎng)；建模；計(jì)算機(jī)軟件系統(tǒng)

中圖分類號：TP302 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）31-0222-02

1 概述

Petri網(wǎng)作為一個新型的建模工具，已在計(jì)算機(jī)科學(xué)的各個領(lǐng)域得到了應(yīng)用。除了計(jì)算機(jī)硬件之外，計(jì)算機(jī)軟件也可以由petri網(wǎng)來建模。這可能是petri網(wǎng)最普遍的用處， 并且有巨大的潛力，產(chǎn)生有用的結(jié)果。對于計(jì)算機(jī)硬件的描述和建，許多系統(tǒng)已經(jīng)開發(fā)了數(shù)年，但是應(yīng)用petri網(wǎng)對計(jì)算機(jī)軟件建模研究的較晚。 本文主要對生產(chǎn)者—消費(fèi)者問題、哲學(xué)家進(jìn)餐問題、讀者—寫者問題、PV 操作等操作系統(tǒng)中的著名問題的petri網(wǎng)建模進(jìn)行分析。

2 生產(chǎn)者—消費(fèi)者問題

2.1 基本的生產(chǎn)者—消費(fèi)者問題

生產(chǎn)—消費(fèi)問題中包括共享數(shù)據(jù)對象，但這個例子中共享對象是一個緩沖區(qū)。生產(chǎn)者進(jìn)程（producer process）生產(chǎn)一個對象，將它放入緩沖區(qū)中；消費(fèi)者進(jìn)程（consumer process）等待生產(chǎn)者將這個對象放入緩沖區(qū)之后，將它取走并消費(fèi)、生產(chǎn)者—消費(fèi)者問題可以用圖1所示建模。位置B表示緩沖區(qū)，每個token表示一個已經(jīng)產(chǎn)生但沒有被消費(fèi)的項(xiàng)（item）。

2.2 多生產(chǎn)者—多消費(fèi)者問題

基本的生產(chǎn)者—消費(fèi)者問題的一種變化形式是多生產(chǎn)者—多消費(fèi)者問題。在這種變化形式中，多個生產(chǎn)者生產(chǎn)多個項(xiàng)，這些項(xiàng)放入公共緩沖區(qū)中，以便多個消費(fèi)者消費(fèi)在圖2中用Petri網(wǎng)描述這個問題。與圖2不同的是描述了s個生產(chǎn)者，t個消費(fèi)者。系統(tǒng)起始于從有s個token的生產(chǎn)者進(jìn)程的初始位置和有t個token的消費(fèi)者進(jìn)程的初始位置。這表示有s個生產(chǎn)者和t個消費(fèi)者執(zhí)行可重入程序，共享代碼。有一種可能的方法是為生產(chǎn)者和消費(fèi)者進(jìn)程復(fù)制代碼，但這會導(dǎo)致具有相同行為的比較大的Petri網(wǎng)的產(chǎn)生。

2.3 采用約速性緩沖區(qū)的生產(chǎn)者—消費(fèi)者問題

生產(chǎn)者—消費(fèi)者問題的另一種變化形式是采用約束緩沖區(qū)（bounded buffer）的生產(chǎn)者—消費(fèi)者問題。這種形式中，認(rèn)為生產(chǎn)者與消費(fèi)者之間的緩沖區(qū)有限制，也就是說，僅有n個格來放置項(xiàng)。這樣生產(chǎn)者不能一直以期望的速度生產(chǎn)，它需要在消費(fèi)者消費(fèi)慢且緩沖區(qū)滿的時候等待。圖3是這個問題的Petri網(wǎng)模型，受約束的緩沖區(qū)用兩個位置來表示：B表示已被生產(chǎn)但未被消費(fèi)的項(xiàng)的數(shù)目（既滿格的數(shù)目），B表示緩沖區(qū)中空格的數(shù)目。初始時B有n個token，B為空。如果緩沖區(qū)滿了， B為空，B有n個token.這時，生產(chǎn)者如果試圖將另外一個項(xiàng)放入緩沖區(qū)，這個操作將會被中止，因?yàn)锽中沒有token可讓變遷點(diǎn)火。

3 哲學(xué)家進(jìn)餐問題

哲學(xué)家進(jìn)餐問題是Dijkstra在1968年提出的。問題中描述了五位哲學(xué)家，他們或者思考或者進(jìn)餐，坐在一個擺滿中餐的圓桌前。每兩個哲學(xué)家之間放著一只筷子。然而，一個人必須有兩只筷子才能吃中餐；因此每個哲學(xué)家必須同時拿起他左右側(cè)的兩只筷子，才能進(jìn)餐。這里存在一個問題就是如果所有哲學(xué)家都拿起左邊的筷子，等待右邊的筷子，那么將陷入無限等待狀態(tài)，既死鎖狀態(tài)。

圖4是這個問題的Petri網(wǎng)模型。位置C1、C2、C3、C4、C5表示筷子，因?yàn)樽畛趺恐豢曜佣伎臻e，所以每個位置有一個token.對于每個哲學(xué)家用兩個位置Mi和Ei代表其思考和進(jìn)餐狀態(tài)。對每個哲學(xué)家來說，當(dāng)從思考狀態(tài)轉(zhuǎn)變到進(jìn)餐狀態(tài)時，他兩邊的筷子，只能由他一個人使用，別人就不能再用了。這個問題很容易用Petri網(wǎng)來描述。

4 讀者—寫者問題

讀者—寫者問題有幾種變化形式，但基本結(jié)構(gòu)相同。有兩種進(jìn)程：讀者進(jìn)程和寫者進(jìn)程。所有進(jìn)程共享一個公共文件、變量或數(shù)據(jù)對象。讀者進(jìn)程不能修改共享對象，而寫者進(jìn)程可以進(jìn)行修改。所以寫進(jìn)程對所有其他讀進(jìn)程和寫進(jìn)程互斥，但多個讀進(jìn)程能夠同時訪問共享數(shù)據(jù)。在這個問題的關(guān)鍵在于定義一個控制結(jié)構(gòu)，使得不產(chǎn)生死鎖或者說不違背互斥原則。圖4描述了當(dāng)讀者進(jìn)程的數(shù)目限定為n的Petri網(wǎng)模型。

5 P V 操作

多數(shù)同步問題不能直接用Petri網(wǎng)解決，而更適合用已有的同步機(jī)制來解決?；谛盘柫康腜、V操作是一種典型的同步機(jī)制，由Dijkstra提出。信號量是一個取非負(fù)整數(shù)的數(shù)據(jù)項(xiàng)。V操作對信號量加1，P操作對信號量減1，P操作只能在信號量非負(fù)的時候進(jìn)行；如果信號量為零，不能進(jìn)行P操作，只有等其他進(jìn)程執(zhí)行V操作后，才能進(jìn)行P操作。P、V操作用原語實(shí)現(xiàn)；沒有其他的操作能夠同時修改信號量的值。

這些操作很容易用來模型化，圖6是PV操作的Petri網(wǎng)模型。每個信號量用一個位置表示，位置中Token的個數(shù)表示信號量的值。一個P操作將信號量位置作為輸入；一個V操作將信號量位置作為輸出。這種能夠?qū)V操作模型化的能力優(yōu)勢使得很多系統(tǒng)用PV操作來實(shí)現(xiàn)或設(shè)計(jì)。例如，Venus操作系統(tǒng)將PV操作作為基本的內(nèi)部進(jìn)程通訊機(jī)制。這些系統(tǒng)可以用Petri網(wǎng)來建模。

6 結(jié)論

Petri網(wǎng)作為一種建模工具，已在計(jì)算機(jī)科學(xué)的各個領(lǐng)域得到了應(yīng)用。操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中最重要的系統(tǒng)軟件，而操作系統(tǒng)又是最復(fù)雜的大型系統(tǒng)軟件，如何解決操作系統(tǒng)中的經(jīng)典問題，減小操作系統(tǒng)的規(guī)模，對于開放操作系統(tǒng)乃至大型軟件系統(tǒng)十分必要。本文中對計(jì)算機(jī)軟件系統(tǒng)中幾個典型問題的petri網(wǎng)建模進(jìn)行了分析。通過使用petri網(wǎng)建模，可以對操作系統(tǒng)中資源共享及引起的競爭、可能產(chǎn)生的死鎖一目了然，為描述其他類似的問題開辟了一條新路。

參考文獻(xiàn)：

[1] 舒遠(yuǎn)仲，劉炎培，彭曉紅，等.面向?qū)ο驪etri網(wǎng)建模技術(shù)綜述[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010（15）.

[2] 湯小丹.計(jì)算機(jī)操作系統(tǒng)[M].4版.西安：西安電子科技大學(xué)出版社，2014.

[3] 秦江濤. 基于Petri網(wǎng)的生產(chǎn)系統(tǒng)建模與分析研究[J].上海理工大學(xué)學(xué)報(bào)，2017（4）.