| dc.contributor | 資訊管理學系 | |
| dc.creator (作者) | 趙玉 | zh_TW |
| dc.date (日期) | 2012 | |
| dc.date.accessioned | 15-Apr-2016 11:37:40 (UTC+8) | - |
| dc.date.available | 15-Apr-2016 11:37:40 (UTC+8) | - |
| dc.date.issued (上傳時間) | 15-Apr-2016 11:37:40 (UTC+8) | - |
| dc.identifier.uri (URI) | http://nccur.lib.nccu.edu.tw/handle/140.119/84760 | - |
| dc.description.abstract (摘要) | 鎖死停止自動化系統對公司造成重大的財政損失。 學界使用派翠網路把所有狀態找出(由狀態樹)便能找出死鎖原因。狀態樹可分為好和壞兩區域，壞區域又可分為危險和死鎖區。一旦進入危險區，便無可避免地走向死鎖區。死鎖防治是目前普遍採用方法，加控制器以防止系統進入危險區。 主要是防治首次會見壞標記（First-met Bad Marking, FBM）的發生，以減少控制器數目。最大許可和使用最少監控的最佳合成控制器一直是一個熱門的課題。同時記憶體及CPU的使用量也要越少越好。 目前所有最大許可的死鎖防止方法都須依靠狀態樹來列舉所有的狀態或混合整數規劃（MIP）測試。這隨著派翠網路大小迅速(稱為指數型態)往上爆升而超過電腦所能承擔。因此此類方法無法處理大型網路。其他方法亦有類似問題。 本人提議革命性的控制理論以線性複雜度找出所有基本虹吸，進而以最少的控制器達到最大允許狀態，且能避免電腦難以處理的指數型態(避免狀態樹建立) 。 目前本人已發展理論，找出由N個基本虹吸複合成區域死鎖所有標記(Marking) 狀態。從而據此加入控制器。進一步，結合數個控制器，以減少控制器，並達到最大允許狀態。 本人提議結合上述理論，直接由N個基本虹吸複合推導出最少控制器最大允許，而無須找出死鎖所有標記及結合數個控制器之部驟。 | |
| dc.description.abstract (摘要) | Deadlocks halting automated systems cause significant financial loss. Scholars use Petri nets to find all the states (by the state tree) are able to identify the cause of deadlocks. State tree can be divided into two areas of good and bad. Once inside the danger zone, it will inevitably evolve towards deadlock area. Deadlock prevention is commonly used methods by adding the controller to prevent the system from entering the danger zone. It has been a hot research to synthesize optimal controllers to be maximally permissive with fewest monitors. Both memory and CPU usage should be as minimal as possible. At present, all the maximally permissive methods rely on state tree to enumerate all of the states or mixed integer programming (MIP) test. The number of states or iterations grows exponentially with respect to the size of a Petri net. Therefore, such methods cannot handle large nets. I propose a revolutionary fastest maximally permissive control theory to find all the basic siphons with linear complexity and least number of controllers, and there is no need to construct reachability tree. The complexity of the policy is no longer exponential. Currently I have developed theories to identify unmarked token patterns of local blockings for a N-compound region consisting N basic siphons. Furthermore, a method is developed to combine some of these controllers to reduce the number of controllers while achieving maximal permissiveness. I propose to combine these theories to directly find the above final set of controllers based on set of the basic siphons without the need to identify all emptiable siphons and the associated unmarked token patterns to lead to local blockings. | |
| dc.format.extent | 1101999 bytes | - |
| dc.format.mimetype | application/pdf | - |
| dc.relation (關聯) | 計畫編號 NSC101-2221-E004-001 | |
| dc.subject (關鍵詞) | —派翠網;信標可控性;FMS;S3PR;死鎖;控制 | |
| dc.subject (關鍵詞) | Petri nets;siphons;deadlocks;control | |
| dc.title (題名) | 以最少顯示器達到最大許可的Petri網的一個子類的最快死鎖防止方法 | zh_TW |
| dc.title.alternative (其他題名) | A Polynomial Maximally Permissive Deadlock Prevention Policy with Fewest Monitors for a Subclass of Petri Nets | |
| dc.type (資料類型) | report | |
