實時系統的非剝奪資源共享和分層調度

《實時系統的非剝奪資源共享和分層調度》是依託西南大學，由張鳳翔擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：實時系統的非剝奪資源共享和分層調度
• 項目類別：青年科學基金項目
• 項目負責人：張鳳翔
• 依託單位：西南大學

項目摘要

可調度性分析是實時系統的重要理論基礎，為系統的正確運行和任務時限的滿足提供理論依據和保證。最短時限優先（EDF）是單處理器上最優的實時調度算法。非剝奪資源共享是實時系統的重要屬性，在現有文獻中，未能為考慮了非剝奪共享資源的系統提供完整和有效的可調度性分析方法。本項目首次為整合了非剝奪共享資源以及任務釋放抖動的EDF實時系統，提供精確和高效的可調度性分析方法。現代實時系統不斷提高的處理能力使得多個應用程式可以通過分層調度運行在同一個處理器上，好處是系統的整體性能能夠得到增強，並且減少了成本。本項目擬:(1)為整合了非剝奪共享資源的實時系統提出完備、高效並且精確的可調度性分析方法。(2)將非剝奪共享資源整合到分層調度模型中，為基於EDF的分層實時系統提出高效的調度方案和分析方法。

結題摘要

最短時限優先EDF是單處理器實時系統中最優的調度策略。本項目對EDF實時系統中非剝奪資源共享的可調度性問題進行了研究，並建立了適合EDF的分層調度的資源共享協定、調度模型和可調度性分析。非剝奪資源共享是實時系統中的重要特性，已有的對任意相對時限的通用EDF系統的精確可調度性分析，基於簡單任務模型的處理器需求分析，沒有建立完備的整合了非剝奪資源共享以及任務啟動抖動的分析方法。我們在本項目中，證明了傳統的處理器需求分析可以和EDF系統中最常用的SRP資源共享協定結合，在分析了阻塞以及任務啟動抖動的相互作用的基礎上，建立了完整並且精確的可調度性分析方法。我們進一步證明了，該結論可以擴展為快速收斂處理器需求分析（QPA），因此能夠提供高效的針對通用EDF系統的可調度性測試。我們建立了適合於EDF的分層調度框架，並提出了基於EDF分層調度的堆疊共享資源協定（HSRP_GEDF），使得在該框架中，任務和服務程式可以共享全局和本地非剝奪資源。在EDF+HSRP_GEDF的分層調度系統中，我們提出了完整的對任務和服務程式的可調度性分析。我們證明了該結論同樣可以擴展為QPA方法對系統進行快速的可調度性測試。本項目還對採用EDF+FP的混合調度系統進行了研究，提出了具有多項式時間複雜度的可調度性分析算法，通過對大量隨機任務集合的對比實驗證明，相對於已有文獻中的結論，本項目提出的測試算法對任務集合的通過率有大約300%的提高。