谈软件系统模块间循环依赖识别

摘要:软件系统中各平台多模块开发过程中，若开发人员对自己模块扇入、扇出盲目增删，导致模块间依赖变更，容易产生系统级循环依赖。如果模块间产生循环依赖环，代码在编译时若不清除中间生成文件，编译生成的产品有极大的风险或者采用2次编译的方法解决。通过进行循环依赖分析找出所有依赖环的解决办法。

关键词:循环依赖;非法依赖;多模块;软件工程;识别

引言

随着当前软件系统越来越复杂，平台越来越多，平台包含的模块也越来越多，开发人员在开发代码的时候如果对模块的依赖未按照设计要求随意增加，容易导致平台级或系统级别产生循环依赖。贾利敏等提出通过程序执行轨迹，确定数据依赖结点、控制依赖结点和结点可到达语句来计算变量切片［1］;不过此检测方式粒度太细，不利于软件模块级识别。刘杰等提出基于归纳变量的循环依赖分析方法［2］，识别变量级别的循环依赖;刘鹏远等提出采用提取公共部分方法消除包级别循环依赖［3］，若模块粒度更细、数量更大的话，不易实现;丁丽丽等基于GCC5．1针对分支嵌套循环的依赖提出计算依赖距离方法能够快速地分析出该类循环潜在的并行性［4］，但此计算类似C语言某几条语句循环依赖，不适用于系统内模块查找循环依赖。

1依赖概述

在架构设计合理，各平台的依赖关系应该是上层平台依赖下层平台，各模块的扇入、扇出设计合理的前提下，整个系统所有模块的依赖关系不应该存在循环依赖。正常情况下平台或模块间的依赖关系应该是上层平台依赖下层平台:①上层依赖下层。②上层对下层一对一或一对多。③最下层不对本平台依赖，但可能会对下层级平台有依赖。④最上层不会被本平台依赖，但会被上层平台依赖。⑤存在上层跨层依赖下层。⑥所有模块都会被依赖。⑦所有模块对外不重复。

2循环依赖分析与解决方案

2．1分析根因

由于平台级的循环依赖根因也是由于各平台对应的模块产生的模块级循环依赖导致，所以可以把平台级循环依赖和模块级循环依赖看作相同的问题。循环依赖的根因是纵向依赖链上出现了环:如A依赖B、B依赖C、C依赖A或D依赖E、E依赖F、F依赖G、G依赖D，这样就出现依赖环，当然这个是比较简单的环示例，在实际情况中，有的环路节点有很多个可以达到10多个模块，如果靠人工计算，一是计算工作量比较大，另一个是容易遗漏。

2.1.1数学模型假设数学模型如下。1)假定我们当前有一个平台(多个平台检测方法类似)。2)假定这一个平台一共有n个模块{M1，M2，M3，…，Mn}。3)第k个模块扇入ik个。4)第k个模块扇出ok个。

2.1.2计算方法1)把这n个模块所有扇出o1，o2，o3，…，on合并起来，记为AllOutputList［］。2)把这n个模块遍历，扇入不在AllOutputList中的删除，因为这些删除的依赖是从其他平台引入的依赖，此步处理完后，所有模块的扇入只来源此平台的扇出，这样在后续计算时，减少冗余的计算。3)选择任意模块作为当前计算模块，并检查此模块是否有扇入，如果有扇入则把所有扇入的父节点进行统计并去重，并把此模块记录到ParentsList数组，如某模块一共有20个扇入，其中5个扇入来源于A模块、10个扇入来源于B模块、另外5个扇入来源于C模块，则此模块的Parents数据包含A、B、C三个模块，此时Parents里存放A、B、C;如果没有扇入，则不计算。4)遍历Parents数组所有成员，如A，则先把A与Par-entsList中所有元素进行比较，检查是否有重复，若有重复，则发现环，并打印环，然后出栈;若无重复，则把A模块视为当前计算模块，把A模块进行压栈，并返回到步骤3;等数组的第一个成员完成遍历后，继续搜索Parents第二个成员B，并返回到步骤3，把B模块视作模块1进行递归;如果没有重复，则把A压栈到ParentsList;并返回到步骤3，把A模块视作模块1进行递归，依此类推。5)在检查的过程中如果发现当前计算模块没有扇入，则不计算，直接返回。通过不断查询数组中成员数据是否包含新模块名，再对数组进行压栈、出栈，再对比，这样最终可遍历到整个系统所有循环依赖环。经过3、4、5这3步能把所有模块所有依赖环找出来。但还有另一个问题:多个依赖环有重复的情形，假设4个模块依赖环为:A依赖B，B依赖C，C依赖D，D依赖A，则搜索出来的结果可能出现环的4种情况分别为:A，B，C，D;B，C，D，A;C，D，A，B;D，A，B，C。碰到这种情形需要对这几种环进行去重操作，详细处理办法是把生成环的所有结点分别存放到二维数组以模块名为单位排序后进行比较，如果相同，则表示环相同，反之则不相同。像首尾相同的模块:［A—B—C—D—A］，这样的环取［A—B—C—D］，此去重方法较简单，不再赘述。

2．2测试数据来源

来源于XX产品XX平台，测试模块220个，扇入、扇出共计2000多个。

3实验结果与分析

通过对数据进行计算后展示的结果如下(只展示部分数据，实际发现环个数72个)。从上述结果可以看出:①单模块可能会存在于多个环。②可发现被其他多次循环依赖模块。

4结语

本文通过把软件系统中模块名视为树节点，通过深度遍历优先算法进行查找模块间依赖环，不断对纵向依赖链进行先判断再压栈，若对下层无依赖则出栈，递归查询所有依赖环，并且给出多种依赖环去重的方法，最终发现所有模块所有依赖环。不过还有一个问题，当前方法查找出来的依赖环不具备给架构师详细依赖接口的能力，需要在代码实现的时候压栈、出栈时把父子节点之间的接口关系也添加上，这个难度也不大，不再赘述。

参考文献:

［1］贾利敏，张忠林．一种简化依赖关系的动态程序切片算法［J］．郑州大学学报，2009，30(2):84－87．

［2］刘杰，曹琰，魏强，等．符号执行中的循环依赖分析方法［J］．计算机工程，2012，38(22):24－33．

［3］刘鹏远，邓沌华，李祥．不同粒度循环依赖的消去方法［J］．信息通信，2013(6):9－10．

［4］丁丽丽，李雁冰，张素平，等．分支嵌套循环的自动并行化研究［J］．计算机科学，2017，44(5):14－52．

作者：任启红 黄辉 周锋 王永亮 单位：三江学院计算机科学与工程学院