中科大分布式云计算期末考试版本4.0

1、1、分布式系统的定义：分布式系统是若干独立计算机的集合，这些计算机对于用户来说就像单个相关系统。2、分布式系统的特点：各种计算机之间的差别以及计算机之间的通信方式的差别对用户来说是隐藏的；用户和应用程序无论在何时何地都能够以一种一致和统一的方式与分布式系统进行交互。3、分布式系统的目标：分布式系统必须能够让用户方便地访问资源；必须隐藏资源在一个网络上分布这样一个事实；必须是开放的；必须是可扩展的。4、透明性：分布式系统的重要目标之一是将它的进程和资源实际上在多台计算机上分布这样一个事实隐藏起来。如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机的系统，这样的分布式系统就称为透明的。透明

2、性的类型：访问透明性：隐藏数据表示形式的不同以及资源访问方式的不同位置透明性：隐藏资源所在的位置迁移透明性：隐藏资源是否移动到另一个位置重定位透明性：隐藏资源是否在使用过程中移动到另一位置复制透明性：使用资源是否对资源进行复制并发透明性：隐藏资源是否由若干相互竞争的用户共享故障透明性：隐藏资源的故障和恢复5、开放的分布式系统：系统应该符合定义良好的接口、系统应该支持应用程序的可移植性、系统应该容易互操作。6、系统的可扩展性：规模上可扩展、地域上可扩展和管理上可扩展。7、扩展技术：Hidecommunicationlatencies隐藏通信等待时间、Distribution分布技术、Replic

3、ation/caching复制技术。复制/缓冲：将组件复制并拷贝分布到系统各处；缓冲与复制不同的是，是否进行缓存是由要访问资源的客户决定的，而不是资源拥有者决定。缺点是一致性问题。8、分布式系统类型：DistributedComputingSystems分布式计算系统、DistributedInformationSystems分布式信息系统、DistributedPervasiveSystems分布式嵌入系统，又叫分布式普适系统。9、体系结构样式：根据组件、组件之间相互的连接方式、组件之间的数据交换以及这些元素如何继承到一个系统中。组件是一个模块单元，可以提供良好定义接口，在其环境中是可替换的

4、。10、连接器connector:在组件之间传递通信、使组件相互协调和协作。根据组件和连接器的使用，划分成不同体系结构：分层体系结构、基于对象的体系结构、以数据为中心的体系结构、基于时间的体系结构。11、幂等的（idempotent）：某个操作可以重复多次而无害出。有些请求是幕等的，有些不是，不能用某一个解决方法来处理消息的丢失问题。点对点体系结构（P-to-P）1、P2P的一个常见问题是如何高效的定位节点，也就是说，一个节点怎样高效的知道在网络中的哪个节点包含它所寻找的数据。2、DHT的主要思想是：首先，每条文件索引被表示成一个（K,V）对，K称为关键字，可以是文件名（或文件的其他描述信息）

5、的哈希值，V是实际存储文件的节点的IP地址（或节点的其他描述信息）。所有的文件索引条目（即所有的（K,V）对）组成一张大的文件索引哈希表，只要输入目标文件的K值，就可以从这张表中查出所有存储该文件的节点地址。然后，再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上，使得每个节点负责维护其中的一块。这样，节点查询文件时，只要把查询报文路由到相应的节点即可（该节点维护的哈希表分块中含有要查找的（K,V）对）。Chord算法就是解决网络内节点定位问题的一种P2P协议，它通过多个节点跳转找到我们所查找的资源。3、Chord里面的基本要素：节点ID

6、：NID（nodeidentifier），表示一个物理机器；资源ID：KID（keyidentifiers），原为键ID,其实际表示一个资源；Chord环：ChordRing，NID和KID被分配到一个大小为2F的环上，用于资源分配（给某一个节点）和节点分布，以及资源定位。首先我们说资源分配，资源被分配到NID=KID的节点上，这个节点成为k的后继节点，是环上从k起顺时针方向的第一个节点，记为successor（k）。而节点分布则顺时针将节点N由大到小放在这个环上。现在N26节点要加入系统，首先它指向其后继N32,然后通知N32,N32接到通知后将N26标记为它的前序节点（predecesso

7、r）。然后N26修改路由表，下一次N21运行stabilize。询问其后继节点N32的前序节点是不是还是自己，此时发现N32的前序节点已经是N26。于是N21就将后继节点修改为N26,并通知N26自己已经将其设置为后继节点，N26接到通知后将N21设置为自己的前序节点。inill.1-IIT：JCIHLli./IH*就611Chord资源定位（KeyLocation）:资源定位是Chord协议的核心功能这个加入操作会带来两方面的影响：1）正确性方面：当一个节点加入系统，而一个查找发生在stabilization结束前，那么此时系统会有三个状态：A.所有后继指针和路由表项都正确时：对正确性没有影

8、响。B.后继指针正确但表项不正确：查找结果正确，但速度稍慢（在目标节点和目标节点的后继处加入非常多个节点时）。2）效率方面：当stabilization完成时，对查找效率的影响不会超过O（logN）的时间。当stabilization未完成时，在目标节点和目标节点的后继处加入非常多个节点时才会有性能影响。可以证明，只要路由表调整速度快于网络节点数量加倍的速度，性能就不受影响。4、Chord节点失败的处理我们可以看出，Chord依赖后继指针的正确性以保证整个网络的正确性。但如图，若N14,N21,N32同时失效，那么N8是不会知道N38是它新的后继节点。为了防止这样的情况，每个节点都包含一个大小

