【摘要】：近年來，實時系統(tǒng)被廣泛地應(yīng)用到安全關(guān)鍵的汽車電子領(lǐng)域。除保證實時應(yīng)用輸出結(jié)果的邏輯正確性外，還必須具有嚴格的時間確定性和高度的可靠性，否則會導致嚴重后果。然而隨著應(yīng)用需求的擴展，當前實時系統(tǒng)應(yīng)用軟件朝著大規(guī)模、高復雜度的方向發(fā)展，其安全性與可靠性問題變得日益突出。如何利用容錯技術(shù)，，使實時系統(tǒng)在出錯后行為可控是十分必要的。 本文對分層實時調(diào)度框架進行了研究，詳細分析實時系統(tǒng)中廣泛采用的基于任務(wù)復制的容錯算法，歸納出其中存在的問題：1)已有系統(tǒng)可靠性模型假設(shè)系統(tǒng)某一時刻只有一個故障，且在下個故障來時上個故障已解決，假設(shè)較為理想導致實用性不強；2)盲目地使每個任務(wù)擁有ε+1個副版容忍可能的ε個故障，雖然提高可靠性但易造成系統(tǒng)冗余度過高，可能引發(fā)任務(wù)因競爭計算資源而錯過截止期。 針對上述問題，本文將借助分層調(diào)度框架提供的基于組件的設(shè)計和分析方法以及主動任務(wù)復制容錯技術(shù)，以滿足系統(tǒng)可靠性目標和最小化冗余資源為目的，在多處理器平臺上展開實時系統(tǒng)容錯理論和算法研究。 首先，提出了一種同構(gòu)系統(tǒng)周期任務(wù)復制容錯算法。在建模階段，以一個超周期作為量化標準，從總體上通過使用概率統(tǒng)計的方法分析系統(tǒng)可靠性，實現(xiàn)了對基于周期任務(wù)集的系統(tǒng)可靠性模型建模。在精確量化分析階段，依據(jù)系統(tǒng)可靠性目標和對系統(tǒng)可靠性模型的分析，給出了任務(wù)復制次數(shù)邊界值的計算方法，在一定程度上避免對任務(wù)的盲目復制。接著，根據(jù)任務(wù)對系統(tǒng)可靠性貢獻和占用系統(tǒng)計算資源情況的差異，提出了一種經(jīng)濟的任務(wù)復制策略，從而在盡量減少因任務(wù)復制而增加計算資源消耗的條件下，達到動態(tài)確立各個任務(wù)的復制個數(shù)。 其次，提出了一種異構(gòu)系統(tǒng)DAG任務(wù)復制容錯算法。針對建模階段，通過對DAG圖中任務(wù)依賴關(guān)系分析，建立了單DAG的可靠性模型，并在其基礎(chǔ)上，實現(xiàn)了對多DAG系統(tǒng)的可靠性建模。在量化分析階段，借助已建立的可靠性模型和每次選擇可靠性代價最小處理機的思想，提出了一種任務(wù)復制次數(shù)下限值算法。然后采用上述經(jīng)濟的任務(wù)復制策略，在系統(tǒng)可靠性目標的驅(qū)使下動態(tài)地量化各個任務(wù)需要冗余復制次數(shù)，并在多處理機平臺上為任務(wù)分配處理器調(diào)度。 仿真實驗結(jié)果表明，與以往盲目的任務(wù)復制容錯方法相比，以上算法能夠從整體上達到系統(tǒng)的可靠性目標并最小化占用的冗余計算資源。
[Abstract]:In recent years, real-time systems have been widely used in the field of safety-critical automotive electronics. In addition to ensuring the logical correctness of the output results of real-time applications, strict time certainty and high reliability are also required, otherwise it will lead to serious consequences. However, with the expansion of application requirements, the application software of real-time systems is developing towards the direction of large-scale and high complexity, and the security and reliability problems become more and more prominent. It is necessary to make use of fault-tolerant technology to control the behavior of real-time system after making mistakes. In this paper, the hierarchical real-time scheduling framework is studied, and the widely used fault-tolerant algorithm based on task replication in real-time system is analyzed in detail. The problems are summarized as follows: 1) the existing system reliability models assume that there is only one fault in the system at a certain time, and the last fault has been solved when the next fault comes. 2) blindly make each task have 蔚 1 side edition to tolerate possible 蔚 faults, although improve reliability, it is easy to cause system redundancy to be too high, which may lead to task missing deadline due to competing computing resources. Aiming at the above problems, this paper will use the component-based design and analysis method provided by the hierarchical scheduling framework and the active task replication fault-tolerant technology to meet the system reliability goals and minimize redundant resources. The fault tolerant theory and algorithm of real-time system are studied on multi-processor platform. Firstly, a fault-tolerant algorithm for periodic task replication in isomorphic systems is proposed. In the stage of modeling, the system reliability model based on periodic task set is established by using the method of probability and statistics to analyze the reliability of the system with a super-period as the quantification standard. In the stage of accurate quantitative analysis, according to the reliability target of the system and the analysis of the reliability model of the system, the calculation method of the boundary value of the task replication times is given, which avoids the blind duplication of the task to a certain extent. Then, according to the difference of the contribution of the task to the system reliability and the difference of occupying the computing resources of the system, a kind of economic task replication strategy is proposed, which can reduce the consumption of computing resources because of the task replication as far as possible. To dynamically determine the number of copies of each task. Secondly, a fault-tolerant algorithm for DAG task replication in heterogeneous systems is proposed. In the stage of modeling, the reliability model of single DAG is established by analyzing the task-dependent relation in DAG diagram, and on the basis of it, the reliability modeling of multi-DAG system is realized. In the phase of quantitative analysis, with the help of the established reliability model and the idea of minimum cost processor for each selection of reliability, a lower limit algorithm for the number of task replicates is proposed. Then the economic task replication strategy mentioned above is adopted to dynamically quantify the number of redundant replicas required for each task under the drive of system reliability objectives and to assign processors for task scheduling on multiprocessor platforms. Simulation results show that compared with the previous blind task replication fault-tolerant methods, the above algorithm can achieve the reliability goal of the system as a whole and minimize the redundant computing resources.
【學位授予單位】：湖南大學
【學位級別】：碩士
【學位授予年份】：2013
【分類號】：TP302.8

