分布式系统与WEB服务5

第三章分布式系统的同步

和进程

3．1时钟同步

分布式算法的主要特征：

①相关信息分布在多台机器上

②进程仅依据局部的信息作出决定③一台机器的故障不应引起整个系统的失败④没有共用的全局时钟。

1．逻辑时钟先看一个例子:06121824303642485460081624324048566472800102030405060708090100ABCD三个有自己时钟的进程,时钟不同

运行的结果是消息C在时间60上被发送,却在时间点54上到达Lamport的算法以”先于”关系为基础，每个消息都携带它的发送时间,当它到达目的地时，如果目的地的时间早于它的发送时间，那么就把目的地的时间向前拔,至少要比发送时间大1个单位.0612182430364248707608162432404861697785800102030405060708090100ABCD用Lamport的算法纠正时钟

该算法解决了全局时钟问题，它的条件就是两个相关事件之间必须至少相差一个时间

2．时钟同步算法逻辑时钟只给出事物的相对时间,与真实时间并不对应,故要引入外部物理时钟,常用的时钟同步算法:①克里司帝安(CRISTIAN)算法具有国家标致时间接收器的机器,注意:调整的方法,通过调节单位时间内的中断的时间,来逐步完成时钟的调整.

②

伯克利算法计算平均时间,它是一个集中式算法,不能在大规模的分布式系统中使用原理:定期轮询每台机器的时间,由结果计算平均时间,各机器依此调整时间.

3．同步时钟的具体使用①至多一次消息传送

消息的时间戳比存储的时间戳的值早,就拒绝接受该消息

②

基于时钟的缓冲存储器（CACHE）的一致性使用CACHE会出现一致性问题，原解决的方法:区分读写缓存,现在可用同步时钟来解决。即通过提供有效期（利用有效的租约）来控制CACHE一致性问题。3.2互斥操作

有多个进程的系统经常会碰到临界区的操作。当一个进程要访问某个共享数据时，它要先进人临界区进行互斥操作，确保没有别的进程同时访问该数据。在单机系统中，临界区可以用信号灯、管程来实现。那么在分布式系统中，由于不能共享主存，怎么实现临界区和互斥操作呢?下面我们讨论几种算法。①集中式算法该方法就是模拟单机系统,指定一个管理员进行许可管理,该算法保证了互斥,每个临界区只需三条消息(申请,许可,释放)102OK请求C管理员队列空管理员102不回答请求C队列空102OK释放C管理员队列空2(A)进程1向管理员请求进入临界区,得到许可(B)进程2向管理员请求进入临界区,管理员不回答(C)进程2向管理员请求进入临界区,管理员许可缺点:集中式算法管理员是系统的瓶颈②分布式算法算法的条件:系统中的事件必须有全局的顺序

算法的工作过程如下:

当一个进程要进入临界区时，它构造一条包括临界区名、进程号和当前时间的请求消息，然后把该消息广播给其他的所有进程。这里假设，消息的发送是可靠的。当一个进程收到请求后，根据它的状态采取相应的动作：

(1)当接收者不在临界区，并且也不想进入临界区，就应答发送者OK消息。

(2)如果接收者已经在临界区中，它不回答．仅仅把请求加入队列。

