An Approach to Solve Deadlock Problem of Component Connection

Fei-Qiao Mao, Deyu Qi, Weiwei LinJournal of Software 2008 · DOI

Abstract

Implicit hard-coding of procedure call-based component connections restricts software flexibility and introduces reliability risks through deadlock loops. This paper proposes a formal semantic model, the "call-based connector," to explicitly separate connection logic from component implementation. We introduce two key algorithms: TPDCC (Two Phases Deadlock Connection Check) for identifying deadlock loops in a directed connection graph, and DCEMRF (Deadlock Connection Elimination based on Maximum Reuse Frequency) for determining the minimum set of connections to eliminate to resolve these deadlocks. Experimental results on synthetic cases and a large-scale EJB-based system demonstrate the approach's effectiveness and efficiency in enhancing software reliability.

Introduction: The Hidden Fragility of Component Connections

In modern component-based software engineering, components such as EJBs or JavaBeans frequently interact via procedure calls. Often, these interaction patterns are "hard-coded"—embedded directly within the component's internal implementation. This practice leads to significant architectural challenges. Primarily, it obscures the overall system topology, making it easy to inadvertently create circular dependencies (e.g., Component A calls B, which calls C, which then calls A).

Figure 1: A simple example of circular dependencies in Java code.

As illustrated in Figure 1, these loops may pass standard compilation but result in catastrophic runtime failures like stack overflows or infinite loops. Traditional compilers are blind to these cross-component logical cycles, and exhaustive formal verification often fails to scale due to state space explosion.

A Formal Framework for Deadlock Resolution

To address these issues, we propose a lightweight, graph-based framework consisting of three main stages:

1. Formal Modeling of Connectors

We define a "Call-Based Connector" model using Communicating Sequential Processes (CSP) and predicate logic. This model extracts connection logic from the component "black box," transforming it into an explicit, inspectable architectural entity.

2. TPDCC: Deadlock Detection

The Two Phases Deadlock Connection Check (TPDCC) algorithm operates in two stages:

  • Phase 1: It dynamically constructs a directed graph where nodes represent components and edges represent the procedure calls (connectors).
  • Phase 2: It performs a graph traversal to identify all simple cycles, which correspond to potential deadlock loops.

3. DCEMRF: Optimal Elimination

Once deadlocks are identified, the Deadlock Connection Elimination based on Maximum Reuse Frequency (DCEMRF) algorithm determines the most efficient way to resolve them. By identifying "high-frequency" edges—those participating in multiple loops—the algorithm finds the minimum number of connections that must be refactored to render the system deadlock-free.

Evaluation and Results

The framework was evaluated using both synthetic test cases and a real-world "Welfare Registration System" built on Enterprise JavaBeans (EJB). The real-world system comprised 194 interaction points and 295 connectors.

Key findings include:

  • Accuracy: TPDCC successfully identified 100% of deadlock loops across all test scenarios.
  • Performance: In the complex Welfare Registration System, detection (TPDCC) was completed in just 7.035 ms, while the elimination strategy (DCEMRF) took only 0.008 ms.
  • Scalability: The detection algorithm's time complexity is $O(m + v^2 + nv)$, where $m$ is the number of connectors, $v$ is the number of components, and $n$ is the number of loops. This ensures performance remains stable as system complexity increases.

Conclusion

By treating component connections as first-class semantic entities rather than mere implementation details, this approach provides a scalable and efficient means of ensuring software reliability. The separation of connection logic also serves as a foundation for developing "adaptive connectors" capable of dynamic runtime reconfiguration to avoid failures. Future work will focus on automating the extraction of these connector models directly from source code.

Summary updated

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.
BibTeX
@article{mao2008approach,
  author = {Fei-Qiao MAO and Deyu Qi and Weiwei Lin},
  title = {{An Approach to Solve Deadlock Problem of Component Connection}},
  journal = {Journal of Software},
  year = {2008},
  doi = {10.3724/sp.j.1001.2008.02527},
}
Figure