零星事件调度策略

零星发生的事件是困扰很多实时系统的一大难题,正确管理这些非周期性事件有助于实现稳定可靠的实时系统设计。本文介绍了POSIX零星调度策略,利用该策略可使系统在过载时满足关键线程的时限要求,保障系统的可靠性。

大多数实时操作系统均采用基于优先级的占先调度器以使多线程共享单个CPU。这种调度器尤其适用于那些完全由固定周期性线程组成的系统,这些系统都只具有有限的外部激励。然而,实际应用中软件系统通常具有无限的外部激励,因此需要进行时变运算。在这些情况下,事件可能使那些由典型RTOS调度器构建的系统陷入过载,而无法满足关键时限时间(deadline)要求。

理论与实际的冲突

在我们早期的项目中,设计组历经数月才定义出数字交换机系统控制器的软件架构。由于通信交换机必须满足严格的时间要求,因此我们选择了据称能很好地满足实时应用的操作系统。数月之后,产品质量(QA)部门的工程师开始报告出现间歇的系统死锁。在这些死锁期间,用户接口不响应键盘操作,而表征处理器工作状态的LED则一直保持为闪亮状态。这时,固件驱动指示灯仍然闪烁,好像没有产生任何故障。

由于不仅处理器的LED指示内核运行状态连续,而且具有最高优先级的心跳中断服务程序也正常运行,因此可以推断死锁产生的原因是在无限循环中产生中等优先级中断服务程序。由于故障出现是间歇的,因此找到故障根源非常困难。最初,这种问题只在一个系统中出现,但随后在另一系统也出现同样的问题。通过检查,最后在电路板上发现了一条短路线,这条线使闪存的电平感应中断请求信号电平升高。尽管系统可执行高优先级的心跳线程,但无法对低优先级的键盘I/O信号进行响应,因为系统需要不断地处理中等优先级的闪存控制器中断线程。

在过去几年中,我们碰到过类似的死锁:如大量的数据包使网络接口控制器过载、大量突发的输入输出字符使串行控制器过载、SCSI总线上连续不断的数据使磁盘控制器过载。我们开始感到困惑:为什么外部事件能够如此轻易地影响到系统呢？事实上,实际应用环境通常不符合我们简化的设计假设:因为线程并非严格周期性,我们很难构造解决抖动和过载的系统,实时操作系统只是解决这些问题的方案开始部分。

优先级处理

静态优先级占先调度器要求设计工程师为每个线程分配唯一的优先级,这样当有多个线程就绪时,调度器知道运行哪个线程。确定特定线程优先级的常规方法通常有几种,而非常规方法还有很多。在这些方法中,考虑时间约束与线程优先级的方法远优于那些考虑主观测量(如线程重要性)与优先级的方法。

时限时间单调(DM)和速率单调(RM)算法是两种最佳的优先级分配方法,这些方法为那些具有较短时限时间和周期的线程分配更高的优先级。这些方法的优点在于,如果能以任何静态优先级算法调度系统,那么也可以采用DM或RM算法调度系统。此外,如果这些优化算法不能有效地调度特定应用的线程,那么其它静态优先级分配方法也无能为力。

尽管静态优先级占先调度机制不能调度所有系统,设计工程师通常仍会选用该方法,商用的RTOS也提供静态优先级占先调度方法,因为该方法可提供比动态优先级调度方法更高的稳定性和可预测性。静态优先级占先调度器的实现还相对简单,且要求的操作系统开销最小。

数字控制

静态优先级占先调度尤其适用于数字控制系统,包括导航设备、家用电器、工业制造、化学处理和汽车应用。

图1给出了一个简单的单输入/单输出(SISO)控制系统框图。更为复杂的控制系统能以不同的速率管理多个设备,并采用多输入/多输出(MIMO)控制器。

利用标准的RTOS,编程人员可以轻松地实现带有3个并行闭环控制线程的MIMO控制器,这些线程以不同的速率运行来控制3个不同的设备。由于这些线程具有明确的定义和严格周期性线程集,因此这种控制系统符合经典的速率单调分析假定,成为静态优先级占先调度的理想应用。

然而实际上,适用于实时应用的系统同样也可能出现非周期性或零星外部事件。这些系统包括网络和通信设备、多媒体播放器、医疗设备和工业控制系统,或者更一般地说,任何连接到可能存在不正常工作状态的设备环境或在随机间隙时间内运行的设备环境系统。例如,设备管理者可在任何不可预见时刻将工业过程从生产模式切换至安全模式,使系统在这两种模式之间切换的线程就是零星线程。

