基于移动中间件抽象层调度策略研究

黄锦涛,何加铭,陈 平,贾德祥

(宁波大学通信技术研究所,浙江宁波315211)

0 引 言

移动终端上数据业务越来越丰富,应用环境越来越复杂,很多新型应用(如联网游戏)需要实时系统支持,为满足应用实时性要求,在基于移动终端中间件抽象层上完善调度策略。系统实时性具体表现为处理器的响应时间和吞吐率。响应时间指运行程序所需要的所有时间的总和(一个任务从开始到结束所需的时间);吞吐率指单位时间内能运行的任务数。那么缩短响应时间通常也就意味着提高吞吐率。提高实时性的途径有：软件级并行;处理器级并行;线程级并行;指令级并行;执行级并行[1]。线程是程序中的一条执行分支,或者说,线程是可以同时运行的函数。线程有以下特点：(1)共享父进程的所有资源;(2)通过系统调度或者同步变量传送消息;(3)切换时只涉及寄存器和局部变量,开销很小;(4)注意线程同步问题,防止死机现象[2]。线程分时共享处理器资源,大量线程切换带来的开销仍然相当可观,所以需要一种低开销的多任务调度模型。不同操作系统的线程运行机制有很大不同,本目标系统提供了两类调度策略：位图(Bitmap)调度和多级(MLQ)调度。

1 位图调度策略

位图调度策略是一种基于静态优先级的抢占式调度策略。被调度的线程拥有唯一不变的优先级,每一时刻运行的是就绪队列中优先级最高的线程。该调度策略以时钟中断作为基本调度时机,当优先级更高的线程进入就绪态时就立刻抢占正在运行的低优先级线程[3]。主要数据结构如下：

(1)位图表。位图调度策略可支持256种不同的优先级,用32位无符号整型数(针对支持32位整型数的体系结构)数组rdy_queue将256个优先级分成8组,数组每个成员的每一位代表一个优先级,按照从最高有效位至最低有效位优先级逐次降低,当某位为l时表示该优先级线程进入就绪态。线程开始的优先级为基本优先级,线程的当前优先级可在1到32的范围内动态改变。在以下情况会提升线程当前优先级：I/O操作完成;信号量或事件等待结束;前台进程中的线程完成一个等待操作;线程处于就绪状态一定时间,但没能进入运行状态。位图表用来方便查找系统最高优先级线程;

(2)就绪队列。Bitmap_thread_rdy数组用来存储进入就绪态的线程对象的指针。当位图表中某组中任何一个优先级进入就绪状态(被置1)时,就绪队列中对应的元素就记录了该线程的指针如图1所示。

图1 位图表与就绪队列

这样,通过就绪队列与位图表就可以得到线程的优先级。当位图调度器进行调度时只需要依次查找rdy_queue中置1的最高位,即可找到最先级线程。

2 多级调度优化策略

多级队列调度是一种抢占式与时间片轮转(Round-Robin)调度相结合的调度策略,是对位图调度策略的扩充,即允许线程具有相同的优先级。在相同优先级线程之间采间片轮转调度策略,平均分配CPU占用时间。该策略的思想是尽量选择那些处于活动状态的高优先级线程进行取指,保证线程缓存区中的指令极少数是错误路径的,而且该策略对线程进行详细的等级划分,使得只有最低等级的线程才被暂停,提高取指效率[4]。主要数据结构如下：

(1)位图表。与位图调度策略中rdy_queue相同;

(2)就绪队列。mlq_thread_rdy数组用来存储线程指针。与位图调度策略不同的是,thread_rdy每一个元素存储的是一个链表头,其后面可以挂接线程对象形成一个双向链表,THREAD数据结构中的next和prey指针使线程成为一个线程双向链表结点。变量rr_quantum用来指定时间片大小,当某线程时间片用完时,首先确定是否降低该线程的优先级,然后确定是否调度另一个线程进入运行状态。假定刚用完时间配额的线程的优先级没有降低,如果有优先级相同的就绪线程,则选择相同优先级就绪队列中的第一个线程进入运行状态,刚用完时间配额的线程被排到就绪队列的队尾;如果没有优先级相同的就绪线程,刚用完时间配额的线程将得到一个新的时间配额并继续运行;

(3)可达截止期优先算法。可达截止期优先算法是对截止期优先策略的改进,就绪队列的任务优先级,仍然按照截止期顺序排队。但是,在调度时超过截止期的不予调度。

当前时刻离截止时刻的时间：

式中,Tc为系统当前时刻,Te为执行整个任务的估算时间,Tr为任务已执行部分所用的实际时间,Td为截止时刻。

当D ≥0时,任务预计能在截止时刻前完成(也就是说,该任务的截止期是当前可达到的),于是可以进行调度,否则放弃该任务的执行。

在可达截止期最早优先算法中,系统时钟对任务的运行时间进行累计,空闲任务 IDLE的截止时刻DeadTime应设为无限大,而估算时间则为0,就绪队列中至少有一个就绪任务满足调度要求。

3 调度管理模块

在调度管理模块中实现部分主要有：

(1)基本数据类型定义;

(2)线程上下文切换。尽管线程是微内核中调度和执行的基本单位,但对于微处理器而言.它不能感知线程实体的存在,它只能为线程的执行提供一个环境,这个环境就是相关的寄存器。由此可见,线程的切换实质就是微处理器的寄存器更换内容的过程,而这个过程与处理器体系结构密切相关,因此需要对线程上下文切换过程进行封装,使其在抽象层中实现。给出位图调度策略和多级队列调度策略的实现流程图如图2所示;

图2 位图调度策略和多级队列调度策略流程图

(3)调度服务函数。调度管理模块提供的服务函数如表1所示：

表1 调度服务函数

4 测试分析

在通常的位图调度策略中,如果取出过多在IQ中停留时间较长的指令,最终会使IQ中充满不可发射的指令,称之为IQ阻塞(IQ clog),这样吞吐率降低,使执行单元处于空闲状态,浪费资源。利用多级调度结合可达截止期优先算法的混合应用,时间片轮转式交替执行使指令混合,减少IQ阻塞出现的概率。实验测试结果表明改进后多级调度策略相比于原先的位图调度策略,IQ阻塞的概率减少了11%。如表2所示,IQ阻塞率在各种线程数目下都有大幅度降低。

表2 各线程IQ阻塞率

5 结束语

一个好的调度方法,需要综合考虑应用程序多样性以及体系结构两个方面的特征。本文提出一种基于抽象层的线程调度策略,在高效的位图调度的基础上扩充为多级调度策略,一种抢占式与时间片轮转(Round-Robin)调度相结合的调度策略。这种调度方式避免了某项任务长时间占用CPU时间,既提高了程序的性能,又增强了程序的功能。但随着进程或者线程个数的增加,以及处理器个数的增加,需考察的调度决策数呈指数增长。因此调度算法应该和具体的体系结构以及进程本身相关,这也是需要继续完善的方向。

[1]Sohi G,Roth A.Speculative Multithreaded Processors[J].IEEE Computer,2001,34(4)：66-71.

[2]骆斌,费翔林.多线程技术的研究与应用[J].计算机研究与发展,2000,37(4)：407-412.

[3]Seto D B,Lehoczky J,Liu s.Task Period selection and schedulability in real-time systems[J].IEEE Communication Society,1998,16(3)：188-199.

[4]罗宇,商临锋.操作系统多线程实现技术研究[J].小型微型计算机系统,2000,21(5)：500-503.

[5]Reinder J B,Elisabeth S,Wim V.Best-case response times and jitter analysis of real-time tasks[J].Journal of Scheduling,2004,7(2)：133-147.