特定应用系统的实时调度算法研究
文献类型：学位论文
| 作者 | 何东之 |
| 学位类别 | 工学博士 |
| 答辩日期 | 2005-06-01 |
| 授予单位 | 中国科学院研究生院 |
| 授予地点 | 中国科学院自动化研究所 |
| 导师 | 王飞跃 |
| 关键词 | 实时系统 调度算法 特定应用系统 抢占阈 优先级 real-time systems scheduling algorithm application specific operating systems preemption threshold task priority |
| 其他题名 | Real-Time Scheduling for Application Special Operating Systems |
| 学位专业 | 控制理论与控制工程 |
| 中文摘要 | 本文根据 ASOS 算法要求，提出了单处理器的专门基于片上 ASOS 系统的静态优先级和动态优先级调度算法。 对于处理器利用率要求不十分高的 ASOS 系统，本文首先给出了静态优先级下的改进可抢占阈调度算法（IPTS）。它合并了单调截止时限算法（DMS）与抢占阈算法（PTS）,是基于 DMS 算法上的一种改进算法。当每一个任务的抢占阈与按 DMS 算法分配的初始优先级相等时，IPTS 算法就退化成完全可抢占的 DMS算法；当每个任务的抢占阈都等于最高优先级时，它就变成了不可抢占调度算法。文章还给出了 IPTS 算法下的有效线程、最优线程和堆栈需求最小线程的分配方法。由于线程内的任务互不可抢占，又最优线程方法是最少的线程分配方法，所以最优线程能最大限度地降低了任务间的抢占次数，有效满足了 ASOS 任务调度的高效实时性要求。堆栈需求最小线程分配方法给了系统对堆栈内存需要最小情况下的线程分配方法。此外，线程的引进可以使 IPTS 算法与 ROOM 等技术较容易地结合在一起，便于复杂软件的开发。 对处理器要求较高的系统，文章给出了动态优先级抢占阈调度算法（DPTS），在理论上它可以达到 100%的处理器利用率。DPTS 算法是建立在动态优先级调度算法――EDF 算法上的抢占阈调度算法。 |
| 英文摘要 | With hardware technique developing and control tasks being increasingly complex, real-time systems have become those systems with real-time operating systems (RTOS) from non-operating systems. RTOS generally belong to system on chip (SOC). Meanwhile, the development of embedded systems in application also prompts systems architecture transformation from static to dynamic, and from general to application specific. In order to satisfy the new development of real-time systems, application specific operating systems (ASOS) appear. ASOS combine the Internet and application interface seamlessly. ASOS, which are tailorable and reconfigurable system, pursue cost-effective variations in the product. Though ASOS belong to RTOS, there are significant differences in scheduling algorithm between them. ASOS demand (1) lower costs in context switching, (2) lower stack memories, (3) easy to development in design. Though ASOS have been around several years, the study on scheduling for ASOS is still new area. In this paper, static and dynamic preemption threshold scheduling algorithms based on ASOS are presented. Improved preemption threshold scheduling (IPTS) belonging static preemption threshold scheduling would enable those ASOS which have no stringent CPU utilization demand. IPTS algorithm integrates preemption threshold scheduling into deadline monotonic scheduling (DMS), in other words, it is an improved DMS. When every task threshold is equal to its initial priority, which is allocated by DMS, IPTS algorithm degrades DMS; whereas, when every task threshold is equal to the highest initial priority, it is a non-preemption scheduling algorithm. In this paper, I also present effective thread, optimal thread and stack minimal thread calculation methods. Because tasks in identical thread are non-preemptive, optimal thread allocation can at most reduce tasks preemption costs. Minimal stack thread allocation enables to make system minimal stack requirement. Moreover, threads make IPTS easily combine with ROOM and UML.For high CPU utilization systems, dynamic preemption threshold scheduling (DPTS) presented in this paper can achieve full CPU utilization in theory. DPTS algorithm based on earliest deadline first (EDF) belongs to dynamic priority scheduling. In this paper, I also present effective thread, optimal thread and stack minimal thread calculation methods under DPTS. In the last part of the paper, an optimized DPTS algorithm is proposed, which changes threshold at run-time, and can reduce more preemption costs. |
| 语种 | 中文 |
| 其他标识符 | 200218014603159 |
| 源URL | [http://ir.ia.ac.cn/handle/173211/5873]  |
| 专题 | 毕业生_博士学位论文 |
| 推荐引用方式 GB/T 7714 | 何东之. 特定应用系统的实时调度算法研究[D]. 中国科学院自动化研究所. 中国科学院研究生院. 2005. |
入库方式： OAI收割
来源：自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。