摘要:在多核系统中，针对Linux的调度算法对交互式任务响应实时不足的问题，设计并提出了一种改进的交互式、多层次的任务调度GAS模型.该模型通过相近度对CPU实现分组，组内的CPU共享任务队列;通过改进多任务时负载均衡与任务迁移的开销，降低了交互式场景下任务的响应时长，提高了Linux多核多任务的任务执行性能;通过唤醒任务优先执行的机制，提高了交互任务的响应效率.实验结果表明，在不同任务数情况下，GAS算法的平均响应时长和最大响应时长都优于BFS算法和CFS算法.
关键词:多核系统;任务迁移;任务队列;交互式任务;负载均衡
Linux由于其优秀的可扩展性和安全稳定性，使其在PC家用机、嵌入式等领域占据很大市场份额，Linux的调度算法也力求支持不同的领域场景.但PC家用机主要侧重于任务低响应时长，巨型机主要侧重于高吞吐量，嵌入式主要侧重于低开销，而多核领域的实时交互响应则非现有Linux调度策略所擅长[1].主要是Linux的CFS(CompletelyFairSchedule)算法侧重于实现高吞吐量，对于实时响应、快速唤醒等要求难以满足.
针对多核实时任务调度响应慢的问题，文献[2]提出了利用缓存增加任务之间的竞争性以提高任务轮询的效率，增强多任务响应效率，但该算法的开销较高.文献[3]提出了让多核共享同一任务队列以降低实时交互的响应时长的BFS(BrainFuckSchedule)算法，该算法虽然能够有效的降低响应时长但当任务数偏多时则因为多队列竞争开销大，效率明显下降.基于此，提出了基于任务分组的GAS(GroupTaskSchedule)调度策略，将相近的任务分配至同一组内，以降低组内任务切换时CPU迁移开销，同时可以根据负载情况进行组间的均衡处理.
1GAS整体设计
为了解决BFS难以适用于多任务情况中，GAS按照任务相近性进行分组配置，一般多核系统中任务相近度分为四种情况:(1)非统一内存访问间(NonUniformMemoryAccessArchitecture，NUMA)具有独立的内存空间;(2)同一个NUMA结点内占用不同CPU，但独占Cache;(3)占据一个CPU内的不同核，独占不同的L1_Cache，但多任务共享L2_Cache;(4)共享同一个处理核，且共享L1_Cache[4-5].
存储介质的访问时长各为:内存为75ns±25，L1_Cache为1ns，L2_Cache为3ns～10ns，将任务访问时长相近的分配到组内，使CPU的任务迁移导致存储空间的刷新时间会降低.GAS算法为每个组创建了红黑树结构实现的任务管理队列，为每个CPU创建双向链表结构的任务唤醒队列，结构如图1所示.
当新建任务时需要先计算任务的虚拟结束时间vdeadline，计算公式如式(1)所示，其中jiffies表示当前时间，prio_ration表征任务的优先级，rr_interva表示时间片长.
vdeadline=jiffies+prio_ration×rr_interval(1)
后将任务插入到CPU队列红黑树中，首先检查队所有列数中是否存在空闲CPU或在执行的任务的vdeadline大于新的时间，则触发中断将任务加入到该CPU任务队列中.
当需要进行任务唤醒操作时，如果是睡眠前vdeadline不改变，并检查各Group内的CPU是否已经空闲或任务的vdeadline大于新的时间，则在CPU的双向链表中插入该任务，并触发中断将任务加入到该CPU任务队列中.
GAS模型的调度操作流程分为下面两个步骤.
(1)通过周期调度器scheduler_tick计算各任务运行时长，如果超时则添加调度标记，如果各Group间任务负载失衡，则进行Group任务重新分组和迁移;
(2)scheduler()函数实现了将任务插入到对应Group的队列红黑树中，如果任务的时间片已结束则刷新时间片和vdeadline，在进行调度时优先选择CPU的双向链表.
任务调度时要先查看双向链表，再索引红黑树，如果任务满足唤醒条件则加入到双向链表中并启动中断机制加入到CPU中，该机制降低了唤醒任务的响应时长，提高了效率.如果现有K个CPU、M个任务、N个Group，则任务新建与任务唤醒的时间复杂度为O(K/N+lg(M/N)，插入和删除任务的时间复杂度为O(lg(M/N)，调度的开销一般为O(lg(M/N).
2GAS算法实现
2.1分组设计
Linux内置的调度模块初始化函数是sched_init()[6]，GAS算法的初始化策略是通过为每个CPU创建指向主任务队列的指针和指向高级任务队列的指针.为了实现分组的功能，GAS模型为每个CPU创建二维数组，用于存储CPU和其余CPU的相近性关系，GAS模型对处理器中的CPU进行遍历，实现CPU的自适应分组.
Linux内置的用于初始化任务迁移函数是migration_init()，如果GAS模型发现CPU与其他组的CPU相近度更高，则将该CPU重新选定分组.同一个分组内的CPU由于共享L2_Cache，所以在同一个分组内迁移任务的开销更低.如果自动分配的分组不能满足要求，也可以通过sysset_mainq_cpu()函数实现人工手动调整CPU的任务队列，实现更合理的分组.
2.2调度函数设计与实现
2.2.1周期调度函数设计
GAS算法的周期调度函数scheduler_tick()在BFS算法的基础上改进了多任务时的负载均衡管理，以提高多任务存在时的并行能力，负载均衡的代价是任务均衡调度期间需要对执行队列加锁、调用任务迁移功能等操作，所以负载均衡的次数要尽量降低且执行时需要选择合适的时机.
GAS算法按照CPU、CORE、PHY和NUMA四个层次进行遍历，将遍历的结果保存到红黑树型结构中.GAS从最底层开始进行遍历，直到遍历完最高层的节点为止.任务的调度和分组的粒度有关，如果分组时将核内的所有CPU置于一个组内，则索引的最低级别是CORE，与粒度挂钩的机制也降低了负载均衡的负担和复杂度.
2.2.2调度器函数设计
Linux系统中提取任务至执行态使用scheduler()函数，首先查看双向链表，之后索引红黑树.如果双向链表中存在任务，则双向链表中任务的vdeadline已经按照由小至大的顺序进行排序，所以直接选取第一个任务作为待执行任务即可;如果没有任务，则从红黑树中选取最左侧叶子节点作为待执行节点.之后继续扫描，直至所有任务执行完毕.如果经过扫描发现队列中没有待执行的任务，则将对应的CPU标记为空闲状态.
2.3任务唤醒
执行任务唤醒的一个关键步骤是选取CPU，GAS模型使用数组维持CPU相近度的管理，在选取CPU时，最优先选取被标记为空闲状态的CPU;如无空闲状态的CPU，则遍历所有CPU，索引出相似度最高的空闲CPU执行，否则选取vdeadline比自身大的CPU.任务在被唤醒后，需要分配至主任务队列中，之后按照队列与分组对应关系分配CPU，找到CPU后将任务插入到对应的任务队列中等待调用执行.
3实验与结果分析
本文选取的Linux系统版本为centos6.3，内核版本为Linux3.6.2，处理器配置为4核8CPU的IntelCorei7-67003.4GHz.系统性能检测工具选用Interbench-0.31，Interbench能够有效采集和监测系统的响应时长数据.
如图2和图3所示，分别为BFS算法、CFS算法和GAS算法的平均响应时长对比结果和最大响应时长的对比结果，任务数量的取值区间为8～48，每次增长8个任务.从图中可以看出，GAS算法的最大响应时长和平均响应时长都较优于BFS算法和CFS算法.
4结论针对Linux系统在交互式任务场景下的任务响应实时不足的问题，设计并实现了改进的交互式、多层次的任务调度GAS模型.通过Group内共享任务队列、唤醒任务优先执行等机制的设计，降低了交互式场景下任务的响应时长，提高了Linux多核多任务的任务执行性能.通过Interbench工具的性能检测发现，交互式任务场景下改进的GAS算法的性能较CFS算法、BFS算法的性能更高.
相关期刊推荐：《西安文理学院学报(自然科学版)》(季刊)创刊于1994年，是经国家新闻出版署批准国内外公开发行的综合性学术刊物，国内外公开发行。主要刊登生命科学、数学及应用数学、物理学、化学与化学工程、机械电子技术、计算机科学与技术、环境资源与地理科学等方面有创新、有参考价值的研究论文、综述和研究进展，具有领先水平的科研成果，学术报告和动态等.读者对象为科研工作者、高等学校教师和研究生等。
