基于动态时间片的RM实时调度算法

摘要：嵌入式实时操作系统克服了无线抄表系统中的数据重传次数多、实时性差、传输效率低等缺点。论文结合单调速率调度算法和时间片轮转算法的优点，对系统实时调度算法进行改进，提出了一种基于动态时间片的单调速率（RM）实时调度算法，并将新的算法应用于无线抄表系统中。实验证明，所提出的新算法在复杂通信环境下调度用时接近于理想时间，优于传统实时调度算法。
关键词：无线抄表系统；嵌入式系统；实时调度算法；动态时间片

RM Real-Time Scheduling Algorithm Based on Dynamic Time Slice
Zhang Xue-jun, Zhou Hao, Yan Jin-tong, Lu You
(School of Electronic Science and Engineering, Nanjing University of Posts and Telecommunications, Nanjing, Jiangsu 210003, China)
Abstract：The embedded real-time operating system can improve the usefulness of the wireless meter system. The new scheduling algorithm based primarily on the priority algorithms, and it combines the advantages of speed-adjustment scheduling algorithm and the round-robin scheduling algorithm. Experiments show that, the proposed algorithm makes the time of scheduling in complex communication environment scheduling obviously close to the ideal time, superior to the traditional algorithm.
　　
Key words：wireless meter system; embedded system; real-time scheduling algorithms; dynamic time slice
0 引言
　　随着城市规划建设水平的提高和城市人口数量的剧增，高层以及超高层建筑的数量越来越多，这对家居智能化提出了更高的要求。作为家居智能化产业链中的一部分——智能抄表系统也同时得到了蓬勃发展。无线抄表系统作为服务于燃气、电力、自来水行业的工具，它的出现大大减少了抄表人员的劳动量，提高了企业效率，并给住户带来了方便。但是传统的无线抄表系统存在的数据重传次数多、实时性差、传输效率低等缺点。
1 无线抄表系统的设计
1.1硬件设计
　　无线抄表系统的硬件主要由仪表数据发射装置和手持接收机组成，二者硬件结构大体一致，主要由STM32F103系列微控制芯片、SI4432无线发射芯片、SPI总线等核心部分构成，如图1所示。
　　
图1 硬件示意图
　　STM32F103微控制芯片采用ARM公司Cortex-M3内核，该内核具有强大的中断管理机制，能够在复杂的通信环境中，为无线抄表系统提供系统级保障，防止由于数据流过于拥挤、信噪比过于低而导致的数据传输障碍。另外，其内部的SysTick定时器，可提供精确的时钟振荡计时，方便了嵌入式系统的移植。
　　SI4432无线收发芯片提供的频率范围从240MHz到930MHz，可调输出功率达+20dBm，支持调频扩频，并提供了自动唤醒定时器、信道强度评估、低电量检测器、64字节发射/接收、自动数据包处理等功能，同时还支持SPI总线连接。
1.2 μC/OS-II 实时内核的移植
　　μC/OS-II 内核是一个开源、抢占式的内核[1]，它包含了操作系统的任务调度、任务管理、时间管理、内存管理、定时管理以及任务通信与同步等基本的特性[2]。其优先级抢占策略，能够保证系统的实时性。μC/OS-II 内核中，一般只需要移植os_cpu.h，os_cpu_a.asm 和 os_cpu_c.c文件，大大降低了移植难度[3]。μC/OS的定时中断确保了系统的实时性，每个时钟节拍到来就会产生一次定时中断，中断后进行任务调度，运行就绪表中优先级最高的任务。系统架构如图2所示。
　　
图2 系统架构
2 实时调度算法
　　实时调度算法是实时操作系统的核心，经典的实时调度算法主要有单调速率（Rate Monotonic, RM )调度算法和最早截止时间优先 (Earliest Deadline First, EDF) 调度算法两种[4]。
　　RM调度算法是一种典型的静态优先级调度算法，它根据任务执行周期的长短来决定调度优先级，执行周期小的任务具有较高的优先级。这种调度方式主要适合周期性任务，对于突发性任务，无法预先估计执行时间，因而会导致系统的执行效率很低。对于给定任务集合｛S1,S2,S3,S4……Sn｝，调度器的利用率必须满足
　　 (1)
式中，Cn表示任务Sn的执行时间；Tn表示任务Sn的执行周期，L(n)表示调度器利用率的最下界。当n→∞时，L(n)→ln2≈ 0.693。整个任务集的负载小于L(n)时，RM 算法调度是可行的[5]。
传统的RM实时调度算法，用时越短的任务优先级越高，但由于没有时间片或其他终止策略的设置，如果一个实时任务由于某种自身原因或者环境原因超出了自己的执行时间,任务却没有完成，则改任务将保持当前的高优先级执行下去，直到执行完毕。这样就会顺延给后续任务, 形成多米诺效应，造成多个任务超出截止时间。在实际情况中特别是无线通信传输中很容易发生过载时, 导致控制器调度工作大增上，性能退化。[6]
　　EDF 调度算法是一种典型的动态优先级调度算法，它根据就绪队列中各个任务的截止期限来分配优先级，具有最近截止期限的任务优先级最高。主要优点为：任务的优先级能够根据需要动态改变，使得系统适应性比较好。任务调度优先级定义为：di(t)-t，其中：di(t)是任务时限，t是当前时间，两者的差值表示任务的紧迫程度。
　　对于给定任务集合｛S1,S2,S3,S4……Sn｝，任务的调度器利用率必须满足下面的条件[5]
　　 (2)
式中，Cn表示任务Sn的执行时间；Tn表示任务Sn的执行周期，L(n)表示调度器利用率的最下界。

