基于Petri網(wǎng)的圖書借閱系統(tǒng)的建模與優(yōu)化分析

李 增

( 安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院， 安徽 淮南 232001 )

0 引言

圖書借閱系統(tǒng)是一個分布式的系統(tǒng)，它涉及到數(shù)據(jù)庫管理、分布式系統(tǒng)設(shè)計、數(shù)據(jù)數(shù)字化等多方面問題.在該系統(tǒng)中，如何在宏觀層面上對分布式系統(tǒng)進(jìn)行建模，以及如何指導(dǎo)系統(tǒng)后續(xù)設(shè)計與實現(xiàn)，對增大系統(tǒng)的容量和加強(qiáng)系統(tǒng)的可用性具有重要的作用.Petri網(wǎng)作為分布式系統(tǒng)的建模和分析的一種工具，可用于描述系統(tǒng)進(jìn)程或部件的順序、并發(fā)、沖突以及同步等關(guān)系，并且可對系統(tǒng)的活性、可達(dá)性、有界性等進(jìn)行有效驗證.目前，國內(nèi)外有很多學(xué)者利用Petri網(wǎng)的行為輪廓、變化域、變更傳播等性質(zhì)對系統(tǒng)進(jìn)行建模和優(yōu)化.例如：文獻(xiàn)[1]針對在訪問選課系統(tǒng)中的臨界資源時出現(xiàn)的不穩(wěn)定性問題，建立了一種基于Petri網(wǎng)的選課系統(tǒng)流程模型，并利用“生產(chǎn)者-消費者”原理和信號量機(jī)制對模型進(jìn)行了優(yōu)化；文獻(xiàn)[2]利用Petri網(wǎng)對數(shù)字圖書館的服務(wù)系統(tǒng)進(jìn)行了建模，并根據(jù)Petri網(wǎng)的性質(zhì)對數(shù)字圖書館的過程控制進(jìn)行了研究；文獻(xiàn)[3]利用隨機(jī)著色Petri網(wǎng)建立了圖書館文獻(xiàn)檢索系統(tǒng)模型，并通過設(shè)計一種新的排序算法提高了檢索的準(zhǔn)確度.文獻(xiàn)[4]利用Petri網(wǎng)建立了圖書館管理預(yù)測模型，并對預(yù)測量作出了定量分析，為合理制定圖書館的管理方案提供了理論依據(jù).文獻(xiàn)[5-6]描述了圖書館借閱系統(tǒng)的基本功能，并對建立的Petri網(wǎng)模型進(jìn)行了分析.目前為止，未見利用Petri網(wǎng)對圖書借閱中的續(xù)借失敗、借書時長設(shè)置和讀者可借數(shù)目的控制問題進(jìn)行研究的報道.基于此，本文提出一種基于Petri網(wǎng)的圖書借閱系統(tǒng)模型，并對模型進(jìn)行優(yōu)化，最后通過仿真驗證優(yōu)化模型的穩(wěn)定性和可靠性.

1 基本概念

定義1[7](Petri網(wǎng)) 設(shè)PN=(P,T;F)為一個Petri網(wǎng)，滿足以下條件：

1)P是有限庫所集，T是有限變遷集；

2)P∪T≠?且P∩T=?；

3)F?(P×T)∪(T×P)， 表示PN的流關(guān)系且(P∪T，F(xiàn))是強(qiáng)連通圖；

4) dom(F)={x∈P∪T|?y∈P∪T:(x,y∈F)}；

5) cod(F)={x∈P∪T|?y∈P∪T:(y,x∈F)}.

定義2[8](有界性和安全性) 設(shè)Σ=(P,T;F,M0)為一個Petri網(wǎng).若存在正整數(shù)B， 使得?M∈R(M0):M(p)≤B， 則稱庫所p為有界的，并稱滿足此條件的最小正整數(shù)B為庫所p的界，記為B(p)，即B(p)=min{B|?M∈R(M0):M(p)≤B}.當(dāng)B(p)=1時，稱庫所p為安全的.如果每個p∈P都是有界的，則稱Σ為有界Petri網(wǎng),稱B(Σ)=max{B(p)|p∈P}為Σ的界.當(dāng)B(Σ)=1時，稱Σ為安全的.

定義3[9](行為輪廓) 設(shè)(N，M0)是一個網(wǎng)，初始標(biāo)識為M0.對任給的變遷對(ti,tj)， 其弱序關(guān)系??(T×T)滿足下面關(guān)系:

1)若t1?t2且t2?/t1， 則稱t1和t2為嚴(yán)格序關(guān)系，記作t1→t2；

2)若t1?/t2且t2?t1， 則稱t1和t2為嚴(yán)格逆序關(guān)系，記作t1→-1t2；

3)若t1?/t2且t2?/t1， 則稱t1和t2為排他關(guān)系，記作t1+t2；

4)若t1?t2且t2?t1， 則稱t1和t2為交叉序關(guān)系，記作t1‖t2；

5)將所有關(guān)系的集合稱為網(wǎng)系統(tǒng)的行為輪廓，記作BP={→,→-1,+,‖}?(T×T).

2 基于Petri網(wǎng)的圖書借閱系統(tǒng)的建模與優(yōu)化

2.1 基于Petri網(wǎng)的圖書借閱系統(tǒng)模型

圖1 圖書借閱系統(tǒng)的Petri網(wǎng)模型

