网络与分布式计算复习提纲.docx
《网络与分布式计算复习提纲.docx》由会员分享，可在线阅读，更多相关《网络与分布式计算复习提纲.docx（29页珍藏版）》请在冰点文库上搜索。
网络与分布式计算复习提纲
1.2什么是分布式计算系统？
它的实质是什么？
分布式计算系统是由多个相互连接的计算机组成的一个整体，这些计算机在一组系统软件（分布式操作系统或中间件）环境下，合作执行一个共同的或不同的任务，最少依赖于集中的控制过程、数据和硬件。
实质：
分布计算系统=分布式硬件+分布式控制+分布式数据。
1.10多处理机与多计算机的区别是什么？
同构多计算机和异构多计算机各有什么特点？
区别：
多计算机是将多个计算机联合起来处理问题,
多处理机是在一个系统内集成多个处理器.
广义上说，使用多台计算机协同工作来完成所要求的任务的计算机系统都是多处理机系统。
即多计算机系统。
狭义上说：
多处理机系统的作用是利用系统内的多个CPU来并行执行用户的几个程序，以提高系统的吞吐量或用来进行冗余操作以提高系统的可靠性。
同构计算机的特点：
1.每个节点是一台计算机，包含CPU和存储器。
2.节点间的通信量较少。
3.同构计算机系统的互连有两种结构：
基于总线的多计算机系统和基于交换的多计算机系统。
异构计算机的特点：
1.节点差异很大，节点可能是多处理机系统、集群或并行高性能计算机。
2.节点间通过互联网络如Internet连接起来的。
3.有两种实现方法：
采用分布式操作系统和中间件软件层。
1.16什么是中间件，它的功能是什么？
它在分布式系统中的地位是什么？
中间件是一种独立的系统软件或服务程序，分布式应用软件借助这种软件在不同的技术之间共享资源。
中间件位于客户机/服务器的操作系统之上，管理计算机资源和网络通讯，是连接两个独立应用程序或独立系统的软件
功能：
命名服务作业调度高级通信服务资源管理数据持久化分布式事务
分布式文档系统安全服务
地位：
中间件的一个重要目标是对应用程序隐藏底层平台的异构型，因此中间件系统都提供一组完整度不同的服务集。
这些服务是通过中间件系统提供的接口来调用的。
一般禁止跳过中间件层直接调用底层操作系统的服务。
1.18分布式系统有哪些计算模式？
（必考）
1.面向对象模式
2.面向服务模式
3.公用计算模式
4.志愿参与模式
（详见书p21-p22页）
面向对象模式OOM
面向对象模式OOM（ObjectOrientedModel）是基于客户/服务器模型（如CORBA，DCOM）
面向服务模式SOM
WebService是这种面向服务模式的一个实例,SOA是一个较完整的软件结构体系。
公用计算模式UBM
支持e-科学的计算（如网格Grid等）。
志愿参与模式VJM
志愿参与模式VJM（VoluntaryJoinModel）是充分利用网上空闲的计算能力，支持计算量巨大的科学计算
2.5有哪些名字服务形式？
名字服务器的组成与功能是什么？
名字服务形式：
（1）名字服务：
名字服务是根据实体的名字查找它的属性（地址）。
（2）目录服务：
目录服务既可以根据实体的名字查找实体的属性，当不知道实体名时也可以根据实体的一个或多个属性及其值查找并得到一个匹配这些属性的实体列表。
（3）合约服务：
是一种增强的目录服务，通过技术规范来定位一个命名实体。
名字服务器组成：
（1）名字服务器操作：
管理、查询操作和行政管理。
增加、删除和修改上下文的目录项。
访问优先权。
（2）名字解析：
根据名字解析请求，得到被解析对象地址。
（3）缓存：
缓存名字查询和解析的结果。
（4）多副本管理：
副本修改和副本一致性维护。
（5）通信：
客户端的名字代理通信和名字服务器之间
（6）数据库：
存放名字解析上下文或其子域。
名字服务器功能：
管理名字命名上下文、实现名字查询与解析和其它名字服务器通信协调。
2.7什么是迭代名字解析，什么是递归名字解析，它们各有什么优缺点？
迭代名字解析：
建议考试画图解释：
递归名字解析：
也画图解释
各自优缺点：
递归名字解析缺点：
要求每台名字服务器具有较高的性能。
递归名字解析优点：
1.递归名字解析过程中，各名字服务器解析的缓存结果使用更为高效。
2.如果主机与服务器距离很远，那么采用递归名字解析将更为高效。
迭代的优缺点与上面相反。
2.14什么是目录服务？
目录项和属性及属性值的关系是什么？
目录服务：
目录服务既可以根据实体的名字查找实体的属性，当不知道实体名时也可以根据实体的一个或多个属性及其值查找并得到一个匹配这些属性的实体列表。
关系：
目录项是一个命名对象的信息集合。
每个命名对象包括若干个属性，每个属性有一个属性类型和相应的一个或多个属性值。
2.17X.500目录服务中定义了哪些目录服务协议？
查询链与转交的含义是什么？
X.500目录服务有4个协议：
目录访问协议DAP，DUA用来与DSA通信。
目录系统协议DSP，是两个DSA之间的操作协议，在DSA之间传递查询请求和响应。
目录信息镜像协议DISP，是DSA用来将信息从镜像提供者传送给镜像使用者。
目录操作绑定管理协议DOP，DSA用来层次操作绑定管理和镜像管理。
目录服务对用户请求的响应
成功，返回所需信息
失败，返回失败信息
转交，返回一个更适合的DSA
2.18轻量数据访问协议LDAP和目录访问协议DAP的关系和区别是什么？
1.LDAP的最初目标是向用户提供目录服务时避免DAP的大量开销。
2.LDAP的操作集对DAP做了简化，删除了read和list操作，用search代替。
3.DAP是目录用户代理（DUA）与目录系统代理（DSA）之间的请求/响应协议。
LDAP是用户用来访问目录服务的一个协议。
4.建议再回答下LDAP的模型：
3.7什么是远程执行逻辑机模型？
对逻辑机模型的要求是什么？
概念：
客户节点上的代理进程负责远程服务节点上远程进程执行的初始化；远程服务节点执行客户机赋予的进程。
这种模型成为逻辑机模型。
建议画图。
如图所示，它跨越用户节点和两个远程服务节点，在一个逻辑机边界内保持稳健系统，进程的父子关系和进程组的进程视图的一致。
要求：
（1）远程进程必须能访问驻留在源计算机上的文件系统。
（2）远程进程能接收逻辑机内任何进程发来的信号，也能将信号提供给逻辑机内任何进程。
（3）进程组保持在逻辑机内。
（4）基于树型的进程父子关系在逻辑机内必须得以保持。
3.13何为异步进程迁移算法？
何为同步进程迁移算法？
它们的优缺点是什么？
异步进程迁移算法：
这类算法允许非迁移进程在迁移过程中继续运算，只有迁移进程被中断进行相关的操作。
优点：
可以得到较好的执行效率。
缺点：
和原有环境的兼容性不好，不能方便的移植。
同步迁移算法：
这类算法在迁移过程中所有进程（包括非迁移的协同进程）都被挂起，进程之间需要同步来清空通信信道中的中途消息，所有进程均要阻塞等待迁移事件完成后，才能从中断处继续运行。
优点：
算法简单，具有较好的可移植性和易于实现。
缺点：
需要中央控制管理进程参与，所有进程都被迫中断，等待迁移过程的结束。
3.15比较进程远程执行与进程迁移两种机制。
进程远程执行，就是在集群中或者网络中寻找一个或多个合适节点来执行用户程序。
进程远程执行的要求：
（1）寻找管理机制。
（2）进程远程执行是透明的，应与位置无关。
（3）主人优先原则
进程迁移是将一个正在运行的进程挂起，它的状态从源处理机节点转移到目标处理机节点，并在目标处理机上恢复该进程运行。
优点：
进程迁移具有灵活且应用广泛的优点，支持动态负载平衡、系统容错、高效使用本地资源等诸多系统功能。
缺点：
进程迁移的缺点是运行开销相对较大。
进程的迁移可以支持：
（1）动态系统管理与维护
（2）动态负载平衡（loadbalancing），系统中重负载处理机转移一部分负载到轻负载的处理机上运行，使得整个集群系统中的所有处理机的负载趋向均衡，从而提高系统的整体运行效率。
（3）系统容错
（4）主人优先使用原则
4.1在水平时间轴上表示阻塞发送/接收和非阻塞发送/接收进程与操作系统内核之间操作的时间关系。
没有具体答案，先方便理解一下阻塞和非阻塞：
阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）时的状态.
阻塞调用是指调用结果返回之前，当前线程会被挂起。
调用线程只有在得到结果之后才会返回。
非阻塞调用指在不能立刻得到结果之前，该调用不会阻塞当前线程。
例子：
你打电话问书店老板有没有《分布式系统》这本书，你如果是阻塞式调用，你会一直把自己“挂起”，直到得到这本书有没有的结果，如果是非阻塞式调用，你不管老板有没有告诉你，你自己先一边去玩了，当然你也要偶尔过几分钟check一下老板有没有返回结果。
这个图不知道对不对：
4.2试叙述如何实现阻塞发送/接收和非阻塞发送/接收，对操作系统有什么要求？
当进程到达发送原语时执行一次阻塞发送，无需等待对应的接收。
在消息从S安全写入发送缓冲区前，发送进程不能返回。
当进程到达接收原语时执行一次阻塞接收，无需等待对应的发送。
然而，消息从缓冲区接收到R之前，接收进程不会返回。
系统要为阻塞模式消息传送提供临时的缓冲区。
当进程到达发送原语时执行一次非阻塞发送，无需等待对应的接收。
只要通知操作系统有一个消息要发送，发送进程就可以返回。
当进程到达接收原语时执行一次非阻塞接收，无须等待对应的发送。
只要通知操作系统有一个消息要接收，接收进程就可以返回了。
系统要为非阻塞消息传送提供临时的缓冲区。
4.4对以下每个应用程序，你认为“至多一次”和“至少一次”语义哪个最好？
（1）在文件服务器上读写文件：
至少一次。
（2）银行服务：
至多一次
（3）编译一个程序：
至少一次
通过发送原语send和接收原语receive实现要求操作系统能实现4种不同的可靠性语义。
至少一次：
保证正确完成消息传送至少一次
至多一次：
保证正确完成消息传送至多一次。
在没有节点崩溃和网络断开情况下，它只正确地执行一次消息传送。
事务语义：
它保证消息的原子性。
不管节点崩溃或网络端口与否，它或者完成一次消息传送，或者什么也不做。
精确一次：
无论在什么情况下，保证正确完成一次消息传送，不管是否有节点崩溃或网络断开，它接近某种程度的容错机制。
4.9什么是因果定律？
它和FIFO全定序相比，哪个更严格？
因果定律：
不管含有因果关系的消息是由同一个发送进程多播，还是不同发送进程多播，所有接收进程要保证先接收“因”消息，后接收“果”消息。
FIFO：
对同一个发送进程发出的多播消息，要求所有接收进程按发送的顺序接收，而对不同发送进程的多播消息可按不同顺序接收。
相比之下，因果排序更严格。
4.12RPC被认为是分布式最初的中间件，它能实现分布式系统的透明性吗？
p92
在执行RPC过程中，客户可以简单的忽略不关心的内容，客户只是像执行本地调用一样调用远程过程，并不直接执行send和receive原语，也不关心消息的传递，所有这些都隐藏在桩中，从而实现RPC的透明性。
在本地过程调用中，read例程是由连接器从库中提取出来，连接到应用程序，当read是针对远程过程时，从库中获取read例程的另一个版本，客户桩。
在服务器端服务器也为远程客户提供一个read例程，服务器桩。
5.2假设两台机器的时钟每秒滴答1000次和990次，如果UTC每秒更新一次。
两台机器时钟的最大偏移量是多少？
答：
1000-990=10次/秒，每秒的最大偏移量为0.010ms。
5.6在集中式互斥算法中，若考虑进程的优先权，算法应该如何设计？
（找不到答案）
基于事件优先权的完全可靠算法
请求队列P、Q
Q队列放置其他节点送来的请求（接收令牌）
P队列放置其他节点来不及处理的随令牌转来的请求
算法过程
1.进程i发送Request（i，P（i）），并将（i，P（i））存入接收接收进程的Q队列，按优先关系排序，等待接受令牌。
2.握有令牌的j退出临界区后，检查P,Q队列，根据P、Q队列情况判断（标注最高优先权进程，合并队列）
如果P,Q都为空，进程j继续工作，等待请求。
如果P空，Q不空，在Q队列标注最高优先权进程，合并队列P,Q为P队列.
如果P不空，Q空，在P队列标注最高优先权进程，合并队列P,Q为P队列.
如果P,Q都不空，进程j在Q队列标注最高优先权进程，合并P,Q为P队列.
3.进程j将令牌和新的P队列发送到所标注的最高优先权进程
5.7Richart_Agrawala算法如何改进了Lamport算法，它的优点是什么？
（必考）
Lamport算法的开销是3（N-1）个消息，Richart算法只要2（N-1）个消息，N是竞争资源的进程数。
Lamport算法：
1.Pi进程发送资源请求消息Request（Ti：
Pi）；
2.Pj进程收到Request（Ti：
Pi），按T顺序置于其消息队列，如果没有资源请求或请求时间晚于收到消息的时间戳，回应Reply（Tj：
Pj）；（否则不返回任何消息）
3.进程Pi被批准使用临界资源条件：
有请求，且Ti最小（消息全定序）；Pi接收了所有晚于Ti的消息（包括应答）
4.Pi释放资源，退出临界区，发送Release（Tj+1：
Pi）；
5.Pj收到Release后，删除（Ti：
Pi）；检查是否还有进程等待进入临界区。
Richart算法：
1.Pi进程发送资源请求消息Request（Ti：
Pi）；
2.Pj进程收到Request（Ti：
Pi），按T顺序置于其消息队列，并做：
如果没有资源请求或请求时间晚于收到消息的时间戳，回应Reply（Tj：
Pj）；否则推迟返回应答消息。
3.进程从临界区退出，向需要请求资源的进程补发一个应答消息。
4.请求进程从竞争进程得到应答小Reply（Tj：
Pj），便可进入临界区
改进地方：
第二步中，接收到资源请求消息之后，无论赞成或者拒绝都会返回一个应答消息，这样用超时机制可以确定进程是否崩溃。
优点：
1.它具有对称性
2.具有完全的分布式控制
3.对通信链路相对速度的不敏感性
4.能保证互斥，不会发生死锁也不会发生饥饿，能处理进程的加入，退出和崩溃。
5.开销减少。
5.8比较集中式算法、Ricart_Agrawala算法和令牌算法的开销和问题
开销：
集中式算法开销最大，Richar算法需要2（N-1）个消息，令牌算法最多需要N-1个消息。
集中式算法的问题：
容易出现单点故障。
可能成为系统性能的瓶颈。
Ricart算法的问题：
由于不应答被认为是资源被占用，所以如果有某个节点故障，会导致该算法的异常终止。
同时各进程对资源的使用情况缺乏了解。
令牌算法的问题：
检测令牌丢失困难
5.11共享K个相同资源的互斥算法和Ricart_Agrawala算法的共同点和区别是什么？
相同点：
基于相同的概念，每个竞争进程都维持一个推迟应答数组RD[]，数组元素是表示相应进程是否推迟发出应答消息。
区别：
1.应答消息到达的环境。
在Ricart算法中，正在等待进入临界区的进程要得到N-1个应答消息。
在共享K个相同资源的互斥算法中，N-K个应答消息是在进程等待时到达，K-1个消息是进程已在临界区或等待进入临界区或离开临界区后到达。
2.在Ricart算法中，其他竞争进程推迟应答数组的每一项RD[i]是布尔型，因为应答只能是一个，或是推迟，或是不推迟。
在共享K个相同资源的互斥算法中，可能有多个应答消息被推迟，这样RD[i]应声明为整数型。
5.13在基于事件优先权算法中，如何保证低优先权的进程有机会进入临界区，而不挨饿。
（找不到答案）
8.2图8.1（b）为什么违背严格一致性？
因为B读到的不是a，而是数据项x的初值null，客户A的写操作没有立即传播到B，未能及时完成对副本的修改。
8.3图8.2（b）为什么违背顺序一致性？
因为进程C看到数据项x是先写a后写b，而进程D看到数据项x是先写b后写a。
8.4图8.3（c）为什么符合因果一致性定律？
因为W（x）a和W（x）b不存在因果关系，所以W（x）a和W（x）b是并发写，客户C,D看到两个写操作不相同定序也没关系，因此也符合因果一致性要求。
8.5图8.4（b）为什么遵循因果一致性，但对FIFO一致性是无效的？
图中，客户C对数据项x读a,b,c；而客户D对x读c,a,b。
所以不符合FIFO一致性。
虽然遵守因果一致性。
书p200-p205的几种一致性必须弄懂，是必考的。
数据为中心的一致性模型（由强到弱）
严格一致性：
对数据项的读操作返回的值应是该数据项最近写入的值。
顺序一致性：
所有客户以同样的次序看到所有写操作的全局定序。
因果一致性：
具有因果关系的写操作在所有副本上看到按相同的次序被执行，操作不是因果的，可以说是并发的。
FIFO一致性：
一个客户的写操作定序在所有副本上是相同的。
弱一致性：
采用按一个操作组，而不是单个操作进行一致性定序。
释放一致性：
获取操作（Acquire），释放操作（Release）
入口一致性：
数据项一次操作与同步变量相关联
客户为中心的一致性模型
单调读：
如果一个进程读数据项x的值，该进程的任何后续对x的读操作总是返回前一次读同样的值或更加新的值
单调写：
一个进程对数据项x执行写操作，必须在该进程对x执行任何后续写操作之前完成
写后读：
一个进程对数据项x执行一次写操作的结果，总是会被该进行对数据项x的后续读操作所看见
读后写：
一个进程对数据项x的写操作是跟在同一进程对x读操作之后，保证相同的或更加新的x的值能被看见
8.7比较“传播更新通知”、“传播更新数据”和“传播更新操作”和它们的应用场合
传播更新通知：
只传播一个简短的数据无效通知，不包含其他信息。
传播更新数据：
在副本间传送被修改过的数据。
传播更新操作：
不传播被修改过的数据，而是告诉各副本应该执行的操作。
主动复制，要求每个副本有一个进程来执行更新操作，主动的保持各副本关联数据的一致性。
应用场合：
传播更新通知：
写操作对读操作的比率很高时，传播效果好。
传播更新数据：
读操作对写操作的比率很高时，传播效果好。
传播更新操作：
更新操作所关联的参数较少时，所占带宽较小。
8.9一个文件被复制在10个服务器上，列出表决算法的“读集团”和“写集团”。
此算法要求Nr+Nw>N
Nw>N/2
此题的N=10;
那么写集团可以为678910
当Nw=6,
Nr的值可以是5678910
当Nw=7,
Nr的值可以是45678910
当Nw=8,
Nr的值可以是345678910
当Nw=9,
Nr的值可以是2345678910
当Nw=10,
Nr的值可以是12345678910
9.2分布式文件系统的共享语义指的是什么，有哪几种共享语义？
文件共享语义是为了理解文件的行为。
不同共享语义将导致不同编程实现方法。
种类：
（1）UNIX语义（顺序一致性语义）
（2）会话语义
（3）不修改共享文件语义
（4）事务语义
9.4NFS如何访问远程文件，它的虚拟文件系统的作用是什么？
NFS采用远程过程调用（RPC）通信机制，它为客户端提供访问多种文件系统的调用操作接口。
而服务器提供一组过程实现这些操作。
远程共享文件或它的子目录是通过虚inode（即vnode）形式挂接在本地文件目录中。
NFS客户端与远程文件系统服务器之间通信采用安全的远程过程调用（RPC）方式，实现身份验证和消息验证，采用了RPC重传技术，对文件共享进行访问控制。
虚拟文件系统（VFS）作用：
客户使用本地操作系统的系统调用访问文件系统。
在分布式系统中，一个虚拟文件系统接口代替了常规UNIX文件系统接口，VFS的思路是隐藏不同文件系统之间的差异，它已成为不同分布式文件系统接口事实上的标准。
VFS接口上的操作或传送到本地文件系统，或传送到一个成为NNFS客户的组件上。
NFS客户组件负责处理对存储在远程服务器上文件的访问。
1.允许操作系统使用不同的文件系统接口。
2.是物理文件系统与服务之间的一个接口层，对每个文件系统的所有细节进行抽象，使得不同的文件系统在系统中运行的其他进程看来，都是相同的。
9.9NFS的RPC实现了何种可靠性语义？
（不确定的答案）
常规调用复合调用
以及RPC重传（重传过早，重传过晚，响应丢失）
可靠性语义有：
至少一次：
保证正确完成消息传送至少一次
至多一次：
保证正确完成消息传送至多一次。
在没有节点崩溃和网络断开情况下，它只正确地执行一次消息传送。
事务语义：
它保证消息的原子性。
不管节点崩溃或网络端口与否，它或者完成一次消息传送，或者什么也不做。
精确一次：
无论在什么情况下，保证正确完成一次消息传送，不管是否有节点崩溃或网络断开，它接近某种程度的容错机制。
我们可以看出：
符合“至少一次”的可靠性语义。
11.5CORBA的主要特点是什么？
功能是什么？
简述CORBA系统中ORB的作用。
特点：
（1）CORBA定义了一种面向对象的软件构件构造方法，使不同的应用可以共享由此构造出来的软件构件；
（2）每个对象都将其内部操作细节封装起来，同时又向外界提供了精确定义的接口，从而降低了应用系统的复杂性，也降低了软件开发费用；
（3）CORBA的平台无关性实现了对象的跨平台引用，开发人员可以在更大的范围内选择最实用的对象加入到自己的应用系统之中；
（4）CORBA的语言无关性使开发人员可以在更大的范围内相互利用别人的编程技能和成果，是实现软件复用的实用化工具
CORBA的核心是对象请求代理（ORB，ObjectRequestBroker），它提供了网络环境无关性、操作系统无关性和开发语言无关性的公共平台。
在面向对象的应用环境中，CORBA对象的请求者不必知道它所请求的对象是在哪里，是如何实现的，而是由ORB来负责跨平台的运作管理，无须应用系统的开发者干预。
具有的跨平台、分布式、面向对象等优点。
CORBA是一个中间件规范并不是一个实体软件。
软件开发者通过使用第三方的ORB工具或IDL语言来定义CORBA对象，实现ORB功能。
功能：
（1）存取来自现行桌面应用程序的分布信息和资源；
（2）使现有业务数据和系统成为可供利用的网络资源；
（3）为某一特定业务用的定制的功能和能力来增强现行桌面工具和应用程序；
（4）改变和发展基于网络的系统以反映新的拓扑结构或新资源；
ORB的作用：
ORB初始化ORB接口操作获取初始对象引用与线程有关的操作策略设置与管理对象引用操作
11.6什么是接口定义语言？
它在分布式计算环境中起到什么作用？
概念：
是一个描述软件组件接口的语言规范。
IDL用中立语言的方式进行描述，能使软件组件（不同语言编写的）间相互通信。
IDL通常用于RPC（RemoteProcedureCall，远程过程调用）软件。
IDL提供了一个“桥”来连接不同的系统。
作用：
1.实现标准的对象接口，构造分布式对象应用，使客户程序能调用远程服务器上对象的方法。
2.IDL为分布式对象系统定义模块，接口，类型，属性，和方法提供了设施。
11.7在CORBA的体系结构中，根据接口的可移植性和定义方式，接口分为哪几类，各起什么作用？
1.ORB核心
实现对所有ORB都相同的接口
2.对象适配器接口
连接对象实现和ORB。
3.接口定义语言IDL和静态接口
客户用ORB携带的IDL编译器，编译对象接口IDL文件，生成特定编程语言（如C++）的Stub和Sleket
升级会员 