静态实时中间件的优先级映射问题

The Priority Mapping Problem in Static Real-Time Middleware

使用截止期单调(DM)调度算法和分布式优先级冲顶资源访问控制协议(DPCP)的实时CORBA系统中,当节点的本地优先级个数不足时,必须将多个全局优先级映射成一个本地优先级.这需要:①判定映射后任务可调度性的充分必要条件;②减少时间复杂度的映射算法.为此,推导出判定条件,确定了DGPM映射算法.该算法在保证系统可调度的前提下分配任务,或者证明映射后系统不可调度.证明了DGPM算法能调度其他直序列优先级映射算法可调度的任务和GCS集合.判定条件和算法在实际项目中得到了应用.

The deadline monotonic （DM） priority assignment scheme and distributed priority ceiling resource access protocol （DPCP） work well with real-time CORBA. In practice, a potentially large number of global unique priorities must be mapped to the restricted number of local priorities provided by the operating systems. Most operating systems use first-in-first-out （FIFO） scheduling within the same priority. So, a high global priority task could be blocked by lower global priority tasks ahead of it in the local priority FIFO queue. This causes priority inversion and affects the schedulability of tasks with higher global priority. In addition, the optimal priority assignment requires a search of exponential complexity. This is the priority mapping problem. To solve it, necessary and sufficient conditions are presented for analyzing the schedulability of a task which global priority has been mapped to a local priority. The decreasing global priority mapping （DGPM） algorithm is also provided. It can schedule a task and global critical section （GCS） set that is schedulable under any other direct priority mapping algorithms. DGPM can overlap tasks （map two or more tasks to the same local priority） while not allowing the system to become non-schedulable, or prove that the system is no-schedulable after overlapping. The conditions and algorithm are used in the projects.