共享資源約束下的多核實時調度算法研究
發(fā)布時間：2018-07-24 18:54
【摘要】：隨著計算機系統(tǒng)結構的發(fā)展,多核并行已成為當今計算機系統(tǒng)發(fā)展的主流。與此同時,隨著眾多嵌入式系統(tǒng)實時性需求的日益增長,越來越多的實時系統(tǒng)將建立在多核/多處理器平臺之上。在多核實時系統(tǒng)中,任務調度與同步是保障系統(tǒng)實時性的關鍵。其中,實時調度算法,實時鎖協(xié)議(Real-Time Locking Protocols)以及可調度性分析(Schedulability Analysis)是確保系統(tǒng)實時性的基礎與核心技術。為了在滿足實時性約束的前提下充分發(fā)揮多核平臺的計算能力,需要采用準確而高效的可調度性分析方法,同時需要對任務調度與資源共享進行協(xié)同優(yōu)化。然而,已有研究中實時調度算法研究往往假設任務相互獨立,因而沒有充分明確考慮共享資源約束。相反,實時鎖協(xié)議研究往往專注于鎖協(xié)議規(guī)則設計與任務阻塞時間分析,而缺乏對整體系統(tǒng)的可調度性研究。如何改進共享資源約束下的可調度性分析,以及如何優(yōu)化共享資源約束下的任務調度是當前多核實時系統(tǒng)研究領域的重點和難點問題�；谝陨媳尘�,本文圍繞共享資源約束下的多核實時調度問題,對多核實時調度算法,實時鎖協(xié)議,以及可調度性分析技術進行系統(tǒng)性研究。本文研究旨在突破共享資源約束下多核實時調度的基礎理論難題,為構建高效的多核實時系統(tǒng)提供理論支撐。本文主要研究內容及貢獻如下。(1)指出了經典多處理器實時鎖協(xié)議分析中存在的兩個基礎性錯誤,并給出了更正方法。針對經典多處理器實時鎖協(xié)議DPCP(Distributed Priority Ceiling Protocol)和MPCP(Multiprocessor Priority Ceiling Protocol),指出了原始文獻中的任務最壞阻塞時間分析錯誤。同時,指出了近年來在多處理器分組固定優(yōu)先級(Partitioned Fixed-Priority)調度與信號量實時鎖協(xié)議分析中存在的最壞響應時間(Worst-Case Response Time)分析錯誤。隨后,分別分析了產生錯誤的原因,錯誤所造成的影響以及更正這些錯誤的方法。(2)針對全局固定優(yōu)先級(Global Fixed-Priority)調度與信號量實時鎖協(xié)議,提出了一種新的任務最壞響應時間分析方法,并對該調度機制下的主流實時鎖協(xié)議進行了詳細分析與總結。根據全局固定優(yōu)先級調度下任務執(zhí)行的一般性特征,準確定義了6類任務延遲,并提出了任務最壞響應時間分析的一般性框架�；谠摲治隹蚣�,提出了通過線性規(guī)劃分析任務最壞響應時間的一般性方法。該方法可用于全局固定優(yōu)先級調度下所有主流信號量實時鎖協(xié)議的可調度性分析。實驗結果顯示,新分析方法的可調度性明顯高于已有分析方法。此外,進行了大規(guī)�？烧{度性實驗,首次對全局固定優(yōu)先級調度下的主流信號量實時鎖協(xié)議進行統(tǒng)一的比較分析。分析結果顯示,全局固定優(yōu)先級調度中傳統(tǒng)的優(yōu)先級繼承協(xié)議(Priority Inheritance Protocol,PIP)和最簡單的FMLP (Flexible Multiprocessor Locking Protocol)協(xié)議的可調度率最高。(3)針對分組固定優(yōu)先級調度與信號量實時鎖協(xié)議,提出了一種新的任務最壞阻塞時間分析方法。基于任務結構模型,提出了一種任務臨界區(qū)執(zhí)行時間分析方法。該方法能夠準確計算任務在任意時間內使用共享資源的最大時間,提高了任務最壞阻塞時間分析的準確性。同時,結合MPCP協(xié)議提出了一種新的任務最壞響應時間分析方法。實驗分析顯示,新分析方法的可調度性高于已有分析方法。(4)針對自旋鎖協(xié)議,提出了一種共享資源敏感的分組固定優(yōu)先級調度算法。針對非搶占FIFO自旋鎖機制,提出了一種衡量任務相關性的評價方法,并提出了一種衡量系統(tǒng)利用率損失的評價方法。基于這兩種評價方法,提出了一種新的多核任務分配算法。實驗分析顯示,新算法調度給定任務系統(tǒng)所需的處理器數少于已有的同類調度算法。此外,分析證明了負載非均衡“裝箱”(Bin-Packing)啟發(fā)式任務分配算法存在遠程沖突問題,揭示了采用這類算法進行任務分配存在的潛在問題。(5)針對多核固定優(yōu)先級調度,提出了一種資源優(yōu)先分組調度算法。該算法使用共享資源代理實現(xiàn)資源共享,將共享資源調度與任務調度進行分布式管理。理論分析證明,在任務最多包含一個臨界區(qū)的情況下算法具有加速因子(Speedup Factor) 11 - 6/(m+1),其中m為處理器核數。該算法是共享資源約束下目前加速因子最小且唯一確保常數加速因子的多核實時調度算法。實驗分析顯示,在任務具有多個臨界區(qū)的情況下該算法的可調度率仍高于同類算法。所提出的算法解決了實時調度領域長期未解的一個基礎理論難題,為多核／眾核環(huán)境下的實時調度算法研究提供了新的研究思路。
[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
本文鏈接：http://www.wukwdryxk.cn/shoufeilunwen/xxkjbs/2142321.html
最近更新
教材專著
