基于混合实时任务调度器的并行数控系统研究*

陈传伟，付 铄，韩振宇，富宏亚

(哈尔滨工业大学 机电工程学院，哈尔滨 150001)

0 引言

与传统数控系统相比，嵌入式数控系统具有低成本，稳定性、可靠性高等优势[1]。近年来，随着嵌入式多核处理器的出现和发展，嵌入式处理器性能大幅提升，为嵌入式数控系统的发展提供了有力的支持，使其能够朝着高速高精、复合加工、多通道多轴联动、智能化等方向[2]发展，围绕多核调度算法、并行数控系统等方向的研究相继展开。文献[3]对嵌入式实时操作系统uC/OS-II进行扩展，实现了其对嵌入式对称多核处理器多任务调度的支持。文献[4]针对数控系统各任务间数据流不平衡问题题建立了数据流反馈调度模型。文献[5]提出了基于多处理器的最早截止期优先调度算法的测试方法。

本文对并行数控系统实时任务调度需求进行分析，针对数据依赖任务间数据流不平衡问题，提出了一种混合实时任务算法，基于嵌入式实时操作系统eCos设计并实现了该调度器，其能自动维持数据流平衡，具有良好的负载平衡性和加速比。对GRBL串行数控系统进行多任务划分，并基于嵌入式对称多核处理器S698PM[6]和混合实时任务调度器搭建了并行数控系统实验平台。

1 并行数控系统实时任务调度需求分析

数控系统任务分为实时任务与非实时任务，本文主要研究实时任务调度。

本文提出的并行数控系统实时内核架构见图1。其中，虚线框内任务链上的任务具有严格的时序，G代码必须依次经过译码任务、拟合任务、前瞻规划任务、前加减速规划任务、插补任务的处理，才能得到正确的运动控制指令，任务间还存在数据依赖关系，即下游任务的执行必须依赖上游任务产生的数据，本文称这类任务为数据依赖任务，通过在任务间构建循环队列形成多级流水线结构，实现各任务间解耦，各数据依赖任务在满足调度条件的前提下，可在多核处理器各处理核心上并发执行。此外，并行数控系统实时内核中还存在传统的周期性实时任务，该类任务由定时器驱动，按一定的任务周期执行，如位置发送任务，按插补周期将位置指令发送至伺服电机驱动器，控制电机运动，又如机床状态检测任务，对机床状态、标志量等进行周期性检测，并进行相应的机床状态切换和I/O操作。由此，将并行数控系统实时内核任务分为周期性实时任务和数据依赖任务，本文将周期性实时任务用二元组(P,T)描述，其中P为任务优先级，T为任务周期(ms)，将数据依赖任务用三元组(O,UL,DL)描述，O为在任务链上的位置索引，UL为上游缓存数据量，DL为下游缓存数据量，这两类实时任务对应的任务集的合集构成混合实时任务集。

并行数控系统在处理G代码的过程中，由于每条G代码对应的插补曲线类型、长度不定，造成各任务消耗与产生数据量之比为1:N(N>=1)。如拟合任务对圆弧指令的处理，该任务需按照弦高误差将圆弧划分为连续的直线微段，以满足圆弧精度的要求，不同的弧长及弦高误差会导致直线微段数量N的变化，故拟合任务一次作业时间随插补曲线类型、长度变化而变化，造成了任务链上数据流波动。数据流波动会直接影响加工连续性，进而影响数控机床加工质量，需要对数据流波动进行有效调节。

为充分利用对称多核处理器的运算能力，保证各处理核心负载平衡，同时实现周期性实时任务与数据依赖任务统一调度，保证任务链上数据流平衡，需要设计相应的任务调度器，以满足并行数控系统实时内核混合任务集的调度需求，如图1所示。

图1 并行数控系统实时内核架构

2 混合实时任务调度器设计与实现

首先，根据调度需求分析了混合实时任务调度器的调度依据，设计了调度流程，并在分析嵌入式实时操作系统eCos多级队列调度器的基础上，对其进行改造，实现了混合实时任务调度器，并根据该调度器提出了数据依赖任务通用框架。

2.1 数据依赖任务调度算法设计

任务调度器的作用是计算调度时刻优先级最高的就绪任务并执行上下文切换，实现任务调度，故首先应当确定调度依据。

混合实时任务集中的周期性任务可由eCos多级队列调度器进行调度，而任务链上的数据依赖任务需根据调度需求设计调度算法完成调度。图2为某一时刻任务链上数据流状态，纵坐标表示数据量，横坐标从左至右表示任务链上游至下游，各任务消耗数据量与生产数据量之比为1:N(N>=1)，任务每执行一次，任务上下游数据量差值减N+1。为维持数据流平衡，需要使任务上下游数据量差值向0逼近，故任务链上拥有最大上下游数据量差值的任务应当优先执行，即图2中Task1。结合任务上下游缓存数据量大小、多核处理器特性可总结出四条调度依据：①根据任务是否正在某CPU上运行决定是否调度；②根据任务上游缓存是否有数据，下游缓存是否有剩余空间决定该任务是否调度；③计算任务上下游数据量差值，优先执行差值最大的任务；④若存在几个任务有相同的最大差值，优先执行上游任务。