　　本文结合了单调速率调度算法和时间片轮转算法的优点，对系统实时调度算法进行改进，提出了一种基于动态时间片的单调速率实时调度算法（Rate Monotonic real-time scheduling algorithm based on dynamic time slice，简称DTS-RM），并将新的算法应用于无线抄表系统中。实验证明，所提出的新算法所提出的新算法在复杂通信环境下调度用时接近于理想时间，优于传统实时调度算法。
3 基于动态时间片的RM实时调度算法
3.1算法步骤
　　在无线抄表系统应用的实际环境中中，节点所处的环境信噪比高，则传输用时较短；节点所处的环境信噪比低，则传输用时较长。因此，将每个传输任务作为一个任务，信噪比高，则设置该任务优先级高，反之，则设置低的优先级，我们提出了DTS-RM实时调度算法，算法步骤为：
　　注册
　　当手持机进入小区后，首先对小区所有设备发送广播帧，提醒各个仪表设备进行注册。手持机发送广播后，可能会有多个仪表同时向手持机发送注册帧。为了减低碰撞的发生，我们采用经典的ALOHA算法。ALOHA算法是一种随机接入型的算法[7-8]，其工作原理：手持机发送广播帧，接收到广播帧的仪表产生注册帧，并立即发送到无线信道中；若在规定时间内收到手持机的确认应答，表示注册成功，否则执行重发策略，即随机退避若干个时序后再向手持机发送注册帧，直到注册成功，如图3所示。

　　图3 注册示意图
　　2、数据传输
（1）设置多个隔离的就绪队列，依据不同的优先级，将实时任务分配到几个不同级别的队列中。
（2）各个队列按照级别先后进入处理机，高优先级的队列，任务的初始时间片设置的较短，低优先级的队列，任务的初始时间片设置的较长，如图4所示，具体设置在3.2节中详细介绍。
（3）第一个任务时间片是初始时间片，队列中剩余的每个任务的时间片动态调整。若在时间片内，前一个任务完成，则将接下来任务的时间片减小0.05s，以此类推，渐次减小。若一旦遇到某个任务在时间片内无法完成，时间片的设置开始每次增大0.05s，直到任务能够完成。如图5所示。
（4）如果队列上的某个实时任务运行超过分配运行时间，若继续运行下去, 有可能造成整个队列的延时，则放弃该任务，并记录其ID。
（5）在所有队列均执行完毕后，对传输失败的任务依据记录的ID依次进行轮询通信。

　　图4 基于时间片的RM实时调度算法队列示意图

