实时任务准入控制器的自动合成（英文）

Synthesis of Timed Admission Controllers

在许多实时系统中,同一个计算平台上往往既有硬实时关键计算任务又有软实时非关键计算任务。硬实时任务必须在规定时间内完成,否则将导致系统错乱或崩溃等严重后果。而软实时任务若没有在规定时间内完成,虽会影响系统性能,但不会造成重大后果。为确保每个硬实时任务均在其规定时间内完成,在某些情况下需要拒绝一些软实时任务进入任务队列。文章提出了一种基于控制器自动合成策略的解决方案,通过所设计的准入控制器,对系统产生的每一个新任务自动决定是否准其进入任务队列。准入控制器必须使得所有被准入的任务均在规定时间内完成,并且决策序列满足以线性时态逻辑描述的服务质量要求。文章的主要贡献是提出了判定是否存在准入控制器的算法,该算法能在判定结果为真时构造出一个以有限状态时间自动机表达的准入控制器。

In many real-time computing environments, there are some tasks that are time-critical while others are not. To ensure that every critical task can be completed before its deadline, it is necessary to reject some non-critical tasks to entry into the ready queue. We address this problem in the framework of controller synthesis. Our goal is to come up with an admission controller which admits or rejects a task request. With such a controller, no admitted tasks will miss their deadline and the admitted patterns of task releases satisfy a quality-of-service constraint in the form of a linear time temporal logic specification. We prove that it is decidable to determine if such an admission controller exists. Furthermore, if the answer is positive, it is possible to effectively construct a controller in the form of a finite timed controller.