1、2023 年第 36 卷第 3 期Electronic Sci.Tech./Mar.15，2023h t t p s:/j o u r n a l.x i d i a n.e d u.c n收稿日期:2021-09-01基金项目:国家自然科学基金(71840003);上海市自然科学基金项目(15Z1429300)National Natural Science Foundation of China(71840003);Shang-hai Municipal Natural Science Fund Project(15Z1429300)作者简介:张海涛(1994 )，男，硕士研究生。研究方向
2、:分布式实时系统。张通(1992 )，男，硕士研究生。研究方向:分布式实时系统。张凤登(1963 )，男，博士，教授。研究方向:汽车电子与现场总线。基于 MrsP 协议的任务划分优化算法张海涛，张通，张宇辉，管银凤，张凤登(上海理工大学 光电信息与计算机工程学院，上海 200093)摘要多处理器实时系统中，调度和资源共享是核心问题，与之相对应的调度算法和共享资源访问协议将直接影响系统的性能，这就要求调度算法和资源访问协议在保证实时性的基础上尽量发挥硬件平台的计算能力。然而，现有的调度算法多假设任务相互独立，没有考虑任务之间的资源共享，共享资源访问协议也多侧重于规则和最坏响应时间分析。对此，将
3、P M 算法和 MrsP 协议相结合，得出了多处理器实时系统的整体可调度性条件。文中根据 MrsP 协议的特性，提出了一种减小阻塞时间的任务划分算法，通过改进任务利用率的计算方式解决了关键区重复计算的问题，与之前的任务划分算法相比，也解决了关键区重复计算以及任务分类后拆分再分配的问题。实验表明，该算法所需要的处理器数目减少了 15%20%。关键词多处理器;实时系统;共享资源访问协议;可调度性分析;实时调度;最坏响应时间;划分算法;处理器数量中图分类号TP316文献标识码A文章编号1007 7820(2023)03 036 07doi:10.16180/ki.issn1007 7820.2023
4、.03.006Task Partitioning Optimization Algorithm Based on MrsP ProtocolZHANG Haitao，ZHANG Tong，ZHANG Yuhui，GUAN Yinfeng，ZHANG Fengdeng(School of Optical Electrical and Computer Engineering，University of Shanghai forScience and Technology，Shanghai 200093，China)AbstractScheduling and resource sharing a
5、re the core problems in multiprocessor real time systems，the cor-responding scheduling algorithm and shared resource access protocol will directly affect the performance of the sys-tem，which requires the scheduling algorithm and resource access protocol to maximize the computing power of thehardware
6、 platform on the basis of ensuring real time performance However，most existing scheduling algorithms as-sume that tasks are independent of each other and do not consider resource sharing among tasks Besides，shared re-source access protocols also focus on rules and worst case response time analysis I
7、n this regard，the whole scheduleability condition of multiprocessor real time system is obtained by combining P M algorithm and MrsP protocolAccording to the characteristics of the MrsP protocol，this study proposes a task division algorithm to reduce the bloc-king time By improving the calculation m
8、ethod of the task utilization，the proposed method solves the problem of re-peated calculation in the critical area Compared with the previous task partitioning algorithm，the proposed algorithmalso solves the key area of double counting and splits the redistribution after task classification problem
9、Experi-ments resalts show that the number of processors required by the algorithm is reduced by 15%to 20%Keywordsmultiprocessor;real time system;shared resource access protocol;schedule ability analysis;real time scheduling;worst response time;partition algorithm;number of processors随着计算机技术的进步和发展，越来
10、越多的复杂系统依赖于计算机控制，实时系统在当今社会中扮演着至关重要的角色 1。与此同时，人们对实时系统的功能和性能有了更高的要求，实时系统逐渐被构建在多处理器平台之上 2。多处理器实时调度算法主要解决两个问题:任务划分问题和优先级分配问题 3。其中，划分调度中关键的就是任务划分算法。这个划分问题类似于经典装箱问题。使用 P M 调度算法时，文献 4 研究了首次适应算法(First Fit，FF)、最佳适应算法(Best Fit，BF)和最坏适应算法(Worst Fit，WF)等经典的装箱算法的性能，并得到了可调度的利用率上限条件。文献 5 提出了在划分 EDF(Earliest Deadlin
11、e First)和划分固定优先级调度下基于整数线性规划(Integer Linear Program-ming，ILP)的划分问题求解方法。然而，上述方法利用63张海涛，等:基于 MrsP 协议的任务划分优化算法Electronic Science and Technologyh t t p s:/j o u r n a l.x i d i a n.e d u.c n率上限都没有考虑共享资源的影响。当考虑任务访问共享资源时，由于任务可以通过访问共享资源来阻塞其他处理器上的任务，会导致划分问题的复杂化。文献 6 提出了将任务访问本地资源而导致的阻塞合并到ILP 中的任务划分方法。文献 7 提出了
12、多处理器共享资源访问协议(Multiprocessor esource Sharing Protocol，MrsP)，该协议使用了帮助机制来减小阻塞时间，这也是本文主要研究的多处理器共享资源访问协议。然而，上述算法未解决任务分组的利用率大于单个处理器利用率时的拆分和再分配问题。对此，本文的研究内容主要分为两个部分:第 1 部分研究使用划分调度(Partitioned Scheduling)算法，并在每个处理器上使用单调速率(ate Monotonic，M)算法(以下简称 P M 算法)，而对共享资源的管理则使用多处理器共享资源访问协议7。通过将 P M 算法和 MrsP 协议相结合，得出了多处
13、理器实时系统的整体可调度性条件，为 MrsP 协议的实际使用奠定了基础。第 2 部分则在研究共享资源约束的基础上，针对 MrsP 协议的任务划分算法，提出了任务划分的优化方法。1系统模型与假设本文 的 研 究 基 于 同 构 多 处 理 器(SymmetricMultiprocessor)平台8。处理器的集合记为 P=p1，p2，pm，pk表示第 k 个处理器，其中1 k m 且 k为整数。实时任务则记为 =1，2，n，i表示第 i 个的实时任务，其中1 i n 且 i 为整数。共享资源可以分为硬件共享资源和软件共享资源两种，针对硬件类共享资源的访问控制可以使用相应的机制来同步2，9 处理。本
14、文的共享资源为软件类的共享资源，例如任务之间数据结构或者变量的共享。设共享资源的数量为q(q1)，记为=r1，r2，rq，用rs表示第 s个共享资源，其中1 sq且s为整数。此外，本文假设系统中的共享资源不存在嵌套访问的情况，因此在实际使用时可以使用分组锁解决该问题1011。在划分调度下，映射 G(rs)返回使用共享资源 rs的任务集合，映射 F(i)返回任务 i使用的共享资源集合，映射 map()返回任务集合划分到的处理器集合，映射 map1(pk)返回划分到处理器集合的任务集合。本文规定对于给定任务集合 =1，2，n，任务优先级按降序排序，使用i表示任务 i的优先级，即 pri(i)=i。
15、由于本文的研究是基于划分调度算法，对于实时任务集 到处理器集合 P 的划分，定义为 =1，2，m，其中 k为分配到第 k 个处理器上的任务集合。本文研究的任务模型是偶发任务模型。该模型中每个任务有 3 个参数:相对截止时间 D 以及参数最坏执行时间 C 和周期 T。偶发任务 i的模型表示为 i=(Ci，Di，Ti)。这样的一个偶发任务会释放一个无限的实例序列。任意两个相邻实例的释放时间的间隔有一个最小的约束周期 Ti。任务 i释放的每个实例最坏执行时间为 Ci，相对截止时间 Di是指从到达时间起始到截止时间的时间间隔。本文中一个任务系统通常被表示为 =1，2，n。2系统整体可调度性分析原有的
16、MrsP 协议多侧重于最坏响应时间分析，实时调度算法又多基于传统的独立任务模型。因此本节整体研究了实时调度算法、共享资源访问协议，弥补了独立研究的不足，并在资源共享下，得出系统可调度性条件。MrsP 协议可以解决多处理器平台上实时任务访问共享资源的任务同步问题。根据 MrsP 协议的定义和性质，实时任务访问共享资源的阻塞可以分为两类:本地阻塞和远程阻塞12。本地阻塞指同一处理器上低优先级任务通过访问或者占用共享资源，使自身优先级高于原来的高优先级任务，造成对高优先级任务的阻塞。远程阻塞是指在不同处理器上一个任务访问一个已被占用的共享资源时的等待时间，例如在不同处理器上的任务i和j，任务j首先锁定共享资源，当任务i试图访问共享资源时便会进入自旋等待，此时任务j对任务 i的阻塞便称为远程阻塞。任务 i自旋等待时间被称为忙等待(Busy Waiting，BW)时间。本文定义任务 i访问所有共享资源的远程阻塞时间为 BW，除去任务自身访问共享资源的时间后可得BW=rsFi()Ni，smap Grs()()1()cs(1)由文献 13可知，在使用 M 调度算法调度实时任务时，PCP 协议管理共享