图5 时间片动态设置示意图
3.2算法实现
1、 变量的设置
　　将该改进型实时调度算法应用到实际系统中，需要在系统代码中增加队列优先级和任务时间片等变量。在无线抄表系统中，优先级由该仪表所处的无线环境的好坏决定的，量化到数值上就是信噪比。由于本系统采用的无线通信芯片能够测算当前的传输环境的信噪比并形成数值，可在仪表的注册帧中加入3bit位的信号强度位。将000到111生成如表1所示量化等级表。
表1量化等级表
优先级 　量化等级 信号强度(dbmw)
1 　000(0) -66~ 无穷大
2 　001(1) -67 ~ -70
3 　010(2) -71~-74
4 　011(3) -75~-78
5 　100(4) -79~-82
6 　101(5) -83~-86
7 　110(6) -87~-90
8 　111(7) -90~无穷小
　　手持机在接收各个仪表设备的注册帧后，可以根据注册帧中含有的信号强度量化值，将所有仪表分成多个就绪队列，其中信号强度高的仪表队列被赋予高优先级，信号强度低的仪表队列被赋予低优先级。
　　每个队列的初始时间片T与该序列的优先级P的关系为
T=kP（k为常数） （3）
　　经过大量的实际测试，发现在信号强度正常的情况下，每个任务传输完毕需要大约0.8s。设优先级P的取值从1到8，则k取0.25比较合适。
2、数据帧的设置
　　在该调度算法中，一个队列对应多个任务，系统要构造一个结构体OS_line，用来控制队列，称作队列控制块，如图6所示，它主要包含下列元素：
　　 （1）OSPrio：队列的优先级，占3bits。
（2）line_Stat：队列的状态，如果该队列处于就绪状态，那么这个变量就置为就绪，占2bits。
　　 （3）Count：当前优先级下含有的任务数，占9bits。
　　 （4）Tcount：当前队列的初始时间片大小，占3bits。
OSPrio(3bits) line_Stat(2bits) Count(9bits) Tcount(3bits)
图6 队列控制块结构
　　当一个队列得到调度，进入CPU执行后，任务按照时间片轮转调度，同时时间片做动态调整。因此系统中还需要加入一个结构体 OS_task，用来控制任务，称作任务控制块，如图7所示，它主要包含下列元素：
　　 （1）task_ID：当前任务的ID，占10bits。
　　 （2）task_Stat：当前任务的状态，如果该状态处于就绪状态，那么这个变量就置为就绪，占2bits。
　　　（3）task_Tcount：当前任务的时间片大小，占3bits。
　　task_ID(10bits) 　　task_Stat(2bits) 　task_Tcount(3bits)
图7 任务控制块结构
4 性能分析与对比测试
　　我们在不同的信噪比环境下，测试了多次仪表与手持机单独通信成功所需要的时间，实验数据如表2所示。
表2在不同信噪比下仪表与手持机通信时间
信噪比(dB) 优先级 平均完成时间(s)
-65 0 0.2
-73 2 0.35
-81 4 0.6
-88 6 0.7
-92 7 NA
　　　　　　　　 注：NA表示多次未成功通信
　　由表2可见，随着信噪比的减小，通信用时逐渐变长，在低信噪比时，完成所需时间陡然变大，在信噪比接近-100dB时，出现了失败通信。因此，选取前3个信噪比环境，分别在0.2s，0.35s，0.6s，0.7s数据周围，随机选取6个数值，共生成24个数据，排成4个队列的仿真数据。为了模拟真实通信环境中的随机出现的通信延时与干扰，在测试程序中人为添加干扰延时，信噪比较低时，干扰延时发生的概率加大，如表3所示。
表3仿真数据
队列 　　 6个任务完成时间(s)
队列1 　　0.29 　　0.24 　　0.22 　　0.19 　　0.24 　　0.28
队列2 　　0.31 　　0.33 　　0.36s 　　0.38 　　0.40 　　0.44
队列3 　　0.55 　　0.55 　　0.66 　　0.65 　　0.71 　　0.53
队列4 　　0.70 　　0.67 　　0.73 　　0.66 　　0.69 　　0.71
本次测试，全部任务完成最少需要12.5s左右。将此24个任务打乱，形成5种不同的顺序方案，导入基于动态时间片的RM实时调度程序和传统的RM实时调度程序中，以此模拟现实通信中，全部数据点均发起通信的情况。统计5次完成所有任务需要的时间，做出曲线如图8所示。传统RM实时调度算法5次测试用时分别为：15.50s, 14.80s, 15.15s, 15.30s, 14.98s，平均用时15.146s。基于动态时间片的RM调度算法5次测试用时分别为：14.12 s, 15.05 s, 14.95 s, 14.65 s, 13.95 s，平均用时14.544s，比传统RM算法的性能平均提高了约4%。从图8可以看出，5次不同的任务排序，基于动态时间片的RM实时调度算法完成的时间各不相同，说明不同的任务排序对完成时间是有影响的。但在5次测试中，基于动态时间片的RM实时调度算法的完成时间最差仅比最少时间多2.55s。
为了模拟实际通信环境中随机出现的通信延时与干扰，在测试程序中人为添加干扰延时，信噪比较低时，干扰延时发生的概率加大。为了对比明显，将第2次测试中的干扰延时出现的次数减少，使之明显低于现实通信环境中的干扰。测试表明，改进的算法未发生作用且由于时间片的设置，用时较长，所以在图8中第2次测试时改进算法用时较传统RM算法略长。在随后的第3、第4、第5次测试中，将干扰延时发生的概率再次调整到正常范围以内。
　　实验结果表明，基于动态时间片的RM实时调度算法的性能优于传统RM实时调度算法。传统的RM实时调度程序在运行程序时，虽然在优先级比较高即环境信噪比比较好时性能很高，但一旦遇到低信噪比任务，任务完成很容易超时，导致后续任务不断延期，性能退化快，

图8模拟测试
　　在完成该抄表系统的硬件设计与系统移植后，分别在空旷区域（无干扰）和一幢六层的居民楼（架设同频率的无线电遥控器作为干扰）架设5台仪表终端和一台手持机，做了无线抄表试验，实验结果如表4所示。
　　　　　　　　　　　　　　　　　　 表4现场测试结果
通信机制 测试环境 完成时间(s)
轮询 空旷区域 5
轮询 居民楼 7
实时调度 空旷区域 3
实时调度 居民楼 5
5 结束语
实际测试表明，在引入了基于动态时间片的RM实时调度算法后，无线抄表系统在全部数据抄送的完成时间上得到了改进。实验证明，该实时调度算法在无线抄表系统中的应用是可行的，值得推广。当然，该系统仍然有可以改进的空间。例如，在对时间片处理上，可以应用更复杂更有效的算法，对不同信号强度下传输时间进行评估，从而可以更高的提高系统效率。微控制器芯片的许多组网功能还可以利用到无线抄表系统中，从而使该系统更加的智能化。