【參考文獻】

相關(guān)期刊論文 前9條

1 王強,徐俊剛,王宏安,戴國忠;一種新的基于優(yōu)先級表的實時調(diào)度算法[J];電子學報;2004年02期

2 張擁軍,張怡,彭宇行,陳福接;一種基于多處理機的容錯實時任務(wù)調(diào)度算法[J];計算機研究與發(fā)展;2000年04期

3 傅忠傳;陳紅松;崔剛;楊孝宗;;處理器容錯技術(shù)研究與展望[J];計算機研究與發(fā)展;2007年01期

4 羅威;陽富民;龐麗萍;李俊;;基于延遲主動副版本的分布式實時容錯調(diào)度算法[J];計算機研究與發(fā)展;2007年03期

5 胡華平,金士堯,王維;分布式實時系統(tǒng)的高可靠性研究與實現(xiàn)[J];計算機研究與發(fā)展;1998年09期

6 羅威;陽富民;龐麗萍;涂剛;;異構(gòu)分布式系統(tǒng)中實時周期任務(wù)的容錯調(diào)度算法[J];計算機學報;2007年10期

7 李昕穎;顧健;何鋒;熊華鋼;;硬實時系統(tǒng)在強分區(qū)約束下的雙層分區(qū)調(diào)度[J];計算機學報;2010年06期

8 郭亮,唐稚松;三機冗余容錯系統(tǒng)的描述和驗證[J];軟件學報;2003年01期

9 劉懷,費樹岷;基于EDF的分布式控制系統(tǒng)容錯調(diào)度算法[J];軟件學報;2003年08期

相關(guān)博士學位論文 前2條

1 李磊;分布式系統(tǒng)中容錯機制性能優(yōu)化技術(shù)研究[D];國防科學技術(shù)大學;2007年

2 王健;容錯系統(tǒng)中實時任務(wù)調(diào)度和負載均衡算法研究[D];浙江大學;2009年

本文編號：2289501