本文選題：搶占代價 + 有用緩存塊��； 參考：《湖南大學》2013年碩士論文

【摘要】：實時系統(tǒng)應能夠在限定的響應時間內(nèi)提供所需水平的服務。在航空航天、工業(yè)控制、軍事、汽車電子等具有嚴格時間約束的硬實時系統(tǒng)開發(fā)過程中，，必須進行最壞執(zhí)行時間分析和可調(diào)度性分析，驗證系統(tǒng)能夠滿足限定的時間約束。 隨著集成電路工藝和計算機技術的快速發(fā)展，處理器的核心時鐘頻率越來越快，然而主存存取速度始終跟不上處理器頻率的步伐，致使主存和處理器之間速度差異越來越大。緩存在平衡處理器和主存之間的速度差異方面起著重要的作用。在搶占式實時系統(tǒng)中，當搶占發(fā)生時，搶占任務和被搶占任務之間的緩存沖突將會使得被搶占任務的緩存塊被驅(qū)逐出緩存。當被搶占任務重新開始執(zhí)行時由于緩存失效不得不花費時間來加載這些塊，所花費的時間被稱為與緩存有關的搶占代價。這必然對實時系統(tǒng)最壞執(zhí)行時間分析和可調(diào)度性分析產(chǎn)生消極的影響。 在本文中，我們對實時系統(tǒng)任務進行了建模，并提出了一個有效判定直接搶占點和間接搶占點的算法。這個算法利用任務的最壞執(zhí)行時間和最好執(zhí)行時間，判定一個超周期內(nèi)所有任務的每個作業(yè)的直接搶占點和間接搶占點�；谟杏镁彺鎵K和驅(qū)逐緩存塊的概念還提出了計算與緩存有關搶占代價的UCB-ECB方法。然后，利用UCB-ECB方法計算各個作業(yè)在搶占點處的與緩存有關搶占代價，并將計算出來的搶占代價與該作業(yè)的最壞執(zhí)行時間相加，結果就是該作業(yè)最壞執(zhí)行時間的估算值。一個任務最壞執(zhí)行時間的估算值就是超周期內(nèi)該任務各個作業(yè)最壞執(zhí)行時間估算值的最大值。最后利用估算的最壞執(zhí)行時間和與緩存有關搶占代價通過線性規(guī)劃方法計算出各個任務的最壞響應時間，進行響應時間可調(diào)度性分析，判斷任務集是否可調(diào)度。 為了驗證算法的有效性和UCB-ECB方法的優(yōu)越性，本文采用隨機生成實時任務集，與其他計算搶占代價的方法進行搶占代價的對比實驗，同時與前人的研究進行最壞執(zhí)行時間的對比實驗。實驗數(shù)據(jù)表明與其他計算搶占代價方法相比UCB-ECB方法可以得到更嚴格的搶占代價�？烧{(diào)度性分析表明我們得到了一個更安全的最壞執(zhí)行時間，并且在緩存的影響下任務集是可調(diào)度的。
[Abstract]:Real-time systems should be able to provide the required level of service within a limited response time. In the development of hard real-time systems with strict time constraints, such as aerospace, industrial control, military and automotive electronics, the worst-case execution time analysis and schedulability analysis must be carried out to verify that the system can meet the limited time constraints. With the rapid development of integrated circuit technology and computer technology, the core clock frequency of the processor becomes faster and faster. However, the access speed of the main memory can not keep up with the speed of the processor, which makes the speed difference between the main memory and the processor more and more big. Caching plays an important role in balancing the speed difference between processor and main memory. In preemptive real-time systems, when preemption occurs, the cache conflict between preemptive task and preemptive task will result in the cache block of preemptive task being expelled from cache. When the preemptive task starts again, it takes time to load these blocks due to cache invalidation, which is called the cost of preemption related to cache. This will inevitably have a negative impact on the worst execution time analysis and schedulability analysis of real-time systems. In this paper, we model the task of real-time system, and propose an effective algorithm to determine the direct preemption point and indirect preemptive point. The algorithm uses the worst execution time and the best execution time to determine the direct preemption point and the indirect preemption point for every job in a super period. Based on the concepts of useful cache block and expelling cache block, a UCB-ECB method to calculate the preemptive cost related to cache is also proposed. Then, the cache related preemption cost of each job at preemption point is calculated by UCB-ECB method, and the calculated preemption cost is added to the worst execution time of the job. The result is the estimated worst execution time of the job. The estimation of the worst execution time of a task is the maximum value of the worst execution time estimate for each job in the super-cycle. Finally, the worst-case response time of each task is calculated by linear programming method using the estimated worst-case execution time and cache related preemption cost, and the schedulability of response time is analyzed to determine whether the task set is schedulable or not. In order to verify the validity of the algorithm and the superiority of the UCB-ECB method, this paper uses random generation of real-time task sets, and compares the preemptive cost with other methods. At the same time, the worst execution time was compared with previous studies. Experimental data show that the UCB-ECB method can obtain more strict preemptive cost than other computational preemptive cost methods. Schedulability analysis shows that we get a more secure worst-case execution time and the task set is schedulable under the influence of cache.
【學位授予單位】：湖南大學
【學位級別】：碩士
【學位授予年份】：2013
【分類號】：TP333

【參考文獻】

相關期刊論文 前7條

1 沈卓煒;;不可搶占式EDF調(diào)度算法的可調(diào)度性分析[J];計算機工程與應用;2006年09期

2 賓雪蓮;楊玉海;金士堯;賓亞;;基于EDF搶占式調(diào)度的周期任務最小響應時間分析[J];計算機科學;2004年09期

3 楊玉海;賓雪蓮;余勝生;周敬利;;采用搶占閾值調(diào)度的具有釋放抖動和特定釋放偏移的最大響應時間計算方法[J];計算機科學;2007年08期

4 劉育芳,張立臣;實時系統(tǒng)最壞執(zhí)行時間分析[J];計算機應用研究;2005年11期

5 賴娟;洪艷偉;;一種硬實時調(diào)度算法的可調(diào)度性分析[J];樂山師范學院學報;2006年05期

6 王永吉,陳秋萍;單調(diào)速率及其擴展算法的可調(diào)度性判定[J];軟件學報;2004年06期

7 鄭英治;焦哲勇;;基于OSEK標準的嵌入式實時操作系統(tǒng)在汽車電子中的應用[J];現(xiàn)代電子技術;2011年03期

本文編號：1876052