图2 某时刻任务链上数据流状态

根据以上数据依赖任务的调度依据，设计出数据依赖任务调度算法流程，如图3所示，即从任务链上游至下游依次遍历各数据依赖任务，根据数据依赖任务调度依据，计算得到优先级最高的任务并进行调度。

图3 数据依赖任务调度算法流程图

2.2 混合实时任务调度器实现

本文基于嵌入式实时操作系统eCos实现混合实时任务调度器。首先对其原有调度器进行分析。eCos通过多级队列调度算法[7]实现对SMP多核多任务调度的支持。多级队列表示eCos支持多个不同优先级，默认优先级为0～31，每个优先级对应了一个双向循环任务链表。其调度算法流程如图4所示，其中pending[i]表示优先级为i的任务链表中被挂起的任务数目，pending_map的第i位状态表示优先级为i的任务链表中是否有被挂起的任务，eCos通过这两个变量的共同作用实现SMP多核多任务调度。

为基于eCos多级队列调度器实现混合实时任务调度器，将在[0,CRI_N)区间内的优先级定义为周期性任务优先级，将[CRI_N,31)区间内优先级定义为数据依赖任务在任务链上的位置索引。优先级为31的任务为系统空闲任务。混合任务调度算法流程如图5所示，若任务链表中存在就绪的周期性实时任务，根据多级队列调度算法，调度优先级最高的周期性任务，调度结束；若没有就绪的周期性实时任务，根据数据依赖任务调度算法遍历任务链上的数据依赖任务任务，找到优先级最高的数据依赖任务，调度该任务，若没有满足调度条件的数据依赖任务，则调度系统空闲任务。由此，基于eCos多级队列调度器构建了混合实时任务调度器。

图4 eCos多级队列调度算法流程图

图5 混合实时任务调度算法

2.3 数据依赖任务通用框架

根据混合实时任务调度器的调度原理，提出数据依赖任务通用框架，其示意图如图6所示。按该架构定义各数据依赖任务，从而与混合实时任务调度器相适应。

图6 数据依赖任务通用架构

3 并行数控系统设计

本文基于GRBL串行数控系统构建并行数控系统，在深入分析GRBL内核的基础上，对其进行多任务划分，并在任务间引入循环队列实现各任务解耦。由于嵌入式处理器内存空间有限，在上位机与数控系统之间建立了G代码动态批处理机制。

3.1 并行数控系统架构设计

并行数控系总体统架构如图7所示，上位机向数控系统发送G代码，开关量控制指令等。选用嵌入式对称多核处理器S698PM运行并行数控系统，该处理器基于SPARC架构设计，含有4个处理器核心，最高主频可达500MHz。数控系统采用数据采样插补，将插补得到的各轴进给量通过网络端口发送给POWERLINK[8]通信卡，通信卡将位置信息转换为POWERLINK协议帧，发送给支持POWERLINK协议的伺服电机驱动，从而控制电机运动。电气控制柜如图8所示，三轴铣床如图9所示。

图7 并行数控系总体统架构示意图

图8 控制柜 图9 三轴铣床

3.2 并行数控系统任务模块实现

首先对GRBL串行数控系统内核架构进行分析。其工作流程可概括如下：PC通过串口向GRBL发送G代码，GRBL接收到一个完整的G代码段后，进行译码。译码结束后，对于接收到的插补指令，首先按精度要求将曲线拟合成连续直线段，并对直线段序列进行前瞻规划，得到各直线段满足电机加减速性能的最大入口速度，接着对直线段进行前加减速规划，得到具体的速度曲线，再进行粗插补，计算插补时间及距离增量，放入微段缓存segment_buffer[N]中，如图10所示。微段缓存由定时器中断服务函数进行处理，其过程如图11所示，根据各微段的粗插补时间及距离增量计算脉冲序列的频率，采用基准脉冲插补法，利用Bresenham[9]法生成脉冲序列，实现对步进电机的速度及位置控制。

图10 GRBL内核架构示意图

图11 定时器中断处理过程

将GRBL串行数控系统划分为图12所示的各个数据依赖任务，通过在任务间构建循环队列实现任务解耦和数据传递，从而在嵌入式对称多核处理器上实现多级流水线数据并行产销，最后由周期性任务位置发送任务按插补周期向伺服电机驱动器发送位置指令。由于各循环队列的上下游任务可能同时对其进行访问，需通过互斥量[10]对循环队列进行保护，保证运算过程的正确性。

图12 并行数控系统架构

3.3 G代码动态批处理

