在现实世界中，存在一类应用场景，需要对监测到的事件作出实时的响应，也即当事件发生后，需要在一定截止期内执行合适的动作以完成某些任务或避免某些危险。错过截止期将造成灾难性的后果。在这样应用中，事件与动作之间的因果联系可以使用主动规则来描述。主动规则描述了当某些事件按照某种模式发生且某个条件为真时，某个动作应该被执行。针对监测到的事件，判断某条主动规则所描述的事件模式及条件是否满足，从而得出动作的过程，称为针对此条主动规则的推理过程。上述对持续发生的事件作出响应的过程，可以被视为针对一系列主动规则的推理过程的集合。

针对一条主动规则进行推理，从与此主动规则相关的最晚发生的事件的发生到根据主动规则推理得出动作之间的时间间隔，称为推理延迟。在时间关键的应用中，当事件发生后，为了使响应的动作在截止期内完成，动作需要在一定截止期内推理得出，因此，推理延迟需要满足时间约束。一个亟待解决的问题是，对于不断发生的事件，如何找到一种方式使得针对每一条主动规则进行推理的推理延迟都满足相对截止期的约束。

本文围绕应用中一类常见的场景——事件风暴场景中的上述问题展开研究。将针对一条主动规则的推理过程在处理器上的一次执行视为一个主动规则推理任务，为了解决上述问题，需要研究主动规则推理任务的实时调度算法以及可调度条件。首先，在事件风暴场景下，构成可调度条件需要估算主动规则推理任务集的最坏情况反应时间，因此，我们提出了一种基于整数线性规划的主动规则推理最坏反应时间估算方法。其次，我们研究了主动规则推理任务的实时调度问题，提出了主动规则推理任务集的一种启发式的调度算法。然后，我们研究了主动规则集的在线修改对可调度条件的影响，提出了包含推理任务和主动规则集修改任务的任务集的可调度条件。最后，在上述研究的基础上，实现了一个基于主动规则的实时推理系统。

本文的主要研究内容和创新点包括：

l  研究了事件风暴场景中的主动规则推理任务集的最坏情况反应时间估算问题，提出了一种结合算法逻辑分析的最坏情况反应时间估算方法，通过将最坏情况反应时间估算转换为整数线性规划问题，并通过对主动规则推理算法逻辑进行分析，归纳出更加严格的线性约束条件，从而提高估算的精确度。模拟实验表明，我们的最坏情况反应时间估算方法比传统的针对一般程序的估算方法将估算精度提高了1～2个数量级。

l  研究了事件风暴场景下的主动规则推理任务集的实时调度问题，提出了一种主动规则推理任务集的实时调度算法，通过建立规则图将推理任务分解为节点处理任务，并采用启发式算法对节点处理任务进行调度，使得能够得出动作的节点处理任务优先被执行。模拟实验表明，这种算法有效地增加了在截止期内推理得出的动作数量。

l  研究了主动规则集动态修改时的基于主动规则的实时推理问题。首先提出了一种规则图在线修改算法，保证推理任务执行结果的正确性不受到规则图在线修改的影响。其次，研究了包含推理任务和修改任务的任务集的可调度性判定问题。提出了上述任务集在不同情况下的可调度条件。

In some applications, when events occur, appropriate actions are required to be executed to complete tasks or avoid risks before a deadline. Missing a deadline may jeopardize the safety of the system. In these applications, relations among events and actions can be described in Event-Condition-Action (ECA) rules. An ECA rule describe that if some events match an event pattern and a condition is true, an action should be executed. The process of deciding whether the event pattern in an ECA rule is matched and whether the condition in the rule is true is called reasoning based on the ECA rule. Thus, in above applications, with ongoing events, reaction processes from events to actions can be considered as reasoning based on several ECA rules.

When reasoning based on an ECA rule is executed in CPU, there is elapse time from the last event associated with the rule is detected to the time that the action is triggered, called inference delay. In time-critical applications, execution of the action associated with an ECA rule has to complete before a deadline. Thus, the inference delay of the execution of reasoning should be not more than a relative deadline. With ongoing events, the goal is to find an approach to guarantee the inference delay of execution of each ECA rule not more than its relative deadline.

This thesis studied above problem in a common scenario, i.e. event storm. An execution of reasoning based on an ECA rule can be considered as a reasoning task. In order to solve the above problem, a scheduling algorithm and a schedulability test for a set of reasoning tasks should be researched. Firstly, in event storm, for construct schedulability test for the tasks, the worst-case response time (WCRT) of a set of reasoning tasks needs to be estimated. Thus, this thesis proposed a novel integer-linear-programming-based method for estimating the WCRT of the tasks. Secondly, in event storm, the problem to find a scheduling algorithm for reasoning tasks is transformed into an equivalent problem to find a scheduling algorithm for vertex-processing tasks. For this equivalent problem, this thesis proposed a heuristic scheduling algorithm. Thirdly, the effects of online modification of ECA rules on schedulability test are studied. Finally, a reasoning system based on ECA rules is introduced.

The principal innovations of this thesis mainly are:

l  Proposed a method with analysis of reasoning algorithm to estimate the WCRT of reasoning tasks. In the method, the WCRT is estimated by solving a relevant integer linear programming problem. In order to improve estimation precision, we analyzed reasoning algorithm and generate stricter linear constraints. Results of simulation indicate that our method improves estimation precisions by 1~2 orders of magnitude. In addition, we proposed a sufficient schedulability test for reasoning tasks with its WCRT.

l  Proposed a scheduling algorithm for reasoning tasks. In the alogorithm, reasoning tasks are divided to vertex-processing tasks, and we proposed a heuristic algorithm to schedule vertex-processing tasks. With the scheduling alogorithm, more actions can be triggered in the deadline. Results of simulation indicate that the algorithm increases the number of actions exported before a deadline.

l  Proposed an algorithm for online modification of ECA rules, and proposed schedulability tests for reasoning tasks and modification tasks.