分布式系统——试卷分析

本节内容:2015年秋南京大学计算机系分布式系统期末试卷分析。

1. 分布式系统的定义与架构(15分)

1.1 分别描述网络操作系统与分布式系统的定义

  • 网络操作系统:一种面向计算机网络的操作系统,允许网络中的多台计算机访问共享的文件和打印机,允许共享数据,用户,组,安全,应用和其他网络功能。
  • 分布式系统:一个分布式系统是一些独立的计算机集合,但是对这个系统的用户来说,系统就像一台计算机一样,即从硬件角度来讲,每台计算机都是自主的,从软件角度来讲,用户将整个系统看做是一台计算机。

1.2 解释分布式系统中透明性的含义

  • 透明性:将分布式系统中的进程和资源实际上在多台计算机上分布这样一个事实隐藏起来,如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统,这样的分布式系统就称为是透明的。
  • 种类:访问透明性、位置透明性、迁移透明性、重定位透明性、复制透明性、并发透明性、故障透明性

1.3 如何理解分布式系统中的机制与策略

  • 策略:主要定义一些功能完成的程度及要求,如客户端缓存数据时需要什么程度的一致性等
  • 机制:能提供或不能提供什么功能,如允许动态设置缓存策略,支持对移动代码的不同级别的信任
  • 分布式系统中仅提供机制

2. 进程与线程(10分)

2.1 简述进程与线程的异同

  • 进程:进程是正在运行的程序的实例,是系统进行资源分配和调度的一个独立单位。
  • 线程:线程是CPU调度和分派的基本单位。
  • 相同点:都能进行并发。
  • 不同点:线程不拥有系统资源,同一个进程内的线程共享资源,进程至少有一个线程,有自己的独立地址空间。

2.2 代码迁移与虚拟机迁移相比,有什么优势与劣势

  • 优势:迁移量比较少,能快速完成,有效减少网络带宽
  • 劣势:机制复杂,迁移后的代码可能在新机器上不能很好地运行,所引用的资源在新机器上不可用

3. 通信机制(15分)

3.1 在远程过程调用(RPC)过程中,如果客户端出现故障,请给出至少3中可能的解决方式

  • 客户端故障:
    • 客户端无法定位服务器:可能原因:服务器关闭,服务器使用了新版本的存根而客户端使用了较旧版本的存根;解决方法:使用一个特殊码,例如-1作为过程的返回值来指示失败;让错误触发一个异常或信号。
    • 客户端向服务器端发送的请求消息丢失:当发送一个消息的时候内核开启一个计时器:在响应或ACK到来之前定时器过期,则内核重发;如果消息真的丢失:服务器不会区分原始和重传的消息,一切正常;如果许多请求都丢失,内核放弃并假装服务器已经关闭了。
    • 客户端发送请求后崩溃:
      • 消除 extermination: 在日志文件中纪录 RPC 请求,重启后清除孤儿
      • 再生 reincarnation: 按时间顺序编号不同的时间段。当客户端重启时,广播一条消息宣布新的时间段开始,当广播到达时终止所有远程计算,无需日志
      • 温和再生 gentle reincarnation: 与再生相似,但是当广播到达时,每台机器会寻找远程计算的所有者,仅当找不到所有者时,计算才会被终止。
      • 过期 expiration: 赋予每个 RPC 一个标准时间配额,未完成任务明确申请额外配额。

3.2 为什么要采用动态绑定机制来实现服务器的定位?动态绑定有什么缺点?

  • 优点:
    • 灵活性
    • 能支持多个支持同一接口的服务器
      • 绑定程序(binder)可以随机地将服务器上的客户端传播到均匀负载
      • 绑定程序(binder)可以定期轮询服务器,自动取消注册失败的服务器,以达到一定的容错能力
      • 绑定程序(binder)可以帮助身份验证
    • 绑定程序(binder)可以验证客户端和服务器都使用相同版本的接口
  • 缺点
    • 导出/导入接口的额外开销花费时间
    • 绑定程序(binder)可能成为大型分布式系统中的瓶颈

3.3 分别说明持久性通信和非持久性通信的含义,电子邮件和QQ留言分别属于什么样的通信模式?

  • 持久性通信:通信机制本身会对消息进行持久存储,直到它被传递给目的。
  • 非持久性通信:消息的发送者和接收者必须同时存在才能进行,传输服务仅仅提供临时的对消息的存储。
  • 电子邮件:持久通信;QQ留言:持久通信

