(计算机软件与理论专业论文)基于共享资源声明的并发访问控制研究与实现.pdf_第1页
(计算机软件与理论专业论文)基于共享资源声明的并发访问控制研究与实现.pdf_第2页
(计算机软件与理论专业论文)基于共享资源声明的并发访问控制研究与实现.pdf_第3页
(计算机软件与理论专业论文)基于共享资源声明的并发访问控制研究与实现.pdf_第4页
(计算机软件与理论专业论文)基于共享资源声明的并发访问控制研究与实现.pdf_第5页
已阅读5页,还剩60页未读, 继续免费阅读

(计算机软件与理论专业论文)基于共享资源声明的并发访问控制研究与实现.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 摘要 近年来随着超线程、多核体系结构等多线程技术的发展和广泛应用,计算机 底层系统已经提供了越来越高效的并行运行平台。但是,当前并行编程仍然是件 困难的事情。如何提高程序的并发度,保证共享数据的一致性,减轻程序员编程 的负担,降低编译器运行的开销等,都成为制约并行编程的重大问题。 本课题组试图就同步问题提出另一种形式的高级抽象共享资源使用声 明,探索从这种抽象描述获取程序对共享变量的本质要求的程序分析理论和技 术,研究选用最有效的同步方式( 锁、事务内存或无锁等) 生成满足这本质要求的 共享变量访问控制代码的理论和技术。 本文研究重心主要包含三部分:1 ) 研究链表结构动态数据的共享性和维持 性,并给出自动加锁操作的同步控制方法:2 ) 研究整型共享数据的维持区间,根 据程序结构和维持区间的关系,分析具体加锁和解锁的访问控制点。3 ) 在一个编 译框架下完成前面所述语言的实现,戗用于代码翻译的程序变换和变换后程序 的运行库。 通过本文工作中的分析结果,以及变换方法和运行库的支持,能够有助于课 题组对这种高级抽象并行语言的实现。 关键词:并行编程、访问控制、形状分析、程序分析、程序变换 a b s t r a c t w i t ht h ed e v e l o p m e n ta n dw i d e s p r e a du s eo fm u l t i - c o r ep r o c e s s o r st e c h n i q u e s , l o w - ! e v e la r c h i t e c t u r e sa r ep r o v i d i n gm o r ea n dm o r ee f f i c i e n tp l a t f o r mf o rp a r a l l e l a p p l i c a t i o n s h o w e v e ri t i ss t i l l e x t r e m e l yh a r d f o rp r o g r a m m e r st od op a r a l l e l p r o g r a m m i n g 。t h e r ee x i s t sc h a l l e n g i n gp r o b l e m so np a r a l l e lp r o g r a m m m g ,s u c h a 8 h o wt oi n c r e a s ec o n c u r r e n c y ,e n s u r i n gt h ec o n s i s t e n c yo fs h a r dd a t a ,r e l i e v i n gt h e b u r d e no fp a r a l l e lp r o g r a m m i n ga n dr e d u c i n gt h er u n t i m e o v e r h e a do fc o m p i l e r s o u rr e s e a r c hg r o u pa t t e m p t st op r o p o s ean o v e ls y n c h r o n i z a t i o na b s t r a c t l o n t h ed e c l a r a t i o no fu s i n gs h a r e dr e s o u r c e s b a s e do nt h i sn e w a b s t r a c t i o nw ee x p l o r e t h eb a s i ct h e o r i e sa n dt e c h n i q u e sf o ro b t a i n i n gt h er e q u i r e m e n t so v e rs h a r e dv a r i a b l e s t h e ns o m ee f f i c i e n ts y n c h r o n i z a t i o nm e c h a n i s m ( m u t u a le x c l u s i v el o c k ,s o f t w a r e t r a n s a c t i o n a lm e m o r yi n t e r f a c e so rl o c k f r e em e c h a n i s m ) a r eu s e df o rg e n e r a t i n g w e l l s y n c h r o n i z e dc o d e sa c c o r d i n g t ot h er e q u i r e m e n t s t h i st h e s i sm a i n l yc o n t a i n st h r e ep a r t s :1 ) i n v e s t i g a t i o no ft h es h a r i n gp r o p e r t y a n ds u s t a i n a b i l i t yo fd y n a m i c a ld a t as t r u c t u r e ss u c ha sl i n kl i s t ,t h e nt op r o p o s ea m e t h o dt oi n s t r u m e n tt h eo r i g i n a lc o d ew i t hl o c k sa u t o m a t i c a l l y ;2 ) i n v e s t i g a t i o no f t h es u s r a i n i n gr e g i o no fs h a r e di n t e g e rd a t a ,a n da n a l y z i n g t h el o c k i n ga n du n l o c k i n g p o i n t sb y t h er e l a t i o n o f p r o g r a m 3 ) i m p l e m e n t a t i o n o ft h el a n g u a g ei na t r a n s f o r m a t i o na n dr u n t i m el i b r a r y s t r u c t u r ea n dt h es u s t a i n i n gr e g i o n ; c o m p i l e rf r a m e w o r k ,i n c l u d i n gp r o g r a m t h i st h e s i s ,sw o r kw h i c hc o m b i n e st h ea n a l y s i sr e s u l tw i t hc o d et r a n s f o r m a t i o n a n dt h em n t i m el i b r a r yw o u l db eh e l p f u lt oi m p l e m e n th i g h e r - l e v e la b s t r a c t i o n i n p a r a l l e lp r o g r a m m i n gl a n g u a g e s k e yw o r d s :c o n c u r r e n c yp r o g r a m m i n g ;p r o g r a ma n a l y s i s ;c o n c u r r e n t a c c e s s c o n t r o l ;sh a p ea n a l y s i s i i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文,是本人在导师指导卜进行研究工作所取得的成 果。除已特另j ) j n 以标注和致谢的地方外,论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名:星丝至堑 签字日期: 忉l 。6 。l 。 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一,学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权,即:学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版,允许论文被查阅和借阅,可以将学位论文编入有关数据 库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 b 公开 口保密( 年) 作者签名:主丝g 臣 签字日期:竺i2 :堡:i 导师签名: 驰艺 签字口期:丝! ! :墨:! 第l 章绪论 第1 章绪论 近年来随着超线程、多核体系结构等多线程技术的发展和广泛应用,计算机 底层系统已经提供了越来越高效的并行运行平台。但是,当前并行编程仍然是件 困难的事情。如何提高程序的并发度,保证共享数据的致性,减轻程序员编程 的负担,降低编译器运行的开销等,都成为制约并行编程的重大问题。 为了平衡编程难度和编译器分析负担,我所在的课题组正在尝试探索一种新 的面向共享内存的并行编程语言,提出一种语言级的高级抽象一共享资源使用声 明。程序员只需给出共享资源的使用声明,不用关心这些数据的同步控制,编译 器分析这些信息,并自动的插入具体的访问控制代码。 由程序员提供的共享资源使用声明,到具体的访问控制首先需要研究不同类 型共享数据的特,并分析各种类型数据在并行执行时的访问规律;另外需要研究 不同的访问控制方式与共享数据使用之间的联系;最终运用多种程序分析方法, 让编译器可以自动给卜h 不同情况卜具体的同步访问控制方法。 本章首先介绍现今并行语言的发展和主要的访问控制技术,并比较各种技术 的优点和不足,最后给出本文的研究内容。 1 1 问题描述 已有的p t h r e a d t l l 线程库扩展了并行编程的需要,程序员在使用p t h r e a d 库写 并行程序时,需要通过锁来管理对共享变量的访问控制,从而造成编程困难,容 易出现死锁等问题。 现今最流行的并行编程实践是用m p i 2 】表达粗粒度的算法并行性,伴以在每 个m p i 任务内用o p e n m p l3 j 描述辅助的细粒度并行。m p i 通过同时执行多个借助 m p i 库进行消息传递的程序实例来并行,并行粒度足程序;而o p e n m p 则要求程 序员使用预编译指令和库函数调用对程序及数据进行标,来显示控制共享内存下 的并行与同步。这类编程技术给程序员提供了最大的控制程序并行性的自己空 间,却限制了编泽优化在编程语言中所起的作用【4 】。 正在研究的高产能并行编程语言i b m sx 1 0 1 5 , 6 1 、c r a y sc h a p e l 7 】和s u n s f o r t r e s s 8 】都引入了原子区,这种语言构造使得基于共享内存的并行编程不必使用 显示的低级同步。原子区的引入确实简化了对共享资源访问控制的编程一j ,但是 目前支持原子区的软硬件技术尚不令人满意。 第1 章绪论 为了解决以上问题,我所在的课题组正在研发一种新的面向共亨资源的并行 编程语言,程序员使用这种语言编写程序时不需要显式地管理对共享变量的加锁 与解锁,而只需要给出对共享数据及其使用约束的描述;编译器将根据程序中的 粗粒度并行结构以及共享数据描述信息来分析识别共享数据及其并发访问控制 维持区间,然后总结共享数据的不同使用特征,没计不同的并发访问控制实现策 略,自动地在程序中安插共享数据的并发访问控制代码。 然而从程序员提供的共享资源使用声明生成对共享资源的有效访问控制代 码,需要程序分析理论和技术的支持。本文致力于研究各种类型数据的并发访问 控制规律,利用共享数据使用声明信息分析得到共享数据在程序运行时具体的访 问控制点,并给出自动添加访问控制代码的方法。 1 2 相关工作 传统的并行编程主要采用锁进行同步,这种方法不但给程序员带来很大的负 担,也容易产生诸如锁顺序混乱,死锁等错误。近年来出现了一些新的方式来处 理共享数据的同步访问,其中最热门的是存语言中引入形如a t o m i c s ) 的原子区, 其中s 为语句块。a t o m i c s ) 的抽象语义解释为s 是原子执行的,要求满足以下 几点:a ) 原子性:语句块s 要么不做要么仝做,b ) 隔离性:语句块s 执行的中间 状态对其他线程是不可见的,c ) + 致性:事务执行之前和执行之后数据都必须处 于一致性状态。 当前原子区的实现存在有悲观和乐观两种方式( 也称为保守和开放方式) 。 保守的观点认为数据竞争是严重的,在对数据进行访问时需要先获得访问的权 限,然后才能做相应的操作。而乐观方式认为数据竞争不严重,可以先投机地执 行代码块s ,在执行结束前进行冲突检测决定是提交还是回滚。 采用保守方式的原子区实现是由编译器将原子区变成基于锁的代码i l 卜1 9 1 ,编 译器通过全程序分析来识别共享资源并为之分配锁,确定在程序中加锁和解锁的 位置,由于存在指针间接访问共享资源、共享资源被传入到原了区内调用的函数 等情况,编译器只能采取保守的分析,导致生成的代码并发度不高。采用保守方 式设计实现原子区的研究t 作有b i l lm c c i o s k e y 的a u t o l o c k e r i 博j 、m i c h a e le m m i 的l o c ka l l o c a t i o n l 2 2 】、s i g m u n dc h e r e m 的i n f e r r i n gl o c k sf o ra t o m i cs e c t i o n s i1 9 j 、 m i c h a e lh i c k s 的l o c ki n f e r e n c ef o ra t o m i cs e c t i o n s t 刀l 等。其中,a u t o l o c k e r 定义 了一种程序语言,程序员需要给m 共享变量的定义和保护该变量的锁,同时需要 显式的指定原子块。然后编译器运用指针分析和类型推理的方法去分析原子块中 共享数据的访问点,最终由编译器在这些位置添加锁。这种做法程序员只需给出 2 第1 章绪沦 用于保护共亨数据的锁,而不用去管理锁的使用,减轻了程序员的负担。它采用 了两阶段锁的方式去保护整个原子区,当原子区结束后才释放所有的锁,这样的 方式不利于处理类似树这样的结构。s i g m u n dc h e r e m 提供了更简单的语法,程 序员只需要指定原子区的开始和结束点,剩下的事就全由编译器完成。他为了分 析原子区中的共享数据建立了一套程序分析的框架,通过分析得到数据的各种使 用方式,例如变量、偏移地址和引用等,并为这些方式定义了不同的锁,最终通 过他们提供的锁库来运行程序。这种方法大大减轻了程序员的负担,但是编译器 的代价太大。 采用开放方式设计实现原子区的研究工作以事务内存【1o 】技术为主。事务内存 借鉴了数据库中事务的概念,但又有很多区别。粗略的说,事务内存是一种编程 抽象或编程泛型,通过内存事务来保汪共享数据的一致性。一个内存事务是一组 含内存操作的操作序列,要么全做( 即成功提交) 、要么全不做( 失败终止) 。 目前事务内存有硬件事务内存( h t m ) ,h e r l i h y 和m o s s t m 最早在硬件上实 现了事务内存系统。软件事务内存( s t m ) ,s h a v i t 和t o u i t o u 2 5 1 通过软件的方法 实现了事务内存系统。目前主要的研究是在软件事务内存上,d a v ed i c e 的t l 2 1 2 6 】 实现了一种基于版本锁的软件事务内存。它将每个内存映射到一个锁,并且锁中 包含锁标记和锁版本,标记表示是否被锁,版本用来记录该锁对应的地址值最近 被修改的时间戳。根据版本的比较可以让事务在执行时就对读写的内存地址直接 检查是否已被修改,避免了做剩下无用的操作,从而提高了s t m 的执行效率。 事务内存的方法虽然在程序的正确性上大大提高,但是事务内存技术尚未成 熟【1 叫6 1 ,现有的事务内存系统的运行开销普遍较高,囚事务中止而引起的不确定 性会是程序的调试复杂化;因不了解应用程序的数据访问特征而采取的保守冲突 检测导致产生假冲突,此外还有诸如系统调用和i o 操作能否出现在事务中、事 务嵌套 1 5 , 1 6 等问题。 此外一些特殊的原子区也可以用无锁编程实现,低级代码上无锁编程的目标 是在不使用锁的前提下安全的管理共享资源的访问,主要的方法是处理器提供的 c a s 或l l s c 指令,无锁代码虽然效率高但是很难编写和维护1 2 0 , 2 1 。 1 3 研究内容 在充分调研国内外相关工作的基础下,本课题组致力于设计并实现一种基于 共享数据使用声明的并行编程语言。这种语言的特点在于提供一种简单有效的并 行编程方式,通过在语言级卜给卜h 共享数据使用声明信息,然后编译器通过程序 分析【2 7 l 获得共享变量的维持信息,最后依据维持信息由编译器自动给并行程序 3 第l 章绪论 添加共享数据的访问控制代码。基于以上整个项月的研究模块,本文主要研究和 完成以的工作: 1 参与s p c 语言的没计,研究通过共享数据声明来捕述共享数据的使用,从 而给编译器提供简单、有效的静态分析信息。第一阶段我们对语言进行简化,集 中研究共享数据在并行程序中的使用情况,并将s p c 翻译剑采用锁方式的访问控 制上。 2 研究动态数据的维持特性,通过在源语言级给出数据结构的形状信息,从 而使编译器能够分析动态数据的共享性质和维持性质。形状图在程序中的推导可 以用来表示动态数据的形态和数据与指针之间的关系,然后根据图形的表示分析 哪些动态数据是共享,哪些数据需要维持,最终给出这些动态共享数据的维持区 间信息,并通过指针访问路径来进行保护。 3 根据项目组其他同学分析整型共享数据得到的维持开始于结束点信息,研 究在不同程序结构中加锁与解锁的规律,从而给出自动加锁操作的方法。设计一 种能够表示整型共享数据在各种程序结构下加锁和解锁操作的访问控制信息,和 计算这种访问控制信息的方法,为后面的访问控制提供依据。 4 在一种编译平台下实现源到源的程序变换,将s p c 语言翻译到带有访问控 制代码和并行结构的c 程序,并提供翻译后程序的运行库。运行库中的线程管理 和锁操作主要足基于p t h r e a d 库的实现。对于自动添加锁操作的位置则是依据前 面设计的维持信息中存储的访问控制点。 1 4 论文组织 本文的其余部分是这样组织的: 第2 章介绍本项目组共同研究的一种基于共享资源声明的并行语言s p c 。首 先介绍该语言的特点,然后介绍为实现用该语言编写的程序能够编译运行采用的 主要方法步骤,并简要介绍本文承担的主要工作。 第3 章详细介绍一种基于形状图推导的动念数据的访问控制分析方法,利用 形状图对动态单元和指针的抽象,分析程序中动态数据的共享性和维持性。 第4 章介绍整型共享数据在不同程序结构中加锁和解锁的分析,给出一种对 应的方法用于计算这种访问控制信息。 第5 章介绍在s u i f 编译框架下实现一种源到源的程序变换,以及为变换后 程序实现程序的运行库。 第6 章对全文进行总结 4 第2 章s p c 语言总述 第2 章s p c 语言总述 我所在的课题组已设计出一种新的面向共享资源的并行编程语言( s h a r e d v a r i a b l eu s a g ed e c l a r a t i o n sb a s e dp a r a l l e lc s t y l el a n g u a g e ,简称s p c ) ,程序员使用 这种语言编写程序时不需要显式管理共享资源的访问控制代码,而只需要给出共 享数据及其使用的描述,编译器将根据程序员提供的共享数据描述信息来分析识 别共享数据及其访问控制点,然后根据共享数据的使用特征,给出相应的并发访 问控制实现策略,自动地在程序中安捅共享数据的并发访问控制代码。 本章首先介绍课题组设计的并行编程语言s p c 的语法,语义和主要特性。 然后介绍对s p c 这种并行程序语言设汁的具体实现思路和总体实现框架,并简 单介绍本文在整个设汁和实现中完成的工作。 2 1s p c 语言简介 s p c 语言是本项目当前设计的基于共享资源需求描述的并行编程语言。它的 控制流结构、表达式以及类型( 整型、指针型、结构体类型) 等源自c 语言, 增加了共享变量的使用声明l a s t 、s h a r e d 等,另外引入粗粒度的并行机制( 如 c o b e g i n c o e n d 并行语句) 。图2 1 给出了s p c 的详细语法定义。 与已有的共享资源访问的同步方式应用编程接口相比,我们课题组设计的 共享变量维持声明有以下特色: ( 1 ) 语言抽象层次更高:程序员只需声明对共享变量的维持需求,而不需要 采用具体的同步技术来对共享变量的访问控制直接编程。 ( 2 ) 易于分析:利用程序员给出的共享变量维持声明信息,编译器能较容易 地获得对共享变量的维持信息。 ( 3 ) 访问控制策略灵活:利用共享变量的维持信息,编译器可以结合底层结 构特征,采用不同策略灵活生成共享变量访问控制代码。 s p c 与具有锁和原子块特点的浯言相比,为其享数据的同步提供更高层语言 的抽象描述。程序员在编写并行程序时,不需要自己管理锁,也不需要考虑原子 块的问题,只要给出芡享变量的维持声明。例如,为了表达某个线程在一段代码 段范围内对某个共享变量一直保持访问权限,可以使用关键字l a s t 在被维持范围 的最后一条语句上修饰该共享变量。编译器根据程序员提供的这螳信息,分析如 何对共享变量的进行访问控制,并根据具体的情况选择最优的访问控制方式和访 问控制粒度。 5 第2 章s p c 语言总述 ( p r o g r a m ) ( s t r u c td e c l a r a t i o nl i s t ) ( s t u c td e c l a r a t i o n ) ( f i e l dd e f i n i t i o nl i s t l ( f i e l dd e f i n i t i o n ) ( v a r i a b l ed e c l a r a t i o nl i s t ) ( v a r i ab l ed e c l a r a t i o n ) ( i d e n t i f i e rl i s t ) ( f u n c i t i o nd e f i n i t i o n ) ( s t a t e m e n tb l o c kl i s t ) ( s t a t e m e n tb l o c k ) ( s t a t e m e n tl i s t ) ( s t a t e m e n t ) ( a t o m i cs t a t e m e n t j ( e x p r e s s i o n ) ( b o o l e a ne x p r e s s i o n ) ( l v a l u ee x p r e s s i o nl i s t ) ( l v a l u ee x p r e s s i o n ) ( c o n s t a n t ) ( a r i t h m e t i cb i n a r yo p e r a t o r ) ( r e l a t i o n a lb in a r yop e r a t o r ) ( b o o l e a nb i n a r y0 p e r a t o r ) ( i n t e g e rc o n s t a n t ) ( i n d e n t i f i e r ) p ,0 # 7 u ” :2 掌t r u c t d e cl i s t := ,u c t ( h ( := 矗e l d d c t f i s t := 矗e l d d 盯 := v a r d r cl i s t:; u ,d e c := t d h s t := p m d 吖:= b l o c k l i s t := b l o c k:= s l m t h s t:= s h u t:5 l i i i i i i l n t o ,善打h := i := i l i l b e x p := l l i h , a l h s t:= l l , a l:= c , 黼 s h o p r b o p b b o p i n l c o n s t s t l “( t t h :c li s tt ? f l r d e c l i s t t r t d o fi s t r “( t d e c h s ts ,“c t d e c s t r u c ti d f i e 1 d d , 伊讧t : f i e h h l e fi f l e l d d e f l t s t 1 i e l d d 盯 i n ti d : is t r u c t i d : rl , a r d c c l i s to a i r l c c i n tt d h s t ; is t r u c t i d : z dt d h s t ,i d v o i dm a i n ( 1b l o c k b l o c k b l o t m i s tb l o c k f ”r z r w e c l i $ t s t m t l i s t fi , l m t , l 抽z 一竹“ a t o l n , _ t m t r e t u r n ; j f ( b t 一_ ) 一z ,n z i f ( h r ,j ) ) m i n te l s em r n l w h i l e ( 阮:r t j ) , s l m l i d = m a l i o c ( s t u r c t 州) ; f r e e ( i ,班 b l o c k c o b e g l nb l o c k l i s te o e n d h a l = e x p ; s k i pl v a l l i s t : t a l ( n f p ) c o r t a t f :珂, e x pn ,( 巾凹p 【6 p r p ) ! b r x p e x pr b o pe x p 6 p r pb b o p b e x p l a s ti di 胁a l l i a t 1 a s tf d j l a s ti d i di 州- - - fl a s t i d f d l a s tfr zl ,f c i “ l l a s ti d i di 州l a s ti d f ”:r ) t t f + i l i ix - li ! _ i 矗l i il = ;l 一 【o - 9 o - g f _ a - z - = l o 一9 _ a - z a - z , 图2 1s p c 语法定义 以下的各小节将分别介绍s p c 中共享数据的描述,并行结构的定义,以及 共享数据维持的含义。 2 1 1 共享数据描述 s p c 程序中的数据区被分成可以被多个线程访问的共享数据区以及每个线 程的私有数据区。不论是共享数据区还是线程私有数据区,都可以进一步分静态 数据区和动态数据区,前者存放静态分配的数据,后者存放通过m a l l o c 动态分 配的数据。 在函数外声明的变量均认为是共享的,称为全局共享变量。 6 第2 章s p c 语言总述 由m a l l o c 所分配的共享存储空间称为动态共亨变量,而那些在程序中声 明的共享变量称为静态共享变量。 如果一个指针类型的变量是共享的,则不仅该变量对应的存储单元是共享 的,而且其指向的单元也是共享的。 如果一个结构体类型的变量是共享的,则它所有的域都是共享的。不存在 一个结构体的一部分域是共享的,而剩余的域是非共享的情况。 如果指针变量p 声明为全局共享变量或者是指向共享变量的局部变量或 形参,则当执行p = m a l l o c ( ) 时,m a l l o c 将在共享数据区中分配存储空间。 如果指针变量p 声明为不指向共享变量的局部变量或形参,则当执行p = m a l l o c ( ) 时,m a l l o c 将在线程私有数据区中分配存储空间。 2 1 2 并行结构 并行语句e o b e g i nb l o c kl i s tc o e n d 表示组成b l o c kl i s t 的各个程序块将产生 一个线程体,采用f o r k - j o i n 的方式并行执行。其中,执行并行语句中每个程序块 的执行体称为是执行并行语句的线程的子线程。执行并行语句的线程等待各子线 程执行结束后,才继续执行e o b e g i nb l o c kl i s te o e n d 之后的语句。 编译器需要为c o b e g i nb l o c kl i s te o e n d 中的各个程序块分配( 创建) 子线程、 以各程序块作为各子线程的执行任务来启动子线程的执行、等待子线程的执行结 束、销毁子线程等。 2 1 3 维持特性 一个线程t 存执行某段代码期间维持某共享变晕s ,是指该线程在此期间要 访问s ,并且禁止其他线程在此期间访问s 。在线程t 维持共享变量s 期间,只 要出现线程t 对共享变量s 的值的修改,则称线程t 写维持s ,否则称为t 读维 持s 。 对于整型的共享变量s ,在一个线程t 写维持s 期间,禁止其他线程对s 读 和写。对于指针类型的变量s ,则在一个线程t 读维持或写维持s 期间,禁止其 他线程对s 读写,进一步地,还不允许其他线程释放s 所指向的变量( 因为若s 所指向的变量被其他线程释放,本质上就是s 被其他线程修改,即修改成了悬空 指针) 。 仅上述自动维持尚不足以囊括各种需求,因此给程序员提供一种描述维持需 求的手段。 l a s t 可以出现在左值表达式中,带l a s t 的变量出现在某线程的一个原了代码 7 第2 章s p c 语言总述 段中表示,从上次读写该变量到执行该原子代码段期间,该变量被维持。 在自动维持和l a s t 维持还不足以表达维持需求时,可以借助s k i pl v a l l , l v a l 行语句,其中i v a l ,包含有l a s t 修饰符。s k i p 语句本质上是不执行任何操作,但 是把它当作读l v a l t ,l v a l 。的一个语句,以便通过其中的l a s t 来调整对l v a l l , l v a l 。的维持。 共享变量的最简单的维持区间是一个包含该共享变量的原子代码段的执行 区间,即从这个原子代码段之前的程序点到其之后的那个程序点所执行的代码。 更长的维持区间则是南上面的自动维持和l a s t 维持等引起的。 2 1 4s p c 程序实例 s e c o n db l o c k i n tb u f f e r ;s h a r e d v o i dm a i n ( ) i n tf l a g ,c o u n t ; b u f f e ri n i t i a l i z e f l a g = i ;c o u n t = 0 ; w h i l e ( f l a g ) c o b e g i n i f ( b u f f e r 0 ) | | 黾r s tb l o c k l a s tb u f f e r = b u f f e r 1 : c o u n t = o ; i n tf l a g ; e l s e f l a g = 1 : c o u n t = c o u n t + 1 : w h i l e ( f l a g ) ) i f ( b u f f e r = 1o o ) i f ( c o u n t = = 1o o o ) f l a g = o : f l a g20 : e l s e ) i a s tb u f f e r = b u f f e r + l ; ) ) ) c o e n d r e t u r n ; ) ) 图2 2s p c 程序实例 图2 2 是一个用s p c 语言编写的生产者消费者的并行程序实例,程序中包含 一个全局共享变量b u f f e r 用来表示当前剩余产品的数量。该程序中有两个并行 块,每个并行块将创建一个线程,并以f o r k - j o i n 的形式并行执行。其中一个专门 用于生产,另一专门负责消费,两个线程可能回同时对共享变量b u 疏r 进行操作。 因此每个并行块中在使用b u f f e r 时都需要给出相应的l a s t 使用声明,以便编译器 可以根据这个声明分析访问控制信息。 2 2s p c 实现框架 为了能够使s p c 语言编写的程序能够真正的运行,使其更具有实际应用价 值。本阶段我们的考虑通过一个扩展性较高的编译平台将s p c 叶1 的语法结构先 8 第2 章s p c 语言总述 翻译到编译框架的中间表示结构中,然后再中间表示层进行各种程序分析得到所 需要的访问控制信息,最后再通过一种源到源的程序变换方法,将s p c 程序翻 译成具有并行执行能力的c 语言程序。如图2 3 ,整个项目的总体实现方案包含 前端解析、c f g 生成、维持区间分析、访问控制分析和优化、程序变换和运行 库支持等儿大部分。 2 2 1 整体框架 图2 3s p c 语言实现总体方案图 1 ) 其中前端解析是指将s p c 程序翻译成带有扩展结构的s u i f 编译、f 台中 间表示;c f g 生成是在编译,f 台中生成程序的控制流表示结构,为后一阶段的 程序分析和变换提供支持。 2 ) 维持分析是在中间表示层利用各种程序分析技术对s p c 源程序中的共享 数据进行分析,得到共享数据在程序巾需要维持的范用,即维持区间信息。 3 ) 访问控制分析是根据维持分析得到的共享数据维持区间信息,分析程序 的不同情况,决定采用哪种具体访问控制方式,然后给出这种控制方式下自动插 入访问控制代码的方法。 4 ) 程序变换的作用是在中间表示层对s p c 源程序进行包括类型、结构、插 入代码等源到源的变换【37 1 ,将s p c 程序翻译成g c c 可以编译运行的以p t h r e a d 库为基础的c 代码并行程序; 5 ) 运行库的作用是为变换后的程序定义程序运行时需要调用的程序代码, 主要包括内存分配,线程管理和同步控制等实现。 9 第2 章s p c 语言总述 2 2 2 本文工作 本文在整个s p c 实现中承担的辛要工作动态数据的维持和访问控制分析, 整型数据的访问控制分析,以及程序变换和运行库实现。其中主要的难点是动态 数据的维持和访问控制分析,并给 n 动态数据采用锁操作的访问控制实现方法。 论文将在后面的章节中对这儿项工作做具体的介绍。 2 3 本章小结 本章介绍了我们课题组正在研究的一种并行语言简称s p c 语言。该语言目 的在于简化程序员编写并行程序的复杂度和提高并行程序效率。文中首先介绍了 s p c 的语法结构和程序中共享数据的描述,以及数据的维持特性等。然后介绍为 让s p c 程序能够真正运行采用的具体实现框架,分别介绍了框架中主要部分的 研究内容。最后给出本文在整个框架中具体负责的研究工作。 1 0 第3 章动态数据访问控制分析 第3 章动态数据访问控制分析 动态数据由于其自身的不确定性,一直都是各类程序分析中的难点,本章重 点介绍如何分析动态数据的共享性和维持特性。通过一种形状图抽象的方法,分 析动态共享数据的维持信息。该方法的主要思想是利用图中的节点抽象内存中的 动态数据单元,用图1 一的边抽象指针的指向关系。通过不同语句对图形产生的变 换来模拟程序执行中动态资源的具体形态。依赖对图形的推导最终获得基于锁的 访问控制方式下共享资源加锁和解锁的位置,以及用于共享资源锁操作的指针访 问路径。目前本文主要是针对单链表结构的动态数据进行分析。 3 1 共享资源维持介绍 s p c 中的共享资源分为静态共享资源和动态共享资源,前者存放静态分配的 数据( 全局变量) ,后者存放通过m a l l o c 动态分配的数据。指针在程序中的典 型应用是表示动态分配的数据结构,如各种链表、二叉树等。为了便于研究指针 类型变量与动态共享资源的访问控制关系,语言中禁i i :使用取地址符& 操作,强 制类型转换和指针运算操作,并且将m a l l o c 和f r e e 看做是语言白带的语句。 所谓共享资源的维持是指线程t 在执行某段代码区间时要访问某个共享资 源s ,并且禁止其它线程在此期间访问s ,我们称这种对共享资源的保护行为称 作维持,对这段代码区间称作共享资源s 的维持区间。静态共享资源在维持区间 内不允许其它线程读写,动态共享资源在维持区间内不允许读写和释放。 静态共享资源的维持 在s p c 语言中静态共享资源是指全局声明的整型或结构体类型的变量。这 些变量在整个程序中可见,并且存储位置和变量名不会发生变化。 静态共享变量的维持分析依赖l a s t 共享使用声明信息,当静态共享变量仅在 单独语句上要被维持时,无需用l a s t 声明;当静态共享变量v 在语句s l 和s z ( s 2 是s 1 的后继) 之间要被维持时,可以在s 2 上对v 增加l a s t 声明来表达,即线程 在执行s l 到s 2 这段时间内,保持对s 的维持。 对于静态共享资源的维持,主要有两种方式: 1 ) 原子命令维持 即,多个线程必须原子、隔离地执行原子代码段。原子代码段包括赋值语句、 条件表达式、m a l l o c 和f r e e 等一步执行的简单语句。所谓线程原子地执行,是指 原子代码段要么都执行、要么都不执行:所谓线程隔离地执行,是指任一线程t 1 1 笫3 章动态数据访问控制分析 在执行原子代码段期间,其他线程不能看到t 执行时的中间状态,也不能改变t 执行时所访问的共享变量。 在这种方式中对出现在原子代码段中的共享数据进行维持,共享数据的维持 区间开始点和结束点即原子代码段的开始和结束。 2 ) l a s t 维持 即,对使用l a s t 关键字声明的共享变量维持,维持的含义是从上次读写该变 量到本次l a s t 声明位置,该变量被始终维持。若要对i 司一个共享变量在多次读写 处都进行维持,则需要被维持的读写位置都需要用l a s t 声明。如x = y ;z = l a s tx ; l a s tx = t ;表示x 从第一条语句开始一直维持剑最后一条语句结束,若中间一条语 句没有对x 加l a s t 声明则表示x 从第条语句开始直维持到最后一条语句结 束。 从以上的维持语义可知,对于静态共享资源,依赖原子代码段和l a s t 共享使 用声明的辅助信息,通过对控制流的逆向分析即可以得到它在不同代码段中的维 持区间,当然还需要考虑一些程序控制流对维持区间的影响。这部分的详细分析 不作为本文研究的重点,因此不具体介绍。 动态共享资源的维持: 程序中能够通过共享指针变量或其它芡享资源的指针访问到的动态资源称 为动态共享资源。由于动态共享数据的访问是通过指针完成的,因此我们称动态 共享数据的维持为指针维持。 动态共享资源与静态共享资源有两点不同:1 ) 静态共享资源作为全局变量 在程序开始即町确定,而动态其享资源是根据程序执行情况动态产生的;2 ) 静 态共享资源在整个程序执行中数据名称和存储位置不会发生变化,通过变量名即 可访问,而动态共享数据则是通过指针路径访问,在程序执行中内存单元和指针 的对应关系不断发生变化。 与静态共享资源的维持依据不同,动态共享资源维持的依据是通过可以访问 到它的指针引用来决定的,从第一次有指针访问该资源开始,到不再有指针访问 它结束。在这段维持区间内指向该单元的指针访问路径不断发生变化,因此动态 共享资源的维持分析,不仪需要分析语句t j 访问动态资源的情况,还依赖于指针 之间指向关系的变化。 根据动态共享资源的特性和维持含义的描述,可以总结出动态共享资源维持 分析有以下主要难点: 如何确定当前线程存程序运行时动态资源的状况,特别是确定可以访问 的动态共享资源。 1 2 第3 章动态数据访问控制分析 如何确定当前线程在程序运行1 i 同时刻动态资源和指针变鼍的指向关 系。 如何利用静态分析方法研究程序在行循环结构时动态资源的维持状况。 3 2 形状图介绍 为了解决上述问题本文引入一种基于形状图抽象的分析方法,通过图中提供 的信息去辅助分析动态共享资源的维持状况。该方法的主要思想是利片j 图中的节 点来抽象内存中的动态数据单元,用图i i 的边来抽象指针的指向关系。通过不同 语句对图形产生的变换来模拟程序执行t l 动态资源的具体形态。 为了描述如何根据形状图的推导来辅助分析动态共享资源的维持方法,本文 给出基于单链表数据结构下的形状图推导规则和维持分析方法。至于不同数据结 构的形状图推导规则可以根据单链表结构的推导方法给出相应的定义,这不作为 本文研究的重点。 3 2 1 形状图定义 g = e7 ) 表示一个形状图,其中为节点集合,e 为边集合,丁为节点与 其类型的映射关系集合。 w 表示

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论