目前，大學(xué)圖書館借閱系統(tǒng)的基本功能可分為查詢、借書、還書、續(xù)借4個部分，由此建立的圖書借閱系統(tǒng)模型如圖1所示，圖1中各變遷的含義見表1.由圖1可見，當(dāng)讀者進(jìn)入圖書館時t1發(fā)生，并由此引發(fā)t2(借書)或t7(還書)或t11(續(xù)借)發(fā)生.若執(zhí)行t2， 需輸入所需要借閱的圖書信息.t4與t3為排他關(guān)系，t3、t5為嚴(yán)格序關(guān)系.t6為借書成功，t6發(fā)生需進(jìn)行審核，審核包括2個方面：一是所有可被借閱的圖書是否均已被預(yù)借，二是讀者是否已達(dá)到預(yù)借上限.若t7發(fā)生，則引發(fā)排他結(jié)構(gòu)(t8+t9).若讀者未在規(guī)定期限內(nèi)還書，則需繳納罰款，執(zhí)行t8， 否者執(zhí)行t9.若t11發(fā)生，則引發(fā)排他結(jié)構(gòu)(t12+t13)， 即續(xù)借成功或失敗，最后退出系統(tǒng).

表1 各變遷的含義

2.2 圖書借閱系統(tǒng)的Petri網(wǎng)模型優(yōu)化分析

由圖1可以看出，模型雖然能夠反映讀者借閱的整個流程，但依然存在一些問題： ①因所有圖書的借閱時間相同，使得一些使用率較高的圖書(如工具類圖書和習(xí)題類圖書等)不能被充分利用，進(jìn)而降低這些圖書的使用價值.②因所有借閱者的可借圖書數(shù)目相同，因此導(dǎo)致需要大量借閱圖書的讀者需要多次借閱，浪費時間.③多位讀者同時借閱同一本圖書時，若當(dāng)前可借的圖書只有一本，此時會造成系統(tǒng)阻塞，無法進(jìn)行下一步操作.④當(dāng)讀者續(xù)借失敗時，系統(tǒng)不能給出相應(yīng)的解決辦法，使讀者無法繼續(xù)借閱.

基于上述存在的問題，本文對上述模型進(jìn)行優(yōu)化，優(yōu)化后的圖書借閱系統(tǒng)的Petri網(wǎng)模型見圖2，圖2中各變遷的含義見表2.模型優(yōu)化的具體解決方案如下： ①根據(jù)圖書的館藏量、機(jī)密性及實用性等，將圖書分為4個等級，每個等級對應(yīng)不同的可借時間，分別為：特級圖書(不可外借)、Ⅰ級圖書(可借閱15 d)、Ⅱ級圖書(可借閱30 d)、Ⅲ級圖書(可借閱90 d).此時，t8、t9、t10、t11為排他關(guān)系，記為t8+t9+t10+t11.另外，t8與t12為嚴(yán)格序關(guān)系，其他以此類推.②變遷t19為識別進(jìn)館人員身份信息，并將其分為受邀訪客和借閱者，其中借閱者包含本科生、研究生和教師3類.受邀訪客只可在館閱讀，不可借閱；根據(jù)教師和學(xué)生的閱讀能力和借閱需求不同，對老師和學(xué)生分別設(shè)置不同的可借數(shù)目n(t23) (n教師>n研究生>n本科生).t22、t23處于交叉序關(guān)系，記為t22‖t23.通過t22、t23的發(fā)生判斷模型是否執(zhí)行t25.此外，識別讀者身份信息時，若讀者有超期未還的圖書，系統(tǒng)將自動識別，并觸發(fā)變遷t27和t28發(fā)生.③t17(借書成功)發(fā)生的條件是t17的2個前置庫所必須都得到一個token，其目的是通過這種控制結(jié)構(gòu)過濾掉不符合系統(tǒng)要求(讀者當(dāng)前不可借)的請求，這樣既可保證系統(tǒng)的可觸發(fā)序列的執(zhí)行，也能夠減輕系統(tǒng)的運行負(fù)擔(dān).借書成功后，系統(tǒng)自動開始計時，即t18發(fā)生，直到還書或續(xù)借結(jié)束.④讀者借閱超時是續(xù)借失敗的主要原因.讀者續(xù)借時，優(yōu)化后的模型首先確認(rèn)借閱是否超時，若讀者借閱超時則可通過繳納罰金的方式繼續(xù)續(xù)借.該步驟與還書模塊的審核共用一個流程，因此該步驟不會增加系統(tǒng)的負(fù)擔(dān).

圖2 優(yōu)化后的圖書借閱系統(tǒng)Petri網(wǎng)模型

表2 各變遷的含義

圖3 仿真結(jié)果圖

3 模型的有界性和安全性分析

本文利用PIPE軟件對優(yōu)化后的模型進(jìn)行仿真模擬，驗證優(yōu)化后模型的有界性和安全性.驗證結(jié)果如圖3所示.圖3表明，本文所建立的圖書借閱系統(tǒng)Petri網(wǎng)優(yōu)化模型是有界、安全、無死鎖的，即優(yōu)化后的圖書借閱系統(tǒng)是合理可行的.

4 結(jié)論

本文利用Petri網(wǎng)模型建立了圖書借閱系統(tǒng)模型，并通過分析變遷之間的行為輪廓關(guān)系和增加控制結(jié)構(gòu)優(yōu)化了該系統(tǒng)模型.利用PIPE軟件對優(yōu)化后的模型進(jìn)行仿真表明，優(yōu)化后的模型能夠提高圖書的使用效率和系統(tǒng)的工作效率，可為借閱者提供一個更加人性化的借閱環(huán)境.本文在優(yōu)化模型過程中，只對原模型的部分結(jié)構(gòu)進(jìn)行了改進(jìn)，而且僅考慮了變遷之間的行為輪廓關(guān)系，因此具有一定的局限性.今后我們將結(jié)合變化傳播、變化域、過程挖掘等知識對模型進(jìn)行進(jìn)一步的分析.