於異質平台之狀態改變即時非精確運算排程分析

為了讓即時多狀態系統可以適應於動態的環境、功能、參數改變, 有需多研究致力於確保狀態改變的時間限制, 然而,當系統因為特定的事件需要發生狀態改變時,狀態改變會造成有些工作無法在限制的時間內完成及系統的失敗, 因此,需要保證系統在狀態轉換發生時, 系統可以根據當時的工作量,有彈性的分配工作,相較於多模式系統,每個模式又可再細分為好幾個不同的狀態,系統工作量的變化在狀態改變時,比模式改變時少。延長狀態改變的時間可以避免有些工作無法在限定的時間內完成, 有許多研究根據最差的情況做分析,換句話說, 在延長的這段時間內,系統會繼續執行原本狀態的工作量直到狀態改變發生及完成,因此在狀態改變完成前,系統的效能可能會無法達到原本的要求,在傳統的排程分析裡,他考慮了每個工作的被干擾的最差情況,並且針對縮短狀態改變的延遲時間, 在這篇論文中,我們延伸了以限定時間為基礎的排程分析,並應用於搶占式排班和不可搶占式排班,相較於傳統排程分析的方法,我們在系統執行時才去計算干擾時間的最差情形,因此我們的方法可以得到一個比較精準的延遲時間,換句話說, 車輛辨識的模型可以提早被更新,可以減少車輛辨識的失誤率,除此之外,我們還考慮了非精確式運算模型,我們將發展一個狀態改變時的排班分析並且考慮非精確式運算模型。

關鍵字

即時系統；多狀態系統；排程分析；搶占式排班；不可搶占式排班

並列摘要

To enable real-time multi-state systems to adapt to dynamically changing environments, changing functionalities and changing parameters, there have been plenty of studies on guaranteeing the timing constraint in state transi- tion. However, when the system state is changed caused by specific event, the transition of system states can lead to deadline miss and system failure. Therefore, it is desired to assure that the system remains feasible during state transition by properly scheduling the transition of system workload. Com- paring to multi-mode systems, we divide each mode into several states. The changing workload in state transition is less than in mode change. Postponing the state transition can avoid the deadline miss and has been studied for worst case analysis. In other words, during the postpone, the system will continue to execute the workload in current state until the state transmission is scheduled and completed. Therefore, the performance of the system may not meet the requirement before the transmission completes. The traditional pessimistic schedulability analysis considers the worst case inter- ference and aim at shortening the state transition delay time. In this thesis, we extend the existing deadline-based schedulability analysis under preemp- tive scheduling and non-preemptive scheduling. Comparing to traditional ap- proach, we compute the upper bound of interference at run-time and can get the more precise delay time. In other words, the state change delay time can be shortened and the miss rate of vehicle detection will be decreased. In ad- dition, we also consider imprecise computation model. We will develop the schedulability analysis in state transition under imprecise computation model.

並列關鍵字

real time systems ； multi-state system ； schedulability analysis ； preemptive scheduling ； non-preemptive scheduling

參考文獻

[1] C. L.Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-time Environment,” Journal of the ACM, 1973.

[2] K. Tindell, “Adding Time-offset to Schedulability Analysis,” Real-Time Systems Research Group.

[3] Q.D.Z.G.G.Y.NanGuan,WangYi,“SchedulabilityAnalysisforNon-preemptive Fixed-priority Multiprocessor Scheduling,” Journal of Systems Architecture, 2011.

[4] K. CAI, Y., “Non-preemptive Scheduling of Periodic Tasks in Uniprocessor and Multi-processor Systems,” Algorithmica, pp. 572–599, 1996.

[5] J. R. Crespo, “Mode Change Protocols for Real-time Systems: A Survey and a New Proposal,” Real-Time Systems, vol. 26, pp. 161–197, 2004.

國際替代計量

於異質平台之狀態改變即時非精確運算排程分析

全文下載

主題瀏覽