幾種S-PR網(wǎng)子類的活性條件及其應(yīng)用.pdf

1、資源分配系統(tǒng)是一種典型的離散事件系統(tǒng)。由于對有限的資源的競爭使用，資源分配系統(tǒng)的進程間極易產(chǎn)生對資源的循環(huán)等待，進而發(fā)生死鎖，使得系統(tǒng)阻塞而無法繼續(xù)執(zhí)行。作為一種數(shù)學(xué)建模工具，Petri網(wǎng)由于其直觀的圖形表示和形式化的數(shù)學(xué)描述，被廣泛應(yīng)用于分析和解決資源分配系統(tǒng)的死鎖問題。其中，S*PR網(wǎng)以其良好的建模能力，正逐漸受到學(xué)者們的重視，并被廣泛應(yīng)用于建模和分析資源分配系統(tǒng)的死鎖問題。通過研究信標的活性條件，進而檢測網(wǎng)系統(tǒng)活性并設(shè)計滿足條件的

2、活性保持控制器是基于S*PR網(wǎng)的死鎖控制的主要研究方向之一。目前學(xué)術(shù)界對S*PR網(wǎng)活性條件的研究主要集中于它的一個普通網(wǎng)子類Gadara網(wǎng)。Gadara網(wǎng)可建模同種資源總量為1且進程的選擇操作不使用任何資源的資源分配系統(tǒng)。然而經(jīng)過研究發(fā)現(xiàn)，許多常見的資源分配系統(tǒng)并不能通過Gadara網(wǎng)建模，而需要通過S*PR網(wǎng)的其他子類建模和分析其特性。針對這一問題，本文對幾種S*PR網(wǎng)子類活性條件及其應(yīng)用展開了研究，完成的主要工作有:
　　(1

3、)提出了一類用于建模存在緩存區(qū)的資源分配系統(tǒng)的普通S*PR網(wǎng)模型，BS*PR網(wǎng)。同時證明了BS*PR網(wǎng)是活的當(dāng)網(wǎng)中所有信標滿足資源受控條件。進而提出了一個檢測非資源受控信標的混合整數(shù)規(guī)劃算法，該算法可用于BS*PR網(wǎng)的活性檢測。在多線程程序和經(jīng)典制造系統(tǒng)案例中的應(yīng)用表明，該模型能夠有效地建模和分析存在緩存區(qū)的資源分配系統(tǒng)。
　　(2)提出了一類可用于建模進程選擇操作對稱使用資源的資源分配系統(tǒng)的普通S*PR網(wǎng)模型，SEM-S*PR網(wǎng)

4、。該子類進程子網(wǎng)選擇庫所可對稱地使用資源，并不再限制系統(tǒng)中使用的同種資源的總量為1。因而，Gadara網(wǎng)本質(zhì)上是SEM-S*PR網(wǎng)的一個特例。同時證明了SEM-S*PR網(wǎng)是活的當(dāng)且僅當(dāng)網(wǎng)中所有信標始終非空，該結(jié)論為混合整數(shù)規(guī)劃技術(shù)應(yīng)用于SEM-S*PR網(wǎng)的活性檢測提供了理論基礎(chǔ)。進一步地，將SEM-S*PR網(wǎng)結(jié)論推廣至選擇操作對稱使用資源的廣義S*PR模型，OSC-S*PR網(wǎng)。在證明其保持活性的充分條件是網(wǎng)中所有信標Max'-Contr

5、olled的基礎(chǔ)上，提出了一個基于混合整數(shù)規(guī)劃的S*PR網(wǎng)非Max'-Controlled信標檢測算法，該算法可用于檢測該OSC-S*PR網(wǎng)的活性。更重要的是，通過將任意S*PR網(wǎng)轉(zhuǎn)換為一個OSC-S*PR網(wǎng)，該算法也可推廣應(yīng)用于S*PR網(wǎng)的活性檢測。
　　在實際軟件系統(tǒng)，經(jīng)典制造系統(tǒng)以及哲學(xué)家模型中的實驗結(jié)果表明，本文提出的幾種S*PR網(wǎng)子類不但能夠建模和分析Gadara網(wǎng)所建模系統(tǒng)中的死鎖問題，還能夠分別建模進程選擇操作對稱和