基于嵌入式实时操作系统的任务调度机制研究与实现

VIP免费

3.0 侯斌 2024-11-19 5 4 1.11MB 64 页 15积分

侵权投诉

摘要

在嵌入式领域中，随着智能嵌入式设备的广泛应用，且对它的需求也是越来越

复杂，可采用嵌入式实时操作系统来有效地管理处理器的资源，缩短软件设计和

系统开发周期以保证系统的稳定性和实时性。现有的一些嵌入式系统中仍存在一

些缺点，例如内核大、任务调度处理过于复杂，以及调度机制设计不合理造成系

统资源浪费等问题。因此，需要开发研究更高效地任务调度机制。在国内外研究

成果的基础上，本文对嵌入式实时系统的调度机制进行更深入的研究，旨在设计

出一个高效且合理的任务调度机制。

首先，对本课题进行系统规划，且拟定采取的项目实施方案。对嵌入式实时系

统概述、分析实例内核、嵌入式实时系统的实时性指标以及经典调度算法进行了

介绍，并提出一种基于组合优先级的自适应实时调度算法(SREDF)，任务优先级的

计算方式是以多个特征参数作为依据，建立任务模型，确定调度算法的任务优先

级结构，并设计算法流程。该算法能够更全面地描述系统中任务的关键性和紧迫

性。

在任务切换的开销方面，为了改善任务间频繁切换任务的现象，本文基于嵌入

式系统的任务切换机制进行研究和改进，设计了一种改进的任务切换算法(MCST)，

引入一个任务切换因子 βi判断是否进行任务切换，当 βi越小表示该任务 i被切换

的比率也越小，表示该任务快要被系统执行完毕，通过因子 βi决定该任务是否继

续执行或被切换。

在资源利用率方面，基于两层调度和任务管理器的调度方式，设计了实时任务

调度机制。上层调度模块采用 MCST 算法，将此层作为预判断是否任务切换，并

且在 ARM 平台上采用仿 X86 体系架构的动态向量表技术，下层调度模块则采用

SREDF 算法进行任务调度，实现实时动态地调整任务调度，而任务管理器负责管

理实时任务的运行、新任务插入时的处理和删除任务等操作。仿真实验表明，降

低了截止期错失率和任务切换的次数，有效地提高了资源利用率。

最后，对全文进行总结，并指出研究工作中存在不足之处，对其提出几个值得

研究与完善的方面。

关键词：嵌入式实时操作系统、调度算法、任务切换、优先级、截止

期错失率

Abstract

In the field of embedded system, with the wide application of intelligent embedded

devices, the demand for it is becoming more and more complex so that it can adopt the

embedded real-time operating system to effectively manage the resources of the

processor, simplify software design and shorten the system development period and

ensure its real-time and reliability of the system. Nowadays some disadvantages still

exist in some of the existing embedded systems, such as bigger kernel, complex task

scheduling process and unreasonable task scheduling mechanism to waste the system

resource and so on. Therefore, it is necessary to research and develop a more efficient

task scheduling mechanism. This paper made theoretical and practical study on the

embedded real-time system, through reference the research results at home, abroad and

trial in practice in order to design a high efficient and reasonable task scheduling

mechanism.

Firstly, map out the system planning and come up with the implementation scheme.

Analyze and research the overview of the embedded real-time system, kernels, the

performance index and typical scheduling algorithms. This paper proposes a

self-adaptive real-time schedule algorithm based on combinational multiple parameters

as its priority strategy (SREDF) to describe the importance and urgency of the task well.

Build the task module, design task’s priority structure and the algorithm process, then

simulate and analysis the experimental results to prove the correctness and effectiveness

of the algorithm.

Secondly, in terms of the context switching cost, this paper devises a modified

context switch algorithm based on the research and improvement of task switching

mechanism of the embedded system (MCST), introducing the ratio βi to check whether

the context switch happen. The ratio becomes smaller means that the proportion of

switching the task i also becomes lower, in other words, the system will execute the task

i soon through the ratio βi to decide whether the task be executed or switched.

Thirdly, in terms of the context switching cost, this paper devises a real-time task

scheduling mechanism based on two scheduled levels and task manager. The upper

scheduled level is MCST algorithm to predetermine whether task switching and use the

dynamic vector table technology to imitate the X86 architecture on the ARM platform.

The lower scheduled level is SREDF algorithm to realize real-time dynamic adjustment

of the task scheduling. The task manager is response for the management of real-time

tasks running, new tasks insertion and deletion and so on. The simulation results shows

that reduce the missed deadline percentage and the time of task switching and

effectively improve the utilization rate of system resource.

Finally, summarize this paper, point out the deficiency in the research and to make

