理發(fā)師問(wèn)題的Petri網(wǎng)模型

劉萍

（甘肅民族師范學(xué)院計(jì)算機(jī)科學(xué)系，合作　747000）

理發(fā)師問(wèn)題的Petri網(wǎng)模型

劉萍

（甘肅民族師范學(xué)院計(jì)算機(jī)科學(xué)系，合作747000）

0　引言

1962年，C.A.Petri在他的博士論文“用自動(dòng)機(jī)通訊”中，首次提出Petri網(wǎng)的基本概念和Petri網(wǎng)的基本理論。Petri網(wǎng)是一個(gè)6元組（S，T；F，K，W，M0），其中（S，T；F）稱為Petri網(wǎng)的基礎(chǔ)網(wǎng)；基礎(chǔ)網(wǎng)是有限的有向圖，結(jié)點(diǎn)分為條件的集合S和事件的集合T。條件在圖上用圓圈表示；事件在圖上用矩形表示。有向圖的弧只有條件指向事件的弧和事件指向條件的弧兩類，弧在圖上用箭頭表示，F(xiàn)是弧的集合。K是定義在S上的容量函數(shù)，取值是非負(fù)整數(shù)。W是定義在F上的權(quán)值函數(shù)，取值是非負(fù)整數(shù)。Petri網(wǎng)的標(biāo)識(shí)M是定義在S上的非負(fù)整數(shù)函數(shù)，M0稱為Petri網(wǎng)的初始標(biāo)識(shí)。

Petri網(wǎng)是研究分布式系統(tǒng)的建模和分析的有力的工具，這是因?yàn)镻etri網(wǎng)特別便于描述系統(tǒng)中進(jìn)程或部件之間的順序、并發(fā)、沖突以及同步等關(guān)系。經(jīng)過(guò)50多年的研究，Petri網(wǎng)已經(jīng)成為具有廣泛的實(shí)際應(yīng)用的重要學(xué)科。

在實(shí)際應(yīng)用中，Petri網(wǎng)對(duì)于一個(gè)問(wèn)題的研究，首先需要對(duì)問(wèn)題設(shè)計(jì)出一個(gè)常規(guī)的系統(tǒng)，然后設(shè)計(jì)這個(gè)系統(tǒng)的Petri網(wǎng)模型。進(jìn)一步利用Petri網(wǎng)的理論對(duì)這個(gè)系統(tǒng)的Petri網(wǎng)模型進(jìn)行分析。在分析中發(fā)現(xiàn)的任何問(wèn)題都指明設(shè)計(jì)中存在的缺陷。分析這些缺陷，就可以為設(shè)計(jì)的改進(jìn)提供依據(jù)。再對(duì)改進(jìn)后的設(shè)計(jì)修改Petri網(wǎng)的模型，如此循環(huán)反復(fù)，直到分析不出有什么問(wèn)題為止。

1　進(jìn)程間通信（IPC）問(wèn)題

進(jìn)程間通信（IPC）問(wèn)題是在操作系統(tǒng)中的重要問(wèn)題。 IPC問(wèn)題是作為解決在運(yùn)行中的幾個(gè)進(jìn)程的互斥問(wèn)題提出的，問(wèn)題的核心是找到某種途徑來(lái)防止幾個(gè)進(jìn)程同時(shí)讀寫共享的數(shù)據(jù)或文件。睡眠的理發(fā)師問(wèn)題和哲學(xué)家進(jìn)餐問(wèn)題 （Dijkstra，1965），讀者-寫者問(wèn)題（Courtois，1971），生產(chǎn)者-消費(fèi)者問(wèn)題，是在操作系統(tǒng)中關(guān)于進(jìn)程間通信（IPC）問(wèn)題的幾個(gè)較為著名問(wèn)題［2］。對(duì)于上述問(wèn)題中的哲學(xué)家進(jìn)餐問(wèn)題，讀者-寫者問(wèn)題，生產(chǎn)者-消費(fèi)者問(wèn)題等都有了Petri網(wǎng)的模型。從這些問(wèn)題的Petri網(wǎng)的模型中，可以看到，Petri網(wǎng)不僅能夠刻畫系統(tǒng)的結(jié)構(gòu)，而且能夠描述系統(tǒng)的動(dòng)態(tài)行為。這是利用Petri網(wǎng)解決實(shí)際問(wèn)題的優(yōu)點(diǎn)。在已有的文獻(xiàn)中，我們沒(méi)有看到關(guān)于睡眠的理發(fā)師問(wèn)題的Petri網(wǎng)的模型。本文試圖建立該問(wèn)題的Petri模型，并且對(duì)于這種模型作出一些分析。

