圖雅　青松

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

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

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

1 概述

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

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

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

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

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

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

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

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

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

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

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

4 讀者—寫者問(wèn)題

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

5 P V 操作

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

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

6 結(jié)論

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