基于面向服务架构的工业软件的任务调度算法_宁明超 (1).pdf

2023 03 10计算机应用,Journal of Computer Applications2023,43(3):885-893ISSN 10019081CODEN JYIIDUhttp：/基于面向服务架构的工业软件的任务调度算法宁明超，张俊勃*，陈戈（华南理工大学 电力学院，广州 510641）（通信作者电子邮箱）摘要：针对采用面向服务架构（SOA）的工业软件的任务调度问题，考虑任务的多重属性，属性的随机性、时变性及耦合关系，以及调度过程实时性和处理任务并行性的要求，提出一种适用于基于SOA的工业软件的任务调度算法。首先，对任务调度问题进行建模，并设计用于评估任务重要程度的效用函数；然后，提出基于重要程度排序的调度算法（IRSA），按照重要程度递减的顺序对任务进行调度；最后，设计资源预留机制和抢占式调度机制，以提高IRSA的调度效率。实验结果表明，与先来先服务（FCFS）、最早截止时间优先（EDF）、最小松弛度优先（LLF）、固定优先级调度（FPS）这四种在线调度算法相比，当每秒任务到达数量为 7.99 时，IRSA 使任务的平均响应时间减少 55.83%61.27%，且在所有性能指标上均具有明显优势，能够实现对基于SOA的工业软件的高效任务调度。关键词：面向服务架构；工业软件；任务调度；效用函数；资源预留机制；抢占式调度机制中图分类号：TP311 文献标志码：ATask scheduling algorithm for service-oriented architecture-based industrial softwareNING Mingchao，ZHANG Junbo*，CHEN Ge（School of Electric Power Engineering，South China University of Technology，Guangzhou Guangdong 510641，China）Abstract:To address the task scheduling problem of industrial software using Service-Oriented Architecture（SOA），a task scheduling algorithm for SOA-based industrial software was proposed，considering the multiple attributes of tasks，the randomness，time-varying and coupling relationships of attributes，and the requirements of real-time scheduling and parallel processing of tasks.Firstly，the task scheduling problem was modeled，and a utility function was designed to evaluate the importance of the task.Then，Importance Ranking-based Scheduling Algorithm（IRSA）was proposed to schedule tasks in descending order of importance.Finally，a resource reservation mechanism and a preemptive scheduling mechanism were designed in IRSA to improve the efficiency of task scheduling.Experimental results show that compared with the four online scheduling algorithms such as First Come First Serve（FCFS），Earliest Deadline First（EDF），Least Laxity First（LLF），and Fixed Priority Scheduling（FPS），when the number of arrival tasks per second reaches 7.99，IRSA reduces the average response time of tasks by 55.83%to 61.27%，respectively，and has significant advantages on all performance metrics.Therefore，IRSA can achieve efficient task scheduling for SOA-based industrial software.Key words:Service-Oriented Architecture(SOA);industrial software;task scheduling;utility function;resource reservation mechanism;preemptive scheduling mechanism0 引言 随着信息技术的发展及其与工业领域的融合，各类工业软件已经广泛用于工业生产过程的控制和管理1。现有工业 软 件 大 多 采 用 面 向 服 务 架 构（Service-Oriented Architecture，SOA），软件被拆分为多个粗粒度、松耦合的服务，服务间通过网络通信2。基于SOA的软件收到用户请求后，相应服务实例会对请求进行处理，完成处理后向用户返回结果。本文将每个请求的处理过程称为一个任务。与大多数商业软件相比，工业软件对实时性和可靠性的要求非常高3。实时性指软件对请求作出迅速响应的能力；可靠性指软件在规定时间内完成相应任务的能力，与任务的按时完成率呈正相关。任务的完成过程需要占用服务实例的 计 算 资 源，包 括 中 央 处 理 器（Central Processing Unit，CPU）、内存、磁盘输入输出（Input and Output，IO）、网络带宽4。然而，工业软件中通常存在大量待处理任务，而服务实例的可用计算资源有限，无法同时处理所有任务，导致部分任务难以被快速处理，甚至不能按时完成，造成经济损失甚至安全事故5。因此，设计一种高效的任务调度方法将任务合理地分配给服务实例处理，是保障工业软件实时性和可靠性的重要需求6。任务调度方法需要结合应用场景的特点设计。在工业场景中，不同任务的重要程度对工业系统的影响不同7。软件需要优先处理重要任务，同时尽可能多地处理非重要任务。因此，重要程度是任务的属性之一，需要设计合适的方法进行评估。而任务的处理需要占用服务实例的部分计算资源，这就是任务的资源需求量属性。此外，任务还具有到达时间、处理时长和截止时间的属性，而截止时间限制了任文章编号：1001-9081（2023）03-0885-09DOI：10.11772/j.issn.1001-9081.2022010055收稿日期：20220117；修回日期：20220427；录用日期：20220428。基金项目：广东省自然科学杰出青年基金资助项目（2018B030306041）；广州市科技计划项目（202102020413）。作者简介：宁明超（1998），男，湖南衡阳人，硕士研究生，CCF会员，主要研究方向：服务监控、资源调度；张俊勃（1986），男，重庆人，教授，博士，主要研究方向：大型工业软件及其智能化；陈戈（1995），男，广东广州人，博士研究生，主要研究方向：软件设计与测试。第 43 卷计算机应用务的完成时间。例如，在输电线路故障处理场景中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）系统的任务调度问题，该场景中每台服务器是一个服务实例，可以同时承载多台虚拟机任务，因此每个服务实例可以同时处理多个任务。显然，在具有大量任务且任务有截止时间限制的工业场景中，应选择能实现任务并行处