從Petri網(wǎng)的觀點(diǎn)來(lái)看待一個(gè)系統(tǒng)，首先分析系統(tǒng)中所表現(xiàn)的兩個(gè)基本概念：事件和條件。事件是系統(tǒng)中所發(fā)生的動(dòng)作；系統(tǒng)的每一個(gè)動(dòng)作都是由系統(tǒng)的狀態(tài)所控制，而系統(tǒng)的狀態(tài)則由一組條件來(lái)描述。因此，每一個(gè)事件的發(fā)生，總是以一些條件作為前提，這些條件稱為事件的前提條件。當(dāng)事件發(fā)生以后，一些前提條件消失，另外的一些條件成立，稱為事件的后繼條件。設(shè)t是一個(gè)事件，·t表示t的所有前提條件的集合，即·t=｛s| s∈S∧（s，t）∈F｝，稱為t的前集；以t·表示t的所有后繼條件的集合，即t·=｛s|s∈S∧（s，t）∈F｝。對(duì)于一個(gè)系統(tǒng)，重要的工作是確定每一個(gè)事件t的前集和后集。

在Petri網(wǎng)中標(biāo)識(shí)是很重要的概念。標(biāo)識(shí)M在一定的條件下可以由事件t發(fā)動(dòng)，產(chǎn)生新的標(biāo)識(shí)，記作M［t＞。從M0經(jīng)過(guò)發(fā)動(dòng)能夠產(chǎn)生的所有標(biāo)識(shí)的集合記為R（M0）。R（M0）可以按照發(fā)動(dòng)的次序列成樹(shù)稱為Petri網(wǎng)的可達(dá)標(biāo)識(shí)樹(shù)。

2　理發(fā)師問(wèn)題

理發(fā)店中有三名理發(fā)師A，B，C，每人一張理發(fā)椅子，等待室有5張供顧客等待的休息椅子。如果有空閑的休息椅子，顧客進(jìn)入理發(fā)店就可以坐下等待。理發(fā)過(guò)程分為兩個(gè)工序：工序1是A為顧客服務(wù)，工序1完成以后，顧客分男，女由B或C提供第2道工序的服務(wù)。B或C服務(wù)完成以后，由收銀員收取理發(fā)費(fèi)，顧客離開(kāi)理發(fā)店。

顧客的行為：顧客進(jìn)入理發(fā)店看到有空閑的休息椅子，就坐下等待。如果沒(méi)有空閑的休息椅子，顧客就離開(kāi)理發(fā)店。等待休息的顧客看到A的理發(fā)椅子空出，先到的顧客就坐上，并且喚醒理發(fā)師A為自己理發(fā)（工序1）。工序1完成后，如果B或C仍然為上一個(gè)顧客服務(wù)，則這個(gè)顧客仍然坐在A的椅子上等待，否則顧客坐上B或C的理發(fā)椅子，并且喚醒B或C為自己理發(fā)（工序2）。工序2完成后，顧客喚醒收銀員，交付理發(fā)費(fèi)，離開(kāi)理發(fā)店。

理發(fā)師，收銀員行為：理發(fā)師為顧客完成了一道理發(fā)工序以后休息（睡覺(jué)）；等待被下一個(gè)顧客喚醒，為下一個(gè)顧客服務(wù)。收銀員收取顧客的理發(fā)費(fèi)以后休息（睡覺(jué)），等待被下一個(gè)顧客喚醒，收取理發(fā)費(fèi)。理發(fā)師的行為和收銀員行為是循環(huán)的（從理發(fā)店開(kāi)門到關(guān)門）。

理發(fā)店的狀態(tài)由顧客和理發(fā)員、收銀員的行為決定。

在理發(fā)師問(wèn)題中，顧客的行為和理發(fā)師（收銀員）的行為是Petri網(wǎng)的所有的事件。下面討論顧客的行為的事件和理發(fā)師的行為的事件。

a1-有一名顧客進(jìn)入理發(fā)店；

a2-顧客在休息椅子上坐下；

a3-顧客叫醒理發(fā)師A開(kāi)始理發(fā)的第1道工序；

a4-A完成為顧客理發(fā)的第1道工序；

a5-顧客叫醒理發(fā)師B開(kāi)始理發(fā)的第2道工序；

a6-B完成為顧客理發(fā)的第2道工序；

a7-顧客理發(fā)完畢喚醒收銀員，付錢離開(kāi)理發(fā)店；

a8-顧客叫醒理發(fā)師C開(kāi)始理發(fā)的第2道工序；

a9-C完成為顧客理發(fā)的第2道工序；

