论文部分内容阅读
在现实世界中,存在一类应用场景,需要对监测到的事件作出实时的响应,也即当事件发生后,需要在一定截止期内执行合适的动作以完成某些任务或避免某些危险。错过截止期将造成灾难性的后果.在这样应用中,事件与动作之间的因果联系可以使用主动规则来描述。主动规则描述了当某些事件按照某种模式发生且某个条件为真时,某个动作应该被执行。针对监测到的事件,判断某条主动规则所描述的事件模式及条件是否满足,从而得出动作的过程,称为针对此条主动规则的推理过程。上述对持续发生的事件作出响应的过程,可以被视为针对一系列主动规则的推理过程的集合。针对一条主动规则进行推理,从与此主动规则相关的最晚发生的事件的发生到根据主动规则推理得出动作之间的时间间隔,称为推理延迟。在时间关键的应用中,当事件发生后,为了使响应的动作在截止期内完成,动作需要在一定截止期内推理得出,因此,推理延迟需要满足时间约束。一个亟待解决的问题是,对于不断发生的事件,如何找到一种方式使得针对每一条主动规则进行推理的推理延迟都满足相对截止期的约束。
本文围绕应用中一类常见的场景----事件风暴场景中的上述问题展开研究。将针对一条主动规则的推理过程在处理器上的一次执行视为一个主动规则推理任务,为了解决上述问题,需要研究主动规则推理任务的实时调度算法以及可调度条件.首先,在事件风暴场景下,构成可调度条件需要估算主动规则推理任务集的最坏情况反应时间,因此,我们提出了一种基于整数线性规划的主动规则推理最坏反应时间估算方法。其次,我们研究了主动规则推理任务的实时调度问题,提出了主动规则推理任务集的一种启发式的调度算法。然后,我们研究了主动规则集的在线修改对可调度条件的影响,提出了包含推理任务和主动规则集修改任务的任务集的可调度条件。最后,在上述研究的基础上,实现了一个基于主动规则的实时推理系统。主要研究内容和创新点包括:⑴研究了事件风暴场景中的主动规则推理任务集的最坏情况反应时间估算问题,提出了一种结合算法逻辑分析的最坏情况反应时间估算方法,通过将最坏情况反应时间估算转换为整数线性规划问题,并通过对主动规则推理算法逻辑进行分析,归纳出更加严格的线性约束条件,从而提高估算的精确度。模拟实验表明,我们的最坏情况反应时间估算方法比传统的针对一般程序的估算方法将估算精度提高了1~2个数量级。⑵研究了事件风暴场景下的主动规则推理任务集的实时调度问题,提出了一种主动规则推理任务集的实时调度算法,通过建立规则图将推理任务分解为节点处理任务,并采用启发式算法对节点处理任务进行调度,使得能够得出动作的节点处理任务优先被执行.模拟实验表明,这种算法有效地增加了在截止期内推理得出的动作数量。⑶研究了主动规则集动态修改时的基于主动规则的实时推理问题。首先提出了一种规则图在线修改算法,保证推理任务执行结果的正确性不受到规则图在线修改的影响。其次,研究了包含推理任务和修改任务的任务集的可调度性判定问题。提出了上述任务集在不同情况下的可调度条件。