基于系统实时事件驱动和时间驱动相结合的调度方法

　　引言

   　　目前，虚拟化操作系统（hypervisor）广泛应用于服务器、PC机等，这些应用领域对实时性要求较低。随着一些嵌入式实时应用领域的发展，比如下一代手机对安全性、应用聚合和云计算等方面的需求，需要采用虚拟化操作系统。传统的虚拟化操作系统很难满足这些应用领域的实时性要求。经过大量的测试与分析，发现虚拟化操作系统实时性差的主要源头之一是调度算法实时性不佳。有必要对虚拟化操作系统的调度方法进行实时性改造，使之可以应用于实时性要求较高的场合。本文提出了一种基于系统事件驱动和时间驱动相结合的实时调度方法，经实践表明，该方法有效地解决了虚拟化操作系统在嵌入式系统应用中带来的实时性问题。
   　　1 问题提出
   　　基于虚拟化操作系统（hypervisor），可以实现单CPU上多个操作系统（GueSTOS）在相互隔离的内存域（Domain）中同时运行。如图1所示，箭头表示调度。其中的系统调度采用二级调度策略，虚拟化操作系统对GuestOS（Domain）进行第一级调度，GuestOS对自身的任务进行第二级调度，系统的实时性响应很难保证。
   
   图1 虚拟化操作系统
   　　对于第一级调度（Domain调度），传统的调度策略都是基于时间片的调度方法（SEDF、BVT、ARR、Credit等），通常应用于实时性要求较低的场合（网络服务器等），对于实时性要求较高的场合（手机等），调度的实时性就很难满足系统要求。具体表现为：CPU利用率低、中断响应缓慢、GuestOS之间数据通信速率不足等。为了改进这些性能，必须设计一种新的满足实时性应用场合的调度方法。根据实际测试和分析，发现实时性响应差的主要瓶颈在于GuestOS不能够得到及时的调度。
   　　本文的方法主要对第一级调度策略进行改造，即改造虚拟化操作系统对GuestOS（Domain）的调度方法。
   　　2 解决方法
   　　本文的方法采用系统实时事件驱动Domain调度器的策略。当系统中有需要实时响应的紧急或重要事件发生时，这些事件有机会驱动Domain调度器产生调度行为，使之（紧急或重要事件）得到快速处理。当没有紧急或重要事件发生时，Domain调度器采用基于时间片（权重）的调度算法。
   　　2.1 调度原则
   　　图2表示了调度原则。图2中，系统硬件中断、GuestOS事件发送、Guest Idle之类的紧急或重要事件发生时，有机会通过强原则去驱动Domain调度器，切换Domain使之得到快速处理。当系统中没有紧急或重要事件发生时，Domain调度器通过弱原则进行调度（时间片等）。
   
   图2 调度原则
   　　2.2 实时性分析
   　　以中断处理为例分析中断响应时间，如图3所示。从图3中可以看到，原调度策略的中断响应时间包含：“等待Domain调度时间片结束” + “Doamin切换”。新的调度策略，仅包含“Doamin切换”时间。可见，采用新的策略，中断的实时性响应得到了提高。
   
   图3 中断实时响应分析
   
   　　虚拟操作系统应用中常会有以下3类事件的实时响应需要考虑：
   　　0类事件--底层硬件中断需要得到上层某个Domain的快速响应处理；
   　　1类事件--Domain（GuestOS）之间的通信事件需要被另一个Doamin快速处理；
   　　2 类事件--Domain（GuetOS）中的任务空闲时，主动放弃CPU，通知Domain调度器使其他Domain（GuestOS）得到运行机会。
   　　这些事件的实时性响应时间分析和中断响应类似。
   　　在本方法中，如图4所示，上述的3类事件都以设置触发事件的形式驱动Domain调度器，Domain调度器可以根据这些事件组合、当前的GuestOS状态组合、当前的Domain调度状态来产生调度决策。
   　　2.3 方法实施
   　　2.3.1 事件定义
   　　本方法具体实现时，根据实时系统的具体应用情况，首先定义出紧急/重要事件（需要引发调度才能满足实时响应要求的事件），并按照2.2节所述的3类实时事件划分，对其分类并设计优先级排序。0类事件优先级最高，1类事件优先级居中，2类事件优先级最低，每类事件自身也按照优先级排序。
   　　2.3.2 状态定义
   　　然后，根据系统设计和运行情况列出Domain状态组合、GuestOS状态组合，如表1、表2所列。最后，根据系统运行要求，设计出驱动事件调度查询表，如表3所列。
   　　表1给出了GuestOS运行状态组合，表示每个guestOS中的任务运行情况。每个GuestOS可以处于Run或Idle两个状态，多个GuestOS的状态组合起来（本文用2个GuestOS说明），就可以制作出GuestOS的状态组合表。
   表1 GuestOS状态组合
   
   
   图4 基于事件驱动的实时调度方法
   表2 Domain状态组合
   
   　　表2表示了Domain状态组合。表示Domain调度器的调度情况，每个Domain可以处于Run或Ready两个状态，多个Domain的状态组合起来（本文采用2个Domain），就可以制作出Doamin的状态组合表。
   表3 调度查询表
   
   
   　　表3是调度查询表。调度触发事件可以通过它查询到下一个需要被调度运行的GuestOS.它是一个二维的数组，其中列的维度由调度触发事件表示，优先级从高向低排列，另一个行的维度由GuestOS状态组合表示，包含表1的所有GuestOS状态组合。通过这两个维度的输入，可以查询到预期的需要被调度的GuestOS（Domain），作为调度器下一次调度决策的输入。
   　　2.3.3 事件置位与清除规则
   　　2.2节图4中表示了调度事件置位和清除规则，说明了3种类型的调度触发事件是如何设置和清除的。
   　　事件置位和清除规则时序如图5所示。图5表示了3种类型的调度触发事件的设置和清除时机，以及事件驱动策略和时间片驱动策略的切换时机，其中S_timer的关闭/打开分别表示开始事件驱动调度/开始时间片驱动调度。图中有5种事件置位/清除操作，其中虚线箭头表示的5种操作是在GuestOS中进行的，需要采用超级调用（hypercall）实现，其中的硬件中断事件置位操作（实线箭头）是在虚拟化操作系统特权空间中进行的，可以直接操作。
   　　2.3.4 事件优先级处理策略
   　　当调度触发事件到来时，首先设置事件标识位，然后去检查各类事件组中的标识位。如果有更高优先级的事件存在，返回；如果没有，再检查自己是否是第一个触发事件。如果是，关闭时间片驱动调度策略，开始事件驱动调度策略 （关闭S_timer），然后去查询事件驱动调度表，对比当前Domain判断是否需要产生调度。
   　　当调度触发事件响应处理完成后，需要调用hypercall清除，清除该事件的标识位后，要先去检查一下是否有比自己优先级低的事件存在。如果有，就去处理它，查询事件驱动调度表，判断是否需要产生新的调度；如果没有比自己优先级低的事件的存在，表示事件组中没有其他事件存在了，启动事件片调度策略，结束事件驱动调度策略 （打开S_timer）。
   
   图5 事件置位和清除规则时序图
   　　3 测试结果与分析
   　　3.1 测试结果
   　　硬件测试环境：ARM926EJ?S、主频226 MHz、64 MB SDRAM、I/D Cache 16 KB/16 KB enable、MMU enable.软件平台：自研虚拟化操作系统（基于Xen）、Threadx、Linux（参考图1）。测试软件采用LMBench，以及根据实际应用场景设计的大量测试用例。
   　　对本文提出的调度方法和常用的BVT调度算法进行对比测试，测试结果表明系统的实时性响应和系统的运行性能都有较大幅度的提升。根据对大量测试数据的统计，得到以下3个结果：
   　　① GuestOS系统运行性能的平均加速比为：threadx 1.82，Linux 1.94.
   　　② 中断响应加速比为：单个GuestOS运行时为8?474，两个GuestOS同时运行时为15.6015.且响应时间平稳，有良好的可预测性。
   　　③ GuestOS之间的数据通信速度加速比为12.51，且速率稳定。
   　　3.2 测试分析
   　　经过实践应用表明，本文提出的方法有效地解决了虚拟化操作系统传统调度方法带来的CPU利用率低、中断响应缓慢、操作系统（GuestOS）之间数据通信速度慢等问题。