（计算机系统结构专业论文）多核嵌入式系统的实时性研究.pdf

浙江大学硕上学位论文摘要 摘要 目前多核处理器已成为服务器和桌面的主流，不久将广泛地运用在高端嵌入 式领域。以往嵌入式系统的实时性研究主要集中于任务调度和切换、实时任务的 通信和容错性等，未涉及到实时任务本身的改造。而当前多核的优化更关注于系 统的吞吐量，而非针对某一实时任务的优化。 本文在分析了多核处理器的特性和国内外相关的工作后，以实时任务在多核 体系结构上的改造为手段，研究嵌入式系统的实时性问题。目前多核处理器以多 个核为一组共享二级缓存，本文还通过挖掘二级缓存的高命中率来进一步地提升 实时任务的性能 本文提出的多核嵌入式系统实时性改造方案，主要分为任务并行和操作系统 支持两部分。任务并行主要利用多核的资源进行基于功能和数据的划分，通过比 较划分前后在多核上运行的性能，总结出合理的划分方法以提高实时任务的性 能。改造方案还包括在操作系统中设计了基于二级缓存共享的线程分配算法，提 供划分后任务的运行支持。 实验证明，在本文的设计下实时任务的性能可以获得很大的提高。本文以 s i m i c s 模拟器为测试环境，使用基于功能的划分将一个播放器的核心代码划分为 三个线程，性能提升了1 0 2 6 。使用了基于数据的划分将快速排序程序拆分为两 个线程，性能提升了8 7 ；将归并排序拆分为两个线程，性能提升了9 2 。在本 文的测试案例中，基于二级缓存共享的线程分配算法可将实时任务的性能提升 6 2 5 。 通过本文的改造方案，可以大大提升系统实时任务的性能，从而降低系统的 激励响应周期。 关键词多核，实时性，多线程，二级缓存 浙江大学硕上学位论文 a b s t r a c t m u l t i - c o r ep r o c e s s o rc u r r e n t l yp o p u l a ri nt h e $ e l v f f fa n dd e s k t o pa p p l i c a t i o n s ， 1 i ns o o nb ew i d e l yu s e di nh i g h - e n d 锄b c d d e df i e l d t 1 l ep r e v i o u sr e a l - t i m e e m b e d d e ds y s t e m sr e s e a r c hf o c u s e do ns w i t c h i n ga n dt a s ks c h e d u l i n g , r e a l - t i m e c o m m u n i c a t i o n sa n df a u l t t o l e r a n c e , n o tr e l a t et or e a l - t i m et a s ki t s e l f a n d m u l t i - p r o c e s s o rm o r 口c o n c e r n e da b o u tt h eo p t i m i z a t i o no ft h r o u g h p u ti nt h es y s t e m , r a t h e rt h a nar e a l - t i m eo p t i m i z a t i o n b a s e do nt h ea n a l y s i so f m u l t i - p r o c e s s o rc h a r a c t e r i s t i c sa n dr e l a t e dw o r ka th o m e a n da b r o a d , t h i st h e s i sr e s e a r c h e dt h er e s l - t i m ep r o b l e mb yr e b u i l d i n gt h er e a l t i m e t a s k s n o wm u l t i - p r o c e s s o r sc a l ls h a r et h e2 - l e v e lc a c h ea n dt h i sp r o p e r t yi su t i l i z e dt o f u r t h e ri m p r o v et h ep e r f o r m a n c eo f t h er e a l - t i m et a s k s t l l i st h e s i sp r e s e n t st h er e a l - t i m ei m p r o v e m e n ts c h e m eo nm u l t i - p r o c e s s o r e m b e d d e ds y s t e m , w h i c hi sc o m p o s e db yt a s kp a r a l l e l i s ma n do p e r a t i n gs y s t e m s u p p o r t t a s kp a r a l l e l i s mp r o d u c e sm u l t i - t h r e a db ym e 锄o f f u n c t i o n a ld e c o m p o s i t i o n a n dd a t ac o m p o s i t i o n b yc o m p a r i n gt h ep e r f o r m a n c e sb e f o r ea n da f t e rp a r a l l e l i s m , t h i st h e s i sc o n c l u d e st h er e a s o n a b l ed e c o m p o s i t i o nt oi m p r o v et h er e a l t i m ep r o p e r t y o ft h et a s k i m p r o v e m e n ts c h e m ea l s oi n c l u d e s2 - l e v e lc a c h eb a s e dt h r e a da l l o c a t i o n a l g o r i t h m , w h i c hs u p p o r t st h er e a l t i m et a s ka tr u nt i m e e x p e r i m e n t sh a v ep r o v e dt h a tt h er e a l - t i m et a s k s 黜h i g h l yi m p r o v e db yt h e t h e s i s sd e s i g n t h et e s t i n ge n v i r o n m e n ti ss i m i c as i m u l a t o r t h ek e r n e lo fam e d i a p l a y e ri sd i v i d e di n t ot h r e et h r e a d sb yf u n c t i o n a ld e c o m p o s i t i o na n dg e t s1 0 2 6 s p e e d u p q u i c ks o r ta n dm e r g es o r ta r ed i v i d e di n t ot w ot h r e a d sb yd a t ad e c o m p o s i t i o n a n dg e t8 7 a n d9 2 s p e e d u pr e s p e c t i v e l y i nt h i st h e s i s st e s tc a s e , 2 - l e v e lc a c h e b a s e dt h r e a da l l o c a t i o nc a ne n h a n c et h ep e r f o r m a n c eo f 6 2 5 t h r o u g ht h es c h e m ei nt h i st h e s i s , t h er e a l - t i m et a s k sp e r f o r m a n c ei sh i g h l y i m p r o v e d , t h e r e b yr e d u c i n gt h er e s p o n d i n gp e r i o d k e y w o r d sm u l t i c o r e , r e a l - t i m e , m u l t i t h r e a d i n g , 2 - l e v e lc a c h e 浙江大学硕上学位论文图目录 图目录 图2 1 嵌入式系统结构。4 图3 1 多核实时任务并行设计1 4 图3 2 二级缓存利用设计1 5 图3 - 3 每二核共享二级缓存示意图1 6 图3 - 4 四核共享二级缓存示意图1 6 图3 - 5 线程分配设计1 9 图3 - 6 任务分解后的运行时间图2 0 图4 - l 程序功能分解示意图2 2 图4 - 2 视频播放器改造后构造示意图2 3 图4 3 视频播放器线程示意图2 4 图4 - 4 程序数据分解示意2 5 图4 5 快速排序示意图2 6 图4 6 快速排序二线程视图2 6 图4 - 7 归并排序示意图2 7 图4 8 归并排序二线程视图2 8 图4 _ 9 程序分解图2 8 图4 - 1 0 共享关系图。2 9 图4 _ l l 线程分配例子3 l 图5 1s i m i c s 中每二核共享二级缓存图3 4 图5 2s i m i c s 中四核共享二级缓存图3 4 图5 3 不同数据量情况下快速排序的二级缓存读命中率4 l 图5 - 4 不同数据量情况下归并排序的二级缓存读命中率4 4 i 1 1 浙江大学硕士学位论文 表目录 表目录 表5 1 每二个核共享一个二级缓存的配置表 表5 2 四个核共享一个二级缓存的配置表3 3 表5 3 播放器一单线程3 6 表5 - 4 播放器一图3 3 多核体系结构下的多线程3 7 表5 5 播放器图3 - 4 多核体系结构下的多线程3 7 表5 - 6 播放器数据摘要3 8 表5 7 快速排序一单线程3 9 表5 8 快速排序共享二级缓存的多线程3 9 表5 - 9 快速排亭一不共享二级缓存的多线程 表5 1 0 快速排序数据摘要。4 0 表5 - 1 l 归并捧亭一单线程4 2 表5 1 2 归并排序共享二级缓存的多线程。4 2 表5 1 3 归并排序不共享二级缓存的多线程4 3 表5 1 4 归并排序数据摘要4 3 表5 1 5 使用分配算法下的数据摘要 表5 1 6 不使用分配算法下的数据摘要4 5 浙江大学硕上学位论文第1 章绪论 第1 章绪论 1 1 课题背景 随着计算机软件和集成电路技术的发展，嵌入式系统产品日益完善，在航天、 航空、交通、网络、电子、通讯、金融、智能电器、智能建筑、仪器仪表、工业 自动控制、数控机床、掌上型电脑、各种智能i c 卡、第二代身份证验证、公共 交通收费系统、医药系统以及军事等领域得到广泛应用，已成为我国用“信息化 带动工业化，工业化促进信息化”发展的国民经济新的增长点【1 】。国家对嵌入式 的发展也十分关注，并在十五阶段立有多个嵌入式相关的8 6 3 项目，如3 g 移动 嵌入式平台，面向智能手机的嵌入式软件研发，面向区域的嵌入式软件等。 嵌入式系统的核心问题是系统的实时性，这也是嵌入式系统和其它系统的根 本区别所在。实时系统被要求在一个给定的时间内完成工作，如果无法按时完成， 会带来巨大的损失。国内外关于嵌入式系统的实时研究已经进行了几十年，虽然 为此提出了各种方法，但仍缺少核心的解决方案。目前关于实时性的研究仍然是 嵌入式系统研究的核心问题。 而与此同时，随着集成电路技术的发展，处理器的性能提升已不能指望主频 的提高，要想使微处理器性能继续按摩尔定律推进，使处理器能够符合计算发展 的需求，必须研究新的微架构和新的计算模型，因此单芯片多处理器( c h i p m u l t i - p r o c e s s o r s ，简称c m p ) 架构，也就是通常所说的多核，成为现在学术界和 工业界关注的热点，并已成为服务器和桌面领域的主流 从多核的快速发展中可以预见，多核即将被广泛应用到一个更广阔的市场 嵌入式系统。据统计嵌入式芯片占整个芯片市场的8 0 - 9 0 e 1 ，而多核时代 的到来将使得这个领域焕发出新的研究热潮。由于底层体系结构的改变，许多嵌 入式研究方向需要进行修正，包括实时性、可靠性、节能等等。虽然这方面的工 作才公共起步，但必将在未来的几年中成为嵌入式研究的主流。 本文正是在这样的历史背景下，对多核技术如何改善嵌入式系统的实时性进 行了调研，并对其中的关键问题进行了分析和研究。 浙江大学硕l 学位论文 第1 章绪论 1 2 研究意义 每种新的硬件体系结构的提出，必然要与相适应的软件配合，才能发挥它的 最大性能。目前的硬件已经完成了从单核到多核的跨越，但多核的软件设计的研 究还是处于百家争鸣的状态，虽然有了一定的研究成果，但新的方法、新的研究 数据仍然曾出不穷。特别是在嵌入式多核领域，针对性的研究还是太少。而嵌入 式芯片的产量和应用又是远远大于桌面系统和服务器系统，并且高端的嵌入式系 统也早已崭露头角，并将继续占领一个重要的地位。多核嵌入式作为其中的一个 主要代表已渐渐成为嵌入式领域和多核领域的研究热点。 嵌入式的软件优化涉及到方方面面，包括实时性、可靠性、安全性、节能、 系统吞吐量等等但是实时性一直占据着其中最重要的位置。可以说实时性是航 天、军事、工业控制等领域的命脉 实时性的本质问题是在一个给定的时间t 内，系统必须完成所要完成的任务， 如果完成的时间为t ，f 多进程的时间相关性研究； 任务的分配与调度； 缓存的错误共享； 一致性访问研究： 进程间通信； 多处理器内部资源竞争等等。 这些研究点虽互为独立，但又互为覆盖。考虑一个系统的性能时必须将其中 的几点同时加以考虑，有时候对一些点的优化会造成另一些点的性能下降，需要 用程序进行性能优化评测，折中得出一个相对理想的结果以下单独对这几点进 行论述。 程序的并行研究是多核研究的重点，几乎所有的相关研究都脱离不了这方面 的考虑。多核系统之所以不同于单核系统，就是因为多核具备了同时执行多个进 程的能力，而发挥这个能力需要软件的配合，软件的并行研究就是基于这个背景 而产生的一个软件的可并行部分是相当高的，如果并行合理就能真正发挥多核 的优势。目前并行研究还没有一个普适性的方法，针对不同方面进行并行研究的 方法层出不穷，各有优缺点 时间相关性研究在单核情况下是指一块内存在一定的时间内被一个进程或 多个进程不断访问，在多核的构架下衍生到了不同的核在一定的时间内不断访问 一块内存。由于现在c m p 的多核构架中，多个核可以共享二级缓存，如何发挥 这个二级缓存的作用来提升时间相关性是研究的方向。这个研究方向还涉及到线 程的分配。 进程或线程的分配是多核时代提出的新概念。在单核时代，无所谓分配的问 题，一共只有一个核的资源可被使用。而在多核体系下，有多个核资源可以被使 用。如果系统中有几个进程需要分配，是将他们均匀地分配到各个核，还是一起 分配到一个核，或是按照一定的算法进行分配，这很值得研究并且这个分配还 受底层系统结构的影响，系统是s m p 构架还是c m p 构架，在c m p 构架中多少 l o 浙江大学硕t 学位论文第2 章嵌入式系统和多核体系结构综述 核会共享二级缓存，这些都是影响分配算法的因子随着任务分配的完成，接下 来的工作就是任务调度一个进程上一个时间运行在一个核上，下一个个时间片 是否还会运行在这个核上，抑或是进行线程迁移? 实时任务和普通任务直接如何 调度? 系统的处理器资源是否要进行负载均衡? 任务调度可以做的事很多，也是 目前研究的热点之一。 缓存存储数据是按一行来提取的，而不是按一个整型或长整型存取的。一行 一般包括数个整型，所以会存在缓存的错误共享。举一个简单的例子，缓存的一 行有4 个整型长度，一个物理核对其中第一个整型进行了写操作，这一行就被标 记为脏。这时候另一个不与上一行共享缓存的物理核读取了这一行第四个整型， 因为这一行已经被标记为脏，所以必须将上一行的缓存刷出，在从内存里读入这 个核的缓存。事实上，这个操作是不必要的。如何避免这种缓存的错误共享是比 较重要的，毕竟一次读操作涉及到了太多的缓存一致性操作。 在多核体系结构下，一致性访问也产生了变化。单核下的信号量和临界区等 粗粒度锁可能已跟不上多核时代，现在针对多核共同访问变量可以加自旋锁，更 新的研究是关于事务内存的设计。在多核体系结构下如何平衡这几种同步机制的 使用将很大程度上影响系统的吞吐量。 进程间通信在多核时代也变得与单核时期不一样了。在单核时期，进程通信 实质上是在内存中完成的，由于只有一个核，缓存很好地完成了加速的作用。在 多核时代，怎样更好地利用各种缓存就必须被提上议案各种策略的效率相差很 大，操作系统必须在这里做一定的优化。而且现在i n t e l 的新产品已经允许多个核 之间的寄存器直接访问，虽然接口没有公布，但这一功能将直接导致各种优化方 法的提出，毕竟寄存器的直接操作是最快的。 多处理器内部资源竞争在c m p 中表现为二级缓存的竞争，在s m t 中表现为 运算资源的竞争。在s m p s o c 中更会涉及到片上的总线和外设控制器的竞争。 避免竞争，使各个核以最大的性能运行是软件设计师的目标。 2 6 本文的出发点 本章在2 1 节和2 2 节综述了嵌入式系统和它的实时性研究，但过去的实时 性研究基本都集中在任务的调度和切换、实时任务的通信，容错性等方面。因为 在单核体系下实时任务本身的性能是难以进行大幅改进的，而实时任务本身的运 行时间却又是占据所有时间的绝大多数，这使得花了很大的代价也只能提升有限 的实时性能。但是多核的出现打破了这一局面，可以从根本方面改变系统的实时 浙江大学硕士学位论文 第2 章嵌入式系统和多核体系结构综述 性 2 3 节到2 5 节综述了多核发展和软硬件领域国内外目前所从事的一些工作， 这些工作大都集中在如何利用多核体系的特性更好地提升系统的性能和吞吐率。 它们只考虑了普遍情况下的优化或某一具体算法的优化，而忽视了多核这一新的 体系结构在嵌入式实时性领域可以起到的作用，而本文作者认为相对于其他领 域，多核的特性可以在嵌入式实时性方面发挥更大的作用。 在另一个研究方向多核的缓存利用，有些研究者也注意到了缓存在多核 优化中的作用，但一般提到的方法是让一个进程一直调度到一个核或多个共享数 据的进程调度到一个核，以此来提升缓存的命中率。他们忽视了在当静c m p 体 系结构中二级缓存的特殊情况。当l j f 的多核体系中，处理器并不独享一个二级缓 存，而是多个核为一组共享二级缓存。这就给软件优化带来了新任务，需要利用 好这个共享关系来最大实时任务的性能 本文从多核实时任务的角度出发，从它所能看的两大系统资源多个核的 运算能力和共享二级缓存一为基本点，研究如何利用这些资源来提升实时任务 的性能，从而提升系统的实时性。同时也将讨论操作系统的改造，支持实时任务 的运行。 2 7 本章小结 本章首先介绍了嵌入式系统，包括它的发展、结构、软件特点等方面。随后 具体综述了实时性的研究现状，并且提出了过去研究的不足。接着又陈述了多核 体系结构的发展，不同体系结构的优劣以及多核体系结构对操作系统和软件提出 的新的要求。然后本文又橛述了多核软件研究主要关注的几个方面。国内外最新 的研究成果等最后提出了本文的出发点，即利用多核对实时任务进行改造，从 而提升嵌入式系统的实时性。下章将给出多核系统实时性的设计 浙江大学硕上学位论文第3 章多核嵌入式系统的实时设计 第3 章多核嵌入式系统的实时设计 3 1 实时性设计概述 多核系统与单核系统的最大不同之处在于计算资源的扩大。在单核系统之 上，实时任务只能看到一个可用的计算资源，它只能在这个有限的资源之上进行 局部性能优化而在多核系统之上，实时任务可以拥有广大的计算资源，它能够 利用这个资源来最优化它的性能。多核给系统带来的不仅是吞吐量的增大，而且 可以给实时任务带来巨大优化。将实时任务多线程化必定是将来的趋势，任务的 多线程化技术是本文的一个重点。 除了计算资源的扩大外，c m p 体系结构的多核处理器拥有了更特殊的二级缓 存。多个核被划分为一组共同拥有一个二级缓存，而非单核或s m p 体系中一个 核独占一个二级缓存。由于二级缓存的速度远远大于普通内存的速度，可以利用 这个二级缓存来提高实时任务各线程之间的共享访问速度同时也要消除多个线 程访问同一个二级缓存的冲突。 由此，多核嵌入式系统改造问题可以归纳如下：在已知实时任务的情况下， 如何充分利用多核的运算资源和二级缓存，来提升实时任务的性能，同时通过操 作系统对上层实时任务进行运行支持 3 2 多核实时任务改造设计 3 2 1 多核运算资源利用设计 何将实时任务并行运行在多核上，发挥多核的作用，将是实时性的一个重大突破 2 碾1 m 浙江大学硕士学位论文第3 章多核嵌入式系统的实时设计 s p e e d u p ，缩短激励响应周期t 。 首先讨论程序的可并行性，即p 的部分。一般有三种方法对之进行挖掘： 自动化工具： 软硬件配合的投机性并行； 纯粹的软件优化并行。 自动化工具是指通过编译工具和运行分析来自动优化并行，这方面的研究目 前停滞不前，没有广泛的应用，相关研究可参看 2 1 】【2 2 】。软硬件配合的投机性并 行是找出那些难以分析但又是潜在可并行的部分，并行的策略是软件完成，但需 要特定的硬件支持。目前这个方向是并行研究的最前沿，但国内缺少可实验的硬 件平台，文献可以参看【2 3 】【2 4 】【4 l 】。纯粹的软件优化并行是利用硬件提供的接口， 手动地完成多核的程序调优，程序的设计者在设计程序时必须意识到底层硬件的 配置和操作系统的影响，这个是现在的主流研究方向本文挖掘可并行性的方法 是第三点，即纯粹的软件优化并行 当发现了程序的可并行性后，需要利用这种可并行性来提升系统的性能，即 上述公式中的s 部分。由于多核具备了同时计算的能力，最直观的方法就是将这 些可并行部分线程化，然后分配到不同的核上同时运行。图3 - 1 展示了多核下实 时任务的改造出发点。 单核单线 程 ( 多核单线 程 、i 3 s 、 - s 多核多线 程 图3 - i 多核实时任务并行设计 在单核体系结构中，由于只有一个运算资源，一个实时任务往往由一个线程 组成。多核处理器的出现大大增加了系统的运算资源，但如果不对实时任务进行 改造，系统和任务的关系如同图3 1 中的“多核单线”实时任务并没有因计算资 源的增多而获得更好的性能，多核只是带来了更大的系统吞吐量，而非系统实时 性的提升。所以必须对实时任务的可并行部分进行合理的拆分，使之由单线程变 1 4 浙江大学硕士学位论文 第3 章多核嵌入式系统的实时设计 为多线程，再分配至各个运算单元进行计算，由此将大大提高系统实时任务的性 能。如图3 1 的。多核多线程”所示，一个实时任务由一个主线程开始，在适当 的地方分解为多个线程，当有些线程完成运算时再将部分线程进行合并，直至最 后运行结束。 3 2 2 二级缓存资源利用设计 通过2 5 节多核的软件研究方向，作者发现还可以有多种方法来实现并 行部分的性能提升，包括缓存的时间空间性研究，线程间的协调及同步等等。如 果能够全部考虑及实现，是能够将系统的性能达到最大值。但也要考虑到实现的 复杂性和代价，并不是优化得越深入越好长久以来，内存的访问速度远远慢于 处理器的速度，系统的瓶颈往往在于内存的访f 司e 4 2 。如果利用片上内存或是缓 存，将显著提升系统性能。而其他各个方面的作用不如内存访问这么重要，所以 为了研究的清晰性，放弃对其他方面的考虑。本文对二级缓存的利用方法见图3 2 ； 个 线程到棱 i 的映射、 夕 l 共享二级共享二级 i 缓存的多缓存的多 个核个核 图3 - 2 二级缓存利用设计 在图3 2 的左边，处理器和多个线程之间的关系完全是浑沌的。任何一个线 程都有可能被分配到任何位置的一个核。当意识到二级缓存的共享配置后，就必 须分别对处理器和线程进行归类划分。以共享二级缓存的多个核为一多核组，共 享数据的线程为一个线程类，每一个线程类对应一个多核组，这样二级缓存的共 享特性就被充分利用起来了，同时也排除了二级缓存访问冲突。 在嵌入式系统中，硬件能根据上层实时任务的需求进行定制，所以可以根据 实时任务的特性，定制出相适应的硬件。在本文的研究范畴内，硬件的配置包括 1 5 入8雨业臀，驻 彳q 8 、 一 浙江大学硕士学位论文第3 章多核嵌入式系统的实时设计 核的数量和二级缓存的配置。核的数量的增加将会大大提高系统成本，而改变二 级缓存的配置却是简单和低廉的。如图3 3 和图3 _ 4 就是两种四核处理器的配置： 图3 - 3 每二核共享二级缓存示意图 罾目圉目 m 目唧 图3 - 4 四核共享二级缓存示意图 在图3 - 3 中，每两个核为一组共享二级缓存；图3 - 4 中，每四个核为一组共 享二级缓存。在设计实时任务的时候应该对底层硬件进行挑选，选择最能发挥实 时任务性能的硬件配置。 3 3 多核实时操作系统改造设计 3 3 1 支持实时任务的多核操作系统分析 一个嵌入式系统上不仅仅运行着一个实时任务，往往还存在着许多非实时的 任务，这时就需要一个嵌入式操作系统来管理系统的资源。也就是说，实时任务 不是直接操作硬件，而是通过操作系统才能获得运行所需要的资源。如果操作系 统设计得不合理，再好的软件设计都无法达到预期的实时性。 1 6 浙江大学硕士学位论文 第3 章多核嵌入式系统的实时设计 操作系统对运行在它之上的任务的影响主要集中在三个方面： 线程的分配 线程的调度； 线程的切换。 只有操作系统在这三个方面作了足够的改进，才能保障运行在其之上的实时 任务的实时性。 l 、线程分配 在过去的单核体系结构上，根本没有线程分配的问题。所有的线程都被维护 在一个队列里，当它获得了执行权时就被分配到唯一的一个核上运行在s m p 体系结构中，由于各个核都是完全对等的，能够做的优化就是将共享数据的线程 尽量分配到同一个核，使这个核的缓存命中率达到最优。而在当前的c m p 体系 机构中，一部分核是共享二级缓存的。那就产生了新的问题，如何将共享数据的 线程分配到这些共享二级缓存的核上，而将有数据冲突的线程分配到不共享二级 缓存的核上。合理的分配最终会影响到3 2 节公式( 1 ) 中s 因子，线程分配的设计 将在3 3 2 小结进行展开，并提出本文的基于二级缓存的分配算法。 2 、线程调度 日前已有多个关于多核进程调度的研究 4 3 1 1 4 4 ，但本文研究的是多核实时 性，关于它的调度不同于一般多核调度。实时任务在系统中的优先级是最高的， 它将无条件地先于普通任务被调度执行。当一个实时任务被拆分为多个线程时， 它的实时性被继承，即那些线程也是实时的。一个系统中往往只有一个实时任务 存在，而这个系统的硬件会被设计成适应这些实时任务的结构。所以在嵌入式系 统中一般不存在多个实时任务争夺系统资源的情况。而这些并行的实时线程必将 大大抢占系统的运行资源，会给系统上的其他任务带来影响。但实时任务的特殊 性赋予了实时改造这样的权利在一个嵌入式系统上，实时任务的按时完成比其 他所有的事情都重要，这也是评价一个实时嵌入式系统的最重要的指标。所以当 实时线程正在运行时，操作系统的调度程序基本可以不处理普通任务 3 、线程切换 线程切换的速度也会影响到系统的实时性。不确定的切换时间将会导致不可 靠的实时性，即在绝大多数的情况下系统可以达到实时要求，但在一些偶然事件 中，由于无法及时地切换到实时进程从而违背了系统的实时性。 对操作系统这部分的优化由来已久，方法主要集中在两个方面： 切换指令的最短化； 1 7 浙江大学硕士学位论文第3 章多核嵌入式系统的实时设计 指令和数据存储在高速设备 第一条既是用最少的指令来完成线程间的切换工作，可以不做的工作尽量推 迟到以后适当的时间来完成第二条即保证这部分的代码和数据可以被高速访 问简单的来说就是不能被刷出内存，最好能够锁住这部分代码的缓存，使之永 远能够缓存访问命中，现在的s e r a t c h p a d 部件可以很好地完成这个工作。 s e r a t e h p a d 是一个类似于缓存的静态高速存储设备，缓存是通过硬件机制来自动 完成数据的读入和刷出，而s e r a t c h p a d 是由操作系统自己控制数据的进出，可以 将一些更有价值更常用的代码和数据放入其中，以此来提升运行效率，可以参考 文献【4 5 】。在有些系统中，这部分切换指令直接被做成了硬件，只提供接口被操 作系统调用，这种方法已经将优化做到极致，较难做出进一步的改进。 通过上述讨论发现，多核操作系统对实时任务的支持主要在线程分配方面。 调度由于实时任务的特殊性，只需强制优先调用即可；而切换问题在单核和多核 下不存在本质区别。故本文就线程分配问题进行详细讨论，并设计出基于二级缓 存的线程分配算法。 3 3 2 线程分配设计 在3 2 2 节中已经设计了二级缓存的使用方式，但底层的硬件资源的配置总 是不断改变的。让实时任务的开发者始终了解底层硬件的状况，并随着硬件的改 变去改变实时任务的设计是低效且不现实的，必须通过操作系统的封装使得系统 可以自动利用二级缓存来提升实时任务的性能。 操作系统在启动的时候会收集到关于底层处理的所有信息，它会根据二级缓 存的配置将处理器进行分组。当实时任务的开发者将任务分解后的线程共享关系 传入操作系统，操作系统就会根据这个共享关系和处理器的配置进行线程的类别 划分。将共享数据量大的线程划分为一类，将会产生二级缓存访问冲突的线程划 分至不同类，最后将线程类映射至多核组，目的是最大化二级缓存的访问命中。 线程分配设计示意图如图3 5 所示： 在图3 5 中，实时任务在划分为多个子线程后，将这些线程的共享关系传递 给操作系统，操作系统根据底层多核的配置情况，计算出将线程分配给各个核的 策略。 浙江大学硕士学位论文第3 章多核嵌入式系统的实时设计 多核操作系统 挎共享数据的皱稃致配至共享缓 ，侮的核上 一、 ( ( ) ( ) 程、- | 共享二级缓存共享二级缓存 的多个核的多个核 图3 5 线程分配设计 3 4 系统改造后运行目标 实时任务经过改造后，将由原来的单线程程序转为多线程的程序由于多线 程将任务的各个部分并行运行，而每一部分的执行时间小于单线程执行时间。并 且在多线程的过程中，利用好二级缓存，可以进一步缩短运行所需的时问。预计 系统改造前后的运行时间如图3 - 6 所示 图3 - 6 ( a ) 代表实时任务单线程情况下的性能，图3 - 6 c o 玳表将原有的实时任务 根据并行改造后的各线程性能，图3 - 6 ( 曲代表使用二级缓存利用共享访问后性能 的进一步提升 在不对实时任务改造之前，实时任务将只有一个线程，它无法利用多核体系 结构所带来的计算资源。当通过实时任务并行，可以将之分解为多个线程运行在 多个核上，每个线程的运行时间都将小于原单一线程然后在分解的过程中计算 出线程的共享关系，并交由操作系统处理优化，利用二级缓存的共享性可以进一 步提升实时任务的性能 1 9 浙江大学硕 学位论文 第3 章多核嵌入式系统的实时设计 ( a ) 洲叶 _ n d o - ( b ) 1 1 di 卜 一t h 吲 t l e 胡伊一， ( c ) 1 1 dl + 1 1 h 喇2 t i m p 图3 - 6 任务分解后的运行时间图 3 5 本章小结 本章给出了多核嵌入式系统的实时性设计。其设计的主旨在于实时任务的并 行，以利用多核巨大的运算资源。并且在并行的过程中考虑二级缓存的共享情况， 来进一步优化实时任务的性能。最后通过操作系统的线程改造的支持，来自动优 化实时线程到二级缓存的映射关系。下一章将通过案例的方式来解读实时任务改 造，并给出了线程分配的具体算法 2 0 浙江大学硬上学位论文 第4 章多核嵌入式系统的实时改造 第4 章多核嵌入式系统的实时改造 4 1 实时改造概述 上一章中根据多核系统的高计算能力和二级缓存的特殊共享关系，给出了多 核嵌入式系统实时性的设计，包括多核实时任务设计和多核操作系统设计。本章 将以案例的方式解读多核实时任务设计，并给出操作系统线程分配的具体算法。 多核实时任务的设计中提到要发掘程序的可并行部分，并将之拆分并分配到 不同的核上运行程序的可并行部分是一个不确定的因子，它随着任务的改变而 改变。但本文在调研了大量的代码后，发现程序的可并行性部分基本属于两种情 况： 基于功能的并行 基于数据的并行 基于功能的并行可以被认为是程序中多个子模块的并行或者多个事务处理 的并行。基于数据的并行是那些数据密集型程序的并行。本文对实时任务的并行 改造就围绕这两种并行展开，在4 2 节和4 t 3 节将以案例的形式分别解读基于功 能的划分和基于数据的划分的方法和效能。并在案例研究中运用3 2 2 节所设计 的二级缓存的利用方式，来进一步提升实时任务的性能。 在研究利用二级缓存的方式后，在4 4 将利用操作系统的线程分配功能自动 将线程分配至合理的二级缓存。使得任务在线程化时只需考虑线程问的共享关 系，而无须了解底层硬件的具体实现。操作系统会根据底层硬件的配置完成线程 分配的工作 4 2 基于功能的划分 4 2 1 概述 一个实时任务在运行时，并不是在做一个十分孤立的工作。它需要用到系统 的各个资源来达到目的，在这个过程中往往涉及到多个子任务。在单核体系结构 下，如图4 - 1 ( a ) 所示的程序结构在实际应用中十分普遍。在程序的主循环中，需 要先后调用各个子模块的接口来协同完成这个任务。这种程序结构就存在着巨大 的可并行性，可以简单地拆分为图4 1 ( b ) 所示的两个线程。拆分后，多个子任务 可以同时运行在系统上，将大大缩短整个任务的运行时间。这种类型的拆分本文 2 1 浙江大学硕士学位