马 俊，周 凯，任 怡，朱 浩，秦 莹，王 静

(国防科技大学计算机学院， 湖南 长沙 410073)

1 引言

软件发行管理(Software Release Management)在大型软件工程开发中的作用越来越重要[1]，同时由于大型软件组件构建和相互关系复杂，经常会由于某个组件的更新升级导致整个软件系统失效或者崩溃[2]。操作系统作为最复杂的基础软件系统之一，其版本构建和发行管理中面临的这类问题更加突出。

近年来，Linux类操作系统在服务器和桌面领域愈发普及与流行，系统复杂性也随着软件规模的增加而剧增。至2020年，仅内核代码已经超过2 500万行，包含超过61 000个文件[3]，而一个典型的Ubuntu发行版本对应软件仓库中开源软件或组件的数量也超过3万个，二进制软件包数量超过6万个。为了便于组织管理和维护，Linux系统中的应用软件以特定格式的软件包进行组织，通过软件包的各种属性描述软件包之间的相互关系，并提供管理工具(如Ubuntu的DPKG和APT工具、CentOS的RPM和YUM工具等)便于用户安装、升级与卸载软件。在软件包的相互关系中，依赖关系主要体现了一个软件的安装和执行依赖于另一个软件提供的运行库或服务接口等。操作系统在进行发行版本构建时，除了依据必要功能选择核心组件的软件包，还必须将组件依赖的软件包集成到版本中，提供一个依赖关系自洽的闭包。因此，依赖关系对于操作系统版本构建和系统的定制裁剪至关重要。

从开源社区中Linux系列操作系统发行版本的组成来看，不同使用场景与功能特性需求的差异，会导致选取软件包的范围和数量不同。表1选取开源社区发行版本活跃度统计网站Distrowatch[4]上近3个月(2020.08～2020.11)点击率排名靠前的操作系统进行分析，可以大致看出：以Ubuntu为基础衍生出了众多集成不同桌面环境和工具的桌面操作系统版本，而服务器操作系统版本则会选择相对固定的桌面环境。进一步选取比较有代表性的Ubuntu和CentOS的不同版本对软件包数量进行分析，如图1所示，可以看出：桌面版本与服务器版本在软件包的数量上存在非常大的差异。同时，由于很多的开源软件更新频繁，软件之间的依赖等关系复杂，基于这些软件包构建的操作系统也要不断迭代升级，从而使操作系统发行版本构建的碎片化问题突出。因此，如何从软件仓库选取合适的软件包，平衡软件包数量与系统可靠性之间的关系是操作系统发行版本构建和发布管理时需要重点关注的问题。

Table 1 Analysis on composition and characteristics of typical of operating system distribution表1 典型操作系统发行版本组成特点分析

Figure 1 Built-in packages of different Linux distributions图1 不同发行版本默认包含的软件包数量统计

目前，操作系统版本构建主要是从工程实现角度基于历史经验进行软件包的选择和集成，相应的理论分析和支持不足。本文通过依赖关系构建软件包之间的关系图，建立了基于依赖关系的操作系统版本构建模型，并通过对典型Ubuntu发行版本以及对应软件仓库的软件包关系特征进行统计，结合功能分类进行分析，对模型有效性进行验证的同时，总结了几条操作系统版本构建和系统裁剪定制的指导原则。

2 相关工作

软件发行管理最早是由van der Hoek等人[1]提出的，并在2003年提出了基于组件的软件发行管理，指出依赖是软件发行管理的核心[5]。而依赖关系分析在大型软件工程活动中也成为了重要研究热点，覆盖包括软件理解、测试、调试、维护和开发等各个环节[6]。

依赖关系的建模方式主要包括利用结构矩阵、SAT、特性图以及复杂网络等。Sangal等人[7]首次提出了依赖结构矩阵DSM(Dependency Structure Matrix)模型,用于描述软件构件间的依赖关系。Laval等人[8]提出了EDSM(Enriched Dependency Source Matrix)，通过扩展DSM能够判断出软件包之间的循环依赖。类似研究还有设计结构矩阵(Design Structure Matrix)[9]和域映射矩阵(Domain Mapping Matrix)等[11]。在开源操作系统的研究中，Wang等人[11]提出一种分析Linux操作系统发行包依赖关系图的方法，从复杂网络和复杂系统的角度对开源操作系统进行研究，将开源操作系统抽象为软件网络，并且从全局的角度来探索和发现开源操作系统的结构特征与演化规律。叶安达[12]则用图论思想分析源码包之间的依赖关系，研究源码包之间的拓扑关系，给出链式依赖关系的源码包的最佳编译顺序。

从软件包的依赖关系的研究目的来看，目前的研究主要包括：依赖关系改善、依赖关系提取、依赖完整性检测[13]、包管理相关(安装、升级、分发)[14]和探究软件系统生态等。其中改善与解决软件依赖关系的研究主要关注SAT求解与软件包关系管理。例如，顾昊等人[15]对软件包依赖问题进行了分析与归纳，给出了该问题的形式化描述，并提出了一套将软件包依赖问题转变为 SAT问题的基本映射规则，最后结合MiniSAT给出了基本的求解算法。Mancinelli等人[2]则集中于包管理工具,通过探索给定包的依赖需求，执行正确安装所需的所有步骤，自动找到丢失的依赖包，并自动下载安装这些包。

还有部分研究将依赖关系与相应系统软件及其生态相结合。例如，聚焦于依赖关系相关的软件包生态与演进的依赖关系分析[16]，关注理解复杂系统中组件间的关系以更好地管理复杂软件系统[4,17]等。

上述工作主要是以开源操作系统软件包为元素的依赖关系分析，目的是评估系统的兼容性，便于进行软件包的组织管理，很少有直接面向操作系统版本构建和定制裁剪的分析与研究。

在操作系统版本构建和定制裁剪方面，标准化组织与产业界在工程实践中积累了很多经验和行之有效的规则。从系统构建来看，Debootstrap[17]可以用来构建最小系统集合，维持最基本的系统功能运行，开发者可以基于最小系统通过增加软件包及其依赖定制构建版本。从软件包的选择来看，Linux为代表的开源社区将软件包进行分级，例如Ubuntu的Priority属性将软件包分为Required、Important等不同优先级以区分软件包在系统中的必要程度，系统构建时可以根据需要选择不同等级的软件包。Red Hat为此建立一个用来区分软件包兼容程度的分层框架，根据软件包的演化兼容情况划分了4个兼容性等级[18]，指导开发者选择开发依赖的组件，并且在最新的8.0版本中通过引入AppStream对不同功能的包划分管道进行分类选择和管理[19]。总的来看，版本构建领域长久以来工程实践的经验都先于理论分析的指导。

3 基于依赖关系的版本构建模型

操作系统版本构建过程一般是基于一个初始的软件包列表，根据依赖关系把相关的支撑软件包集成，最终构建为一个版本镜像提供给用户进行安装使用。从图论角度来看，软件包及其依赖关系构成了复杂的有向图，通过分析有向图的特性可以在一定程度上了解软件包依赖关系的规律。为更好地分析软件包依赖关系与操作系统版本构建之间的联系，以及操作系统版本构建的过程和原理，本文给出基于依赖关系的操作系统版本构建模型。

依赖关系主要体现在软件包之间，因此下面给出操作系统的软件包依赖关系的定义：

定义1(软件包依赖关系) 依赖关系用一个二元组eij=(vi,vj)表示，即软件包vi依赖软件包vj，等价于如果要安装软件包vi，需要提前或同时安装vj。

在软件包依赖关系模型的基础上，定义依赖关系图模型如定义2所示：

定义2(依赖关系图) 依赖关系图模型是一个二元组G=(V,E)，表示一组软件包节点及其依赖关系,其中V表示软件包节点的集合，E表示V中节点之间的依赖关系的集合。

通过软件包依赖关系和依赖关系图的定义，可以更好地描述操作系统版本和对应的软件仓库。软件仓库通常用于对特定版本或者应用场景所需要的一系列软件包进行组织管理，可以包含操作系统发行版本没有默认集成的各种软件包。软件包仓库定义如定义3所示：

定义3(软件仓库) 用二元组Grespo=(Vall,Eall)表示一个操作系统发行版本对应的软件仓库，其中，Vall表示当前操作系统发行版本支持的所有软件包，Eall表示依赖关系的集合。

为方便论述，将软件包vi依赖的软件包的集合用D(vi)表示，且∀vj∈D(vi)，∃eij=(vi,vj)。与软件仓库模型相比，操作系统特定版本模型多了一组限定条件，其定义如定义4所示：

定义4(操作系统发行版本) 用二元组Gdist=(Vdist,Edist)表示一个操作系统发行版本，其中Vdist表示当前操作系统发行版本中集成的所有软件包，Edist表示依赖关系的集合。

上述4个定义从软件包及其依赖关系角度描述了操作系统发行版本与对应的软件仓库模型。从定义可知Gdist⊆Grespo。由于发行版本必须保证自带的所有软件包都能够正常安装运行，因此很容易得到操作系统发行版本的依赖关系满足完备性。

定理1(发行版本依赖关系完备性) 给定操作系统发行版本Gdist=(Vdist,Edist),∀vi∈Vdist,D(vi)⊂Vdist。

发行版本依赖关系的完备性保证了发行版本自身可以独立完成安装和运行，而不需要额外的软件仓库支持。在开源操作系统发展的早期，由于光盘容量限制，有些发行版本会将操作系统的安装镜像保存在一张光盘中，而将包含其依赖的软件仓库保存在另外一张或者多张光盘中，在这种情况下，发行版本的概念是同时包含了安装光盘和软件仓库光盘。

从上述定义和定理也可以知道，操作系统发行版本的软件包集合根据功能需求的不同，其大小范围也会有差异。其基本的构建过程通常是基于一个初始的基础软件包列表将每个包依赖的软件包都集成进来，如此不断迭代，形成完备的软件包集合。其中比较关键的一步就是根据依赖关系把相关的支撑软件包找到，为了简化流程，将该步骤封装，本文提出软件包依赖析取算法PullDepends。

算法1软件包依赖析取算法PullDepends

输入:vi。//package

输出:V。//a group of packages

PullDepends(vi)

1.V={};

2.Vnext=D(vi);

3.forvjinVnext

4.ifvjnot inV

5.V=V∪{vj};

6.Vnext=Vnext∪D(vj);

7.returnV.

PullDepends的主要思路是通过循环检测获取安装特定软件包所需的所有软件包的集合。输入一个软件包，得到软件包集合D(vi)并遍历，继续得到这些软件包的支撑软件包，最终该算法返回一个软件包的集合V，V为安装特定软件包vi所需要的所有依赖软件包的集合。

该算法是通过Vnext的动态变化避免了递归调用和重复性判断，从算法的执行过程来看，D(vi)实际上是从vi出发的依赖关系树的所有子节点，因此上述算法的效率与该依赖关系树的深度有较大的关联。为此，引入依赖深度的概念。

定义5(依赖深度) 软件包的依赖深度用Depth(vi)表示，Depth(vi)=maxvj{distance(vi,vj)}。

依赖深度可以反映一个软件包在操作系统构建中所处的维度层次，对于版本构建时软件包的选择以及版本构建算法的分析具有重要参考意义。

基于上述软件包依赖析取算法可以实现基于依赖关系的版本构建算法BuildSystem。该算法的输入为一组特定软件包集合V0，这些软件包是构建操作系统版本需要的基础软件包列表集合。V是通过依赖关系获得的所有需要增加的软件包集合，所有V的集合最终组成一个特定的推荐操作系统发行版本S。

算法2版本构建算法BuildSystem

输入:V0。//a group of packages including base packages and specific packages

输出:S。//a specific operating system version

1.V={};

2.forvkinV0

3.Vk=PullDepends(vk);

4.V=V∪Vk;

5.ReturnS=V0∪V.

4 基于依赖关系的版本构建分析系统

第3节中的定义和模型为分析版本构建过程提供了理论依据。本节将以此为基础，以典型操作系统版本和软件仓库的软件包及依赖关系数据为依据，设计和实现一套基于依赖关系的版本构建分析系统，并根据系统分析统计的结果与实际发行版本的组成进行比较，从而分析总结出典型版本构建的规律。

基于依赖关系的版本构建分析系统总体结构如图2所示。该系统主要由数据解析模块、数据分析模块和数据展示模块3部分构成。

Figure 2 Analysis system for distribution building based on dependency relationship图2 基于依赖关系的版本构建分析系统

4.1 数据来源

本文以优麒麟开源操作系统18.04版本为例，选取该版本在仓库中的信息列表，并将数据持久化到软件仓库数据库中。同时选取Ubuntu桌面版和服务器版等典型版本软件包数据作为对比验证的数据来源。

4.2 数据解析模块

数据解析模块实现从外部数据解析导入到本地数据库的过程。为记录描述软件包及依赖关系的数据，本文设计构建了3个数据库表，如表2所示。其中，Package表存放所有的软件包信息，即Vall;Relation表存放提取出来的关系，对应模型中的Eall;Degree表存放解析后的数据，包括出入度等属性。

图3是数据解析的主要流程。首先从优麒麟的软件仓库中提取相关字段并保存到Package表中，该表存储软件仓库中所有软件包信息。然后提取记录中的依赖关系并逐条保存到Relation表中。最后利用python中的networkx库实现已有信息的解析，得到诸如出度、入度和依赖深度等属性并存入Degree表中。对于2个实验操作系统版本，主要提取系统中已有软件包的信息。

Figure 3 Process of dealing dependency realtionship图3 数据解析过程

4.3 数据分析模块与展示模块

本文主要利用统计分析方法，重点对优先级、所属类别属性、出入度和依赖深度等属性和特性进行统计分析和对比验证，并结合模型算法对版本构建过程进行模拟比较。

数据展示模块主要包括数据可视化，并借助自动化脚本且结合已有知识库进行人工分析。其中可视化部分利用python批量生成特定gephi格式文件，并通过Gephi工具与Echart进行结果展示。

5 实验与结果分析

5.1 数据统计

本文统计的系统软件仓库包括60 861个软件包节点和250 608条软件包之间的依赖关系，并以此为基础进行关键特性的统计分析。

5.1.1 基于软件包入度的统计

软件包的入度表示该软件包被其他软件包依赖的次数，入度越大，该软件包被依赖的次数越多。入度在很大程度上也是软件包对其他软件影响程度的一个体现。从版本构建上来说，对其他软件包影响比较大的软件包应该尽量集成到版本中。图4所示是整个软件仓库中软件包的入度总体分布情况。

Figure 4 Statistic graph of in_degree图4 入度区间分布统计图

从图4中可以看出，超过95%的软件包入度都集中于10以下，特别是入度为0的软件包超过了一半，这类软件包通常都是直接面向用户提供服务的软件或者组件。另外有少数软件包的入度特别大，甚至超过1 000，这些通常都是操作系统版本制作需要重点关注和默认集成的。为进一步分析这类软件包的情况，本文统计了入度超过2 000的软件包，如表3所示。

Table 3 Software packages with in_degree more than 2000表3 入度超过2 000的软件包

这些软件包基本上都是系统组成最基础的库或者语言解释支持。如libc6包，它包含了标准C库的共享版本，被操作系统中近1/3的软件包直接依赖，是几乎所有的程序都会使用的标准库。其他大部分软件包为lib库，为系统重要基础软件如C语言编译器、x11等提供函数库，如libstdc++6、libgcc1为源码包gcc-8构建的c++库和gcc支持库。

5.1.2 基于软件包出度的统计

软件包的出度表示该软件包依赖其他软件包的数目，出度大则表示其依赖的软件包多。从软件包的发行维护来说，它依赖的软件包中任意一个出现变动，如版本的变化或者软件包内部函数名的变更等，都可能导致该软件包出现兼容性问题，因此在版本构建和软件包维护过程中应该重点关注。如图5所示为系统软件包出度的分布统计。

Figure 5 Statistic graph of out_degree图5 出度分布统计图

与入度相比而言，出度的分布跨度要小很多，最大出度不超过200，超过98%的软件包的出度在20以内，也间接表明了软件设计的一个要求，软件包内部紧密连接，软件包之间松耦合。从统计来看，出度在0～5的软件包数量比较多，这与开源软件本身提供的开发库相对分散和多样有关，也是当前开源生态建立和维护比较困难的重要因素。

通过对出度超过100的软件包分析发现，出度大的软件包一般都是偏应用层面的软件包，如桌面环境、浏览器的测试组件等，作为非必须安装项，可由用户根据自身需求进行选择。安装这类软件的同时也需要安装大量的依赖软件包，这也是桌面版本通常都比服务器版本的软件包数量多的主要原因。

5.1.3 依赖深度的统计

软件包的出度通常反映其直接依赖的软件包情况，而被依赖软件包的下一级依赖关系则由被依赖软件包进行维护，这种管理方式减少了软件安装时依赖的检测判断，但也给软件的正常执行埋下了隐患。例如某一级软件包的依赖关系出现异常难易被上一级的软件包检测。目前版本构建过程缺少对多级依赖关系的直观衡量，而依赖深度可以作为参考。

表4是依赖深度排名前10的软件包数据统计。目前统计的软件仓库中软件包依赖深度最大不超过20，而且依赖深度大的软件包主要是偏上层应用的软件。

Table 4 Statistics of top 10 dependency depth表4 依赖深度前10的统计

从版本构建来看，某个软件包的依赖深度越大，将其引入版本中时需要构建的软件栈就会越长，会导致版本的管理维护越复杂，特别是软件栈中间组件版本变化对整个系统兼容性的影响也会越大，这也是目前开源发行版本碎片化严重的一个原因。因此，版本的构建应该尽量选择依赖深度较小的软件包。

5.1.4 基于软件包优先级的统计

包的优先级完全由它直接提供给用户的功能决定，优先级高的软件包通常只会被同级别优先级与低级别优先级软件包所依赖，换而言之，优先级高的包将处于依赖关系图中偏底层的位置。如表5所示展示了优麒麟软件仓库中软件包的优先级和在系统中所占比重。

Table 5 Number distribution of software packages with different priorities表5 不同优先级的软件包数量分布

从平均入度来看，Required类型的平均入度远高于其他类型优先级，其次Important优先级的平均入度为151.39，优先级的平均入度也与优先级的划分相对应：优先级越高，入度越高，被依赖的程度越深。同样，平均出度作为当前类别软件包依赖其他软件包的平均程度，也表明Required类型软件包作为必备软件包在系统中一般都是被依赖的角色。在操作系统版本构建中，Required和Important类型优先级的软件包通常需要首先被开发者考虑。

5.2 典型系统印证

本文选择Ubuntu-18.04.5-live-server-amd64(以下简称服务器版本)和Ubuntu-18.04.5-desktop-amd64(以下简称桌面版本)2个版本进行验证。

5.2.1 依赖出入度与版本构建关系

图6所示为不同范围入度的软件包系统中所占比重。从图6中可以看到，操作系统中软件包的入度从0～50到大于1 000都有分布，并且系统中入度小于50的软件包占所有软件包80%左右，这类软件包即使入度不是很高，但也为系统的正常运行提供重要支撑。

Figure 6 Proportion of software packages in different in_degree intervals in systems图6 不同入度区间软件包数量在系统中所占比重

在出入度为0的软件包中，服务器版本含有4个，包括崩溃检测报告功能的相关脚本、bash的补充工具、krb5的语言包和ncurses-base。桌面版本中额外多了字体、主题等相关的软件包。因此，单个软件包的入度低并不能说明该软件包对系统不重要。在入度超过1 000的13个软件包中，与软件仓库相比，桌面版本缺少2个编程类库包，服务器版本缺少3个编程语言类软件包和qt5核心软件包。语言类软件包如python、ruby等由于本身广泛的使用而有着极高的出入度，但对于构建一个基础系统来说并不是必需考虑的软件包。

结论1单个软件包的出入度不能作为衡量系统版本能否正常运行的指标，但高入度的软件包依旧是版本构建需要重点关注的。入度为0的软件包通常是直接向用户提供功能的组件，在系统构建时可以根据功能需求进行选择。

5.2.2 优先级分类与版本构建关系

图7展示了2个实验版本不同优先级下的软件包数量。2个系统中，Required、Important和Standard 3种优先级的软件包数量与软件仓库一致，系统中软件包数量的差异主要体现在Optional与Extra中软件包的不同。在服务器版本中，Extra的软件包主要与云实例功能模块相关。Optional中的软件包主要有lib和python 2类软件包，其中lib主要是优先级高的软件包支持库，python类别软件包则提供了核心组件的python接口和功能模块。这2类软件包为系统中必要功能模块提供支持，需要根据实际情况进行选择。

Figure 7 Classification of software packages with different version图7 不同版本的软件包分类

结论2在系统版本构建过程中，根据系统基础功能需求，优先级为Required、Important和Standard的软件包通常会加入版本，其他属性的软件包可以根据需求功能自由选择。如果是做精简定制裁剪，一些常用的命令工具则可以根据情况裁剪，因此针对系统裁剪需要提供更详细的分类标记。

6 结束语

本文从依赖关系角度对操作系统版本构建过程建立了基础模型，并以优麒麟18.04软件仓库的实际数据和Ubuntu典型服务器及桌面2个版本的实际数据为参考，进行了软件包依赖关系出入度、优先级和依赖深度等属性的统计和对比验证，总结给出了出入度、优先级等属性对版本构建的影响规律，对于操作系统研发和版本构建人员具有一定的指导意义，也为从理论上进行版本的自动分析和大规模软件包的属性及标记分析奠定了基础。

从实际分析来看，软件包的出入度在一定程度上依赖于软件包开发和维护人员的经验，可能存在冗余依赖或者缺少依赖的问题，后续将结合依赖深度和优先级等属性和标记，对软件包的属性标记规律和准确性进行挖掘分析，并结合典型软件包及CentOS等更多典型操作系统版本的演化进行数据分析，为操作系统版本构建和裁剪、软件兼容性评估以及故障关联性分析等提供理论和数据支撑。