4. 命名与同步(20分)

4.1 请简述“基于本部的方法”(home-based approach)是如何解决移动实体定位的

  • 实体的本部位置地址在命名服务中注册;
  • 本部位置上注册了实体的外部地址(Foreign address);
  • 客户端先访问本部位置,随后访问外部地址。

4.2 为什么要进行同步?分布式系统的同步与集中式系统有何区别?

  • 同步:
    • 与进程间通信紧密相关的问题是进程间如何协作和同步
    • 多个进程不能同时访问访问一个共享资源,而是相互协作,彼此暂时地独占访问
    • 多个进程有时可能需要就时间的顺序达成一致
  • 区别:相较于集中式系统的同步,分布式系统没有共享的存储,也难以实现物理时钟的一致性。集中式系统中的同步问题不适合于分布式系统。

4.3 假设有 3 个机器采用 Lamport 算法进行同步,设左边图给出了机器原始时钟下的交互图。

  • 在右边方框内画出经过 Lamport 算法调整后的时钟图。
  • 判定下面 4 组事件中两个消息发送事件的先后顺序:在先发生事件后打钩,如果不能判定,则在“不能判定”后面打钩。

i. P1 (send, m3) P3(send, m4) 不能判定 yes

ii. P2 (send, m4) P1(send, m5) 不能判定 yes

iii.P3 (send, m4) yes P2(send, m6) 不能判定

iv. P3 (send, m7) yes P2(send, m8) 不能判定

时钟图 Lamport时钟

5. 一致性与容错(15分)

5.1 下图所示两组进程读写是否满足因果一致性和顺序一致性?如果不满足,需要说明原因。

一致性

  • a: 不满足顺序一致性:读到的最终值应该b,不满足因果一致性:p2中a在b之前,不应该先读b再读a
  • b: 满足顺序一致性:最终读到b,满足因果一致性:先a后b

5.2 下面的已编号小竖线表示进程的检查点(check point),箭头表示消息发送,横轴表示时间,设 P2 在图所示处出现故障,3 个进程从检查点进行恢复,请从这些检查点中构建一个最近的一致全局状态,并说明理由。

检查点

检查点为258:因为全局一致要求任意两个检查点作恢复点时中间连线与事件没有交点。

6. 社会网络(10分)

6.1 比较随机图(Random Graph)、小世界(Small-World)和无标度(Scale-free)三种网络模型。

6.2 请描述社会影响力最大化问题,并阐述解决该问题的思路。


6. 本学期未上这一章节


7. 云计算(15分)

7.1 简要说明虚拟化技术所解决的问题,并说明虚拟化技术与云计算的关系。

  • 虚拟化:细粒度资源分配,动态迁移,增加资源利用率
  • 关系:
    • 封装与隔离:保证每个用户有安全可信的工作环境
    • 多实例:保证较高的资源利用率,为服务器合并提供基础
    • 硬件无关性:整合异构硬件资源可实现虚拟机迁移,使资源调度、负载平衡容易实现
    • 特权功能:入侵检测和病毒检测
    • 动态调整资源:细粒度的可扩展性

7.2 以 Openstack 为代表的这一类云计算平台的基本功能是什么?

  • OpenStack是一个开源的云计算管理平台,主要为了管理:计算、存储、网络三个方面的资源,是IaaS组件,这些资源可以通过OpenStack进行配置分配并提供给上层应用或用户去使用。

7.3 应用场景

应用场景1:某校计算中心需要不同资源需求的桌面(Linux、Windows 等),应用于不同类型的计算机课程教学;

应用场景2:某校物理系多个实验室需要三种软件进行模拟实验,这些模拟实验对计算资源消耗极大,但这些实验往往不是同时进行。

上述两个应用场景分别是否适合采用 Openstack 平台来搭建系统,说明理由。

    1. 能:教学是一个典型的多用户,每个用户使用资源不是很多,同时性的环境。终端用户对资源需求较少,数据中心资源利用率较低。
    1. 不能:OpenStack主要用来进行资源分配给多个用户同时使用,但模拟实验对计算资源消耗极大,划分资源后运行软件资源会不够用,并且往往也不是同时运行。