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

【摘要】：實(shí)時(shí)系統(tǒng)應(yīng)能夠在限定的響應(yīng)時(shí)間內(nèi)提供所需水平的服務(wù)。在航空航天、工業(yè)控制、軍事、汽車電子等具有嚴(yán)格時(shí)間約束的硬實(shí)時(shí)系統(tǒng)開發(fā)過程中，，必須進(jìn)行最壞執(zhí)行時(shí)間分析和可調(diào)度性分析，驗(yàn)證系統(tǒng)能夠滿足限定的時(shí)間約束。 隨著集成電路工藝和計(jì)算機(jī)技術(shù)的快速發(fā)展，處理器的核心時(shí)鐘頻率越來越快，然而主存存取速度始終跟不上處理器頻率的步伐，致使主存和處理器之間速度差異越來越大。緩存在平衡處理器和主存之間的速度差異方面起著重要的作用。在搶占式實(shí)時(shí)系統(tǒng)中，當(dāng)搶占發(fā)生時(shí)，搶占任務(wù)和被搶占任務(wù)之間的緩存沖突將會(huì)使得被搶占任務(wù)的緩存塊被驅(qū)逐出緩存。當(dāng)被搶占任務(wù)重新開始執(zhí)行時(shí)由于緩存失效不得不花費(fèi)時(shí)間來加載這些塊，所花費(fèi)的時(shí)間被稱為與緩存有關(guān)的搶占代價(jià)。這必然對實(shí)時(shí)系統(tǒng)最壞執(zhí)行時(shí)間分析和可調(diào)度性分析產(chǎn)生消極的影響。 在本文中，我們對實(shí)時(shí)系統(tǒng)任務(wù)進(jìn)行了建模，并提出了一個(gè)有效判定直接搶占點(diǎn)和間接搶占點(diǎn)的算法。這個(gè)算法利用任務(wù)的最壞執(zhí)行時(shí)間和最好執(zhí)行時(shí)間，判定一個(gè)超周期內(nèi)所有任務(wù)的每個(gè)作業(yè)的直接搶占點(diǎn)和間接搶占點(diǎn)�；谟杏镁彺鎵K和驅(qū)逐緩存塊的概念還提出了計(jì)算與緩存有關(guān)搶占代價(jià)的UCB-ECB方法。然后，利用UCB-ECB方法計(jì)算各個(gè)作業(yè)在搶占點(diǎn)處的與緩存有關(guān)搶占代價(jià)，并將計(jì)算出來的搶占代價(jià)與該作業(yè)的最壞執(zhí)行時(shí)間相加，結(jié)果就是該作業(yè)最壞執(zhí)行時(shí)間的估算值。一個(gè)任務(wù)最壞執(zhí)行時(shí)間的估算值就是超周期內(nèi)該任務(wù)各個(gè)作業(yè)最壞執(zhí)行時(shí)間估算值的最大值。最后利用估算的最壞執(zhí)行時(shí)間和與緩存有關(guān)搶占代價(jià)通過線性規(guī)劃方法計(jì)算出各個(gè)任務(wù)的最壞響應(yīng)時(shí)間，進(jìn)行響應(yīng)時(shí)間可調(diào)度性分析，判斷任務(wù)集是否可調(diào)度。 為了驗(yàn)證算法的有效性和UCB-ECB方法的優(yōu)越性，本文采用隨機(jī)生成實(shí)時(shí)任務(wù)集，與其他計(jì)算搶占代價(jià)的方法進(jìn)行搶占代價(jià)的對比實(shí)驗(yàn)，同時(shí)與前人的研究進(jìn)行最壞執(zhí)行時(shí)間的對比實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)表明與其他計(jì)算搶占代價(jià)方法相比UCB-ECB方法可以得到更嚴(yán)格的搶占代價(jià)�？烧{(diào)度性分析表明我們得到了一個(gè)更安全的最壞執(zhí)行時(shí)間，并且在緩存的影響下任務(wù)集是可調(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.
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TP333

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

本文編號(hào)：1876052