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