多处理器单调速率任务调度算法研究

发布时间：2018-03-23 09:19

本文选题：实时系统　切入点：双曲线边界　出处：《东华大学》2012年硕士论文　论文类型：学位论文

【摘要】：实时系统是计算机科学的一个重要领域,这类系统目前广泛的应用于生产生活中。随着多核/多处理器系统在实时应用中的日益普及,多处理器实时系统的研究成为当前的热点。可调度性判定边界的研究是多处理器实时系统领域的一个重要方面,确立多处理器可调度判定边界具有理论和应用上的双重意义。提高可调度性判定边界能够提高多处理器实时系统中处理器的利用率,从而提高多处理器实时系统的应用效率。 Lopez等学者求解出基于单调速率算法,LL判定边界(C.L.Liu提出的基于单调速率算法的单处理器判定边界),RAD分派策略的多处理器实时任务可调度性判定边界,并给出了相关的证明和分析。据我们所知这是目前最好的多处理器实时任务的可调度性判定边界。在单处理器领域,Bini等学者提出的双曲线可调度性判定边界,并证明了该边界全面优于LL边界。由于双曲线边界相对于LL边界的优势,本文基于双曲线边界对多处理器可调度性判定边界进行了研究。本文的主要工作包括： 1.本文基于双曲线可调度判定边界,RAD任务分派策略,单调速率算法给出了多处理器实时任务新的可调度性判定边界,通过理论证明的形式验证了新边界的充分性和必要性。 2.分析了新边界的性能,通过理论上的推导和大规模实验全面系统的比较了新旧边界。虽然新边界无法全面超越旧边界,但新旧边界具有相容性。实验结果表明在任何参数条件下联合使用两种边界能够显著提高可调度任务集的数量。
[Abstract]:Real-time system is an important field of computer science, which is widely used in production and life. With the increasing popularity of multi-core / multiprocessor systems in real-time applications, The research of multiprocessor real-time systems has become a hot topic. The research of schedulability decision boundary is an important aspect in the field of multiprocessor real-time systems. It is of double significance in theory and application to establish the multi-processor schedulable decision boundary. Improving the schedulability decision boundary can improve the utilization rate of processors in multiprocessor real-time systems and thus improve the application efficiency of multi-processor real-time systems. Lopez and other scholars have solved the multi-processor real-time task schedulability decision boundary based on monotone rate algorithm based on monotone rate algorithm and the monotone rate algorithm proposed by C.L. Liu. It is known to us that this is the best schedulability decision boundary for multiprocessor real-time tasks. The hyperbolic schedulability decision boundary proposed by Bini et al. It is proved that this boundary is superior to LL boundary completely. Because hyperbolic boundary is superior to LL boundary, this paper studies the decision boundary of multiprocessor schedulability based on hyperbolic boundary. The main work of this paper includes:. 1. Based on the hyperbolic schedulable decision boundary (RAD) task allocation strategy, the monotone rate algorithm gives a new schedulability decision boundary for multiprocessor real-time tasks, and proves the adequacy and necessity of the new boundary by the form of theoretical proof. 2. The performance of the new boundary is analyzed, and the new boundary is compared systematically with the theoretical derivation and the large-scale experiment, although the new boundary can not completely exceed the old boundary. However, the new and old boundaries are compatible. The experimental results show that the number of schedulable task sets can be significantly increased by using the two kinds of boundaries under any parameters.
【学位授予单位】：东华大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP332

【参考文献】