(3)如果接收者不在临界区，但它也想进入临界区，就要将收到消息的时间戳和它广播消息的时间戳比较.如果到来的消息时间戳早，接收者回答发送者OK消息；反之接收者把到来的请求加入队列，不回答.在发完完进入入临界界区请请求后后，进进程将将等待待所有有的允允许消消息，，一旦旦得到到许可可，就就可进进入临临界区区，当当退出出时向向队列列中的的所有有进程程发OK消息，，并将将它从从队列列中删删除。。所有进进程都都要参参与决决定是是否进进入临临界区区，若若有进进程不不能做做，算算法将将出错错。由于所所有进进程都都要参参加算算法，，所以以比集集中式式算法法慢，，复杂杂，开开销大大。改进算算法：：不需所所有进进程同同意，，部分分回答答OK即可③令牌环环算法法进程只只有拥拥有令令牌时时,才能进进入临临界区区,一个进进程从从相邻邻的进进程收收到令令牌时时先检检查自自己是是非要要进入入临界界区;如果要要,就进入入,否则就就将令令牌传传递给给下一一个进进程.缺点:令牌可可能丢丢失且且检测测困难难，一一个要要进入入临界界区的的进程程最差差情况况下要要等待待其他他进程程进入入和退退出临临界区区所用用时间间总和和④三种算算法的的特点点比较较集中式式算法法简单单、高高效，，每次次进入入和离离开临临界区区只需需3次消息息传递递：请求、、许可可；释释放，分布布式算算法中中，n个进程程需要要(n-1)个请求求和(n-1)个许可可，总总共要要2(n—1)个消息息。在在令牌牌环算算法中中，所所需的的消息息数是是不固固定的的。如如果每每个进进程都都要进进入临临界区区，那那么每每个令令牌都都有一一次进进人和和退出出，平平均每每次进进入有有—个消息息传递递；如如果令令牌被被一个个进程程占有有很长长时间间，那那么进进入临临界区区需要要的消消息就就不确确定。。进程从从它发发出进进入临临界区区的请请求到到它进进入临临界区区的时时间延延迟在在三个个算法法中是是不同同的,当临界界区很很短并并且使使用频频率很很低时时，进进入临临界区区时间间延迟迟的决决定因因素是是进人人临界界区的的控制制机制制．当当临界界区很很长并并且使使用的的频率率很高高时，，决定定因素素在于于等待待时间间，消消息数数就能能说明明这一一点。。这三种种算法法出现现故障障时,都会有有很大大影响响,要避免免系统统的崩崩溃,须注意意:在容错错系统统中,次三种种算法法都不不适用用.3.3选举算算法在分布布式系系统中中，大大多数数算法法要求求有一一个进进程充充当管管理员员或初初始启启动者者等特特殊角角色。。前面面几个个算法法就有有这样样的例例子。。一般般来说说，由由哪个个进程程充当当特定定角色色无关关紧要要，但但是必必须有有一个个进程程做这这个工工作。。下面面我们们来看看如何何选一一个进进程担担当特特定角角色。。选举算算法的的目的的是当当选举举完成成后，，能够够让所所有的的进程程知道道谁是是管理理员.1.霸道算算法该算法法提出出。当当一个个进程程P注意到到管理理员不不再对对请求求作出出反应应时，，它就就开始始选举举．进进程P执行下下列步步骤：：(1)向所有有进程号号比它它大的进程程发送送ELECTION消息；；(2)如果没没有进进程响响应，，进程程P成为管管理员员；(3)如果有有进程程响应应，该该响应应进程程成为为管理理员，，P结束选选举。。注意：：一个进进程只只能从从号码码比它它小的的进程程处得得到一一个选选择消消息20536417(A)进程4启动选举20536417(B)进程5,6响应,让4停止20536417(C)进程5,6,都启动动选举举20536417(D)进程6让进程程5停止选选举20536417(E)进程6成为管管理员员,发通知知霸道算算法图图示2.环形算法法这个算法法使用环环，但不不是令牌牌环。这里假定定所有的的进程都都是有序序号的，，即每个个进程都都知道它它的后继继进程。。当一个个进程发发现管理理员不能能工作时时，它把把包含其其进程号号的ELECTION消息发给给它的后后继进程程；接收收消息的的进程再再向后继继进程发发送ELECTION消息。如果接接收进程没有有反应，发送送消息的进程程便向下一个个进程发消息息。每一次发发送ELECTION，进程都要将将自己的进程程号加入消息息。20465137使用环形选举举算法选举消息选举消息232556560出现故障的管管理员最后，第一个个发出该选举举（ELECTION）消息进程收收到该消息,再将其转换为为协调（COORDINATOR）消息后，再再循环一周,通知谁是管理理员，谁是组组成员，这时消息包中中进程号最高高的进程将成成为管理员。。当这个消息循循环一周后，，由发送进程程把它从网上上清除。图中2和5都发现7失效，分别建建立选举消息息，两条消息息都沿环运行行，结果是一一样的，只是是浪费了带宽宽。3．4线程进程因等待而而挂起,使进程中可并并行部分不能能执行,从而使系统性性能下降,故引入---线程.1.线程：就是可可以共享地址址空间的轻型型进程，它有有自己的程序序寄记数器栈栈和寄存器集集合。它与进程的主主要区别是它它的地址空间间是共享的。。线程相对于进进程，犹如进进程相对于机机器2.线程的使用，，将并行性引引入到顺序执执行的系统.多线程组织的的常用模型：：1)分配器／工作作者模型有一个分配器器线程唤醒工工作者线程可可用信号灯2)团队模型地位平等线线程各自获取取和处理自己己的请求.3)流水线模型管道线模型，，第一个线程程产生一些数数据传给下一一个线程处理理，且持续下下去。多线程可分时时工作在单CPU上也可工作在在多处理器系系统上,而且多线程系系统设计的好好将可与多处处理机工作性性能相当.共享缓冲区到达的工作请求邮箱文件服务器进程分配器线程工作者线程到达的工作请求到达的工作请求内核分配器/工作者模型流水线模型团体模型进程中线程三种组织方式3.线程包的设计计的相关问题题线程包就是供供用户或程序序员调用的关关于线程的一一组原语。线程的管理方方法有静态和和动态方法两两种。静态即开始就确定定好线程的个个数，动态个数不定线程的代码与与进程一样，，由多个过程程组成。线程包中临界界区控制利用用互斥体（mutex),其总处于：打开和锁住两两种状态lockmutex;checkdatastructureslockmutexwhile(resourcebusy)markresourceasfree;wait(conditionvarable);unlockmutex;markresourceasbusy;wakeuo(conditionvariable);unlockmutex;互斥变量与条条件变量的使使用线程可由算法法进行调度，，如优先级调调度、循环调调度等4.线程包的实现现在用户空间实实现线程（如如图）这种方法是将将线程包完全全放在用户空间，内核对此一一无所知，在在这种方法中中，内核只是是管理普通的的单线程进程程。这种方法法最明显的优优点是它可以在一一个不支持多多线程的操作作系统上实现现用户线程包包。同时它还还允许每个进进程有自己特特定的调度算算法.线程1线程2线程3线程4线程5线程6运行期系统内核内核空间用户空间缺点是：数量太多会引引起资源紧张张.同时(1)它也难实现阻阻塞系统的调调用.(2)它的调度是非非抢先式的.进程内部无时时钟中断,无法进行时间间片的调度.2)在操作系统内内核实现（如如图）不需要运行系系统,线程创建或撤撤销,只需一次系统统调用,比在用户空间间实现线程开开销大.可通过在撤销销时加标记，，当做为新线线程创建时仅仅需激活即可可。线程1线程2线程3线程4线程5线程6内核用户空间内核空间3)调度员活动方方法结合前两种的的优点(用户线程的高高性能和内核核线程的实现现简单)原理：当使使用调度员员活动方法法时，内核核给每个进进分配一些些“虚处理器”，并由运行行系统分给给线程，同同时通过避避免在用户户空间和内内核空间之之间的不必必要的转换换来实现高效率。如：线程在局部部信号上阻阻塞并不去去涉及内核核，而是由由用户运行行期系统去去完成阻塞塞和调度。。具体是由内核激活用用户运行期期系统4)线程和RPC希望使一个个进程中的的线程可以以有效的调调用同一台台机器上的的另一个进进程中的线线程，具体采用与RPC相似的过程程完成。加速RPC执行的技术术，具体即即为当一个线程程执行请求求时，它将将消失并且且它的堆栈栈和环境信信息也丢弃弃，当有新新的消息进进入时，内内核动态创创建一个新新线程去为为其服务。。优点首先线线程不用等等待所以不不保留环境境，其次创创建新线程程比存储一一个存在的的线程花费费少，节约约了时间减减少了开销销，从而提提高了速度度。3．5分布式系统统模型1．工作站模模型其主要指：：一组工作作站通过高高速局域网网互连，在在某一时刻刻,每台机器只只有一个用用户登录，，即拥有者者，要么空空闲。优点：清晰晰、、易易于于理理解解，，计计算算能能力力固固定定、、系系统统反反应应时时间间固固定定、、有有一一定定的的自自主主性性、、同同时时增增强强了了独独立立性性。。缺缺点点:资源源存存在在浪浪费费,资源源利利用用率率不不高高.2.空闲闲工工作作站站的的使使用用1）找找出出空空闲闲工工作作站站两种种定定位位方方式式：：服服务务器器驱驱动动和和客客户户端端驱驱动动2）透透明明运运行行远远程程进进程程由内内核核完完成成3）机机主主人人重重新新使使用用时时如如何何处处理理直接接杀杀死死进进程程、、移移植植到到另另一一台台机机器器上上（（进进程程全全部部包包括括子子进进程程））3.处理理机机池池模模型型处理理机机池池是是无无盘盘工工作作站站的的进进一一步步发发展展。。理论论依依据据是是排排队队论论,具体体有有理理发发师师模模型型、、超超市市收收款款等等。。CPU根据据需需求求动动态态的的分分配配给给用用户户。。模模型型如如图图虽然然有有证证明明：用用一一个个是是小小系系统统功功能能N倍的的大大系系统统来来代代替替N个独独立立的的小小系系统统的的资资源源可可把把平平均均响响应应时时间间减减少少为为原原来来的的1/N倍。。文件服务器处理机池CPU然而而平平均均响响应应时时间间不不代代表表一一切切，，从费费用用角角度度来来看看，，不不惜惜代代价价建建造造巨巨型型机机甚甚至至是是不不可可能能的的。。同时时也也并并不不是是有有N个处处理理器器的的处处理理机机池池就就可可比比单单个个处处理理器器的的性性能能高高N倍，，而是是决决定定于于任任务务可可分分几几部部分分。。4.混合合模模型型用那那种种模模型型要要依依情情况况而而定定,若是是偶偶发发的的事事件件为为主主,则个个人人工工作作站站模模型型机机可可,若是是仿仿真真或或工工程程计计算算则则用用处处理理机机池池较较好好,也可可两两者者结结合合.3．6处理理机机分分配配与与调调度度如何何决决定定进进程程运运行行在在那那台台机机器器上上，，即即为为处处理理机机的的分分配配。。1.分配配模模型型1）分分配配策策略略有有两两大大类类:非迁迁移移的的（（进进程程创创建建后后，，一一直直呆呆到到进进程程结结束束））迁移移的的（（进进程程可可在在运运行行中中迁迁移移到到其其它它机机器器上上运运行行））2）分分配配算算法法的的目目标标：：(1)最大大限限度度地地提提高高CPU利用用率率(2)尽可可能能缩缩短短平平均均响响应应时时间间(3)最小化响应率率例如：有两个处理机机1及2和两个进程程A及BA（1亿条指令）10秒6秒B（3亿条指令）30秒8秒分配1：处理机1运行进程A，处理机2运行进程B，平均响应时时间为（10+8）/2=9秒（较优）分配2：处理机2运行进程A，处理机1运行进程B，平均响应时时间为（30+6）/2=18秒处理机机110MIPS处理机机2100MIPS5秒队列列2．设计计分配配算法法的主主要相相关问问题1）确定定式还还是启启发式式确定式式适用用进程程是否否可预预知;启发是是指以以经验验性规规则和和信息息指导导.2）集中中式还还是分分布式式依全局局信息息做判判定,以局部部信息息做判判断.3）最优优的还还是次次优的的4）局部部的还还是全全局的的解决转转移策策略5）发送送者初初启还还是接接收者者初启启解决定定位策策略3．处理理机分分配算算法实实现中中的问问题1）对负负载的的测量量2）额外外开销销的处处理3）问题的复复杂度4）稳定性问问题4．典型的处处理机分配配算法1)图论决策算算法2)集中式算法法（上—下算法）3)层次算法逻辑上构成成分层结构构4)投标算法把系统中的的资源和任任务作为买买方和卖方方以寻求平平衡.ABCDGIH22255811443ABCDGIH22255811443FFEE30单位通信量量28单位通信量量5．调度假设进程成成组创建,组间通信比比组内通信信要少,基于协同调度概念的算法法.算法使用一一个矩阵列是处理机机的进程表表行是时间段段的进程表表主要思想:每个处理机机采用时间间片轮转法法,因此可将进进程组的所所有成员放放在不同处处理机上的的同一时间间段××××××××××××××处理机时间片实现文件服服务的技术术对于分布布式系统的的设计非常重重要。在分布式系系统中，必必须提供与与传统文件件系统相当当的性能和和可靠性。。实现分布布式文件服服务器的技技术源自传统系统，但由于要要将许多设设施分布在在多个不同同的服务器器中，系统统结构有所所不同，因此，其技技术要求及及高于传统统系统。共享持久性分布式缓存/副本维护一致性例子主存×××1RAM文件系统×√×1UNIX文件系统分布式文件系统√√√√SUNNFSWEB√√√×WEB服务器分布式共享内存√×√√IVY远程对象√××1CORBA持久对象存储√√×1CORBA持久对象存储持久分布式对象存储√√√√PERDIS第四章分布式文文件服务务4．1引言文件被认认为是一一个基于于磁盘或或其它二二级存储储器的存存储结构构的抽象象。最简单情情况下，，文件定定义为数数据项的的序列，，文件系系统提供供按指定定位置读读／写文文件数据据项或子子序列的的操作。。有些文件件系统将将文件定定义成复复杂数据据结构的的集合(如记录等等)，可以用用记录的的键字来来定位。。在集中式式文件系系统中，，文件系系统可以以管理大大量的文文件，包包括读、、写或删删除等。。而目录录是一种种抽象的的文件管管理设施施，它能能将文件件名映射射到一个个文件指针针，这种映映射(即目录)一般以特特殊类型型的文件件存储，，若要访访问文件件，需要要首先打打开目录录。文件系统统要负责责文件共共享和访访问控制制的管理理，限定定用户的的访问权权限，为为每个文文件定义义访问类类型等。。文件系统统一般提提供以下下服务:文件组织织文文件件存储文件检索索文文件件命名文件共享享文文件件保护。。设计文件件系统的的目的，，是使程程序员可可以使用用抽象操操作来访访问磁盘盘空间，，传统文件件系统的的层次结结构如下下图所示示：文件系统统模块图图以上也同同样是分分布式文文件系统统的基础础.目录模块块:负责文件件名到文文件标识识的映射射文件模块块:负责文件件标识到到文件的的映射文件访问问:文件数据据、属性性的读写写访问控制制:操作的许许可性检检查盘块模块块:磁盘块的的分配及及访问设备模块块:磁盘I/O缓冲另外加上上:1.支持共享享信息的的管理不必先拷拷贝，再再访问，，永久性性数据管管理2.为用户提提供透明明的文件件访问服服务3.提供目录录服务提供文件件命名及及文件名名到文件件标识的的映射功功能4.事务服务务为用户提提供的最最高层服服务,提供并发发服务,保证文件件的一致致性综合而言言,分布式文文件可分分为三种种服务:目录服务务,文件服务务,事务服务务用户程序用户程序用户程序客户模块网络文件服务目录服务事物服务文件服务的RPC界面用户程序界面API目录服务的RPC界面事物服务的RPC界面4.2文件服务务在UNlX和DOS系统中，，文件是没没有任何何解释的的字节序序列，文文件的结结构和意意义完全全由应用用程序决决定，操操作系统统不关心心其结构构和意义义。但在某些些大型机机的操作作系统中中，有许许多不同同类型的的文件，，每种文文件具有有不同的的特性。。文件可以是一一组记录构成成的序列，该记录又可以以是复杂的结结构，这个结结构的意义是是由操作系统统解释的。这样，文件便便由数据和属属性构成，其其中，属性包包括文件长度度、访问时间间、访问控制制表和拥有者者，文件长度度和数据可为为用户使用，，其它属性均均为目录服务务使用，可以以将这种文件件看作一种文文件对象。关于文件的另另一个重要问问题是文件的的可修改性。。如果文件创建建之后，不能能再修改，则则称为不可修修改(Immutable)文件，否则称称为可修改(Mutable)文件。这里主要讨论论可修改的文文件。文件服务的模模型和任务对于一般的文文件服务而言言，有两种服服务模型1)装载／卸载(UpLoad／DownLoad)模型2)远程访问(RemoteAccess)模型在装载／卸载载模型中，文件服务仅提提供读文件和和写文件两种种操作。读操作用于将将整个文件从从服务器中完完全读出，写写操作用于将将整个文件从从客户机写入入服务器。在在这种模型下下，可以将文文件缓冲于客客户机的主存存或磁盘中，，其优点是概概念简单，应应用程序可以以局部拥有并并访问文件，，程序结束后后，必须将新新建或修改过过的文件写回回服务器。在在此，不需要要复杂杂的文文件服服务界界面，，整个个文件件的传传输是是高效效的。但是是，客客户机机必须须有足足够的的空间间来存存储所所需要要的文文件，，另外外，如果实实际上上应用用程序序作用用于文文件的的一小小部分分，就就会造造成很很大的的浪费费。在远程程访问问模型型中，，文件服服务将将提供供大量量的文文件操操作，，包括括打开开、关关闭读和写写等，，其优优点是是不需需要客客户机机具有有大量量空间间。另外外，当当应用用程序序只需需处理理文件件中少少量数数据时时，不不需要要将整整个文文件全全部拷拷贝到到客户户机上上去。。文件服服务的的任务务两个任任务：：文件件存储储和文文件寻寻址。。其中，，文件件寻址址利用用文件件位置置映射射方法法完成成文件件的定定位，，文件件访问问通过过调用用外存存访问问功能能完成成文件件的存存储，，外存存访问问功能能通常常以块块服务务的形形式提提供。。所以以，文文件服服务的的基本本任务务就是是，提提供通通用和和有效效的操操作集集合，，为多多个客客户提提供大大容量量的外外存设设备。。另外，，文件服服务还还要解解决保保护问问题，即严严格控控制用用户对对于文文件的的访问问，从而保保证文文件的的一致致性。。文件服服务可可以同同时支支持多多个目目录服服务，，这样样，目目录服服务可可以采采用多多种不不同语语法，，从而而使文文件服服务可可以用用于不不同的的目录录服务务。一一个文文件服服务可可能同同时管管理几几个目目录服服务支支持的的多个个文件件集合合，每每个集集合中中的文文件属属性记记录和和结构构可能能还有有差异异。文件服服务界界面所谓界界面，，主要要提供供服务务的基基本操操作名名和调调用格格式及及简单单功能能描述述。文件的的UFID；参数数;数据;出错信信息4.3目录服服务目录服服务定定义了了构成成文件件(或目录录)名的某某种字字母表表示语语法。。文件名名可以以是由由一个个或多多个字字符、、数字字及特特殊字字符构构成的的字符符串。。有些些系统统通过过句点点将文文件名名分成成两部部分，，如prog．c表示C语言文文件，，maim．txt表示文文本文文牛，，第二二部分分一般般叫做做文件件扩展展名。。分布式式系统统目录录一般般也都都包含含子目目录，，从而而使用用户可可以给给相关关文件件：分分组，，形成成层次次文件件系统统。因因此，，目录录服务务就包包括创创建、、删除除、进进入、、退出出和查查找文文件等等功能能。有的的系统统还提提供建建立目目录指指针的的功能能，指指针可可以设设置到到任何何目录录中，，这样构构成的的目录录和文文件就就不再再只是是树型型结构构，而而是图图(网状)结构，，从而而使表表示能能力更更强，，当然，，管理理也就就更复复杂。。设计分分布式式文件件服务务的关关键在在于，是否否支持持所有有机器器对于于目录录层次次具有有同样样的视视图。。目录服服务的的任务务大多多数数分分布布式式系系统统都都使使用用两级级命命名名方方式式，即即每每个个文文件件(或其其它它对对象象)都有有一一个个符符号号名名(常称称为为文文件件名名)和一一个个内内部部二二进进制制名名(用UFID表示示)。符号号名名一一般般供供程程序序员员或或用用户户使使用用，，如如prog.c；内内部部二二进进制制名名供供系系统统使使用用。。所谓谓目目录录，，就就是是一一组组文文件件名名到到UFID的映映射射表表。。目目录录服服务务最最基基本本的的任任务务就就是是将将文文件件名名映映射射到到UFID，通过过这这一一映映射射可可以以取取代代传传统统文文件件系系统统中中的的打打开开(Open)文件件操操作作，，客客户户一一旦旦拿拿到到UFID，便便可可以以操操作作文文件件.目录录服服务务本本身身要要确确保保UFID正确确送送到到请请求求客客户户。。目目录录服服务务还还要要检检查查客客户户的的合合法法性性，，通过过访访问问控控制制表表做做合合法法性性检检查查，最最终终决决定定是是否否发发出出一一个个UFID.目录录服服务务的的功功能能也也可可以以分分解解为为基基本本功功能能和和辅辅助助功功能能两两类类,基本功能能提供文文件名到到文件标标识的映映射，它它是构造造面向用用户的目目录服务务的基础础，包括括名字、、结构和和访问控控制方法法。根据据授权客客户的请请求允许许用户执执行UFID所指出的的文件增增、删操操作。辅辅助功能能包括文文件名的的词法分分析、建建立目录录形成层层次结构构和其它它复杂操操作。因因此，目目录服务务可以在在给定目目录中查查找文件件名，然然后得到到UFIO，每个UFID都指出对对于文件件的相关关访问权权限，如如对文件件拥有者者可读、、写和删删除，对对于其它它用户只只读。目录通常常以文件件形式存存储，因因此，目目录服务务本身是是文件服服务的一一个客户户，每个个目录本本身有一一个UFID。目录服务务界面目录服务务定义了了一组目目录服务务操作。。不同系系统有响响应的约约定.目录服务务的定义义遵循约约定记号号。文件属性性与目录录访问目录服务务要进行行访问控控制，可可以通过过访问和和更新文文件属性性完成。如可以以在新文文件名加加入目录录时，在在文件属属性中设设置访问问许可；；提供查查看文件件属性的的操作；；还可以以提供允允许文件件拥有者者认定或或重设其其它用户户的许可可权限、、及将所所有权转转让给其其它用户户的操作作。文件系统统除管理理数据外外，还要要管理许许多相关关信息，如创建建日期、、最后访访问日期期和最后后修改日日期、文文件类型型、文件件所属目目录和访访问控制制信息等等，我们们称这些些信息为为文件属属性。文件系统统将文件件属性作作为一组组不可分分解的数数据，文件属性性可以执执行读写写访问，，但没有长长度或结结构等操操作目录服务务不但要要确定属属性中的的内部结结构和所所存数据据值，还还要负责责文件属属性的访访问，包包括读取取和修改改。如改改变访问问日期、、修改文文件所属属关系和和管理访访问控制制表等。。目录存储储着所有有文件的的拥有者者，文件件拥有者者可以对对其文件件执行所所有操作作，如创创建、读读、写和和删除等等．问题是让让谁来执执行目录录服务中中的LookUp、AddName、ReName和UnName操作，查查看或修修改文件件属性?当用户具具有各自自独立、、分离的的目录时时，目录录的UFID可能认定定为一种种权能，，不需要要进一步步的访问问控制；；但是要要访问共共享目录录时，则则需要访访问控制制。一个简单单的解决决办法是是，让目目录拥有有者的访访问许可可模式与与文件拥拥有者的的访问许许可模式式取得一一致。另外，为为用户同同时提供供文件服服务和目目录服务务操作可可以克服服文件的的丢失问问题。对对于文件件创建，，用户通通过创建建操作指指定的文文件名和和目录名名，然后后依靠文文件服务务Create操作和目目录服务务AddName操作完成成。对于于文件删删除，通通过删除除操作指指定一个个UFID和目录录名．．树型结结构在UNIX提供的的树型型文件件系统统中，，包含含组织织成树树型结结构的的许多多目录录，通通过链链使文文件具具有多多个名名字，，可以以使用用基本本的文文件和和目录录服务务来实实现。。树型结结构的的目录录集合合可以以通过过叶、、根和和内部部结点点构成成。树树根是是一个个目录录，其其UFID是共用用的。。树中任任何结结点或或叶结结点就就是文文件或或目录录，可以通通过路路径名名命名名文件件或目目录，路径是是由多多部分分组成成的表表示路路径的的名字字。根具有有特殊殊名，，并且且每个个文件件或目目录都都有自自己的的名字字。在树型结构构的目录服服务中，文文件属性应应当包括一一个类型属属性用来区区分文件和和目录。这可用于沿沿树结构按按路径名检检索时，保保证名字除除最后一个个名字外一一定是一个个目录名。。当创建文文件或目录录时，文件件属性中要要设置适当当的数值，，包括访问问控制表、、创建日期期等等。目目录一旦创创建了，可可以使用AddName操作将它的的名字和UFID插入到另一一个目录中中。命名透明透明命名与与位置透明明性相关，，其意义是是路径名并并不表示文文件的位置置，如／serverl／dirl／dir2／x并不说明文文件x一定处于server1上。服务器器可以随意意地迁移和和切换，而而路径名则则保持不变变。这种系统称称为位置透明的的系统。但是，假设设文件x非常之大，，其空间的的确处于serverl上，再假设设在server2上也有大量量的空间。。系统有可可能自动地地将文件x迁移到server2上．但是，，当路径名名中第一部部分是服务务器的时候候，系统是是不能自动动将文件迁迁移走的，，即使diri和dir2在两个服务务器上都有有也不行，，因为迁移移文件将把把路径名／／serverl／dirl／dir2／x改变为／server2／dirl／dir2／x。具有前一路路径名的程程序在路径径名改变时时必须停下来来重新编译译。如果文件可可以迁移，，其命名不不必改变，则称其具具有位置独独立性。将机器名或或服务器名名嵌入到路路径名中的的分布式系系统不是位位置独立的的，基于远远程安装的的系统也不不是位置独独立的，因因为将一个个文件从一一个文件组组(安装单位)迁移到另一一个文件组组后，不可可能仍然使使用原来的的路径名。。位置独立性性不易实现现，却是分分布式系统统追求的目目标。通常，在分布式系系统中有三三种普遍的的命名文件件和目录的的方法：①机器+路径命名法法，如／machine／path或machine：path；②在本地文文件层次结结构中安装装远程文件件系统；③在所有机机器上表现现一致的统统一命名空空间。前两种方法法容易实现现，特别是是在使用没没有特殊设设计分布式式服务的系系统中非常常有效。第第三种方法法非常难于于实现，必必须精心设设计，但是，如果果要求分布布式系统的的表现像集集中式系统统一样，则则必须做到到这一点。。4．4文件服务的的实现系统结构要实现文件件服务器，，首要问题题是客户机机与服务器器是异构的的还是同构构的?第二个问题题是文件服服务和目录录服务的结结构如何?当然，对这这两个问题题还没有定定论的方法法。一.同构型／异异构型有些系统没没有区分客客户机和服服务器。所所有的机器器都运行相相同的软件件，任何机机器都需要要提供文件件服务。在有些系统统中，文件件服务器和和目录服务务器只是一一些用户程程序，所以以，在同一机器器上，可以以将系统组组织成运行行客户机软软件的系统统或运行服服务器软件件的系统，，也可以同同时运行客客户机软件件和服务器器软件。这些都是同同构的客户户机和服务务器。还有一种极极端的情况况，就是客户机机和服务器器从根本上上(包括系统硬硬件和系统统软件)就是不同的的机器，服服务器可以以运行与客客户机不同同的操作系系统或同一一操作系统统的不同版版本。这就是异构构的客户机机和服务器器。二、文件服服务和目录录服务的结结构一种方法是是将两部分分结合处理理，即将文文件和目录录服务统一一处理；另另一种方法法是分开处处理，即，当打开一个个文件时要要求先请求求目录服务务器将符号号名映射为为内部二进进制名，然然后再用二二进制名访访问文件服服务器，完完成文件的的读写。第二种方法法的优点是是两种功能能互相独立立、灵活性性好。但由由于要有两两个服务器器，因而会会增加额外外的开销。通常情况况下，客户户机向目录录服务器发发送一个符符号名，服服务器返回回一个二进进制名供在在文件服务务器上访问问文件用。。但目录层层次可能在在多个服务务器上分开开存储。三、可重复复操作与文文件服务的的状态如果一个操操作被执行行多次，其其效果与执执行一次是是一样的，，这就是可可重复操作作。在分布式系系统中，通通信上的错错误、计算算机的故障障和延迟都都可能导致致一次远程程调用的多多次执行。。如果重复执执行可能对对服务器产产生不良影影响，就必必须实现重复抑制机机制来防止重复复操作。如果操作作是可重复复的，则不不需要进行行重复抑制制的开销。。另一方面，，操作可重重复会引起起性能的降降低，例如如，服务器器的超载可可能引起客客户程序等等待超时，，从而引起起不必要的的重复调用用。CFS件服务器支支持可重复复的操作，，而XDFS则同时支持持可重复操操作和重复复抑制机制制，而UNIX文件访问操操作是不可可重复的，，因为其文文件的读写写指针在每每次操作中中都要增值值。在传统的操操作系统中中，内核为为每个进程程打开的文文件保持一一个读写指指针，但可可能会产生生两种情况况：如果服服务器故障障后重新启启动，所持持有的状态态信息将会会全部丢失失，而客户户可能不知知道服务器器的故障而而继续工作作，从而产产生不一致致的结果；；同样，当当一个客户户程序故樟樟而重新启启动工作时时，服务器器仍继续持持有原状态态信息，同同时又不易易恢复到初初态。因此此，操作在不依依赖于服务务器的存储储状态时，，可以简化化文件服务务器的设计计。因此，对于分布式式文件服务务器，无状状态的文件件服务更为为优越。四、原子性性简单的无状状态服务器器不能满足足所有应用用的需要。。如果多个个客户进程程同时修改改文件，按按照一致性性约束，服务器必须须能够保证证一个客户户对某数据据项所做的的完整修改改应在另一一个客户进进程访问这这一数据项项之前完成成。五、Cache的应用Cache(高速缓存)的应用非常常广泛，其其意义在于于提高访问问效率，减减少文件的的访问开销销。在文件服务务中，文件件可以在四四个位置上上存储，就就是客户机机的主存、、客户机硬硬盘、服务务器主存和和服务器硬硬盘(如图所示)在Cache的设置时必必须解决几几个重要问问题：首先是Cache中可交换单单元的大小小，如可以以用磁盘块块作为单位位，也可以以将整个文文件作为缓缓冲单位。。以磁盘块为为单位，可可以增加Cache的利用率；；以整个文文件为单位位，可以提提高文件的的访问速度度．4231客户机主存客户机磁盘服务器主存服务器磁盘网络文件可以存存放的位置置其次是Cache中文件或文文件块的替替换算法，，这些算法在在操作系统统和体系结结构课程中中均有论述述，常用算算法有随机机选取、FIFO(先进先出））和LRU（最近最小小使用）等等。其中最最一般方法法是将文件件放在服务务器的硬盘盘上，此方方法最大问问题是效率率即访问文文件非常慢慢。Cache设置于何处处?第一种方法法是设置在在服务器的的主存中；；第二种是将将其设置在在客户机的的磁盘中；；第三种是将其其设置在客户户机的内存中中。第一种方法直直接、简单，，对于客户机机是透明。完全由服务器器来处理Cache与磁盘的数据据一致性和同同步关系，且可对客户透透明，可保持持主存和磁盘盘拷贝同步，，不产生一致致性问题。但这种方法在在网络上仍然然有大量消息息需要传送。。第二种方法可可以消除大量量的网络传输输，对于大量量数据的访问问有优势，但对于少量量数据反而不不如第一种方方法，此种方方法还存在Cache的一致性问题题。第三种方法既既可以消除大大量的网络传传输，又可以以获得较高的的性能。但是这种方法法需要系统给给予必须的支支持(如内存锁定)，若无此功能能，用户是无无法控制数据据是否处于内内存之中的。。与第二种方方法一样，必必须考虑Cache的一致性问题。六、Cache的一致性值得注意的是是，在计算机机中任何设计计方法都是““有得必有失失”，比如，，Cache的设置带来了了访问的高效效性，同时又又带来了访问问数据的一致致性问题。解决一致性问问题的一般方方法有写穿透透(WriteThrough)，也就是当客客户机程序要要修改文件时时，直接修改改服务器文件件，而读文件件时直接读取取Cache中的文件。但是，如果当当客户机1上的A进程读取文件件F后暂时挂起，，另一个客户户机上的进程程B此时修改文件件F，当进程A重新执行时，，会直接使用用其Cache中的数据，那那么两个客户户机进程使用用的数据便是是不一致的。。解决这一问题题，可以让Cache管理程序定期期检查服务器器是否已经修修改，可以通过比较较Cache的读取时间和和服务器上的的文件最后修修改时间得知知其修改状况况。如果时间间一样，则Cache可用，否则必必须从服务器器中重新读取取数据。写穿透算法只只有助于读文文件时提高性性能：对于写文件件，则没有任任何性能收益益。许多设计计人员认为这这是不能接受受的，于是提提出一种修改改方案，就是是客户程序在在写文件时只只在Cache中做记号，过过一段时间(如30s)之后，再将这这些有记号的的数据一起写写人服务器，，这种方法叫做做延迟写(DelayedWrite)。但是许多程序序都产生一些些临时文件，，在短时间内内先写、后读读，最后删除除，假如这个个时间段小于于延迟写方法法中的写时间间段，那么，，这些文件就就不会写入服服务器，这样样，对于临时时文件既不必必使用服务器器，也提高了了访问效率。。当然，延迟写写带来的问题题是语义问题题。因为若有另一一进程读文件件，则读取文文件的正确性性取决于读的的时刻。因此此，延迟写策策略是在性能能和清晰语义义之间的权衡衡。沿此思路就有有了使用----对话语义方法法（关闭时写写），即仅在在文件关闭时时才写服务器器。这样就会出现现问题，若两两个进程都读读取了文件，，并先后关闭闭文件，那么么第一个关闭闭文件的进程程：不会对文文件有影响，，文件的最后后版本完全决决定于笔二个个关闭文件的的进程，即出出现前述的““修改丢失””问题。还有一种完全全不同的处理理一致性的方方法是集中控控制方法文件服务器记记录客户打开开文件和读、、写文件的情情况。如果文文件是以读方方式打开的，，则可以让其其它进程读，，但必须阻止止其它进程写写；如果某个个进程以写方方式打开文件件，则必须防防止其它进程程的任何访问问。当一个文文件关闭时，，可以将修改改后的文件写写回服务器，，服务器修改改文件访问记记录。访问控制UNlX系统使用的访访问控制方法法比较通用和和高效，目录录服服务务的的访访问问控控制制可可以以参参照照这这种种方方法法实实现现。。可可以以访访问问文文件件的的对对象象一一般般有有四四类类：：①文文件件拥拥有有者者；；②目目录录服服务务负负责责命命名名和和访访问问控控制制；；③标标记记为为系系统统管管理理员员的的客客户户进进程程，，必必须须经经特特殊殊授授权权来来管管理理文文件件内内容容；；④所所有有其其它它客客户户。。在UNlX中，，同同一一文文件件可可以以出出现现在在许许多多目目录录中中，，使使用用有有向向图图让让用用户户在在自自己己的的目目录录中中记记录录共共享享文文件件的的名名字字。。如如果果要要使使文文件件可可存存放放到到不不同同目目录录中中，，访访问问控控制制表表就就不不能能只只与与特特定定文文件件相相关关，，需需要要将将访访问问控控制制表表存存在在文文件件属属性性中中，，而而不不是是目目录录文文件件中中。。权能能(Capability)对于于文文件件的的访访问问必必须须加加以以控控制制，，权能能就就是是一一种种基基本本的的文文件件访访问问控控制制方方法法。。一、、权权能能定定义义权能能是是对对文文件件的的一一种种标标识识，，该该标标识识含含有有授授予予该该文文件件执执行行一一定定操操作作的的权权限限。。权能用位位串来描描述，该该位串由由以下三三部分：：①标识符：：标识符符能唯一一标识权权能所涉涉及的文文件。②访问权限限：访问问权限是是进程对对所操作作文件拥拥有的操操作权限限的详细细说明，，每个权权限一般般用一个个二进制制位来描描述。③随机数数：随机机数使得得权能难难以猜测测，通常常将访问问权限与与随机数数组合在在一起使使用。二、建立立权能权能可由由专门管管理权能能的服务务操作建建立，以以相应权权限为用用户所使使用。当为某某客户建建立新文文件时，，服务器器建造一一个具有有所有权权限的权权能返回回该用户户。如果果该文件件是一个个独占个个人文件件和目录录，则该该权能不不需修改改，也不不必传给给另外的的用户；；三、修改改权能任何一个个为文件件授予权权能的服服务都可可以包含含修改访访问权限限的部分分，访问权限限的修改改允许客客户把现现有权能能与其所所需权限限结合在在一起并并最终返返回一个个具有这这些权限限的新权权能四、取消消权能具有权限限的用户户可以请请求服务务器收回回权能从从而取消消对该文文件的访访问。权能的副副本可分分布在用用户的多多个进程程中，用用户和服服务器都都不必知知道这些些副本在在什么地地方五、保存存权能由于文件件、目录录的生存存期一般般比具有有其权能能的用户户进程生生存期要要长，用用户为了了今后能能重新得得到这些些文件的的权能，，需要用某某种方法法保存权权能。六、权能能的保护护如果权能能被当成成保护机机制，其自身必必须被保保护文件的存存储一、文件件的逻辑辑结构在文件服服务器中中文件逻辑辑上是数数据项序序列。设F为文件，，Pi为第i页，Ii为页中的的一个数数据项，，E为二串数数据项称称为文件件尾。文件可定定义为页页的有序序集F=<P1，P2，…，Pn-1,E>二、块服服务文件服务务器的一一个主要要任务是是记录文文件的地地址以及及与之相相应的UFID，故需需要一一个文文件位位置映映射表表(FLM，即FileLocationMap)．该映映射表表存储储一组组<UFID，文件件地址址>映射，，用于于将内内部名名直接接对应应到物物理地地址上上。当创建建和扩扩充文文件时时，必必须为为该文文件分分配空空间；；当删删除或或截断断一个个文件件时，，必须须回收收空间间。这这些操操作需需要存存储空空间的的动态态分配配和按按不连连续存存储块块进行行管理理的机机制，以便便于文文件的的扩充充和缩缩小。。要完成成文件件的这这些基基本操操作，，其基基础就就是块块服务务。块服务务主要要用于于管理理外存存储器器，包包括分分配、、读、、写等等操作作。在在分布布式文文件系系统中中，块块服务务一般般是嵌嵌入在在文件件服务务中的的模块块，也也可以以做成成单独独的块块服务务层次次。以块服服务支支持文文件服服务的的优点点有以以下几几点：：①不同同服务务共享享同一一磁盘盘空间间②可使使用不不同的的存储储介质质；③将文文件服服务与与磁盘盘和其其它存存储介介质的的优化化访问问问题题分开开考虑虑。三、文文件索索引文件索索引主主要包包括文文件长长度、、文件件属性性和物物理块块的指指针，，主要用用于支支持文文件逻逻辑页页到物物理块块的映映射，，另外，，文件件索引引可组组织成成树型型索引引结构构，即即，一一个索索引中中物理理块指指针指