a10-顧客理發(fā)完畢喚醒收銀員，付錢離開(kāi)理發(fā)店。

下面分析理發(fā)店的各種狀態(tài)，即Petri網(wǎng)的所有的條件。

S1-理發(fā)師A休息（睡覺(jué)）；

S2-理發(fā)師B休息（睡覺(jué)）；

S3-理發(fā)師C休息（睡覺(jué)）；

S4-收銀員休息（睡覺(jué)）；

S5-休息室有顧客（最多容納5人，設(shè)置S5的容量K=5來(lái)控制）；

S6-顧客坐在A的理發(fā)椅子上；

S7-顧客接受理發(fā)師A第1道工序的服務(wù)；

S8-理發(fā)師A第1道工序的服務(wù)完成，顧客等待第2道理發(fā)工序；

S9-顧客接受理發(fā)師B第2道工序的服務(wù)；

S10-理發(fā)師B完成理發(fā)的第2道工序；

S11-顧客接受理發(fā)師C第2道工序的服務(wù)；

S12-理發(fā)師C完成理發(fā)的第2道工序。

下面計(jì)算在2.1中出現(xiàn)的事件的前提條件和后繼條件。

3　理發(fā)師問(wèn)題的Petri網(wǎng)

下面根據(jù)2.5的計(jì)算給出理發(fā)師問(wèn)題的Petri網(wǎng)。規(guī)定每一條弧的權(quán)值為1；S5的容量為5，其余各條件的容量都是1，如圖1所示。

4　理發(fā)師問(wèn)題的Petri網(wǎng)的可達(dá)標(biāo)識(shí)樹(shù)

為了使得理發(fā)師問(wèn)題的Petri網(wǎng)能夠運(yùn)行，需要給出初始標(biāo)識(shí)。由于S5的前提事件所以S5可以通過(guò)a1的發(fā)動(dòng)獲得標(biāo)識(shí)，不需要預(yù)先設(shè)置標(biāo)識(shí)。S1，S2，S3和S4在運(yùn)行中是循環(huán)出現(xiàn)的條件，因此必須預(yù)先設(shè)置標(biāo)識(shí)。因此M0=｛S1，S2，S3，S4｝。R（M0）包括以下9個(gè)標(biāo)識(shí)：

可達(dá)標(biāo)識(shí)樹(shù)如下：

圖1

［1］Petri C.A..Kommunikation Mit Automaten，Bonn，1962

［2］Peterson J.L..Petri網(wǎng)理論與系統(tǒng)模擬.吳哲輝譯.中國(guó)礦業(yè)大學(xué)出版社，1989

［3］吳哲輝.Petri網(wǎng)導(dǎo)論.北京：機(jī)械工業(yè)出版社，2006

［4］袁崇義.Petri網(wǎng)原理.北京：電子工業(yè)出版社，1998

［5］袁崇義.Petri網(wǎng)原理與應(yīng)用.北京：電子工業(yè)出版社，2005

［6］劉萍.關(guān)于Petri網(wǎng)的代數(shù)結(jié)構(gòu).甘肅高師學(xué)報(bào)，2014（2）

［7］劉萍.出現(xiàn)網(wǎng)的抽象描述.甘肅高師學(xué)報(bào)，2014（5）

［8］劉萍.出現(xiàn)網(wǎng)的S切.現(xiàn)代計(jì)算機(jī)，2014（7）

Petri Net；Problem of Barbers；Reachability Tree of Markings

Petri Net Model on the Problem of Barbers

LIU Ping
（Department of Computer Science，Gansu Normal University for Nationalities，Gansu 747000）

1007-1423（2015）17-0059-04

10.3969/j.issn.1007-1423.2015.17.013

2015-04-29

2015-06-10

討論在操作系統(tǒng)中研究的關(guān)于進(jìn)程間通信（IPC）的一個(gè)著名的問(wèn)題：睡眠的理發(fā)師問(wèn)題。給出這個(gè)問(wèn)題的Petri網(wǎng)模型和這個(gè)Petri網(wǎng)的可達(dá)標(biāo)識(shí)圖性質(zhì)。

Petri網(wǎng)；理發(fā)師問(wèn)題；可達(dá)標(biāo)識(shí)圖

甘肅民族師范學(xué)院院長(zhǎng)基金（No.2013-16）

劉萍（1978-），青海西寧人，碩士，講師，研究方向?yàn)镻etri網(wǎng)、數(shù)據(jù)庫(kù)理論

Discusses the Petri net model on the problem of barbers.The problem of Barbers is an important problem in operating systems.Carries out the Petri net model of the problem，and the property of the reachability tree of markings.