9、为r的后继节点列表，一个后续节点失效了就依次尝试列表中的其他后继节点。可以证明，在失效几率为1/2的网络中，寻找后继的时间为O（logN）4、Chord的特征和应用，特征：去中心化，高可用度，高伸缩性，负载平衡，命名灵活。应用：全球文件系统、命名服务、数据库请求处理、互联网级别的数据结构、通信服务、事件通知、文件共享。第三章：进程1、不同层次提供4个不同界面：由机器指令组成，可由任何程序及其的软硬件界面；由机器指令组成，只有特权程序才可激活的软硬件界面；由操作系统提供的系统调用组成的界面；由库调用组成的界面，通常形成了所谓的应用程序编程接口。2、虚拟化可采用的两种方式:构建运行时系统，提供一套

10、抽象指令集执行程序一进程虚拟机；做成一层完全屏蔽硬件但提供一个人同样指令集的界面一虚拟机监视器。第六章：同步化1、物理时钟：高频振荡器（石英晶体）、计数器和保持寄存器。高频振荡器的每次震荡使计数器减1,档计数器减为0时，产生一个中断，计数器从保持计数器中重新装入初始值。国际原子时间（TAI）.UTC统一协调时间isTAIwithleapseconds.3、Lamport逻辑时钟：为了同步logicalclocks,Lamport定义了一个关系叫做happens-before（先发生），记作a-b意味着所有的进程都agree事件a发生在事件b之前。在两种情况下，可以很容易的得到这个关系：如果事件

11、a和事件b是同一个进程中的并且事件a发生在事件b前面，那么a-b；如果进程A发送一条消息m给进程B,a代表进程A发送消息m的事件，b代表进程B接收消息m的事件，那么a-b（由于消息的传递需要时间）。如果事件a和事件b发生在不同的进程，并且这两个进程没有传递消息，那么既不能推到a-b也不能推到b-a，这样的两个事件叫做并发事件三个机器上各自跑着一个进程，分别为P1,P2,P3,由于不同的机器上的quartzcrystal不一样，所以不同的机器上的时钟速率可能是不同的，例如当P1所在的机器tick了6次，P2所在的机器tick了8次。图中，P1给P2发送了消息m1,m1上附带了发送m1时的时钟6,

12、随后P2收到了m1,根据P2接收到m1时的时钟，认为传输消息花了16-6=10个tick，随后，P3给P2发送消息m3,m3附带的发送时钟是60,由于P2的时钟走的比P3的慢，所以接收到m3时，本机的时钟56比发送时钟60小。这是不合理的，需要调整时钟，如图中，将P2的56调整为61,即m3的发送时钟加1。Lamportlogicalclocks的实现:每个进程Pi维护一个本地计数器Ci,相当于logicalclocks,按照以下的规则更新Ci；每次执行一个事件（例如通过网络发送消息，或者将消息交给应用层，或者其它的一些内部事件）之前，将Ci加1；当Pi发送消息m给Pj的时候，在消息m上附着上

13、Ci；当接收进程Pj接收到Pi的发送的消息时，更新自己的Cj=maxCj,Ci。向量时钟:Lamportlogicalclocks的问题是：事件a和事件b实际发生的先后顺序不能仅仅通过比较C（a）和C（b）来决定。Lamportlogicalclocks没有capturecausality（因果关系），而causality可以通过VectorClocks来capture，用VC（a）来表示事件a的VectorClock。有性质：VC（a）VC（b）可以推出事件a发生在事件b之前。为每个进程Pi维护一个向量VC,也就是Pi的VectorClock，这个向量VC有如下属性：VCii是到目前为止进程

14、Pi上发生的事件的个数；VCik是进程Pi知道的进程Pk发生的事件的个数（即Pi对Pj的了解）。每个进程的VC可以通过以下规则进行维护（和Lamportlogicalclocks算法类似）:进程Pi每次执行一个事件之前，将VCii加1;当Pi发送消息m给Pj的时候，在消息m上附着上VCi（进程Pi的向量时钟）；当接收进程Pj接收到Pi的发送的消息时，更新自己的VCjk=maxVCjk,VCik,对于所有的k。因果有序多播一个进程组中，每个进程需要广播消息给其它进程（相当于一个并发更新问题），一个消息被delivered到应用层，仅当所有的causally发生之前的消息都被收到。假设：Pi给Pj

15、发送消息m,那么Pj可以将消息m交给应用层必须首先满足上面两个条件：VCji=VCii-1VCik=VCjkforallkHi第一个条件的意思是指Pj看到了Pi发生的所有的事件（不包括本次发送消息m的时间）；第二个条件意味着，Pj看到了其它的所有的进程看到的事件。以上两个条件说明，对消息m做下一步动作（比如本例中的将消息m交给应用层）之前，所有的m依赖的消息都收到了。4、互斥:基于令牌的解决方案：拥有令牌这获得使用资源的权限，可以避免饿死和死锁，但令牌可能会丢失；基于许可的解决方案：获得其他进程的许可来使用资源。集中式算法:保证互斥的实现，且公平，但协调者是故障点，会出现单点崩溃。非集中式算法

16、：扩展集中式协作者，进程每次访问资源需要多于一半的协作者同意即可，解决单点故障。分布式算法：如该进程不想进入临界区，则立即发送0K消息；如该进程想进入临界区，则把自己的request消息时间戳与收到的request消息时间戳相比较。获得大多数进程的许可即可。令牌环算法。四种算法中集中式算法是最简单也最有效的。第七章：一致性和复制进行数据复制主要出于两个目的：可靠性和性能。数据一旦被复制，就会带来一致性的问题。以数据为中心的一致性模型严格一致性（strictconsistency）:对于数据项x的任何读操作将返回最近一次对x进行写操作的结果所对应的值。严格一致性是限制性最强的模型，但是在分布式系

