Prevention of task overruns in real-time non-preemptive multiprogramming systems
Prevention of task overruns in real-time non-preemptive multiprogramming systems
复制标题
防止实时非抢占式多道程序设计系统中的任务溢出
DOI：
--
复制
发表时间：
1980
期刊：
影响因子：
--
通讯作者：
Mahmoud Naghibzadeh
中科院分区：
文献类型：
--
作者：
K. Kim;Mahmoud Naghibzadeh
考虑了实时多道程序设计系统，其中一个硬件处理器被动态分配来运行多个软件进程，每个进程被设计用来控制一个重要的设备（用户）。每个软件进程执行一个任务，以响应来自相应用户的重复服务请求。每个服务任务都与严格的截止日期相关联，因此我们关心的设计问题是确保所请求的服务任务始终能够在相关的截止日期内执行，即不会发生任务超时。针对采用抢占调度策略的情况，一些研究者对这个问题进行了研究。相比之下，对非抢占调度的研究很少。在本文中，我们证明了一种称为相对紧迫性非抢占（RUNP）策略的非抢占策略是最优的，因为如果系统在任何一种非抢占策略下运行时没有任务溢出，那么在RUNP策略下也不会出现任务溢出。在此基础上，提出了一种在设计时使用RUNP策略检测系统中任务溢出可能性的有效方法。这个过程对于设计无溢出的实时多路程序设计系统是有用的，可以产生高处理器利用率。还讨论了使用RUNP策略的一些特殊类型的系统，这些系统甚至可以使用更简单的检测程序。
Real-time multiprogramming systems, in which a hardware processor is dynamically assigned to run multiple software processes each designed to control an important device (user), are considered. Each software process executes a task in response to a service request repeatedly coming from the corresponding user. Each service task is associated with a strict deadline, and thus the design problem that we are concerned with is to ensure that the service tasks requested can always be executed within the associated deadlines, i.e., no task overrun occurs. This problem was studied by several investigators for the cases where preemptive scheduling strategies are used. In contrast, very few studies have been conducted for cases of non-preemptive scheduling. In this paper we show that a non-preemptive strategy, called relative urgency non-preemptive (RUNP) strategy, is optimal in the sense that if a system runs without a task overrun under any non-preemptive strategy, it will also run without a task overrun under the RUNP strategy. Then an efficient procedure used at the design time for detecting the possibility of a task overrun in a system using the RUNP strategy is presented. The procedure is useful in designing overrun-free real-time multiprogramming systems that yield high processor utilizations. Some special types of systems using the RUNP strategy for which even simpler detection procedures are available are also discussed.