一种基于有向无环图的依赖管理机制及实现*

2020-12-23李洋昕张咏秋

通信技术 2020年12期

颜雨，李洋昕，张咏秋

（1.海军装备部，四川成都 610036；2.中国电子科技集团公司第三十研究所，四川成都 610041）

0 引言

控制类软件通常需要维护大量的状态信息，根据输入数据推动内部状态机运转，从而输出控制信息。这些内部状态信息之间通常包含复杂的依赖关系，一个输入条件的改变会引起内部一系列的连锁反应。如果这些状态以及状态之间的关系都采用硬编码，状态依赖关系处理会分散在软件代码各处，正确性完全依赖于实现人员，易出现偏差，且后期软件的维护工作会非常困难。当依赖关系稍有变动，软件就需要做较大改动，易有所遗漏。

图论以图为研究对象。研究的图是由若干抽象的点以及若干连接两点的线所组成。在实际应用中，通常可以用点代表事物，连线代表两个事物之间的关系，以此研究处理多个事物间的复杂关系[1]。

本文针对大量状态之间的复杂依赖关系问题，基于图论中的有向无环图相关理论，把软件中的每一个状态信息抽象成一个点，两个状态之间的依赖关系抽象成这两个点之间的有向线段，把复杂状态依赖问题抽象成对有向无环图问题的求解[2]。

1 需求分析

控制软件的主要功能是根据系统输入信息以及系统当前的状态做出控制决策。系统输入信息包括设备时钟或定时器、系统数据输入、系统传感器输入以及用户输入等。系统状态包括系统内部数据状态、系统软件运行状态等。控制软件在处理系统外部输入时，需先要根据预定的逻辑推动内部状态机运转，修改系统内部状态[3]。控制软件内部通常会包含多个状态机，分别处理不同子系统的逻辑。多个状态机之间彼此推动运转，直到达成一个稳定状态。在状态机运转的同时，根据状态机设定执行预定操作，输出控制决策。同样的，对于外部输入，当系统状态不同时，系统做出的控制决策也不尽相同。

控制软件通常需要面对一个复杂系统，软件内部需要维护大量的状态信息，以便精确与实际环境相对应。数量众多的状态之间相互依赖，关系盘根错节，增加了控制软件的复杂度，严重威胁软件的可靠性。目前，比较常用的简化问题的方法是把全部状态集合划分成若干个较小的子集合。每个子集合规模不大，内部状态关系相对清晰[4]。跨越子集合的状态依赖关系归结为子集合之间的依赖关系。这样实际上就把原始问题划分成了两个层次，一是子集合内部问题，二是子集合之间的问题，降低了问题规模，间接提高了软件实现的正确性。

虽然通过上述方法可以降低软件实现难度，但是并没有解决软件正确性全部交由实现人员保证的问题，且仍然存在软件可维护性基础较差、无法灵活面对需求变更的问题。本文应用图论中的有向无环图理论，设计并实现了一套依赖管理机制，把系统内状态信息抽象成点，状态信息之间的依赖关系抽象成有向边，每个状态点仅需要关注有依赖关系的少数状态点，简化了问题规模，通过有向无环图的相关算法自动解决状态信息之间的依赖传递问题。

2 算法设计

首先需要构建生成系统状态信息组成的有向图，初始化有向图各顶点的基本状态，然后可以接收处理外部输入，修改内部状态，通过遍历有向图传播内部状态变动，输出控制指令。

2.1 初始化

2.1.1 建立有向图存储

有向图的建立主要是生成顶点和有向边信息。信息可以从配置文件加载，也可以把构建过程固化在软件代码中。有向图在算法中采用双重邻接表的结构存储。普通邻接表为图中的各个顶点独自建立一个链表，链表中存放所有直接可达的顶点，即是以该顶点为起始点的有向边的终止顶点。双重邻接表在邻接表的基础上为每个顶点增设了一个链表，存放所有逆向直接可达的顶点，即是以该顶点为终止顶点的有向边的起始顶点。双重邻接表实质上分别以起始顶点和终止顶点为线索，把有向边保存了两次，方便从正向和逆向遍历有向图。

