（计算机软件与理论专业论文）非阻塞算法在安全文件访问控制系统中的研究与应用.pdf

硕士论文非阻塞算法在安全文件访问控制系统中的研究与应甩 摘要 随着计算机的发展，特别是操作系统和多处理器的出现，如何开发高效率的 多线程的并发程序也显得越来越重要。传统的基于锁的同步机制解决了多线程对 同一对象操作的正确性问题，但是没有解决一些例如死锁和优先级倒置等问题， 而且在中度甚至高度并发的情况下，系统的效率也不能满足人们的要求。本文重 点研究了非阻塞算法，实现了堆栈和链表数据结构上的非阻塞算法，并将其应用 到文件访问控制系统中。实验表明，非阻塞算法在实现并发控制功能的同时也提 高了系统的吞吐率以及解决了基于锁的机制中存在的死锁等问题。 为了解决基于访问控制列表的方法所存在的问题，文中将基于p k i 技术的 s p k i 属性证书弓f 入到文件访问控制系统中，对s p k i 证书的一些相关问题进行研 究：在m i t 的j s d s i 包的基础上，改进现有的s p k i 证书的结构，设计和实现了 颁发给用户的属性证书和资源所拥有的策略证书；同时对于证书的生成过程和在 关系数据库中的存储与管理进行了研究：最后详细讨论了证书链搜索中的证书集 的化简问题，实现了基于c o l l e c t i o n 和h a s h m a p 的方法。 本文最后设计和实现了一个基于w e b 的安全文件访问系统，通过试验验证了 非阻塞方法取代基于锁的同步方法的可行性。 关键词：非阻塞算法，并发控制，s p k i ，证书链化简。 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e r s ，e s p e c i a l l yt h ee m e r g e n c eo fo p e r a t i n g s y s t e ma n dm u l t i p r o c e s s o r s ，h o wt od e v e l o pa ne f f i c i e n tm u l t i t h r e a d e dc o n c u r r e n t p r o c e d u r e sa l eb e c o m i n gi n c r e a s i n g l yi m p o r t a n t b a s e do nt h el o c k , 拄a d i t i o n a l s y n c h r o n i z a t i o n m e c h a n i s ms o l v e st h e p r o b l e m o ft h ec o r r e c t n e s so ft h e m u l t i - t h r e a d e do p e r a t i o no nt h es a m eo b j e c t , b u ts o m ep r o b l e m sa l eu n r e s o l v e ds u c h a sd e a d l o c ka n dp d o n t yi n v e r s i o n a l s oi nt h em o d e r a t e l ye v e nh i g hc o n c u r r e n c y c k c m n s t a n c e s t h ee f f i c i e n c yo ft h es y s t e mc a l ln o tm e e tt h ep e o p l e sd e m a n d s t h i s p a p e rf o c u s e so nt h ei m p l e m e n t a t i o no f t h en o n - b l o c k i n ga l g o r i t h mb a s e do nt h es t a c k a n dl i n k e d l i s td a t as t r u c t t t r e ，w h i c hi sa p p l i e dt ot h ef i l ea c c e s sc o n t r o ls y s t e m r n 地 r e s u l to ft h ee x p e r i m e n ts h o wt h a t ：n o n - b l o c k i n ga l g o r i t h mt oa c h i e v ec o n 打o l ，a tt h e s a m et i m ei m p r o v i n gt h et h r o u g h p u to ft h es y s t e ma n dt or e s o l v et h ee x i s t i n g d e a d l o c ka n do t h e ri s s u e sb a s e do nt h el o c k i n gm e c h a n i s m i no r d e rt os o l v et h ep r o b l e mb a s e do nt h em e t h o do fa c c e s sc o n t r o ll i s t s ，i nt h i s p a p e r , w ei n t r o d u c es p k ia t t r i b u t ec e r t i f i c a t eb a s e do i lp k it e c h n o l o g yi n t ot h ef i l e a c c e s sc o n t r o ls y s t e m ：o nt h eb a s i so fj s d s im i tp a c k e tw ei m p r o v et h ee x i s t i n g s p k ic e r t i f i c a t e ss t r u c t u r e ，d e s i g na n di m p l e m e n tt h ea t t r i b u t ec e r t i f i c a t e sp r e s e n t e d t ot h eu s e ra n dt h es t r a t e g yc e r t i f i c a t eo w n e db yr e s o u r c e s ；m e a n w h i l e ，r e s e a r c ht h e c e r t i f i c a t e p r o c e s sa n d t h ef o r m a t i o no ft h er e l a t i o n a ld a t a b a s e s t o r a g e a n d m a n a g e m e n t ；f i n a l l yd e t a i l yd i s c u s st h es i m p l i f i c a t i o no ft h ec e r t i f i c a t es e t si nt h e s e a r c ho fc e r t i f i c a t e sc h a i l l ，r e a l i z et h em e t h o d sb a s e do nt h er e a l i z a t i o no ft h e c o l l e c t i o na n dh a s h m a p f i n a l l y , w ed e s i g na n di m p l e m e n t aw e b - b a s e df i l ea c c e s ss e c u r i t ys y s t e m p r o v e t h ef e a s i b i l i t yo f t h en o n b l o c k i n ga l g o r i t h mb ye x p e r i m e n t k e y w o r d s ：n o n b l o c k i n ga l g o r i t h m ，c o n c u r r e n c yc o n t r o l ，s p k i ，c e r t c h a i nr e d u c e 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 渺6 月矽号 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 1 绪论 1 1 并发算法的研究现状 近些年来，随着计算机技术的不断发展，特别是操作系统的发明和多处理器 的出现，传统的顺序执行的程序无论在资源的利用率，公平性还是方便性等方面 已经不能满足人们实际应用的需求了。于是出现了并发程序，并发程序可以提供 很好的系统吞吐量。但是并发程序在带来好处的同时也存在着线程安全性的问 题。国内外很多专家学者对于并发算法进行了大量的研究，提出了很多解决方案。 传统的关系数据库中需要解决并发的问题，b 口有多个用户需要对同一个数据 对象进行访问和修改工作，如何确保用户能正确地访问这些数据，是并发算法所 研究的内容。目前市面上所流行的关系数据库，例如o r a c l e 和s q l s e r v e r 对于并 发控制都是采用的基于锁的同步机制。1 3 5 1 1 4 1 l 【4 2 】 j a v a 在5 0 版本出来前，解决多线程程序正确执行问题的方法是在需要并发 执行的函数前加上关键字s y n c h r o n i z e d ，表明这是一个同步的方法，实现了一个 内在锁的机制，同样可以实现并发控制唧。 但是，随着进一步的研究发现，基于锁的机制在中度到高度争用的情况下， 会牵涉到多次的线程的挂起以及上下文的切换，对系统的硬件要求越来越高，系 统的吞吐量，即整个系统的效率也不敬如人意l ”“4 3 1 。 为了解决锁机制中的线程挂起和上下文切换所带来的系统开销，许多在专家 学者提出了无锁定的并发算法思想。无锁定算法也称为非阻塞算法，作为科研的 主题已经有2 0 年了【j u j 。 非阻塞算法属于并发算法，它们可以安全地派生自身的线程，所采用的派生 方式不是传统的锁定，而是通过一种低级的原子性的硬件原生形式c a s ( l k 较和 交换) 来实现的。非阻塞算法的设计与实现极为困难，因为在很大程度上取决于 系统平台的支持，但是非阻塞算法可以提供很好的吞吐率，对于并发算法中存在 的生存问题( 例如死锁和优先级反转问题) 能提供很好的防御措施1 1 4 6 1 。 在j a v a5 0 之前，利用j a v a 语言开发非阻塞算法是不可能实现的。因为j a v a 语言所基于的m 平台没有提供对非阻塞算法中的硬件原生形式的支持。j a v a 5 0 出来后，这一状况得到了改变，j a v a5 0 引入了j a v a u t i l c o n c u r r e n t a t o m i c 包， 包中提供了九种类型的原子变量。可以通过这些原子变量中提供的c a s 方法实 现在各种数据结构中的非阻塞算法。国际并发大师b r i a ng o e t z 在m m 网站上所 做的j a v at h e o r ya n dp r a c t i c e 专题中对于非阻塞算法和原子变量进行了专门的讨 论和研究，目前的研究热点是在各种数据结构的操作中实现非阻塞算法。 2 9 1 1 4 5 】 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 1 2 安全文件访问控制系统 本文的研究内容为非阻塞算法在安全的文件访问控制系统中的应用。所谓安 全，是指防止系统中的对象不会被未授权的用户所访问，从而不会导致信息的泄 漏【2 】。 实现安全主要方法是进行访问控制。访问控制直接限制和决定一个用户能做 什么，或者代表着用户的程序能做什么，实际上是决定主体是否被授权对客体执 行某种操作。它依赖于身份认证使主体合法化，并将特权与主体联系起来。只有 经过授权的用户才允许访问特定的资源。访问控制是以认证作为前提的。传统的 访问控制有自主性访问控s t j ( d a c ) 和强制性访问控s t j ( m a c ) p a 及基于角色访问 控制f i 出a c l 【3 】【1 7 1 1 2 0 l 。 传统的授权和访问控制决策通常都是基于访问控制列表的。访问控制列表非 常适合于集中式的客户机朋艮务器系统，但是却不能很好地扩展到大型分布式系 统中。在分布式系统中使用访问控制歹口表意味着必须有一个中央存储机制，而在 大系统中这很可能成为影响整个系统性能的瓶颈；或者可以将访问控制列表数据 库复制到多个分布的服务器中，但这又带来了更复杂的更新和同步问题，同时还 必须保证访问控制列表的完整性和安全性以防止非授权的修改、替换和破坏。访 问控制列表必须使用全局唯一的名字以映射到相应的访问权限，这使得访问控制 列表方案很难支持匿名性和隐私性。而且访问控制列表没有支持给第三方授权委 托的机制。而匿名性或隐私性以及授权委托等特性对于基于i n t e m e t 的电子商务 应用具有非常重要的意义【1 8 】。 为了避免传统的基于访问控制列表的方法带来的种种问题，许多研究工作将 p k i 技术引入到了访问控制和权限认证的领域。p k i 是一个利用公钥概念与技术 来实施和提供安全服务的具有普适性的安全基础设施。它是遵循标准的密钥管理 平台，它能够为所有网络访问控制应用透明地提供采用加密和数字签名等密码服 务所必须的密钥和证书管理。所有提供公钥加密和数字签名服务的系统，都可以 叫做p k i 系统，p k i 的主要目的是通过自动管理密钥和证书，可以为用户建立起 一个安全的网络运行环境，使用户可以在多种应用环境下方便地使用加密和数字 签名技术，从而保证网上数据的机密性、完整性和有效性。1 5 在保证系统中对象不会被未授权的用户访问的同时，也要确保多个用户同时 对某一对象进行修改或者删除工作时，系统中的对象始终处于一致的状态中。也 就是所有用户不会读取到脏数据。这是并发控制所研究的内容。传统的方法是采 用基于锁的机制，但是无论在系统吞吐率还是在死锁等问题上都不能令人满意， 于是许多研究工作将非阻塞的方法引入到了访问控制系统的并发控制模块中【1 9 】。 2 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 1 3p k i 发展现状和标准化工作 1 国内外发展现状 公钥基础设施( p u b l i ck e yi n f r a s n u c t u r e ，p k d 是一种遵循既定标准的密钥管 理平台，由密钥体系和证书管理体制两部分组成，其作用是为使用者提供数据加 密和数字签名等服务。目前，世界各国的p k i 已经在政府、银行、海关等领域广 泛应用1 4 】。 国外的信用体系启用数字证书认证体系比国内早很多，从9 0 年代初期开始， 美国、加拿大、英国、德国、日本和新加坡等国相继开展了可信的第三方认证体 系的研究和建设工作。 美国联邦p k i 筹委会成立于1 9 9 6 年，它与联邦首席信息官委员会共同致力 于f p 体系结构的研究。首先成功地在个联邦机构中分别使用了公开密钥密码 技术，为网上交易提供全面解决方案，为所有的服务颁发和管理数字证书，登记 机构验证用户的身份，认证机构负责批准证书，分发证书和发布证书黑名单，密 钥恢复机构恢复遗失的私钥等。为了增强国际间的合作，提高整体竞争力，解决 不同信任域之间的互操作性问题，联邦政府计划联合各联邦机构中独立的 p k i c a 一美国国防部( d e p a r t m e n to fd e f e n s e ，d o d ) ，国家标准技术研究所 ( n a t i o n a li n s t i t u t eo fs t a n d a r d sa n dt e c h n o l o g y ，n i s l ) ，乔治亚州技术研究所 ( g e o r g i a t e c hr e s e a r c hi n s t i t u t e ，g t r i ) ，卅f 政府和地方等共同组建美国联邦p k i 体系。使用该体系可以使信任域不仅局限在本信任域的环境中，而且可以使信任 域扩展到整个联邦政府甚至是全球。 加拿大对于政府p k i 体系的研究要比美国早，早在1 9 9 3 年加拿大通信安全 部( c o m m u n i c a t i o ns e c u r i t ye s t a b l i s h m e n t ，c s e ) 就已经开始了政府p k i 体系雏形 的研究工作，当时主要是开发一种满足政府需求的p k i 产品，实行无货架商业贸 易。随后，陆续有部分联邦政府机构参入了g o cp k i 体系的开发工作。经过若 干年的研究，到2 0 0 0 年，终于在建立一个开放的p k i 体系方面获得了重要的进 展，政府p k i 体系为联邦政府与公众机构、商业机构等进行电子数据交换提供信 息安全的保障，从而推动了政府内部管理电子化的进程。与f p k i 相比，g o cp k i 体系结构要简单得多。g o cp k i 充分考虑了交易的私密性和安全性，并把保护 交易私密性和安全性列为信息高速公路的首要阿题。它提供了完全一致的密钥管 理办法，并为加密和数字签名提供完全相同的验证过程，它是电子认证、鉴别和 智能卡等多项技术的集成。 我国数字证书认证体系目前在许多地方已经进入了应用领域的拓展和数字 证书的推广阶段。推广的办法是通过实现网上工商、网上税务等方式，将企业用 户的数字认证应用推进到实质阶段。例如有了网上工商，企业在完成年审后即可 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 实现网上缴费；有了税务和网上纳税企业的信用体系，那么该企业的资金就可以 通过支付网关到达金融部门，完成交税过程。而网上支付系统就要依赖基于合法 数字认证中心提供的企业用户的网上身份识别技术和支付款的确认。 但是现在在我国，c a 技术真正得到应用的还是工商、税务、网站、金融、 海关、对外进出口、电信这几大领域和部门，个人应用的需求量极小。这是和我 国互联网发展水平相对应的，也是国内外c a 存在差距的根本原因。 2 p k i 技术新变化 随着p i e d 技术应用的不断深入，p k i 技术本身也在不断的发展与变化，近年 来比较重要的变化有以下几个方面： 属性证书。x 5 0 9 v 4 增加了属性证书的概念。为了使附加信息能够保存 在证书中，x 5 0 9v 4 中引入了公钥证书扩展项，这种证书扩展项可以保 存任何类型的附加数据。 漫游证书。它通过第三方软件提供，只需在任何系统中正确配置，该软 件( 或者插件) 就可以允许用户访问自己的公钥，私钥对； 无线p k i ( w p k i ) 。将p k i 技术直接应用于无线通信领域存在两个方面的 问题：首先，无线终端的资源有限( 运算能力、存储能力、电源等) ；其 次，通信模式不同。为适应这些需求，目前已公布了w p k i 草案，其内 容涉及w p k i 的运作坊式、w p k i 如何与现行的p k i 服务相结合等等【5 】。 3 p k i 标准化工作 从整个p k l 体系建立与发展的历程来看，与p k i 相关的标准化工作主要包括 以下几个方面： x 2 0 9 ( 1 9 8 8 ) a s n 1 基本编码规则的规范。a s n 1 是描述在网络上传输信 息格式的标准方法。它有两部分：第一部分0 s o8 8 2 4 i t ux 2 0 8 ) 描述信 息内的数据、数据类型及序列格式，也就是数据的语法；第二部分( i s o 8 8 2 5 i t ux 2 0 8 ) 描述如何将各部分数据组成消息，也就是数据的基本编 码规则； x 5 0 0 ( 1 9 9 3 ) 信息技术之开放系统互联：概念、模型及服务简述。x 5 0 0 是一套已经被国际标准化组织( i s o ) 接受的目录服务系统标准，它定义了 一个机构如何在全局范围内共享其名字和与之相关的对象； x 5 0 9 ( 1 9 9 3 ) 信息技术之开放系统互联：鉴别框架。x 5 0 9 是由国际电信 联盟( i t u t ) 带4 定的数字证书标准。在x 5 0 0 确保用户名称唯一性的基础 上，x 5 0 9 为x 5 0 0 用户名称提供了通信实体的鉴别机制，并规定了实 体鉴别过程中广泛适用的证书语法和数据接口。 p k c s 系列标准。由r s a 实验室制定的p k c s 系列标准，是一套针对p i e d 4 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 体系的加密解密、签名、密钥交换、分发格式及行为的标准，该标准目 前已经成为p k i 体系中不可缺少的一部分； o c s p 在线证书状态协议。在线证书状态协议( o n l i n ec e r t i f i c a t es t a t u s p r o t o c o l ，o c s p ) 是m t f 颁布的用于检查数字证书在某一交易时刻是否 仍然有效的标准。 l d a p 轻量级目录访问协议。轻量级目录访问协议( l i g h t w e i g h t d i r e c t o r ya c c e s sp r o t o c o l ，l d a p ) 规范( r f c l 4 8 7 ) 简化了笨重的x 5 0 0 目 录访问协议，并且在功能性、数据表示、编码和传输都进行了相应的修 改。嘲 1 4s p k i s i ) s i 的研究现状 针对基于x 5 0 9 标准的传统p k i 的全局命名机制和缺乏访问控制支持等问 题，1 9 9 6 年m i t 的r p n a l dr i v e s t 、b u t l e rl a m p s o n 等提出了一种新的公钥基础 设施，称为“简单分布式安全基础设施( s d s i ) ”。它的特点是具有分布式的名字空 间，也就是公钥的拥有者能够创建相对于该公钥的本地名字空间，这种名字空间 可以灵活高效地组成名字链，可以定义“组”。与此同时，c a r le l l i s o n 、b i l lf r a n t z 等提出了令一种新的公钥基础设施，称为“简单公钥基础设施( s p k i ) ”。它强调的 是简单的设计、灵活的授权。 因为s d s i 和s p k i 的提出都是为了克服基于x 5 0 9 标准的p k i 的复杂性和 缺乏灵活性，由于这两种p k i 的相似性，想在它们合并成为了一个共同的规范， 称为s p k i s d s i2 0 。1 3 7 这些学者认为传统p k i 过于复杂且不完备，他们致力于提供一种有效的、完 整的、自然的、直观的公钥构架。他们最初集中精力想创造一种根据管理者的安 全策略的、易用的、用于创建安全分布式系统的p k i ，同时授权也加入到 s p k i s d s i 中，并且成为了其中的种核心部分。 s p k i s d s t 自从提出之后，国内外一些学者对其进行了研究，特别是美国的 m i t 和芬兰的h e l s i n k i 的研究生，他们针对s p k i s d s i 的一些研究工作主要集中 在以下一些方面： 1 证书的结构和生成 2 基于s p k i s d s i 证书的访问控制方法 3 s p k s d s i 中的证书链搜索算法。其中牵涉到证书集的化简问题。 4 基于s p k i s d s i 证书的访阿控制系统的实现。 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 1 5 课题背景及本文的主要工作 本文来源于某部“十一五”重点课题“x x x x x ”中的关键技术之一。主要 对非阻塞算法进行研究，并将其应用到一个安全的文件访问控制系统中。采用基 于s p k i 证书的访问控制方法来确保系统的安全性。论文所做的主要工作包括以 下一些内容： 1 对j a v a5 0 中新引入的j a v a u t i l c o n c u r r e n t 包进行研究，设计并实现了 堆栈数据结构中的入栈和出栈操作以及链表数据结构中的插入元素和 删除元素的非阻塞方法。通过j i j 血编写继承于t e s t c a s e 的测试类和 j s r l 6 6 开发组开发的测试工具类对实现的非阻塞方法进行正确性测 试；同时与传统的基于锁的同步的方法进行效率方面的对比，得出相 应的结论。 2 为了实现一个安全文件访问控制系统，需要将s p k i 证书引入到访阎控 制系统中的权限认证中。将s p k i 作为一种p k i 与传统的p k i ( 基于 x 5 0 9 标准的p k i ) 进行比较，详细地分析了传统p k i 的局限性，讨论 了新型p k i s p k i 的特性，指出s p k i 克服了传统p k i 的缺陷。 3 在m i t 的j s d s i 包的基础上对s p k i 证书的原理、结构和实现进行研 究，设计实现了用户持有的属性证书和资源所持有的策略证书。 4 对属性证书五元组结构的缩减方法进行研究。提出基于c o l l e c t i o n 和 h a s h m a p 的缩减方法，通过模拟证书集对三种方法进行效率上的对比。 5 设计一个基于j s p 以及s c r v l c t 的w e b 安全文件访问控制系统，并发控 制模块所采用的是非阻塞方法，而系统采用了s p k i 证书来保证访问的 安全性。 1 6 本文的内容结构 本文共分为六章，具体内容安排如下： 第一章中主要研究了并发程序以及非阻塞算法的研究现状；讨论了安全的文 件访问控制系统中安全性传统的实现方式，并提出了p k i 的概念：接着详细说明 了p k i 的发展现状和标准化的工作，以及s p k i 研究中的主要热点问题，最后提 出了本文的主要工作和内容结构。 第二章对并发控制进行全面的介绍。从并发的历史到多处理器的出现，详细 地分析了并发程序与传统的顺序执行的程序相比的优势。在得出优势的同时也分 析了线程潜在的危险因素。为了避免传统并发控制算法中所存在的问题，引出了 非阻塞的概念，研究了非阻塞算法的原理和实现的基本方法。 6 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 第三章讨论了传统的p ) ( 5 0 9 安全机制的概念以及存在的一些局限性。全 面重点介绍了s p k i 证书的概念和理论，分析了s p 的特点，这是后续章节的 基础知识。 第四章首先用j a v a 实现了基于堆栈和链表的非阻塞方法，通过j u n i t 编写测 试类，对于非阻塞算法进行正确性方面的验证以及与传统的基于锁的同步方法进 行效率上的对比，得出了相应的结论。最后讨论了非阻塞算法实现中必须要考虑 的a b a 问题，并就避免a b a 问题的发生提出了一些方案。第二部分辅助性地 研究了系统所采用的属性证书和资源策略证书的格式和内容；分多种情况讨论了 证书的颁发过程；对于证书链搜索中的属性证书五元组化简的问题进行了研究， 在前人研究的关于名字证书闭包缩减算法的基础上实现了基于单c o l l e c t i o n 、双 c o l l e c t i o n 和h a s h m a p 的属性证书五元组的缩减方法，并通过构造一些不同证书 数量和密钥数的模拟证书集对三种算法进行了效率上和正确性方面的对比。 第五章利用第二章和第三章的基础知识以及第四章中讨论的实现细节，结合 流行的基于j a v a 的多项技术，设计和实现了一个基于w e b 的安全文件访问控制 系统，该系统采用了非阻塞方法代替传统的基于锁的机制，实现了对文件访问系 统不同粒度的并发控制功能；s e r v l e t 和j a v a b e a n 的设计与实现；以及对s p k i 证书所做的辅助性研究进行实现，主要工作为：基于关系数据库的证书存储；属 性证书和策略证书的颁发过程；证书链的缩减算法。 第六章为对全文所做工作进行的总结，并提出了将来需要进一步研究的内 容。 7 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 2 线程的研究 编写一个正确的程序难，编写一个正确的并发程序更难。并发程序比顺序执 行的程序更容易出错。既然这样，我们为什么要使用并发程序呢? 线程是j a v a 语言中不可缺少的特征，它可以通过将复杂的不同步的代码转化为简单的排成队 列的代码来简化复杂系统的开发。另外，线程是实现对多处理器系统的计算资源 的优化分配最简单的方式。同时，随着处理器数量的增加，高效地开发并发程序 会变得越来越重要。 2 1 并发的发展 在过去很长一段时间内，计算机中不存在操作系统；计算机从开始到结束都 执行一个单一的程序，在执行的过程中，程序独自享有计算机的所有资源。不仅 编写一个运行在裸金属上的程序很困难，而且在一个时刻只运行一个单一的程 序，对于昂贵且稀有的计算机资源的使用也是效率低下的。 操作系统的出现和发展使一次可以运行多于一个的程序，以进程的形式运行 独立的程序，这个过程是隔离的，独立地使用操作系统分配的资源诸如内存、文 件句柄和安全证书来执行程序。如果需要，进程可以通过多种不同的通信机制： s o c k e t 、信号手柄、共享内存、信号量和文件来与其他进程进行通信。 操作系统允许多个程序同时地运行，许多因素激发促进了操作系统的发展： 资源利用率。程序在执行过程中通常要等待外部的操作，例如：输入或输出； 在等待的这段时间，此程序不能进行任何有用的工作。如果使用这段时间来运行 其他程序，将使资源利用率和程序运行的效率都有所提高。 公平性。多个用户和程序都有平等的获得机器资源的权利。用户和程序通过 一种恰当粒度的时间片来共享计算机资源，显然要比一个程序执行完再执行另外 一个程序的方法更好。 方便性。编写许多程序，其中每一个程序完成一个单独的任务，并且与一些 必要的其他程序并列，这种方式和写一个单独的程序来完成所有任务的做法比起 来更简单，更让人满意。 在早期的基于时间共享的系统中，自从n e u m a n n 计算机以来，每个进程都是 虚拟的，计算机用一个内存空间来存放指令和数据，根据机器语言的语义学来顺 序执行指令，且通过操作系统中的i o 集合与外部世界进行交互。对于每一条执 行的指令，必定存在一条定义清楚的“下一条指令”，并且根据指令集的规则来控 制程序的执行。现代所有被广泛使用的编程语言都遵循这种顺序执行的模型，也 就是说在这样的语言中，一个指定的动作执行完后，系统中已经定义好了”接下 硕士论文 非阻塞算法在安全文件访问控制系统中的研究与应用 来将要发生一些什么”。 顺序化编程模型是人们很容易想出来，这种模型的工作方式和人类的工作有 类似之处：在一个时间段只做一件事，尽可能地按顺序做事情。起床，穿上睡衣， 下楼开始喝茶。在编程语言中，每个真实世界发生的事件都可以抽象为一个顺序 执行昀指令集。选择一种风味的茶，然后取出一定量放在壶中，看茶壶中是否有 足够的水，如果没有足够的水，将茶炉打开，等待水烧沸腾，等等。最后一步等 待水烧开的过程同样包含一定程度的不同步：在水加热的过程中，你可以选择等 待，或者开始做其他一些事情，例如：烤面包( 另一个不同步的任务) 或者取报纸 来阅读，同时也要注意到正在烧的开水。茶壶和面包烤箱的生产者知道他们的产 品经常在非同步的方式下工作，所以他们在完成任务的时候增加了可以听见的声 音信号。在顺序编程和非同步编程之间寻找一种正确的平衡是一个做事效率高的 人的一种特征，在程序中，这个结论同样成立。 促进进程发展的一些因素( 资源利用率、公平性和方便性) 同样在激发线程的 发展。线程共享进程范围内的资源：例如内存和文件句柄；但是每个线程都有自 己的程序计数器、堆栈和局部变量。线程也提供一种在多处理器系统中开发硬件 并行性的自然分解方法，同一个程序的多个线程可以同时被多个c p u 预定。 线程一般被称作轻量级进程，大多数现代操作系统因为时序处理基本单元处 理的是线程而不是进程。在缺少外界调和的情况下，线程在考虑其他线程的情况 下同时但不同步地执行。因为线程共享他们所属的进程的内存地址空间，一个进 程的所有线程都访问相同的变量和从同一个堆中分配对象，要求一个合适粒度的 数据共享。但是缺少外在同步的对共享数据的同等访问的情况下，一个线程可能 修改一个另外线程正在使用中的数据，这将导致不可预测的结果。【3 5 l 2 2 线程的优点 如果我们使用得当，线程可以减少开发和维护的成本，并且可以改进复杂应 用程序的性能。线程可以将不同步的工作流转化为普通的顺序指令集，使我们更 容易对人类如何进行工作和相互交流进行建模。线程同样可以将令人费解的代码 转化为直接的简单代码，这样可以更容易编写、阅读和维护程序。 在g u i 应用程序中，线程可以对用户接口的响应做出改进，在服务器应用程 序中，可以改进资源的利用率和提高系统的吞吐量。线程同样可以简化j a v a 虚 拟机上垃圾回收器的执行，垃圾回收器通常运行在一个或多个专用的线程上。大 多数不平凡的j a v a 应用程序都依赖于自身体系结构中线程的度数。 9 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 2 2 1 开发多处理器 多处理器系统曾经是昂贵和稀有的，一般在大型数据中心和科学计算设备才 会拥有。现在，多处理器系统变得便宜，也大量出现，这种趋势会不断加速，因 为增加时钟频率已经变得越来越困难，处理器制造商将在一块单一的芯片上放置 多个处理器核心来提高处理器的性能。所有主要的芯片制造商都开始了这样的转 变，具有多处理器的机器已经问世。 因为时序安排的基本单元是线程，一个仅有一个线程的程序在某个时刻只能 运行在一个处理器上。在有两个处理器的系统中，单线程的程序放弃使用5 0 可用的c p u 资源；在有1 0 0 个处理器的系统中，放弃使用的比例将达到9 9 。 另一方面，拥有多个活动线程的程序可以同时在多个处理器上运行。如果设计正 确的话，多线程的程序可以通过更有效地年o 用处理器资源来提高系统的吞吐量。 在单处理器的系统中，使用多线程同样可以达到更好的吞吐量。如果一个程 序是单线程的，在线程等待同步的i o 操作完成时，处理器保持空闲。在多线程 的程序中，当第一个线程等待i o 操作完成时，另一个线程仍然可以运行，这样 在阻塞v o 时，系统的完成进度在不断地向前( 这正如在烧开水的同时阅读报纸， 而不是等待水烧开后才开始看报纸) 。 2 2 2 简单建模 如果你仅仅只有一种类型的任务要完成( 例如修复1 2 个b u g s ) ，这种情况和有 多种类型的任务需要完成( 例如修复b u g s 、面试系统管理员的候选者等等) 的情况 比起来更容易进行管理。如果你只有一种类型的任务需要去做，从堆的顶部开始， 直到堆已经耗尽了才停止工作；在这个过程中，你不需要花费精力指出下一步该 做什么。另一方面，管理多种优先权和最后期限以及从一个任务切换到另一个任 务通常会带来许多系统开销。 这对于软件开发来说同样成立：一个仅仅顺序处理单一类型任务的程序一般 与需要一次管理多种不同类型任务的软件相比，编写简单，不容易出错，且测试 相对容易。操作系统为每个任务类型或模拟的元素分配一个线程可以提供一种认 为程序是顺序执行，以及从计划的细节，交错操作，异步v o 和资源中隔离定义 域的逻辑的错觉。一个复杂、不同步的工作流可以被分解为多个简单的同步的工 作流，每个工作流都运行在独立的线程上，在定义的同步点与其他线程进行交互。 上述的一些优点经常在一些框架结构，例如s e r v l e t 或者r m l ( r e m o t em e t h o d l n v o e a t i o n ) q ，体现出来。这些框架结构处理请求管理、仓u 建线程以及负载平衡的 细节问题，在工作流中，对在适当时间点上对于合适的应用程序组件的请求处理 1 0 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 进行调度分配。s e r v l e t 的编写者不需要考虑在同一时刻有多少请求需要处理，也 不需要考虑s o e k d 输入和输出流是否阻塞；一个s e - r v l e t 的服务方法通常称作是 对一个来自w e b 的请求的响应，如果这是一个单线程的程序，程序可以同步处 理请求。这样可以简化组件的开发以及减少学会使用这种框架所用的时间。 2 2 3 简化非同步事件的处理 开发一个可以从多个远程客户端接受s o e k e t 连接的服务器程序比为每个连 接分配各自的线程，同时允许线程使用同步v o 的程序简单。 如果一个程序需要从s o e k e t 接口读取数据，但此时没有任何数据可用，在有 数据可用之前，读取进程会阻塞。在一个单线程的程序中，当单个线程被阻塞时， 这种做法不但将相应的请求阻塞，而且还会将其他所有的请求都阻塞。为了避免 这样的问题，单个线程的服务器程序选择使用非阻塞i o ，与阻塞i o 比起来， 非阻塞i o 更复杂且更容易出错。因此，如果每个请求都有各自的线程，那么对 某个线程的阻塞不会影响到其他线程的执行。 从历史的角度来看，操作系统对于处理器可以创建的线程数量做了一个相对 较低的限制，这个数量一般在数百( 甚至更少 。结果，操作系统为多路复用f o 开发了高效的功能，例如u n i ) 【下的选择和轮询系统调用，为了使用这种功能， j a v a 类库中为非阻塞f o 设计了一系列的包o a v a t o o ) 。可是，操作系统支持数量 很多的线程数是很重要的，对于数量很多的在许多平台上的客户端情况，为每个 客户端分配一个线程的模型是实用的。 2 2 4 更多做出响应的用户接口 g u i 应用程序一般是单线程的，这意味着要么通过代码对输入事件进行频繁 的轮询，要么就通过“主要事件循环”的方式间接执行所有程序的代码。如果从主 要事件循环中的代码调用需要花费很长时间去执行，用户接口表现为“冻结”，直 到这段代码完成执行，因为随后的接口事件直至上一个事件的控制信息从主要事 件循环返回后才能够被处理。 现代g u i 框架，例如a w t 和s w m g 工具包，采用事件调度线程( e d t ) 来取 代以前所采用的主要事件循环。当一个用户接口事件，例如用户按下按钮，程序 在事件线程中所定义的事件处理程序将会被调用。大多数g u i 构架是一个单线 程的子系统，所以主要事件循环的方式仍然是有效的，但是在g u ii 具包的控 制而不是应用程序的控制下运行在自身的线程上。 如果只有短任务在事件线程上运行，因为事件线程可以比较快地处理完用户 的行为，所以接口保持对用户事件的响应。可是，在事件线程中处理一个长任务， 硕士论文非阻塞算法在安全文件访问控制系统中的研究与应用 例如：在一个大文档中进行拼写检查操作或者通过网络获取资源，这样就会削弱 系统的响应能力。如果用户要执行一个动作，而这个动作正在运行中，那么需要 一个很长延时，事件线程才可以处理或者接受这个用户的请求。但是令人伤心的 是，不但u i 的响应能力下降，而且尽管u i 提供了取消按钮，用户想取消这种不 愉快的任务还是不可能的，因为事件线程正在运行中，不能处理取消按钮定义的 事件，直至先前的任务完成了，系统才会对取消按钮的事件进行响应。可是，如 果将运行事件较长的任务分解为许多独立的线程，事件线程会保持空闲处理来自 u i 的事件，这样可以提高系统的响应能力。 3 3 1 2 3 线程的风险 j a v a 内在支持线程可以说是把双刃剑。通过提供语言和类库以及规范跨平台 内存模型( 正是因为这种跨平台性，可以使得j a v a 语言具有一次编写，到处运行 的特征) ，可以简化并发应用程序的开发过程，同时因为许多程序会用到线程， 这样对程序员提出了更高的要求。因为线程理论是深奥的，所以并发是一个很先 进的科研主题；现在，主流的程序员必须对线程安全的理论有所了解。 2 3 1 影响安全的因素 线程的安全性一般是出乎意料地敏感，因为在缺乏足够同步的环境中，在多 线程中操作的顺序通常不可预测和令人惊讶。表2 3 1 1 中展示的 u n s a f e s e q u e n c e ，目的是产生一个唯一的整数数值的序列，并一个简单的例子说 明了在多线程的系统中，行为之间的交互可能导致无法忍受的结果。在单线程的 环境中，这个程序可以正确地运行，而在多线程的环境中则不行。 表2 3 1 1 线程不安全的序列生成器 n o t t h r e a d s a f e p u b l i cc l a s su n s a f e s e q u e n c e p r i v a t ei n tv a l u e j i + + r e t u r n sau n i q u ev a l u e + p u b l i ci n tg e t v a l u e ( ) r e t u r nv a l u e + + j 在一些不幸运的时刻，上述程序可能会发生问题，两个线程可以调用g e t v a l u e 并且返回一个相同的值。图2 3 1 1 展示了问题发生的过程。增加的操作，v a l u e + + 表面上看起来是一个单一的操作，但是实际上是三个独立的操作：读取原值，在 原值上加1 ，写回新值。因为在多线程的环境中，在运行时刻操作有可能被任意 硬_ 士豫文非驻糕算法在安全文锌访羯控铡系统孛麴蘸究与应焉 交鬣，所以有可能出现以下的情况；两个线稷同时读取v a l u e 的值，它们读取至4 的值熙一样的，然后每个线程都