17、统中实现这种模型代价太大，所以在实际系统中运用有限。顺序一致性：任何执行结果都是相同的，就好像所有进程对数据存储的读、写操作是按某种序列顺序执行的，并且每个进程的操作按照程序所制定的顺序出现在这个序列中。也就是说，任何读、写操作的交叉都是可接受的，但是所有进程都看到相同的操作交叉。顺序一致性由Lamport（1979）在解决多处理器系统的共享存储器时首次提出的。因果一致性：所有进程必须以相同的顺序看到具有潜在因果关系的写操作。不同机器上的进程可以以不同的顺序看到并发的写操作（Hutto和Ahamad1990）。假设P1和P2是有因果关系的两个进程，例如P2的写操作信赖于P1的写操作，那么P1和

18、P2对x的修改顺序，在P3和P4看来一定是一样的。但如果P1和P2没有关系，那么P1和P2对x的修改顺序，在P3和P4看来可以是不一样的。FIFO致性：在因果一致性模型上的进一步弱化，要求由某一个使用者完成的写操作可以被其他所有的使用者按照顺序的感知到，而从不同使用者中来的写操作则无需保证顺序，就像一个一个的管道一样。相对来说比较容易实现。弱一致性：要求对共享数据结构的访问保证顺序一致性。对于同步变量的操作具有顺序一致性，是全局可见的，且只有当没有写操作等待处理时才可进行，以保证对于临界区域的访问顺序进行。在同步时点，所有使用者可以看到相同的数据。释放一致性：弱一致性无法区分使用者是要进入临界

19、区还是要出临界区，释放一致性使用两个不同的操作语句进行了区分。需要写入时使用者acquire该对象，写完后release,acquire-release之间形成了一个临界区，提供释放一致性也就意味着当release操作发生后，所有使用者应该可以看到该操作。入口一致性：入口一致性要求每个普通的共享数据项都要与某种同步变量关联。数据存储满足下列条件，那么它符合入口一致性：在一个进程获取一个同步变量签，所有由此同步变量保护的共享数据的更新都必须已经由相应进程执行完毕。、在一个进程对一个同步变量的独占访问被允许前，其他进程不可以拥有这个同步变量，也不能以非独占方式拥有这个同步变量、一个进程对一个同步变

20、量执行独占访问之后，对该同步变量的所有者进行检查之前，任何其他的进程都不能执行下一个独占访问。Hi倉址3询可搖腮如间博序沁It阳習曲乱1相冋的宵列阳有的貝車诉问-而目问胡上冲U:-同时册闻号前静序衙育也旦:丄相同閻歼昔钊所肖茁拦字術可.：.诂问苹到于眄问FII序的窩育旳进圧伯辰扫1.宇li刽13舉拥光fr=理鼻旳弼衙育1扱事戈不P的世腔3定出耳抬岸的籾庁忆互看列右15；悴来自下阿的迪程枫肖作可駅不归就霞g胖曲閻序坤)Ej:只百珈行一挟同寸1.共锁財很认为是TS的二一.廿=：刊主也；:1ST=-7-J-:.z-I-rZc-：i较性沁-jj结以客户为中心的一致性模型1.最终一致性：最终一致性指的是

21、在一段时间内没有数据更新操作的话，那么所有的副本将逐渐成为一致的。例如OpenStackSwift就是采用这种模型。以一次写多次读的情况下，这种模型可以工作得比较好。2单调读：如果一个进程读取数据项x的值，那么该进程对x执行的任何后续读操作将总是得到第一次读取的那个值或更新的值单调写：一个进程对数据x执行的写操作必须在该进程对x执行任何后续写操作之前完成。写后读：一个进程对数据x执行一次写操作的结果总是会被该进程对x执行的后续读操作看见。5读后写：同一个进程对数据项x执行的读操作之后的写操作，保证发生在与x读取值相同或比之更新的值上第八章：容错性1、系统容错的一些要求：（1）可用性（avail

22、ability）用来描述系统在给定时刻可以正确的工作。（2）可靠性（reliability）指系统在可以无故障的连续运行。与可用性相反，可靠性是根据时间间隔而不是任何是可以来进行定义的。如果系统在每小时中崩溃1ms,那么他的可用性就超过99.9999%,但是它还是高度不可靠的。与之相反，如果一个系统从来不崩溃，但是要在每年8月中停机两个星期，那么它是高度可靠的，但是它的可用性只有98%。因此，这两种属性并不相同。（3）安全性（safety）指系统偶然出现故障的情况下能正确操作而不会造成任何灾难。（4）可维护性（maintainability）发生故障的系统被恢复的难易程度。如果一个系统无法满足

23、对用户的承诺，这个系统被称为失灵（fail）。一个系统在正常工作时会在若干种运行状态之间变迁，一旦出现异常，则该系统进入错误（error）状态。一个系统的错误状态可能是导致系统失灵的原因。这里使用了一个模糊的术语可能”，因为有的错误状态并不一定导致系统失灵，如系统死锁是一种错误状态，当死锁被排除后，系统又可以恢复正常运行。造成错误的原因是故障（fault），故障的种类繁多，软件和硬件都可能产生故障，而且，某些场合下，与系统无关的外部环境也可能引发故障。2、故障分类：故障通常被分为暂时的（transient）、间歇的（intermittent）和持久的（permanent）。不同类型的故障：WK