clear the further research.

Key Words: Embedded Real-time Operating System, Schedule

Algorithm, Context Switch, Priority, Missed Deadline

Percentage(MDP)

中文摘要

Abstract

第一章绪论 ......................................................... 1

1.1 研究背景 ..................................................... 1

1.2 研究目的和意义 ............................................... 2

1.3 本文的主要工作 ............................................... 3

1.4 本文内容组织结构 ............................................. 5

第二章嵌入式系统实时任务调度的概述 ................................. 6

2.1 嵌入式实时系统概述 ........................................... 6

2.2 μCLinux 和 FreeRTOS 实例及调度算法分析 ....................... 6

2.3 嵌入式操作系统相关实时性评价指标 ............................. 8

2.3.1 任务管理指标 ........................................... 8

2.3.2 中断管理指标 ........................................... 9

2.4 嵌入式实时系统调度算法的分类 ................................ 11

2.5 本章小结 .................................................... 13

第三章基于组合优先级的自适应实时调度算法研究 ...................... 14

3.1 任务模型的建立 .............................................. 14

3.2 算法描述 .................................................... 15

3.3 算法分析 .................................................... 18

3.4 仿真实验分析 ................................................ 19

3.5 本章小结 .................................................... 21

第四章嵌入式系统任务切换机制研究和改进 ............................ 22

4.1 任务切换概述 ................................................ 22

4.2 任务切换的产生 .............................................. 22

4.2.1 多任务 ................................................ 22

4.2.2 中断处理 ............................................... 23

4.2.3 用户和内核的模式切换 .................................. 23

4.3 任务切换的过程 .............................................. 23

4.4 任务切换的开销 .............................................. 26

4.5 嵌入式实时系统中任务切换的改进 .............................. 27

4.5.1 非抢占式内核中的任务切换 .............................. 27

4.5.2 抢占式内核中的任务切换 ................................. 28

4.5.3 改进的任务切换算法 MCST ................................ 29

4.6 本章小结 .................................................... 30

第五章基于 ARM9 的任务调度机制设计、实现和测试 ..................... 31

5.1 任务状态设计 ................................................ 31

5.2 调度机制设计 ................................................ 32

5.3 中断处理设计 ................................................ 36

5.4 时钟中断模块设计 ............................................ 40

5.5 数据结构设计 ................................................ 45

5.5.1 任务控制块设计 ......................................... 45

5.5.2 任务堆栈设计 ........................................... 46

5.5.3 任务队列设计 ........................................... 48

5.6 实现与测试 .................................................. 49

5.6.1 硬件平台 ............................................... 49

5.6.2 软件平台 ............................................... 49

5.6.3 实验设计 ............................................... 50

5.6.4 实验结果与分析 ......................................... 50

5.7 本章小结 .................................................... 52

第六章总结与展望 .................................................. 54

6.1 课题总结 .................................................... 54

6.2 研究展望 .................................................... 55

参考文献 ........................................................... 56

在读期间公开发表的论文和承担科研项目及取得成果 ..................... 60

致谢 ............................................................. 61

第一章绪论

1.1 研究背景

随着科学技术的发展不断地提高，计算机技术随之也突飞猛进地发展，电子信

息技术也有了长足的进步，大大提高了信息处理的能力，与此同时，计算机软件

的需求是越来越复杂，促使计算机软件的设计思想和开发方式都在不断地创新。

嵌入式系统作为计算机系统不可或缺的构成，需要软硬件技术的配合，它的发

展将会带来一场信息技术的革命，它们广泛地应用与机器人、工业控制、POS 网

络及电子商务集、汽车电子、交通管理、家庭智能管理系统、信息家电、医疗仪

器、移动通信、航空航天与军事国防等领域，与我们的生活息息相关，应用的范

围也在不断地拓宽。我们可以通过研究嵌入式系统来提高和改善我们的生活质量，

研究嵌入式系统是非常有必要的，也是计算机科学研究人员责无旁贷的使命。

当今的嵌入式实时系统兼具有很复杂的嵌入式软件，嵌入式实时系统与一般操

作系统不同之处是具有实时性的要求，在满足完成应用的功能的同时还要满足应

用时限的要求。如何在时限的要求下完成任务集内各个任务，使系统得以正常地

和高效率地工作。任务调度的好坏和执行效率会直接影响到嵌入式内核的应用范

围和实时性的程度，所以任务调度算法一直是实时系统领域内研究的焦点。

早期 Liu 和Layland 提出了 RM(Rate Monotonic)算法[1]和最早截止优先

EDF(Earliest Deadline First)算法，这个时期的实时系统主要应用的领域为军事和生

产领域，系统功能比较简单，调度算法也相对简单。主要集中研究单一任务类型

