1、1.2 什么是分布式计算系统？它的实质是什么？ 分布式计算系统是由多个相互连接的计算机组成的一个整体，这些计算机在一组系统软件（分布式操作系统或中间件）环境下，合作执行一个共同的或不同的任务，最少依赖于集中的控制过程、数据和硬件。 实质：分布计算系统 =分布式硬件 +分布式控制 +分布式数据。 1.10 多处理机与多计算机的区别是什么？同构多计算机和异构多计算机各有什么特点？ 区别：多计算机是将多个计算机联合起来处理问题 , 多处理机是在一个系统内集成多个处理器 . 广义上说，使用多台计算机协同工作来完成所要求的任务的计算机系统都是多处理机系统。即多计算机系统。 狭义上说：多处理机系统的作用是
2、利用系统内的多个 CPU 来并行执行用户的几个程序，以提高系统的吞吐量或用来进行冗余操作以提高系统的可靠性 。 同构计算机的特点： 1.每个节点是一台计算机，包含 CPU 和存储器。 2.节点间的通信量较少。 3.同构计算机系统的互连有两种结构：基于总线的多计算机系统和基于交换的多计算机系统。 异构计算机的特点： 1.节点差异很大， 节点可能是多处理机系统、集群或并行高性能计算机。 2.节 点间通过互联网络如 Internet 连接起来的。 3.有两种实现方法：采用分布式操作系统和中间件软件层。 1.16什么是中间件，它的功能是什么？它在分布式系统中的地位是什么？ 中间件是一种独立的系统软件或
3、服务程序，分布式应用软件借助这种软件在不同的技术之间共享资源。中间件位于客户机 / 服务器的操作系统之上，管理计算机资源和网络通讯 ， 是连接两个独立应用程序或独立系统的软件 功能：命名服务 作业调度 高级通信服务 资源管理 数据持久化 分布式事务 分布式文档系统 安全服务 地位：中间件的一个重要目标是对应用 程序隐藏底层平台的异构型，因此中间件系统都提供一组完整度不同的服务集。这些服务是通过中间件系统提供的接口来调用的。一般禁止跳过中间件层直接调用底层操作系统的服务。 1.18分布式系统有哪些计算模式？（必考） 1.面向对象模式 2.面向服务模式 3.公用计算模式 4.志愿参与模式 （详见书
4、 p21-p22 页 ） 面向对象模式 OOM 面向对象模式 OOM（ Object Oriented Model）是基于客户 /服务器模型（如 CORBA，DCOM) 面向服务模式 SOM Web Service 是这种面向服务模式的一个实例 ,SOA 是一个较完整的软件结构体系。 公用计算模式 UBM 支持 e-科学的计算 (如网格 Grid 等）。 志愿参与模式 VJM 志愿参与模式 VJM(Voluntary Join Model)是充分利用网上空闲的计算能力，支持计算量巨大的科学计算 2.5 有哪些名字服务形式？名字服务器的组成与功能是什么？ 名字服务形式： （ 1）名字服务：名字服
5、务是根据实体的名字查找它的属性（地址）。 （ 2）目录服务：目录服务既可以根据实体的名字查找实体的属性，当不知道实体名时也可以根据实体 的一个或多个属性及其值查找并得到一个匹配这些属性的实体列表。 （ 3）合约服务：是一种增强的目录服务，通过技术规范来定位一个命名实体。 名字服务器组成： （ 1）名字服务器操作 ：管理、查询操作和行政管理。增加、删除和修改上下文的目录项。访问优先权。 （ 2）名字解析 ：根据名字解析请求，得到被解析对象地址。 （ 3）缓存 ：缓存名字查询和解析的结果。 （ 4）多副本管理 ：副本修改和副本一致性维护。 （ 5）通信 ：客户端的名字代理通信和名字服务器之间 （
6、6）数据库 ：存放名字解析上下文或其子域。 名字服务器功能：管理名字 命名 上下文、实现名字查询与解析和其它名字服务器通信协调。 2.7 什么是迭代名字解析，什么是递归名字解析，它们各有什么优缺点？ 迭代名字解析：建议考试画图解释： 递归名字解析：也画图解释 各自优缺点： 递归名字解析缺点：要求每台名字服务器具有较高的性能。 递归名字解析优点： 1.递归名字解析过程中，各名字服务器解析的缓存结果使用更为高效。 2.如果主机与服务器距离很远，那么采用递归名字解析将更为高效。 迭代的优缺点与上面相反。 2.14什么是目录服务？目录项和属性及属性值的关系 是什么？ 目录服务：目录服务既可以根据实体的
7、名字查找实体的属性，当不知道实体名时也可以根据实体的一个或多个属性及其值查找并得到一个匹配这些属性的实体列表。 关系：目录项是一个命名对象的信息集合。每个命名对象包括若干个属性，每个属性有一个属性类型和相应的一个或多个属性值。 2.17 X.500 目录服务中定义了哪些目录服务协议？查询链与转交的含义是什么？ X.500 目录服务有 4个协议： 目录访问协议 DAP， DUA 用来与 DSA 通信。 目录系统协议 DSP，是两个 DSA 之间的操作协议，在 DSA 之间传递查询请求和响应。 目录信息镜像协议 DISP，是 DSA 用来将信息从镜像提供者传送给镜像使用者。 目录操作绑定管理协议
8、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 什
9、么是远程执行逻辑机模型？对逻辑机模型的要求是什么？ 概念： 客户节点上的代理进程负责远程服务节点上远程进程执行的初始化；远程服务节点执行客户机赋予的进程。这种模型成为逻辑机模型。 建议画图。 如图所示，它跨越用户节点和两个远程服务节点，在一个逻辑 机边界内保持稳健系统，进程的父子关系和进程组的进程视图的一致。 要求： （ 1）远程进程必须能访问驻留在源计算机上的文件系统。 （ 2）远程进程能接收逻辑机内任何进程发来的信号，也能将信号提供给逻辑机内任何进程。 （ 3）进程组保持在逻辑机内。 （ 4）基于树型的进程父子关系在逻辑机内必须得以保持。 3.13何为异步进程迁移算法？何为同步进程迁移算法
10、？它们的优缺点是什么？ 异步进程迁移算法：这类算法允许非迁移进程在迁移过程中继续运算，只有迁移进程被中断进行相关的操作。 优点：可以得到较好的执行效率。 缺点：和原有环境的兼容性不好，不能方便的移植。 同步迁移算法：这类算法在迁移过程中所有进程（包括非迁移的协同进程）都被挂起，进程之间需要同步来清空通信信道中的中途消息，所有进程均要阻塞等待迁移事件完成后，才能从中断处继续运行。 优点：算法简单，具有较好的可移植性和易于实现。 缺点：需要中央控制管理进程参与，所有进程都被迫中断，等待迁移过程的结束。 3.15比较进程远程执行与进程迁移两种机制。 进程远程执行，就是在集群中或者网络中寻找一个或多个
11、合适节点来执行用户程序。 进程远程执行的要求： （ 1）寻找管理机制。 （ 2）进程远程执行是透明的，应与位置无关。 （ 3） 主人优先原则 进程迁移是将一个正在运行的进程挂起，它的状态从源处理机节点转移到目标处理机节点，并在目标处理机上恢复该进程运行。 优点： 进程迁移具有灵活且应用广泛的优点，支持动态负载平衡、系统容错、高效使用本地资源等诸多系统功能。 缺点： 进程迁移的缺点是运行开销相对较大。 进程的迁移可以支持： （ 1）动态系统管理与维护 （ 2）动态负载平衡（ load balancing），系统中重负载处理机转移一部分负载到轻负载的处理机上运行，使得整个 集群系统中的所有处理机的
12、负载趋向均衡，从而提高系统的整体运行效率。 （ 3）系统容错 （ 4） 主人优先使用原则 4.1 在水平时间轴上表示阻塞发送 /接收和非阻塞发送 /接收进程与操作系统内核之间操作的时间关系。 没有具体答案，先方便理解一下阻塞和非阻塞： 阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）时的状态 . 阻塞调用是指调用结果返回之前，当前线程会被挂起。调用线程只有在得到结果之后才会返回。 非阻塞调用指在不能立刻得到结果之前，该调用不会阻塞当前线程。 例子： 你打电话问书店老板有没有分布式系统这 本书，你如果是阻塞式调用，你会一直把自己“挂起”，直到得到这本书有没有的结果，如果是非阻塞式调用，你不
13、管老板有没有告诉你，你自己先一边去玩了， 当然你也要偶尔过几分钟 check一下老板有没有返回结果。 这个图不知道对不对： 4.2 试叙述如何实现阻塞发送 /接收和非阻塞发送 /接收 ，对操作系统有什么要求？ 当进程到达发送原语时执行一次阻塞发送，无需等待对应的接收。在消息从 S安全写入发送缓冲区前，发送进程不能返回。 当进程到达接收原语时执行一次阻塞接收，无需等待对应的发送。然而，消息从缓冲区接收到 R 之前，接收进程不会返回。 系统要为阻塞模式消息传送提供临时的缓冲区。 当进程到达发送原语时执行一次非阻塞发送，无需等待对应的接收。只要通知操作系统有一个消息要发送，发送进程就可以返回。 当进
14、程到达接收原语时执行一次非阻塞接收，无须等待对应的发送。只要通知操作系统有一个消息要接收，接收进程就可以返回了。 系统要为非阻塞消息传送提供临时的缓冲区。 4.4 对以下每个应用程序，你认为“至多一次”和“至少一次”语义哪个最好？ （ 1）在文件服务器上读写文件：至少一次。 （ 2）银行服务：至多一次 （ 3）编译一个程序：至少一次 通过发送原语 send 和接收原语 receive 实现要求操作系统能实现 4 种不同的可靠性语义。 至少一次：保证正确完成消息传送至少一次 至多一次：保证正确完成消息传送至多一次。在没有节点崩溃和网络断开情况下，它只正确地执行一次消息传送。 事务语义：它保证消息
15、的原子性。不管节点崩溃或网络端口与否，它或者完成一次消息传送，或者什么也不做。 精确一次：无论在什么情况下，保证正确完成一次消息传送，不管是否有节点崩溃或网络断 开，它接近某种程度的容错机制。 4.9 什么是因果定律？它和 FIFO 全定序相比，哪个更严格？ 因果定律：不管含有因果关系的消息是由同一个发送进程多播，还是不同发送进程多播，所有接收进程要保证先接收“因”消息，后接收“果”消息。 FIFO：对同一个发送进程发出的多播消息，要求所有接收进程按发送的顺序接收，而对不同发送进程的多播消息可按不同顺序接收。 相比之下，因果排序更严格。 4.12RPC 被认为是分布式最初的中间件，它能实现分布
16、式系统的透明性吗？ p92 在 执行 RPC 过程中，客户可以简单的忽略不关心的内 容，客户 只是像执行本地调用一样调用远程过程， 并不直接执行 send 和 receive 原语，也不关心消息的传递，所有这些都隐藏在桩中，从而实现 RPC 的透明性。 在本地过程调用中， read 例程是由连接器从库中提取出来，连接到应用程序，当 read 是针对远程过程时，从库中获取 read 例程的另一个版本，客户桩。在服务器端服务器也为远程客户提供一个 read 例程，服务器桩。 5.2 假设两台机器的时钟每秒滴答 1000 次和 990 次，如果 UTC 每秒更新一次。两台机器时钟的最大偏移量是多少？
17、 答： 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
18、继续工作，等待请求。 如果 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是竞争资源的进程数。 Lampo
19、rt 算法： 1.Pi 进程发送资源 请求消息 Request（ Ti： Pi） ； 2.Pj 进程 收到 Request（ Ti： Pi），按 T顺序置于其消息队列，如果没有资源请求或请求时间晚于收到消息的时间戳，回应 Reply（ Tj： Pj） ； （ 否则不返回任何消息 ） 3.进程 Pi被批准使用临界资源条件： 有请求，且 Ti 最小（消息全定序）； Pi接收了所有晚于 Ti 的消息（包括应答） 4.Pi 释放资源 ， 退出临界区 ，发送 Release（ T j+1： Pi） ； 5.Pj 收到 Release 后，删除（ Ti： Pi） ； 检查是否还有进程等待进入临界区。 Ri
20、chart 算法： 1.Pi 进程发送资源 请求消息 Request（ Ti： Pi）； 2.Pj 进程 收到 Request（ Ti： Pi），按 T 顺序置于其消息队列 ， 并做： 如果没有资源请求或请求时间晚于收到消息的时间戳，回应 Reply（ Tj： Pj） ；否则推迟返回应答消息 。 3.进程从临界区退出，向需要请求资源的进程补发 一个 应答消息 。 4.请求进程从竞争进程得到应答小 Reply（ Tj： Pj），便可进入临界区 改进地方：第二步中，接收到资源请求消息之后，无论赞成或者拒绝都会返回一个应答消息，这样 用超时机制可以确定进程是否崩溃。 优点： 1.它具有对称性 2.具
21、有完全的分布式控制 3.对通信链路相对速度的不敏感性 4.能保证互斥，不会发生死锁也不会发生饥饿，能处理进程的加入，退出和崩溃。 5.开销减少。 5.8 比较集中式算法、 Ricart_Agrawala 算法和令牌算法的开销和问题 开销：集中式算法开销最大， Richar 算法需要 2（ N-1） 个消息，令牌算法最多需要 N-1个消息。 集中式算法的问题：容易出现单点故障 。 可能成为系统性能的瓶颈。 Ricart 算法的问题：由于不应答被认为是资源被占用，所以如果有某个节点故障，会导致该算法的异常终止。同时各进程对资源的使用情况缺乏了解。 令牌算法的问题：检测令牌丢失困难 5.11 共享
22、K 个相同资源的互斥算法和 Ricart_Agrawala 算法的共同点和区别是什么？ 相同点：基于相同的概念，每个竞争进程都维持一个推迟应答数组 RD，数组元素是表示相应进程是否推迟发出应答消息。 区别： 1.应答消息到达的环境。在 Ricart 算法中，正在等待进入 临界区的进程要得到N-1 个应答消息。在共享 K 个相同资源的互斥算法 中， N-K个应答消息是在进程等待时到达， K-1个消息是进程已在临界区或等待进入临界区或离开临界区后到达。 2.在 Ricart 算法中，其他竞争进程推迟应答数组的每一项 RDi是布尔型，因为应答只能是一个，或是推迟，或是不推迟。在共享 K 个相同资源的互斥算法中，可能有多个应答消息被推迟，这样 RDi应声明为整数型。 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） 为什么符合因果一致性定律？