系统过载

当事件的间隙时间比计划的短,或者线程的执行间隙比计划的长时,系统将进入过载状态。此时,系统必须摒弃一些事件或允许一个或多个线程错过其时限时间,从而使更多的关键线程按时完成。

当系统出现过载时,硬件设备可能会失效,由此产生远远偏离常规行为的虚假信号。错误代码或恶意代码、未经正确培训的用户或恶意用户、过多的外部系统都能产生过多事件,这与设计工程师的统计假设相背离。

调度策略的不同选择使系统在发生过载时的行为具有很大差异,并且还决定了设计工程师能否预测性地描述系统在过载条件下的特性。例如,时限时间最早优先(EDF)动态优先级调度策略在过载条件下性能很差,由于EDF可用于动态配置线程特性,因此系统设计工程师无法预测过载条件下哪个特定线程将错过时限时间。而且,超过额定界限的线程以后还可能导致其它线程错过时限时间。

另一方面,设计工程师采用静态优先级策略可进行可调度性分析,以保证即使在过载条件下重要线程不会错过时限时间。采用可预测调度策略对于安全关键系统尤为重要,这些系统要求即使在过载条件下也需要保持可预测性。例如,宁愿采用那些在出现过载时错过几次用户界面刷新的系统,而不用那些故障时不能关闭控制阀的系统。

由于设计差的系统通常不能满足过载条件下重要线程和不甚重要线程的约束条件,因此设计良好的系统必须有选择地处理事件,以确保总能满足关键线程的时限要求。POSIX的零星调度策略可以很好满足这样的设计要求。

零星调度策略

IEEE POSIX规范套件组描述了便携操作系统的编程接口。1999年,POSIX工作组引入了IEEE 1003.1d,规定了附加的C语言实时扩展。该标准的13.2.4节中,除了之前标准化的轮询(Round Robin)和FIFO策略外,还增加了零星调度器策略。POSIX工作组详细规定了适用于处理非周期性和零星事件以及静态优先级占先调度条件下线程的零星调度策略。

除了适用于FIFO调度和轮询调度的标准优先等级,零星调度策略的参数还包括一个次级较低优先级的背景优先级(background priority)、补充间隙(replenishment interval)、执行预算,以及在每个补充间隙中所允许的最大补充数量。此外,补充间隙和执行预算还规定了线程在其“常规”优先级上的最大处理器利用率。

如果线程需要比其预算更高的处理器时间,那么零星调度策略将把线程的优先级动态地调低至其“背景”优先级。在这两种优先级的任意一种下,调度器平等对待该线程与其它采用传统FIFO调度策略的线程。例如,就绪队列中的优先级继承和配置保持一致,最重要的差异在于线程的执行时间和线程的优先级重分配。

通过降低线程的优先级,系统允许执行其它线程,否则零星线程将在正常优先级占先。线程优先级的动态调整是使程序设计工程师能构建可预测系统策略的核心功能。零星线程的运行将占用处理器执行时间,这样每次线程被阻塞或调度器占先时,调度器将从被占先线程预算中扣除占用的时间。

当零星线程被阻塞时(但未被占先)时,零星调度器在距离该线程最近的去阻塞之后给新的补充事件分配一段补充周期。调度器设定执行预算量,并允许线程在去阻塞之后的这段补充期间也可以执行。

在单个周期内,某个线程可能需要与较低优先级线程竞争多种资源,因此可能出现多个未完成的补充事件。为了使调度器的开销最小,POSIX规范可使设计工程师限制每个周期内未完成补充事件的数量。如果完成补充事件的数量达到最大值,那么在这段补充周期内将不会调度额外的补充事件。

如果零星线程占用了全部执行预算,那么处理器将通知调度器,这样调度器将调低线程的优先级至背景级。线程保持该优先级,直到出现下一个补充事件,这时调度器将恢复线程的正常优先级。如果因为没有其它更高优先级的线程准备运行,那么该线程将能在背景优先级条件下运行,这样调度器将运行零星线程并且不在执行预算中扣除时间。

这些消耗和补充策略可确保在等于线程补充间隙的任何时间间隙内,线程只能执行所计算的预算时间那么长。因此,调度器将迫使线程的处理器利用率符合设计工程师的期望,并满足优化的速率单调静态优先级占先调度的假定条件。这样可以确保即使在系统过载条件下仍能保持可预测性。

