一种解决构件连接死锁问题的方法
作者:
基金项目:

Supported by the Natural Science Foundation of Guangdong Province of China under Grant No.05300200 (广东省自然基金); the Guangdong-Hong Kong Technology Cooperation Funding Scheme of China under Grant No.2005A10307007 (粤港关键领域重点突破项目)


An Approach to Solve Deadlock Problem of Component Connection
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [28]
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    隐式硬编码的基于过程调用构件连接束缚构件集成的灵活性,且存在的死锁连接造成软件可靠性隐患问题.针对该问题,首先建立基于过程调用连接器形式语义模型,显式地将连接关系从构件中分离;然后给出并通过映射规则进行连接器到构件连接有向图的转换,并设计给出两阶段死锁检查算法和基于极大复用频率死锁连接消除算法,用于找到存在的所有死锁连接回路和消除所有死锁连接需要消除的最小数目连接的位置.最后应用及实验结果表明,该解决方法可行而且有效,可以用于增强软件可靠性,同时因其从语义上分离描述和存储构件连接方式,适合以此为基础进一步设计实现适应性连接器.

    Abstract:

    Procedure call-based component connections which are latent in hard code do not only restrict the flexibility of software but also cause hidden problems to software reliability because of the existing deadlock connection loops. To solve this problem, first, a formal semantic model called call-based connector has been built which explicitly separates connection from components. Second, mapping rules used to convert call-based connectors into component the connection directed graph are proposed. Then, two algorithms, TPDCC (two phases deadlock connection check) used to find all existing deadlock connection loops, and DCEMRF (deadlock connection elimination based on maximum reuse frequency) used to find locations with the least number of connections that must be eliminated to eliminate the loops, are provided respectively. Last, its application and experimental results show that the presented approach is feasible and effective, so it can be used to enhance the reliability of software, also be fit as a basis to further design and implement adaptive connector due to its separative way of description and storage of component connection in semantic.

    参考文献
    [1] Li G, Jing MZ. Concept, properties and functions of component connection in adaptive software architecture. Computer Engineering, 2003,29(1):265-267 (in Chinese with English abstract).
    [2] Gossler G, Sifakis J. Composition for component-based modeling. Science of Computer Programming, 2005,55(1-3):161-183.
    [3] Allen RJ. A formal approach to software architecture [Ph.D. Thesis]. Pittsburgh: Carnegie Mellon University, 1997.
    [4] Ren HM, Qian LQ. Research on component composition and its formal reasoning. Journal of Software, 2003,14(6):1066-1074 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/14/1066.htm
    [5] Xiong HM, Ying S, Yu LJ, Zhang T. A composite reuse of architectural connectors using reflection. Journal of Software, 2006, 17(6):1298-1306 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/1298.htm
    [6] Wermelinger M, Lopes A, Fiadeiro JL. Superposing connectors. In: Proc. of the 10th Int’l Workshop on Software Specification and Design. San Diego: IEEE Computer Society Press, 2000. 87-94. http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath= /dl/proceedings/&toc=comp/proceedings/iwssd/2000/0884/00/0884toc.xml&DOI=10.1109/IWSSD.2000.891129
    [7] Magee J, Dulay N, Eisenbach S, Kramer J. Specifying distributed software architectures. In: Schafer W, Botella P, eds. Proc. of the 5th European Software Engineering Conf. Berlin: Springer-Verlag, 1995. 137-153.
    [8] Milner R, Parrow J, Walder D. A calculus of mobile processes. Information and Computation, 1992,100(1):1-40.
    [9] Oquendo F. p-ADL: An architecture description language based on the higher-order typed p-calculus for specifying dynamic and mobile software architectures. ACM Software Engineering Notes, 2004,29(3):1-14.
    [10] Li CY, Li GS, He PJ. A formal dynamic architecture description language. Journal of Software, 2006,17(6):1349-1359 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/1349.htm
    [11] C?mpan S, Leymonerie F, Oquendo F. Handling dynamic behaviour in software architectures. In: Morrison R, Oquendo F, eds. Proc. of the 2nd European Workshop on Software Architectures. LNCS 3527, Berlin: Springer-Verlag, 2005. 77-93.
    [12] Allen R, Garlan D. A formal basis for architectural connection. ACM Trans. on Software Engineering and Methodology, 1997,6(3): 213-249.
    [13] Allen R, Douence R, Garlan D. Specifying and analyzing dynamic software architectures. In: Astesiano E, ed. Proc. of the 1st Int’l Conf. on Fundamental Approaches to Software Engineering. LNCS 1382, Berlin: Springer-Verlag, 1998. 21-37.
    [14] Hoare CAR. Communicating sequential process. 2004. http://www. usingcsp.com
    [15] Matena V, Drishnan S. Apllying Enterprise JavaBeans, Component-Based Development for the J2EE Platform. 2nd ed., Beijing: Pearson Education, Inc., Tsinghua University Press, 2004. 50-207.
    [16] Minnameier C. Local and global deadlock-detection in component-based systems are NP-hard. Information Proc. Letters, 2007,103(3):105-111.
    [17] Majster-Cederaum M, Martens M, Minnameier C. A polynominal-time checkable sufficient condition for deadlock-freedom of component-based systems. In: van Leeuwen J, ed. Proc. of the 33rd Int’l Conf, on Current Trends in Theory and Practice of Computer Science. LNCS 4362, Berlin: Springer-Verlag, 2007. 888-899.
    [18] Gossler G, Sifakis J. Compoent-Based construction of deadlock-free systems. In: Pandya PK, ed. Proc. of the Annual Conf. on Foundations of Software Technology and Theoretical Computer Science. LNCS 2914, Berlin: Springer-Verlag, 2003. 420-433.
    [19] Wang ZF, Huang C. Static detection of deadlocks in OpenMP Fortran programs. Journal of Computer Research & Development, 2007,44(3):536-543 (in Chinese with English abstract).
    [20] Shi XH, Gao ZY, Shao H. A dynamic deadlock testing method of a concurrent ADA program. Journal of Computer Research & Development, 1999,36(8):954-960 (in Chinese with English abstract).
    [21] Compare D, Inveradi P, Wolf AL. Uncovering architectural mismatch in component behavior. Science of Computer Programming, 1999,33(2):101-131.
    [22] Ye Z, Lee EA. A causality interface for deadlock analysis in dataflow. In: Proc. of the ACM & IEEE Conf. on Embedded Software. Seoul: ACM Press, 2006. 44-52. http://portal.acm.org/citation.cfm?id=1176887.1176895&coll=GUIDE&dl=ACM&CFID= 2029577&CFTOKEN=10062163
    [23] Gradara S, Santone A, Villani ML. DELFIN+: An efficient deadlock detection tool for CCS processes. Journal of Computer and System Science, 2006,72(8):1397-1412.
    [24] Bouajjani A, Fernandez JC, Halbwachs N. Minimal model generation. In: Proc. of the 2nd Int’l Workshop on Computer-Aided Verification. LNCS 531, Berlin: Springer-Verlag, 1990. 197-203. http://springerlink.lib.tsinghua.edu.cn/content/ jntlcg33mv7rrwpd/?p=61814a0ed1d74ecc930363eec0f0292e&pi=4
    [25] Graf S, Steffen B, Luttgen G. Compositional minimization of finite state systems using interface specifications. Formal Aspects of Computing, 1996,8(5):1-28.
    [26] Stirling C, Walker D. Local model checking in the modal mu-calculus. Theoretical Computer Science, 1991,89(1):161-177.
    [27] Tsai JJP, Juan EYT. Model and heuristic technique for efficient verification of component-based software systems. In: Proc. of the 1st Int’l Conf. on Cognitive Informatics. Calgary: IEEE Computer Society Press, 2002. 59-68. http://csdl2.computer.org/ persagen/DLAbsToc.jsp?resourcePath=/dl/proceedings/&toc=comp/proceedings/icci/2002/1724/00/1724toc.xml&DOI=10.1109/COGINF.2002.1039283
    [28] Hu HY, Lu J, Ma XX, Tao XP. Study on behavioral compatibility of component in software architecture using object-oriented paradigm. Journal of Software, 2006,17(6):1276-1286 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/ 1276.htm
    相似文献
    引证文献
引用本文

毛斐巧,齐德昱,林伟伟.一种解决构件连接死锁问题的方法.软件学报,2008,19(10):2527-2538

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2007-06-04
  • 最后修改日期:2007-10-09
文章二维码
您是第20037580位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号