1. 请解释分布式透明性的含义，并且给出各种类型的透明性示例。
2. 为什么有时候最大程度地实现透明性并不总是好的？
3. 什么是三层客户-服务器体系结构？
4. 简述结构化Peer-to-Peer体系结构的特点，并画出Chord的体系结构图。
5. 在结构化的覆盖网络中，消息时根据覆盖的拓扑结构来路由的。这种方法的
主要缺点是什么？
6. 请从技术的角度来解释为什么BitTorrent中的tit-for-tat策略比因特网中的文
件共享要好得多？
第6章波动算法和遍历算法在对各种应用程序或分布式系统设计分布式算法时，一些一般性的问题经常可以看成是该分布式算法的子任务。
这些子任务包括消息的广播(比如说启动和终止消息传递)，在进程之间获取一个全局的同步，在每个进程中触发执行某个事件或计算一个每个进程拥有部分输入的函数等。
这些任务的执行都要通过在某些指定的、依赖于拓扑结构的模式上传递消息来保证所有进程参与这个活动。
这种消息传送的模式，我们今后叫做波动算法（wave algorithms），顾名思义，这一计算必须波及到所有结点或进程。
在这一章，我们将形式化地给出波动算法的定义，并证明一些在波动算法方面的一般性结论(6.1.2)。
从6.1.3到6.1.5将严格阐述一个相同的算法被用于上面列出的所有的基本的任务。
6.2节提出一些广泛使用的波动算法。
6.3节考虑遍历算法，它是在波动算法的基础上增加这样的属性: 算法对应的一个计算的所有事件都在因果序关系上是全序的。
6.4节给出了几个在分布式深度优先搜索上的算法。
波动算法的意义波动算法不仅是一类重要的分布式算法，而且也提供了分布式算法设计的一种途径和方式方法。
本章将表明，许多分布式算法实际上是一种波动算法，所有的波动算法都具有共同的特征，满足波动算法的属性条件。
一旦一个问题弄清楚了求解该问题的算法具有波动性的特点，就可以考虑用波动算法来求解这个问题。
此时，算法的设计不必另起炉灶，从头开始一步一步地分析、设计这个分布式算法，而是可以从一个已知的波动算法出发，通过改造这个算法来达到设计算法，求解波动问题的目标，而这样一个改造波动算法从而获得一个新的波动算法的过程，是相对简单和容易的。
换言之，波动算法的研究，不仅划分了一类具有共同特征属性的算法，而且提供了这类算法设计的一种新的途径或方式方法。
6.1 波动算法的定义和使用除非明确指出，否则我们在本章中都将假设网络拓扑是固定的(网络拓扑结构不发生改变)、无向的(每个通道可以在两个方向上携带消息)，并且是连通的(每两个进程之间有一条路径)。
1、列出下列类型操作系统的基本特点。
(10分)a．批处理 b．交互式 c．分时 d．实时e．网络 f．并行式 g．分布式 h．集群式2、MS-DOS没有提供并发执行的方式。
论述并发执行给操作系统带来的哪些主要复杂化因素。
论述期短、中期和长期调度之间的区别。
(15分)短期调度：从就绪可执行的进程中选择进程。
中期调度：特别用于分时系统中作为中等程度调度程序。
能将进程移出内存（并移出对CPU的激烈竞争），因此降低多道程序设计的程度。
长期调度：从缓冲池中选择进程，并将它们装入内存以执行。
3、考虑使用邮箱的进程间通信方案。
(10分)·假设进程P想等待两条消息，一条来自邮箱A，一条来自邮箱B，它应该以怎样的顺序来执行send和 receive？·如果进程P想等待一条来自邮箱A或邮箱B（或A和B）的消息，它应以怎样的顺序来执行send和 receive？·一个receive操作使得进程处于等待状态直到邮箱非空。
设计一个方案，允许进程等待直到邮箱为空，或解释一下为什么这样的方案不存在。
假设进程P想等待两条消息，一条来自邮箱A，一条来自邮箱B，它应该以怎样的顺序来执行send和 receive？Either receive(A, message A); receive(B, messageB); or receive(B, messageB); receive(A, messageA); will be okay.•如果进程P想等待一条来自邮箱A或邮箱B（或A和B）的消息，它应以怎样的顺序来执行send和 receive？Construct a mailbox set C, including mailbox A and B, then receive(C, message);•一个receive操作使得进程处于等待状态直到邮箱非空。
设计一个方案，允许进程等待直到邮箱为空，或解释一下为什么这样的方案不存在。
关于分布式系统复习题与参考答案一、填空题(每题n分,答错个扣分,全错全扣，共计m分)1．下面特征分别属于计算机网络和分布式计算机系统，请加以区别：分布式计算机是指系统内部对用户是完全透明的；系统中的计算机即合作又自治；系统可以利用多种物理和逻辑资源，可以动态地给它们分配任务。
计算机网络是指互连的计算机是分布在不同地理位置的多台独立的“自治计算机”。
2．点到点通信子网的拓扑结构主要有以下几种：星型、环型、树型、网状型，请根据其特征填写相应结构。
网状型：结点之间的连接是任意的，没有规律。
环型：节点通过点到点通信线路连接成闭合环路。
星型：节点通过点到点通信线路与中心结点相连；树型：结点按层次进行连接。
3．分布式计算系统可以分为两个子组，它们是集群计算系统和网格计算系统。
4．分布式事务处理具有4个特性，原子性：对外部来说，事务处理是不可见的；一致性：事务处理不会违反系统的不变性；独立性：并发的事务处理不会相互干扰；持久性：事务处理一旦提交，所发生的改变是永久性的。
5．网络协议有三要素组成，时序是对事件实现顺序的详细说明；语义是指需要发出何种控制信息，以及要完成的动作与作出的响应；语法是指用户数据与控制信息的结构与格式6．根据组件和连接器的不同，分布式系统体系结构最重要的有4种，它们是：分层体系结构、基于对象的体系结构、以数据为中心的体系结构、基于事件的体系结构7．在客户-服务器的体系结构中，应用分层通常分为3层，用户接口层、处理层和数据层。
8．有两种类型的分布式操作系统，多处理器操作系统和多计算机操作系统。
9．软件自适应的基本技术有3种，一是要点分离、二是计算映像、三是基于组件的设计。
10．DCE本身是由多个服务构成的，常用的有分布式文件系统、目录服务、安全服务以及分布式时间服务等。
11．TCP/IP体系结构的传输层上定义的两个传输协议为传输控制协议(TCP)和用户数据报协议(UDP)。
12．Windows NT的结构借用了层次模型和客户/服务器两种模型。
