（电路与系统专业论文）嵌入式linux实时性应用研究.pdf

西南科技大学硕士研究生学位论文第1 页 摘要 l i n u x 实时化是指通过系统改造使其具备实时系统的一些特性，保证某些任务 的调度和执行在规定时问内完成。实时性是嵌入式系统的一个重要考量，l i n u x 系 统设计并非实时性操作系统，但它具备很多优良的结构特点，非常适应嵌入式设备 的应用环境，因此l i n u x 的实时性研究是极具应用价值的课题。本课题旨在寻找 l i n u x 实时性缺陷、探讨部分实时化方案的原理与可行性，并且将方案作工程应用 上的尝试。论文根据内核时钟粒度较粗、定时精度不高等特点主要研究了嵌入式 l i n u x 的系统构建、时钟原理、高精度时钟子系统的工作机制和测试、高精度定时 器接口的创建和工程应用。 本文构建了能够稳定运行的嵌入式l i n u x 系统，硬件平台为中嵌科技公司 c e 9 2 0 0 3 。在理论上，对l i n u x 实时性的缺陷做了较全面的概述，重点分析其时钟 精度低的原因，详细论述了h r t 子系统对内核时钟精度的修改方案：在应用上，实 现了基于高精度时钟( t i r t ) 方案的设备驱动和用户接口，并将两者应用于车载恒温系 统的核心控制部分。底层定时器实现了系统高速数据采集和温度控制。 。关键词：嵌入式l i n u x 实时性内核时钟h r t 西南科技大学硕士研究生学位论文第页 a b s tr a c t l i n u xr e a l - t i m ec h a n g i n gm a k ei tt oh a v es o m ec h a r a c t e r i s t i c so ft h er e a l - t i m e s y s t e m st h r o u g ht h es y s t e mt r a n s f o r m a t i o n ，e n s u r i n gc e r t r i nt a s ks c h e d u l ea n de x e c u t i o n w i l lb ec o m p l e t e do nt i m e r e a l - t i m ei sa ni m p o r t a n tc o n s i d e r a t i o ni nt h ee m b e d d e d s y s t e m , l i n u xs y s t e md e s i g n a t i o ni sn o tr e a l - t i m eo p e r a t i n gs y s t e m ，b u ti th a sm a n y e x c e l l e n ts t r u c t u r ec h a r a c t e r i s t i c s ，a n di sw e l la d a p t e dt ot h ee m b e d d e de n v i r o n m e n t , s o t h er e s e a r c ho fr e a l - t i m ea b o u tl i n u xs y s t e mh a v ee x t r e m e l ya p p l i c a t i o nv a l u e t h i s s u b j e c ta i m st of i n do u tr e a l t i m ed e f e c t sa n dp a r to ft h ep r i n c i p l eo f r e a l - t i m es c h e m ea n d f e a s i b i l i t y , a n da t t e m p t i n gt h es c h e m eo nt h ee n g i n e e r i n ga p p l i c a t i o n b e c a u s eo ft h e t h i c k e rc l o c kg r a n u | a r i t yo fk e r n e la n dl o w e rt i m i n gp r e c i s i o n w es t u d i e dt h es y s t e m c o n s t r u c t i o n ，c l o c kp r i n c i p l e , a n dw o r k i n gm e c h a n i s mo fh i g hp r e c i s i o nc l o c ks u b s y s t e m , u s e ri n t e r f a c ee s t a b l i s h i n gw i t hh i g hp r e c i s i o no f t h et i m e ra n de n g i n e e r i n ga p p l i c a t i o n ，n l ee m b e d d e dl i n u xs y s t e mi sc o n s t r u c t e ds t a b l yi nt h i sp a p e r , h a r d w a r ep l a t f o r m c e 9 2 0 0 3c o m ef o r me m s y s c h i n ac o ，l t d i nt h e o r y , w eh a v eac o m p r e h e n s i v eo v e r v i e w i nr e a l t i m ed e f e c t so f l i n u xk e r n e l w ea n a l y z e dt h er e a s o n sf o rt h el o wp r e c i s i o nc l o c k ， a n dm o d i f i c a t i o np l a no fh i 曲r e s o l u t i o nt i m e r ( h r t ) s u b s y s t e m0 1 1k e r n e lc l o c k p r e c i s i o n ；i na p p l i c a t i o n , w er e a l i z e dt h ed e v i c ed r i v e r sa n du s e ri n t e r f a c eb a s e do nh r t , a n da p p l i e dt h e mt ot h et e m p e r a t u r ec o n t r o ls y s t e m w er e a l i z e dt h eh i 曲s p e e dd a t a a c q u i s i t i o na n dt e m p e r a t u r ec o n t r o l l i n gb a s e do nt h et i m e r d r i v e k e yw o r d s ：e m b e d d e dl i m i ) 【；r e a l - t i m e ；k e r n e lc l o c k ；h r t 西南科技大学硕士研究生学位论文第1 页 1 绪论 1 1 研究背景 l i n u x 是常用的嵌入式操作系统之一，稳定的系统结构和便于移植的特 点使其迅速成为了嵌入式领域的主角瞻”。l i n u x 系统从功能上讲是较为全面 的，作为最早的通用操作系统之一，它的执行效率和稳定性不逊于商业操作 系统。然而应用于嵌入式领域的操作系统，实时性能是重要的考量标准，l i n u x 的设计初衷为p c 兼容机操作系统，并没有太多考虑系统的实时性能。目前， l i n u x 2 6 内核时钟频率最高为1 0 0 0 h z ，即毫秒级定时精度，在高速数据采集 或收发的情况下往往难以接受。不过，l i n u x 系统本身具备不少优势，内核 的完全开放，使得自行设计和开发出真正的硬实时系统成为可能n ，：对于软实 时系统，在l i n u x 中也容易得到实现t ，。由于系统的广泛使用和实时化的迫 切需求，l i n u x 的实时化成为了极具应用价值的研究课题。笔者正是在这样 的背景下，并结合中电十四所的“嵌入式车载诱饵冷却系统”拟定了这一课 题：嵌入式l i n u x 实时性的应用研究。 1 2 研究的目的及意义 嵌入式l i n u x 实时化研究本身是一个非常庞大的课题，它涉及到体系架 构、操作系统原理、调度策略与算法等多门计算机学科知识。限于精力并结 合项目需要，笔者的研究工作希望到达以下目的和意义： ( 1 ) 研究l i n u x 内核运行机制和实时化方案，并作出讨论和总结。 ( 2 ) 在a r m 处理器上构建嵌入式l i n u x 系统，掌握嵌入式l i n u x 的主要 构成因素和各环节开发的关键技术。对系统的移植和开发做深入的学习和研 究。 ( 3 ) 对部分实时化方案进行扩展和应用移植，并给出测试数据。 l i n u x 本身是一个宏内核结构”，其设计非常复杂。而由于l i n u x 内核各 个部分衔接紧密，互相牵制，可以说是牵一发而动全局，所以从这个角度来 改进其实时性存在相当的难度，。笔者认为，通过研究部分实时化方案，并 继续进行适当的扩展和应用，将理论与实践相结合更能体现出应用研究的意 义。 ( 4 ) 将实时功能接口应用于“嵌入式车载诱饵冷却系统”的部分内容，并 西南科技大学硕士研究生学位论文第2 页 完成温度采集和控制部分的工作。 1 3 嵌入式l in u x 简述 l i n u x 由l i n u st o r v a l d s 在1 9 9 1 年设计并开发，最初设计目的是开发一款 兼容i b m p c 机的操作系统，然而由于l i n u x 开放性的特点和极具灵活性的 系统架构，其发展在现今已经远远超出了其最初的设计理念。 嵌入式系统是用于控制或者监视机器、装置、工厂等大规模系统的设备 ，是当前最具发展前途的信息技术应用领域之一。嵌入式的应用领域极广， 包括手机、电子字典、可视电话、数字相机、数字摄像机、机顶盒、游戏机、 路由器、数控设备、车载电子、家电、医疗仪器、航天航空设备等都是典型 的嵌入式系统。 嵌入式l i n u x 是指将l i n u x 操作系统进行裁剪修改，使之能在嵌入式计 算机系统上运行的一种操作系统m ，。较典型的开发模式如下图： 相比其他嵌入式操作系统而言，它具有如下特点： ( 1 ) 开放性代码 l i n u x 是内核源代码公开的操作系统，并没有采取商业操作系统的黑箱 技术。这个特点，使l i n u x 具有了遍布全球的强大技术支持，大量工程师多 年的开发和补充，使其积累了门类众多的技术应用案例。使用l i n u x 进行嵌 入式开发的技术人员拥有丰富的代码资源、参考对象和开发工具，可以有效 提高项目的开发效率。 ( 2 ) 可自定制的内核结构 在实际应用中，在嵌入式系统上使用的内核应具有，尺寸小，功能可裁 剪，执行效率高和稳定性好的特性。首先，作为模块化构架，l i n u x 各模块 之间的耦合性很小，某个模块的卸载或损坏不会对整个系统性能产生负面影 响m ，：其次，用户可以根据实际需求自行裁剪内核，提高执行效率；另外， 内核体积可压缩，处理后可至几k 字节，能满足大多数嵌入式系统的要求。 ( 3 ) 支持大多数硬件平台 l i n u x 内核已经被移植到多种硬件平台上，目前已经支持i n t e l x 8 6 、 p o w e r p c 、a r m 和m i p s 等处理器，具备成熟的系统移植方案。设计者几乎 可以选择所有主流的硬件平台来进行项目开发，有效减少了内核移植的工作 量。 ( 4 ) 多样的文件系统 西南科技大学硕士研究生学位论文第3 页 图1 - 1嵌入式l i n u x 开发流程图 f i g u r e1 - 1t h ed e v e i o p m e n tf i o wc h a r to fe m b e d d e dl i n u x 嵌入式l i n u x 除支持包括r a m d i s k 、n o r f l a s h 、n a n d f l a s h 等的常用嵌入 式文件系统外，也兼容类似f a t 、n t f s 等硬盘格式的文件系统。除此以外， l i n u x 还支持如n f s ( n e tf i l es y s t e m ) 这样的网络文件系统。设计者可以根据 实际情况来选择多种存储方式，以适应于不同的应用场合。 ( 5 ) 支持i e e ep o si x ( p o n a b l eo p e r a t i o n ss y s t e mi n t e r f a c e ) 标准 l i n u x 的应用软件代码由c 或c + + 语言编写，代码完全可以在标准p c 平台上开发，完成后选择相应交叉编译器生成执行文件。执行文件可以跨平 台执行，代码使用率高。 1 4a r m 处理器简介 a r m 的全称为进阶精简指令集处理器( a d v a n c e dr i s cm a c h i n e ) ，是一种 3 2 位元中央处理器架构m 1 。a r m 系列处理器被广泛应用于嵌入式系统的设 计。 西南科技大学硕士研究生学位论文第4 页 目前常见的嵌入式处理器架构包括p o w e r p c 、m i p s 、m o t o r o l a 、i n t e l x 8 6 和a r m 等，然而a r m 以其高效和低耗能的设计，占据了大多数的市场份额。 主要芯片制造商在a r m 核的基础上扩展自己的外设，设计出了型号众多的 a r m 处理器以满足不同的嵌入式应用方向，其中较著名的有三星公司的 $ 3 c 2 4 1 0 、a t m e l 的a t 9 l r i l l 系列，以及p h i l i p s 的l p c 2 0 0 0 系列。 a r m 微处理器通常有两种工作方式：a r m 状态和t h u m b 状态陋“。在a r m 状态下，处理器执行3 2 位字对齐的a r m 指令；在t h u m b 状态下，处理器执 行1 6 位半字节对齐的t h u m b 指令。在程序的执行过程中，微处理器可以随 时在两种状态之间切换，并且工作状态的转变不影响处理器的当前工作模式 和相应寄存器的内容。在开始执行代码时，处理器处于a r m 状态，状态的切 换由操作数寄存器的状态位取值决定。 a r m 处理器有7 种运行模式，可以通过软件编程、外部中断和异常处理 改变，包括五种中断异常模式协”。 用户模式( u s r ) ：正常程序执行状态 系统模式( s y s ) ：运行具有特权的任务 快速中断模式( 行q ) ：高速数据传输或通道处理 外部中断模式( i r q ) ：通用中断处理 管理模式( s v c ) ：操作系统使用的保护模式 数据访问终止模式( a b t ) ：数据或指令预取终止时进入模式，用于存储保 护 口 定义指令集终止模式( u n d ) ：为定义指令时进入模式，可用于硬件协处理 的软件仿真 a r m 处理器包含3 7 个3 2 位寄存器，其中包括31 个通用寄存器和6 个 状态寄存器，供7 种处理器运行模式使用。 1 5 研究的主要内容 本课题的研究对理论和实践进行了有机结合，在研究嵌入式l i n u x 的实 时性理论得同时，也对其应用开展了实践工作。本文作者在完成学业期间在 导师的指导下主要完成了以下几个方面的研究。 1 5 1 嵌入式lin u x 的实时性研究 这一部分为理论研究内容，通过研究大量相关资料，从概念上确立l i n u x 西南科技大学硕士研究生学位论文第5 页 的实时性和其存在的问题，为后一步的研究工作打好基础。嵌入式l i n u x 的 实时性问题源于标准l i n u x 的内核机制，要弄清l i n u x 实时性不足的原因， 必须搞清l i n u x 内核机制的相关内容，例如内核定时机制、进程调度策略和 系统调用等。为此，课题研究的首要内容就是研究l i n u x 内核特性和运行原 理，总结影响l i n u x 实时性能的原因和解决该问题的入手点。在这一基础上， 再对部分实时化方案进行理论研究，总结出各方案的解决手段和优缺点。 1 5 2 基于a r m 的嵌入式l in u x 系统构建 在测试和应用l i n u x 实时化方案时，需要建立一个较完整的嵌入式l i n u x 平台作为实验基础。所以，研究工作的第二个内容是构建一个可靠的、能够 稳定运行的嵌入式平台。嵌入式平台的构建包括硬件和软件，本文将构建的 重点放在嵌入式l i n u x 软件平台上。一个较完整的l i n u x 平台移植，主要包 括以下工作内容：交叉编译器的选择与建立、u b o o t n ”( u n i v e r s a lb o o t l o a d e r ，引导l i n u x 启动的工具) 的移植、l i n u x 内核源文件的裁剪与移植、 建立根文件系统，最后添加字符设备驱动妇，。本课题在研究过程中，搭建了 能够稳定运行的嵌入式l i n u x 系统作为工作平台，其中硬件平台为 a t 9 1 r m 9 2 0 0 d k ，内核为l i n u x 2 6 2 7 ，文件系统为e x t 2 格式。 1 5 3lin u x 的实时化方案扩展与应用 这一部分研究工作，主要以l i n u x 的高精度时钟子系统h r t ( h i g h r e s o l u t i o nt i m e r ) 门4 1 实时化方案为基础。该实时方案针对l i n u x 内核时钟粒度 粗，定时精度低的问缺陷而设计，其主要原理是使用h r t 替代原有内核时钟， 将周期时钟模式( t i c k ) 变为单次触发模式( o n e s h o t ) b “，从而更有效地利用硬件 计时器。 该部分具体工作如下： ( 1 ) 详细研究h r t 的时钟机制，包括：h r t 初始化方式、触发过程、切 换方式等。 ( 2 ) 在l i n u x 系统上创建h r t 设备供用户层调用，给出具体实现方案、 设备的f i l e 结构心1 和测试报告。 ( 3 ) 将h r t 方案应用于在中电十四所“嵌入式车载诱饵冷却系统 项目 中，工作包括：用户层代码，温度采集和控制驱动，并给出测试结果。 根据以上研究内容，论文将在下一章开始对嵌入式l i n u x 的内核结构、 l i n u x 实时性能缺陷、h r t 实时方案等内容进行详细阐述。 西南科技大学硕士研究生学位论文第6 页 2 嵌入式l in u x 的实时性分析 本章内容从系统内核入手，对l i n u x 基本结构进行分析，研究工作着重 于探讨l i n u x 在实时性方面的缺陷和改良方案。l i n u x 的实时性是一个比较 热门且综合性较强研究方向，提升其实时性的方案很多，限于篇幅，本章将 简要介绍部分改良方案。为解决在实际项目中碰到的问题，本文选择提升 l i n u x 时钟精度作为实时性研究的重点内容。这部分内容，将从l i n u x 系统 时钟触发原理开始阐述，分析标准内核时钟的缺陷，最后详细分析l i n u x 高 精度时钟子系统的原理与结构。本章主要完成理论研究阶段工作，具体的应 用研究将在后面两章叙述。 2 1 嵌入式l in u x 的内核结构 首先介绍l i n u x 的内核结构，见图2 1 ： 图2 1 由下至上简要展示了l i n u x 的系统层次。整个系统设计呈纵向分 层结构，与进程运行相关的各个管理和支撑模块以分层的方式存在于内核空 间”。用户代码位于系统顶端，存在于用户空间；内核由各个管理和支撑模 块组成；设备驱动位于底层，向内核提供硬件信息。在l i n u x 的应用层与设 备驱动层，探讨其实时性的意义并不大，原因如下： ( 1 ) 由于内核的存在，用户的操作通过标准化的调用执行 ，来操作硬件， 而难以涉及到系统调用方法和i o ( i n p u t o u t p u t ，输入输出) 数据的具体处理。 虽然修改应用层代码，在一定程度上能优化管理方式，减少资源开销，但不 能改变一些系统基本特性，如调度策略、内存使用和中断服务等。 ( 2 ) l i n u x 设备驱动的功能为：使某个特定硬件响应一个定义良好的内部 编程接口，这些接口完全隐藏设备的工作细节，并使设备驱动独立于内核的 其他部分而建立，在运行时“插入 内核忙，。设备驱动虽然在系统内核态中 运行，但是与内核的耦合性不强，而且描述硬件工作细节也不能从根本上改 变系统的实时性能。 本节的研究将从系统内核部分开始，重点讨论l i n u x 内核的时钟机制和 进程调度。 2 1 1 内核特点 l i n u x 是类u n i x 操作系统，所以l i n u x 操作系统的架构与u n i x 是一致 西南科技大学硕士研究牛学位论文第7 页 用户层应用程序 一- - - $ - - - - 翟 系系统调用 内 核 ? 进程管理 内存管理文件系统设各控制 l$ll 拿$ i 幻地址映射字符设备架构相关代码网络子系统 $ 、 设备驱动程序 $ 硬件 _ 内核态数据 一 数据 图2 1l i n u x 操作系统结构简图 f i g u r e2 1 t h es t r u o t u r ed i a g r a mo fl i n u xo s 空间 空间 的，可被看作是u n i x 的兼容操作系统”。最突出的特点为：宏内核结构、用 户态内核态模式。 宏内核也称单内核，核心程序都是以核心空间( k e r n e ls p a c e ) 的身份及监 管者模式( s u p e r v i s o rm o d e ) 来运行“。在宏内核中用户态与内核态是严格区分 的，两者不会在同一空间运行，内核代码在用户态是不可见的，它们之间的 数据传递透过特殊的系统函数来实现，用户代码无法直接访问内核程序。我 西南科技大学硕士研究生学位论文第8 页 们通过进程的上下文切换说明这种结构，以s h e l l 进程为例。s h e l l 是提供操 作系统内核与用户之间交互的程序，它是从登录开始运行的使用程序，允许 用户通过s h e l l 脚本或命令行的方式输入命令，并通过翻译这些命令完成用户 与内核的交互n ”。图2 2 表示在s h e l l 中执行名为h e l l o 的用户程序。 i s h e l l 进程 i h e l l o 进程 _ 执行过程露：塞潞内核代码 图2 - 2 进程的上下文切换 f i g u r e2 。2 c o n t e x ts w i t c h 阶段，s h e l l 进程运行，表现为等待命令输入，输入命令“h e l l o 后， s h e l l 启动系统调用，将控制权交给内核。在阶段，执行过程对用户层屏蔽 的，内核代码保存s h e l l 状态，创建h e l l o 进程并交予控制权。阶段，h e l l o 进程执行，输出“h e l l ol i n u x ”字符串后，控制权交还内核。阶段，内核 恢复s h e l l 进程，将控制权传递给s h e l l 进程。阶段继续执行s h e l l 进程，再 次等待命令输入。 现阶段的l i n u x 内核引入了可卸载模块管理机制，l i n u x 各模块的分布 与微内核的横向结构非常相似，不需要的模块可以从内核中剔除，避免无意 义的内存开销。虽然在移植过程中，l i n u x 仍显繁琐，但是它的裁剪和修改 功能明显适应嵌入式应用环境。 2 1 2 内核时钟机制 时钟是操作系统核心之一，有很重要的地位。基本作用如下： 西南科技大学硕士研究生学位论文第9 页 记录系统时间：很多应用程序需要知道日期和时问、由日期和时间构成 的时间戳也会被打在文件上面。 统计功能：如查看一段时间内的系统负载，以及各个进程占用c p u 的时 间等。 定时功能：很多程序会使用到定时器，比如进程定时睡眠、s e l e c t 监听 设置超时时间等伸“。 此外，进程调度器、超时检查等系统任务均依靠时钟来向f ； 驱动。总之， 无论是周期定时或动态定时都要参照当前时钟值来设置到期时间，时钟粒度 越细，定时精度越高，就能提高程序的时间处理精度和灵活性。所以，时钟 精度是衡量操作系统实时性关键指标之一，研究l i n u x 内核时钟机制是有必 要的。 l i n u x 内核时钟本质上完成两类定时工作，供内核与用户使用。 保存当前的时间和日期 维持定时器运行，即告知内核某一时间问隔已经过去( 某定时器到期并 执行该定时器事件) n ， 本节用三个部分阐述l i n u x 的时钟机制。 2 1 2 1tim e k e e pin g 和h z 机制 时钟产生的源头来自于固定频率振荡器和计数器等硬件电路，在操作系 统中无论是外接的时钟源或c p u 自带的计数器都由内核进行管理，不同的操 作系统对其管理方式存在差别。l i n u x 内核中有两个模块负责对硬件时钟源 和计时器进行读写操作，t i m e k e e p i n g 模块通过读取计数器值来更新当前时 间和日期，它是整个l i n u x 系统的时间来源。t i c k ，本意为时钟滴答，该模 块通过设置计时器产生周期性的硬件中断，使用中断旬柄函数完成对定时器 的维持。这两个模块是在内核时钟中处于核心地位，图2 3 详细说明了两个 模块的工作内容。 t i m e k e e p i n g 模块在获得计数寄存器的数值后，会更新两个以纳秒为单 位的关键时间变量s y s t e mt i m e 和r e a lt i m e ，计算方式如下。 。 r e a l _ t i m e 2 x t i m e + c y c 2 n s ( n o w _ r e a d la s t r e a d ) s y s t e m _ t i m e = x t i m e + c y c 2 n s ( n o w _ r e a d - l a s t _ r e a d ) + w a l lt o m o n o t o n i c r e a lt i m e 是从1 9 7 0 年开始到现在的绝对时间值，x t i m e 是指最近一次更 新的r e a lt i m e ，n o wr e a d 是指当前计数器读取值，l a s tr e a d 是指上一个时 钟周期的计数器读取值，c y c 2 n s 函数将时间转换为纳秒。 西南科技大学硕士研究生学位论文第l o 页 l 硬件时钟 软件时钟模块 图2 - 3l i n u x 内核的时钟机制 f i g u r e2 3 l i n u xk e r r e ic i o c km e c h a n i s m s y s t e mt i m e 公式中的w a l lt om o n o t o n i c 值在系统启动时由内核更新， 更新内容为系统启动完成那一刻的x t i m e 值并取负，故s y s t e mt i m e 变量表示 系统最近一次启动到现在的纳秒数。 定时器基于这两个变量设置过期时间，而用户空间通过调用g e t t i m e o f d a y 和s e t t i m e o f d a y 函数将其转换为t i m e v a l 结构，获取当前时间点。熟悉l i n u x 应用开发的人员对t i m e v a l 结构体应该不会陌生，它有两个成员变量t vs c c 和t vu s c c 分别存放秒和微秒时间点。 t i c k 模块完成两个工作，更新j i f f e s 值和t i m e w h e e l 数据结构。t i m e w h e e l 完成对到期定时器的检查和定时器链表的更新。这里先讨论j i f f e s 的作用， j i f f e s 变量是一个计数器，用于记录系统启动以来产生的节拍总数，每当时钟 中断发生时( 每个节拍) 它便加。该值溢出后，清零重新计数。内核周期性 任务需要用它来判定任务是否开始或到期，定时器也不例外。在标准内核中， j i f f e s 是衡量系统定时精度的参考量，它每秒发生次数由内核赫兹设定值 ( k e r n e lh z ) 决定，h z 值为2 0 0 ，则每秒产生2 0 0 个j i f f e s ，此时定时精度为 5 m s 。这种通过j i f f s 计数来驱动定时器的模式称为l i n u x 的h z 机制。 2 1 2 2t i m e w h e e i 结构 西南科技大学硕士研究生学位论文第1 1 页 定时器在系统中被经常使用，用户在使用定时器时，只设置到期时间和 定时器事件，剩下部分交由内核的t i m e w h e e l 来完成。内核会根据上节提到 的h z 值来设定硬件计时器的中断产生周期，在每一个计时器中断来临时， t i e k 模块都会调用t i m e w h e e l 来清理到期的定时器。在过程阐述之前，我们 需要搞清几个数据结构，下段代码摘自内核源码l i n u x k e r n e l t i m e r c 。 行数代码 6 7s t r u c tt v e c 6 8s t r u c tl is t h e a dv e c t v n si z e ； 6 9 ； 71s t r u c tt r e e r o o t 7 2s t r u c tl i s t h e a dv e c t v rs i z e ； 7 3 ) ； 7 5s t r u c tt v e c b a s e 7 6 s p i n l o e k _ tl o c k ； 7 7 s t r u c tt i m e r l i s t r u n n i n g _ t i m e r ； 7 8 u n s i g n e dl o n gt i m e r j i f f i e s ； 7 9 u n s i g n e dl o n gn e x t _ t i m e r ； 8 0s t r u c tt v e c r o o tt vl ； 8 1s t r u c tt r e et v 2 ； 8 2 s t r u c tt v e et v 3 ； 8 3s t r u c tw e e t v 4 ； 8 4s t r u c tt r e et v 5 ； 8 5 c a c h e l i n e _ a l i g n e d ； 其中t v rs i z e 取值为2 5 6 ，t v ns i z e = 6 4 。 6 8 行与7 2 行的l i s th e a d 数组存放双向链表表头，所有定时器都通过表 头加入到链表当中，内核通过该链表中的数据检查到期定时器，并获取事件 句柄。在t i m e r w h e e l 中，所有正在使用的定时器并不是按顺序的存放在一 个平坦的链表中，因为这样会使查找、删除等操作效率低下，。它由一个5 层的链表组t v l - - - t v 5 构成，按照到期时间先后顺序排列。函数r u nt i m e r s 是t i m e w h e e l 的核心管理函数，下面代码摘自内核源码l i n u x k e r n e l t i m e r c 。 行数代码 9 6 7s t a t i ci n l i n ev o i d r u n _ t i m e r s ( s t r u c tt v e c b a s e 宰b a s e ) 9 6 8 西南科技大学硕士研究生学位论文第1 2 页 9 6 9 9 7 1 9 7 2 9 7 3 9 7 4 9 7 5 9 8 0 9 8 1 9 8 2 9 8 3 9 8 4 9 8 5 s t r u e tt i m e r l i s t 宰t i m e r ； s p i n _ l o c k _ i r q ( & b a s e 一 l o c k ) ； 事通过m r s 值检查定时器是否到期幸， w h i l e ( t i m e _ a f t e r _ e q ( j i f f i e s ，b a s e 一 t i m e r j i f f i e s ) ) s t r u c tl i s t h e a dw o r k _ l i s t ； s t r u e tl i s t h e a d 幸h e a d = & w o r k _ l i s t ； i n ti n d e x = b a s e - t i m e r _ _ j i f f i e s & t v r _ m a s k ；获取t v l 索引值， * i f 语句检查t i m e r - w h e e l 的t v 之间是否需要进位事 i f ( ! i n d e x & & ( ! c a s c a d e ( b a s e ，& b a s e 一 t v 2 ，i n d e x ( 0 ) ) ) & & ( ! c a s c a d e ( b a s e ，& b a s e 一 t v 3 ，i n d e x ( i ) ) ) & & ! c a s c a d e ( b a s e ，& b a s e - t v 4 ，i n d e x ( 2 ) ) ) c a s c a d e ( b a s e ，& b a s e - t v 5 ，i n d e x ( s ) ) ； * t v l 索引右移到下个j i f f e s 到期定时器 + + b a s e 一 t i m e rj i f f i e s ； 9 8 6 l i s t _ r e p l a e e _ i n i t ( b a s e - t v1 v e c + i n d e x ，& w o r k _ l i s t ) ； 幸进入t v l 的到期定时器链表表头，处理所有到期定时事件 9 8 7 w h i l e ( ! l i s t _ e m p t y ( h e a d ) ) 9 91 t i m e r = l i s t f i r s t e n t r y ( h e a d ，s t r u c tt i m e r l i s t ，e n t r y ) ； 9 9 2 f n = t i m e r - f u n c t i o n ；执行定时器事件函数 9 9 3 d a t a = t i m e r - d a t a ； 1 0 4 1 10 4 2 10 4 3 s e t _ r u n n i n g _ t i m e r ( b a s e ，n u l l ) ； 10 4 4 s p i n _ u n l o c k _ i r q ( & b a s e - l o c k ) ； 10 4 5 ) 代码9 7 2 行w h i l e 语句的条件函数t i m e r _ a f t e r e q 。它检查参数j i f f e s 来 判定定时器是否到期，t v l 的数组变量以设定的到期j i f f e s 为排列顺序。为更 好的说明其t i m e w h e e l 的检查过程，我们假设h z 值为1 0 0 0 ，即j i f f e s 每l m s 增加1 次。t i m e r a f t e r e q 函数中的t i m e r j i f f e s 参数记录当前到期定时器的 j i f f e s 值。每当t i m e w h e e l 处理一次，t i m e r _ j i f f e s 就自加l ，使t v l 的索引值 i n d e x 向前移动，当i n d e x 重置o 时表示t v l 完成一次遍历，也就是经过2 5 6 m s ， 此时再取出t v 2 中链表放到t v l 中，t v l 重新开始遍历过程，t v 2 到t v 5 的关系 西南科技大学硕士研究生学位论文第1 3 页 也是如此。t v 数组之间存在着类似时分秒的进位关系3 “。该方式优点在于： 检查t i m e w h e e l 中的超时定时器只需查看t v l 数组的2 5 6 个表头元素，不用 遍历全部定时器链表，提高查找效率。 代码9 8 1 行的c a s c a d e 函数完成进位工作。假设t i m e rj i f f e s 为0 ，到期 时间不超过2 5 5 m s 的定时器存放到t v l 链表组，t v 2 链表组存放到期时间为 2 5 6 m s 至i ( 2 5 6 6 4 1 ) m s 的定时器。依次类推t v 3 、t v 4 和t v 5 。简单来说t v l 每 l m s 就被访问一次，t v 2 每2 5 6 m s 访问一次，t v 3 需要16 s ，t v 4 需要1 7 分钟， t v 5 需要大概1 8 小时。t i m e w h e e l 最大容纳超时节拍为2 5 6 串6 4 宰6 4 誊6 4 木6 4 ， 即2 3 2 个j i f f e s 。 2 1 2 3 到期定时器的处理 每当硬件计时器中断产生后，t i c k 模块都会访问一次t i m e w h e e l 结构。 前面说明了定时器的过期检查和存放方式，下面分析内核对过期定时器的处 理措施。 首先所有定时器( 包括：到期时间、定时事件) 都存放在t i m e rl i s t 链表中， 由于到期的定时器可能不止一个，内核将t i m e rl i s t 的表头按过期j i f f e s 的先 后顺序存入t i m e w h e e l 的t v 数组中。当某个表头被判过期后，内核会获取该 表头，遍历链表的全部非空节点，依次执行定时器事件。我们以t v 数组来说 明这种数据结构，见图2 4 。 在r a i lt i m e r s 函数中，l i s te m p t y ( h e a d ) 首先检查到期链表表头，若链表 非空则返回0 值。w h i l e 循环语句将该链表中非空节点依次提取出来： 在代码的9 9 2 和9 9 3 行，f n 是节点上定时器的事件函数指针，d a t a 为事 件参数。由f n ( d a t a ) 语句执行定时器事件，这样便完成某个定时器的工作， 最后跳回l i s te m p t y ( h e a d ) 继续检查剩余链表节点，直到链表中所有到期定时 器执行完成；另外，若定时器事件为周期任务。在完成任务后，内核会判定 f n ( d a t a ) 的返回值，把该定时器的到期时间换算为j i f f s 值，重新插入到 t i m e w h e e l 的对应位置。 2 1 3 进程调度 l i n u x 的调度基于分时( t i m es h a r i n g ) 技术：多个进程以“时间多路复用 方式运行，因为c p u 的时间被分为“片( s l i c e ) ，给每个可运行的进程分配一 片。进程调度负责选择某个进程来运行以及进程何时切换，合理的为进程 分配c p u 。调度器在所有处于可运行状态进程中选择最合适的进程来运行。 西南科技大学硕士研究生学位论文第1 4 页 t v 2 t v l 2 5 6 m s 进位一次 口 链表节点 _链表表头口t v 数组_ 到期链表 图2 - 4 ti m e r - w h e el 数据结构 fig u r e2 。4tim e r 。w h e eid a t as t r u c t u r e 在l i n u x 中，选择依据位于每个进程t a s ks t r u c t 结构体，选项如下： p o l i c y ：进程的调度策略，用来区分实时进程和普通进程。原则上，实时 进程的调度优先于普通进程。 p r i o r i t y ：普通进程的静态优先级。 c o u n t e r ：该值在计算g o o d n e s s ( 变量指某可运行进程的可信度) 时起重要作 用，可作为进程的动态优先级。 r t 实时进程的静态优先级，有效范围在1到99之间，用于实时_prioriyt： 进程问的选择，该值在普通进程中为0 。 进程调度器的代码位于l i n u x k e r n e l s c h e d c 中，负责执行调度的函数是 s c h e d u l o 。它的任务是从运行队列链表中找到一个进程，随后把c p u 资源分 配给这个进程。调度算法的核心是在运行队列链表的所有进程中确定最佳 候选者。函数g o o d n e s s ( ) 来衡量某可运行状态的进程的可信度。除上面四项 外，函数还考虑了其他因素，赋予每个可运行进程一个权值( w e i g h t ) ，若权值 大于或等于1 0 0 0 ，则该进程就是一个实时进程。调度程序以这个权值作为选 择进程的唯一依据n ”。 l i n u x 中对实时进程和普通进程的调度是不同的，实时进程应该先于普 通进程而运行1 。l i n u x 通过t a s k s t r u c t 中的p o l i c y 区分实时和普通进程，进 程调度有三种p o l i c y ： 西南科技大学硕士研究生学位论文第1 5 页 、 ( 1 ) s c h e do t h e r ：普通的用户进程，进程的缺省类型，采用动态优先 调度策略，选择进程的依据主要是根据进程g o o d n e s s 值的大小。