CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

A BDD-Based Approach for Designing Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems

Zhennan Fei (Institutionen för signaler och system, Automation) ; Spyros Reveliotis ; Sajed Miremadi (Institutionen för signaler och system, Automation) ; Knut Åkesson (Institutionen för signaler och system, Automation)
Göteborg : Chalmers University of Technology, 2013. - 18 s.

In order to develop a computationally efficient implementation of the maximally permissive deadlock avoidance policy (DAP) for complex resource allocation systems (RAS), a recent approach focuses on the identification of a set of critical states of the underlying RAS state-space, referred to as minimal boundary unsafe states. The availability of this information en- ables an expedient one-step-lookahead scheme that prevents the RAS from reaching outside its safe region. The work presented in this paper seeks to develop a symbolic approach, based on binary decision diagrams (BDDs), for efficiently retrieving the minimal boundary unsafe states from the underlying RAS state- space. The presented results clearly demonstrate that symbolic computation enables the deployment of the maximally permissive DAP for complex RAS with very large structure and state-spaces with limited time and memory requirements. Furthermore, the involved computational costs are substantially reduced through the pertinent exploitation of the special structure that exists in the considered problem.

Nyckelord: Resource Allocation Systems, Discrete Event Systems, Deadlock Avoidance, Maximal Permissiveness, Supervisory Control Theory, Binary Decision Diagrams.

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2013-11-14. Senast ändrad 2015-01-16.
CPL Pubid: 186774