Deadlock Analysis, Prevention and Avoidance in Sequential Resource Allocation Systems

Tricas García, Fernando
Ezpeleta Mateo, Joaquín (Director de la tesis)

Universidad de Zaragoza, 2003


ISBN: 978-84-692-7503-0

Resumen: El propósito de este trabajo es generalizar y extender los resultados existentes en el análisis, prevención y evitación de bloqueos en sistemas de asignación de recursos, con una atención especial hacia los sistemas de fabricación flexible. En este sentido, se proponen nuevas clases de sistemas con restricciones similares a las que podemos encontrar dentro del ámbito de los sistemas de fabricación. En un primer paso se estudiarán las propiedades estructurales de estas clases para comprobar que son adecuadas para el modelado y análisis del tipo de problemas considerado. Las soluciones al problema de los bloqueos se presentarán desde dos puntos de vista: prevención y evitación de los problemas de bloqueo, junto con algunos datos comparativos con otras soluciones al problema. El objetivo es obtener políticas de control muy permisivas, que puedan implantarse según diferentes consideraciones, proporcionando flexibilidad al diseñador del sistema. Finalmente se propone una mejora de un método de cálculo de cerrojos. Estas componentes estructurales están ligadas a la existencia de problemas de bloqueo en algunas clases de sistemas, y en ese sentido es muy conveniente disponer de métodos eficientes para su cálculo. El método propuesto mejora a los existentes mediante la utilización de paralelismo, y la adaptación a las características de los sistemas considerados. ------- This work concentrates on deadlock problems in concurrent systems due to the common use of system resources organized in what is commonly known as Sequential Resource Allocation Systems and paying a special attention to subclasses of manufacturing systems. To do that, special classes of Petri net models are defined that allow to capture resource allocation events used to synchronize processes that have to share a set of reusable system resources. The classes of Petri nets introduced are studied from the structure point of view, showing the clear mapping among system and model structures. It is also shown how deadlock related situations can be explained in terms of markings and model structures. To solve deadlock problems, two different approaches are adopted. The first one is known as a deadlock prevention perspective, and makes an intensive use of different liveness characterizations developed in this work. The final result is a deadlock prevention algorithm that iteratively constrains the language of the input model so that the final controlled model is live in terms of Petri net definitions, which implies that the controlled system is free of deadlocks and ensures that the execution of any active process can terminate. The second approach falls into the deadlock avoidance family of solutions. In this work it is shown how the specific characteristics of the class of systems in consideration can be used to extend and improve the well-known Banker's solution for deadlock avoidance, allowing us to give a solution to deadlock problems in the most general class of sequential resource allocation systems. In both cases, and taking into account that obtaining the most permissive solution is NP-complete, the proposed solutions are experimentally compared with other solutions in order to get insight of how permissive the proposed algorithms are, showing they provide a good trade-off between computation cost and permissiveness.

Nota: Presented on 20 05 2003

Nota: Tesis-Univ. Zaragoza