24、胆寻羽障机J但是在傅札之椚工作正常服昔匪不能flfas卒未的址尹胆昔期不龍按世到来的消曲决爲故陣不龍奏爲徂桓埜时枷UH胆务縣的申血柱*埜时值1间隔乏申卜胆舟期茁用应不正确响应的值猎袞蕊钟抠站P1IILIll；RE汨認可龍毎陲环HE叵1广主脱腥旳应3、使用冗余来掩盖故障：如果系统是容错的，那么它能做的最好的事情就是对其他进程隐藏故障的发生。关键技术是使用冗余来掩盖故障。有三种可能：信息冗余、时间冗余和物理冗余。信息冗余中，添加额外的位可以使错乱的位恢复正常。时间冗余中，执行一个动作，如果需要就再次执行。使用事务就是这种方法的一个例子。物理冗余中，通过添加额外的装备或进程使系统作为一个整体来容忍部

25、分组件的失效或故障成为可能。物理冗余可以在硬件上也可以在软件上进行。其中，一种著名的设计是TMR（三倍模块冗余，TipleModularRedundancy）。在包括TMR的系统中，每个关键模块中的部件都被复制了三份，采用多数表决的方法，确保当某些模块中的单个部件发生故障时，系统还可以正确的运行。4、进程恢复：为防止进程失败，把进程复制到组。当消息发送到组时，组中所有成员都接收它，一个进程失败，其他进程可以接管它。进程组是动态的，分为平等组和简单等级组。平等组通信：对称的，没有单独的失败点，但做出决定比较复杂。增加了延迟和开销。简单等级组通信：协作者的故障会使整个组崩溃，可以独自做出决定，不需

26、要其他进程参加。5、故障掩盖和复制如果系统能够经受k个组件的故障并且还能满足规范的要求，就称k容错。如果进程发生拜占庭失败，继续错误运行并发送出错误或随机的应答，那么至少需要2k+1个进程才能获得k容错。拜占庭协定的目标是一致性意见只与无故障进程的值有关。在一个含有k个有故障进程的系统中，只有有2k+1个无故障进程时才可以达到协定，即总进程为3k+1个。只有无故障进程数多于三分之二时才可以达成协定。如果有k个有故障进程，我们需要获得的是无障碍进程组的大多数投票，不管她们之中是否有有故障进程，如果有k个有故障进程，我们需要确保它们的投票和其他进程所有无障碍投票，仍然符合无障碍进程占大多数。如果有

27、2k+1个无障碍进程，只要有多于三分之二的无障碍进程，就可以达到协定。MapReduce是一种抽象模型，使我们只需执行简单计算，而将并行化、容错、数据分布、负载均衡等杂乱细节放在一个库里，使并行编程时不必关心它们。一个软件架构，是一种处理海量数据的并行编程模式。用于大规模数据集的并行运算。2、MapReduce的作用：对BigTable中的数据进行并行计算处理，使用BigTable或GFS存储计算结果。MapReduce实现了Map和Reduce两个功能：Map（映射）把一个函数应用于集合中的所有成员，然后返回一个基于这个处理的结果集。Reduce（规约）对结果集进行分类和归纳。在数据被分割后

28、通过Map函数的程序将数据映射成不同的区块，分配给计算机机群处理达到分布式运算的效果，在通过Reduce函数的程序将结果汇整，从而输出开发者需要的结果。MapReduce借鉴了函数式程序设计语言的设计思想，其软件实现是指定一个Map函数，把键值对（key/value）映射成新的键值对（key/value）,形成一系列中间结果形式的key/value对，然后把它们传给Reduce（规约）函数，把具有相同中间形式key的value合并在一起。昇Recap:MapReducePriiliiPtiniPiHiHi1L:ili.,kFnF-nlibP-nrirNlhHlinihn(winwrdaw/ja

29、fa)rIEivwilfanmlhnnnrakitrva-Luea工“I皿rwtii04-i4-lhanrh-vritHodtottwAnulciilpul文件存储位置：源文件：GFSMap处理结果：本地存储Reduce处理结果：GFS日志：GFS单词计数：Step1：自动对文本进行分割Step2:在分割之后的每一对key,value进行用户定义的Map进行处理，再生成新的key,value对step3:对输出的结果集归拢、排序（系统自动完成）Step4:通过Reduce操作生成最后结果3、MapReduce的容错Worker故障：Master周期性的ping每个worker。如果master

30、在一个确定的时间段内没有收到worker返回的信息，那么它将把这个worker标记成失效重新执行该节点上已经执行或尚未执行的Map任务重新执行该节点上未完成的Reduce任务，已完成的不再执行Master故障：定期写入检查点数据、从检查点恢复云计算：1、云计算特点（1）超大规模（2）虚拟化（3）高可靠性（4）通用性（5）高可扩展性（7）极其廉价（8）潜在的危险性。2、HDFS关键运行机制-保障可靠性的措施1）一个名字节点和多个数据节点-数据复制（冗余机制）2）存放的位置（机架感知策略）-故障检测3）数据节点-心跳包（检测是否宕机）-块报告（安全模式下检测）数据完整性检测（校验和比较）4）名字节

31、点（日志文件，镜像文件）-空间回收机制3、HDFS关键运行机制-读文件流程客户端缓存、流水线复制、并发写控制、客户端联系NameNode，得到所有数据块信息，以及数据块对应的所有数据服务器的位置信息、尝试从某个数据块对应的一组数据服务器中选出一个，进行连接（选取算法未加入相对位置的考虑）、数据被一个包一个包发送回客户端，等到整个数据块的数据都被读取完了，就会断开此链接，尝试连接下一个数据块对应的数据服务器，整个流程，依次如此反复，直到所有想读的都读取完了为止4、HDFS与GFS比较中心服务器模式的差异：GFS:多台物理服务器，选择一台对外服务，损坏时可选择另外一台提供服务；HDFS:单一中心服

