共享资源约束下的多核实时调度算法研究
发布时间：2018-07-24 18:54
【摘要】：随着计算机系统结构的发展,多核并行已成为当今计算机系统发展的主流。与此同时,随着众多嵌入式系统实时性需求的日益增长,越来越多的实时系统将建立在多核/多处理器平台之上。在多核实时系统中,任务调度与同步是保障系统实时性的关键。其中,实时调度算法,实时锁协议(Real-Time Locking Protocols)以及可调度性分析(Schedulability Analysis)是确保系统实时性的基础与核心技术。为了在满足实时性约束的前提下充分发挥多核平台的计算能力,需要采用准确而高效的可调度性分析方法,同时需要对任务调度与资源共享进行协同优化。然而,已有研究中实时调度算法研究往往假设任务相互独立,因而没有充分明确考虑共享资源约束。相反,实时锁协议研究往往专注于锁协议规则设计与任务阻塞时间分析,而缺乏对整体系统的可调度性研究。如何改进共享资源约束下的可调度性分析,以及如何优化共享资源约束下的任务调度是当前多核实时系统研究领域的重点和难点问题。基于以上背景,本文围绕共享资源约束下的多核实时调度问题,对多核实时调度算法,实时锁协议,以及可调度性分析技术进行系统性研究。本文研究旨在突破共享资源约束下多核实时调度的基础理论难题,为构建高效的多核实时系统提供理论支撑。本文主要研究内容及贡献如下。(1)指出了经典多处理器实时锁协议分析中存在的两个基础性错误,并给出了更正方法。针对经典多处理器实时锁协议DPCP(Distributed Priority Ceiling Protocol)和MPCP(Multiprocessor Priority Ceiling Protocol),指出了原始文献中的任务最坏阻塞时间分析错误。同时,指出了近年来在多处理器分组固定优先级(Partitioned Fixed-Priority)调度与信号量实时锁协议分析中存在的最坏响应时间(Worst-Case Response Time)分析错误。随后,分别分析了产生错误的原因,错误所造成的影响以及更正这些错误的方法。(2)针对全局固定优先级(Global Fixed-Priority)调度与信号量实时锁协议,提出了一种新的任务最坏响应时间分析方法,并对该调度机制下的主流实时锁协议进行了详细分析与总结。根据全局固定优先级调度下任务执行的一般性特征,准确定义了6类任务延迟,并提出了任务最坏响应时间分析的一般性框架。基于该分析框架,提出了通过线性规划分析任务最坏响应时间的一般性方法。该方法可用于全局固定优先级调度下所有主流信号量实时锁协议的可调度性分析。实验结果显示,新分析方法的可调度性明显高于已有分析方法。此外,进行了大规模可调度性实验,首次对全局固定优先级调度下的主流信号量实时锁协议进行统一的比较分析。分析结果显示,全局固定优先级调度中传统的优先级继承协议(Priority Inheritance Protocol,PIP)和最简单的FMLP (Flexible Multiprocessor Locking Protocol)协议的可调度率最高。(3)针对分组固定优先级调度与信号量实时锁协议,提出了一种新的任务最坏阻塞时间分析方法。基于任务结构模型,提出了一种任务临界区执行时间分析方法。该方法能够准确计算任务在任意时间内使用共享资源的最大时间,提高了任务最坏阻塞时间分析的准确性。同时,结合MPCP协议提出了一种新的任务最坏响应时间分析方法。实验分析显示,新分析方法的可调度性高于已有分析方法。(4)针对自旋锁协议,提出了一种共享资源敏感的分组固定优先级调度算法。针对非抢占FIFO自旋锁机制,提出了一种衡量任务相关性的评价方法,并提出了一种衡量系统利用率损失的评价方法。基于这两种评价方法,提出了一种新的多核任务分配算法。实验分析显示,新算法调度给定任务系统所需的处理器数少于已有的同类调度算法。此外,分析证明了负载非均衡“装箱”(Bin-Packing)启发式任务分配算法存在远程冲突问题,揭示了采用这类算法进行任务分配存在的潜在问题。(5)针对多核固定优先级调度,提出了一种资源优先分组调度算法。该算法使用共享资源代理实现资源共享,将共享资源调度与任务调度进行分布式管理。理论分析证明,在任务最多包含一个临界区的情况下算法具有加速因子(Speedup Factor) 11 - 6/(m+1),其中m为处理器核数。该算法是共享资源约束下目前加速因子最小且唯一确保常数加速因子的多核实时调度算法。实验分析显示,在任务具有多个临界区的情况下该算法的可调度率仍高于同类算法。所提出的算法解决了实时调度领域长期未解的一个基础理论难题,为多核／众核环境下的实时调度算法研究提供了新的研究思路。
[Abstract]:With the development of computer system structure, multi core parallel has become the mainstream of the development of computer system. At the same time, with the increasing demand of the real time of many embedded systems, more and more real-time systems will be built on the multi core / multi processor platform. In the multi verifying time system, task scheduling and synchronization are the guarantee system. The real-time scheduling algorithm, the real-time lock protocol (Real-Time Locking Protocols) and the schedulability analysis (Schedulability Analysis) are the basic and core technologies to ensure the real-time performance of the system. In order to give full play to the computing power of the multi core platform under the premise of satisfying the real-time constraints, it needs to be accurate and efficient. The schedulability analysis method requires cooperative optimization of task scheduling and resource sharing. However, the research of real-time scheduling algorithms in the existing research often assumes that tasks are independent of each other, so that the shared resource constraints are not fully considered. On the contrary, the research of real-time lock protocols often focuses on the design of the lock protocol rules and the time of the task blocking. Analysis, and lack of schedulability for the overall system. How to improve the schedulability analysis under shared resource constraints and how to optimize task scheduling under shared resource constraints is the key and difficult problem in the current research field of multi-core real-time systems. Based on the above background, this paper focuses on multi-core real-time scheduling under the constraints of shared resources. The problem is to systematically study the multi-core real-time scheduling algorithm, real-time lock protocol, and schedulability analysis technology. This paper aims to break through the basic theoretical problems of multi-core real-time scheduling under shared resource constraints, and provide theoretical support for the construction of efficient multi-core real-time systems. The main contents and contributions of this paper are as follows. (1) point out the following. Two basic errors in the analysis of the canonical multiprocessor real-time lock protocol and the correction method are given. The worst blocking time analysis error in the original document is pointed out for the classic multi processor real-time lock protocol DPCP (Distributed Priority Ceiling Protocol) and MPCP (Multiprocessor Priority Ceiling Protocol). This paper points out the worst response time (Worst-Case Response Time) analysis errors in the analysis of the Partitioned Fixed-Priority scheduling and the signal quantity real-time lock protocol analysis in recent years. Then, the causes of the errors, the effects of the errors and the methods to correct these errors are analyzed. (2) (2) In this paper, a new method for the worst response time analysis of the global fixed priority (Global Fixed-Priority) scheduling and semaphore real-time locking is proposed, and the mainstream real time lock protocol under the scheduling mechanism is analyzed and summarized in detail. The general characteristics of the task execution under the global fixed priority scheduling are defined and the exact definition is defined. 6 types of tasks are delayed, and a general framework for the worst response time analysis is proposed. Based on the analysis framework, a general method is proposed to analyze the worst response time of the task through linear programming. This method can be used for the schedulability analysis of all the main traffic signal time lock protocols under the global fixed priority scheduling. It shows that the schedulability of the new analysis method is obviously higher than that of the existing analysis methods. In addition, a large-scale scheduling experiment is carried out, and a unified comparison and analysis of the mainstream signal real-time lock protocol under the global fixed priority scheduling is first compared for the first time. The analysis results show that the traditional priority inheritance protocol in the global fixed first level scheduling (Priorit Y Inheritance Protocol, PIP) and the simplest FMLP (Flexible Multiprocessor Locking Protocol) protocol have the highest schedulability. (3) a new task worst blocking time analysis method is proposed for the packet fixed priority scheduling and the signal traffic real time lock protocol. A task critical area implementation is proposed based on the task structure model. The method of row time analysis. This method can accurately calculate the maximum time of the task to use shared resources at any time and improve the accuracy of the worst blocking time analysis of the task. At the same time, a new method of the worst response time analysis is proposed with the MPCP protocol. There are analysis methods. (4) in view of the spin lock protocol, a shared resource sensitive packet fixed priority scheduling algorithm is proposed. In view of the non preemptive FIFO spin lock mechanism, a method of evaluating the task correlation is proposed, and an evaluation method for measuring the loss of the system utilization ratio is proposed. Based on these two evaluation methods, a new method is proposed. The experimental analysis shows that the number of processors required for the scheduling of a given task system is less than the existing scheduling algorithm. Furthermore, the analysis shows that the load non equilibrium "packing" (Bin-Packing) heuristic task allocation algorithm has a remote impulse problem, and reveals the use of this kind of algorithm for task division. (5) a resource priority packet scheduling algorithm is proposed for multi core fixed priority scheduling. The algorithm uses shared resource agents to share resources, and distributive management of shared resource scheduling and task scheduling. The theoretical analysis shows that the algorithm has a critical area at most in the case of the task. The acceleration factor (Speedup Factor) 11 - 6/ (m+1) is the kernel number of the processor. The algorithm is a multi-core real-time scheduling algorithm with the minimum acceleration factor and the only constant acceleration factor under the shared resource constraints. The experimental analysis shows that the scheduling rate of the algorithm is still higher than that of the same algorithm under the condition of multiple critical areas. The proposed algorithm solves a basic theoretical problem that has not been solved for a long time in the field of real-time scheduling, and provides a new research idea for the research of real-time scheduling algorithms in the multi-core / public kernel environment.
【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP301.6
，
本文编号：2142321
[Abstract]:With the development of computer system structure, multi core parallel has become the mainstream of the development of computer system. At the same time, with the increasing demand of the real time of many embedded systems, more and more real-time systems will be built on the multi core / multi processor platform. In the multi verifying time system, task scheduling and synchronization are the guarantee system. The real-time scheduling algorithm, the real-time lock protocol (Real-Time Locking Protocols) and the schedulability analysis (Schedulability Analysis) are the basic and core technologies to ensure the real-time performance of the system. In order to give full play to the computing power of the multi core platform under the premise of satisfying the real-time constraints, it needs to be accurate and efficient. The schedulability analysis method requires cooperative optimization of task scheduling and resource sharing. However, the research of real-time scheduling algorithms in the existing research often assumes that tasks are independent of each other, so that the shared resource constraints are not fully considered. On the contrary, the research of real-time lock protocols often focuses on the design of the lock protocol rules and the time of the task blocking. Analysis, and lack of schedulability for the overall system. How to improve the schedulability analysis under shared resource constraints and how to optimize task scheduling under shared resource constraints is the key and difficult problem in the current research field of multi-core real-time systems. Based on the above background, this paper focuses on multi-core real-time scheduling under the constraints of shared resources. The problem is to systematically study the multi-core real-time scheduling algorithm, real-time lock protocol, and schedulability analysis technology. This paper aims to break through the basic theoretical problems of multi-core real-time scheduling under shared resource constraints, and provide theoretical support for the construction of efficient multi-core real-time systems. The main contents and contributions of this paper are as follows. (1) point out the following. Two basic errors in the analysis of the canonical multiprocessor real-time lock protocol and the correction method are given. The worst blocking time analysis error in the original document is pointed out for the classic multi processor real-time lock protocol DPCP (Distributed Priority Ceiling Protocol) and MPCP (Multiprocessor Priority Ceiling Protocol). This paper points out the worst response time (Worst-Case Response Time) analysis errors in the analysis of the Partitioned Fixed-Priority scheduling and the signal quantity real-time lock protocol analysis in recent years. Then, the causes of the errors, the effects of the errors and the methods to correct these errors are analyzed. (2) (2) In this paper, a new method for the worst response time analysis of the global fixed priority (Global Fixed-Priority) scheduling and semaphore real-time locking is proposed, and the mainstream real time lock protocol under the scheduling mechanism is analyzed and summarized in detail. The general characteristics of the task execution under the global fixed priority scheduling are defined and the exact definition is defined. 6 types of tasks are delayed, and a general framework for the worst response time analysis is proposed. Based on the analysis framework, a general method is proposed to analyze the worst response time of the task through linear programming. This method can be used for the schedulability analysis of all the main traffic signal time lock protocols under the global fixed priority scheduling. It shows that the schedulability of the new analysis method is obviously higher than that of the existing analysis methods. In addition, a large-scale scheduling experiment is carried out, and a unified comparison and analysis of the mainstream signal real-time lock protocol under the global fixed priority scheduling is first compared for the first time. The analysis results show that the traditional priority inheritance protocol in the global fixed first level scheduling (Priorit Y Inheritance Protocol, PIP) and the simplest FMLP (Flexible Multiprocessor Locking Protocol) protocol have the highest schedulability. (3) a new task worst blocking time analysis method is proposed for the packet fixed priority scheduling and the signal traffic real time lock protocol. A task critical area implementation is proposed based on the task structure model. The method of row time analysis. This method can accurately calculate the maximum time of the task to use shared resources at any time and improve the accuracy of the worst blocking time analysis of the task. At the same time, a new method of the worst response time analysis is proposed with the MPCP protocol. There are analysis methods. (4) in view of the spin lock protocol, a shared resource sensitive packet fixed priority scheduling algorithm is proposed. In view of the non preemptive FIFO spin lock mechanism, a method of evaluating the task correlation is proposed, and an evaluation method for measuring the loss of the system utilization ratio is proposed. Based on these two evaluation methods, a new method is proposed. The experimental analysis shows that the number of processors required for the scheduling of a given task system is less than the existing scheduling algorithm. Furthermore, the analysis shows that the load non equilibrium "packing" (Bin-Packing) heuristic task allocation algorithm has a remote impulse problem, and reveals the use of this kind of algorithm for task division. (5) a resource priority packet scheduling algorithm is proposed for multi core fixed priority scheduling. The algorithm uses shared resource agents to share resources, and distributive management of shared resource scheduling and task scheduling. The theoretical analysis shows that the algorithm has a critical area at most in the case of the task. The acceleration factor (Speedup Factor) 11 - 6/ (m+1) is the kernel number of the processor. The algorithm is a multi-core real-time scheduling algorithm with the minimum acceleration factor and the only constant acceleration factor under the shared resource constraints. The experimental analysis shows that the scheduling rate of the algorithm is still higher than that of the same algorithm under the condition of multiple critical areas. The proposed algorithm solves a basic theoretical problem that has not been solved for a long time in the field of real-time scheduling, and provides a new research idea for the research of real-time scheduling algorithms in the multi-core / public kernel environment.
【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP301.6
，
本文编号：2142321
本文链接：https://www.wllwen.com/shoufeilunwen/xxkjbs/2142321.html
