Abstract: The scheduling strategies and schedulability conditions of RM(Rate Monotonic) tasks allocation algorithms were analyzed, and the actions that how the tasks allocation algorithms allocate the task to processors were depicted in detail based on the model of preemptive period task in multiprocessor system. According to the theory of Liu & Layland, the theory of the minimum utilization bound for task allocation algorithm was presented. The results of simulation show that the utilization bound of allocation algorithm is the key principle for differently characterized task sets to select different algorithms to allocate tasks. Through the comparison between the total utilization of the task set and the utilization bound of the algorithm, it can be judged whether the algorithm will bring out feasible allocation of the task set.

Key words: rate monotonic, tasks allocation, schedulability, utilization bound

摘要： 通过对单调速率任务分配算法调度策略和可调度条件的分析，在多处理器周期任务抢占调度模型基础上，细致刻画了任务分配算法如何分配任务的行为。依据Liu和Layland定理，给出多处理器下任务分配算法的最小RM利用率界的定理。仿真结果表明，分配算法的利用率界是不同特征任务集选择不同分配算法进行任务划分的关键，通过对任务集总利用率与算法利用率界的比较,判断使用该算法对任务集是否可以产生可行分配。

关键词: 速率单调, 任务分配, 可调度性, 利用率界