由于数控系统的G代码存储空间有限，而G代码大小与工件复杂程度相关，为防止数控系统G代码的存储空间溢出，须在上位机数控系统之间建立G代码动态批处理机制。首先根据数控系统G代码存储空间大小设置上溢值和下溢值，启动上位机发送G代码后，数控系统在接收G代码的同时，检测G代码存储空间的数据量，当数据量超过上溢值时，向上位机发送停止发送指令，此时数控系统继续消耗G代码，当检测到数据量小于下溢值时，向上位机发送启动发送指令，从而实现G代码动态批处理。

4 实验验证

首先对调度器进行测试，验证其正确性及数据流平衡效果，测试了负载平衡性和加速比。通过加工实验验证了并行数控系统的正确性。

4.1 调度器测试

图13 各缓存数据量变化情况

为验证混合实时任务调度器的正确性，建立了2个周期性任务，其参数为(0，500)，(1，500)，同时建立了6个数据依赖任务，其在任务链上的位置索引依次为16、17、18、19、20、21。各任务每执行一次将对应指示灯取反。测试程序运行后，周期性任务按500ms周期执行。当在最上游缓存放置数据时，数据依赖任务按位置关系顺序执行，验证了混合实时任务调度器的正确性。

为验证调度过程中任务链上数据流平衡效果，基于QT[11]编写了数据流状态演示软件，在最上游缓存放入150个待处理数据，调度过程中各缓存数据量趋于平衡，如图13所示，验证了调度器的数据流平衡效果。

用硬延时语句for循环1千万次模拟任务的数据处理过程，在最上游缓存内放置150个待处理的数据，统计程序执行过程中各CPU执行各任务的次数，由于各任务数据处理过程相同，执行次数可类比于CPU运行时间，统计结果如表1所示。实验表明，该条件下，各CPU执行次数占总执行次数基本相同，验证了各CPU负载平衡。

通过定时器测试各任务执行时间及并行时间，单位为ms，测试结果如表2所示，测得并行时间为17649ms，加速比为3.895，具有较好的加速效果。

表1 各CPU任务执行情况统计

表2 加速比测试

4.2 并行数控系统测试

为验证并行数控系统的正确性，进行了加工实验，设定插补周期为2ms，进给速度100mm/min，加速度72000mm/min2，选用4mm直径铣刀，加工轨迹如图14所示，将并行数控系统安装至三轴铣床，进行蜡模加工，其实际加工效果如图15所示。由此，验证了并行数控系统系统的正确性。

图14 加工轨迹 图15 加工效果

5 结束语

本文在分析并行数控系统任务调度需求的基础上提出了混合实时任务调度器，通过改造嵌入式实时操作系统eCos实现了该任务调度器，并基于嵌入式对称多核处理器S698PM搭建了并行数控系统实验平台。实验结果明，混合实时任务调度器实现了周期性任务与数据依赖任务统一调度，能自动维持数据流平衡，保证良好的负载平衡性和加速比，在调度数控系统实时任务方面具有众多优点，基于该调度器的并行数控系统能正确运行，证明了该调度器具备实用性。未来将继续完善该并行数控系统，以体现出多核并行数控系统在运算性能方面的优势。

[参考文献]

[1] 刘建康. 基于ARM+FPGA的嵌入式数控系统硬件设计[D]. 哈尔滨: 哈尔滨工业大学, 2013.

[2] 刘大炜, 汤立民. 国产高档数控机床的发展现状及展望[J]. 航空制造技术, 2014(3): 40-43.

[3] 章承科. 基于多核处理器的实时操作系统的扩展[D]. 成都: 电子科技大学, 2006.

[4] 秦承刚. 开放式数控系统的实时操作系统优化技术研究与应用[D]. 北京: 中国科学院大学, 2012.

[5] Theodore P Baker. An Analysis of EDF Schedulability on a Multiprocessor[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(8): 760- 768.

[6] 颜军. SPARC嵌入式系统设计与开发[M]. 北京: 中国标准出版社, 2013.

[7] 蒋句平. 嵌入式可配置实时操作系统eCos开发与运用[M]. 北京: 机械工业出版社, 2008.

[8] 肖维荣, 王瑾秋, 宋华振. 开源实时以太网Powerlink详解[M]. 北京: 机械工业出版社, 2015.

[9] Liu X W, Cheng K. Three-dimensional extension of Bresenham's algorithm and its application in straight-line interpolation[J]. Proceedings of Institution of Mechanical Engineers Part B Journal of Engineering Engineering Manufacture, 2002, 216(3): 459-463.

[10] Anthony J Massa. 嵌入式配置实时操作系统eCos软件开发[M]. 颜若麟,译. 北京: 北京航空航天大学出版社, 2006.

[11] 吴纯赟, 栾勇, 杜少华,等. 基于Qt的数控系统测试软件的设计与实现[J]. 组合机床与自动化加工技术, 2016(11): 76-79.