Abstract
Systems in which individual units concurrently process indivisible resources are inherently prone to starvation and deadlocks. This paper describes a fair scheduling mechanism for self-organizing resource-flow systems that prevents starvation as well as a distributed deadlock avoidance algorithm. The algorithm leverages implicit local knowledge about the system’s structure and uses a simple coordination mechanism to detect loops in the resource-flow. The knowledge about the loops that have been detected is then incorporated into the scheduling mechanism. Limitations of the approach are presented along with extension to the basic mechanism to deal with them.
This research is partly sponsored by the priority program “Organic Computing” (SPP 1183) of the German research foundation (DFG) in the project SAVE ORCA.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abate, A., Innocenzo, A.D., Pola, G., Di Benedetto, M.D., Sastry, S.: The Concept of Deadlock and Livelock in Hybrid Control Systems. In: Bemporad, A., Bicchi, A., Buttazzo, G. (eds.) HSCC 2007. LNCS, vol. 4416, pp. 628–632. Springer, Heidelberg (2007)
Ashfield, B., Deugo, D., Oppacher, F., White, T.: Distributed Deadlock Detection in Mobile Agent Systems. In: Hendtlass, T., Ali, M. (eds.) IEA/AIE 2002. LNCS (LNAI), vol. 2358, pp. 146–156. Springer, Heidelberg (2002)
Banaszak, Z.A., Krogh, B.H.: Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. IEEE Transactions on Robotics and Automation 6(6), 724–734 (1990)
Bandyopadhyay, A.K.: Fairness and conspiracy concepts in concurrent systems. SIGSOFT Softw. Eng. Notes 34(2), 1–8 (2009)
Barbosa, V.C.: Strategies for the prevention of communication deadlocks in distributed parallel programs. IEEE Transactions on Software Engineering 16(11), 1311–1316 (1990)
Belik, F.: An efficient deadlock avoidance technique. IEEE Transactions on Computers 39(7), 882–888 (1990)
Bracha, G., Toueg, S.: Distributed deadlock detection. Distributed Computing 2(3), 127–138 (1987)
Bustard, D., Hassan, S., McSherry, D., Walmsley, S.: GRAPHIC illustrations of autonomic computing concepts. Innovations in Systems and Software Engineering 3(1), 61–69 (2007)
Buth, B., Peleska, J., Shi, H.: Combining Methods for the Livelock Analysis of a Fault-Tolerant System. In: Haeberer, A.M. (ed.) AMAST 1998. LNCS, vol. 1548, p. 124. Springer, Heidelberg (1998)
Coffman, E.G., Elphick, M.J.: System deadlocks. Computing Surveys (1971)
Costa, G., Stirling, C.: Weak and strong fairness in CCS. Information and Computation 73(3), 207–244 (1987)
Durvy, M., Dousse, O., Thiran, P.: Self-Organization Properties of CSMA/CA Systems and Their Consequences on Fairness. IEEE Transactions on Information Theory 55(3), 1 (2009)
Ezpeleta, J., Colom, J.M., Martinez, J.: A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Robotics and Automation 11(2), 173–184 (1995)
Fanti, M.P., Zhou, M.C.: Deadlock control methods in automated manufacturing systems. IEEE Transactions on Systems, Man and Cybernetics, Part A 34(1), 5–22 (2004)
Goldman, B.: Deadlock detection in computer networks. Technical report, Massachusetts Institute of Technology, Cambridge, MA, USA (1977)
Güdemann, M., Nafz, F., Ortmeier, F., Seebach, H., Reif, W.: A Specification and Construction Paradigm for Organic Computing Systems. In: Proceedings of the 2008 Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems, pp. 233–242. IEEE Computer Society, Washington (2008)
Hsieh, F.S.: Fault-tolerant deadlock avoidance algorithm for assembly processes. IEEE Transactions on Systems, Man and Cybernetics, Part A 34(1), 65–79 (2004)
Huang, Y.S., Jeng, M.D., Xie, X., Chung, D.H.: Siphon-based deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans 36(6), 1249 (2006)
Kim, K.H., Jeon, S.M., Ryu, K.R.: Deadlock prevention for automated guided vehicles in automated container terminals. OR Spectrum 28(4), 659–679 (2006)
Kobayashi, N.: Type systems for concurrent processes: From deadlock-freedom to livelock-freedom, time-boundedness. In: van Leeuwen, J., Watanabe, O., Hagiya, M., Mosses, P.D., Ito, T. (eds.) TCS 2000. LNCS, vol. 1872, pp. 365–389. Springer, Heidelberg (2000)
Kwong, Y.S.: On the absence of livelocks in parallel programs. In: Kahn, G. (ed.) Semantics of Concurrent Computation. LNCS, vol. 70, pp. 172–190. Springer, Heidelberg (1979)
Lamport, L.: Fairness and hyperfairness. Distributed Computing 13(4), 239–245 (2000)
Li, Z.W., Zhou, M.C., Wu, N.Q.: A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews 38(2), 173–188 (2008)
Nafz, F., Ortmeier, F., Seebach, H., Steghöfer, J.-P., Reif, W.: A generic software framework for role-based Organic Computing systems. In: SEAMS 2009: ICSE 2009 Workshop Software Engineering for Adaptive and Self-Managing Systems (2009)
Nafz, F., Ortmeier, F., Seebach, H., Steghöfer, J.-P., Reif, W.: A universal self-organization mechanism for role-based Organic Computing systems. In: González Nieto, J., Reif, W., Wang, G., Indulska, J. (eds.) ATC 2009. LNCS, vol. 5586, pp. 17–31. Springer, Heidelberg (2009)
Park, D.: On the Semantics of Fair Parallelism. In: Bjorner, D. (ed.) Abstract Software Specifications. LNCS, vol. 86, pp. 504–526. Springer, Heidelberg (1980)
Sanchez, C., Sipma, H.B., Manna, Z., Gill, C.D.: Efficient distributed deadlock avoidance with liveness guarantees. In: Proceedings of the 6th ACM & IEEE International conference on Embedded software, pp. 12–20. ACM, New York (2006)
Sfinghal, M.: Deadlock detection in distributed systems. Computer 22(11), 37–48 (1989)
Wang, J., Zhang, X., Zhang, Y., Yang, H.: A Probabilistic Model for Parametric Fairness in Isabelle/HOL. In: Theorem Proving in Higher Order Logics: Emerging trends Proceedings, pp. 194–209 (2007)
Wang, Y., Kelly, T., Kudlur, M., Mahlke, S., Lafortune, S.: The application of supervisory control to deadlock avoidance in concurrent software. In: 9th International Workshop on Discrete Event Systems, WODES 2008, pp. 287–292 (2008)
Wang, Y.M., Merritt, M., Romanovsky, A.B.: Guaranteed deadlock recovery: Deadlock resolution with rollback propagation. In: Proc. Pacific Rim International Symposium on Fault-Tolerant Systems (1995)
Wu, N., Zhou, M.C.: Deadlock resolution in automated manufacturing systems with robots. IEEE Transactions on Automation Science and Engineering 4(3), 474–480 (2007)
Wu, N., Zhou, M.C., Li, Z.W.: Resource-oriented Petri net for deadlock avoidance in flexible assembly systems. IEEE Transactions on Systems, Man and Cybernetics, Part A 38(1), 56–69 (2008)
Zajac, J.: A deadlock handling method for automated manufacturing systems. CIRP Annals-Manufacturing Technology 53(1), 367–370 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Steghöfer, JP., Mandrekar, P., Nafz, F., Seebach, H., Reif, W. (2010). On Deadlocks and Fairness in Self-organizing Resource-Flow Systems. In: Müller-Schloer, C., Karl, W., Yehia, S. (eds) Architecture of Computing Systems - ARCS 2010. ARCS 2010. Lecture Notes in Computer Science, vol 5974. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11950-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-11950-7_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11949-1
Online ISBN: 978-3-642-11950-7
eBook Packages: Computer ScienceComputer Science (R0)