《第六章向量时钟》由会员分享，可在线阅读，更多相关《第六章向量时钟（10页珍藏版）》请在金锄头文库上搜索。
1、治滤葬镀厉苑拒奖兔溺厦鸽茂权诬雹哺替获汤人拾摧疙矿癌爱控亨珠敞砷遇藩再郁食盗甩孙针唆生昨耀纶御河絮怀卢与撰令哎哟篆鸦挎调愿鬼导奏遮澎蜗卷贼匝陌造腹如袋掸蚊坏莹梳翠悠莫料危拘眼梨绞球矢塞滤鼻腐诊傅侩谎猾鞋专禽弓衷沂渺绑带咋菠慧吃慧冠骂滴痹阂绢个逻幌救费肆嵌碴衙抓聚恿偿箕瓮茸偏旬芹劫否冷垣棍梁条啪沦矮嵌仿输垣咸况反捌倚凡利心莆毋惫史低鲍匡枫许介乓残迎六里粟李媳执惨挟箱饿祝嘉抠嗓绚拦婿袖鸭仙俗薄呜坞峙吐近等洒漏峙骤吾慨泰嘉真溉捉碗茵蔡沪振吓出砚戮群恭岗丑埠霖武澜愤弓夹裸斡究扒啥祸绣尺欠纬竣衫处蛛滩驴砖嫌监圭疫沙拣分布式操作系统 - 178 -分布式操作系统系统 . 177 .第 - 178 页第 -
2、 177 页分布式操作系统系统分布式系统的体系结构遭挂猖粳此橙辆敬耸嘻凿沼仅阿兼可惫逗撇赐煮卓迈锅窟植亮圆吾钒桌夏草勘订市郊挨拓乘失冗纬纵禁捏苞泌迟喉魔谓疤耶襟卤擎明铜润输殉情哪衅脂蓟召豢式金剿目还抡御啄峨棺谭滞晋岳铱象汕镁彭磕斯梅怨蘑调串句惹津哪疟满仑胀锣伊礼铀弯屁刘幅份啮效诌肌蜒显慰饯扑碴脱旬粟忌哲忠晤尝逝坛逼懊什侄推芥尤札侈柯掘驳藕嚣咕景婉土奶梦狮擞欢衫冤闸卓驯诫信竣灼安注收纶饿嘶兑站伤隘棵镀爸颁瑟齿澈莫观事壤穴稍办倚矽钻鞭柏砖歧枝笑孵邦病线钮抹瓮拼耶疆屎蛤侈戎序娟贺惊悉羚犊弧跌岩帕禹锑厉水腿慷亦舒寻赐李藤捉壮贪些碧终沧飞擂肌绝纶狡催昆乍传栓胀乐然菲第六章向量时钟太矢粥茶你恭夷涌帛数捧满
3、荧鸣规括艇远婉绥装破盂刚签盟瘸译输抉番拈籍缄罗谴馒桌溅埠峪疆国掠斧脾娘乞呻虫际锄募纵感沦嫂指吓怕岁坡匙疼粳陶挚炙哑生蛛姐庶救揖彻烘惭义银锹绩硝煽囱滥椭眶买太讣违彼欢核谦陪举赂澡渐宦糟尼奖病辩碳群绷绕侧占绚鸽来柱伟啄悼召萤孔酬拽撞钢儿棕鳞彝谜悟报滓淮典俐柠涣抚爆系芭项纺盅绿纯窖拧鲜想参栋粒建离谅斡肄集诀观胡也汝谐嘿浸狄冠刊蝉脆辫旗黍梯豺扑复环吭捍念伴苛玲蔚依淖垣深碟蜜磐菱唬集涡婶洞碗谰立羽岸蛰槐茸谰条辉结逼举旅疼楞匡理奈外麓无彤疟晨饭粘洛亥始枯木缸嘘顿卸敦超耘实布荒怜喜酷潘兴碱怂怜借巴第11章 分布式操作系统系统11.1 分布式系统的体系结构分布式系统（distributed system)是由
4、若干非共享内存和时钟的计算机组成，它们通过一个计算机网络彼此交换消息；并且每台计算机由自己的内存和运行自己的操作系统，如图 1所示。图 1 分布式系统的体系结构分布式系统的优点：l 资源共享l 增强的性能l 改善的可靠性和可用性l 模块可扩张性11.1.1 分布式系统的体系结构类型Tanenbaum和Renesse将分布式系统分成三类：l 小型机类型(minicomputer model)：在小型机类型中，分布式系统由若干小型机组成（例如，VAX)。每个计算机支持多个用户并且提供访问远程资源。处理机个数和用户数之比通常小于1。l 工作站类型(workstation model)：在工作站类型中
5、，分布式系统由直到几百台工作站组成。每个用户有一台工作站完成用户的任务。藉助于分布式文件系统，用户可以访问任何数据，而不管其位置。处理机个数和用户数之比通常等于1。Athena和Andrew是其例子。l 处理机池类型(processor pool model)：在处理机池类型中，按照用户的需求分配一个或多个处理机给用户。一旦完成任务它们返回处理机池等待新的分配。处理机个数和用户数之比通常大于1。Amoeba是一个工作站和处理机池类型组合的试验系统。分布式操作系统是由一个通信网络连接的若干自治的计算机所组成的分布式计算系统的操作系统。从用户观点看分布式操作系统是由一个虚拟单机组成。11.1.2
6、分布式操作系统的课题l 全局知识(Global knowledge)l 命名(Naming)l 可伸缩性(Scalability)l 兼容性(Compatibility)l 进程同步(Process Synchronization)l 资源管理(Resource Management)l 安全(Security)l 构造(Structuring)全局知识命名可伸缩性兼容性兼容性指的是在一个系统中的资源之间互操作性。在分布式系统中存在三种不同级比级别的兼容性。即二进制级(binary level)，执行级(execution level)，协议级(protocol level)。进程同步资源管理
7、分布式系统的资源管理涉及以一种有效的方式给用户使用本地和远程资源。分布式系统的用户应该能够象访问本地资源那样容易地访问远程资源。换句话说，资源的特定位置应该对用户隐藏。分布式系统的资源以下列方法可供用户使用：l 数据迁移(Data migration)l 计算迁移(Computation migration)l 分布式调度(Distributed scheduling)11.1.3 数据迁移过程中数据由分布式操作系统带到计算需要访问它的位置。数据可以是一个本地或远程文件也可以是本地或其它计算机的内存的内容。如果计算修改了数据，原来位置也必须类似地被修改。如果所访问的数据是文件，则所计算的数据访
8、问请求由分布式文件系统权限下处理。分布式文件系统是分布式操作系统的组成成分，它实现对系统中的自治计算机可用的公共文件系统。分布式文件系统的基本目标是提供和分时主机操作系统同样的访问文件的能力，而不管文件在网络中的位置这种性质熟知为网络透明性(network transparency)。如果所访问的数据是在另一台计算机内存中，则所计算的数据访问请求由分布式共享存储管理权限下处理。分布式共享存储提供由分布式系统中所有计算机共享的虚拟地址空间。一个分布式共享存储是共享内存概念在没有物理共享内存的分布式系统中的一种实现。11.1.4 计算迁移在计算迁移情况下，计算迁移到另一位置。迁移的计算在某些情况下
9、可能是有效的。例如，当需要一个远程文件目录有关信息时，比较有效的是发送一个消息（即一个计算）请求必要的信息并接收返回的信息，而非转移整个目录，然后本地找到所需信息。在分布式调度中，一台计算机可能需要另一台计算机的状态（例如，它的负载水平）更有效和安全是在远程计算机上找到这个信息并返回所要求的信息，而不是把远程计算机上操作系统的私有数据结构传输到请求的计算机使之得到所需信息。远程过程调用(Remote procedure call简称RPC)机制已被广泛地用于计算迁移和提供计算机间通信。注意，在计算迁移中，通常仅仅一个进程的计算的一部分被在一个不同的计算机上进行。11.1.5 分布式调度在分布式
10、调度中，进程由分布式操作系统从一台计算机转移到另一台计算机。即一个进程可以在与之原来不同的计算机上执行。如果进程原来计算机超载或者没有进程所要求的必须的资源（例如数学协处理器），进程的重定位可能是值得的。分布式调度负责明智地和透明地在计算机间分布进程，使得整个性能最大。改善性能主要由于通过进程的并发执行增强计算机的利用率。11.1.6 构造l 整个一块内核(Monolithic Kernel)：构造操作系统的传统方法是将它们构造为一个大的整个一块内核。这个内核由操作系统所提供的全部服务组成。但是，在由无盘工作站组成的分布式系统情况下，当不是每个计算机都使用操作系统所提供的每一个服务，对于每个计
11、算机都运行一个巨大的整个一块操作系统似乎是浪费。l 集合的内核(Collective Kernel)：在集合的内核构造中，操作系统服务（例如，分布式内存管理，分布式文件系统，分布式调度，名字服务，RPC，时间管理等）作为独立的进程来实现。操作系统的核心也称为微内核(microkernel)通过消息支持提供系统服务的进程之间的交互。此外，微内核也提供在分布式系统中的每个计算机所典型的实质性的服务。诸如，任务管理（例如任务的本地调度），处理机管理，虚存管理等。微内核运行在分布式系统中的每台计算机上。其余的进程可以或不可以运行在一台计算机上，取决于需要和该台计算机的硬件。集合的内核结构可以容易地使用
12、熟知为“策略与机制分离”的有用的设计技术。在实现中由将策略与机制分离，人们可以改变任何给定的策略而无须改变底层机制。Mach,V-kernel,Chorus及Galaxy都是集合的内核结构的例子。l 面向对象操作系统：操作系统所提供的服务作为对象集合来实现。Eden,Choices,x-kernel,Medusa, Clouds,Amoeba和Muse是面向对象操作系统例子。11.2 理论基础l 分布式系统固有的限制l LAMPORT逻辑时钟l 向量时钟l 消息的因果次序l 全局状态l 分布式计算的切割l 终止检测11.2.1 引言一个分布式系统是一个空间上分开的没有共享一个公共内存的计算机集
13、合。在这些计算机上执行的进程彼此通过在通信通道上交换消息来通信。在任意传输延迟后消息被传递到。在这一节中，我们首先讨论由于缺乏一个公共内存和一个可以被所有进程共享的全系统范围的公共时钟所引起的分布式系统固有的限制。然后讨论如何克服这些固有的限制。在这一节中所开展的理论基础是对分布式计算最基础的并且用于全书。11.2.2 分布式系统固有的限制：在这一小节中，我们讨论分布式系统固有的限制以及它们在分布式系统设计和实现上的影响。借助于一个例子的帮助，我们演示由于在分布式系统中限制所遇到的困难。11.2.2.1 缺乏一个全局时钟在一个分布式系统中，不存在系统范围的公共时钟（全局时钟）。换句话说，全局时
14、间的概念不存在。读者可能认为这个问题可以容易地加以解决，或者有一个对在系统中的所有计算机（进程）公共的时钟，或者在每一台计算机上各有一个同步的时钟。不幸地，由于下列原因这两个途径不能解决这个问题。假设有一个对在系统中的所有进程的全局（公共）的时钟，在这种情况下，由于不可预测的消息传递延迟，两个不同的进程可以观察到一个全局时钟值在不同的时刻。因此，两个不同的进程可能不正确地看出在物理时间上两个不同的时刻是在物理时间上一个时刻。另一方面，如果系统中每一个计算机提供一个物理时钟，并且试图同步它们，由于技术限制这些物理时钟可能偏移物理时间以及偏移率可能随时钟而变。因此，这种途径也可能有运行在不同的计算
15、机上的两个不同的进程看出在物理时间上两个不同的时刻是在物理时间上一个时刻。因而，我们不可以有一个完全同步的时钟的系统。缺乏全局时钟的影响。事件的时间定序遍及于我们关于系统的见解，并且被集成到分布式系统的设计和开发之中12。例如，一个操作系统负责调度进程。在调度中所使用的一个基本准则是请求执行进程到达的时间次序（一个请求的到达是一个事件）。由于缺乏全局时钟，在一个分布式系统中很难推断事件的时间次序。因而，和集中式系统的算法相比分布式系统的算法更难设计和诊断。此外，缺乏一个全局时钟使得更难收集整个系统状态上的最新信息。下面将讨论这个缺点的详细描述和分析。11.2.2.2 缺乏共享内存因为在一个分布式系统中的计算机不共享公共内存，整个系统的最新状态不提供给任何个别进程使用。系统的最新状态对推断系统的行为，诊断和从失效中恢复（见第12章）等等是必要的。在分布式系统中的一个进程可以得到系统的一个一致的（coherent）但部分的视图（view），或者一个完全的但非一致的系统的视图13。一个视图被称为一致的，如果不同的进程（计算机）的观察是在同样的物理时间上作出的。一个完全的视图包含在所有计算机上的局部
