一种面向负载均衡的多核IMA可预测性调度方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN115904711A(43)申请公布日2023.04.04(21)申请号202211444693.4(22)申请日2022.11.18(71)申请人南京航空航天大学地址211106江苏省南京市江宁区将军大道29号南京航空航天大学(72)发明人杨志斌刘晨谢宛玲谢红梅郭鹏周勇(74)专利代理机构南京苏高专利商标事务所(普通合伙)32204专利代理师颜盈静(51)Int.Cl.G06F9/50(2006.01)权利要求书2页说明书6页附图2页(54)发明名称一种面向负载均衡的多核IMA可预测性调度方法(57)摘要本发明公开了一种面向负载均衡的多核IMA可预测性调度方法，通过将IMA系统模型形式化后，给出描述分区模型和任务模型的参数；并设计一个资源回收机制，追踪较为关键分区的资源预算情况，若其实际执行时间小于其最坏执行时间，那么便设计算法来分析其预算捐赠状况；接着将节约的预算通过三种不同的启发式算法分配给不那么关键的分区。本发明保留了分区之间的时间隔离，保证在一个时间段内只有一个分区被激活，比经典的循环调度方案的灵活性更强，可以处理由异步事件导致的非周期性请求，并在基于最大响应时间的分析方法下能够缓解其资源的严重浪费现象，提高系统的平均性能，管理不可预测的负载变化。CN115904711ACN115904711A权利要求书1/2页1.一种面向负载均衡的多核IMA可预测性调度方法，其特征在于：假设，IMA系统有N个分区∏1,∏2,...,Πi,...,ΠN，每个分区由3个参数定义(Qi,Pi,πi)，其中，Qi表示分区的容量，Pi表示分区的周期，πi表示分区的优先级；每个分区包括m个周期服务器每个周期服务器由分区的参数(Qi,Pi)定义，并用来表示周期服务器的剩余容量；每个分区Πi上都有一组任务ti,1,...,ti,n，每个任务由4个参数定义(Ci,j,Di,j,Ti,j,pi,j)，其中，Ci,j表示任务的最坏执行时间，Di,j表示任务的截止日期，Ti,j表示任务的周期，pi,j表示任务的优先级；根据是否可以选择不执行，每个任务分为强制部分和可选部分，每个任务先执行强制部分，再执行可选部分，任务的Ci,j包括强制部分的最坏执行时间和可选部分的最坏执行时间；调度方法包括以下步骤：步骤1：按照容量转移策略，确定捐赠分区；步骤2：按照容量分配策略，确定接受捐赠的分区；步骤3：捐赠分区向接受捐赠的分区捐赠容量，接受捐赠的分区在核上使用捐赠的容量来执行分配给该核的有资格接受捐赠的任务的可选部分；其中，所述的容量转移策略，包括：S00：在周期服务器开始时，初始化周期服务器的最坏预算为Qi；最坏预算表示所有任务在执行最坏执行时间时消耗的容量；S10：当周期服务器开始调度，判断用于执行任务的核c是否处于空闲状态，若处于空闲状态，则转入S20；否则表示任务正在执行，并转入S30：S20：判断应用程序是否处于静止状态，若处于静止状态，则按比递减；若不处于静止状态，则转入S40；S30：判断任务是否在其最坏执行时间之内完成，若完成，则减去(Ci,j‑ai,j)，其中，ai,j就是任务的实际执行时间；若没有，则按比递减；S40：判断最坏预算是否和剩余容量相同，若相等，则按比递减；若不相等，则维持不变，并再次转入S40；S50：当满足周期服务器的剩余容量且其响应的应用程序处于静止状态或者周期服务器的最坏预算时，此时说明该周期服务器准备捐赠；当一个分区内的所有周期服务器都准备捐赠时，此时该分区为捐赠分区；其中，所述容量分配策略，包括：假设在时刻t，捐赠分区捐赠了一定数量的容量，只有在时刻t完成了强制部分的任务且该任务不执行可选部分，且该任务的优先级低于捐赠分区的优先级，该任务才有资格接受捐赠，并将该有资格接受捐赠的任务插入到有资格接受捐赠的任务队列中；每个核均有一个有资格接受捐赠的任务队列；若一个分区最少有一个有资格接受捐赠的任务，则这个分区为有资格接受捐赠的分区；依据有资格接受捐赠的任务队列，确定接受捐赠的分区。2.根据权利要求1所述的一种面向负载均衡的多核IMA可预测性调度方法，其特征在于：应用程序处于静止状态按照以下步骤判断得到：2CN115904711A权利要求书2/2页假设核c上所有挂起的任务都已经完成，核c处于空闲状态，且当前周期服务器在周期结束之前不会释放任何其他的任务，则认定在核c上运行的分区的应用程序在给定的周期内处于静止状态。3.根据权利要求1所述的一种面向负载均衡的多核IMA可预测性调度方法，其特征在于：按比递减的速率与递减的速率相同。4.根据权利要求1所述的一种面向负载均衡的多核IMA可预测性调度方法，其特征在于：所述的依据有资格接受捐赠的任务队列，确定接受捐赠的分区，包括