32、务器模式，存在单点故障。子服务器管理模式差异：GFS：ChunkServer在Chubby中获取独占锁表示其生存状态，Master通过轮询这些独占锁获知ChunkServer的生存状态；HDFS：DataNode通过心跳的方式告知NameNode其生存状态；GFS中，Master损坏时，替补服务器可以快速获知ChunkServer的状态；HDFS中，NameNode损坏后，NameNode恢复时需要花费一段时间获知DataNode的状态；在添加数据存储节点时，GFS的伸缩性较HDFS要好HDFS具备安全模式：获知数据块副本状态，若副本不足，则拷贝副本至安全数目；GFS不具备安全模式HDFS具备

33、空间回收机制5、Google的云计算应用均依赖于四个基础组件1）分布式文件存储，GFS2）并行数据处理模型MapReduce3）分布式锁Chubby4）结构化数据表BigTableChubby的作用：为GFS提供锁服务，选择Master节点；记录Master的相关描述信息；通过独占锁记录ChunkServer的活跃情况、为BigTable提供锁服务，记录子表元信息，记录MapReduce的任务信息、为第三方提供锁服务与文件存储。GFS的作用：存储BigTable的子表文件、为第三方应用提供大尺寸文件存储功能。MapReduce的作用：对BigTable中的数据进行并行计算处理，使用BigTab

34、le或GFS存储计算结果。1虚拟化的概念？虚拟化是表示计算机资源的抽象方法，通过虚拟化可以用与访问抽象前资源一致的方法来访问抽象后的资源。这种资源的抽象方法并不受实现、地理位置或底层资源的物理配置限制。（wiki）6虚拟化与云计算的关系？虚拟化技术以及各种计算机科学概念，虚拟化的发展和商业实现打开了云计算的大门，而云计算本质上说应该就是虚拟化服务。从虚拟化和云计算的过程，我们实现了跨系统的资源调度，将大量的计算机资源组成资源池，用于动态地创建高度虚拟化的资源提供给用户，从而最终实现应用、数据、IT资源以服务的方式通过网络提供给客户。可以说云计算是虚拟化的最高境界，虚拟化是云计算的底层结构。分布

35、式计算机是指系统内部对用户是完全透明的;系统中的计算机即合作又自治；系统可以利用多种物理和逻辑资源，可以动态地给它们分配任务。计算机网络是指互连的计算机是分布在不同地理位置的多台独立的自治计算机。点到点通信子网的拓扑结构主要有以下几种：星型、环型、树型、网状型，请根据其特征填写相应结构。网状型：结点之间的连接是任意的，没有规律。环型：节点通过点到点通信线路连接成闭合环路。星型:节点通过点到点通信线路与中心结点相连；树型：结点按层次进行连接。分布式计算系统可以分为两个子组，它们是集群计算系统和网格计算系统10.DCE本身是由多个服务构成的，常用的有分布式文件系统、目录服务安全服务以及分布式时间服

36、务等12.WindowsNT的结构借用了层次模型和客户/服务器两种模型。17.操作系统通常可以分为以下几种类型：批处理系统、分时系统、实时系统、网络操作系统和分布式操作系统。在面向流的通信中，为连续提供支持数据流的模式有异步传输模式、同步传输模式和等时传输模式三种。在流同步机制，通常有在数据单元层次上进行显式同步和通过高级接口支持的同步两种。24.在名称解析的实现中，通常采用两种方法，一是迭代名称解析；二是递归名称解析。在以数据为中心的一致性模型中，顺序一致性是指任何执行结果都是相同的，所有进程对数据存储的读/写操作是按某种序列顺序执行的，并且每个进程的操作按照程序所制定的顺序出现在这个序列中

37、”。在因果一致性中，所有进程必须以相同的顺序看到具有潜在囚果关系的写操作。不同机器可以以不同的顺序看到并发的写操作。以客户为中心的一致性模型中，满足最终一致性的数据存储具有以下属性：没有更新操作时，所有副本逐渐成为相互完全相同的拷贝。以客户为中心的一致性模型中，一个写操作总是在同一进程执行的后续读操作之前完成，而不管这个后续的读操作发生在什么位置。在一致性协议中，基于主备份的协议比较盛行，它包括远程写协议和本地写协议两种。在一致性协议中，复制的写协议包括主动复制和基于多数表决的一致性协议两种。在容错性中，故障通常被分为暂时性故障、间歇性故障和持久性故障三大类型。在可靠的客户-服务器通信中，失败

38、时的RPC系统中发生客户不能定位服务器、请求消息丢失、服务器崩溃、应答消息丢失和客护端崩溃等5种形式。在原子多播里，消息排序通常有4种不同的排序方法，它们分别是：不排序的多播、FIFO顺序的多播、按囚果关系排序多播和全序多播。容错性的基本要求是从错误中恢复，本质上有两种形式的错误恢复，一是吐恢复；另一种是前向恢复。50.在容错性中，人们定义了一些不同类型的故障，主要的有崩溃性故障、遗漏性故障、定时性故障、响应性故障以及随意性故障等五大类。90.在容错性中，消息日志的基本思想是：如果消息的传输可以重放，那就能够到达一个全局致的状态而不需要从稳定存储中恢复该状态。分布式系统中的扩展技术通常有：隐藏

39、通信等待时间、复制技术；下面属于分布式混合体系结构的是：边界服务器系统、协作分布式系统；在迁移与本地资源的关系中，资源对机器的绑定有：未连接资源、附着连接的资源、紧固连接的资源在DEC中，IDL中的头文件包含：唯一标识符、类型定义、常量定义与函数原型IDL编译器的输出包括的文件是：文件头、客户存根、服务器存根在面向消息的持久通信中，消息队列系统中的基本接口有：Put、get在流同步中，同步机制要搞清楚问题：两个流同步的基本机制、在网络下机制的版本网络体系结构可以定义为：建立和使用通信硬件和软件的一套规则和规范在OSI参考模型中，数据链路层的数据服务单元是：帧3下面属于分布式计算系统的是：集群计

40、算、网格计算目前分布式信息系统按集成可分为事务处理系统、企业应用集成7.DNS属于(应用层)层协议。9.对于域名：，DNS服务器查找顺序是：先查找.com域，再查找test主机远程客户端登录终端服务器必须提供一定的信息，必要的信息：用户名、服务器IP地址。在多播通信中，应用层多播树的质量的度量尺度：链接树、相对延时补偿、树成本以多播流方式传递内容时只能采用(广播发布点)类型的发布点。DNS名称空间是分层组织的一棵有根树，标识符是有:字母和数字组成下列属于流同步的是：离散数据流与连续数据流之间同步、口型同步19.多线程服务器可行的设计方法:多线程文件服务器/单线称文件服务器/作为有限状态机20与

41、迭代名称解析比较，递归名称解析的优点是：缓存结果更为有效、能减少通信开销分布式系统的全局状态是指：每个进程的本地状态、当前正在传输中的消息面向消息的中间件模型一般提供：持久异步通信、电子邮件、工作流在分布式系统中，实现事务的方法是：为进程分配私有工作空间、做写前日志并发控制的总体思想是：正确调度相冲突的操作下面属于进程间同步算法的是：选举算法、互斥算法严格一致性中存在的问题是：依赖于绝对的全局时间下面属于一致性协议的是：基于主备份的协议、复制的写协议基于主备份的协议是指：负责协调X上的远程写操作、负责协调X上的本地写操作34.在可靠多播通信中，解决反馈拥塞的方法是：无等级的反馈控制、分等级的反

42、馈控制35.实现可靠原子多播的方法是：消息排序、虚拟同步三.简答题(每小题n分，共m分)2为什么传输层通信服务常常不适于构建分布式应用程序？答：因为它不适合用于支持多层客户-服务器交互过程所使用的同步请求-应答方式，在可靠传输中，造成许多开销都耗费在连接的管理上。3描述一下客户和服务器之间使用套接字的无连接通信是如何进行的？答：首先服务器和客户端都要创建一个套接字，并遵循UDP协议，服务器将其所在的IP地址以及一个端口号绑定到套接字，完成绑定后，服务器就能接收来自客户端的UDP数据包了。同样，客户端在创建套接字后，能够向服务器发送UDP包进行通信，通信过程中，服务器和客户端之间是不用建立连接的

43、。7.在深度为k的分层定位服务中，当移动实体改变它的位置时，最多需要更新多少条位置记录？答：移动实体改变位置会产生删除操作和插入操作，删除操作至少需要更新k条位置记录。同样，插入操作也需要更新k条位置记录。最后，删除与插入更新移动实体位置的记录共需要2k+1条。&要使用Lamport时间戳实现全序多播，是不是每个消息都必须要被严格地确认？答：不需要，任何类型的消息，只要它的时间戳大于所接收到的消息的时间戳，就可以被加入消息队列，使用Lamport时间戳实现全序多播。9.许多分布式算法需要使用协调进程。讨论一下，这样的算法实际上可总ft-VTlAE迭帛迂堆祗用的井民羊也-v區糾疋r.tTT一的僅

44、枸：客注许上：列唱总的卜孑乳肌上:肝爸理的modelthatsaideverysetofoperationsonaP2:R(x)aW(x)bPlP2P3P4W(x)lW(X)2R(x)2W(x)3R(x)2R(X)3RX)3R(X)21虚拟化的典型类型:基础设施虚拟化、系统虚拟化、软件虚拟化2虚拟化的目的：对象脫离原有环境、在计算机上被表示、通过计算机控制按需获取。一个开放的分布式系统就是根据一系列准则来提供服务，这些谁则描述了所提供服务的语法和语义。可扩展性至少可以通过3个方面度量：规模上扩展一用户和进程的数量、地域上可扩展一节点之间的最大距离、管理上可扩展一管理域的数量。分散式算法与集中式

45、相比不同的特性：没有任何计算机拥有关于系统状态的完整信息；计算机只根据本地信息做出决策；某台计算机的故障不会是算法崩溃；没有存在全局性时钟的假设。分布式系统的分类：分布式计算系统、分布式信息系统、DistributedPervasiveSystems。分布式事务处理的特性，原子性；一致性：事务处理不会违反系统的不变性；独立性：并发的事务处理不会相互干扰；持久性：事务处理一旦提交，所发生的改变是永久性的。根据组件和连接器的不同，分布式系统体系结构最重要的有4种，它们是：分层体系结构、基丁对象的体系结构(MVC-J2EE)、以数据为中心的体系结构、基丁事件的体系结构在客户-服务器的体系结构中，应用

46、分层通常分为3层，用户接口层、处理层和数据层&有两种类型的分布式操作系统，多处理器操作系统和多计算机操作系统系统体系结构：软件体系结构的具体实例。确定了软件组件、这些组件的交互以及它们的位置就是软件体系结构的一个实例。分布式软件体系结构主要分集中式、非集中式和各种混合形式三大类。其非集中式体系结构又分为结构化的点对点、非结构化的点对点、超级对等体三种集中式体系结构-客户/服务器体系结构：客户机怎么告诉请求消息丢失：超时。客户机怎么检测请求丢失和回复丢失的区别：最多一次服务，至少一次服务。幂等性：一个操作重复多次而没有害处就说它是幂等的。客户/服务器结构的应用程序通常划分为三层，它们是：用户接口

47、层、处理层和数据层在结构化点对点体系结构中覆盖网络是用一个确定性的过程来构成的，这个使用最多的进程是通过一个分布式哈希表来组织进程的。新型体系结构：垂直分布(不同功能的分布)、水平分布(相同功能的分布)、对等型(P2P)分覆盖网络：建立在另一个网络上的网络，属于应用层，很少考虑网络层物理层的问题。P2P网络是建立在Internet之上的一种覆盖网络。P2PChord是基于分布式Hash(DHT)的结构化P2P一个线程独立地执行它自己的程序代码。线程系统一般只维护用来让多个线程共享CPU所必需的最少量信息。有两种实现线程线程包的基本方法：一是可以构造一个完全在式下执行的线程；二是由内核来掌管线程

48、并进行调度。1&分布式系统中的多线程通常有：多线程用户和多线程服务器两大类型。而以分发器/工作者模型组织起来的多线程服务器是最为流行的一种。虚拟化可采用两种方法，一是构建一个运行时系统，提供一套抽象指令集来执行程序。二是提供虚拟机监视器。57.常用的进程调度算法有先来先服务、优先数法和轮转法60.进程通常的四个特征是动态性,并发性,独立性,异步性互斥锁：防止多个线程同时读写某一块内存区域；信号量：用来暴走多个线程不会相互冲突。操作系统的设计：(1)以多进程的形式，允许多个任务同时执行；(2)以多线程形式，允许单个任务分成不同的部分运行(3)提供协调机制，一方面防止进程之间和线程之间产生冲突，另

49、一方面运行进程之间和线程之间共享资源。在流与服务质量(QOS)描述中，服务质量特性指的是数据传输所要求的比特率、创建会话的最大延时、端到端的最大延时、最大延吋抖动以及最大往返延吋流同步有两种类型，一种是在离散数据流与连续数据流之间保持同步；另一种是连续数据流之间的同步。在流同步的机制中，需要研究的两个问题是：一个是两个流同步的基本机制；二是在网络环境下这些机制的分布式版本。在基于gossip的数据通信中，通常采用感染协议传播信息。一种流行的传播模型是arnrentropy向量时钟能捕获因果关系。仓曬向量时钟是让每个进程和维护一个向量VCI来完成。互斥集中式算法的优点是易于实现、很公平、保证了顺

50、序致性。而缺点是协作者是单个故障点，如果它崩溃了，整个系统可能瘫痪。分布式互斥算法的优点是不会发生死锁与饿死现象，也不存在单个故障点。其缺点是单个故障点被n个故障点所代替，所以故障率高；要求更多的网络流量。50.分布式系统中，传统的选举算法有两种，一是欺负选举算法；二是环选举算法。令牌环算法每次进/出需要的消息数是Lb；进入前的延迟是01；但存在令牌丢失和进程崩溃的问题。进程恢复编组的目的是把若干等同的进程抽象成一个具备容错能力的虚进程。因此，组内成员要具备彼此通信的能力。然而，由于一组等同进程分布在不同服务器上，我们必须假定组内任一个进程都可以把信件送达该组的所有服务器上，而无需知道究竟有多

51、少服务器，这些服务器位于何处，以及这些服务器处于何种状态等。集群计算系统一个突出的特征是它的同构性；它提供了最大限度的分布式透明性。可用于单个程序在多台计算机上并行地运行。网格计算系统具有高度的异构性：其硬件、操作系统、网络、管理域和安全策略等都不尽相同。网格计算系统一个关键问题是如何把来自不同计算机组织的拠集中起来，使一组人或机构进行协调工作。超级对等体通常是维护一个素引或充当一个代理程序的结点。分布式的自主系统指的是自我管理、自我恢复、自我配置和自我优化等各种自适应性。在服务器的组织结构中，迭代服务器是自己处理请求,将响应返回给客户；而并发服务器将请求传递给某个独立线程或其他进程来处理。服

52、务器集群在逻辑上由三层组成，第一层是逻辑交换机；第二层是应用/计算服务；第三层曰-At-IlU是文件/，数据丿库系统进程对资源的绑定有三种类型：一是按标识符绑定；二是按值绑定；三是按类型绑定。而三种类型的资源对机器的绑定是耒连接资源、附着连接资源和紧固连接资源。中间件是一种应用程序，它在逻辑上位于应般中，但在其中包含有多种通用协议，这些协议代表各自所在的层，独立于其他更加特别的应用。在RPC操作中，客户存根的功能是将得到的参数打包成消息，然后将消息发送给服务器存根。所有DCE的底层编程模型都是客户-服务器模型。而DCE本身的一部分是由分布式文件服务、目录服务、安全服务以及分布式吋间服务等构成I

53、DL编译器的输出包括三个文件，它们是头文件、客户存根和服务器存根2&在面向消息的通信中，通常分为面向消息的瞬时通信和持久通信两种机制。在面向消息的瞬时通信中，通常采用套接字接口和消息传递接口。在面向持久的通信中，消息队列系统为持久异步通信提供多种支持。它提供消息的中介存储能力。在消息队列系统中，队列由队列管理器来管理，它与发送或接收消息的应用程序直接交互。在消息队列系统中，转换是由队列网络中特定结点完成的，这些结点称为消息转换器应用层多播的基本思想是结点组织成一个覆盖网络，然后用它来传播信息给其成员。一个重要的因素是网络路由器不在组成员中。3&在覆盖网络构建时，主要有两种方法，一种是结点本身直

54、接组织成树;另一种是结点组织成一个网状网络。39.应用层多播树的质量通常以三种不同的尺度来度量，一是链接树；二是相对延吋补偿;三是l-rl.n.I树成本分布式系统中，有三种不同的命名系统，它分别是无层次命名；结构化命名和基于属性的命名。在无层次命名中，通常有广播和多播、转发指针、基丁宿主位置、分布式散列表、分层结构等方法实现实体定位。基于属性的命名系统实现的方式有两种。一种是分层实现，使得目录项集合形成了分层的目录信息树。而另一种是非集中式实现，它是采用映射到分布式散列表的方式。45.一次将所有的消息以相同的顺序传送给每个接收的多播操作称为全序多播Lamport时间戳可以用于以完全分布式的方式

55、实现。52.高速缓存相关性协议的设计与实现是基于两种策略的：一是相关性检测策略；二是相关性实施策略。在开发的持久一致性协议中，有三种限定的偏差：它们是限定复制的数字偏差、限定复制的新旧程度偏差和限定顺序偏差。65.在名称解析的实现中，通常采用两种方法，一是迭代名称解析；二是递归名称解析。1.下面特征分别属于计算机网络和分布式计算机系统，请加以区别：以在什么程度上被看作为分布式的？答：在集中式算法中，一般会选择一个固定的进程作为协调者，其它的进程可以分布在不同的机器上运行。分布式算法中也同样可以引入协调进程，但是，这个进程并不是固定的，它是从作为算法一部分的进程中选择的。因此，使用协调进程并不会

56、影响算法的分布性。请解释DNS如何进行复制，以及它实际运行很好的原因。答：DNS进行复制的基本思想是：域名服务器可以缓存以前查找过的结果。由于DNS的名称到地址的映射很少更改，因此，这些结果可以缓存很长一段时间。原子多播的可扩展性重要到哪种程度上？答：它取决于一组包含多个进程的状态。如果进程为故障容错进行了复制，拥有少量的副本可能就足够了，在这种情况下，可扩展性几乎不成问题。如果是由不同进程构成的组，可扩展性就可能成了一个问题。当为了性能而复制时，原子多播自身可能超出负荷的能力。在两阶段提交协议中，为什么即使在参与者们选择一个新的协调者的情况下也不会完全消除阻塞？答：因为选举结束后，新的协调者

57、也同样可能会崩溃。在这种情况下，其余的参与者也不能做出最后决定，因为这需要由新当选的协调者发起选举。列举出为密钥管理使用集中式服务的一些优点和缺点。答：一个显著的优点是简单。比如：若有N个客户在一个集中式的服务器上共享了1个密钥，我们就只需要维护N个密钥；如果是成对共享密钥，那我们就需要维护N(N-1)/2个。而且使用集中式服务器存储和维护都在一个站点上，使存储和维护都比较方便。潜在的缺点：首先是服务器有可能成为性能和可用性的瓶颈。其次，如果服务器机密被泄露，就必须建立新的密钥。一个网络中，DNS服务器应该部署在什么地方最合适？答：要用域名访问Internet上的服务器必须先访问DNS服务器，

58、经过DNS对域名的解析才能连接到相应的主机。所以，在一个网络中，DNS服务器应该部署在客户端可以集中访问的网络位置上。进程间同步和互斥的含义是什么？答：进程间同步是并发进程之间存在的相互制约和相互依赖的关系。进程间互斥是若干进程共享一资源时，任何时刻只允许一个进程使用。5.分布式令牌环算法存在令牌丢失的问题，如果令牌丢失，会导致算法失败，请将该算法改进一下，使该算法既能检测到令牌丢失，也能进行补救。令牌环的维护令牌环的故障处理功能主要体现在对令牌和数据帧的维护上。令牌本身就是比特串，绕环传递过程中也可能受干扰而出错，以至造成环路上无令牌循环的差错；另外，当某站点发送数据帧后，由于故障而无法将所

59、发的数据帧从网上撤消时，又会造成网上数据帧持续循环的差错。令牌丢失和数据帧无法撤消，是环网上最严重的两种差错，可以通过在环路上指定一个站点作为主动令牌管理站，以此来解决这些问题。主动令牌管理站通过一种超时机制来检测令牌丢失的情况，该超时值比最长的帧为完全遍历环路所需的时间还要长一些。如果在该时段内没有检测到令牌，便认为令牌已经丢失，管理站将清除环路上的数据碎片，并发出一个令牌。为了检测到一个持续循环的数据帧，管理站在经过的任何一个数据帧上置其监控位为1，如果管理站检测到一个经过的数据帧的监控拉的已经置为1,便知道有某个站未能清除自己发出:的数据帧，肆理站将清除环路的残余数据，并发出一个令牌。一

60、个最完备的分布式体系由以下模块组成：分布式任务处理、分布式节点注册和查询、分布式数据库、分布式cache、分布式文件、网络通信、监控管理、分布式编程语言、分布式算Q:AttheendofSec.6.3.2,wediscussedaformalsequentiallyconsistentdatastorecanbemodeledbyastring,H,fromwhichalltheindividualprocesssequencescanbederived.ForprocessesP1andP2inFigurebellow,giveallthepossiblevaluesofH.P1:W(x)日