的调度算法，提出了基于优先级、基于时间表和比例共享的调度算法。RM 和EDF

算法为日后的实时调度算法研究奠定了基础。随着计算机科技和技术的飞速发展，

实时操作系统的研究进入了高速发展的阶段，嵌入式系统的发展逐渐成为计算机

发展中的一个新兴研究对象，于此同时，嵌入式实时系统的应用越来越广泛，也

越来越复杂，其功能也越来越强大，单一的任务类型的调度算法已经不能够在适

应当今社会的发展，一些研究机构和学者们也开始提出了一些实时任务的混合调

度算法，主要的调度算法有后台处理(Background Processing)算法、基于时间空闲

(Slack Based)算法以及基于服务器(Server Based)算法等等调度算法，这些调度算法

促进了实时操作系统的发展。紧接着，计算机的网络技术和硬件技术的巨大发展，

人们开始关注计算机的性能、价格和功耗。例如，Michael Culbert 于1994 年提出

了MIPS per Watt (每瓦功率换取的 MIPS)作为计算机系统的评价指标，而 Mark

Weiser 提出了 MIPJ(每焦耳能量执行的指令数)，区别在于前者的量纲中包含了时

间，而后者则无包含时间。因此，这个时期的研究学者们关注低能耗在实时系统

的研究。1995 年Juan Echague,Ismael Ripoll 和Alfons Crespo 在Real-Time System

上海理工大学硕士学位论文

上发表了一篇关于任务切换的硬实时抢占式调度算法论文，这个时期的学者们更

专注于提高任务切换的效率降低系统功耗。随着硬件技术的快速发展，国内外的

学者也尝试着将实时调度算法应用到多核处理器上，或应用在其他计算机技术的

各个领域中等等。

国内对于嵌入式操作系统的研究起步较晚，但发展很快。近年来，学者们基于

EDF 算法提出了很多创新的混合调度算法，如 EDV ( Earliest Deadline Value)和

VED (Value Earliest Deadline) 算法[2]合了价值和截止期为优先级依据的特征参数，

以多个特征参数来作为任务的优先级来进行任务调度[3]。再如，基于 DPA 的抢占

调度算法 DRTP[4]，根据任务的价值和剩余执行时间讨论剩余价值，通过综合考虑

任务的剩余价值和执行的紧迫性[4]。除此之外，文献[4]中学者们还提出了基于阈

值和高级算法来改进 EDF 算法，如模糊阈值 EDF 调度算法通过和延长当前任务截

止期至动态模糊阈值的方法，降低了 CPU 的消耗，提高 CPU 的利用率。至今，诸

多实时调度算法应运而生，推进了嵌入式系统应用领域的快速发展。

1. 2 研究目的和意义

在传统的嵌入式程序的设计中，如果有一个以上的任务，系统一般采用无限主

循环。每个任务模块执行前都有前提条件，系统以轮询的方式查询每一个条件并

进行判断，一旦某个任务的模块执行条件成立，则立即执行该条件所对应的任务

模块。在这个期间，一旦发生中断，由中断服务程序 ISR 负责处理[6]，整个过程如

图1-1 所示。

图1-1 中断处理过程

这种执行方式只适合简单的应用，随着计算机科学与技术的飞速发展，计算机

的应用范围不断的扩大和复杂化，系统需要控制任务数量逐渐增加并且要求实时

响应，若采用传统的方式开发系统，会存在两个比较突出的问题，一是中断响应。

一般为了保证系统中的任务实时性，就会在 ISR 中进行处理，这样一来，在 ISR

模块

ISR

模块

ISR

主循环

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要在嵌入式领域中，随着智能嵌入式设备的广泛应用，且对它的需求也是越来越复杂，可采用嵌入式实时操作系统来有效地管理处理器的资源，缩短软件设计和系统开发周期以保证系统的稳定性和实时性。现有的一些嵌入式系统中仍存在一些缺点，例如内核大、任务调度处理过于复杂，以及调度机制设计不合理造成系统资源浪费等问题。因此，需要开发研究更高效地任务调度机制。在国内外研究成果的基础上，本文对嵌入式实时系统的调度机制进行更深入的研究，旨在设计出一个高效且合理的任务调度机制。首先，对本课题进行系统规划，且拟定采取的项目实施方案。对嵌入式实时系统概述、分析实例内核、嵌入式实时系统的实时性指标以及经典调度算法进行了介绍，并...

展开>> 收起<<

基于嵌入式实时操作系统的任务调度机制研究与实现.pdf

共64页,预览7页

还剩页未读，继续阅读

基于嵌入式实时操作系统的任务调度机制研究与实现

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: