（计算机应用技术专业论文）嵌入式linux实时性研究与改进.pdf

西南交通大学硕士研究生学位论文第1 页 第一章绪论 1 1 嵌入式系统的定义及分类 嵌入式系统被定义为：以应用为中心、以计算机技术为基础、软硬件可裁 剪、适应应用系统对功能、可靠性、成本、体积、功耗严格要求的专用计算机 系统。1 1 l 根据不同的分类标准，嵌入式系统有不同的分类方法，由于嵌入式系统由 硬件和软件两大部分组成，所以其分类也可以从这两方面划分： 1 1 1 1 嵌入式系统的硬件： 从硬件方面来讲，各式各样的嵌入式处理器是嵌入式系统硬件中最核心部 分。目前，世界上具有嵌入式功能的特点的处理器已经超过1 0 0 0 种，目前主要 分为以下几类：【2 l 1 嵌入式微处理器o 咀c m c o n t m i l e ru n i t m c u ) 嵌入式微控制器的典型代表是单片机。从2 0 世纪7 0 年代出现到今天，4 位、8 位、1 6 位的单片机在各个领域有着极其广泛的应用。由于m c u 低廉的 价格、优良的性能、以及开发手段的简易性，m c u 拥有大量的品种，并占有 嵌入式系统约7 0 的市场份额。h i t e l 、m o t o r o l a 、p h 眦p s 等公司的产品为其 中的代表。 2 嵌入式d s p 处理器i 舀l a ls i 弘蛆p m c e s s ，d s p ) d s p 处理器是专门用于信号处理方面的处理器，其在系统结构和指令算法 方面进行了特殊设计，具有很高的编译效率和指令运行速度。在数字滤波，f f t 、 频谱分析等各种仪器上获得大规模的应用。自进入9 0 年代以后，d s p 发展到 了第5 代产品，集成度进一步增加，使用范围也更加广阔。目前最流行的是1 1 公司的i m s 3 2 0 c 2 0 0 0 c 5 0 0 0 系统。 3 嵌入式微处理器o 哪p m c 豁su n i t 。m p 们 它是由通用计算机中的c p u 演化而来的，它的特征是具有3 2 位以上的处 西南交通大学硕士研究生学位论文第2 页 理器，具有较高的性能，其价格也较高。目前主要的嵌入式处理器类型有3 8 6 e ) ( 、 s c 4 0 0 、p o w e r p c 、6 8 k 、a r m s t r o n g a r m 系统等。 4 嵌入式片上系统( s y s t e mo nc h i p ，s o c ) 片上系统s o c 是追求产品系统最大包容的集成器件，是目前嵌入式应用领 域的热门话题之一。其最大的特点是成功实现了软硬件无缝连接。 1 1 2 嵌入式系统的软件 目前嵌入式系统的软件主要有两大类：实时系统和分时系统。所谓实时系 统，是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时 间，如果系统的时间约束条件得不到满足，将会发生系统出错。 目前随着嵌入式系统的发展，在市场上占有较大份额主要有以下几种嵌入 式的操作系统：v x w o r k s ，r 卫ij n l 】x ，u a j n u x ，w i n c e ，q n x ，p a l mo s 等。 下边对以上几种操作系统作简要介绍； 1 v x w o r k s ：、飞w o r k s 是美国w i i l dr i v e rs y s t e m 公司( 以下简称风河公 司，即w r s 公司) 推出的一个实时操作系统。v x w b r l 蹬是一个运行在目标机 上的高性能、可裁减的嵌入式实时操作系统。 2 r t - l i n u x ：这是由新墨西哥科技大学( n e wm 懿i c 0m s l “u t eo f t c 岫o l o g y ) 开发的嵌入式u n l l 】【操作系统。到目前为止，r t - l 血u x 已经成功 地应用于航天飞机的空间数据采集、科学仪器测控和电影特技图像处理等广泛 领域。 3 u a i n u x ：u c u n u x 是u n e o 公司的主打产品，同时也是开放源码的嵌入 式u n l l x 的典范之作。u c u n u x 主要是针对目标处理器没有存储管理单元加讯7 ( m e m o r ym 龃a g c m e n tu n i t ) 的嵌入式系统而设计的。它已经被成功地移植到 了很多平台上。 4 w l n d o w sc em i c m s o f lw i n d a w sc e 是从整体上为有限资源的平台设计 的多线程、完整优先权、多任务的操作系统。它的模块化设计允许它对于从掌 上电脑到专用的工业控制器的用户电子设备进行定制。操作系统的基本内核需 要至少2 0 0 k 的r o m 。 5 q n xq n x 是一个实时的、可扩充的操作系统，它部分遵循p o s 相关 标准，如：p o s 1 b 实时扩展。它提供了一个很小的微内核以及一些可选的配 西南交通大学硕士研究生学位论文第3 页 合进程。因此q n x 内核非常小巧( q n x 4 x 大约为1 2 l 嘞而且运行速度极快。 6 p a i mo s3 c o m 公司的p a l mo s 在p d a 市场上占有很大的市场份额，它 有开放的操作系统应用程序接口( a p i ) ，开发商可以根据需要自行开发所需要 的应用程序。 1 2 目前嵌入式l i h u x 系统的应用 由于l m 驱是个与生俱来的网络操作系统，成熟而且稳定。u n 麟是源代 码开放软件，不存在黑箱技术，任何人都可以修改它，或者用它开发自己的产 品。u 如x 系统是可以定制的，系统内核目前已经可以做得很小。目前i j 矾x 已经在许多领域投入使用，发挥了越来越大的作用。 以下是目前已经使用u n u x 做为系统的嵌入式设备：【4 ”，从左到右依次是： m o t 啪1 ae 6 8 0 ip d ah a i c rn 6 0 ，e i i c s s o nc o r d k s sw e b p a 帅h o n e ，s h a i pz a u n l s s b c 3 1 0 0 ，i j n k s y sw i r e l e s sp r e s e n t a t i o ng a t e w a y 1 3 本课题目的及意义 嵌入式工业的基础是以应用为中心的芯片设计和面向应用的软件开发。 中国将是世界上最大的r 1 的s 市场之一。就目前的技术而畜，我国的嵌入 式u 肌x 的研究成果与市场的真正需求还有一段差距。因此，要开发出真正成 熟的嵌入式强实时u n u x ，还需要我们不断的进行努力。 由于u n u x 当初设计时是一种通用的操作系统，从而在实时性方面一直差 强人意，总结一下主要在以下几个方面： 内核的不可抢占性，本文主要从抢占锁、互斥锁，中断处理与调度函数四 个方面提出自己修改方法。 调度算法，针对目前l i 肿x 在实时调度方法方面的缺陷，建立调度模型， 西南交通大学硕士研究生学位论文 第4 页 提出新的调度算法。 中断处理及定时器细粒度，本文针对目前u u x 定时精度不高的问题，从 提高时钟中断服务程序效率、多模式的时钟中断和精密的时钟系统，三个 方面入手，分别分析了每个方面的好处与缺陷，并测试其结果。 本课题将重点深入研究在1 i l l 】【标准内核基础上对其实时性进行改进和完 善，使其内核更加完善以适应嵌入式系统。从而对其标准内核进行部分改造， 提出新的改进方法，以提高l i n 驱实时性。 1 4 本课题的内容及结构 本课题主要分一章绪论、三章的详细的描述和讨论以及一章的总结与展望， 从简单的嵌入式系统介绍入手，一层层剖析其内容，其中包括了l j n u x 系统和 内核改造和修改，内容如下； 第一章“绪论”介绍了嵌入式系统定义与分类。 第二章“内核结构的调整”介绍了【j 肌x 内核的结构和目前h 曲x 内核 所存在的不足，并提出了自己的修改u 肌x 内核实时性的方法。 第三章“对进程调度算法的研究与改进”详细的介绍了目前的l m u x 采用 的调度策略及其原理，在此基础上提出了新的修改策略，使其更适应实时系统。 第四章“中断反应时间与任务切换时间的调整”详细阐述了什么是中断， 以及中断在1 i n u x 中的作用，并描述了u 肌x 定时器的实现机制，以及目前i j n u x 定时器存在的缺陷，从三个方面论述了怎样提高u n u x 内核的时钟精度。 第五章“结束语”对本文的工作进行总结并对未来工作的展望。 西南交通大学硕士研究生学位论文第5 页 第二章内核结构 2 1 内核结构介绍 肉核，是一个操作系统的核心。它负责管理系统的进程、内存、设备驱动 程序、文件和网络系统，决定着系统的性能和稳定性。 一般来讲，操作系统上运行的代码可以分成两部分：内核程序所在的地址 空间称作内核空间，较低的应用程序所在的地址空间称之为用户空间；u x 内核主要包括下列功能：资源抽象，资源分配，资源共享。i l q i j n u x 与太部分的u n i x 内核一样是单内核体系结构( m o l i l h i c k m e l ) 的1 3 j j 与之对应的是微内核体系结构，这种内核只包括同步原语、简单的进程调度以 及进程通信机制等功能。一般来说，微内核相对于单内核来说要慢，但微内核 有模块化、移于移植等优点。n “使用“模块”( m o d i l l e ) 来有效弥补单一内 核的缺点，同时避免了引入微内核而带来的性能损失。 2 2 目前l i n u x 内核实时性增强的方案 i 血u x 分为用户态和内核态两种模式，进程运行在用户态时，实时进程具 有高的优先级，能进行进程抢占，故可以较好的完成任务；运行在内核态时， 如系统调用，实时进程不能抢占该进程。因此，从实质上来说，u u x 内核是 非抢占式的。 为了让l j n u x 实现硬实时的性能，目前有两种典型的解决方案： 2 2 1 双内核结构： 这种方法在同一硬件平台上采用了两个相互配合，共同工作的系统内核。 一个内核提供精确的实对多任务管理，另一个内核提供复杂的非实时通用功能， 如图2 1 所示【划，这种方法是通过在u n u x 操作系统的最底层增加一层实时核 心层来实现的。 心层来实现的。 西南交通大学硕士研究生学位论文第6 页 由于双内核机制保留了常规i j n u x 内核，以较小的代价提供了强实时性， 避免了大规模结构改造，新系统可以使用几乎所有常规i 抽操作系统提供的 功能，如：中文图形环境( ) ( w 缸d o w ) 、t c p ，口网络、丰富的编程资源等功能。 新墨西哥科技大学的r t _ i j n u x ，就是基于这种策略而成功开发的。 这种方法的一个关键所在是运行在常规lj 删x 核心上的所有非实时任务必 须是支持可抢占式调度的。这样才能做到对实时核心提供精确实时保证没有任 何影响。由于实时核心非常小，并不会增加整个系统的负载，所有这些对开发 实时性要求严格的实时软件提供了有力保障。 软中 m 一辱 ” 1 、t n n 内棱实时进程 黼111 宴时内棱 111 硬中断信号 硬件层 图2 ，1 双内核结构 2 2 2 直接修改u 懈内核 这类方案的共同点是针对以上提到的i j n u x 实时性能的缺陷，直接修改内 核，增强其实时性能。典型的例子是m o n t a s t a 公司的h a f dh a tu n u x ( 最新版 本已改名为m o m a v i s t ai j n u x ) 。【3 2 1 在实时性能方面，它提供了基于优先级的实 时调度器。基于无实时需求的进程，仍按i j 加x 原有进程调度策略进行调度； 而对于实时进程，则按照优先级驱动的原则进行调度，还实现了一定的抢占式 内核。 西南交通大学硕士研究生学位论文第7 页 2 2 ；3 目前内核存在的问题 尽管由于诸多原因，导致了i j m l 】【对实时支持的缺陷，但其中的主要原因 之一就是u n 职核心的不可抢占性。抢占( p r e e m p t i o n ) 是指当系统中出现一个优 先级高于当前运行进程的进程时，系统立刻中断当前进程运行该进程，以保证 在任意时刻当前所运行的进程都是系统中优先级最高的，这也是绝大多数实时 系统的调度方式。 h n u x 最初是以一种通用的分时系统为设计目标的，主要追求的是系统的 吞吐量和竞争的公平性。在标准i j n u x 下有用户态和核心态两种模式，当进程 运行在用户态时，很容易被优先级更高的进程抢占，但当它进入核心态时( 例 如通过系统调用f b r “) ) ，则其它的用户态的进程优先级更高，如实时进程，也 不能抢占处理核心态的低优先级的普通进程。这就是n 呱内核的不完全抢占 性。系统的抢占性是保证正确实现实时调度算法的一个重要因素。 而对于内核可抢占系统必须保护临界段以防止重入问题。通过以下方法可 以实现抢占式内核。 第1 种方法是只允许内核在已知是安全的、固定的点进行抢占，这些点称 为抢占点。改善一个非抢占内核响应时间的简单方法是在大致相同的间隔上设 置抢占点，执行到抢占点时进行检查，如果有高优先级进程就绪则抢占当前运 行，这样就可以限定新的高优先级进程必须等待的调度延迟的时间，最长的延 迟时间是内核中距离最长的两个抢占点之间的执行时间。抢占点是内核中这样 一些位置，内核的数据结构处于稳定的状态，并且内核马上要开始长时间的、 大量的运算。 第2 种方法是实现完全抢占内核，也就是内核可以在任何时间被抢占。当 然为了保持共享资源的一致性在临界段内仍然是不允许抢占，这就要求操作系 统提供某种互斥机制。 实现完全抢占内核的技术主要有3 种： ( 1 ) 在临界段的执行期间禁止中断，保证对临界段操作的原子性： ( 2 ) 使用信号量，获得锁后进入临界段，离开临界段时释放锁。如果进程 试图获得的锁已经被锁定则进程被阻塞，直到获得锁的进程离开临界段且锁被 释放，阻塞进程被唤醒，进入就绪队列等待调度： ( 3 ) 在临界段上使用抢占锁。系统维护一个全局变量，进入临界段时设置 西南交通大学硕士研究生学位论文 第8 页 该变量，离开时清除壕变量。当该变量被设置时说明进程在临界段内执行，不 允许抢占。如果此时发生中断，在执行完中断处理程序后将恢复被中断的进程， 不会进行调度。当获得抢占锁的进程离开临界段时释放锁，并检查是否有高优 先级进程就绪，如果有则执行上下文切换。 接下来将对i j n u x 内核的可抢占性进行分析和研究，提出自己的改造理念。 2 3 抢占式内核的实现 通过对u 肌x 内核源代码的修改可以实现对应用程序透明的完全抢占式内 核，采用抢占锁与互斥锁f 3 3 爿】两种同步机制对临界段提供保护的方法来提高内 核的抢占性。 使用抢占锁对内核中一般的临界段进行保护，允许系统在任何时间抢占未 被上锁的内核。当一个外部事件发生引发一个更高优先级的进程就绪时，即使 当前运行任务在内核态下运行，系统也可以立刻抢占当前运行的进程，并运行 这个更高优先级的进程。为了保证共享资源的一致性，根据u n u x 目前的实现， 对内核的抢占要遵守以下的原则，当内核运行于以下一些时机时不能进行抢占： ( 1 ) 进行中断或异常处理时。由于i 血u x 的中断处理没有实现内核线程化， 对中断嵌套的返回不能进行抢占； ( 2 ) 当获得自旋锁s p i n j o c k 和读写锬r 龃吐- l o c k r f i t e - j o c l 【时。这些锁控制 的内核代码是临界段，由于不可重入性和数据保护的原因不能被抢占； ( 3 ) 进行“b o t l o mh a l f ”处理时。b o l f o mh a l f 处理是可以在不需严格约束的 时间进行处理的中断程序，也就是在允许中断的情况下可以推迟进行的中断处 理： ( 钔当内核运行调度器时。调度器负责决定哪个任务获得c p u ，当它运行时， 不应使其放弃处理器。在所有其它时机都允许抢占，而且每当系统离开上述状 态对要检查是否需要抢占，如果需要，当前的进程将被抢占。 对于执行时间较长的临界段则使用互斥锁保护，“执行时间长”是指临界 段的执行时间远远大于进行两次上下文切换的时间。互斥锁是利用二元信号量 实现的。当进程在这类临界段执行时仅能够阻塞需要同一资源的进程，而不是 所有的高优先级进程，这将有效的减小进程的调度延迟。 西南交通大学硕士研究生学位论文第9 页 2 3 1 抢占锁的实现 为了实现抢占锁需要在u 珊x 的进程结构t a s k - t m c t 中增加一项抢占计数 器a l o m i 9 jp r m p l u n t 。当进程执行抢占锁时抢占计数器加1 ，当进程释 放抢占锁时抢占计数器减1 ，如果进程的抢占计数器值为o ，则该进程在内核 态下执行时可以被抢占。抢占锁属于一种递归锁，对于已经拥有锁的进程可 以再次获得抢占锁，也就是允许嵌套使用临界段。 在u n 腻的头文件i n c l u d 虮i n u 埔p i n l o c k h 中增加设置抢占计数器和清除抢 占计数器的宏： 卑设置抢占计数器，禁止内核抢占。* 黼e p r e e m p t _ i o c l u 敝) d o a t o m i 屯i n & p t e e m p l c o 岫t ) ；用原子操作使进程的内核抢占计数加1 ) w h i l e ( 0 ) ； 阜清除抢占计数器，并在进程抢占计数为0 时完成内核抢占。 荸d e f i n ep r e e m p u o c ：k - 0 n _ _ n o p r e e m p t ( ) d o a t 0 1 n i c e c ( p r c e m p t _ c 叫n t ) ；用原子操作使当前进程的内核抢占计数 减1 ) w h i l e ( o ) ； 广清除抢占计数器，并在进程抢占计数为o 时完成内核抢占。 群d e 血ep r e e m p t _ l o c ko n ( ) d 0f a t o m i 叫e c ( p r e e m p t - c o u m ) ；p 用原子操作使当前进程的内核抢占计 数减1 + i f ( p r e e m p t _ c o u n t = = 0 c u r r e n t - n e e d e s c h e d ) s d l c d u l e ( ) ；则进行抢占调度 ) w h i l e ( o ) ； 其中c u e n t 是当前运行进程的进程结构，当前进程的时间片用完或有高优 先级进程就绪时置c 眦e n t 一 n e e d j e s c h e d 为1 ，表示需要进行调度。 为了保证对抢占锁操作的原子性，抢占计数器加1 和减1 的操作使用u n u x 西南交通大学硕士研究生学位论文第2 1 页 第三章对进程调度算法的研究与改进 3 1 有关进程调度相关概念 进程调度分成两个部分，一个是调度的时机，即什么时候调度：一个是调 度的算法，即如何调度和调度哪个进程。h u 肌x 进程调度时机 调度时机是指在什么情况下运行调度程序来选择进程运行。在u n l l 系统 中调度程序是通过函数s c h e d u l “) 来实现的，这个函数被调用的频率很高，由 它来决定要运行的进程。 u 肌x 调度时机主要分两种情况：主动调度和被动调度。主动调度是指当 进程状态发生变化时直接调用s c h e 咖“) 来实现调度。被动调度是指当一个进 程运行时间片到或就绪队列中增加了一个进程，此时系统并不立即进行调度， 而仅仅是将当前进程的调度标志位置1 ，当系统由核心态往用户态转变之前检 查当前进程的调度标志是否为l ，若为1 ，则调用s c h e d u l e ( ) 进行调度。 3 2 进程调度的原理 调度程序运行时，要在所有可运行状态的进程中选择最值得运行的进程投 入运行。选择进程的依据是什么呢? 在每个进程的 t a s ks t n l c t ( i n d u d 枷i n u 加c h e d h ) 结构中有以下四项：p 0 1 i c y 、p t i o r n y 、u n t e r 、 岫r i o r i t y 。【1 2 】这四项是选择进程的依据。其中，p o l i c y 是进程的调度策略，用 来区分实时进程和普通进程，实时进程优先于普通进程运行；p i i o r n y 是进程( 包 括实时和普通) 的静态优先级：c o u n t e r 是进程剩余的时间片，它的起始值就是 p r i o d t y 的值；由于c o u n t e r 在后面计算一个处于可运行状态的进程值得运行的 程度g o o 血e s s 时起重要作用，因此，c o 岫t c r 也可以看作是进程的动态优先级。 岫r i o r i t y 是实时进程特有的，用于实时进程间的选择。 u n u x 用函数9 0 0 d e s s ( ) 来衡量一个处于可运行状态的进程值得运行的程 度。 x 西南交通大学硕士研究生学位论文第12 页 m o v le f l a g s ( e s p ) ，e a x群合并e f l a g s 和c s m o v bc s ( e s p ) ，a l t e s u $ mm a s ki3 ) ，e a 】【群是否返回到v m 8 6 模式或用户态 i n er e tw i 也一r e s c h e d u l e 撑是，则执行调度； j m pr c s t o r e a l 社否则，恢复被中断的进程 c s ( c s p ) 保存了中断产生时代码段的c p u 特权级( c s 寄存器的b i t 0 和b i t 1 ) ，如果等于3 ，也就是用户态，那么可以执行调度；否则表明在内核态下， 不执行调度，结束中断后返回被中断的进程。可以看出上面的代码限制了内核 中只能有一个进程的实例在运行。 在u n u x 中，当异常处理完毕后调用r e l 肋m _ e x p t i ( ) ，而 r e l 加i n - e x c e 埘o “) 也要调用r e t _ 丘o m j n 蜓) ，所以从异常返回后对抢占的判断 与从中断返回时的情况相同。 为了实现抢占式的l j n u x 内核，必须对中断的处理过程进行修改。其要点 是在中断返回进行抢占性判断时，如果进程在内核态下运行，还必须要判断是 否可以对内核抢占，即判断进程抢占计数器的值是否为o 。修改后的中断处理 流程如图2 2 所示。 西南交通大学硕士研究生学位论文第13 页 中断产生源 j 中斯向量 中断入口程序 保存硬件中断现场； 增加咖r r 舶t _ p r 钟m p l u t ； j 中断处理程序 i 吲j ! m j n 打0 捌 小c l i r 他n 卜p 弛卸难t ，u n t i f ( 返回v m 8 6 模式或用户态) 执行调度程序： e h e l f 呵以进行抢占) 执行调度程序： e l 恢复被中断的进程： 图2 2 修改后的中断处理流程 为了在进行中断处理期间禁止抢占内核，需要修改中断入口程序，在保存 硬件中断现场后增加当前进程的抢占计数器，也就是c u 咖t p r e e m p tc o u n t ， 这样在中断处理程序执行期间进程的抢占计数器大于o ，进程不会被抢占；在 中断返回处理程序r e t - 且o m - i n 呱) 中首先减小当前进程的抢占计数器，这样就 恢复了进入中断前进程抢占计数器原来的值，然后就可以根据抢占计数器的值 判断当前进程是否可以抢占。对异常入口处理程序的修改与对中断入口处理程 序的修改类似。 西南交通太学硕士研究生学位论文第1 4 页 萎翼琵冀嚣誉五酱* 辎筒腻；滴隳鎏彗羹罱港列骣计职支蒂耋萋葶圭；葡 垂丽蠹鹪翼抛哩观；雾i 璺饕羔羹薹雾”垮缱誊蠢鐾疆莲学交巍鏊嚣笳塑葡匿薹； 翼瑟蠹鬻凄翼藕程耐噶丞! 趟藉y 咚曼霭固羹鬻澎萋茆i 琢点蟊面蠢稻篓蓊镯 节通箭! 盏搿圜鱼霸鬻茅蠢蛙；鍪涔尚撼翼蔷蜀黍馑鎏巍甜妊墨篓嚣笪蓁； 焉篓蒴萎嚣逸踺渲崾圳点蠖鞫烈幕鞘；笔漂融陵暖墅犁孺董鑫霪产南翼孽蔓 童蠹删妻；墓请皤! 苜； 甄烈嘉囊孽i 薹l 霪1 1 ；誊z r 氢i l l l 嚣| 孽冶淄绘灞岽黼磷酐韵引妇鞘甬雾望霁塑 霎j 羹葡翼羹霎舞拜f 雯j 霎翼藿磊蛹羹霎蠢商蓁。鏊矍廷冀丽蓁冀鋈蝗耍垫鋈 雾壁耄 鬻薹嗝嚣遁羹挚b 鍪落爨禹藿篓蠹i 雾g 萎囊墅篓释嚣蔫掣0 裂杖瑶 宴墨霞鞠1 两。餮薹莲匏曼剡一匹柳划掘刚捌i “墓财童塑莲蝉2 1 l l 薹鋈裂蒂驯蕞黑面渤蓬萄啊阳译嘲拦灞| 。囊 瑟誉封蚤；冀荔一笺鍪美型鎏攀霪蓬甄醚非酶i 美至薹雨蠢丘墓羹囊巍嚣| 璧錾蠹冀羹m 翻j 冀呼羹孽甚一霎篓s = ! ! 耋目垂je 三 j 鹊黟萋蠡蓍；囊i i 基i l l 鎏i 同i ；薹| i i l i 贮鞠辩蟑氆獬鲣誓 弭“靶配骘塑弼寐业 酗，鬯孽篓簿g 举喾驯引，簧墨互杂击辐牟驿朱煮；彰商彦i i 基娼堡硷铿一 鬟弊鼓鲴婺艇譬g 靶酩蛩髅i 描替掣至! 到蒜置燃譬哥霪，；? ， 萋：萋；羹薹霎羹藜囊辇季 嘲攀【j ：目南嘲吲巨谚别撕婴e 嚣篓葡戮蜮鐾，羲劐蠢鹱嚣鞋弹鬣攘 蠹l g m e l ， h e d i i ：a s m l i n k a g e v o i ds c h e d x 西南交通大学硕士研究生学位论文第1 5 页 p r c e m p u o c ko 皿) ； 似椭l x 原来调度的实现 p r e e m p l l o c ko - _ n o - p r e e m p t ( ) ； 这里减少抢占锁计数器使用的是p r e e m p u o d 【_ 0 n _ n q _ p m 孽囊i 滤唾 蠢噬 晶薹墼霪囊辇妻i ；，龋雕移爵稀帅 薹豇皤b 嘲塞雾ll 拍鞭鞴貉；引锄鲫葡醋裂良 m 吲勾f 冠妫协谲循潍一唔嘱耨i 糟阜曩浔艨0 囊攘一- 囊模型的建立 作为实时系统调度算法应综合考虑进程的价值和截止两个概念，以保证实 时进程在截止期内尽可能多地完成。因此本文提出新的调度算法中实时进程的 优先级数计算公式为： w 。谢+ 卫+ 七 d 一外 公式中各参数定义 ( 3 8 ) v i 表示进程的优先级数，w i 表示该进程的价值( 代表进程的重要程度) ，p i 表示进程的估计执行时间，d 表示绝对截止期，t i 表示该进程提交时间，( d t i ) 是相对截止期，即该进程最大容忍的等待时间，在相对截止期内，这个进程就 应该被执行，否则这个进程夭折；兰这里称之为紧迫度，即这个值越大，说 一l f 明从时间上看这个任务越紧迫，k 是系数因子。 优化后调度算法仍以进程的价值为基础，同时也关注了完成进程的紧迫度， 对于优先级相同的进程，采用啪调度策略。进程的价值越大说明该进程越 重要，c p u 越应完成它，可是对一些价值和它相差不多，而紧迫度要比它大得 多的进程来说，就不公平了。例如，有两个进程a ，b 同时提交，a 的价值是 1 0 0 1 ，估计执行时间是1 1 n s ，相对截止期是5 m s ，b 的价值是1 0 0 0 ，估计执行时 间是1 m s ，相对截止期是2 m s ，假设这里的系数因子k 是1 0 ，则更应该执行进 程b 。这是因为进程a ，b 的价值相近，而b 的紧迫度要比a 的大一些，a 的 优先级= 1 0 0 1 + 1 5 1 0 = 1 0 0 3 ，b 的优先级= 1 0 0 0 + 1 2 1 0 = 1 0 0 5 ，因此选择b 先运 行，以防止b 的夭折( 注：u n u x 中实时进程的值设为从1 0 0 0 到1 0 9 9 ，非实时进 程的值设为从1 到9 9 ，因此选择系数因子k 为1 0 ) 优化后的调度算法依然采用 西南交通大学硕士研究生学位论文 第1 7 页 程状态标志位1 a s k 崔搓_ 们件要共畦委；滢毽诂曼虱，蔺鍪道咧渺翰西腑葡翻 看誉于时间片到或被更二辑鞋弹堪鲤辎i 雾咀s ：；螋沥砸渤l 霎l 国瑚墨蕊警蓄 哥需馨菱疆蒜碡擘垄鎏奏上图；疼器嘲坦菊览晖偈隧霪铲 萋耋曼蠹鏊转妻垲麓萋j 割煳眦向f 墅刚廷铲二恳靖墼稽囊瞪潭惯趔圳匾唧型切哑 塬呵慷9 li 坦登k 吕p | 量i ! ! 髟自 级 队列。 非实时进程的调度也通过单链表来实现。如果新来的进程属非实时进程则 根据优先级高低插入非实时队列。只有实时队列( 一级和二级队列) 为空时，非 实时队列才能被调度。 3 4 4 实时进程的调度策略算法描述 实时就绪队列的初始化 撑d e f i n eu ns i z e o f ( 1 b k n o d e ) o d e c r e 也n e w _ l i n e ( ) p 创建空链表+ 1 a s k n 0 d e h e a d ： h e a d = c 陆l 妯d e ”m a o c ( l e n ) ； h e a d - w = - 1 ： h e a d l = h e a d 2 = h e a d ： h e a d l - n e x t = h e a d 2 - n e x t = h e a d ： r e t u mh e a d ： 实时进程接收策略 x 西南交通大学硕士研究生学位论文 第1 8页 舟m a k e x c o n j ! ；i g 进行配置时，大部分选项可以使用缺省值，只有小部分需要根据用户不同 的需要进行选择。将与核心其它部分关系较远且不经常使用的部分功能代码编 译成为可加载的模块，有利于缩减内核的，减小内核消耗的内存，简化该功能相应的环境改变时对内核的影响。 配置完内核，接下来运行阻下两条命令清除源代码树，产生相关文件：撑m a k ed e p群m d k e d e 强 下面的命令将编译产生压缩形式的内核文件：静m a k ez h n a g e 或在需要内核支持较多的外设和功能时，内核可能变得很大，此时可以用 以下命令编译大内核产生压缩率更高的内核文件：撑m a k e bzhnage 这需要花费一段时间，生成新的内核后，分别选用新旧两种内核进行测试。 在这里选用a m l a t 做为测试工具，用来测试任务的响应时间，a m l a t 的主 要程序是r e 北e 1 岛该程序的主要思想是通过r 1 暇lt i m e c l o c k ) ，也就是 实时时钟，产生中断来测量响应时间的具体的做法是让测量程序对devnc：进行 读操作，该读操作是一种阻塞读操作，它必须在一次实时时钟的中断后才能完 成，因为这样才能得到最新的时间因而每次实时时钟产生中断，就可以结束一 次对l 她r 帆c ：的读操作程序设置实时时钟的中断次数为2 k h z ，这样对，d e v n c ：的读操作也应有每秒2048次因此每一次测量的理想值应为12048秒，也就是 488微秒把该理想值与实际测量值相比较就可得系统的响应时间。分别启动两种不同的内核，用realfeel来启动5x106次迭代(5x106次时钟中断)在中断频率为2048次秒，即运行大约40分钟。运行完成后成hist0掣锄文件并把测试结果写入其中，这个直方图显示在微秒内或几十微秒内延迟发生的次数，接着用髓uplot生成图表，(在这里用对数表)。下列图表即生成的标准内核和抢占式内核的图表以及一些统计数据(用sheu脚本提取略)：【柏】实际测量值的测量主要依据于时间戳寄存器(tsc)，由读操作前后的tsc的差值，依据cpu的晶振频率就可以转换以秒或毫秒为单位的时间值。我们选用lmx的2418内核(intclccl啪n2gcpu，256ddr内存)避逃逊逝选遵迷遴ttdd88版nnhkaa日a行杼符厅打秆抒衍荇纾00rrhh洹ex 西南交通大学硕士研究生学位论文第19 页 在测试时，。在另一个窗口执行l s - l r 命令作为系统的负载。 2 4 1 原始版本与修改后的抢占式版本的情况 图2 原始内核的测试情况 图2 4 修改后的内核测试情况 西南交通大学硕士研究生学位论文第2 0 页 2 4 2 结果分析 通过s h d l 脚本提取数据分析如表2 1 所示，显示结果可以看出抢占式内核 明显提高了实时系统的延迟性能，大多数样本都低于5 m s 以下。最大延迟时间 是4 5 2 m s ，平均延迟时间是5 2 8 u s 。 表2 1 原内核与抢占内核的数据比较 2 4 ，1 8 m a x ( d m s 2 3 2 6 m e 如f m s ) 0 0 8 8 3 2 3 l o 1 m s ( ) 9 2 8 4 l o 2 m s ( 1 9 7 0 8 i 0 5 m s ( ) 9 9 7 3 l ( 1 m s ( 1 9 9 9 4 9 6 l 5 m s ( ) 9 9 9 8 l l o m s f 19 9 9 8 l n e x t ； i f ( h = = h e a d1 ) 插入一级队列 w h i l e ( ( 4 p ) w = ( + p 2 ) w p l ! - h e a d 2 ) 优先级相同的进程采用f 1 f 0 调 西南交通大学硕士研究生学位论文 第3 1 页 度策略 p 1 = p 2 ； p 2 = p p 2 ) n e x t ； ) ( p ) n e x t = p 2 ； ( p 1 ) n e x t = p ； i f ( p 1 = = h e a d 2 ) 该节点插入到一级队列的末尾，则该节点便成了一级 队列的末尾 h e a d 2 = p ； e l s e w 埘e “p ) w = ( p 2 ) w ) 施入二级队列 p 1 = p 2 ； p 2 = ( 幸p 2 ) n e x t ； ( + p ) n e x t = p 2 ： ( + p 1 ) n e x t = p ； ) ) 说明：根据传来的h 值，决定在一级队列h 的值是h 朗d l 时还是在二级队列 h 的值是h e a d 2 时中查找插入的合适位置。 当p 是新来的任务时，h 的值是h 髓m ，p 被括入一级队列。p 2 是p 1 的后继 节点。在循环体中，当新来的进程p 高于一级队列的进程p 2 时，停止循环，将 p 插入到p 1 的后面；当p 1 等于h e a d 2 时，说明一级队列的节点的优先级都比 p 节点的高，停止循环，把p 插在p 1 的后面，则该节点便成了一级队列的末尾。 当p 是被抢占的任务时，h 的值是h e a d 2 ，p 被插入二级队列。在循环体中， 当p 的优先级高于二级队列的进程p 2 时，停止循环，将p 插入到p 1 的后面； 如果p 高于= 级队列的所有进程时，也会在p 2 指向h d 时，因( p ) w = ( p 0 w ) d t i e ) m o v e j 鹊t - t 肋q u e u e ( h e a d 2 ，o w ) ，将未完成的进程插入到 二级队列 e l s e p n o w ； 被夭折 e l s e m o v t j 够t ( p n o w ) ；将未完成的非实时进程插入到非实时队列 ) p = g e l n o d e ( ) ；从就绪链表中获得优先级最大的进程 州】1 ) j f o i _ n u l l ) i f ( ( + p ) t i i n e “+ p ) d t i m e - p n ，伽e ) ) 进程未完成的时间大于 相对截止期，该进程夭折 ( h e a d l ) n e x t = ( 4 p ) n e x t ； j f0 = = h e a d 2 ) ，删除的节点是一级队列的尾节点时 h e a d 2 = h e a d 3 ；二级队列荣升为一级队列 h e a d 3 = h e a d 2 ；新二级队列为空 ) e l s e p 进程可以在规定时间完成 r e t u m p ； e l s e 无进程等待 r c t u mn u l l ： ) 针对目前l i n l l x 实时系统调度算法中仅用进程的价值来确定优先级的现 象，本文提出了综合考虑进程的重要性和紧迫度来决定优先级的调度算法。算 西南交通大学硕士研究生学位论文第3 4 页 法将进程的截止期和价值两个不相关的概念，通过公式( 3 8 ) 结合在一起，用来 计算就绪等待队列中进程的优先级数。 该算法通过双链表来实现。在c p u 正常负载的情况下，优化后的调度算法 体现了更优的实时性能。 西南交通大学硕士研究生学位论文 第3 5 页 第四章中断反应时间与定时器的调整 4 1 中断机制及其原理 计算机内部的中断主要有两种【4 l ，一种是由c p u 外部产生的，一种是由 c p u 本身在执行程序的过程中产生的。也就是通常所说的异步中断和同步中 断，外步中断也就是通常所说的“中断”，对于执行软件来说，这种中断完全是 “异步”的，根本无法预测此类中断是在什么时候发生，因此c p u 对外部事件 的发生完全是被动的。由软件产生的中断则不同，它是由专设的指令，如x 8 6 中的“盯n ”，在程序中有意产生的，所以是主动的，“同步”的。只要c p u 执行了一条盯指令，就知道在开始执行下一条指令前一定要先进入中断服务 程序。这种主动的中断称为：“陷阱”。 在i n t c l8 0 x 8 6c p u 手册中，同步中断和异步中断也被分别称为“异常 ( e x c 印t i ) ”和“中断( n t e l n l p i ) ”。砷e 1 又详细地把中断和异常细分为以下 几类：【叭 ( 1 ) 中断：可屏蔽中断( m a s k a b kh l t e m l p t ) ，不可屏蔽中断( n 伽m 鲢k a b l e i m e 删p t ) 。 ( 2 ) 异常：处理器探测异常( p r d c e s s o r d e t e c t e dc x c e p t i o n ) ，编程异常 ( p r o 乎煳e db x c 印t i o n ) 。 4 2 中断反应时间和任务切换时间 由于目前u n l l x 过长的中断反应时间和任务切换反应时间，从而造成目前 l i n l l c 的实时性能不佳。 过长的中断反应时间是由于和中断一起运行的冗长核心代码段被禁止造 成的。这就限制了操作系统响应中断的频率。 任务切换反应时间在一个普通的n u x 内核里，用户模式的进程都是抢先 多任务的( p r c e m p i i b l e ) ，但是到内核里的系统调用却不是。在极少的情况下， 有些系统调用能够花几十或者几百毫秒来完成，而不会受到其它的进程的限制。 西南交通大学硕士研究生学位论文 第3 9 页 s t a l i cs t n i c tt i m e r j c cr o o tt v ；l l ! 璧篓要裂墓 ；壤茸i 譬嬲 舅篓r i 尚蠹囊 ；|蠢蓉爨 ；雯曼 羹羟。i 蠢f i j 蒌岛；蔫茜i j 一墨重；耋滴l i 飞机到移动电照研塞。期y 。盈傅殳 ”雾醑葬i 虿崮崔嚣囊；塑 h 萎囊豁辫l 墼型毡暂玢配h 獬l ；篓鲡篓骣一妄l i 量嘉i 耄h 蕊g i 谐煞猿曼魅扣拢i 载靶得 茸e 墓j 的应用软件基础提 供了坚实的后盾。 但是由于u m 是一种通用操作系统，而不是一个真正的实时操作系统， 而只能称其为软实时操作系统，而不是一种强实时系统。其标准内核不支持事 件优先级和抢占实时特性，没提供很多嵌入式应用程序所需要的可预测响应时 间( p r e d i c t a b l er e s p o n s et i i n 伪) 等。所以，在进行嵌入式i j n 职系统动态扩展性 研究开发时，首要的问题是扩展u n u x 的实时性能。 由于l i n u x 主要在三个方面不利于实时性的增强，即过长的中断封锁时间， 非抢占式的内核，耗尽的、机会均等的调度策略，本文结合目前的常用的改造 内核的方法，提出新的修改方式，重点在l i n u x 以下几个方面着手： 内核的不可抢占性，本文主要从抢占锁、互斥锁，中断处理与调度函 数四个方面提出自己修改方法。 调度算法，针对目前u n l l x 在实时调度方法方面的缺陷，建立调度模 型，提出新的调度算法。 中断处理及定时器细粒度，本文针对目前u n u x 定时精度不高的问题， 西南交通大学硕士研究生学位论文 第4 1 页 4 5 1 时钟频率的修改 在以x 8 6 为处理器的p c 上，系统时钟可以提高的最高频率超过了1 m h z ， 但u n u x 通过对它的编程，