实时系统的非剥夺资源共享和分层调度

Schedulability analysis is an important theoretical basis of real-time systems, it provides the guarantees that the correctness and all timing requirements of a system can be satisfied. Earliest deadline first (EDF) is an optimal scheduling policy for uniprocessor real-time systems. Non-preemptive resource sharing is an important characteristic of real-time systems. The existing literature does not provide an available schedulability analysis for systems when resource sharing is considered. This project first provides exact and efficient schedulability analysis for EDF systems when resource both non-preemptive resource sharing and release jitter are considered. The increasing processing capacity of modern real-time systems enables many real-time applications execute on the same processor by employing hierarchical scheduling, the benefits are performance enhancement of systems and cost reduction. This project has the following plans: (1) propose complete, effect and exact schedulability analysis for the systems integrated with non-preemptive shared resources. (2) incorporate resource sharing into hierarchical scheduling model, and provide efficient schedulability analysis for hierarchical systems with EDF scheduling.

可调度性分析是实时系统的重要理论基础，为系统的正确运行和任务时限的满足提供理论依据和保证。最短时限优先（EDF）是单处理器上最优的实时调度算法。非剥夺资源共享是实时系统的重要属性，在现有文献中，未能为考虑了非剥夺共享资源的系统提供完整和有效的可调度性分析方法。本项目首次为整合了非剥夺共享资源以及任务释放抖动的EDF实时系统，提供精确和高效的可调度性分析方法。现代实时系统不断提高的处理能力使得多个应用程序可以通过分层调度运行在同一个处理器上，好处是系统的整体性能能够得到增强，并且减少了成本。本项目拟:(1)为整合了非剥夺共享资源的实时系统提出完备、高效并且精确的可调度性分析方法。(2)将非剥夺共享资源整合到分层调度模型中，为基于EDF的分层实时系统提出高效的调度方案和分析方法。

最短时限优先EDF是单处理器实时系统中最优的调度策略。本项目对EDF实时系统中非剥夺资源共享的可调度性问题进行了研究，并建立了适合EDF的分层调度的资源共享协议、调度模型和可调度性分析。非剥夺资源共享是实时系统中的重要特性，已有的对任意相对时限的通用EDF系统的精确可调度性分析，基于简单任务模型的处理器需求分析，没有建立完备的整合了非剥夺资源共享以及任务启动抖动的分析方法。我们在本项目中，证明了传统的处理器需求分析可以和EDF系统中最常用的SRP资源共享协议结合，在分析了阻塞以及任务启动抖动的相互作用的基础上，建立了完整并且精确的可调度性分析方法。我们进一步证明了，该结论可以扩展为快速收敛处理器需求分析（QPA），因此能够提供高效的针对通用EDF系统的可调度性测试。我们建立了适合于EDF的分层调度框架，并提出了基于EDF分层调度的堆栈共享资源协议（HSRP_GEDF），使得在该框架中，任务和服务程序可以共享全局和本地非剥夺资源。在EDF+HSRP_GEDF的分层调度系统中，我们提出了完整的对任务和服务程序的可调度性分析。我们证明了该结论同样可以扩展为QPA方法对系统进行快速的可调度性测试。本项目还对采用EDF+FP的混合调度系统进行了研究，提出了具有多项式时间复杂度的可调度性分析算法，通过对大量随机任务集合的对比实验证明，相对于已有文献中的结论，本项目提出的测试算法对任务集合的通过率有大约300%的提高。