（计算机应用技术专业论文）linux内核支持smp并行机制的分析.pdf

四川人学颤l 学位论文 l i n u x 内核支持s m p 并行机制的分析 计算机应用技术专业 研究生：潘华指导教师：李炳法 计算机的处理能力在过去的几十年间一直以较高的速度不断增长，但新的 应用对计算机的处理能力提出了更高的要求，特别是随着i n t e r n e t 的迅速普及， 要求i n t e m e t 服务器有高度的并行处理能力。s m p ( s y m m e t r i c a l m u l f i p r o c e s s i n g 卜对称多处理是目前较为成熟、应用比较广泛且性价比较高的 一种并行处理技术，特别适用于小型的并行服务器，同时，它又是构成大型并 行服务器的一种基础技术。 l i n u x 是一个免费的开放源代码操作系统，其开放性已经吸引了成千上万的 计算机从业人员不断对它进行改进和完替。但由于l i n u x 并行技术的历史还不 长，l i n u x 内核是从2 0 版本才开始加入对s m p 并行处理器制支持的，因此存 在不完善之处是在所难免的。 本文正是针对l i n u x 2 4 2 的内核对s m p 并行处理器制的支持进行研究和改 进的。首先介绍了并行处理技术的发展以及l i n u x 对并行处理支持的历史；接 着，通过研究基于i n t e l 处理器平台的s m p 硬件基础和系统接口，了解l i n u x s m p 并行处理赖以存在的基础；然后，详细分析了l i n u x 的s m p 互斥机制， 指出了算法的局限性所在，给出了有效的改进方法；接着深入研究l i n u x 对多 处理器系统的进程调度，分析其性能并指出不足之处。最后对l i n u x 的物理页 面分配算法和回收算法进行研究，分析它在s m p 环境下的性能，并针对s m p 系统提出了一些改进策略。 关键词：l i n u x对称多处理器内核互斥进程调度 四川大学硕士学位论文 a n a l y s i so fs m p o nl i n u xk e r n e l c o m p u t e r sp r o c e s s i n gc a p a b i l i t yg r e wr a p i d l ya n dc o n t i n u o u s l yi n t h ep a s t t w e n t yy e a r s ，b u tt h en e wa p p l i c a t i o n sr e q u i r em o r ep o w e r f u lc o m p u t e rw i t hh i g h e r p r o c e s s i n gc a p a b i l i t y ，e s p e c i a l l ya l o n gw i t ht h er a p i dp o p u l a r i z a t i o n ，i n t e r n e ts e r v e r s m u s th a v e p o w e r f u lp a r a l l e lp r o c e s s i n gc a p a b i l i t y s m p ( s y m m e t r i c a l m u l f i p r o c e s s i n 曲i sar a t h e rm a t u r ep a r a l l e lp r o c e s s i n gt e c h n o l o g yw i t hp e r v a s i v e a p p l i c a t i o na n dh i 【g hp e r f o r m a n c e p r i c er a t e ，i t se s p e c i a l l ya p p l i c a b l e i ns m a l l p a r a l l e ls e r v e r , i na d d i t i o n ，i t sa l s oab a s et e c h n o l o g yi nc o n s t r u c t i n gl a r g es c a l e p a r a l l e ls e r v e r l i n u xi saf r e ea n do p e ns o u r c eo p e r a t i n gs y s t e m t h o u s a n d su p o nt h o u s a n d s c o m p u t e rp r a c t i t i o n e r sh a v eb e e na p p e a l e db yi t so p e n i n gc h a r a c t e rt oi m p r o v ea n d p e r f e c ti t b e c a u s et h eh i s t o r yo fl i n u xp a r a l l e lt e c h n o l o g yi ss h o r t , a n dl i n u x m e r e l yb e g a n t o p r o v i d es m ps u p p o r tf r o m v e r s i o n2 0 ，s of a u l t i n e s s e sa r e u n a v o i d a b l e t h i st h e s i sa i m sa tr e s e a r c h i n ga n di m p r o v i n gt h es m pp a r a l l e lp r o c e s s i n g m e c h a n i s mf o rl i n u xk e r n e l f i r s t ，i ti n t r o d u c e st h ed e v e l o p m e n to fp r e s e n tp a r a l l e l p r o c e s s i n gt e c h n o l o g ya n dt h eh i s t o r yo fl i n u xp a r a l l e lp r o c e s s i n gs u p p o r t i n g s e c o n d ，t h o u g ht h er e s e a r c ho fs m ps p e c i f i c a t i o nb a s e d o i li n t e lp r o c e s s o rp l a t f o r m , w ec o m p r e h e n dt h eb a s eo fl i n u xs m pp a r a l l dp r o c e s s i n g t h e n ，w ea n a l y z et h e s m pm u t u a le x c l u s i o no fl i n u x ，p o i n to u tt h el i m i t a t i o no ft h ea l g o r i s m ，a n d p r o v i d ea ne f f e c t i v ei m p r o v e m e n t t h e nw es t u d yt h el i n u xs c h e d u l e rf o rs m p s y s t e m ，a n a l y z ei t sc a p a b i l i t ya n dp o i n to u tt h el i m i t a t i o n f i n a l l y ，w er e s e a r c ht h e a l l o c a t i o n a l g o r i s m a n dr e c l a m a t i o n a l g o r i s m o fp h y s i c a l p a g e s ，a n a l y z e i t s p e r f o r m a n c eu n d e rs m pc o n d i t i o n s ，a n db r i n gf o r w a r dam e l i o r a t i v es t r a t e g y k e yw o r d s ：l i n u x ，s m p ，k e r n e l ，m u t u a le x c l u s i o n ，s c h e d u l e r 四门i 大学硕士学位论文 1 综述 1 1 对称多处理器系统简介 随着科学技术的发展，人们对计算机的运算能力的要求在不断增长。计算 机计算速度的提高，可以通过提高硬件的性能来获得，比如使用速度更快的处 理器。由于超大规模集成电路的反展目前已经接近极限，进一步提高硬件的处 理速度已经受到不小的限制，而且还出现了功耗过大、不易散热和电磁兼容等 问题。而使用多个处理器一起工作，可以用多个低档的处理器来达到甚至超过 高性能处理器的性能。 在一个多处理器系统中，有n 个处理器，其优点是能进行真正的并行处理， 即n 条指令能被同时执行。一般来说，多处理器系统主要由以下三种用途： ( 1 ) 如果一个程序能被分成几个部分，并像进程一样分别独立运行，则会减少 程序的运行时间； ( 2 ) 并行执行用户的几个程序，提高系统的吞吐量； ( 3 ) 多处理器实行冗余操作，可实现高可靠性系统。 上述( 1 ) 用的很少，因为把一个大型程序分解为n 个较小的单元且能并行执 行，需要用到相当高级的并行程序设计方法，这种方法已经用来设计某些特定 的程序，但在一般的程序设计中并不常用。 情况( 2 ) 是在多计算机系统应用中最流行的。多处理器系统的使用使系统能 同时运行多个进程，减少进程切换的时间，从而提高整个系统的处理能力。 情况( ( 3 ) 应用在要求高可靠性的系统中，通常是两台处理器一起使用，一台 正常工作；另一台冗余备份，做相同的工作。 s m p 是一种紧藕合的多处理器系统，系统中除了处理器外，其他设备都是 共享的，各个处理器之间通过总线或交叉开关相互连接，是一种以提高计算机 处理能力为目标的计算机系统。s m p 内部高速的数据传输率( 处理器与处理器 之间以及处理器与存储器之间) ，使得它在中小型应用中比其他松耦合的多处理 器系统有更好的性能，同时s m p 又是构成大型并行处理系统的基础之一。目前， 世界上大部分的高性能计算机系统都是采用s m p 技术或以s m p 技术为基础构 建具有可扩展性、更高容错性的系统。 l 四川大学硕士学位论文 在单处理器计算机上的并行计算，实际上是宏观上的并行，在某个时间段 能够运行多个任务，但在具体的某一个时刻只能执行一条指令，运行一个任务。 而在多处理器系统中，由于有多于一个的处理器，能实现真正的并行计算，每 个处理器可以运行不同的任务，在微观上同时执行多条指令。 s m p 将共享内存结构和分布式处理器、分布式中断结合在一起。它是完全 对称的，也就是说，所有处理器在功能上是相同的，处于对等状态。每个处理 器能与其它处理器通信。没有层次结构、主从结构，也没有只能与相邻处理器 通信的限制。s m p 的对称性体现在以下两个方面： ( 1 ) 内存对称性。如果所有处理器共享相同的内存空间，且通过相同的地址访 问内存空间，那么内存是对称的。内存对称提供了个重要的特性所 有处理器运行o s 单一拷贝的能力。任何已有的系统软件和应用软件在执 行时都相同，与处理器的数量无关。 ( 2 ) i o 对称性。如果所有处理器共享相同的i o 子系统( 包括i 0 端口和中 断控制器) ，任何一个处理器都能接受来自任意源的中断，则i 0 是对称 的。考虑到i o 对称性，有些能够对称访存的多处理器系统实际上不是完 全对称的，因为它们将一个处理器专门用来处理中断。i o 对称有助于消 除i o 瓶颈，因而可以增大系统的可扩展性。 1 2 多处理器操作系统简介 多处理器操作系统是在单机多道程序系统上发展起来的，具有以下特征： 1 并行性由于多处理器系统中有多个处理器，所以使多个进程并 行执行，从而获得更高的系统吞吐量和更快的运算速度。 2 分布性系统中的进程被分散到多个处理器上运行，进程不必绑 定到某一个处理器上。 3 通信和同步在多处理器系统中，由于进程间的资源共享和相互 合作，不仅运行在同一个处理器上的进程之间需要进行通信和同步， 不同处理器上的进程之间也需要通信和同步。 4 可重构性当系统中某个处理器发生故障时，操作系统应该能够 从故障中换出，并重新启动该处理器。 四川大学颂j = 学位论文 1 3 论文的结构 第一章简单介绍多处理器系统、多处理器操作系统及其互斥。第二章对比 目前的并行处理技术c l u s t e r 、n u m a 和s m p ，并阐述l i n u x 内核对s m p 的支 持。第三章讨论了s m p 系统的硬件基础，包括处理器、中断、内存和高速缓存。 第四章描述了s m p 的系统接口。第五章讨论单处理器系统中的互斥。第六章研 究l i n u x 内核中的多处理器互斥策略，并提出了一种新的互斥算法。第七章深 入研究了l i n u x 对多处理器系统的进程调度。第八章是对l i n u x 操作系统中物 理页面的分配和回收的研究。第九章是对本文的总结。 四川大学硕士学位论文 2 并行处理技术及l i n u x 对s m p 的支持 2 1 并行处理技术 并行技术是提高计算机系统处理能力的行之有效的重要手段，通过多 个处理器的并行，能实现多道程序的真正并行，而非并发执行。耦合程度是多 处理器系统的一个重要指标，耦合程度通常是指处理器之间的物理距离，耦合 程度越高，处理器之间的距离越小，反之处理器之间的距离越大。按处理器的 耦合程度由低到高，目前应用比较广泛的并行处理技术主要有c l u s t e r 技术、 n u m a 技术和s m p 技术 c l u s t e 一群集，又称机群技术，是全体计算机( 结点) 的集合，这些计算机由 高性能网络或局域n ( l a n ) 物理地互联。典型情况下，每个计算机结点是一台 s m p 服务器、一台工作站或是一台p c 计算机。更重要的是，除了满足由交互 用户单独地使用每个结点的协定任务外，所有c l u s t e r 结点必须能一起集体工 作，如同一个单一集成的计算资源。 c l u s t e r 的五个体系结构概念： ( 1 ) c l u s t e r 结点 每个结点是一台完整的计算机。这就意味着每个结点有自己的处理 器、高速缓存、磁盘以及某些1 1 0 适配器此外在每个结点上留驻有完 整、标准的操作系统。一个结点可以拥有多台处理器，但只有一份操作 系统映象拷贝。 ( 2 ) 单一系统映象一个c l u s t e r 系统是一个单一的计算资源。c l u s t e r 借助 若干单一系统映象( s s i ，s i n g l e s y s t e mi m a g e ) 技术，实现单资源概念。 s s i 使c l u s t e r 变得更加容易使用和管理。 ( 3 ) 结点间连结 c l u s t e r 中的结点，通常采用商品化网络，如以太网、f d d i 、光纤通 道以及a t m 开关进行连接，此外使用标准协议以平滑结点间通信。 ( 4 ) 增强的可用性 4 四川大学硕士学位论文 c l u s t e r 提供了一个成本有效方法以增强一个系统的可用性，这是指 一个系统可为用户使用的时间百分比。 ( 5 ) 更好的性能 在若干服务领域中，c l u s t e r 应能提供更高性能。其中一个领域是将 c l u s t e r 作为超级服务器使用。如果一个具有u 个结点的c l u s t e r 中的 每个结点能为m 个客户服务，则该c l u s t e r 能同时为i n n 个客户服务：另一个服 务领域是c l u s t e r 通过分布式并行处理方法，用最短的时间去完成一个大型作业 的执行。 2 1 2 n u m a n u m a ( n o n - u n i f o r mm e m o r ya c c e s s ，非均匀存储访问) 是s m p 技术的扩 展，它将多个s m p 结点通过系统互联网络联接起来构成一个更大的系 统n u m a 技术既保持了s m p 结构的优点，又缓解了传统s m p 系统规模不可 扩展的问题。 n u m a 系统采用的是分布式存储器体系结构，存储器在物理上是分离的， 分布到各个结点上，每个结点都有本地存储器，但通过内存页面在不同结点之 间的复制和迁移，它们在逻辑上又表现为一个整体，系统中的处理器共享地访 问所有存储空间。n u m a 的这种分布式共享存储器的结构大大提高了系统的可 扩展性，通过增加结点，不仅增加了处理器数目，还加大了存储容量，提高了 加处理能力。由于应用程序可充分利用数据的局部性，在大部分时间内能同时 访问多个局部存储器，从而缓解了s m p 系统中存在的争用和带宽问题。 除了扩展问题外，某些n u m a 系统还试图解决s n p 系统所存在的容错性 问题，在这些n u m a 系统中，操作系统的部分可被复制多份，分别运行于 多个结点之中，其中一个运行失效时，它的任务可由其他操作系统复本处理， 不会导致整个系统的瘫痪。n u v i a 的结构见图2 一l 。 四川丈学硕上学位论文 图2 1 n u m a 的一般结构 s m k 对称多处理是目前耦合程度最高的一种多处理器系统。系统具有 对称性这一点很重要，它能使对称多处理器系统获取比非对称多处理器系统更 高的并行性。在非对称多处理器系统中，任务和资源由不同的处理器进行管理， 有的处理器只能处理i o ，有的处理器只能处理操作系统的任务提交，显然非 对称多处理器系统是不能负载均衡的。在对称多处理器系统中，资源为系统中 的所有处理器共享，每个处理器能平等地访问共享存储器、i o 部件以及操作 系统服务，系统负载能有效地分配到所有的处理器上。 目前，大多数s m p 系统的处理器通过高速监听总线( s n o o p yb u s ) 连接处理 器和共享存储器，例如：由i n t e l 系列处理器所组成的s m p 系统，就是基于i n t e l 的m u l t i p r o c e e s o rs p e c i f i c a t i o n 规范和p 6 总线仲裁算法开发出来的。由于争用 共享总线和争用共享存储器，从而限制了总线型的s m p 系统中处理器的数目一 般不超过4 个。 为解决总线的瓶颈问题，许多s m p 系统中都使用交叉开关的方式连接多个 处理器和共享存储器，如：s u nu l t r ae 一1 0 0 0 0 并行服务器，采用1 2 8 g b i s 的 g i g a p l a n e - x b 交叉开关。交叉开关的使用，令s m p 系统的规模可扩展到3 2 ， 甚至是6 4 个处理器。 虽然采用交叉开关的s m p 系统在性能和可扩展性上优于总线型的s m p 系 统，但从整体来说，s m p 系统所提供的扩展性仍然有限。s m p 系统中增加更多 四川大学硕士学位论文 处理器的难点是系统不得不消耗资源来支持处理器抢占内存，以及内存同步两 个主要问题。 抢占内存是指当多个处理器共同访问存储器中的数据时，它们并不能同时 去读写数据，虽然一个处理器正在读一段数据时，其他处理器可以同时读这段 数据，但当一个处理器正在修改某段数据时，该处理器将会锁定这段数据，其 他处理器要操作这段数据就必须等待数据的解锁。显然，处理器数目越多，这 样的等待问题就越严重，系统性能不仅无法得到提升，甚至会出现下降。为了 尽可能地增加更多的处理器，现在的s m p 系统基本上都采用增大服务器高速缓 存容量的方法来减少抢占内存，因为高速缓存是处理器的“本地内存”，它与处 理器之间的数据交换速度远远高于内存总线速度，又由于高速缓存不支持共享， 这样就不会出现多个处理器抢占同一段内存资源的问题了，许多数据操作就可 以在处理器内置的高速缓存或外置的高速缓存中顺利完成。 然而，高速缓存的作用虽然解决了s m p 系统中的抢占内存问题，但又引起 了另一个较难解决的所谓“内存同步“问题。在s m p 系统中，各处理器通过高速 缓存访问内存数据时，要求系统必须经常保持内存中的数据与高速缓存中的数 据一致，若高速缓存的内容更新了，内存中的内容也应该相应更新，否则就会 影响系统数据的一致性。由于每次更新都需要占用处理器资源，同时还要锁定 内存中被更新的字段，而更新频率过高必然会影响系统性能，更新间隔过长又 可能导致因交叉读写而引起的数据错误，因此，高速缓存的更新算法十分重要。 目前的s m p 系统多采用侦听算法来保证处理器高速缓存中的数据与内存保持 一致。系统的高速缓存越大，抢占内存出现的概率就越小，同时由于高速缓存 的数据传输速度高，高速缓存的增大还提高了处理器的运算速度，但系统保持 内存同步的难度也增大。 2 2 l i n u x 操作系统对s m p 的支持 l i n u x 来源于u n i x ，它首先由l i n u st o r v a l d 开发出来，其后遍布在世界 各地的成千上万的自愿者通过i n t e r n e t 组织起来，不断对它进行修改、完善， 使得l i n u x 逐渐成为一个稳定可靠、功能完善的操作系统。 早期的l i n u x 系统并不具备对s m p 并行处理的支持。l i n u x 最初设计为单 四川大学硕士学位论文 机处理系统，l i n u x 单处理器( u n i p r o c e s s o r ) 内核设计遵循三大原则： ( 1 ) 在内核态运行的进程不能被其它要在内核态运行的进程所抢先( 中断返 回时检查是否是用户态才可能重新调度) ，除非它主动放弃( 时间片用完， 返回用户态) 或者进入睡眠( 等待资源或事件被阻塞) 。该原则保证了对其 它进程看来，大部分的内核代码是原子的，确保了内核得以处于一个一 致的状态，为大多数同步问题提供了全面而彻底的解决方案。 ( 2 ) 中断处理可以打断运行在核心态的进程，但它是在这个进程的上下文中 执行的，中断处理结束后仍然会将处理器的控制权交回给被中断的那个 进程( 也即，嵌套的中断返回时不会进行重新调度) 。同时，进程可以对 中断进行屏蔽。 ( 3 ) 中断处理不能为其它要在内核态运行的进程所抢先，因此，或者中断完 整地得到处理，或者为更高优先级的中断所打断。 l i n u x 内核从2 0 版开始，通过对内核进行了大量修改以实现对s m p 的支 持。主要的变化包括：启动代码，处理器问通信，中断处理，同步，并行和调 度策略以及相应的对内核关键数据结构的修改。但为了加速和方便s m p 支持的 实现，重用大量现有的单处理器代码，l i n u s 决定，仍然维护单处理器内核设 计三个原则，为此引入了一个内核大自旋锁，所有进程都通过这个大锁来实现 向内核态的迁移。只有获得这个大锁的处理器可以进入内核( 如中断处理) 。这 种实现对i 0 密集型的应用性能无疑是相当差的。但对计算密集型的应用，大 部分时间处于用户态，性能尚可，但一旦1 ( 3 事件增加，系统性能会大大下降， 与单处理器就无甚区别了。 l i n u x 内核2 2 版对s m p 并行处理作了比较大的改进，但它仍然遵守 后二个内核设计原则，而第一个原则对于每个处理器还是成立的。多个处理器 已经可以同时位于内核中，实现了粗粒度的自旋内核。信号处理，中断处理和 一些i 0 都已经使用了细粒度的锁，为中断处理引入全局中断锁。内核自身有 了一定程度的并行，性能有所改善。但文件系统和网络，存储管理等子系统还 是被大锁k e r n e lf l a g 保护着，基本无法并行。可以预见l i n u x 对s m p 并行处理 器制的支持将会越来越完善。 四川大学硕士学位论文 3 s m p 硬件基础 3 1 处理器 s m p 系统中的处理器分为b s p 和a p 。系统中的处理器在功能上是相同的， 这样区分b s p 和a p 是为了方便。在系统启动时，b s p 负责初始化硬件和启动 操作系统，然后唤醒a p 一起工作。在系统关闭时，b s p 负责关闭a p ，然后关 闭系统。图3 1 是s m p 系统的一般结构。3 2 中c p u i 为b s p ，其它c p u 为a p 。 3 2 蝴c 图3 1s m p 系统结构 a p i c 基于分布式结构，在这种结构中中断控制功能分布在两种基本功 能单元中：局部a p i c 单元和i oa p i c 单元。局部单元与i o 单元通过中 断控制通信总线i c c 互相通信，如3 2 。 9 四川大学硕士学位论文 图3 2a p i c 的配置 在多c p u 系统中，多个局部单元和y o 单元运行起来就像一个整体， 互相之间通过i c c 通信。a p i c 有选择地传送来自中断源的中断。 a p i c 有助于获得可扩展性： 1 减少了内存总线上与中断有关的流量，使内存总线更有效地为c p u 服务。 2 有助于多个c p u 共享中断处理负载。 局部a p i c 也提供处理器间中断1 p i ，允许一个c p u 中断其它c p u 。i p i 有 几种类型，其中i n e ri p i 和s t a r t u pi p i 专用于系统启动和关闭。每个局部 a p i c 有一个局部单元d 寄存器，每个y oa p i c 也有一个y o 单元d 寄存器。 这些d 作为各个a p i c 的物理名称。软件用此d 为y o 中断和c p u 间中断指 定目的地，也可用于访问i c c 总线。 由于是分布式架构，在实现时局部a p i c 和y oa p i c 可以是单个芯片，如 i n t e l 8 2 4 8 9 d x ，也可是集成到系统中的其它组件。例如局部a p i c 可以集成到 l o 四川大学硕士学位论文 c p u 中，如p e n t i u m 系列c p u ：i oa p i c 也可集成到i o 芯片组中，如i n t e l 8 2 4 3 0 p i c e i s a 桥芯片组。 a p i c 是基于分布式结构的。中断控制功能分布在局部a p i c 和i oa p i c 中。局部a p i c 和i oa p i c 通过i c c 进行通信。i oa p i c 检测中断输入，寻址 局部a p i c ，然后在i c c 总线上发送中断。被寻址的局部a p i c 接收i oa p i c 发送的消息。在s m p 系统中，每个c p u 都需要一个局部a p i c 。可以使用一个 或者多个i oa p i c 。总线的中断信号线的分配可以在实现时指定，也可以由第 4 章描述的m p 配置表来指定。 3 3 中断模式 s m p 系统中有3 种不同的中断模式，如下： 1 p i c 模式旁路所有的a p i c 组件，强制系统运行在单c p u 模式下 2 虚线路模式用一个a p i c 作为虚线路，但是在其它方面运行起来与 p i c 相同 3 对称i o 模式使系统运行在多个处理器之上 p i c 和虚线路模式提供了p c a t 兼容性。在p i c 和虚线路模式下，将a p i c 和8 2 5 9 a 联合使用，可提供与单c p u 的p c a t 机的全d o s 兼容性。 必须实现对称i o 模式。操作系统被启动到p c a t 兼容模式中的一种，然 后当操作系统进入多处理器模式时，就切换到对称i o 模式下。 四川大学硕士学位论文 3 3 1p i c 模式 图3 3p l c 模式( 阴影区域表示未使用的部分，点线表示中断的路径) p i c 模式在软件上与p c a t 兼容，因为它实际上使用了与p c a t 相同的 硬件中断配置。如图3 3 。通过使用中断配置寄存器i m c r ，硬件旁路了a p i c 组件。i m c r 寄存器控制到达b s p 的中断信号是来自主p i c 还是来自局部a p i c 。 在进入对称i o 模式前，b i o s 或o s 必须改变i m c r 以退出p i c 模式。两个读 偈或只写i o 端口2 2 h 和2 3 h 支持i m c r ，他们分别接收地址和数据。为访问 i m c r ，应向i o 端口2 2 h 写入7 0 h 以选择i m c r 。然后向端口2 3 h 写入数据。 在上电时端口2 2 h 的默认值为0 ，将n m i 和8 2 5 9i n t r 直接连接到b s p 。写入 0 1 h 则强制n m i 和8 2 5 9 中断信号通过a p i c 。如果没有实现p i c 模式，那么i m c r 是可选的。操作系统可以利用n i p 特征信息字节的i m c r 位来检测m c r 是否 实现。 四川大学硕上学位论文 3 3 2 虚线路模式 一一一j 一一! i 一一j 一一 i 一一：_ i 一一i ；l 。 f ；jfl ；l1 l ! h 。 j i l 。“ i i i i ”“ i i l | r ，f i lw lh i i lli l ：l li ：ill ： ：i 肾 l ；|。j i l 。冀。、li。l i i t i , l f j 3 ： f iil 町1 h v l i l 一卜h 一卜一- - 4 - 1 1 - - f j一- 4 - i t - t i ll i 、i。、 i 一。 f l篇t=lf i i m p-s一；”卜i l： 图3 - - 4 不通过l oa p i c 的虚线路模式( 阴影区域表示未使用的部分，点线表示中 断的路径) 虚线路模式提供了一个单处理器的硬件环境来启动系统，并提供了p c a t 兼容性以运行d o s 程序。系统有两种虚线路方式，如图3 4 和图3 5 。图2 4 ，8 2 5 9 ap i c 截获所有中断，通过局部a p i c 的局部中断0 ( l 删0 ) 将 他们发送到b s p 。局部a p i c 的i n t i n o 引脚被编程为e x t l 奠i t 以指定a p i c ， p i c 作为外部中断控制器使用。只要局部a p i c 发现一个e x t i n t 类型的中断， 它就e x t i n t 事务和p i n t 中断一起声明给c p u 。在这种情况下i oa p i c 未使 用。图3 5 中，同时使用局部a p c 和i o a p i c 。 四川大学硕士学位论文 f f i 1 i 1 i i i j f l 1 i l i i i l f i i i l i i i i i 一i j 1 i 1一卜斗_ _ 卜 ，l 一 十斗o _ 一 j - f 一一一 、 。f 3 e r 、 _ ：0 j ：1 i 。凛卜， j ； - i ，t 二5j i 一 l l h t e r r l f ti h f u ts l 、 图3 5 通过i o p i c 的虚线路模式( 阴影区域表示未使用的部分，点线表示中断传送的 路径) 3 3 3 对称i o 模式 对称 0 模式需要至少一个加la p i c 在工作。i ，o 中断由 0a p i c 产生， 送到i c c 总线上，所有的处理器都可以接收这个中断。所有的8 2 5 9 中断信号 线要么被屏蔽，要么与oa p i c 一起工作在混合模式下。硬件必须使系统从 p i c 或虚线路切换到对称i o 模式。如果实现了i m c r 寄存器，则当操作系统 准备切换到多处理操作时，系统向i m c r 写入0 1 h ，并启用i oa p i c 的重定向 表项。图3 6 是对称模式下传送中断的路径。 4 四川大学硕士学位论文 l j 一一! j 一j 一一 i 一一= ：一一 i i i i i i i i l l i l l i | ii 垃 | | i i l 。二 1 1 i l 二： i i i 卜n m v ij 。l - t - t -；- w jr 开； 一1l 1 一1 1 一 、 l i t - r n 、c 、 j ， ：0 1 1 、 j ，l c c6 1 _ s j ：锤； 1 川，。 “。紫# ”1f ， l li i t r l p ir , p j t 。 i 、 l ， 图3 6 对称i 0 模式( 阴影部分未使用，点线表示中断传送的路径) 3 4 内存 s m p 内存配置基于p c ，a t 的内存映射，拥有4 g 的物理内存空间，如图2 5 。物理内存应该从0 开始且应是连续的。内存映射 o 设备应该被映射到物 理内存的顶端。a p i c 的默认内存基地址是0 f e c o _ 0 0 0 0 h 和0 f e e 0 _ 0 0 0 0 h 。与 单处理器系统相比，s m p 需要高带宽的内存总线。为了减少内存总线带宽的限 制，可使用高性能的二级缓存，例如有写回更新策略和s n o o p i n g c o n s i s t e n c y 协议的缓存。通过减少总线的流量、增加带宽，使用二级缓存能提高系统性能。 图3 7 显示s m p 系统的内存布局。 四j 1 i 大学硕士学位论文 3 5 高速缓存 f e f 0 0 0 0 0 h f e e o - 0 0 0 0 h f e d o - 。0 0 0 h f e c i ) _ 0 0 0 0 h 0 0 1 0 _ 0 0 0 0 h 0 0 0 f - o o h 0 0 0 e _ 0 0 0 0 h 0 0 0 d0 0 0 0 h 0 0 0 a 一0 0 0 0 h 日时sp r o m l o c a la p l c l ? o a p l c “1 鼢渊e f 。 。后猪般器。 s h a d o w e db i o s 茹始黜器。 e x p a n s l o nr o m r o me x t e n s i o n s v l d e ob u r f e r 讣骠嚣等 图3 7s m p 系统的内存布局 由于几乎所有的程序都具有局部引用特性，所有各种计算机上面都能找到 高速缓存。现在大多数的处理器上都集成了高速缓存。系统可以使用相互独立 的指令高速缓存和数据高速缓存，处理器可以同时从指令高速缓存中取指令， 而从数据高速缓存加载或者存储数据。 1 6 四川大学砸七学位论文 3 5 1 程序的局部引用特性 在对l i n u x 、u n i x 及其他一些系统存在着对称多处理器系统调度中的个 重要特性，我们称其为处理器的亲和性。 处理器的亲和性指的是将每一个进程都保持在同一个处理器上运行的能 力，实践证明它将能充分利用高速缓存所带来的好处。所有的系统中都具有分 级的内存结构，由位于不同级别的、速度和容量都不同的内存组成。最快的内 存是高速缓存，就像它的名字暗示的一样，用于临时存放或缓存主内存的内容。 高速缓存非常快但是比较昂贵，因此多数处理器芯片上内置有少量的高速缓存， 而大多数高速缓存放在系统主板上。它的工作原理是基于程序访问的局部性。 对大量典型程序运行情况的分析结果表明，在一个较短的时间间隔内，由程序 产生的地址往往集中在存储器逻辑地址空间的很小范围内。指令地址的分布本 来就是连续的，再加上循环程序段和子程序段要重复执行多次。因此，对这些 地址的访问就自然地具有时间上集中分布的倾向。数据分布的这种集中倾向虽 不如指令明显，但是对数组的存储和访问以及工作单元的选择都可以使存储器 地址相对集中。这种对局部范围的存储器地址频繁访问，而对此范围以外的地 址则访问甚少的现象，就称为程序的局部引用特性。根据程序的局部性原理， 可以在主存和处理器通用寄存器之间设置一个高速的容量相对较小的存储器， 即高速缓存，把正在执行的指令地址附近的一部分指令或数据从主存调入这个 存储器，供处理器在一段时间内使用。这对提高程序的运行速度有很大的作用。 系统正是依据此原理，不断地将与当前指令集相关联的一个不太大的后继指令 集从内存读至高速缓存，然后再向处理器高速传送，从而达到速度匹配的。处 理器对存储器进行数据请求时，通常先访问缓存。由于局部性原理不能保证所 请求的数据百分之百地在缓存中，这里便存在一个命中率的问题。即处理器在 任一时刻从缓存中可靠获取数据的几率。命中率越高，正确获取数据的可靠性 就越大。一般规定缓存与内存的空间比为4 ：1 0 0 0 ，即1 2 8 k b 缓存可映射3 2 m b 内存；2 5 6 k b 缓存可映射6 4 m b 内存。在这种情况下，命中率都能在9 0 以上。 至于没有命中的数据，c p u 只好直接从内存获取，获取的同时，也把它复制进 缓存以备下次访问。 因此在很多对称多处理器系统中都利用到了程序的局部引用特性。局 四川大学硕上学位论文 部引用特性在两个方面提高了高速缓存利用率： 1 一个给定的处理器试图运行它上次运行过的进程，尽量将每 一个进程放在一个固定的处理器上运行，它可以充分利用缓 存资源中既存的信息，有效地减少进程调度的时间花销和进 程的执行时间，否则将造成缓存资源的极大浪费。 2 被调度的进程试图返回到它上次运行过的处理器，因此避免 了在另一个处理器上重新装入缓存所造成的损失。 目前国际上己有一些针对程序局部性的研究。由斯坦福大学的r o h i t c h a n d r a ，s c o t td e v i n e ，b e nv e r g h e s e ，a n o o pg u p t a 和m e n d e lr o s e n b l u m 共同研究 开发的多处理器计算服务器的调度和页迁移中就充分利用了亲和性调度方 法，它检验了在这样性能的计算服务器上的o s 调度和页迁移策略的有效性。 该实验是在s i a n f o r dd a s h 上实现的，它是一个分布存储器的、带有缓存一致 性的多处理器系统。实验中将处理器簇亲和性和缓存亲和性( 处理器亲和性) 以 及简单的页迁移算法结合起来，发现由顺序工作组成的多道程序负载在传统的 u n i x 调度策略上运行改率极低。相比之下，新算法的策略产生了两倍以上的 性能提高。还有加拿大的s a s k a t c h e w a ns a s k a t o o n 大学的s r i k a n ts a b r a m a n i a m 和d e r e kl e a g e r 在失衡工乍负荷的亲和性调度一文中指出，在有一个占用 大量执行时间的任务的工作负荷环境中( 一个循环迭代) ，由于每次迭代所产生 的计算量不同，被执行的并行循环将严重失衡。 在这种环境下，亲和性调度的简单形式就变得不适合了。于是文中提出了 两种新的被称为d y n a m i e 和w r a p p e d 的调度算法。实验研究发现这些新算法既 能保持亲和性又能维护负载平衡，在这些特殊环境下性能良好。足见亲和性调 度的重要作用。 3 5 2 高速缓存的替换策略 因为高速缓存比主存小得多，所以在高速缓存缺失时必须用新的数据来替 换高速缓存中的缓存线。典型的替换策略是l r u ( 最近最少使用) 。替换策略 对软件是透明的。 四川大学硕士学位论文 3 5 3 写入策略 当处理器保存数据的时候，如果该数据在高速缓存中命中，则将数据直接 写到高速缓存中。这样做能提高系统的性能，其原因有两个：首先，由于程序的 局部引用特性，被保存的数据在写入之后会被频繁地使用，所有提高了高速缓 存的命中率：其次，写高速缓存的速度比写主存的速度要快，减少了处理器等 待存储数据的时间。 如果数据在高速缓存中命中，处理器将其写入高速缓存的同时也可写入主 存中，这就产生了两种不同的高速缓存写入策略：写透协议和写回协议。写透 协议是指将数据同时写入到高速缓存和系统主存。这意味着高速缓存和主存中 的数据副本完全相同，其缺点是每次写入操作都会产生一个主存储器周期，会 降低系统的速度。写回协议也将数据写入到高速缓存中，但是不写入主存，直 到缓存线替换或操作系统要求写入主存才写入主存储器。与写透协议相比，它 没有写主存的存储器周期，所以速度比写透协议快。写回策略的缺点是，主存 中的数据和高速缓存中的数据不一致。在多处理器系统中，由于一个处理器在 缓存中修改了数据而没有写入主存，另一个处理器就可能会访问到过时的数据， 因此必须使用高速缓存一致性协议来保证数据的一致性。 如果处理器要写入的数据在高速缓存中没有命中，那么采取的措施取决于 高速缓存是否使用了写分配策略。使用了写分配策略时，处理器要保存的数据 被写入高速缓存中，以利用程序局部性所带来的好处。首先，替换策略选择一 个要丢弃的缓存线，为新数据腾出空间。如果使用了写回策略，而且被替换的 缓存线被修改过，这意味着它与主存中的副本不一致，因此必须将其写入到主 存。然后，处理器从主存中读取要保存的数据所在的缓存线，再将数据写入到 高速缓存中，并设置这个缓存线的修改位，表明主存中的数据与高速缓存不一 致。如果采取的是写透策略，则处理器从主存中读取缺失的缓存线，然后同时 将数据写入高速缓存和主存中。与写回策略相比，每一次缓存缺失都会导致两 个主存周期：一次读和一次写，因此在使用写透策略的同时使用写分配会降低 性能。 1 9 四川大学硕士学位论文 3 5 4 高速缓存一致性协议 在多处理器系统中，如果任何处理器对任何共享存储位置的读取总是返回 最近写入的值，那么该系统的高速缓存是一致的。 假设一个多处理器系统没有维护高速缓存的一致性，考虑这样一个进程， 它睡眠一秒种，将计数器加1 ，然后再睡眠，再将计数器加1 ，就这样循环往复