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

提出了一种基于系统实时事件驱动和时间驱动相结合的调度方法，可以对虚拟化操作系统进行实时性改造，改进其调度算法的实时性，满足虚拟化操作系统在嵌入式实时系统中的应用。实际改进测试表明，虚拟化操作系统的实时性能有较大幅度提升，能够满足嵌入式系统虚拟化的实时性需要。

引言

目前，虚拟化操作系统（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基于事件驱动的实时调度方法