每个顶点在实现上使用state_vertex 类来保存。类定义如下：

需要说明的是，state 成员表示顶点的当前状态，initted 成员表示节点顶点状态是否经过初始化，edges_in 存储逆向直接可达顶点，edges_out 存储直接可达顶点。

2.1.2 加载状态

完成有向图存储的建立后，需要加载各个顶点的初始状态。由于各个顶点代表的实际状态有很多类型，部分顶点有外部真实状态相对应，可以在初始化时确定状态值。部分顶点只代表了软件的一个中间状态，需要根据其他顶点的状态动态计算实际的状态值。顶点状态初始化的第一步是独立计算各个顶点的状态值。

对于无法独立确定状态值的顶点，采用默认的load_state 方法设置初始状态值。load_state 方法定义如下：

需要说明的是，设置initted 成员为false，表示该顶点的状态值没有最终确定。对于可以独立确定状态值的顶点，则需要根据具体情况重载该方法，为state 成员设置合适的取值，并将initted 成员设置为true，表示该顶点的状态值已经最终确定。

2.1.3 进入稳定状态

完成状态加载后，由于部分中间状态还没有确定，需要计算确定这部分顶点的状态值后，有向图才能进入稳定状态发挥功效。中间状态节点的状态值由该顶点的逆向直接可达顶点的状态值共同决定。check_depends 方法用于完成这一功能。该方法遍历了指定顶点的edges_in 列表，检查是否列表中的所有顶点状态值都是true，如果是则返回true，否则返回false。如果其中有顶点的initted 成员是false，则抛出异常。check_depends 允许顶点重新定义，采用更加个性化的状态值计算方法，定义如下：

由于中间状态顶点可能存在嵌套依赖的现象，一次遍历不一定能计算出所有中间状态顶点的状态值，因此需要采用多轮遍历。如果某一次遍历成功得到状态值的顶点数为0，则表示出现了无法确定初始值的中间状态顶点。这表示有向图的设计有问题，需要重新安排各个顶点的类型与连通关系等。完整的有向图初始化函数实现如下：

2.1.4 示例

下面以一个远程访问流程控制为例，简述有向图的初始化过程。远程访问过程需要用户设置目标服务器的IP 地址和端口，以及用于身份认证的用户名和密码信息。根据软件控制流程，建立如图1所示的有向图。

“IP 地址”“端口号”“用户名”和“密码”4个顶点与配置信息内容高度相关，初始化时根据配置项是否加载成功设置状态。“连接信息”是“IP地址”和“端口号”状态的汇总，便于软件衡量是否具备建立连接的基础，属于中间状态，需要等待其他顶点状态加载完成后，通过自身的check_depends 方法计算状态值。“登录信息”同样属于中间状态，需要通过自身的check_depends 方法计算状态值。“连接状态”和“登录状态”是软件的动态状态，需要自定义加载状态方法，设置初始状态为false。

图1 有向图初始化

2.2 处理外部输入

有向图进入稳定状态后，可以开始处理外部输入。外部输入信号经过处理后最终会造成某个顶点的状态值产生变化。该顶点处理完自身状态变动后，将沿着有向边向直接可达的顶点发起通知信号。收到该信号的顶点由于输入依赖的状态值有变化，需要重新计算并更新自身的状态值，并继续沿着有向边传播通知信号，直到整个有向图达成一个新的平衡。

外部信号通过调用顶点的set_state 方法改变顶点的状态值，其中使用到的change_state 是一个可重载的方法，默认实现是直接返回新状态值，通过重载可以实现对输入信号的个性化处理。

顶点之间传递通知信号，使用当前顶点的broadcast 方法在broadcast 方法中遍历需要接收信号的顶点，并调用其activate 方法，实现信号的传递。