实时系统静态优先级调度理论与优化设计研究
文献类型：学位论文
| 作者 | 邢建生 |
| 学位类别 | 博士 |
| 答辩日期 | 2007-06-05 |
| 授予单位 | 中国科学院研究生院 |
| 授予地点 | 中国科学院软件研究所 |
| 导师 | 王永吉 |
| 关键词 | 实时系统 静态优先级调度 调度模型 优先级分配 可调度判定 可调度分析方法 有限优先级 优化设计 能耗管理 |
| 其他题名 | Static-Priority Scheduling Theory and Optimization Design for Real-Time Systems |
| 学位专业 | 计算机软件与理论 |
| 中文摘要 | 随着多媒体、嵌入式、移动计算、普适计算等计算机科学与技术的发展，实时系统的应用日趋广泛和复杂，这同时也对实时系统理论提出了许多新的需求。静态优先级调度理论被实时计算标准和商业操作系统广泛支持，同时也是实时系统中研究最充分、应用最广泛的理论，它也需要适应这些新的需求。现有静态优先级调度理论在如下几方面仍存在不足，主要包括：(1)理论体系还不太成熟。许多研究均基于较简单的调度模型，相应成果是否可以推广到更一般的调度模型中，尚有待进一步的研究和总结；(2)理论与应用之间仍存在较大的差距。现有研究主要基于一些比较理想化的调度模型，对实际应用中各种约束(如异步、不可抢占、有限优先级、阻塞等)下调度理论的研究仍处于初步阶段；(3)缺乏对可调度分析方法的系统总结和比较研究。可调度分析方法是静态优先级调度理论研究的重要工具，但迄今未见对可调度分析方法的系统总结和比较研究，这不利于对可调度性的深入理解和调度理论的进一步发展；(4)缺乏对性价比等指标进行评估的方法和理论。现有研究主要面向专用系统，未考虑性价比等指标，而随着实时系统越来越多地应用于通用系统，性价比等指标已成为实时系统设计的关键因素，迫切需要对性价比等指标进行评估，综合考虑可调度性和性能、价格等指标的方法和理论。本文对上述几方面中的若干典型问题进行了研究，主要创新成果有： 1.隐含截止期模型各种可调度判定算法性能比较和适用范围研究。归纳总结了隐含截止期模型的调度理论和各种可调度判定算法，开发了一个软件平台，对这些算法进行了详细的测试和比较，给出了它们的性能和适用范围，为实际应用中选择合适的算法提供了确切的依据。 2.可调度分析方法研究。归纳了现有的可调度分析方法：调度点分析法和响应时间分析法，分析、测试了两种方法的性能和适用范围，指出了响应时间分析法的优越性，这一结论为统一可调度约束及实时系统优化设计研究奠定了基础。 3.基于有限优先级的静态优先级调度理论研究。分析了有限优先级对可调度性的影响，给出了有限优先级下的可调度充要条件。归纳比较了有限优先级下的两类优先级分配算法，指出：最少优先级分配优于固定数目优先级分配，并提出一种最少优先级分配算法，该算法优于已知算法。 4.基于统一可调度约束的实时系统优化设计研究。基于响应时间分析法的优越性，提出了统一可调度约束，建立了以其基础的实时系统优化设计方法，并通过实验证实了方法的有效性。该方法改进了实时系统优化设计的性能，扩展了实时系统优化设计的适用范围。 |
| 英文摘要 | With the development of new computer sciences and technologies such as multimedia technology, embedded system, mobile computing, and pervasive computing, real-time systems have been applied more and more widely and become more and more complicated. Real-time scheduling theory must be improved to adapt to new application requirements. Static-priority scheduling, which has been widely supported by real-time computing standards and commercial operating systems, is most widely applied and most sufficiently studied in real-time scheduling domain. Current static-priority scheduling theory is not eligible for new application requirements in the following areas. (1)The system architecture of static-priority scheduling theory is not fully developed. Much research is based on simple scheduling models, and whether the research results can be extended to more complicated scheduling models is not known. (2)A wide gap still exists between theory and application. Much research is based on relatively ideal models and the theory which takes into account practical factors such as asynchronous, blocking and non-preemptive is only in its infancy. (3)There lacks systematic summarize and comparative study for schedulability analysis methods. So far, schedulability analysis methods, which are key tools for scheduling theory and can help us understand schedulability deeply, have not been summarized and compared. (4)There lacks the method for performance/price ratio evaluation. Current theory is mainly for special application. But as real-time systems have been applied in more and more general-purpose systems, performance/price ratio has become a major concern for real-time system designers. There exists an urgent demand for such method which can evaluate performance/price ratio and consider synthetically system schedulability, performance and price. This dissertation addresses some typical issues for static-priority scheduling, major innovative achievements are listed as follows: 1.Research on the performance comparison and applicability of schedulability tests for implicit deadline model. Summarize all schedulability tests for implicit deadline model and implement a test platform for these algorithms. Test and compare all these algorithms by the platform, and present applicability for each algorithm. 2.Research on the schedulability analysis methods for static-priority scheduling. Classify schedulability analysis methods into two categories: scheduling point analysis and response time analysis. Compare the performance and applicability of them. Point out that the response time analysis method is superior to the scheduling point analysis method. This result is fundamental for the schedulability constraint and the real-time system optimization design method presented next. 3.Research on the static-priority scheduling theory with limited priority levels. Analyze the impact of limited priority levels to schedulability. Present the sufficient and necessary schedulability condition for limited priority levels. Classify priority assignment algorithms for limited priority levels into two categories: least-number priority assignment and fixed-number priority assignment. Point out that the least-number priority assignment is superior to fixed-number priority assignment. Propose a new least-number priority assignment algorithm. 4.Research on the real-time system optimization design. Present a uniform schedulability constraint based on the response time analysis method. Build up a real-time system optimization design method based on the uniform schedulability constraint. Verify the efficiency and superiority of this optimization design method through examples and experiments. This research advances the performance of real-time system optimization design and extends its applicability. |
| 公开日期 | 2011-03-17 |
| 源URL | [http://124.16.136.157/handle/311060/7658]  |
| 专题 | 软件研究所_互联网软件技术实验室 _学位论文 |
| 推荐引用方式 GB/T 7714 | 邢建生. 实时系统静态优先级调度理论与优化设计研究[D]. 中国科学院软件研究所. 中国科学院研究生院. 2007. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。