一种实时任务可调度性问题的研究

论文摘要

嵌入式系统一般指非PC系统,包括硬件和软件两部分。硬件包括微处理器、存储器及I/O端口等。软件部分包括应用程序和嵌入式操作系统(EOS)。嵌入式操作系统一般要求实时和多任务操作,这里的“实时”不仅意味着要求逻辑结果正确,而且要求结果必须产生在截止时间之前。 ARMLinux是一个嵌入式操作系统。对于嵌入式系统来说,通过预测一个任务能否在绝对时限之前运行完成而决定是否调度执行是很有意义的。在多代理协作求解、交通监控和卫星等各个领域都有这方面的要求。但是,ARMLinux作为软实时操作系统,当然无法提供这种能力。基于固定优先级的RM调度策略的系统虽然可以预测,但是,它的对象是周期任务。而有些系统根本不预测,只是一直监视任务的运行时间,对超过时限的任务只是简单的杀死。系统利用率很低。 在ARMLinux上,为了对新任务的运行结束时间进行预测,本文对它的内核做了几处修改:按优先级排序就绪队列;每次时钟中断看是不是有优先级比当前任务更高的任务就绪,决定是否调度;去掉了SCHED_RR调度策略。这样新任务的运行结束时间可以得到准确的计算。系统对不能直接接受的任务,动态地改变它的实时优先级,重新插入就绪队列后再做能否接受的判断。这样,增加了被系统接受的概率。另外,对实际运行时间超过了预计运行时间的任务,系统直接终止此任务。以避免由于某个任务的超时,使比它优先级低的任务顺次超时。最后,本文对此系统做了严密的测试,证明了它工作的正确性和稳定性。

论文目录

• 独创性声明
• 摘要
• Abstract
• 第一章 引言
• 1.1 课题的背景
• 1.2 课题的提出
• 1.3 论文的组织
• 第二章 相关技术背景
• 2.1 嵌入式系统
• 2.2 嵌入式操作系统
• 2.3 进程
• 2.3.1 概述
• 2.3.2 进程的定义和特性
• 2.3.3 进程的状态
• 2.3.4 进程的控制结构
• 2.4 调度
• 2.4.1 概述
• 2.4.2 调度准则
• 2.4.3 调度策略
• 2.5 中断
• 2.5.1 中断概述
• 2.5.2 时钟中断
• 第三章 研究基础
• 3.1 硬件环境
• 3.2 软件环境
• 第四章 ARMLinux内核的修改
• 4.1 概述
• 4.2 调度的修改
• 4.2.1 原来的调度策略
• 4.2.2 调度的修改
• 4.3 内核的其它修改
• 4.3.1 排序就绪队列
• 4.3.2 时钟中断服务程序的修改
• 4.4 修改之后的内核
• 第五章 解决方案的设计与实现
• 5.1 重要的数据结构和系统调用
• 5.1.1 任务的数据结构
• 5.1.2 调度参数的数据结构
• setscheduler（）'>5.1.3 系统调用sched_setscheduler（）
• 5.2 实时进程结束时间的计算
• 5.3 解决方案的实现
• 5.3.1 设计思想
• 5.3.2 解决方案的概述
• 5.3.3 解决方案的详细说明
• 5.3.4 实际运行时间超过估计时间的处理
• 5.3.5 不同方式插入就绪队列的讨论
• 5.3.6 算法工作的时机
• 第六章 内核性能测试
• 6.1 内核测试准备
• 6.1.1 内核测试目的
• 6.1.2 内核测试方法描述
• 6.2 进行内核测试
• 6.2.1 直接接受所有进程
• 6.2.2 直接拒绝所有进程
• 6.2.3 直接拒绝一个进程
• 6.2.4 进程向前移动后被接受
• 6.2.5 进程向前移动后因本身仍超时被拒绝
• 6.2.6 进程向前移动后因使别的进程超时被拒绝
• 6.2.7 进程向后移动后被接受
• 6.2.8 进程向后移动后因本身超时被拒绝
• 6.2.9 进程因实际运行时间超过预计运行时间被杀死
• 6.3 内核测试的分析和总结
• 第七章 总结与展望
• 参考文献
• 致谢
• 论文相关工作