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

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

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

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

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

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