（计算机科学与技术专业论文）并行分布操作系统共享存储管理及其优化技术的研究.pdf

国防科学技术大学研究生院学位论文 摘要 本文研究了并行分布操作系统中共享存储管理及其优化技术，主要包括共享存储 抽象层的设计与实现、线程一致性模型以及基于即态访问信息的动态页迁移技术等。 经过对并行分布操作系统面l | 缶的机遇和挑战以及相关理论和具体实现技术的深入剖 析，本文着重对共享存储管理技术进行了研究。f 针对不n 体系结构所呈现出的不n 存储 共享的性质，我们提出了一个共享存储抽象层的概念，用以统一s m p 等系统中的真共 享、c c - n u m a 等系统中由硬件支持的分布共享以及工作站机群系统中的虚共享等情 况，并在此基础上探讨和设计了并行分布操作系统的逻辑结构框架。 共享存储管理中最关键的问题之一就是如何维护存储一致性的问题。针对现有的存 储一致性模型大都存在可扩展性不足和不适于在操作系统级实现的缺点，我们提出了一 个基于同步点的存储一致性模型及实现的框架s 3 c 框架，通过它来更好的研究和比 较不同的存储一致性模型及其优化的实现方式，为设计和实现新的存储一致性模型提供 指导，以弥补现有存储一致性模型存在的不足。在该框架中，我们通过定义三个同步点 和一个一致性维护点的概念，对不同存储一致性模型中正确的存储访问事件顺序进行了 描述。 在s 3 c 框架的基础上，我们提出了一种新的以操作系统为中心的存储一致性模型一 一线程一致性模型。该模型通过程序执行过程中线程状态的变化来观察和限制存储访问 事件的正确顺序，因而有机的将操作系统存储管理和执行体管理的功能结合在一起，更 适合于在操作系统级进行实现。同时，线程一致性模型能够充分利用多线程系统中计算 与通信重叠从而隐藏通信延迟的优势，特别适合于多线程操作系统内核和多线程c p u 。 此外，我们通过对线程一致性模型条件的进一步放松，提出了模型的懒惰实现方式，从 而减小系统维护一致性的消息传递开销，提高了系统的可扩展性。 我们针对共享存储管理的优化技术展开了探讨。高效的页迁移策略能够动态改善数 据局部性，提高存储系统的性能。因此，我们重点针对页迁移技术进行了研究。现有的 页迁移策略大都需要特殊的硬件支持( 如访问次数计数器) ，因而硬件开销大且软件模 块的可移植性不够好。为了提高策略的通用性，我们设计了一种无需特殊硬件支持的基 于即态访问信息的动态页迁移策略，在策略的信息收集阶段采用直接从c a c h e 中获取的 即态访问信息来代替传统策略使用的历史访问信息，在此基础上形成页面动态复制或迁 移的策略，从而消除了硬件开销。测试结果表明该策略能接近甚至达到传统页迁移策略 的优化效果。川+ ， 关键词：并行分布操作系统，单系统映像，虚共享，共享存储抽象层，存储一致性模型， 线程一致性模型，页迁移，即态访问信息 第1 i i 页 国防科学技术大学研究生院学位论文 a b s t r a c t i nt h i s t h e s i s ，w es t u d yt h e t e c h n o l o g i e s o fs h a r e d m e m o r y m a n a g e m e n ta n d i t s o p t i m i z a t i o ni np a r a l l e la n dd i s t r i b u t e do p e r a t i n gs y s t e m s o u rp r i m a r yw o r kf o c u s e so nt h e d e s i g na n di m p l e m e n t a t i o n so fs h a r e d - m e m o r ya b s t r a c tl a y e r , t h r e a dc o n s i s t e n c ym o d e l a n di n s t a n t a n e o u si n f o r m a t i o n b a s e dd y n a m i c p a g em i g r a t i o np o l i c y f i r s to f a l l ，a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fm e m o r ys h a r i n gi nd i f f e r e n ta r c h i t e c t u r e s ， w eb r i n gf o r w a r dt h e c o n c e p to fs h a r e d m e m o r ya b s t r a c tl a y e r w i t hs h a r e d - m e m o r y a b s t r a c tl a y e r , w ea r ea b l et ou n i t es e v e r a lm e m o r ys h a r i n gc a s e si n c l u d i n gt r u es h a r i n gi n s m p , h a r d w a r e s u p p o r t e dd i s t r i b u t e ds h a r i n gi nc c n u m aa n dv i r t u a ls h a r i n gi nc l u s t e r s b a s e do nt h i s ，w ed i s c u s sa n dd e s i g nt h e l o g i c a l f r a m w o r ko fp a r a l l e la n dd i s t r i b u t e d o p e r a t i n gs y s t e m s o n eo ft h ek e yp r o b l e m si ns h a r e d m e m o r ym a n a g e m e n ti sh o wt om a i n t a i nm e m e o r y c o n s i s t e n c y b e t w e e nm u l t i p r o c e s s o r s m o s to fc u r r e n t m e m o r yc o n s i s t e n c ym o d e l s a r e c o n f r o n t e dw i t ht h ed e f i c i e n c yo f s c a l a b i l i t ya n dd i f f i c u l tt oi m p l e m e n ti no p e r a t i n gs y s t e m s a i m i n g a t t h i s ，w ep r o p o s e s c f r a m e w o r k ，w h i c hi s an e wf r a m e w o r ko fm e m o r y c o n s i s t e n c ym o d e l sa n dt h e i ri m p l e m e n t a t i o n sf o u n d e do ns y n c h r o n i z a t i o np o i n t s i n $ 3 c f r a m e w o r k ，w ed e f i n et h r e es y n c h r o n i z a t i o np o i n t sa n do n ec o n s i s t e n c ym a i n t a i n i n gp o i n t w h i c ha r eu s e dt o g e t h e rt od e s c r i b et h ec o r r e c te v e n to r d e ri nd i f f e r e n tm o d e l s v i a $ 3 c f r a m e w o r k ，w ec a nd i v ei n t oa n dc o m p a r ed i f f e r e n tm e m o r yc o n s i s t e n c ym o d e l sa n dt h e i r i m p l e m e n t a t i o n s s oa st op r o v i d ei n s t r u c t i o n so n d e s i g n i n g a n d i m p l e m e n t i n g n e wm o d e l s w i t ht h eh e l po fs 3 cf r a m e w o r k ，w ep r o p o s ean e w o p e r a t i n gs y s t e m - c e n t r i cm e m o r y c o n s i s t e n c ym o d e l ，t h r e a dc o n s i s t e n c ym o d e l i nt h i sm o d e l ，m e m o r ya c c e s se v e n to r d e ri s o b s e r v e da n dr e s t r i c t e d b yt h et r a n s f o r m a t i o no ft h r e a d s s t a t e sd u r i n gt h e e x e c u t i o no f p r o g r a m s i t i s r e l a t i v e l ya p p r o p r i a t et oi m p l e m e n tt h i s m o d e li n o p e r a t i n gs y s t m ss i n c e m e m o r y a n d p r o c e s s e s t h r e a d sm a n a g e m e n t c o u l db ec o m b i n e d o r g a n i c a l l y a tt h es a r n et i m e ， t h r e a dc o n s i s t e n c ym o d e li sa b l et ou t i l i z et h ea d v a n t a g eo fm u l t i t h r e a d e da r c h i t e c t u r et o o v e r l a pc o m m u n i c a t i o nw i mc o m p u t i n g s oa st oh i d ec o m m u n i c a t i o n l a t e n c y a sar e s u l t t h i s m o d e li s e s p e c i a l l ys u i t a b l ef o rm u l f i t h r e a d e d k e r n e lo p e r a t i n gs y s t e m sa n dm u l t i t h r e a d e d c p u s f u r t h e r m o r e ，t h r o u g ht h er e l a x a t i o no fc o n d i t i o n so f t h r e a dc o n s i s t e n c ym o d e l ，w e p r o p o s es o m el a z yi m p l e m e n t a t i o n s ，t r y i n g t or e d u c et h eo v e r h e a di nm a i n t a i n i n g c o n s i s t e n c y s oa st oi m p r o v e s y s t e mp e r f o r m a n c e a i m i n g a to p t i m i z a t i o nt e c h n o l o g i e so fs h a r e d m e m o r ym a n a g e m e n t ，w ei n v e s t i g a t eo n d a t al o c a l i t y o p t i m i z a t i o np o l i c i e s s i n c ep a g em i g r a t i o ni s a ne f f i c i e n tw a yt o i m p r o v e l o c a l i t y , w es t r e s so ni t c u r r e n tr e p r e s e n t a t i v ep o l i c i e sa r ei nn e e do fs p e c i a lh a r d w a r et o r e c o r dh i s t o r yp a g ea c c e s si n f o r m a t i o n ，r e s u l t e di nt h e i rp o o rg e n e r a l i t y t oo v e r c o m et h i s d e f i c i e n c y ，w ep r o p o s ea ni n s t a n t a n e o u si n f o r m a t i o n - b a s e dd y n a m i cp a g em i g r a t i o np o l i c y , w h i c hd o e s n tn e e da n ys u p p o r to fh a r d w a r e i nt h i sp o l i c y , w eu s es o m ei n s t a n t a n e o u s 第1 v 页 国防科学技术大学研究生院学位论文 i n f o r m a t i o nd i r e c t l yo b t a i n e df r o mc a c h e st os u b s t i t u t et r a d i t i o n a l h i s t o r yi n f o r m a t i o n t h e r e s u l t so fo u re x p e r i m e n ts h o wt h a tt h i s p o l i c yc o u l da p p r o a c ht h ee f f e c to ft r a d i t i o n a l p o l i c i e s k e y w o r d s ：p a r a l l e la n dd i s t r i b u t e do p e r a t i n gs y s t e m ，s i n g l es y s t e mi m a g e ，s h a r e d v i r t u a l m e m o r y , s h a r e d m e m o r ya b s t r a c tl a y e r , m e m o r yc o n s i s t e n c y m o d e l ，t h r e a d c o n s i s t e n c ym o d e l ，p a g em i g r a t i o n ，i n s t a n t a n e o u s i n f o r m a t i o n 第v 页 国防科学技术大学研究生院学位论文 第一章导论 1 1 课题背景 回顾从1 9 4 6 年世界上第一台计算机e n i a c 诞生至今五十余年的历史，不难发现， 计算机技术发展的根本动力主要来自于各类科学技术和各种应用领域对计算机性能永 无止境的需求和生产的实际需要。尽管处理器、存储器等计算机中基本部件的性能随着 超大规模集成电路等技术的不断发展已经得到了极大的改善，但是由于受到主频、集成 电路、组装工艺、散热等方面的限制，串行计算机的处理能力远未达到许多科学计算、 大型事务处理以及其它大型计算和处理的要求。 一方面，科学计算作为和理论研究、实验并列的三大科学研究手段之一，对计算机 的计算能力提出了巨大的、不断增长的需求。1 9 9 2 年，美国高性能计算和通信计划委员 会( h i g h p e r f o r m a n c ec o m p u t i n ga n dc o m m u n i c a t i o n ，h p c c ) 提出了科学与工程计算领 域里具有深远影响的一些重大挑战性课题【l 】，这些课题大致可分为如下几类： 量子化学、统计力学和相对论物理学 宇宙学和天体物理学 计算流体动力学和湍流学 新材料和超导 生物学、药物学、遗传工程、酶活性和细胞模型 医学、人类器官和骨骼模型 全球气象和环境模型等 所有上述课题全都具有极大的数据量和计算量，因而无一不对计算机的处理能力提 出了非常高的要求，而这些要求是串行计算机无法达到的。同时，这些问题本身都蕴含 着大量的并发特征，非常适合于进行并行计算，从而推动了并行计算机体系结构的产生 和不断发展。 另一方面，在商业应用领域，随着信息化进程的不断深入，大型数据库系统得到了 广泛的应用，网络信息服务业以惊人的速度扩展，电子商务也在日益普及。这些新的应 用领域对计算能力的需求虽然不及科学计算，但是它们也需要大规模的数据存储系统以 及大规模的计算能力，并且本质上具有很好的并行性。因此，它们也从市场的角度对并 行计算提出了新的要求。 此外，包括多媒体应用在内的其它一些大型计算和处理方面的应用也需要计算机提 供并行处理能力的支持。 在这种背景下，并行计算机和并行计算技术的研究成为一个当务之急的课题，成为 一个对科学技术发展和社会进步有重大影响的课题。所谓并行计算机就是由一组处理单 第1 页 国防科学技术大学研究生院学位论文 元组成的计算机，这组处理单元通过相互之间的通信与协作，以更快的速度来共同完成 一项大规模的计算任务。 1 1 1 并行计算机体系结构 并行计算机体系结构是并行计算技术的基础。在过去的十余年中，随着c p u 性能的 提高以及通信技术的飞速发展，并行计算机的体系结构发展非常迅速。 按照f l y n n 分类法，计算机可以划分为四种基本类型，即s i s d 、m i s d 、s i m d 和 m i m d 。目前，绝大多数并行计算机从体系结构的角度来看都属于多指令流多数据流计 算机，即m i m d ( m u l t i p l e i n s t r u c t i o nm u l t i p l ed a t a ) 计算机，其中，每个处理单元都是 根据不同的控制流程来执行不同的操作，处理不同的数据集合。 根据并行计算机系统中结点与存储器的组织情况，m i m d 机器又可划分为共享存储 的多处理器系统和非共享存储的多计算机系统【2 】，如图1 1 所示。它们的区别就在于任 何一个结点上运行的进程是否能够直接访问整个系统中的存储单元，无论它是本地地址 还是远程地址。 m 蹦d 图1 1 并行计算机系统分类 如上图所示，尽管目前出现的并行计算机系统在规模和拓扑结构上各具特色，但它 们基本上都可以归入以下几类【2 j ： 向量并行处理机p v p ，如c r a y y m p 9 0 、n e cs x 3 和v u j i t s u v p 2 0 0 0 等； 对称多处理器系统s m p ，如i n t e ls h v ，s u r f f i r e ，d e c8 4 0 0 ，s g ip o w e r c h a l l e n g e “、i b mr s 6 0 0 0 【4 】等； 大规模并行处理系统m p p ，如i n t e lp a r a g o n 等； c a c h e 一致性非一致存储访问系统c c 艄7 m a ，如s g io r i g i n2 0 0 0 3 0 0 0 5 , 6 1 ， 第2 页 一一 叽一 哪 一一 一 时 一 一 一一一一 一 l 恶 ： 吲 黼 饥 肿 一吖 塞一 = 国防科学技术大学研究生院学位论文 s t a n f o r dd a s h f l a s h v , s 1 等； 非c a c h e 一致性非一致存储访问系统n c c - n u m a ，如c m yt 3 e t 9 ：o l 等； 工作站机群系统c l u s t e r t l l , 1 2 ，如b e o w u l f 1 3 , 1 4 ，i b ms p 2 1 5 】等。 其中，p v p 承袭了早期向量机的特点，技术成熟，在科学计算方面效率较高，但是 通用性不是很好，工艺复杂，性价比较低。s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) 系统作为 一种比较成熟的共享存储体系结构，具有全局一致的存储访问延迟，目前已经能够很好 的支持科学计算、大型数据库管理以及w e b 服务器等多种应用，但由于受到其共享主存 访问带宽的限制，可扩展性受限，一般规模比较小。m p p 系统是一种s h a r e n o t h i n g 的大 型并行处理系统，各个结点有自己的处理器和存储器，结点间通过高速互连网络连接， 其结点数目可以扩展到数干个以上，但是由于不具有共享存储的特性，进程间主要通过 消息传递来进行通信，因而在可编程性和负载平衡方面存在不足。c c - n u m a 和 n c c - n u m a 系统中，分布在各个结点上的存储器组成了全局存储空间的视图。二者的 区别在于：前者由硬件实现了各处理器间的c a c h e 一致性，而后者没有提供这一功能。 工作站机群系统则是近年来发展最为迅速的一种体系结构，它由商用工作站或p c 经过 普通网络或专用互连开关连接而成，具有较高的性价比。在2 0 0 1 年1 1 月公布的最新 t o p5 0 0 排名【l6 j 中，已经占据了1 8 8 个席位( 包括c l u s t e r 和c o n s t e l l a t i o n ，其中， c o n s t e l l a t i o n 是指每个结点的处理器数目超过1 6 个) ，仅次于传统的m p p 系统，具有极 大的发展潜力7 1 。 并行计算机两个主要研究的问题是可扩展性与可编程性，它们既共生而又相互矛盾。 可扩展性是并行计算机最大的优势，可以简单的理解为在确定的应用背景下，计算机系 统的性能要随处理机数的增加而线性增长，主要包括规模可扩展、时间可扩展和问题可 扩展等几个方面。可编程性则体现了开发应用程序的方便程度。 和并行计算机系统共享与分布式两种存储结构相对应，操作系统进程间的通信 ( i p c ) 也有两种不同的机制：共享变量和消息传递。机器结构和操作系统的这些区别 又影响到支撑软件和应用软件的编程模式。在共享存储多处理器系统中，程序设计仍以 传统的高级语言为基础，系统增加并行语言成分或提供自动并行识别。而在分布存储多 计算机系统中，必须建立另一种编程环境( 如p v m t l 8 - 2 0 、m p i l 2 1 , 2 2 1 等) ，在程序中显式 地进行消息的发送和接收，这不仅导致应用软件编写困难，还给用户增加了很多负担。 总的来说，前者可编程性好，不易扩展；而后者可扩展性好，不易编程。 为了融合共享存储多处理器系统与分布存储多计算机系统各自的优势，人们提出了 分布式共享存储体系结构( d i s t r i b u t e ds h a r e d m e m o r y ，简称d s m l 2 3 , 2 4 1 ) 的概念。d s m 通过硬件或软件的方式在物理分布的存储空间基础上提供了逻辑上共享的全局存储空 间，一方面，它的存储空间在物理上是分布的，各结点间采用可扩展的拓扑结构进行互 连，因而具有较好的可扩展性；另一方面，由于d s m 系统对用户提供了逻辑上共享的 地址空间，使得在这种平台上可以比较容易地进行程序开发，基于共享存储的应用程序 也能够很容易的移植到d s m 系统平台上。因此，分布式共享存储体系结构已经成为目 第3 页 国防科学技术大学研究生院学位论文 前并行计算机领域的主要发展方向之一。 一个d s m 系统可以通过硬件直接支持全局共享存储的方式来实现，如 c c n u m a 【5 8 】，n c c - n u m a 和c o m a 2 5 , 2 6 1 等，也可以通过软件的方式来统一分布在各 个结点的存储空间，如工作站集群环境下的虚共享系到2 7 3 0 1 ( s h a r e dv i r t u a lm e m o r v ， 简称s v m ) 。 并行计算机系统另外值得注意的一个发展趋势是多种体系结构相互融合，相互渗透。 相互融合的趋势主要表现在，随着处理器技术和网络互连技术的高速发展，各种体系结 构之间的界限越来越模糊。例如s m p 系统所采用的r i s c 芯片的发展目标之一就是增加 向量处理的功能，若能如此，s m p 与p v p 之间的界限就比较模糊了。另一个例子是随 着通用网络技术性能的提高，m p p 系统和工作站机群系统之间的界限也越来越模糊，它 们在耦合度方面的区别越来越不明显。相互渗透的趋势主要表现在，高性能计算机体系 结构有向混合式的结构发展的倾向，如在机群系统中已经出现使用s m p 系统或者 c c n u m a 系统作为结点的原型系统，即c l u m p ( c l u s t e ro f s m p ) 或者c n u m a ( c 1 u s t e r o fn u m a ) 结构。在这种混合式体系结构中，各结点本身具有强大的并行处理能力和易 编程性；就整个系统而言，它又具有较好的可扩展性和可靠性。 1 1 2 并行分布操作系统 并行系统软件是并行计算机提高性能和增强功能的关键。它主要包括并行操作系统、 并行程序语言及编译系统、程序开发环境及工具等，其中并行操作系统是最核心的部分。 操作系统既是一种虚拟机，向用户隐藏底层体系结构的细节，提供给用户基本的方 便的接口：同时，它又是系统中各种资源的管理器，负责管理和协调处理器、主存、i o 、 网络等资源的分配和使用。随着并行和分布体系结构的出现和日益发展，相应操作系统 的研究也越来越重要，如何尽可能的发挥多处理器系统的优势，同时仍然保持用户使用 的方便性，给现代操作系统的研究提出了新的机遇和挑战。 目前，操作系统的内核个主要的发展方向是多线程内核结构，按照用户级多线程 库和多线程操作系统内核这种二级线程的机制来组织整个系统，允许单个内核地址空间 支持多线程的服务进程，从而提高系统的并行性和效率。 总的来说，当前主流高性能并行计算机厂商所采用的操作系统仍然是基于u n i x 的分 布式并行操作系统。但由于用户需求和机器结构的不同，这些操作系统在实现上也存在 着结构上的巨大差异。其中几种比较有代表性的操作系统包括： s g ic e l l u l a ri r i x 6 5 【3 l 】这是一种蜂窝结构的新一代操作系统，其特点是将分布 与共享相结合，支持s m p 和c c & 兀d m a 体系结构，具有良好的可扩展性。目前 已在5 1 2 个c p u 的系统上实现了单一系统映像，有较强的可靠性、可用性和可 维护性，与w i n d o w $ n t 有良好的互操作性。 i b m a i x 4 3 p s s p 3 2 l这是一种典型的集中式机群服务器结构的操作系统。 a 装在系统的每个结点上，在它的上一层使用了机群管理软件p s s p ( 并行系 第4 页 国防科学技术大学研究生院学位论文 统支持程序) ，相当于整个机群的操作系统。其特点是系统开发量少，用户界面 友好。 i n t e l t o s c o u g a r 【j j lt o s 是一种基于o s f 的分布式u n i x 系统，用于管理系统、 服务和i o 节点的运行，可提供系统单一系统映像。c s o u g a r 用于执行运算功能， 它能有效地支持数千个结点的m p p 系统，提供了并行计算所需的功能。这种操 作系统结构简单，因而可靠性较强。 c r a y u n i c o s m k t ”j u n i c o s m k 是原c r a y6 4 位u n i x 操作系统的变种，属分布 式操作系统。它在核心层提供单一系统映像。u n i c o s m k 系统分为许多本地和 全局服务器，p e 分为用户和系统p e 。用户p e 运行用户的应用和命令；系统 p e 负责提供全局操作系统服务。其特点是可裁剪性强，既适用于单一大课题的 巨型机系统，也适用于多种应用的超级服务器系统。 另外，随着近年来l i n u x 操作系统的流行，它的开放源码的特性和高效性以及u n j x 系统兼容性比较适合于构建低价位的高性能并行计算机系统。在l i n u x2 2 x 之后的版 本中还集成了对s m p 体系结构的支持，在2 4 1 7 版本中集成了对c c - n u m a 体系结构 的初步支持【35 1 ，使之在中低档并行计算机和服务器市场方面具有广阔的前景。目前，包 括i b m 在内的许多并行计算机厂商已经开始构建基于l i n u x 的大规模可扩展工作站机群 系统。随着软硬件技术的进一步成熟，l i n u x 在大型事务处理、数据服务以及高性能计 算领域必将占有重要的席位。 尽管并行分布操作系统已经有了很大的发展，但面对数万个c p u 或数百个以上结点 的大规模系统，仍有许多技术难点需要克服。从设计的角度，要考虑到用户使用的透明 性、系统的灵活性、可靠性、以及性能和可扩展性等多方面的因素。其中，一个重要的 研究方向就是在越来越大的系统中，如何有效的实现单系统映像。 单系统映像，即s s i ( s i n g l es y s t e mi m a g e ) ，就是使用软件或硬件的方式给用户造 成一种幻觉，使多个计算元素统一为单一计算资源【1 2 , 3 6 - 3 8 】。换句话说，即使用户实际上 面对的是一个分布式的环境，但整个系统给用户的感觉并不是一个分布式的环境，用户 在使用整个系统时，他感觉不到系统中分布资源的存在，而是觉得自己正在使用一台独 立的p c 或工作站，只不过这台独立的p c 或工作站的功能要强大的多。 一般来说，单系统映像具有以下几个特性： 单一系统：从用户视图来看，系统是一个具有多个c p u 的单个系统，是一个整 体的概念。 单点控制：用户在使用系统时，通过单一的接口从同一点获取服务；系统管理 员在对系统进行管理和控制时，也是通过单一的接口向整个系统发送控制信息。 对称性：用户可以在不同的结点获得相同的服务，也就是说，整个系统对于用 户而言是对称的。 位置透明性：在系统中，提供服务的物理设备位置对于用户是透明的。 以工作站机群系统为例，对其系统结构进行分析，就可以看到s s i 在机群系统中的 第5 页 垦堕型堂垫查奎兰竺壅生堕兰垡丝苎 重要地位。一般的工作站机群体系结构如图1 2 所示。 图1 2工作站机群系统的体系结构 从图1 2 中可以看到，s s i 层和高可用性支持层一般是作为机群的中间件来实现的， 作为上层应用和下层分布资源之间的桥梁，它们既向应用程序隐藏了底层分布的机群环 境的细节，又为整个机群环境的控制管理和高可用性提供了支持。 目前为并行分布操作系统提供单系统映像支持方面的研究已经成为当前并行计算研 究领域的一个重点方向，许多典型的系统都在有关s s i 的各个方面具有鲜明的特点和较 高的性能。通过以s s i 实现的层次为标准可将现有的代表系统分为以下三类： i 在操作系统级实现s s i 有些系统的实现是在操作系统级进行的，通常可以采用修改已有的操作系统源代码 的方式，将s s i 的实现特征和内容加入到现有操作系统的内核中去，或者采用直接实现 一个新的单映像操作系统内核的的方式来实现s s i 。在这一级别实现的代表系统有 s o l a r i sm c 3 9 t 4 0 】、s c on s cu n i x w a m 4 1 蝽。 2 在中间件级( m i d d l e w a n ) 实现s s i 即在操作系统和应用程序之间附加一个单系统映像层，由这一层来实现各种单系统 映像的功能。这是目前最为普遍的一种实现方式，典型系统有b e r k e l e y 大学的g l u n i x 系统h 2 舶1 以及一些针对单地址空间的虚共享系统，如t r e a d m a r k 2 9 j 5 1 ，c o n d o r 4 6 , 4 7 等。 3 在应用级实现s s i 这种实现方式是直接面向应用程序的。可以采用在应用程序中加入一些单系统映像 的特征和扩展，以达到应用程序的用户的需求，但是以这种方式实现s s i 时，底层的分 第6 页 国防科学技术大学研究生院学位论文 布集群环境对程序员并非完全透明。这种方式的典型代表是并行数据库软件如p a r a l l e l o r a c l e 和并行系统管理软件如p a r m o n t 4 8 j 等。 要完整的实现一个s s i 系统，具体内容很多，其中比较重要的方面包括： 单入口点在支持s s i 的并行计算机系统中，一般有多个物理主机结点提供完 全相同的登录服务；另外，一般都使用某种策略来平衡各登录结点的负载。 位置透明的全局文件系统各结点的局部磁盘和文件系统集成为统一的文件映 像，用户从任一结点可以访问分布在不同结点的文件系统，并且全局文件系统 具有位置透明性。 单点控制系统管理员可以从任何一个结点登录，通过单一的控制点配置、监 测和管理整个系统。 单网络从任何一个结点都可以访问分布在不同结点的网络连接。 单i o从任何一个结点都可以使用分布在不同结点的i ，o 设备。 单一进程空间运行在整个系统中的进程都具有全局进程标识，由虚拟的进 程对象进行全局控制，并且应该具有一套一致性进程转移机制，包括进程的创 建、迁移、跟踪和调度等等。 单一存储空间在s s i 系统中，所有结点的存储空间在逻辑上是全局编址 的，通过相应的一致性模型和一致性协议来保证和维护各个结点地址空间的一 致性，同时，单一存储空间为程序员提供了基于共享变量的用户编程接口，体 现了相对于基于消息传递的编程模型的优越性。 以上这些内容如果根据实现难易程度可分为两类，一类是在许多实际系统中已经得 到了较好支持的内容，包括单入口、单点控制、单网络等；另一类是目前实现上还存在 较大困难的内容，包括单一存储空间映像和单一进程空间映像。 总的来说，并行计算机体系结构呈现多样化的形式，并行分布操作系统方面的研究 相对滞后，还面临着许多机遇和挑战。存储管理作为操作系统的核心内容之一，对系统 的性能起到了至关重要的作用。在并行分布环境下，无论是性能方面的需求，还是操作 系统支持单一系统映像方面的需求，都促使我们对并行分布操作系统中的存储管理机制 进行深入的研究。本文基于此背景，针对并行分布操作系统中共享存储管理及其优化技 术展开了研究和探讨，从而为并行分布操作系统提供高效的单一存储空间映像的支持。 1 2 课题研究的内容 本课题来源于国家杰出青年科学基金项目，该项目的主要研究内容是可扩展并行分 布操作系统与系统软件优化技术。作为该项目的一个组成部分，本课题重点针对并行分 布操作系统中共享存储管理及其优化技术进行了深入的研究。 第7 页 国防科学技术大学研究生院学位论文 1 2 1 课题研究重点 为了在并行分布操作系统中高效地管理存储空间并且提供良好的单一存储空间映像 支持，主要涉及到两个方面的问题。一方面，要构造逻辑上共享的存储空间：另一方面， 对共享存储系统性能进行优化，改善其效率。 根据目前并行分布操作系统研究的背景，我们确立了并行分布操作系统的设计目标， 即： 操作系统应具有对下层体系结构多样化的适应性： 操作系统应支持上层用户界面的统一性； 操作系统本身应具有较好的可扩展性； 操作系统应对单系统映像提供较为基本和完备的支持。 根据上述目标，我们重点针对共享存储管理问题展开研究。首先针对不同体系结构 所呈现出的不同存储共享的性质，我们提出了一个共享存储抽象层的概念，用以统一 s m p 等系统中的真共享、c c - n u m a 等系统中由硬件支持的分布共享以及工作站机群系 统中的虚共享等情况，为多样化的下层体系结构提供统一的单一存储空间映像解决方 案：接着在此基础上设计了并行分布操作系统的逻辑结构框架，通过它来对系统中各类 资源，如处理器、存储器、文件、网络、i o 等进行全局管理，以支持单系统映像。 在设计和实现共享存储抽象层的过程中，一方面，要考虑如何组织逻辑上的共享存 储空间，实现局部存储空间和逻辑共享存储空间之间的地址转换；另一方面，必须解决 存储一致性( m e m o r yc o n s i s t e n c y ) 问题。因为我们的设计目标之一是使得操作系统能够 对下层多样化的体系结构具备较为广泛的适应能力，所以必须对分布存储的多计算机系 统提供良好的支持。在存储模块物理上分布的系统中，处理器和存储模块的分布结构会 导致非一致的存储访问延迟，远程存储访问延迟通常是本地访问延迟的几倍甚至几十 倍；另外，无论在共享存储系统中，还是在分布存储系统中，c a c h e 的引入都使得同一 存储单元可能在系统中有多个副本，这种情况会破坏数据只有单个副本的系统中存储访 问操作的原子性，将存储访问顺序的问题进一步复杂化。无论是非一致的存储访问延迟 还是非原子性存储访问，都可能导致系统中不同处理器在同一时刻对同一共享存储单元 的观察结果不一致，从而使得程序的执行产生违背程序员本意的结果。为了避免这种情 况，保证程序的正确执行，必须采用某种存储一致性模型对共享存储访问的顺序加以限 制，也就是决定究竟什么时候某个处理器的访存结果为整个系统中的其它处理器所见以 及该访存结果如何为其它处理器所见。 存储一致性模型的问题可以说是一个古老而经典的问题，迄今为止已有数十种模型 被提出和得到应用。但是现有的存储一致性模型大都存在可扩展性较差和不适于在操作 系统中实现的缺点。因此，我们针对存储一致性模型的设计和实现问题进行了深入的研 究，在理论框架的基础上提出了一种新的线程一致性模型。这是本课题的重点研究内容 之一。 第8 页 国防科学技术大学研究生院学位论文 在构造了逻辑上统一的共享存储空间并对存储一致性问题解决的基础上，如何减小 由于存储访问延迟对系统性能造成的负面影响，从而提高共享存储系统的性能是另个 值得深入研究的问题。从并行计算机系统的分类情况来看，除了s m p 等具有集中共享 存储结构的系统外，存储器在物理上分布结构的系统都普遍存在存储访问延迟不一致的 现象。在这些系统中，本地和远程存储访问延迟之间存在差异，存储访问等待时间对程 序的执行效率起到了很大的影响。如果能够尽量改善数据的局部性，变远程存储访问为 本地访问，缩短存储访问等待时间，就能在很大程度上提高系统的整体性能。为此，我 们对数据的局部性优化技术进行了研究。 尽管通过编译优化等静态方法能够在很大程度上改善程序的数据局部性，但是由于 它受到工作集的复杂性和程序执行过程中系统环境变化的不可预测性的影响，其优化效 果受到一定的限制。如果能够在此基础上结合操作系统级的动态局部性优化技术，就能 在一定程度上弥补静态编译优化策略的不足，取得更好的局部性优化效果。因此，我们 重点针对在操作系统级实现数据局部性优化的动态页迁移策略进行了研究。现有的几种 具有代表性的页迁移策略都存在过分依赖体系结构，需要特殊硬件支持的特点，使得它 们的硬件开销大，通用性不够好。为了达到并行分布操作系统的既定设计目标，使之具 有较好的通用性，我们提出了一种基于即态访问信息的动态页迁移策略，它在没有特殊 硬件支持的前提下也能够达到较好的局部性优化效果，从而改善共享存储系统的性能。 这是本课题的另一研究重点。 1 2 2 课题研究难点 由于本课题主要是围绕并行分布操作系统中共享存储管理技术进行研究，涉及到的 知识领域比较广；另外，对操作系统进行研究离不开大量的实践工作，因此本课题具有 一定的难度，主要的难点表现在： 第一，尽管现代操作系统出于易扩展和易移植等方面的考虑，大都采用模块化的结 构，但是由于操作系统本身蕴含的复杂性，各个模块之间的关系比较错综复杂，针对任 何一个主题展开研究都要考虑诸多相关主题带来的影响，如在设计和实现线程一致性模 型的时候，必须结合全局存储管理以及线程的上下文切换等其它相关方面综合考虑。 第二，在分布环境下实现彻底的单系统映像是一个十分复杂的问题，特别是单一存 储空间和单一进程空间映像的实现方面。为了保证方案设计的有效性，必须对方案中各 种策略和算法的实际开销进行估算，否则，过于复杂和开销过大的策略是没有实际意义 的。为此，必须经过大量的模拟实现和性能分析工作，才能逐步验证和改进方案，达到 满意的效果。受到时间、环境和人力等方面的限制，我们目前的工作只能停留在提出具 体的方案、部分实现功能模块、通过模拟的方式来测试系统性能的阶段，要进一步把方 案应用到实际的系统中，还有大量的工作需要去做。 第三，由于我们研究的对象是操作系统存储管理部分，而现有的分布并行操作系统 内核源代码大都不是开放的，无法具体的进行分析，使得实验平台和环境的搭建有比较 第9 页 国防科学技术大学研究生院学位论文 大的难度。因此，我们主要针对开放源码的l i n u x 操作系统内核进行了剖析，在此基础 上考虑并行处理和单系统映像的特性，并在基于l i n u x 的p c 机上构建一个简单的机群 环境作为实验平台，借助些现有的操作系统模拟器进行具体的实验和性能评价。 第四，l i n u x 操作系统内核本身对多线程的支持不够，而我们提出的线程一致性模 型比较适