为了更好地说明这些概念,图2描述的零星调度线程开始于8个单位的执行周期和12个单位的补充周期的预算。线程开始执行后,线程在阻塞之前先运行4个单位时间。调度器从预算中扣除4个单位时间,并在线程启动12个周期之后调度4个单位的补充线程。在线程再次阻塞之前,线程将无阻塞运行3个单位时间。调度器将这3个单位周期从预算中扣除,并在线程去阻塞12个单位周期之后调度3个单位周期的补充线程。第二次去阻塞后运行一个单位周期,此时调度器将检测到执行预算已经用完,并降低该线程的优先级。如果没有更高优先级的线程占先,那么该线程将能以背景优先级自由运行。

由于操作系统时间信号的分辨率限制了零星调度器的精确度,因此分辨率为10ms的低分辨率时钟时信号在毫秒级的线程周期和预算测量中很难得到好的效果。

应用实例

下面我们将通过考察网络接口控制器(NIC)设备驱动器的接收线程,研究如何在实际应用中利用零星调度策略。

在数据分组网络中,应用程序络通过连接到网络接口控制器的设备驱动器进行通信。这些控制器实现了物理介质通信协议中的物理层和数据链路层,从而提供节点至节点的无差错连接、协调不同传输介质并满足在介质中传输数据所需的物理和电气规范要求。网络设备驱动器至少包含一个用于接收作为中断服务一部分的分组数据的线程和另一发送分组数据的线程。

在设计中采用多节点通信媒体时,设计工程师首先必须进行如下假设:期望的媒体利用率、媒体带宽、分组数据包的平均大小和最坏条件下的大小,以及发往相连系统的分组数据之间的期望间隙。根据这些假设,设计工程师就能确定适当的周期、运算间隙和分组数据接收线程的优先级。

在我们的设计中需要将系统连接到100Mbps的网络、接收固定大小(64字节)的分组数据,每个分组数据包的处理时间为25ms并且每64ms接收一次分组数据。所选的NIC在每次接收分组数据时将中断主处理器,并带有一个32个记录的环形缓存。我们通过使环形缓存的占用量低于50%来防止数据包丢失。在一定的时间限制内处理所有的分组数据包只是一个目标,但必须不引发系统过载。为确保这一点,在不得已的情况下允许系统丢弃数据包。

在表1给出的要求下,我们创建了一个周期线程来处理分组数据接收,并为其指定一个根据优先级推导的速率,该速率基于其1,024ms的周期特性。为保证环形缓存的利用率低于50%,周期可设定为16×64μs,并且计算间隙为16×25μs。在我们的设计中,我们还采用了用极短中断异常处理程序的操作系统,并在设定优先级的线程中执行中断处理。

在设计中我意识到,如果入口速率超过每秒15,625个数据包,系统将进入过载状态。为防止这种情况出现,将接收线程的默认FIFO策略设定为零星调度策略,由此将处理器的高优先级利用率限制在期望的最坏条件值,即39%。通过将POSIX调度参数的属性初始化为期望的周期和执行预算,并在POSIX线程创建时传递这些属性值,即可实现上述目标。

零星调度策略可确保系统能经受异常的突发数据包的影响,丢弃过多的输入传输流,但仍然能满足比NIC接收处理器优先级更低的关键线程的时间约束。

列表1给出了为网络驱动程序分组数据接收线程配置零星调度策略的POSIX C代码。QNX操作系统中Realtek NIC设备驱动程序的完全实现可从以下网址下载:。

可预测性

零星调度可通过将非周期性和零星的事件和线程打包到一个周期性架构中进行管理。这是静态优先级占先调度器中进行过载预处理的一种有效方法。通过采用零星调度,线程就能避免在过载情形下出现不期望的信号抖动或使处理器无法处理低优先级线程。利用零星调度,我们就能对不可预知的系统进行预测分析。

如果希望在应用中集成零星调度处理,那么可以基于Ada95编程语言、QNX RTOS、符合实时Java规范(RTSJ)的Java虚拟机以及几种不同的实时Linux内核来实现。但是需要注意的是,并非所有的实现方法都完全符合POSIX 1003.1d规范。例如,RTSJ的零星调度策略既不采用C绑定,也不实现补充。Ada95实现则采用了POSIX 1003.5 Ada绑定。

作者:Lonnie VanZandt

顾问

Email: lonniev@