CASIA OpenIR  > 毕业生  > 博士学位论文
特定应用系统的实时调度算法研究
其他题名Real-Time Scheduling for Application Special Operating Systems
何东之
学位类型工学博士
导师王飞跃
2005-06-01
学位授予单位中国科学院研究生院
学位授予地点中国科学院自动化研究所
学位专业控制理论与控制工程
关键词实时系统 调度算法 特定应用系统 抢占阈 优先级 Real-time Systems Scheduling Algorithm Application Specific Operating Systems Preemption Threshold Task Priority
摘要本文根据 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.
馆藏号XWLW915
其他标识符200218014603159
语种中文
文献类型学位论文
条目标识符http://ir.ia.ac.cn/handle/173211/5873
专题毕业生_博士学位论文
推荐引用方式
GB/T 7714
何东之. 特定应用系统的实时调度算法研究[D]. 中国科学院自动化研究所. 中国科学院研究生院,2005.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[何东之]的文章
百度学术
百度学术中相似的文章
[何东之]的文章
必应学术
必应学术中相似的文章
[何东之]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。