政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/84760
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 113318/144297 (79%)
Visitors : 51071854      Online Users : 945
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version


    Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/84760


    Title: 以最少顯示器達到最大許可的Petri網的一個子類的最快死鎖防止方法
    Other Titles: A Polynomial Maximally Permissive Deadlock Prevention Policy with Fewest Monitors for a Subclass of Petri Nets
    Authors: 趙玉
    Contributors: 資訊管理學系
    Keywords: —派翠網;信標可控性;FMS;S3PR;死鎖;控制
    Petri nets;siphons;deadlocks;control
    Date: 2012
    Issue Date: 2016-04-15 11:37:40 (UTC+8)
    Abstract: 鎖死停止自動化系統對公司造成重大的財政損失。 學界使用派翠網路把所有狀態找出(由狀態樹)便能找出死鎖原因。狀態樹可分為好和壞兩區域，壞區域又可分為危險和死鎖區。一旦進入危險區，便無可避免地走向死鎖區。死鎖防治是目前普遍採用方法，加控制器以防止系統進入危險區。 主要是防治首次會見壞標記（First-met Bad Marking, FBM）的發生，以減少控制器數目。最大許可和使用最少監控的最佳合成控制器一直是一個熱門的課題。同時記憶體及CPU的使用量也要越少越好。 目前所有最大許可的死鎖防止方法都須依靠狀態樹來列舉所有的狀態或混合整數規劃（MIP）測試。這隨著派翠網路大小迅速(稱為指數型態)往上爆升而超過電腦所能承擔。因此此類方法無法處理大型網路。其他方法亦有類似問題。 本人提議革命性的控制理論以線性複雜度找出所有基本虹吸，進而以最少的控制器達到最大允許狀態，且能避免電腦難以處理的指數型態(避免狀態樹建立) 。 目前本人已發展理論，找出由N個基本虹吸複合成區域死鎖所有標記(Marking) 狀態。從而據此加入控制器。進一步，結合數個控制器，以減少控制器，並達到最大允許狀態。 本人提議結合上述理論，直接由N個基本虹吸複合推導出最少控制器最大允許，而無須找出死鎖所有標記及結合數個控制器之部驟。
    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.
    Relation: 計畫編號 NSC101-2221-E004-001
    Data Type: report
    Appears in Collections:[Department of MIS] NSC Projects

    Files in This Item:

    File Description SizeFormat
    101-2221-E004-001.pdf1076KbAdobe PDF2311View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback