基于面向服务架构的工业软件的任务调度算法

宁明超，张俊勃，陈戈

（华南理工大学 电力学院，广州 510641）

0 引言

随着信息技术的发展及其与工业领域的融合，各类工业软件已经广泛用于工业生产过程的控制和管理［1］。现有工业软件大多采用面向服务架构（Service-Oriented Architecture，SOA），软件被拆分为多个粗粒度、松耦合的服务，服务间通过网络通信［2］。基于SOA 的软件收到用户请求后，相应服务实例会对请求进行处理，完成处理后向用户返回结果。本文将每个请求的处理过程称为一个任务。

与大多数商业软件相比，工业软件对实时性和可靠性的要求非常高［3］。实时性指软件对请求作出迅速响应的能力；可靠性指软件在规定时间内完成相应任务的能力，与任务的按时完成率呈正相关。任务的完成过程需要占用服务实例的计算资源，包括中央处理器（Central Processing Unit，CPU）、内存、磁盘输入输出（Input and Output，IO）、网络带宽［4］。然而，工业软件中通常存在大量待处理任务，而服务实例的可用计算资源有限，无法同时处理所有任务，导致部分任务难以被快速处理，甚至不能按时完成，造成经济损失甚至安全事故［5］。因此，设计一种高效的任务调度方法将任务合理地分配给服务实例处理，是保障工业软件实时性和可靠性的重要需求［6］。

任务调度方法需要结合应用场景的特点设计。在工业场景中，不同任务的重要程度对工业系统的影响不同［7］。软件需要优先处理重要任务，同时尽可能多地处理非重要任务。因此，重要程度是任务的属性之一，需要设计合适的方法进行评估。而任务的处理需要占用服务实例的部分计算资源，这就是任务的资源需求量属性。此外，任务还具有到达时间、处理时长和截止时间的属性，而截止时间限制了任务的完成时间。例如，在输电线路故障处理场景中［8］，线路可能由于绝缘老化、鸟兽跨接、气象条件等因素突然发生短路故障（到达时间）；不同故障对电力系统危害程度不同（重要程度）；故障处理软件需要在规定时间内尽快完成故障处理（截止时间）。在工厂生产管理系统中［9］，生产计划根据销售订单的到来而制定（到达时间），不同生产计划的重要程度不同（重要程度），生产计划的执行有截止时间限制，工厂必须在订单规定的交货时间之前完成相应产品的生产（截止时间）。此外，故障处理和生产计划的制定都需要在一段时间内占用服务实例的部分计算资源（处理时长、资源需求量）。

上述部分属性还具有随机性和时变性，属性间存在一定的耦合关系。首先，任务的到达时间是随机的，同一任务在多次处理过程中使用的资源量和处理时长会在一定范围内随机波动；其次，任务的重要程度随等待时间的增加而变高；再次，任务在临近截止时间时，重要程度会大幅增加。例如，在上述输电线路故障处理场景与工厂生产管理系统中，故障发生时间和销售订单的到达时间随机，且故障处理任务和订单处理任务的重要程度都随处理时间的增加而变高，在临近截止时间时会大幅增加。

通过上述分析可知，工业软件的任务具有多重属性，部分属性具有随机性、时变性且相互耦合。基于这些任务特点，可以对任务调度方法进行设计。针对工业软件的实时性要求，任务调度方法也需要具备实时性，保证随机到来的新任务能被快速分配给服务实例处理；同时，为满足工业软件的可靠性要求，每个服务需要设置多个实例，且每个服务实例应能并行处理多项任务。因此，是否具有实时性，以及服务实例的处理能力也是任务调度方法需要考虑的因素，本文将从这两个角度出发，分析现有任务调度方法的适用性。

是否具有实时性指调度方法能否实时作出决策，如果能则称为在线方法，否则称为离线方法。离线方法适用于任务信息在调度前已经确定的场景。例如，文献［10］中提出一种考虑截止时间和时隙可用性约束的离线方法，文献［11］中提出一种考虑截止时间约束的基于蚁群优化算法的离线方法，均实现了对非实时任务的高效调度。在线方法适用于任务不断到来的场景，主要有基于优化算法和基于优先级排序的两种解决思路：前者将调度问题建模为最优化问题，从解空间中搜索最优解，根据最优解分配任务［12-13］；后者只需计算所有待处理任务的优先级并排序，根据优先级顺序调度任务［14-15］。由于求解优化问题的计算量较大，故前者的调度决策耗时较长；而优先级通常由函数表达式计算得到，计算量较小，故后者的调度决策耗时较短。因此，基于优先级排序的方法应用更广泛，其中常用的方法有先来先服务（First Come First Serve，FCFS）方法［16-17］、最早截止时间优先（Earliest Deadline First，EDF）方法［18-19］、最小松弛度优先（Least Laxity First，LLF）方法［20-21］和固定优先级调度（Fixed Priority Scheduling，FPS）方法［22］等。在工业软件中，任务随机到来，数量多且具有截止时间限制，因此适合采用基于优先级排序的在线调度方法。

按照服务实例的处理能力不同，可将现有方法分为单线程和多线程方法。单线程方法中的每个服务实例只能同时处理一个任务，而多线程方法中的每个服务实例可以同时处理多个任务。在单线程方法的研究中，文献［15］中考虑的云服务平台提供多种类型的服务实例，服务实例在任何时刻最多只能执行一个任务；文献［23］中提出了一种云计算服务的调度算法，该算法选择期望效用最高的待处理任务进行处理，只有在当前任务处理完成或被丢弃时，才能处理下一个任务。在多线程方法的研究中，文献［9］中利用服务容量衡量服务实例的处理能力，在满足容量约束的条件下，每个服务实例可以同时处理多个任务；文献［24］中研究了基础设施即服务（Infrastructure as a Service，IaaS）系统的任务调度问题，该场景中每台服务器是一个服务实例，可以同时承载多台虚拟机任务，因此每个服务实例可以同时处理多个任务。显然，在具有大量任务且任务有截止时间限制的工业场景中，应选择能实现任务并行处理的多线程方法。

综上，工业软件的任务调度问题具有以下特点：1）具有重要程度属性，重要程度具有时变性且与截止时间相互耦合；2）实时性要求高，需要对任务进行实时调度；3）可靠性要求高，服务实例应具有并行处理多任务能力。在现有的任务调度方法中，文献［10-11］中的方法属于离线方法，不适用于任务实时到达的工业场景，不能满足实时性要求；文献［12-13］中的方法虽然为在线方法，但由于采用优化方法求解调度问题，调度决策耗时较长，也不能满足高实时性要求；文献［15，23］中的方法属于单线程方法，每个服务实例不具备并行处理任务能力，不能满足高可靠性要求；同时，现有方法都没有融合工业场景的特点，没有考虑任务重要程度的时变性以及重要程度与截止时间的耦合。由此可见，现有方法都不能同时满足上述三个特点。

因此，本文同时考虑了工业软件任务调度问题的三个特点并进行建模，主要工作包括：建立任务重要程度模型，设计用于评估任务重要程度的效用函数；建立任务模型；建立服务实例具有并行处理能力的资源模型。在此基础上，本文提出了一种适用于基于SOA 的工业软件的任务调度算法——基于重要程度排序的调度算法（Importance Ranking-based Scheduling Algorithm，IRSA）。该算法属于基于优先级排序的在线的多线程方法，根据重要程度对任务进行排序，按照重要程度递减的顺序将任务分配给服务实例处理。为提升IRSA 的调度效率，本文设计了资源预留机制［12］，当所有服务实例的资源都不足以处理当前效用值最高的任务时，将某一服务实例未来可用的资源预留给该任务。考虑到有些任务在任何情况下都需要被立即处理，将这类任务称为紧急任务，相应地将非紧急任务称为普通任务。为保障紧急任务在所有服务实例的资源不足时仍然可以被立即处理，本文设计了抢占式调度机制［25］，通过抢占其他普通任务的资源，使紧急任务得到优先处理。同时，本文采用Golang 实现了IRSA，并在基于SOA 的电网调度控制软件中对其进行仿真测试，实验结果表明，IRSA 可以实现高效的任务调度，在多项性能指标上显著优于其他对比算法。

1 问题建模

本章对工业软件的任务调度问题进行建模，包括任务模型、资源模型和任务重要程度模型。为定量评价调度算法的性能，还提出了性能评估模型。

1.1 任务模型

将系统中正在处理和等待处理的任务表示为集合X={x1，x2，…，xp}，其中：p是任务的数量，随时间动态变化。将X中的任务xi建模为xi={ai，di，Ii}，其中：ai表示系统接收到xi的时间；di表示xi的截止时间，系统需要在di之前完成对xi的处理；Ii表示xi的固有重要程度，与xi对应业务的重要程度相关，一般根据专家经验或知识给定。

1.2 资源模型

资源需求量是任务的一种关键属性，它指任务在处理过程中需要消耗的服务实例的计算资源量。将xi消耗的资源量表示为ri（kk=1，2，3，4），分别表示CPU、内存、磁盘IO 和网络带宽。所有能处理xi的服务实例组成了xi的服务实例池，表示为SP(xi)。对于任务x1和x2，若SP(x1)=SP(x2)，则称x1与x2的类型相同。服务实例分为主实例和备用实例；当任务较少、主实例的剩余资源充足时，任务会被分配到主实例处理；当任务较多、主实例的剩余资源不足以处理紧急任务时，紧急任务会被分配到备用实例处理。

与SP(xi)相关的参数定义如下：sxi，m表示SP(xi)中第m个服务实例，m=1，2，…，|SP(xi)|，其中：|SP(xi)|是所有能处理xi的服 务实例的数量；R(sxi，m，k)表示sxi，m的第k类资源可用量。若x1，x2，…，xn与xi的类型相同，在满足式（1）所示的服务实例资源约束时，sxi，m可以同时处理这n个任务。

假设SP(xi)中所有服务实例的可用资源量和处理任务的能力都相同，则它们处理xi的时间相同。

通常将所有服务实例部署在多台物理机上，将第l台物理机表示为PMl，与PMl相关的参数定义如下：sPMl，j表示部署在PMl上的第j个服务实例，j=1，2，…，u，u是部署在PMl上的服务实例数量；R(PMl，k)表示PMl的第k类资源可用量。

假设sxi，m部署在PMl上，由于服务实例使用的资源都来源于物理机，将任务xi分配给服务实例sxi，m处理时，除了需要满足式（1）外，还需要满足式（2）所示的物理机资源约束：

1.3 任务的重要程度模型

在工业软件中，不同任务的重要程度不同。任务的重要程度越高，错过截止时间对工业系统的影响越大，越需要尽早处理。任务的重要程度主要与固有重要程度和松弛度相关，本文设计了包含这两个因素的效用函数，采用效用值表示重要程度。任务的效用值越大，则重要程度越高。

1）固有重要程度。

固有重要程度是任务的固定属性，与对应业务的重要程度相关，通常根据专家经验或知识给定。例如，在工厂生产管理系统中，对于查询设备信息和下达生产计划两项业务，后者比前者更重要，对应任务的固有重要程度更高。

将任务xi的固有重要程度表示为I(xi)，取值为［1，5］的整数，数值越大表示固有重要程度越高。本文将固有重要程度为5 的任务称为重要任务，该类任务属于紧急任务，需要被优先快速处理。

2）松弛度。

任务的松弛度指任务在满足截止时间的条件下可以延迟处理的最大时间。任务xi的松弛度计算如下：

其中：deadline(xi)表示xi的截止时间；duration(xi)表示xi的预估处理时长；timenow表示当前时间。由式（3）可知，松弛度随着时间的推移而减小。松弛度为非负数时，任务可以延迟处理，且松弛度越小，任务越需要被尽快处理；松弛度为负数时，任务错过截止时间。本文将松弛度小于阈值的任务也归类为紧急任务。

3）效用函数。

任务的重要程度由上述两个因素共同决定，且与固有重要程度呈正相关，与松弛度呈负相关。其中，松弛度为负数的任务已经错过截止时间，可以认为它的重要程度不再随松弛度的减小而增加。根据这些关系，本文设计了用于评估任务重要程度的加权效用函数，如式（4）所示：

其中：utility(xi)表示xi的效用值，代表xi的重要程度；w1、w2为权重系数，满足式（5）的关系；f1(xi)和f2(xi)分别表示固有重要程度和松弛度对任务重要程度的影响，分母的作用是对任务的固有重要程度进行归一化。当松弛度laxity(xi)为非负数且较大时，任务具有较大的处理时间裕度，f2(xi)的值较小；当松弛度不断减小趋向于0 时，任务离截止时间越来越近，f2(xi)的值逐渐增加并趋向于1，且增加的速度不断变快；当松弛度为负数时，任务已经错过截止时间，f2(xi)的值恒为1。由于f2(xi)∈(0，1]，不需要进行归一化。

1.4 性能评估模型

在工业软件中，重要任务对系统的影响较大，而非重要任务对系统的影响较小。为提高软件可靠性，一般要求优先处理重要任务，同时尽可能多地处理非重要任务。因此，评估调度算法的性能时，首要关注的是重要任务的处理情况，其次是非重要任务的处理情况。其中，处理情况包括任务的按时完成情况和等待时间。此外，还需要关注所有任务的总体处理情况，一般以响应时间作为依据。本文引入5 种指标评估调度算法的性能表现。其中：M1、M3用于评价算法对重要任务的分配效率，M2、M4用于评价算法对非重要任务的分配效率，M5用于评价算法对所有任务的总体分配合理性。所有指标均假设被调度任务的数量是n。

1）M1：重要任务的按时完成比例，即在截止时间之前完成的重要任务占所有重要任务的比例。计算公式如下：

其中：N1（xi）表示xi是否为按时完成的重要任务；N2(xi)表示xi是否为重要任务；finishAt(xi)表示xi的完成时间。

2）M2：非重要任务的按时完成比例，即在截止时间之前完成的非重要任务占所有任务的比例。计算公式如下：

其中：N3(xi)表示xi是否为按时完成的非重要任务，N4（xi）表示xi是否为非重要任务。

3）M3：重要任务的平均等待时间，即所有重要任务的等待时间的平均值。计算公式如下：

其中：WT1(xi)表示重要任务xi的等待时间；startAt(xi)表示xi的开始处理时间；arriveAt(xi)表示xi的到达时间。

4）M4：非重要任务的平均等待时间，即所有非重要任务的等待时间的平均值。计算公式如下：

其中：WT2(xi)表示非重要任务xi的等待时间。

5）M5：任务的平均响应时间，即所有任务的响应时间的平均值。计算公式如下：

2 IRSA设计

本文提出一种适用于工业场景的调度器框架，以及基于重要程度排序的调度算法（IRSA），并设计了资源预留机制和抢占式调度机制以提高算法的调度效率。

2.1 调度器框架

调度器框架如图1 所示。调度器具有任务分配功能和辅助功能。任务分配功能由算法1 实现，通过正常分配、资源预留和抢占式调度三个子算法（算法2～4）的协同配合将任务分配给服务实例处理。算法1～4 共同组成了IRSA，它们的详细逻辑将在2.2 节介绍。辅助功能负责任务分配过程的相关辅助工作，主要包括任务预处理、任务池更新、信息监控，具体如下。

图1 调度器框架Fig.1 Framework of scheduler

1）任务预处理。调度器在接收到任务后，根据式（4）计算任务的效用值，并将其存入任务池。

2）任务池更新。由于任务池中任务的效用值会随时间动态变化，调度器需要定时更新它们的效用值信息。

3）信息监控。调度器需要监控各种信息来作出任务分配决策，包括服务实例的健康状态信息和资源信息、物理机的资源信息等。

2.2 IRSA

在工业软件中，任务可以分为普通任务和紧急任务，服务实例可以分为主实例和备用实例。考虑到紧急任务的到来具有随机性且需要被尽快处理，本文规定备用实例只用于处理紧急任务，制定了以下任务分配原则：

1）将普通任务只分配给主实例处理，若主实例的剩余资源不足，则延迟对它们的处理。

2）将紧急任务分配给主实例处理，若主实例的剩余资源不足，则分配给备用实例处理。若备用实例的剩余资源也不足，则抢占主实例中普通任务所占用的资源，使该主实例满足紧急任务的资源需求。

根据上述任务分配原则，本文提出了一种适用于2.1 节所提框架的在线调度算法（IRSA），如算法1 所示。其中：TP表示任务池，用于存放所有待分配的任务；WP表示等待任务池，用于存放所有分配失败、等待再次分配的任务。随着时间的推移，WP中任务由于松弛度不断减小，可能由普通任务变成紧急任务。因此，调度器需要定时检测WP中是否有紧急任务出现，如果有，则将它们转移到TP中，防止这些任务因长时间存放在WP中而错过截止时间。

算法1 IRSA。

2.2.1 正常分配算法

在正常分配过程中，调度器将任务xi与SP(xi)中的主实例进行资源匹配，判断服务实例的资源是否满足需求，如果匹配成功则将xi分配给该主实例处理。如果匹配失败且xi是紧急任务，则将它与SP（xi）中的备用实例进行资源匹配；如果匹配成功则分配给该备用实例处理，否则跳过该任务的分配，任务xi的正常分配过程结束。

在分配的过程中，需要保证主实例之间的负载均衡，因此调度器会将xi分配给剩余资源最多的服务实例处理。然而，xi的处理需要使用四类资源（CPU、内存、磁盘IO、网络带宽），且每类资源的需求量通常不同。因此，调度器需要先计算xi所需各类资源量占服务实例总资源量的比例，其中占比最高的资源称为主导资源，然后将xi分配给主导资源剩余最多的服务实例处理。

当所有主实例的资源都不足时，紧急任务才会被分配给备用实例处理。为保证资源需求量较大的紧急任务可以被成功分配给备用实例处理，调度器不对备用实例做负载均衡，而是使用尽可能少的备用实例去处理紧急任务。例如，SP（xi）中有s1和s2两个备用实例，调度器通常将紧急任务xi分配给s1，当s1的资源不足时才将xi分配给s2。

正常分配算法的具体逻辑如算法2 所示，其中SI表示服务实例集合，用于临时存放满足要求的服务实例信息。

算法2 正常分配算法。

2.2.2 资源预留算法

WP用于存放暂时没有足够资源去处理的任务。考虑到TP中如果存在一些效用值更低且资源需求量更少的任务，则这些任务可能会先被分配给服务实例处理，导致WP中高效用值的任务不能得到优先处理。为避免这一情况发生，本文设计了资源预留算法，为WP中高效用值的任务预留服务实例，被预留的实例不能用于处理其他非预留任务，直到预留任务被分配出去。

为保证高效用值的任务被优先处理，同时不影响紧急任务的处理，任务按效用值递减的顺序被预留给实例，其中预留实例都属于主实例，且每个实例只能被预留给一个任务。例如，假设WP中x1、x2、x3是按效用值递减排序的同一类型的任务，即SP（x1）=SP（x2）=SP（x3），且SP（x1）中有两个主实例s1和s2，则只有x1和x2可以被预留给实例s1和s2。

在资源预留过程中，调度器会根据任务所需资源、服务实例正在处理的任务资源量、开始处理时间和预估处理时长来分配预留实例，将预估最短时间内可以满足任务需求的主实例预留给对应任务。例如，假设x1有两个主实例s1和s2，如果预估s1的剩余资源在5 s 后可以满足x1的需求，预估s2的剩余资源在10 s 后可以满足x1的需求，则将s1预留给x1。

资源预留算法的具体逻辑如算法3 所示，其中TS表示任务集合，用于临时存放任务信息；length表示可以分配预留实例的任务数量。

算法3 资源预留算法。

2.2.3 抢占式调度算法

为保证紧急任务能被尽早处理，当SP（xi）中所有服务实例的资源都不能满足紧急任务xi的处理需求时，调度器将进行抢占式调度，终止SP（x）i中某个主实例对普通任务的处理，抢占这些任务所占用的资源，使xi能被分配给该主实例处理。

任务在处理过程中需要占用一定资源，且被终止任务在下一次分配给服务实例时，需要重新处理。因此，调度器终止任务会产生一定代价，需要对终止任务的代价进行评估，优先选择代价低的抢占方式。例如，调度器执行抢占式调度时需要终止主实例sq中的普通任务xj，代价为：

其中：rjk为xj消耗的资源量；startAt(xj)表示xj的开始处理时间；bk为权重系数，根据实际需要确定。

为满足xi的资源需求，sq可能需要终止多个任务。为尽可能降低终止任务的代价，在满足xi的资源需求条件下，调度器首先需要找出使sq终止代价总和最小的任务组合；然后，对每个主实例的最小代价和进行比较，得到代价和最小的服务实例smin-cost；最后，终止该实例中代价和最小的任务，并将xi分配给smin-cost处理。

抢占式调度算法的具体逻辑如算法4 所示，其中SC用于存放每个任务的终止代价。

算法4 抢占式调度算法。

3 实验与结果分析

本文在电力系统调控业务场景中对IRSA 的有效性进行了测试。首先验证了2.2 节中三种任务分配流程（正常分配、资源预留、抢占式调度）的正确性；然后在不同任务到达率下，对IRSA 以及目前广泛应用的FCFS 算法、EDF 算法、LLF 算法和FPS 算法的性能表现进行了测试，验证IRSA 的优越性。其中，FPS 算法中任务的优先级为固有重要程度。所有算法均采用Golang 编码，运行环境为：Intel Core i7-7700HQ@2.80 GHz 四核CPU、8GB RAM 和Windows 10 操作系统。

3.1 案例背景

电力系统是负责电能生产、输送、分配的系统，它的安全稳定运行对工业生产制造和人们日常生活至关重要。电网调度控制软件是应用于该场景的一类工业软件，主要负责计划检修、电网调度恢复和查询业务。其中：计划检修业务是指按照停电检修单对电网设备进行检修操作；电网调度恢复业务是指当电网发生设备故障或异常等事故时，调度员对电网进行调度恢复的过程；查询业务是指各种数据查询操作，例如查询开关状态、全网电压分布情况等。

上述三类业务具有以下特征：1）业务发生的时间随机，停电检修单的到来、事故的发生以及查询操作都是随机的；2）业务具有截止时间限制，例如，事故发生后，调度员需要在规定时间内采取有效措施进行调度恢复；3）业务具有重要程度属性，例如，被检修设备的重要性越高，检修单的重要程度也越高；4）业务的重要程度随等待时间的增加而变高，例如，事故等待处理的时间越长，危害性越大，重要程度也会越高。

电力系统中的各种应用软件由不同厂家开发，软件之间一般以服务的方式进行交互。考虑到电网调度控制软件不仅需要与其他软件进行大量交互，例如数据采集与监控系统、电网高级应用软件等，同时需要具备较高的可靠性和可扩展性，该类软件适合采用SOA 架构进行设计。本文考虑的电网调度控制软件由7 个服务组成，各服务对应的业务功能如下：服务A 负责对停电检修单进行审批操作，审批通过后生成操作票，其中操作票是指检修设备的详细操作指令；服务B 负责对操作票进行校核操作，并将通过校核的操作票下发给厂站执行；服务C 负责对数据采集与监控系统传输过来的报文进行解析、识别和校核，确认是否发生跳闸事故；服务D 负责对故障进行诊断和评估；服务E 负责通知配电网调度员进行转电操作；服务F 负责通知变电站运维人员进行现场检查；服务G 负责查询开关状态和全网电压分布情况等。

3.2 案例设计

本案例考虑14 类任务，覆盖计划检修、电网调度恢复和查询操作三种业务。本文为服务A、B、C、D 分别设置3 个服务实例，为服务E、F、G 分别设置2 个服务实例，其中每个服务都有1 个备用实例，其余实例为主实例，服务实例均部署在物理机PM1、PM2上。任务和服务实例的具体情况如图2所示。其中，每个服务实例的可用资源量如下：CPU 为2 核，内存为1 GB，磁盘IO 是50 MB/s，网络带宽是10 Mb/s。每台物理机的可用资源量如下：CPU 为12 核，内存为6 GB，磁盘IO 是400 MB/s，网络带宽是80 Mb/s。

图2 软件的任务和服务实例情况Fig.2 Tasks and service instances in software

由于运行环境的影响，同一类任务（例如图2 中的A_1）在多次处理过程中，处理时长和消耗的资源量可能会发生小范围波动。为反映这种波动情况，任务的预估处理时长、所需资源量等参数均为服从均匀分布的随机变量。通过调节每100 ms 生成一个任务的概率为10%、20%、…、80%，随机生成8 组任务，编号为1、2、…、8，各组任务的到达时间均为0～80 s，平均每秒到达任务数量为1.06、2.01、3.03、3.95、5.09、5.84、6.84、7.99。

为便于分析，按照时间顺序，将各组内任务的名称分别设置为t1、t2、…。根据专家经验，将式（4）效用函数的权重系数设置为w1=0.8，w2=0.2；将式（17）代价评估函数的权重系数设置为b1=0.32，b2=0.28，b3=0.2，b4=0.2。

3.3 仿真结果与分析

使用IRSA 对随机生成的8 组任务进行调度，根据调度结果，可绘制出每个服务实例的资源使用时序图。如图3 所示为IRSA 对第6 组任务调度得到的服务C 的三个实例的资源使用时序图，由于篇幅限制，只展示0～60 s 的情况。其中，每个时序图都包含4 个子图，分别表示4 类资源（CPU、内存、磁盘IO、网络带宽）的使用情况。每个子图的横轴表示时间，纵轴表示资源量，其最大刻度与服务实例的可用资源量相等。子图中的每个矩形表示一个任务的处理过程，矩形的长度表示任务的处理时间，宽度表示资源使用量。为了区分不同任务的处理过程，相邻的矩形采用不同灰度标识。为显示服务实例的资源使用情况，一个矩形可能被拆分为多个矩形，例如图3（a）中的t20。在这种表示方法下，图中空白区域表示服务实例的剩余资源量。下面基于图3 介绍三种任务的分配过程，其中：T1=3.35 s；T2=5.38 s；T3=6.60 s；任务t20、t94、t116、t142、t170、t32用H～M 表示。

图3 服务C的3个实例的资源使用时序图Fig.3 Sequence diagrams of resource usage for 3 instances in service C

在正常分配过程中，调度器根据负载均衡原则将任务尽可能均匀地分配给主实例处理。例如，任务t20在3.35 s 到来，它的主导资源是磁盘IO，由于该时刻sC_1的剩余磁盘IO比sC_2多，且sC_1的其他资源都可以满足t20的需求，因此将它分配给sC_1处理。备用实例主要用于缓解主实例在负载高峰期的压力，只有在主实例的资源占用率都很高且无法处理紧急任务时，紧急任务才会被分配给备用实例处理，例如，sC_3只在部分时段内处理任务，其他时间都处于空闲状态。主实例sC_1和sC_2在大部分时间的资源使用量都比较接近，且都明显高于备用实例sC_3的资源使用量，说明负载在主实例间的分配是比较均衡的。

以任务t32为例介绍资源预留过程，t32在5.38 s 到来，从图3（a）、（b）中可以看出，此时sC_1和sC_2的剩余内存都无法满足该任务的需求。由于t32是普通任务，调度器预估sC_2在更短时间内能够满足该任务的资源需求，因此将sC_2预留给t32。从5.38 s 到6.60 s，sC_2被预留给t32，其他任务不能分配给sC_2处理。在6.60 s 时，sC_2的剩余资源可以满足任务t32的需求，因此将该任务分配给sC_2处理。

在抢占式调度过程中，调度器需要终止一些普通任务，以保证紧急任务能够按时完成。在图3（a）、（b）中，虚线框表示被终止的任务。例如，紧急任务t116在18.29 s 到来，此时服务C 的3 个实例的剩余资源都无法满足该任务的需求，因此调度器终止sC_1对普通任务t94的处理，并将t116分配给sC_1处理。同理，调度器在28.26 s 终止了sC_1对普通任务t142的处理，并将紧急任务t170分配给sC_1处理。

对于随机生成的8 组任务，应用IRSA 和4 种对比算法进行调度，得到各类性能指标如图4 所示。

图4 不同算法的性能比较Fig.4 Performance comparison of different algorithms

由图4 可知，在第1～4 组任务中，即每秒任务到达数量较少时，服务实例的资源在绝大多数时间都可以同时满足所有待处理任务的需求。因此，除了FCFS 在第3、4 组中M1为89.58%和79.69%，所有算法在5 个指标上的表现基本相同，任务的按时完成率都大于96%。

当每秒任务到达数量从每秒3.95 增加到5.09 时，即从第4 组到第5 组任务，FCFS、EDF 和LLF的M1分别降低了55.88%、65.48% 和64.29%，而IRSA 只降低 了1.19%；FCFS、EDF 和LLF的M2分别降低了74.62%、72.05% 和72.89%，而IRSA 只降低了8.24%；由于FPS 基于任务的重要程度进行排序，优先分配重要任务，它的M1只降低了1.19%，然而FPS 延迟了对非重要任务的处理，导致M2降低了34.60%。

在第5～8 组任务中，即每秒任务到达数量较多时，服务实例的资源难以同时满足所有待处理任务的需求，IRSA 的性能表现显著优于FCFS、EDF 和LLF，且随着任务到达率的增加，IRSA 在各指标上的优势都越来越明显。本文根据工业软件中任务的特点，在1.3 节中建立了任务重要程度模型，将固有重要程度为5 的任务和松弛度小于阈值的任务都归类为紧急任务。由于IRSA 根据效用值递减的顺序对任务进行调度，非重要任务在松弛度小于阈值之前就已经得到处理，避免了大量非重要任务转变为紧急任务，因此IRSA 在优先保障重要任务被尽快处理的同时，也使非重要任务得到了更快的处理，有效提升了任务的总体响应速度。

而FPS 始终优先分配重要任务，使大量非重要任务长期处于等待状态，直到松弛度小于阈值时转变为紧急任务。因此，在第5～8 组任务中，FPS在M2、M4和M5上的表现显著差于IRSA；在第7～8 组任务中，重要任务的数量较多，服务实例难以及时处理大部分重要任务，因此FPS在M1和M3上的表现显著差于IRSA。

当每秒任务到达数量增至7.99 时，即第8 组任务中，所有算法的性能表现如表1 所示。

表1 第8组任务的调度结果对比Tab.1 Comparison of scheduling results for 8th group of tasks

由表1 可知，相较于对比算法，IRSA的M1提高了14.40～88.80 个百分点，M2提高了38.96～55.66 个百分点，M3减少了55.62%～97.93%，M4减少了63.92%～73.70%，M5即平均响应时间分别减少了55.83%～61.27%。这说明在任务到达率很高时，4 种对比算法的性能明显下降，而IRSA 依然可以对任务进行合理高效的调度，在优先保障重要任务被尽快处理的同时，兼顾非重要任务的按时完成，显著提高了任务的响应速度。

4 结语

针对基于SOA 的工业软件的任务调度问题，本文设计了一个用于评估任务重要程度的效用函数，提出了IRSA。IRSA 根据重要程度对所有任务排序，按重要程度递减的顺序依次将任务分配给服务实例处理，同时引入了资源预留机制和抢占式调度机制，在提高任务的处理效率的同时保障了紧急任务得到优先快速处理。

实验结果表明，IRSA 的各项指标均显著优于目前广泛应用的FCFS、EDF、LLF 和FPS 算法，尤其是在任务到达率较高时，IRSA 能够大幅降低重要任务的等待时间，保障绝大部分重要任务被按时完成，同时使非重要任务得到更快的处理，显著提升了任务的总体响应速度。关于未来的研究工作，还有一些问题有待进一步解决，包括寻找效用函数的最优权重值，估计任务的处理时长和所需资源量等。