一种基于滑动窗口的多核数控系统任务调度策略

张丽鹏，于 东，胡 毅

1(中国科学院 沈阳计算技术研究所，沈阳 110168)

2(中国科学院大学，北京 100049)

3(沈阳高精数控智能技术股份有限公司，沈阳 110168)E-mail:lipzhang_hn@outlook.com

1 引 言

数控系统技术是机械制造和控制相结合的产物，是当今高端装备制造业的核心技术之一.数控(numerical control，NC)机床特别是高档数控机床是国际装备制造业竞争的热点领域[1].随着计算机信息技术的发展，多核处理技术成为了新的趋势，这对数控技术提出了新的要求.目前，基于嵌入式芯片的数控系统仍较多采用单核处理器平台，在这种情况下，通过多核平台来解决单核遇到的问题具有重要的现实意义.

同构多核处理器是采用多个相同结构的核心组成的芯片，每个核心的功能完全相同，地位完全相等，没有层级之分[2].各个核心执行相同或相似的任务，整个芯片作为一个统一的结构对外提供服务，以满足提高性能、实现负载均衡的需求.

结合多核处理器系统结构的特征，文献[3]针对嵌入式多核处理器资源有限特点，采用整数线性规划方法对软件流水中负载、通信与内存开销建立模型，提出了一种基于软件流水的任务调度方法以实现负载均衡及通信、内存开销的优化.文献[4]将系统中的所有可用核分组，将共享高速缓存的多个核作为一个簇集，采用簇间独立调度、簇内统一调度的混合调度策略，并利用核间中断信号来同步任务处理过程.文献[5]以最小化任务集的执行跨度为目标，提出一种基于改进蚁群算法的多核任务分配与调度算法.文献[6]通过对粒子群算法适应度函数调整,提出一种基于粒子群算法的多核调度算法.文献[7]提出一种种群均衡遗传算法(BPGA)，将任务节点在处理器核上随机分配而任务节点数均衡分配.上述文献提出的任务调度策略具有一定的普适性，但算法实现的复杂性相对较高，实用性不强.

本文在以上研究成果的基础上，以负载均衡性为目标，首先取合适的滑动窗口值，将待执行的任务序列以滑动窗口大小进行分批处理.文末对比实验表明了算法较好的满足了系统的负载均衡并且有较好的执行效率.

2 任务分配模型

2.1 相关理论

多核处理器上的任务分配与调度业已证明是NP-完全问题[8].通常的做法是使用启发式算法或遗传算法、模拟退火等优化求解算法寻其近似解.文献[9]提出RADG算法来消除迭代内的数据依赖性，该算法通过重定时技术将周期相关的依赖任务图转换为一组独立的任务.经过算法处理后所有的任务在迭代内都不存在数据依赖关系，这样就对任务顺序的调整提供了可能.本文以此理论研究为基础，为实验简单，假定任务之间不存在数据依赖关系，提出基于滑动窗口的多核数控系统任务调度策略.

cpu负载是指在一段时间内正在使用和等待使用cpu的平均任务数,文献[10]中采用一段时间间隔内所有任务的执行时间表示.本文引用并改进了这个思想，将cpu的负载表示为:

(1)

按照负载计算公式(1),时间间隔取本次任务分配完成的时间与上一次任务分配完成的时间之差,理想状态下每个内核的负载为0.7,本文实验在同构4核心处理器上进行,因此可以认为当系统负载达到3以上时即为负载超标,应考虑适当降低滑动窗口大小提高系统吞吐量.

2.2 任务分配模型

图1描述了任务分配过程,考虑在某一小段时间内,设同构多核处理器的核心数为m,记为C={c1,c2,…,cm}.待分配进程P中有n个线程任务,记为P={tr1,tr2,…,trn}，其中m>0,n>m.

图1 任务分配模型

由于是同构处理器，同一任务在不同核心上的执行时间认为是相同的，则每个任务在各相应核心上的执行时间可以表示为T={t1,t2,…,tn}.取滑动窗口值为w，w<=n.则该滑动窗口内任务在各相应核心上的执行时间可表示为矩阵E，该矩阵有w/m行,m列.

令sum1,sum2,…,summ分别表示矩阵E中每一列的列和,则sum1,sum2,…,summ分别表示分配在核心1,2,…,m上的线程执行完成所用时长.为使负载均衡，问题可转化为寻求在m个核心上分配任务的策略，使得summax与summin差值最小.即:

min(summax-summin)

(2)

3 任务分配算法

3.1 算法思想

在任务执行调度之前，首先进行任务序列的预处理，以系统的实时负载为依据采用大小合适的滑动窗口限制每轮任务的分配量，将滑动窗口中的任务队列设为多核心访问的公共资源.对任务队列依序取滑动窗口大小的前两份,记为首列和次列.首先对两个任务队列进行不同的预处理,过程为链式归并排序过程的改进,排好序的首列基于优先级由大到小、运行时间由大到小排列，而次列则基于优先级由大到小、运行时间由小到大排列.基于此,在任务分配时分别选择已排序的首列和次列的当前列表头部的任务作为复合任务分配给轮到的核心.首次分配任务时的核心得到的复合任务将是优先级最高执行时间最长的任务与优先级最高执行时间最短的任务,下一个核心得到的任务将分别是任务队列剩余任务中优先级最高执行时间最长的任务与优先级最高执行时间最短任务的复合,以此类推,直到本轮滑动窗口中的任务分配完毕,计算当前的系统负载,更新滑动窗口值.整体处理流程如图2所示.

图2 算法执行流程图

3.2 任务预处理

将任务队列看作有序的结构，首先依次取任务队列中前w个任务作为首列Task1,次列Task2.基于链式归并排序过程的改进，分别对两任务队列进行排序,算法整体时间复杂度为O(nlogn),空间复杂度为O(1).

主要数据结构说明:

struct task_struct{

……

long etm;

long pro;

struct task_struct *next;

……

}

在数据结构task_struct中，属性etm表示该任务执行时间计数或运行时间片，pro表示任务运行优先级数,越大优先级越高.

过程详图如图3,流程中newHead表示该次迭代中需合并部分的后半部链表的头部,内部循环每次迭代中①处剪断需要合并的前半段,②处剪断需要合并的后半段,lastHead在合并前指向后半段开始的位置,合并后指向下一轮将要从哪个位置合并.

图3 预处理算法执行流程图

过程merge()为合并两个队列的核心处理流程，实现对首列及队列按照不同需求的分割，排序及合并.对原始队列Task按照任务优先级降序，运行时间降序排序.Task.pro、Task.etm分别代表任务的优先级与执行时长.对于次列Task2的处理流程于此基本一致,所不同的是需将流程merge()中循环体内的条件“>”改为“<=”.如此得到的两队列即可进行任务的复合并进一步进行任务分配.过程见图4.

图4 归并过程执行流程图

上述两个过程完成了按滑动窗口值依次取任务task1，task2并已按照预设要求排序，是后续步骤的基础.为使任务队列在指定核心上分配，并使得分配任务后在滑动窗口内所有任务在执行期间每个处理器核心的负载相对均衡.需要继续对上述得到的任务队列进行任务的两两复合.在这里需要利用Linux系统在多核计算机上对处理器核心的亲缘性，即绑定进行/线程到指定处理器核心上执行，在本文中使用c语言头文件sched.h中的sched_setaffinity系统调用的方式.对于复合后任务的执行情况，默认情况是先执行task.etm较大的.算法流程如图5所示.

图5 复合与分配任务算法流程图

过程adjust_()计算处理器当前负载，据此动态调整滑动窗口值w,防止任务的阻塞,提高的系统实时吞吐量.

w值的确定借鉴了TCP中拥塞控制机制[11],采用慢开始和拥塞避免算法,开始时将w值设置为处理器核心数用以探测,随之由小到大逐渐增大滑动窗口,即每经过一轮处理,w值加倍.当系统的负载达到2时,采用拥塞避免机制,线性增大w值.当系统负载达到3时,重置w值为最小值.流程如图6所示.

图6 调整窗口值程序流程图

4 实验验证与结果分析

实验环境：飞凌公司研发的搭载i.MX6处理器的同构4核心ARM开发板,Linux版本号位3.05.如图7所示.实验采取随机任务图作为任务调度与分配的测试任务集.

图7 多核ARM开发板

各次实验中随机生成八百万任务数据,进行多次实验后随机取5次实验结果测得各个核心的负载百分比情况如表1所示.结果表明本文提出算法对于系统的负载均衡性测试有较好的实验结果.

表1 各核心负载情况

对文献[7]中提出的BPGA算法进行对比，设定处理器数为1，处理器核心数固定为4，杂交与变异概率分别仍为0.8、0.4，种群规模为100，算法最大迭代次数1000.随机取10次实验执行时长对比,其结果如图8所示,计算所取10次实验结果的平均执行效率较前者提高了11.96%.

图8 执行时间对比图

分析原因可能在于种群规模与迭代次数过大的设置使算法收敛时间过长，为增加对比性，更改BPGA算法参数，设定种群规模为50，最大迭代次数800，其实验对比结果如图9.

图9 执行时间对比图

计算所取10次随机实验结果的平均执行效率,本文算法较前者提高了11.27%.主要原因在于BPGA算法在寻找最优解时的频繁迭代使得任务执行时间较长.实验结果表明，本文算法能够较好的满足多核系统处理器的负载均衡性，同时在执行效率上有良好的表现.

5 结束语

本文在前人研究的基础上,针对同构多核数控系统,研究并实现了多核任务调度算法,在任务预处理阶段,采用滑动窗口动态调控任务序列大小以避免任务阻塞,在任务分配之前对任务队列进行复制、排序并复合.最后实验结果表明本文算法较好的满足了负载的均衡性,同时又有较好的执行效率.

本文存在的问题是任务数据为随机生成,具有正态分布的特征，对于数据类别分布不稳定、极端的任务集未能验证.下一步将在实际生成环境中进行测试.