南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务第三章第三章分布式系统的同步分布式系统的同步和进程和进程 南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务31 时钟同步时钟同步 分布式算法的主要特征：分布式算法的主要特征：相关信息分布在多台机器上相关信息分布在多台机器上 进程仅依据局部的信息作出决定进程仅依据局部的信息作出决定一台机器的故障不应引起整个系统的失败一台机器的故障不应引起整个系统的失败没有共用的全局时钟没有共用的全局时钟南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务1 1逻辑时钟逻辑时钟先看一个例子先看一个例子:06121824303642485460081624324048566472800102030405060708090100ABCD三个有自己时钟的进程三个有自己时钟的进程,时钟不同时钟不同 运行的结果是运行的结果是消息消息C C在时间在时间6060上被上被发送发送,却在时间点却在时间点5454上到达上到达南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 LamportLamport的的算算法法以以”先先于于”关关系系为为基基础础，每每个个消消息息都都携携带带它它的的发发送送时时间间,当当它它到到达达目目的的地地时时，如如果果目目的的地地的的时时间间早早于于它它的的发发送送时时间间，那那么么就就把把目目的的地地的的时时间间向向前前拔拔,至至少要比发送时间大少要比发送时间大1 1个单位个单位.0612182430364248707608162432404861697785800102030405060708090 100ABCD用用LamportLamport的的算算法法纠正时钟纠正时钟南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务该该算算法法解解决决了了全全局局时时钟钟问问题题，它它的的条条件件就就是是两两个个相相关关事件之间必须至少相差一个时间事件之间必须至少相差一个时间 2 2时钟同步算法时钟同步算法 逻逻辑辑时时钟钟只只给给出出事事物物的的相相对对时时间间,与与真真实实时时间间并并不不对对应应,故要引入外部物理时钟故要引入外部物理时钟,常用的时钟同步算法常用的时钟同步算法:克里司帝安克里司帝安(CRISTIAN)(CRISTIAN)算法算法 具具有有国国家家标标致致时时间间接接收收器器的的机机器器,注注意意:调调整整的的方方法法,通通过过调调节节单单位位时时间间内内的的中中断断的的时时间间,来来逐逐步步完完成成时时钟钟的的调调整整.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务伯克利算法伯克利算法 计计算算平平均均时时间间,它它是是一一个个集集中中式式算算法法,不不能能在在大大规规模模的的分布式系统中使用分布式系统中使用 原原理理:定定期期轮轮询询每每台台机机器器的的时时间间,由由结结果果计计算算平平均均时时间间,各机器依此调整时间各机器依此调整时间.3 3同步时钟的具体使用同步时钟的具体使用 至多一次消息传送至多一次消息传送 消消息息的的时时间间戳戳比比存存储储的的时时间间戳戳的的值值早早,就就拒拒绝绝接接受受该该消息消息南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 基于时钟的缓冲存储器（基于时钟的缓冲存储器（CACHECACHE）的一致性）的一致性 使使用用CACHECACHE会会出出现现一一致致性性问问题题，原原解解决决的的方方法法:区区分分读读写写缓缓存存,现现在在可可用用同同步步时时钟钟来来解解决决。
即即通通过过提提供供有有效效期期（利利用有效的租约）用有效的租约）来控制来控制CACHECACHE一致性问题一致性问题南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务3.2 3.2 互斥操作互斥操作 有有多多个个进进程程的的系系统统经经常常会会碰碰到到临临界界区区的的操操作作当当一一个个进进程程要要访访问问某某个个共共享享数数据据时时，它它要要先先进进人人临临界界区区进进行行互互斥斥操操作作，确确保保没没有有别别的的进进程程同同时时访访问问该该数数据据在在单单机机系系统统中中，临临界界区区可可以以用用信信号号灯灯、管管程程来来实实现现那那么么在在分分布布式式系系统统中中，由由于于不不能能共共享享主主存存，怎怎么么实实现现临临界界区区和和互互斥斥操操作作呢呢?下下面面我我们们讨讨论论几种算法几种算法集中式算法集中式算法 该该方方法法就就是是模模拟拟单单机机系系统统,指指定定一一个个管管理理员员进进行行许许可可管管理理,该该算算法法保保证证了了互互斥斥,每每个个临临界界区区只只需需三三条条消消息息(申申请请,许许可可,释释放放)南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务1 10 02 2OKOK请求请求C C管理员管理员队列空队列空管理员管理员1 10 02 2不回答不回答请求请求C C队列空队列空1 10 02 2OKOK释放释放C C管理员管理员队列空队列空2 2 (A)(A)进程进程1 1向管理员请求向管理员请求进入临界区进入临界区,得到许可得到许可 (B)(B)进程进程2 2向管理员请求进向管理员请求进入临界区入临界区,管理员不回答管理员不回答 (C)(C)进程进程2 2向管理员请求进向管理员请求进入临界区入临界区,管理员许可管理员许可缺点缺点:集中式算法管理员是系统的瓶颈集中式算法管理员是系统的瓶颈南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 分布式算法分布式算法 算法的条件算法的条件:系统中的事件必须有全局的顺序系统中的事件必须有全局的顺序 算法的工作过程如下算法的工作过程如下:当当一一个个进进程程要要进进入入临临界界区区时时，它它构构造造一一条条包包括括临临界界区区名名、进进程程号号和和当当前前时时间间的的请请求求消消息息，然然后后把把该该消消息息广广播播给给其其他他的的所所有有进进程程。
这这里里假假设设，消息的发送是可靠的消息的发送是可靠的当一个进程收到请求后，根据它的状态采取相应的动作：当一个进程收到请求后，根据它的状态采取相应的动作：(1)(1)当接收者不在临界区，并且也不想进入临界区，就应答发送者当接收者不在临界区，并且也不想进入临界区，就应答发送者OKOK消息2)(2)如果接收者已经在临界区中，它不回答仅仅把请求加入队列如果接收者已经在临界区中，它不回答仅仅把请求加入队列3)(3)如如果果接接收收者者不不在在临临界界区区，但但它它也也想想进进入入临临界界区区，就就要要将将收收到到消消息息的的时时间间戳戳和和它它广广播播消消息息的的时时间间戳戳比比较较.如如果果到到来来的的消消息息时时间间戳戳早早，接接收收者者回回答答发送者发送者OKOK消息；反之接收者把到来的请求加入队列，不回答消息；反之接收者把到来的请求加入队列，不回答.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 在在发发完完进进入入临临界界区区请请求求后后，进进程程将将等等待待所所有有的的允允许许消消息息，一一旦旦得得到到许许可可，就就可可进进入入临临界界区区，当当退退出出时时向向队队列列中中的的所所有有进进程程发发OKOK消消息息，并并将将它它从从队队列列中删除。
中删除所有进程都要参与决定是否进入临界区，若有进程不能做，算法将出错所有进程都要参与决定是否进入临界区，若有进程不能做，算法将出错由于所有进程都要参加算法，所以比集中式算法慢，复杂，开销大由于所有进程都要参加算法，所以比集中式算法慢，复杂，开销大改进算法：改进算法：不需所有进程同意，部分回答不需所有进程同意，部分回答OKOK即可即可 令牌环算法令牌环算法 进进程程只只有有拥拥有有令令牌牌时时,才才能能进进入入临临界界区区,一一个个进进程程从从相相邻邻的的进进程程收收到到令令牌牌时时先先检检查查自自己己是是非非要要进进入入临临界界区区;如如果果要要,就就进进入入,否则就将令牌传递给下一个进程否则就将令牌传递给下一个进程.缺缺点点:令令牌牌可可能能丢丢失失且且检检测测困困难难，一一个个要要进进入入临临界界区区的的进进程最差情况下要等待其他进程进入和退出临界区所用时间总和程最差情况下要等待其他进程进入和退出临界区所用时间总和南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 三种算法的特点比较三种算法的特点比较集集中中式式算算法法简简单单、高高效效，每每次次进进入入和和离离开开临临界界区区只只需需3 3次次消消息息传传递递：请请求求、许许可可；释释放放，分分布布式式算算法法中中，n n个个进进程程需需要要(n-1)(n-1)个个请请求求和和(n-1)(n-1)个个许许可可，总总共共要要2(n2(n1)1)个个消消息息。
在在令令牌牌环环算算法法中中，所所需需的的消消息息数数是是不不固固定定的的如如果果每每个个进进程程都都要要进进入入临临界界区区，那那么么每每个个令令牌牌都都有有一一次次进进人人和和退退出出，平平均均每每次次进进入入有有个个消消息息传传递递；如如果果令令牌牌被被一一个个进进程程占占有有很很长长时时间间，那那么进入临界区需要的消息就不确定么进入临界区需要的消息就不确定进进程程从从它它发发出出进进入入临临界界区区的的请请求求到到它它进进入入临临界界区区的的时时间间延延迟迟在在三三个个算算法法中中是是不不同同的的,当当临临界界区区很很短短并并且且使使用用频频率率很很低低时时，进进入入临临界界区区时时间间延延迟迟的的决决定定因因素素是是进进人人临临界界区区的的控控制制机机制制当当临临界界区区很很长长并并且且使使用用的的频频率率很高时，决定因素在于等待时间，消息数就能说明这一点很高时，决定因素在于等待时间，消息数就能说明这一点这这三三种种算算法法出出现现故故障障时时,都都会会有有很很大大影影响响,要要避避免免系系统统的的崩崩溃溃,须须注注意意:在容错系统中在容错系统中,次三种算法都不适用次三种算法都不适用.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务3.3选举算法选举算法 在在分分布布式式系系统统中中，大大多多数数算算法法要要求求有有一一个个进进程程充充当当管管理理员员或或初初始始启启动动者者等等特特殊殊角角色色。
前前面面几几个个算算法法就就有有这这样样的的例例子子一一般般来来说说，由由哪哪个个进进程程充充当当特特定定角角色色无无关关紧紧要要，但但是是必必须须有有一一个个进进程程做做这这个个工工作作下下面面我我们们来来看看如如何何选选一一个个进程担当特定角色进程担当特定角色选选举举算算法法的的目目的的是是当当选选举举完完成成后后，能能够够让让所所有有的的进进程程知道谁是管理员知道谁是管理员.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务1.霸道算法霸道算法 该该算算法法提提出出当当一一个个进进程程P P注注意意到到管管理理员员不不再再对对请请求求作作出反应时，它就开始选举进程出反应时，它就开始选举进程P P执行下列步骤：执行下列步骤：(1)(1)向所有向所有进程号比它大进程号比它大的进程发送的进程发送ELECTIONELECTION消息；消息；(2)(2)如果没有进程响应，进程如果没有进程响应，进程P P成为管理员；成为管理员；(3)(3)如果有进程响应，该响应进程成为管理员，如果有进程响应，该响应进程成为管理员，P P结束选举结束选举注注意意：一一个个进进程程只只能能从从号号码码比比它它小小的的进进程程处处得得到到一一个个选选择择消息消息南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务2 20 05 53 36 64 41 17 7(A)(A)进程进程4 4启动选举启动选举2 20 05 53 36 64 41 17 7(B)(B)进程进程5,65,6响应响应,让让4 4停止停止2 20 05 53 36 64 41 17 7(C)(C)进进程程5,6,5,6,都都启启动动选选举举2 20 05 53 36 64 41 17 7(D)(D)进进程程6 6让让进进程程5 5停停止止选举选举2 20 05 53 36 64 41 17 7(E)(E)进进程程6 6成成为为管管理理员员,发通知发通知霸道算法图示霸道算法图示南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务2.环形算法环形算法 这这个个算算法法使使用用环环，但但不不是是令令牌牌环环。
这这里里假假定定所所有有的的进进程程都都是是有有序序号号的的，即即每每个个进进程程都都知知道道它它的的后后继继进进程程当当一一个个进进程程发发现现管管理理员员不不能能工工作作时时，它它把把包包含含其其进进程程号号的的ELECTIONELECTION消消息息发发给给它它的的后后继继进进程程；接接收收消消息息的的进进程程再再向向后后继继进进程程发发送送ELECTIONELECTION消消息息如如果果接接收收进进程程没没有有反反应应，发发送送消消息息的的进进程程便便向向下下一一个个进进程程发发消消息息每每一一次次发发送送ELECTIONELECTION，进进程程都都要要将将自自己己的的进进程程号号加加入入消息2 20 04 46 65 51 13 37 7使用环形选举算法使用环形选举算法选举消息选举消息选举消息选举消息2 23 32 25 55 56 65 56 60 0 出现故障的出现故障的管理员管理员南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 最最后后，第第一一个个发发出出该该选选举举（ELECTIONELECTION）消消息息进进程程收收到到该该消消息息,再再将将其其转转换换为为协协调调（COORDINATORCOORDINATOR）消消息息后后，再再循循环环一一周周,通通知知谁谁是是管管理理员员，谁谁是是组组成成员员，这这时时消消息息包包中中进进程程号号最最高高的的进进程程将将成成为为管管理理员员。
当当这这个个消消息息循循环环一一周周后后，由由发发送送进进程程把把它它从从网网上上清除图图中中2 2和和5 5都都发发现现7 7失失效效，分分别别建建立立选选举举消消息息，两两条条消消息息都都沿环运行，结果是一样的，只是浪费了带宽沿环运行，结果是一样的，只是浪费了带宽南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务34 线线 程程 进进程程因因等等待待而而挂挂起起,使使进进程程中中可可并并行行部部分分不不能能执执行行,从从而而使系统性能下降使系统性能下降,故引入故引入-线程线程.1.1.线线程程：就就是是可可以以共共享享地地址址空空间间的的轻轻型型进进程程，它它有有自自己己的的程程序序寄寄记记数数器器栈栈和和寄寄存存器器集集合合它它与与进进程程的的主主要要区区别别是是它它的地址空间是共享的的地址空间是共享的线程相对于进程，犹如进程相对于机器线程相对于进程，犹如进程相对于机器 2.2.线程的使用，将并行性引入到顺序执行的系统线程的使用，将并行性引入到顺序执行的系统.多线程组织的常用模型：多线程组织的常用模型：南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 1)1)分配器工作者模型分配器工作者模型 有一个分配器线程唤醒工作者线程可用信号灯有一个分配器线程唤醒工作者线程可用信号灯 2)2)团队模型团队模型 地位平等地位平等 线程各自获取和处理自己的请求线程各自获取和处理自己的请求.3)3)流水线模型流水线模型 管管道道线线模模型型，第第一一个个线线程程产产生生一一些些数数据据传传给给下下一一个个线线程处理，且持续下去。
程处理，且持续下去多多线线程程可可分分时时工工作作在在单单CPUCPU上上也也可可工工作作在在多多处处理理器器系系统统上上,而而且且多多线线程程系系统统设设计计的的好好将将可可与与多多处处理理机机工工作作性性能能相当相当.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务共享缓冲区共享缓冲区到达的工作请求到达的工作请求邮箱邮箱文件服务器进程文件服务器进程分配器线程分配器线程工作者线程工作者线程到达的工作请求到达的工作请求到达的工作请求到达的工作请求内核内核分配器分配器/工作者模型工作者模型流水线模型流水线模型团体模型团体模型进程中线程三种组织方式进程中线程三种组织方式南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务3.3.线程包的设计的相关问题线程包的设计的相关问题线程包就是供用户或程序员调用的关于线程的一组原语线程包就是供用户或程序员调用的关于线程的一组原语线程的管理方法有静态和动态方法两种线程的管理方法有静态和动态方法两种静态静态即开始就确定好线程的个数即开始就确定好线程的个数，动态，动态个数个数不定不定 线程的代码与进程一样，由多个过程组成。
线程的代码与进程一样，由多个过程组成线程包中临界区控制利用互斥体（线程包中临界区控制利用互斥体（mutex),mutex),其总处于：其总处于：打开和锁住两种状态打开和锁住两种状态 lock mutex;lock mutex;check data structures lock mutex check data structures lock mutex while(resource busy)mark resource as free;while(resource busy)mark resource as free;wait(condition varable);unlock mutex;wait(condition varable);unlock mutex;mark resource as busy;wakeuo(condition variable);mark resource as busy;wakeuo(condition variable);unlock mutex;unlock mutex;互斥变量与条件变量的使用互斥变量与条件变量的使用南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 线程可由算法进行调度，如优先级调度、循环调度等线程可由算法进行调度，如优先级调度、循环调度等4.4.线程包的实现线程包的实现1)1)在用户空间实现线程（如图）在用户空间实现线程（如图）这这种种方方法法是是将将线线程程包包完完全全放放在在用用户户空空间间，内内核核对对此此一一无无所所知知，在在这这种种方方法法中中，内内核核只只是是管管理理普普通通的的单单线线程程进进程程。
这这种种方方法法最最明明显显的的优优点点是是它它可可以以在在一一个个不不支支持持多多线线程程的的操操作作系系统统上上实实现现用用户户线线程程包包同同时时它它还还允允许许每每个个进进程程有有自自己己特特定的调度算法定的调度算法.线程1线程2线程3线程4线程5线程6运行期系统运行期系统内内核核内核空间内核空间用户空间用户空间南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 缺点是：缺点是：数量太多会引起资源紧张数量太多会引起资源紧张.同时同时 (1)(1)它也难实现阻塞系统的调用它也难实现阻塞系统的调用.(2)(2)它它的的调调度度是是非非抢抢先先式式的的.进进程程内内部部无无时时钟钟中中断断,无法进行时间片的调度无法进行时间片的调度.2)2)在操作系统内核实现（如图）在操作系统内核实现（如图）不不需需要要运运行行系系统统,线线程程创创建建或或撤撤销销,只只需需一一次次系系统统调调用用,比比在在用用户户空空间间实实现现线线程程开开销销大大.可可通通过过在在撤撤销销时时加加标标记记，当做为新线程创建时仅需激活即可当做为新线程创建时仅需激活即可线程1线程2线程3线程4线程5线程6内内核核用户空间用户空间内核空间内核空间南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 3)3)调度员活动方法调度员活动方法 结结合合前前两两种种的的优优点点(用用户户线线程程的的高高性性能能和和内内核核线线程程的的实实现简单现简单)原原理理：当当使使用用调调度度员员活活动动方方法法时时，内内核核给给每每个个进进分分配配一一些些“虚虚处处理理器器”，并并由由运运行行系系统统分分给给线线程程，同同时时通通过过避避免免在在用用户户空空间间和和内内核核空空间间之之间间的的不不必必要要的的转转换换来来实实现现高高效效率率。
如如：线线程程在在局局部部信信号号上上阻阻塞塞并并不不去去涉涉及及内内核核，而而是是由由用用户户运运行行期期系系统统去去完完成成阻阻塞塞和和调调度度具具体体是是由由内内核核激激活活用用户运行期系统户运行期系统南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 4)4)线程和线程和RPCRPC 希希望望使使一一个个进进程程中中的的线线程程可可以以有有效效的的调调用用同同一一台台机机器器上上的的另另一一个个进进程程中中的的线线程程，具具体体采采用用与与RPC RPC 相相似似的的过过程程完完成成加加速速RPCRPC执执行行的的技技术术，具具体体即即为为当当一一个个线线程程执执行行请请求求时时，它它将将消消失失并并且且它它的的堆堆栈栈和和环环境境信信息息也也丢丢弃弃，当当有有新新的的消消息息进进入入时时，内内核核动动态态创创建建一一个个新新线线程程去去为为其其服服务务优优点点首首先先线线程程不不用用等等待待所所以以不不保保留留环环境境，其其次次创创建建新新线线程程比比存存储储一一个个存存在在的的线线程程花花费费少少，节节约约了了时时间间减减少少了了开开销销，从从而而提提高高了速度。
了速度南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务35 分布式系统模型分布式系统模型 1 1工作站模型工作站模型 其其主主要要指指：一一组组工工作作站站通通过过高高速速局局域域网网互互连连，在在某某一一时时刻刻,每台机器只有一个用户登录，即拥有者，要么空闲每台机器只有一个用户登录，即拥有者，要么空闲优优点点：清清晰晰、易易于于理理解解，计计算算能能力力固固定定、系系统统反反应应时时间间固固定定、有有一一定定的的自自主主性性、同同时时增增强强了了独独立立性性缺缺点点:资资源源存存在浪费在浪费,资源利用率不高资源利用率不高.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 2.2.空闲工作站的使用空闲工作站的使用 1 1）找出空闲工作站）找出空闲工作站 两种定位方式：服务器驱动和客户端驱动两种定位方式：服务器驱动和客户端驱动 2 2）透明运行远程进程）透明运行远程进程 由内核完成由内核完成 3 3）机主人重新使用时如何处理）机主人重新使用时如何处理 直直接接杀杀死死进进程程、移移植植到到另另一一台台机机器器上上（进进程程全全部部包包括括子进程）子进程）南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 3.3.处理机池模型处理机池模型 处处理理机机池池是是无无盘盘工工作作站站的的进进一一步步发发展展。
理理论论依依据据是是排排队队论论,具具体体有有理理发发师师模模型型、超超市市收收款款等等CPUCPU根根据据需需求求动动态态的的分分配给用户模型如图配给用户模型如图 虽虽然然有有证证明明：用用一一个个是是小小系系统统功功能能N N倍倍的的大大系系统统来来代代替替N N个独立的小系统的资源可把平均响应时间减少为原来的个独立的小系统的资源可把平均响应时间减少为原来的1/N1/N倍文件服务器文件服务器处理机池处理机池CPUCPU南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 然然而而平平均均响响应应时时间间不不代代表表一一切切，从从费费用用角角度度来来看看，不不惜惜代价建造巨型机甚至是不可能的代价建造巨型机甚至是不可能的同同时时也也并并不不是是有有N N个个处处理理器器的的处处理理机机池池就就可可比比单单个个处处理理器器的性能高的性能高N N倍，倍，而是决定于任务可分几部分而是决定于任务可分几部分4.4.混合模型混合模型 用用那那种种模模型型要要依依情情况况而而定定,若若是是偶偶发发的的事事件件为为主主,则则个个人人工工作作站站模模型型机机可可,若若是是仿仿真真或或工工程程计计算算则则用用处处理理机机池池较较好好,也也可两者结合可两者结合.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务36 处理机分配与调度处理机分配与调度 如何决定进程运行在那台机器上，即为处理机的分配。
如何决定进程运行在那台机器上，即为处理机的分配1.1.分配模型分配模型1 1）分配策略有两大类）分配策略有两大类:非迁移的（进程创建后，一直呆到进程结束）非迁移的（进程创建后，一直呆到进程结束）迁移的（进程可在运行中迁移到其它机器上运行）迁移的（进程可在运行中迁移到其它机器上运行）2 2）分配算法的目标：）分配算法的目标：(1)(1)最大限度地提高最大限度地提高CPUCPU利用率利用率 (2)(2)尽可能缩短平均响应时间尽可能缩短平均响应时间 (3)(3)最小化响应率最小化响应率南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务例如：例如：有两个处理机有两个处理机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秒秒处理机处理机1 110MIPS10MIPS处理机处理机2 2100MIPS100MIPS5 5秒队列秒队列南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务2 2设计分配算法的主要相关问题设计分配算法的主要相关问题1）确定式还是启发式）确定式还是启发式 确确定定式式适适用用进进程程是是否否可可预预知知;启启发发是是指指以以经经验验性性规规则则和和信信息指导息指导.2）集中式还是分布式）集中式还是分布式 依全局信息做判定依全局信息做判定,以局部信息做判断以局部信息做判断.3）最优的还是次优的）最优的还是次优的 4）局部的还是全局的）局部的还是全局的 解决转移策略解决转移策略5）发送者初启还是接收者初启）发送者初启还是接收者初启解决定位策略解决定位策略南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 3 3处理机分配算法实现中的问题处理机分配算法实现中的问题 1 1）对负载的测量）对负载的测量 2 2）额外开销的处理）额外开销的处理 3 3）问题的复杂度）问题的复杂度 4 4）稳定性问题）稳定性问题 4 4典型的处理机分配算法典型的处理机分配算法 1)1)图论决策算法图论决策算法 2)2)集中式算法（集中式算法（上上下算法）下算法）3)3)层次算法层次算法 逻辑上构成分层结构逻辑上构成分层结构 4)4)投投标标算算法法 把把系系统统中中的的资资源源和和任任务务作作为为买买方方和和卖卖方方以以寻求平衡寻求平衡.A AB BC CD DG GI IH H2 22 22 25 55 58 81 11 14 44 43 3A AB BC CD DG GI IH H2 22 22 25 55 58 81 11 14 44 43 3F FF FE EE E3030单位通信量单位通信量2828单位通信量单位通信量南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 5 5调度调度假假设设进进程程成成组组创创建建,组组间间通通信信比比组组内内通通信信要要少少,基基于于协协同同调度调度概念的算法概念的算法.算法使用一个矩阵算法使用一个矩阵 列是处理机的进程表列是处理机的进程表 行是时间段的进程表行是时间段的进程表主主要要思思想想:每每个个处处理理机机采采用用时时间间片片轮轮转转法法,因因此此可可将将进进程程组的所有成员放在不同处理机上的同一时间段组的所有成员放在不同处理机上的同一时间段处理机处理机时间片时间片南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务实实现现文文件件服服务务的的技技术术对对于于分分布布式式系系统统的的设设计计非常重要。
非常重要在在分分布布式式系系统统中中，必必须须提提供供与与传传统统文文件件系系统统相相当当的的性性能能和和可可靠靠性性实实现现分分布布式式文文件件服服务务器器的的技技术术源源自自传传统统系系统统，但但由由于于要要将将许许多多设设施施分分布布在在多多个个不不同同的的服服务务器器中中，系系统统结结构构有有所所不不同同，因因此此，其技术要求及高于传统系统其技术要求及高于传统系统南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务共享共享持久性持久性分布式分布式缓存缓存/副本副本维护维护一致性一致性例子例子主存主存1RAM文件系统文件系统1UNIX文件系统文件系统分布式文件系统分布式文件系统SUNNFSWEBWEB服务器服务器分布式共享内存分布式共享内存 IVY远程对象远程对象1CORBA持久对象存储持久对象存储1CORBA持久对象存储持久对象存储持久分布式对象存储持久分布式对象存储PERDIS南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务第第四四章章分布式文件服务分布式文件服务南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务41 引引 言言文文件件被被认认为为是是一一个个基基于于磁磁盘盘或或其其它它二二级级存存储储器器的的存存储储结结构构的的抽抽象象。
最最简简单单情情况况下下，文文件件定定义义为为数数据据项项的的序序列列，文文件件系系统统提提供供按按指指定定位位置置读读写写文文件件数数据据项项或或子子序序列列的的操操作作有有些些文文件件系系统统将将文文件件定定义义成成复复杂杂数数据据结结构构的的集集合合(如如记录等记录等)，可以用记录的键字来定位可以用记录的键字来定位在在集集中中式式文文件件系系统统中中，文文件件系系统统可可以以管管理理大大量量的的文文件件，包包括括读读、写写或或删删除除等等而而目目录录是是一一种种抽抽象象的的文文件件管管理理设设施施，它它能能将将文文件件名名映映射射到到一一个个文文件件指指针针，这这种种映映射射(即即目目录录)一一般般以以特特殊殊类类型型的的文文件件存存储储，若若要要访访问问文文件件，需需要要首首先先打打开开目录南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务文文件件系系统统要要负负责责文文件件共共享享和和访访问问控控制制的的管管理理，限限定定用用户的访问权限，为每个文件定义访问类型等户的访问权限，为每个文件定义访问类型等文件系统一般提供以下服务文件系统一般提供以下服务:文件组织文件组织 文件存储文件存储 文件检索文件检索 文件命名文件命名 文件共享文件共享 文件保护。
文件保护设设计计文文件件系系统统的的目目的的，是是使使程程序序员员可可以以使使用用抽抽象象操操作作来访问磁盘空间，来访问磁盘空间，传统文件系统的层次结构如下图所示：传统文件系统的层次结构如下图所示：南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 文件系统模块图文件系统模块图以上也同样是分布式文件系统的基础以上也同样是分布式文件系统的基础.目录模块目录模块:负责文件名到文件标识的映射负责文件名到文件标识的映射文件模块文件模块:负责文件标识到文件的映射负责文件标识到文件的映射文件访问文件访问:文件数据、属性的读写文件数据、属性的读写访问控制访问控制:操作的许可性检查操作的许可性检查盘块模块盘块模块:磁盘块的分配及访问磁盘块的分配及访问设备模块设备模块:磁盘磁盘I/O缓冲缓冲南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 另外加上另外加上:1.1.支持共享信息的管理支持共享信息的管理 不必先拷贝，再访问，永久性数据管理不必先拷贝，再访问，永久性数据管理 2.2.为用户提供透明的文件访问服务为用户提供透明的文件访问服务 3.3.提供目录服务提供目录服务 提供文件命名及文件名到文件标识的映射功能提供文件命名及文件名到文件标识的映射功能 4.4.事务服务事务服务 为为用用户户提提供供的的最最高高层层服服务务,提提供供并并发发服服务务,保保证证文文件件的的一一致性致性南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 综合而言综合而言,分布式文件可分为三种服务分布式文件可分为三种服务:目录服务目录服务,文件服务文件服务,事务服务事务服务用户程序用户程序用户程序用户程序用户程序用户程序客户模块客户模块网络网络文件服务文件服务目录服务目录服务事物服务事物服务文文件件服服务务的的RPCRPC界面界面用用户户程程序序界界面面APIAPI目目录录服服务务的的RPCRPC界面界面事事物物服服务务的的RPCRPC界面界面南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务4.2 文件服务文件服务 在在UNlXUNlX和和DOSDOS系系统统中中，文文件件是是没没有有任任何何解解释释的的字字节节序序列列，文文件件的的结结构构和和意意义义完完全全由由应应用用程程序序决决定定，操操作作系系统统不不关关心心其其结结构构和和意意义义。
但但在在某某些些大大型型机机的的操操作作系系统统中中，有有许许多多不不同同类类型的文件，每种文件具有不同的特性型的文件，每种文件具有不同的特性文文件件可可以以是是一一组组记记录录构构成成的的序序列列，该该记记录录又又可可以以是是复复杂杂的的结结构构，这这个个结结构构的的意意义义是是由由操操作作系系统统解解释释的的这这样样，文文件件便便由由数数据据和和属属性性构构成成，其其中中，属属性性包包括括文文件件长长度度、访访问问时时间间、访访问问控控制制表表和和拥拥有有者者，文文件件长长度度和和数数据据可可为为用用户户使使用用，其其它它属性均为目录服务使用，可以将这种文件看作一种文件对象属性均为目录服务使用，可以将这种文件看作一种文件对象南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 关关于于文文件件的的另另一一个个重重要要问问题题是是文文件件的的可可修修改改性性如如果果文文件件创创建建之之后后，不不能能再再修修改改，则则称称为为不不可可修修改改(Immutable)(Immutable)文文件件，否否则则称称为为可可修修改改(Mutable)(Mutable)文文件件。
这这里里主主要要讨讨论论可可修修改改的文件4.2.1 4.2.1 文件服务的模型和任务文件服务的模型和任务 对于一般的文件服务而言，有两种服务模型对于一般的文件服务而言，有两种服务模型 1)1)装载卸载装载卸载(Up Load(Up LoadDown Load)Down Load)模型模型 2)2)远程访问远程访问(Remote Access)(Remote Access)模型模型南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务在在装装载载卸卸载载模模型型中中，文文件件服服务务仅仅提提供供读读文文件件和和写写文文件件两种操作两种操作读读操操作作用用于于将将整整个个文文件件从从服服务务器器中中完完全全读读出出，写写操操作作用用于于将将整整个个文文件件从从客客户户机机写写入入服服务务器器在在这这种种模模型型下下，可可以以将将文文件件缓缓冲冲于于客客户户机机的的主主存存或或磁磁盘盘中中，其其优优点点是是概概念念简简单单，应应用用程程序序可可以以局局部部拥拥有有并并访访问问文文件件，程程序序结结束束后后，必必须须将将新新建建或或修修改改过过的的文文件件写写回回服服务务器器。
在在此此，不不需需要要复复杂杂的的文文件件服服务务界界面面，整整个个文文件件的的传传输输是是高高效效的的但但是是，客客户户机机必必须须有有足足够够的的空空间间来来存存储储所所需需要要的的文文件件，另另外外，如如果果实实际际上上应应用用程程序序作作用于文件的一小部分，就会造成很大的浪费用于文件的一小部分，就会造成很大的浪费南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务在在远远程程访访问问模模型型中中，文文件件服服务务将将提提供供大大量量的的文文件件操操作作，包包括括打打开开、关关闭闭 读读和和写写等等，其其优优点点是是不不需需要要客客户户机机具具有有大大量量空空间间另另外外，当当应应用用程程序序只只需需处处理理文文件件中中少少量量数数据据时时，不不需需要将整个文件全部拷贝到客户机上去要将整个文件全部拷贝到客户机上去文件服务的任务文件服务的任务 两两个个任任务务：文文件件存存储储和和文文件件寻寻址址其其中中，文文件件寻寻址址利利用用文文件件位位置置映映射射方方法法完完成成文文件件的的定定位位，文文件件访访问问通通过过调调用用外外存存访访问问功功能能完完成成文文件件的的存存储储，外外存存访访问问功功能能通通常常以以块块服服务务的的形形式式提提供供。
所所以以，文文件件服服务务的的基基本本任任务务就就是是，提提供供通通用用和和有有效效的操作集合，为多个客户提供大容量的外存设备的操作集合，为多个客户提供大容量的外存设备南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务另另外外，文文件件服服务务还还要要解解决决保保护护问问题题，即即严严格格控控制制用用户户对对于于文文件件的的访访问问，从从而而保保证证文文件件的的一一致致性性文文件件服服务务可可以以同同时时支支持持多多个个目目录录服服务务，这这样样，目目录录服服务务可可以以采采用用多多种种不不同同语语法法，从从而而使使文文件件服服务务可可以以用用于于不不同同的的目目录录服服务务一一个个文文件件服服务务可可能能同同时时管管理理几几个个目目录录服服务务支支持持的的多多个个文文件件集集合合，每个集合中的文件属性记录和结构可能还有差异每个集合中的文件属性记录和结构可能还有差异南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务4.2.2 4.2.2 文件服务界面文件服务界面 所所谓谓界界面面，主主要要提提供供服服务务的的基基本本操操作作名名和和调调用用格格式式及及简单功能描述。
简单功能描述文件的文件的UFIDUFID；参数；参数;数据数据;出错信息出错信息南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务4.3 目录服务目录服务 目目录录服服务务定定义义了了构构成成文文件件(或或目目录录)名名的的某某种种字字母母表表示示语语法法文文件件名名可可以以是是由由一一个个或或多多个个字字符符、数数字字及及特特殊殊字字符符构构成成的的字字符符串串有有些些系系统统通通过过句句点点将将文文件件名名分分成成两两部部分分，如如progprogc c表表示示C C语语言言文文件，件，maimmaimtxttxt表示文本文牛，第二部分一般叫做文件扩展名表示文本文牛，第二部分一般叫做文件扩展名分分布布式式系系统统目目录录一一般般也也都都包包含含子子目目录录，从从而而使使用用户户可可以以给给相相关关文文件件：分分组组，形形成成层层次次文文件件系系统统因因此此，目目录录服服务务就就包包括括创创建建、删删除除、进进入入、退退出出和和查查找找文文件件等等功功能能有有的的系系统统还还提提供供建建立立目目录录指指针针的的功功能能，指指针针可可以以设设置置到到任任何何目目录录中中，这这样样构构成成的的目目录录和和文文件件就就不不再再只只是是树树型型结结构构，而而是是图图(网网状状)结结构构，从从而而使使表表示示能能力力更更强，强，当然，管理也就更复杂。
当然，管理也就更复杂南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 设设计计分分布布式式文文件件服服务务的的关关键键在在于于，是是否否支支持持所所有有机机器器对于目录层次具有同样的视图对于目录层次具有同样的视图4.3.1 4.3.1 目录服务的任务目录服务的任务 大大多多数数分分布布式式系系统统都都使使用用两两级级命命名名方方式式，即即每每个个文文件件(或或其其它它对对象象)都都有有一一个个符符号号名名(常常称称为为文文件件名名)和和一一个个内内部部二二进进制制名名(用用UFIDUFID表表示示)符符号号名名一一般般供供程程序序员员或或用用户户使使用用，如如prog.cprog.c；内内部部二二进进制制名名供供系系统统使使用用所所谓谓目目录录，就就是是一一组组文文件件名名到到UFIDUFID的的映映射射表表目目录录服服务务最最基基本本的的任任务务就就是是将将文文件件名名映映射射到到UFIDUFID，通通过过这这一一映映射射可可以以取取代代传传统统文文件件系系统统中中的的打打开开(Open)(Open)文文件件操操作作，客客户户一一旦旦拿拿到到UFIDUFID，便便可可以以操操作文件作文件.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 目目录录服服务务本本身身要要确确保保UFIDUFID正正确确送送到到请请求求客客户户。
目目录录服服务务还还要要检检查查客客户户的的合合法法性性，通通过过访访问问控控制制表表做做合合法法性性检检查查，最最终终决决定是否发出一个定是否发出一个UFID.UFID.目目录录服服务务的的功功能能也也可可以以分分解解为为基基本本功功能能和和辅辅助助功功能能两两类类,基基本本功功能能提提供供文文件件名名到到文文件件标标识识的的映映射射，它它是是构构造造面面向向用用户户的的目目录录服服务务的的基基础础，包包括括名名字字、结结构构和和访访问问控控制制方方法法根根据据授授权权客客户户的的请请求求允允许许用用户户执执行行UFIDUFID所所指指出出的的文文件件增增、删删操操作作辅辅助助功功能能包包括括文文件件名名的的词词法法分分析析、建建立立目目录录形形成成层层次次结结构构和和其其它它复复杂杂操操作作因因此此，目目录录服服务务可可以以在在给给定定目目录录中中查查找找文文件件名名，然然后后得得到到UFIOUFIO，每每个个UFIDUFID都都指指出出对对于于文文件件的的相相关关访访问问权权限限，如如对对文文件拥有者可读、写和删除，对于其它用户只读件拥有者可读、写和删除，对于其它用户只读南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务目目录录通通常常以以文文件件形形式式存存储储，因因此此，目目录录服服务务本本身身是是文文件件服务的一个客户，每个目录本身有一个服务的一个客户，每个目录本身有一个UFID。
4.3.2目录服务界面目录服务界面目目录录服服务务定定义义了了一一组组目目录录服服务务操操作作不不同同系系统统有有响响应应的的约定约定.目录服务的定义遵循约定记号目录服务的定义遵循约定记号4.3.3文件属性与目录访问文件属性与目录访问目目录录服服务务要要进进行行访访问问控控制制，可可以以通通过过访访问问和和更更新新文文件件属属性性完完成成如如可可以以在在新新文文件件名名加加入入目目录录时时，在在文文件件属属性性中中设设置置访访问问许许可可；提提供供查查看看文文件件属属性性的的操操作作；还还可可以以提提供供允允许许文文件件拥拥有有者者认认定定或或重重设设其其它它用用户户的的许许可可权权限限、及及将将所所有有权权转转让让给给其它用户的操作其它用户的操作南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务文文件件系系统统除除管管理理数数据据外外，还还要要管管理理许许多多相相关关信信息息，如如创创建建日日期期、最最后后访访问问日日期期和和最最后后修修改改日日期期、文文件件类类型型、文文件件所所属属目目录录和和访访问问控控制制信信息息等等，我我们们称称这这些些信信息息为为文文件件属属性性。
文文件件系系统统将将文文件件属属性性作作为为一一组组不不可可分分解解的的数数据据，文文件件属属性性可可以以执行读写访问，执行读写访问，但没有长度或结构等操作但没有长度或结构等操作目目录录服服务务不不但但要要确确定定属属性性中中的的内内部部结结构构和和所所存存数数据据值值，还还要要负负责责文文件件属属性性的的访访问问，包包括括读读取取和和修修改改如如改改变变访访问问日日期、修改文件所属关系和管理访问控制表等期、修改文件所属关系和管理访问控制表等目目录录存存储储着着所所有有文文件件的的拥拥有有者者，文文件件拥拥有有者者可可以以对对其其文文件执行所有操作，如创建、读、写和删除等件执行所有操作，如创建、读、写和删除等南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务问问题题是是让让谁谁来来执执行行目目录录服服务务中中的的LookUp、AddName、ReName和和UnName操操作作，查查看看或或修修改改文文件件属属性性?当当用用户户具具有有各各自自独独立立、分分离离的的目目录录时时，目目录录的的UFID可可能能认认定定为为一一种种权权能能，不不需需要要进进一一步步的的访访问问控控制制；但但是是要要访访问问共共享享目目录录时时，则则需需要要访访问问控控制制。
一一个个简简单单的的解解决决办办法法是是，让让目目录录拥拥有有者者的的访访问许可模式与文件拥有者的访问许可模式取得一致问许可模式与文件拥有者的访问许可模式取得一致另另外外，为为用用户户同同时时提提供供文文件件服服务务和和目目录录服服务务操操作作可可以以克克服服文文件件的的丢丢失失问问题题对对于于文文件件创创建建，用用户户通通过过创创建建操操作作指指定定的的文文件件名名和和目目录录名名，然然后后依依靠靠文文件件服服务务Create操操作作和和目目录录服服务务AddName操操作作完完成成对对于于文文件件删删除除，通通过过删删除除操操作作指指定一个定一个UFID和目录名和目录名南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务4.3.4树型结构树型结构在在UNIX提提供供的的树树型型文文件件系系统统中中，包包含含组组织织成成树树型型结结构构的的许许多多目目录录，通通过过链链使使文文件件具具有有多多个个名名字字，可可以以使使用用基基本本的的文文件件和和目目录录服服务务来来实实现现树树型型结结构构的的目目录录集集合合可可以以通通过过叶叶、根根和和内内部部结结点点构构成成。
树树根根是是一一个个目目录录，其其UFID是是共共用的树树中中任任何何结结点点或或叶叶结结点点就就是是文文件件或或目目录录，可可以以通通过过路路径径名名命命名名文文件件或或目目录录，路路径径是是由由多多部部分分组组成成的的表表示示路路径径的的名名字字。