越来越多的开发者在基于 Linux 系统构造嵌入式实时应用，他们迫切地需要一份基于 Linux系统构造嵌入式实时系统的指南性的文章。考虑到这种需求，本文在介绍了几种基本的实时进程调度算法的基础上，研究了普通的 Linux操作系统的进程调度，并十分全面地调查了各种实时 Linux 系统为了支持实时特性对普通 Linux 系统所做的改进。文章分析了将 Linux操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时 Linux是如何解决这些问题的，最后对于如何将这些已有的研究成果应用与实际的研究和开发工作中作了很好的建议。
作者 : 张焕强 ([email protected] ) 中科院软件研究所多媒体通信和网络工程研究中心 越来越多的开发者在基于 Linux 系统构造嵌入式实时应用，他们迫切地需要一份基于 Linux系统构造嵌入式实时系统的指南性的文章。考虑到这种需求，本文在介绍了几种基本的实时进程调度算法的基础上，研究了普通的 Linux操作系统的进程调度，并十分全面地调查了各种实时 Linux 系统为了支持实时特性对普通 Linux 系统所做的改进。文章分析了将 Linux操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时 Linux是如何解决这些问题的，最后对于如何将这些已有的研究成果应用与实际的研究和开发工作中作了很好的建议。 第一部分： 实时调度算法介绍 对于什么是实时系统，POSIX 1003.b 作了这样的定义：指系统能够在限定的响应时间内提供所需水平的服务。而一个由 DonaldGillies提出的更加为大家接受的定义是：一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。 实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。如果明确地来说，软实时系统就是那些从统计的角度来说，一个任务（在下面的论述中，我们将对任务和进程不作区分）能够得到有确保的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。 一个计算机系统为了提供对于实时性的支持，它的操作系统必须对于 CPU和其他资源进行有效的调度和管理。在多任务实时系统中，资源的调度和管理更加复杂。本文下面将先从分类的角度对各种实时任务调度算法进行讨论，然后研究普通的 Linux 操作系统的进程调度以及各种实时 Linux 系统为了支持实时特性对普通 Linux 系统所做的改进。最后分析了将 Linux操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时 Linux 是如何解决这些问题的。 1. 实时 CPU 调度算法分类 各种实时操作系统的实时调度算法可以分为如下三种类别 [Wang99][Gopalan01]：基于优先级的调度算法（Priority-drivenscheduling-PD）、基于 CPU 使用比例的共享式的调度算法（Share-drivenscheduling-SD）、以及基于时间的进程调度算法（Time-drivenscheduling-TD），下面对这三种调度算法逐一进行介绍。 1.1. 基于优先级的调度算法 基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器总是调度那个具有最高优先级的任务来执行。根据不同的优先级分配方法，基于优先级的调度算法可以分为如下两种类型 [Krishna01][Wang99]： 静态优先级调度算法： 这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行，比如任务的周期，用户优先级，或者其它的预先确定的策略。RM（Rate-Monotonic）调度算法是一种典型的静态优先级调度算法，它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级。 动态优先级调度算法： 这种调度算法根据任务的资源需求来动态地分配任务的优先级，其目的就是在资源分配和调度时有更大的灵活性。非实时系统中就有很多这种调度算法，比如短作业优先的调度算法。在实时调度算法中，EDF算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各个任务根据它们的截止期限（Deadline）来分配优先级，具有最近的截止期限的任务具有最高的优先级。 1.2. 基于比例共享调度算法 虽然基于优先级的调度算法简单而有效，但这种调度算法提供的是一种硬实时的调度，在很多情况下并不适合使用这种调度算法：比如象实时多媒体会议系统这样的软实时应用。对于这种软实时应用，使用一种比例共享式的资源调度算法（SD 算法）更为适合。 比例共享调度算法指基于 CPU 使用比例的共享式的调度算法，其基本思想就是按照一定的权重（比例）对一组需要调度的任务进行调度，让它们的执行时间与它们的权重完全成正比。 我们可以通过两种方法来实现比例共享调度算法 [Nieh01]：第一种方法是调节各个就绪进程出现在调度队列队首的频率，并调度队首的进程执行；第二种做法就是逐次调

评论 (0) All

登陆 还没注册？