（计算机系统结构专业论文）基于smp的线程轻化相关研究.pdf

摘要 约5 0 年的并行计算历程中，从处理机内部指令集并行到集群尺度上的并行，部在现 有计算能力的基础上，极大的开发了计算的潜能。随着线程应用日益广泛，体系结构、 编译技术、编程模型、线程库等层面都在朝向更高并行度、更细并行粒度方向发展。同 时，对网络信息服务类海量并发细粒度应用而言，利用传统线程不能如期获得s m p 上的 加速，而随着c m p 和s m t 的进展，线程开销的优化更是提上了日程。 为此，本文围绕优于传统p o s i x 线程的合适的调度粒度和相应高效低开销的调度切换 技术展开讨论，以提高细粒度并行下资源的有效利用率。主要工作如下： 基于p t h r e a d 线程全面分析与开销测试，实验定量分析出p t h r e a d 线程微秒级开销下 同步粒度与多处理机上性能加速的关系：在相当于线程切换开销十倍量级的同步粒度下， 执行流在多处理机上很难获得有效的性能提高，进而指出细粒度并行性能一定程度上受 制于线程自身开销的问题。 针对细粒度并行线程开销敏感问题，提出了资源自封闭体和主动调度机制，设计并 开发了独立于操作系统的高效低开销调度模块。该调度模块兼顾核心级线程真正并行、 用户级线程开销小的优点，可根据应用特征进行用户级调度，有效地减少了调度和切换 开销，可高效实现每秒十万次级别的切换频度。初步达成线程粒度和切换开销的轻化， 克服了细粒度并行应用在多处理机上利用标准线程无法有效获得加速的弊端。此外，该 调度模块实现不改变操作系统核心的情况下有效利用多处理机，可广泛适用于此类相关 度不大的细粒度并行应用。 进一步，利用资源自封闭体的构造和该调度模块成功改善了并行模拟器s a n d f o x 的 实际性能，获得了较标准线程库p t h r e a d 实现而言几倍的提高。对于建立的高密度访问 w e b 服务器模型，由于在微秒级同步粒度情况下，有至少3 0 以上的开销浪费于调度切 换，应用轻化手段后如期获得c p u 有效利用率的大幅提高。从而为网络信息服务类海量 并发细粒度应用的性能提高研究提供了新的解决思路。 另外，本文还分析了l i n p a c k 、n p b 等常用并行应用，试图为线程轻化作应用特征准 备。作为辅助分析，编写了误差精度在5 以内的l i n p a c k 仿真模型。利用该模型获得的 详细开销数据表明，l i n p a c k 等常用高性能应用不适于轻化，文末给出总结以备后续轻化 工作参考。 关键词：s m p 、线程、轻化、调度、并行模拟器、w e b 服务器、l i n p a c k r e l a t e dr e s e a r c ho nt h r e a dl i g h t w e i g h t i n gb a s e do ns m p z h a n gw e n l i ( c o m p u t e r a r e h l r e c t u r e ) d i r e c t e db yf a nj i a n p i n g i nt h ec o n r s eo fp a r a l l e lc o m p u t i n ga b o u t5 0y e a r s ，t h ep o t e n l a a lo fc o m p u t i n gi sg r e a t l y d e v e l o p e df r o mi s ap a r a l l e li n s i d ep r o c e s s o rt op a r a l l e li nc l u s t e ro nt h eb a s i so fe x i s t i n g c o m p u t i n gc a p a b i l i t y a st h r e a da p p l i c a t i o n sa r eb e i n gp o p u l a r h i g h e rp a r a l l e ld e g r e ea n df i n e r p a r a l l e lg r a n u l a r i t ya l ed e v e l o p e do ns y s t e ma r c h i t e c t u r e ，c o m p i l et e c h n o l o g y , p r o g r a m n u n g m o d e l ，a n dt h r e a dl i b r a r y e t c m e a n w h i l e ，f o rm a s s i v e l yc o n c u r r e n c yf i n e g r a i n e da p p l i c a t i o n s l i k en e t w o r ki n f o r m a t i o ns e r v i c e ，i ti sh a r dt og e ts p e e d u po ns m p b yt r a d i t i o n a lt h r e a d a n d w j t ht h ep r o g r e s so fc m pa n ds m t o p t i m i z a t i o no ft h r e a do v e r h e a di sb r o u g h ti n t os c h e d u l e e s p e c i a l l y f o rt h i sr e a s o n , t oi m p r o v ee f f e c t i v eu t i h z a t i o no fr e s o u r c c su n d e rf i n e - g r a i n e dp a r a l l e l s u i t a b l e g r a n u l a r i t ys u p e r i o rt ot r a d a i o n a lp o s i xt h r e a da n dt h ec o r r e s p o n d i n gh i g h - e f f i c i e n t l o w - o v e r h e a ds c h e d u l i n gt e c h n o l o g ya l ed i s c u s s e di nt h et h e s i s t h eo l a l nw o r ki sa sf o l l o w s ： b a s e do nd e t m la n a l y s i sa n do v e r h e a dt e s to fp t h r e a d ，t h er e l a t i o n s h i pb e t w e e n s y n c h r o n i z a t i o ng r a n u l a r i t ya n ds p e e d u po n $ m p d e ip t h t e a dm i c r o s e c o n dl e - e ls v d t c h o v e r h e a di sg o tb yq u a n t i t a t i v ea n a l y s i sw i t he x p e r i m e n t s f o rs y n c h r o n i z a t i o ng r a n u l a r i t y e q u i v a l e n tt ot e n f o l dl e v e lo ft h r e a ds w i t c ho v e r h e a d , t h ee x e c u t i o nf l o wi sh a r dt oo b t a i n e f f e c t i v ep e r f o r m a n c es p e e d u po ns m et h ep r o b l e mi sp o i n t e do u tt h a tf i n e - g r a i n e dp a r a l l e l p e r f o r m a n c ei sl i m i t e db yt h r e a do v e r h e a di t , s e l l a i m i n ga tt h r e a do v e r h e a ds e n s i t i v ep r o b l e mf o rf i n e - g r a i n e dp a r a l l e l ，t h ep r i n c i p l eo n r e s o u l i ? - es e l fc l o s u r ea n da c t i v es c h e d u l i n gi sp u tf o r w a r d , a n dh i g h - e f f i c i e n tl o w - o v e r h e a d s c h e d u l i n gm o d u l ei n d e p e n d e n tw i t ho p e r a t i n gs y s t e mi sd e s i g n e da n dd e v e l o p e d t ot h e s c h e d u l i n g m o d u l e ，i ti so fa d v a n t a g e so ub o t hr e a lp a r a l l e l i s mf o rk e r n e lt h i e a da n dl o w o v e r h e a df o ru s e rt h r e a d i tc a nd os c h e d u l i n ga c c o r d i n gt oa p p l i c a t i o nc h a r a c t e r i s t i c si nu s e r l e v e l ，i m p l e m e n th i g he f f i c i e n ts w i t c ht of r e q u e n c ya st e nt h o u s a n d sp e r * , e e o n d , a n dr e d u c e s w i t c ho v e r h e a de f f e c t i v e l y t h u s i tc o n d u c e st ol i g h t w e i g h to nt h r e a dg r a n u l a r i t ya n ds w i t c h o v e r h e a dt e n t a t i v e l y a n do v e r c o m et h ep r o b l e mt h a tt i n , g r a i n e dp a r a l l e l a p p l i c a t i o n sa r e u n a b l et oe f f e c t i v e l yo b t a i ns p e e d u po i ls n i pb ys t a n d a r dt h r e a d b e s i d e s t h es c h e d u l i n g m o d u l ei m p l e m e n t ss m pe f f e c t i v eu s ew i t h o u tm o d i 聊n go p e r a t i n gs y s t e mk e r n e l ，a n dc a l lb e w i d e l yu s e di nf i n e - g r a i n e dp a r a l l e la p p l i c a t i o n sw i t hl i t t l ed e p e n d e n c y b yc o n s t f t l c l i o no fr e $ o o r c es e l fc l o s u r ea n dt h es c h e d u l i n gm o d u l ef u r t h e r , t h er e a l p e r f o r m a n c eo fp a r a l l e ls i m u l a t o rs a n d f o xi si m p r o v e da n ds e v e r a lt i m e sb e t t e rt h a nt h a to n s t a n d a r dt h r e a dh b r a r yp t h r e a d t h e nt os i m u l a t e dh l 曲d e n s i t ya c c e s sw e bs e r v e rm o d e l u n d e r t h ec o n d m o nt h a ts y n c h r o n i z a t i o ng r a n u l a r i t yo fm i c r o s e c o n dl e v e l t h e r ei sa tl e a s t3 0 o v e r h e a di sw a s t e d0 ns c h e d u h n ga n ds w i s h ，l a r g es c a l eo fc p ue f f e c t i v eu s er a t ei so b t a i n e d b ya p p l y i n gt h r e a dl i g h l w e l g h tw a y s c o n s e q u e n t ly i tw i l la f f o r dd e ws e t t l e m e n t c l u ef o r p e r f o r m a n c ei m p r o v e m e n tr e s e a r c ho na p p l i e a t i o n ss i m d a rt on e t w o r ki n f o r m a t i o ns e r v i c ew l t h m a s s i v ec o n c t l p f e n c yf i n e - g r a i n e do p e r a t i o n s b e s i d e s ，i no r d e rt o d oa p p l i c a t i o nc h a r a c t e r i s t i c s p r e p a r a t i o nf o rt h r e a dl i g h t w e i g h t r e s e a r c h ，t r a d i t i o n a lp a r a l l e la p p l i c a t i o n s ，s u c ha sl i n p a c ka n dn p b ，a t ea n a l y z e di nt h i st h e s i s a sa s s i s t a n ta n a l y s i s ，al i n p a c ke m u l a t i o nm o d e li sp r o g r a m m e dw h o s ee w o l p r e c i s i o ni s w i t h i n5 t h ed e t a i l e do v e r h e a dd a t ag o tt h r o u g ht h i sm o d e li n d i c a t et h a t , u s u a lh i g h p e r f o r m a n c ea p p l i c a t i o n sl i k el i n p a c k a i en o ts u i t a b l et 0l i g h tw e i g h t i ti ss u m m a r i z e di nt h e e n do ft h e w sf o r t h ef o l l o w i n gt h r e a dl i g h t w e i 曲tw o r kr e f e r e n c e k e y w o r d s ：s m p , t h r e a d ，l i g h t w e i g h t ，s c h e d u l i n g 。p a r a l l e ls i m u l a t o r , w e bs e r v e r , l i n p a c k ： h 、 0 图目录 图1 i 非对称多处理( 左图) 与对称多处理( 右图) 体系 图1 2s m t ( 左) 与c m p ( 右) 示意图 图1 3 目i 鸭自译( 左，s t r a n d ) 与编程模式( 右， 图1 4m c c 的可重构节点示意图 图1 5m mb l u e g e n e 系统研制资料一些节选 图2 1 单线程和多线程的进程模型 l i l y t a s k ) 的尝试6 图2 2 用户级和内核级多线程 图2 3 由用户线程库和内核混合支持的多线程示意图一 图2 4d o _ f o r k 流程示意 。8 1 2 图2 5 进程切换的上下文信息1 8 图3 1d s a g 主体框架示意 图3 2s a n d f o x 模拟器主要框架 2 1 2 2 图3 3 模拟器执行流程抽象2 3 图3 4 线程切换阻塞问题分析举例 图3 5 模拟器同步粒度统计 2 5 3 ( 1 图3 6 滤除管理类线程部分的模拟器同步粒度统计3 0 图3 72 c p u 机器上调度粒度优势的测试结果( 左：执行时间，右：加速比) 3 3 图3 84 c p u 机器上调度粒度优势的测试结果3 3 图3 9 三种执行方式平稳性比较 图3 1 0 模拟器改进测试结果。3 5 图4 1 基本客户服务器工作流程 图4 2 以c g i 为例的动态内容处理示意 图4 3w e b 服务器模型选择计数起始点和计数数目的测试结果 图4 aw e b 服务器模型简化演进。 图4 5 高密度访问服务器模拟测试结果 图4 6w e b 服务器最简化抽象与改写后的测试结果比较 图5 1a m d o p t e r o n 计算节点l i n p a c k 性能分析测试结果 图5 2 列向优先处理机阵列分布示意 图5 3 分块矩阵对应于处理机阵列的数据分白情况 图5 4 分块矩阵l u 分解过程示意。 图5 5n p b 程序代码计时部分主体结构 图6 1c m p 示意及各级访问延迟参照 4 0 4 5 4 5 4 6 4 7 4 9 5 0 5 0 5 l 5 6 5 8 表目录 表2 1 进程和线程的比照1 2 表2 2 进、线程创建开销参考值1 9 表2 3 上下文切换开销参考值1 9 表2 4 同步操作开销参考值。 表2 5m e m o r y 延迟及局部通信带宽参考 表3 1 简化模型下的测试结果 2 0 2 5 表3 2 轻权调度静态负载平衡的测试结果2 7 表3 3 轻权调度静态随机负载的测试结果2 8 表3 4 轻权调度动态负载平衡的测试结果2 8 表3 5 模拟器测试体系汇总3 3 表4 1w e b 服务器性能测试指标参考 表4 2 服务器执行过程中对主要资源的使用情况 表5 1h p l 测试体系汇总 表5 2 真实系统记录结果与估 贝9 值的对照 表5 3l i n p a c k 按块开销参照 表5 4 各n p b 程序测试倾向 4 0 4 2 5 2 5 2 5 3 5 5 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写过的研究成果。与我同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：3 长文力 日期：加 4 牙 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许论 文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、缩印 或其它复制手段保存该论文。 轹狮加雌轹兢p 双 托一事：0 l 高 第一章引言 峰值计算速度达万亿次、十力亿次的国产大规模机群系统深腾6 8 0 0 、曙光4 0 0 0 a 已相 继研制成功并投入使用，我国高性能计算的硬件平台又上了一个新台阶。以b l u e g e n e 为 首更庞大规模的研究，自主知识产权千力亿次m c c 系统的研制，但高性能计算机的实际 性能和应用水平却亟需提高。l i n p a c k 测试值可达峰值性能的5 0 一9 0 ，并不能代表一般 应用程序的实际性能。目前，b 程序能发挥出的系统效率仍然徘徊在1 0 左右。 计算机体系经历了u p 、m p 、m p p 、c l u s t e r 的沿革，如今又有了向细粒度演进的c - q v l p 、 s m t 的尝试【l 】。应用研究也从科学计算转向了对实际需求的更多关注。针对这些变化， 长久以来不乏进程到线程以及对线程更深入的探讨，然而对于大多数i o 较多的线程应用 ( 如w e b 服务) 来说，用户级线程的优势很难发挥，尤其在重负载及多处理机环境下对 一些细粒度并行应用，p t h r e a d 之类的标准线程更是难以应付。对这类应用而言，到底什 么样的执行粒度，什么样的并行度，什么样的调度方式才更有利于提高效率，更有利于 提高系统资源的有效利用率? 在国际细粒度并行研究如火如荼的大环境下，基于现有的 实验环境，我们从多处理机s m p 下线程的情况着手展开进一步的探讨。 1 。1 基于s m p 的并行研究现状 1 1 1 内核并行运行多进程、多线程存在的问题 从1 9 9 4 年开始，s m p ( s y m m e t r i cm u l t i p r o c e s s i n g ，对称多处理) 由于其体系结构的 发展相对成熟曲和卓越的性能价格比，受到了工业界用户的普遍欢迎，如s g ip o w e r c h a l l e n g e 和我国的曙光1 号。 画画画 图1 1 非对称多处理( 左圈) 与对称多处理( 右图) 体系 相对于非对称多处理，在对称多处理体系中，系统资源被系统中所有c p u 共享。所 坫- s m p 的琏程轻化相关1 0 f - f t 有的处珲机邵可以平等地访问共享存储器、i o 设备，同样地运行执行程序( 如操作系统 内核和i o 服务程序等) ，工作负载能够均匀地分6 a 到所有b ，用处理机之上，其与i # 对称 多处理的对照见图1 1 。正是对称，爿可能开拓较高的并行度。 然而解放非对称多处理中那些无权执行操作系统、无f o 操纵能力、只在主处理机的 监控之下执行用户代码的从处理机，实现多个处理机上的真j 下并行，还需要操作系统给 与相应的支持才行。 对称多处理使得任何进程( 线程) 都可以在任何处理机上运行，包括内核代码和应 用程序。基于多道程序设计概念设计出来的操作系统已不能适应新的结构的要求，多处 理机操作系统内核需要构造成多进程或多线程，允许部分内核并行执行。s m p 结构引发 了新的操作系统设计问题 3 4 5 6 1 ： 1 多任务并行支持。为了开发应用的并行性，将原来串行程序的可并行执行部分分 离开来，让它们可以占用不同的处理机同时运行。操作系统为了支持这种需求允 许多个处理机同时执行相同的内核代码，必须改造原来的进程概念，重新设计进 程管理模块，增加多线程支持，使内核例程是可重入的。 2 同步支持由于多个处理机执行的程序可能同时访问共享的地址空间或其他系统 资源，操作系统及用户必须利用硬件提供的同步手段来实现互斥访问。锁( 1 0 c k ) 是多处理机操作系统中一个通用的同步机制。 3 调度支持。每个处理机都要能够运行调度程序，对核心支持的多线程系统要支持 同时调度同一进程内的线程占用不同处理机，以加速进程的执行过程。 4 存储管理及c a c h e 一致性。由于处理机拥有自己的t l b ，多个处理机则可以有多个 t l b 。当页表项的映射地址变化时，操作系统要考虑到失效多个处理机中的n b ，对 于数据和指令c a c h e ，操作系统要保证在对内存f o 时c a c h e 与内存的一致性要求。 5 可靠性和容错当处理机失败时，操作系统应该提供故障弱化能力调度程序和 操作系统的其他部分必须知道处理机的损失，并且因此重新组织管理表。 由于本文着重于性能提高方面的讨论，更多考虑应用性能、系统资源的有效利用率， 所以进一步的探讨工作主要围绕前三个方面展开 1 1 2 对上述问题已有的解决思路及方法 1 从多进程到多线程，从用户级线程到核心级线程再到混合实现 早年并行程序设计停留在相关性很弱的并行任务上，用户可以利用多进程来实现并 行任务的执行，并行程序设计只能获得处理机与外设的并行执行。随着多处理机的出现 以及开发多进程并行程序通信和同步上的困难与性能因素，多线程概念被提出来。这样， 进程可以拥有多个执行流程，并行性开发可以延伸到进程内多线程并行。 为了支持用户进程内多线程，有两种典型的实现方法，即线程库支持的用户级线程 实现和核心支持的核心级线程实现。 线程库实现的多线程分时地在进程中运行，由线程库调度器负责线程的调度与切换， 2 、 _ 第一争：i 高 而对内核是透明的。如r o a c h 操作系统的c - t h r e a d s 库和p o s i x 标准定义实现的p t h r e a d s 库。 这些库提供了处理线程的所有功能，无需操作系统特别支持，由于对线稃的所有操作都 不涉及内核，因此，用户级线程的创建、结束、调度、现场保护与切换开销非常少。用 户可以根据应用的并行度申请足够多的线程而无需考虑系统资源限制。但是，它不能做 到进程内线程在多处理机上真正并行运行，操作系统调用进程占用处理机运行，它无法 感知进程内多线程的存在，因而无法让用户进程在多个处理机上同时运行；如果用户级 线程发系统调用或中断进入操作系统，则其所在进程被阻塞，线程库无法知道刚运行的 线程被阻塞，因此也无法转到其他线程运行。这种情形下有改进的尝试，让可能引起阻 塞的系统调用全部经过线程库转发，使线程库能够根据情况调度其他线程运行。 核心支持线程实现是在多处理系统出现后，由操作系统支持实现的线程。线程库支 持的多线程并不能够同时在多个处理机上运行。要做到多线程能够同时在多个处理机上 运行，需要操作系统见到进程内多线程的存在，并分配处理机给这些线程运行。核心级 线程可以支持进程内多线程在多处理机上真正并行执行，因为核心处理机调度程序是以 线程为单位的，调度程序可以选定同一进程的线程同时占用处理机。内核线程不用和进 程联系起来，它可以通过内核执行特定的函数来创建、运行和释放。这样，内核就不用 在内核线程切换时重新映射地址空间。因此，内核线程的上下文切换要比一个进程的上 下文切换花费少得多。而且它不会出现用户级线程方式下，线程在内核被阻塞但线程库 调度器一无所知的情形，由于线程调度在核内进行，如果线程因等事件阻塞，核心即可 将处理机切换到其他线程上运行。但由于管理由内核程序进行，需要用户态到核心态的 切换，核心级线程比用户级线程开销要大一些。另外，核心级线程占用系统空间及资源， 并不适合用户根据其任务的并行度来创建相应多的线程。 鉴于二者各有优缺点，在现代操作系统中，往往结合这两种实现方法，以满足用户 方便地进行多任务程序设计，且使多任务高效的占用多处理机运行。用户级线程和核心 级多线程的结合，使得可以有一种最有效、最适合的方法开发应用程序并行性。一般来 说，核心级线程个数与系统处理机个数相当为宜，太多的话占用系统资源太多，太少则 不能让进程内多任务真正在多处理机上最大程度的并行。 2 从巨型锁到细粒度锁，从单一锁到多样锁 在多处理机中，由于内核所具有的最基本保护方式非抢占特性不复存在，两个进( 线) 程会在不同处理机上同时处于内核态，甚至并发地执行同一函数。因此，任一时刻当内 核访问某一全局数据结构时，必须对其加锁以防其他处理机访问。这种加锁机制必须是 多处理机安全的。若有不同处理机上运行的两个进程同时希望对某一对象加锁，只能有 个成功地获取锁。 由于有多个处理机处理中断，对中断的保护更加复杂通常阻塞每个处理机上的中 断不是很好的方法，这可能会极大地降低性能。显然多处理机需要更复杂的同步机制。 多处理机的互斥不能像单处理机那样通过简单的屏蔽中断或提高优先级的办法阻止 进程调度来实现l i 缶界区的互斥执行，而是要用更为复杂的软件方法或直接采用硬件提供 3 缺1 - s m p 的线程轷化拥关，e 的、更为方便和高效的手段来实现多处理机系统的同步与互斥。 这咀t 要涉及的问题包括：加锁的策略、锁类型的选择，加锁位霄的选择、死锁的 预防、性能统计分析改进工具。加锁的策略可根据多机硬件特征( c p u 的个数) 与应用 领域( 数据处理、并行计算、实时处理等) 进行粗粒度与细粒度加锁的选择，也可以对 使用频繁的子系统进行细粒度加锁，使用频度小的子系统进行粗粒度的加锁等。锁类型 有简单的s p i n - l o c k 【”、信号灯机制、r e a d - w r i t e 锁等，涉及到的问题包括如何高效地在不 同的硬件中进行实现，在不同的加锁位置选择哪一种锁。加锁位置的选择主要针对共享 的数据结构来进行。死锁问题的解决方法包括完全预防死锁的发生以及死锁发生时如何 解锁两种方案。在系统进行初步的并行化处理后，还需要通过一些专门的性能调试工具 进行并行化后性能的调整，以期达到最好的效果。 采用巨型上锁的最简单的内核实现就是只使用一个锁的内核。在这种极端情况下， 锁保护着全部内核数据，防止一个以上的进程同时以内核态执行，这样所有的内核活动 就被限制在一个处理机上。对这种巨型上锁技术进行扩展，让内核中每个子系统使用独 立的锁，可以通过增加更多的锁带来一些额外的并行性。 进一步，可以用自旋锁保护内核的许多全局数据结构和列表等进行细粒度上锁，达 到利用不同处理机提高并行内核活动数量的目的。 逐渐地，伴随不同的需求又产生了各种不同的锁：读写锁( 专为i o 所设计的特殊锁) 、 障碍锁( 为并行程序实现同步而设计的一种同步机制) 、带计数器的信号灯机制( 主要通 过一个计数器来标识锁的状态) 等等。 继m i c h e lr a y n a l 【8 】之后。【9 】对1 9 8 6 年至2 0 0 1 年共享存储系统互斥机制的主要研究 趋势进行了综述。 3 从负载共享到多级动态调度 要在资源利用率、用户作业周转时间、系统吞吐率等诸多方面达到最佳，是多处理 机系统线程调度必须面对的问题。 在许多多处理机线程调度【i 伽和处理机分配问题的研究中，以下4 个方面在现代操作 系统设计中影响很大： 负载共享：进程不被指定到任何特别的处理机，系统维护一个全局的就绪线程队 列，任何处理机在空闲时都可以到该队列上去获得一个就绪线程运行。此调度策 略对系统吞吐率及资源利用率无疑是很有帮助的，但它也存在以下几方面缺点： 由于各用户的所有线程共享同一个就绪队列，不能很好组织相关线程同时运行； 不能保证处理机最小限度地切换线程或尽可能少的在不同进程的线程间切换。 【l l 】分析了先来先服务( f c f s ) 、最少线程数优先和有剥夺的最少线程数优先三 种负载分配方案。 组调度：将一组相关的线程同时调度到一组处理机上运行。同步阻塞、进程切换 和调度开销都可能会减少。u n i x 将某轻权进程l w p ( 核心级线程) 与处理 机捆绑到一起。如果将同一进程的不同l w p 捆绑到不同的处理机上，则可以保 4 第一节：0 i 南 证它们的并行执行。【1 2 价绍了曙光一号操作系统s n i x 上组调度策略的实现。 独占处理机调度：这与负载共享恰恰相反，将一组处理机分配给指定并行程序中 的线程运行，等到并行程序运行结束，处理机才被系统收回，以利系统分配给其 他并行程序。它是组调度的一种特殊形式，运行过程中完全没有进程或线程切换。 但如果并行作业的执行单位数大于系统内处理机个数，各并行的执行单位无论如 何都不可能同时占用处理机运行，这样势必引起系统处理机频繁切换的开销，各 并行执行单位之间同步等待时间的增加，并行应用的加速比不但不会因并发读提 高而增加，反而因系统开销的增加而降低。 多级动态调度f 1 3 l ：允许并行程序中的线程数目在运行过程中动态改变，利用多 级线程支持实现多级调度线程库和操作系统都利用函数接口和系统调用给上层 用户动态地创建线程和结束线程，这样资源可以适时的被使用而无需预先分配。 但这种分级的动态调度方式下，用户级线程库调度器与内核的线程调度器之间没 有信息交换。因此会出现一些影响整体并行作业运行及系统性能的问题。这有待 于进一步研究。 1 2 国际前沿细粒度并行处理技术跟踪 多处理机中的并行性存在于不同层次上，其充分开发须从算法、语言、编译、操作 系统、用户库和体系等各方面来统筹协调。这里我们分别进行了体系结构、编译技术、 编程模式和用户级线程库层次的细粒度技术追踪。 体系结构：在体系结构上一个明显的趋势就是在线程级提供高度并发执行环境。见图 1 2 。i n t e l 、m m 的同时多线程( 即s m t , s i m u l t a n e o u sm u l t t t h r e a d i n g ) 处理机通过复 制程序计数器p c 和寄存器等资源，使一个物理处理机提供给操作系统多个逻辑处理 机，允许有多于一个的指令流流入，使应用可以在每个逻辑处理机上执行独立的任务。 普遍认为是超标量的自然扩展。但限于技术，目前线程数一般不超过4 个；c m p c b p c h i pm u l t i p r o c e s s i n g ) 是在每个芯片上集成多个c p u ，一般也只有4 个，预期研制的 m c c 就是类似的结构。这种将s m p 思想微缩到芯片上的实现，大大减少了片上处理 机间的通信开销，提供多个物理执行环境。参考资料【1 4 】显示，从工艺、性能及市场 趋势等方面看c m p 较s m t 更具前景。 编译技术：d e l a w a r e 大学在编译一级提出了s t r a n d f i b e r ，见图1 3 ，s t r a n d 是一个单 入口单出口的原子指令调度单位，其中所有指令都无条件执行。这种根据数据依赖划 分更细粒度的编译技术基本得到认可，被c r a y 的c a s c a d e 计划采用。根据文献中数 据，其在编译器上处理相关，将调度单位细化到平均1 0 几条指令的级别。我们考虑 做粒度优势的探讨 编程模式：常用的程序级并行方式有进程、线程和l o o p 。进程的开销较大需要显 式通信实现数据共享：线程缺乏逻辑语义，通常需要操作系统的支持，对程序员而言 堆t - s m p 的线程轻化相关i 卅，z 难以控制：l o o p 只对s m p 系统适用，执行效率一般不高。为此，l i l y t a s k 系统1 1 5 1 6 l 采用任务 意度的并行，试图在比线程更小的调度单位基础上编程，仞衷在于、求编程 易用性与性能的挈合点。见图1 3 ，l i l y t a s k 以任务作为问题的抽象描述，任务包括数 据、操作和结果。而任务又必须在组内运行，所以必须为其定义顺序，属典犁的数据 流思想的继承。虽然声称：l i l y t a s k 系统深度挖掘程序的并行性；任务粒度由程序员 控制，可以实现粗粒度并行和细粒度并行；任务逻辑上和实际语义相对应，便于理解 和修改：不需要操作系统的支持，可控性强，但目前资料显示较m p i 模式并未显出 性能上的优势，按其开销情况目前仅适用于c l u s t e r 级剐。 图1 2s m t ( 左) 与c m p ( 右) 示意图 s 1 ：i f ( a b ) ： s 2 ：f = r + w ： ： e l s e： s 3 ：r = f w ： ： ：s t r a n d - l ：! - s i ： c o n d s y n c ( ( a b ) 2 3 ) ； e n d _ s t r a n d ( ) ； ： ：s t r a r i d _ 2 ： ! 。s 2 ：r = r4 - w ： ： e n d _ s t r a n d ( ) ； ： q t r a n n ： l i l y c l a s sn a m e o t t a s k c l a s si l i l y md a t a t y p ev a n a b l e l n n a m e l ； l i l y o u td a t a t y p ev a n a b l e o u t n a m e l ； ：l i l y f l l n cf u n c t i o n n a m eo ： ： j l l l y 嘲一“8 概m8 嚯船盥d e s 亿l c i 胁) 图1 3 目前编译( 左- s t r a n d ) 与编程模式( 右，l i l y t a s k ) 的尝试 线程库1 7 1 ： 用户级线程在性能上明显优于核心级线程，为满足人们对应用性能的追求，对线程 库改进的尝试一直在进行： 1 ) 用户级线程可能阻塞在缺页异常和i o 请求上： 2 ) 于是，s c h e d u l e r a c t i v a t i o n s 引入内核通知机制； 3 ) f i l a m e n t s 1 9 l g , k s t a t e l e s s 线程，线程没有私有的栈。在一个处理机上一个核心级线 程将在一个栈上顺序执行所有f i l a m e n t s 。但它是为并行科学计算应用设计的。仅有迭 代和f o r k j o i n 两类没有标准的锁之类，编程性不好； 6 第一争：0 i 高 4 ) 为了进一步降低开销，一些线程库使用专门的编译器，预处理或后期处理程序。 l a z y t a s k c r e a t i o n ( l t c ) 绑定编译器，把r u n t o - c o m p l e t i o n 的粒度单位以过程调用的方 式处理：s t a c k t h m a d s m p 1 j 启用了后期处理程序； 5 ) c f l k 使用续体c o n t i n u a t i o n s 避免同步。 其实，每个线程库都在一定条件有其独特的优势，但真正能解决实际问题、有实际 作用的还不多。c i l k 高度可扩展，在相对粗的粒度下有更好的性能。f i l a m e n t s 在趋于复 杂、且限制因素多的模型条件下，对迭代式的应用以及f o r k - j o i n 式的程序发挥效能。 s t a c k t h r e a d s m p 相对简单易用，把线程的开销减少到了过程调用级别，支持不受限制的 线程模型，然而，它对细粒度并行却很敏感，有严重的潜在开销。l t c 有近乎过程调用 的效率，极小化了同步开销，依然保持对全线程模型的支持，可是它需要很强的编译器 支持总的来说，线程库的好坏很大程度上依赖于应用本身的特点和程序员的编程风格。 另外，面向对象的持久分布式操作系统r a m b l e r t 加1 中对事件线程做了尝试。但较基于 事件的方法而言，我们始终相信线程具有更清晰的静态控制流1 2 1 1 。 综上，各层次各角度的不同级别的线程轻化在不同程度的进行。线程轻化成为一种 趋势。从我自身而言，将在把握现有线程的基础上，从典型应用本身特性入手，探讨合 适的程序粒度，降低调度切换开销，从而提高应用并行度及c p u 有效利用率。待总结出 一定规律后才考虑以合适的形式体现，比如将改进加入p t h r e a d 线程库或编译器。 1 3 细粒度并行研究的意义 约5 0 年的并行计算历程中，从处理机内部指令集的并行到集群尺度上的并行，都在 现有计算能力的基础上，极大的开发了计算的潜能。同时，人们对计算能力的追求也从 来没有停止过。随着线程使用的日益广泛，体系结构、编译技术、编程模型、线程库等 方面都在朝向更高并行度、更细并行粒度方向发展。总的来说，线程轻化是一种趋势， 有m c c 的现实需求，也有b l u e g e n e 的推动因素。其意义