PPPP.ink 粉墨 - 粉墨日记

北航 研究生 分布式操作系统考试内容

6/20/2021

大概是人生中最后一场专业课考试，接下来又会有怎样的考验？

我们的征途是星辰大海

# 考试考了啥？

笔者参与了 2021 年的北航计算机学院研究生分布式操作系统考试，考试是开卷考试，大概考了下面的内容：

  • 论述题：
    • alice 和 bob 想要实现交易，他们在安全性上需要注意什么
    • 一致性和复制的意义，给了两个一致性模型的图，判断达到了怎样的一致性模型，为什么
  • 简答题 和 概念题：
    • 什么是分布式系统，什么是分布式操作系统
    • 什么是逻辑时钟，什么是 lamport 逻辑时钟
    • 分布式系统的挑战是什么，研究方法是什么
    • RPC 中存在哪些问题， 以 read 远程方法为例，简述 RPC 的实现原理
    • 进程迁移的研究策略和方法
    • 什么是面向消息的瞬时通信，什么是面向消息的持久通信
    • 什么是递归名称解析，什么是迭代名称解析
    • 拜占庭问题是怎么解决的，三副本容错能否解决拜占庭错误

# 感受

说真的，开卷考试的话，大部分内容在书上都能找到，而且老师最后一节课还划了重点。但是，题目真的多，要写的内容好多，一共有六页卷子，差点写不完。而且总感觉好多内容答得并不到位...

# 1. 概论

  • 分布式系统的定义：

    • 分布式系统是若干 独立 计算机的集合，这些计算机对于用户来说就像是一个 单一 的系统
    • Andrew S. Tanenbaum：一组独立的计算机系统，但是对 用户 看起来像是一个 单一 的计算机
    • 分布式系统通常表现出中间件的形式

  • 分布式系统基本特性

    • 系统由并行执行部件组成
    • 系统没有共享内存
    • 系统中无全局时钟
    • 没有节点拥有全局信息状态
    • 系统部件可能失效
    • 系统具有容错机制
    • 多副本需具有一致性，保证扩展性

  • 单机操作系统与分布式操作系统的区别

    • 围绕基本特性，阐述自己的观点
    • 缺乏自治性，强调统一操作系统下整体控制

  • 网络操作系统与分布式操作系统的区别

    • 主要目标是资源共享，缺乏透明性。
    • 网络操作系统：
      • 主要目标是信息共享和提供非透明服务，用户具有完全的自治 性。对全局管理、并行操作、自治控制等特性无硬性要求，结 点之间物理联系、逻辑关系松散，强调个性，没有一个完全一 致的系统状态图。
    • 分布式操作系统：
      • 所有的系统资源都是对用户开放的，用户就像在使用一个完整 的单机 (基于微内核的和现有OS之上的二种构建方法）
      • 每个机器安装统一的微内核以连接各不同的硬件系统，微核结 构减小了操作系统尺寸，隐藏了硬件的异构性
      • 分布式系统中处理机只有很少的自治性，主要由DOS和系统管理员统一管理
    • 两者区别：

      • 与分布式系统的最根本区别： 透明性：对用户屏蔽系统组件的分散性 [ISO 1992]: • 访问透明性: 相同操作访问本地和远程资源 • 位置透明性：不需要知道资源位置就可访问 • 并发透明性：几个进程能并发共享资源，互不干扰 • 复制透明性：无需知道副本的存在 • 故障透明性：屏蔽错误 • 移动透明性：不影响应用的情况下，允许资源和客户移动 • 性能透明性：负载变化时，允许系统重构 • 伸缩透明性：不改变系统结构前提下，允许系统扩展

      • 文件系统：

        1. 没有操作系统方法：文件传送（如USENET网络）
        2. 网络操作系统方法：把不同文件系统连接起来 Open (“/machine1/pathname”,READ)
        3. 分布式操作系统方法：所有各子系统的文件系统组成一 个整体文件系统，任何机器想要读password文件时 open(“/etc/password”,READ ONLY) 不必指出该文件在哪里（LOCUS）

      • 访问控制：

        用户标识（UID）问题：多机远程访问不唯一性

        1. 没有操作系统时：使用远程机器上用户名。
        2. 网络操作系统时：对不同机器的UID进行变换，需要提供一个充分大的变换表
        3. 分布式系统中：单一的UID

      • 执行地点：

        用户运行一个程序时，在哪里运行？

        1. 没有操作系统时：远程登录，然后运行在那里的作业
        2. 网络操作系统时：指定一个机器运行 remote vax4 job
        3. 分布式操作系统: 用户只需要简单提交job,由操作系统 寻找合适的处理机，用户察觉不到机器的边界。

  • 分布式系统的中间件模式

    • 分布式系统DOS具有上述的优势，却并不实用，其主要原因：

      • 技术难度大；

      • 继承性差，一般需对底层重新开发；

      • 现实中存在大量的独立设备，具有自治性，很难把它们联入分 布式系统、

    • 中间件模式可以 增加系统透明性， 抑制网络用户自治性 屏蔽底层异构性

  • 分布式操作系统目标，必须做到四件事 ：

    • 资源可访问：能够使用户方便地访问资源
    • 透明性：必须隐藏资源在一个网络上分布
    • 开放性
    • 可扩展性

  • 基本研究方法

    • 合理的假设：通信问题带来的影响
    • 动态方法，静态方法
    • 最大最小问题
    • 管理系统和数据本身是分布式的：DNS
      • 解决分布式的问题，但本身是分布式

  • 三种可扩展性技术是什么：

    1. 隐藏通信等待时间：采用异步通信的方式，发出通信操作后执行其他工作，不单纯等待响应；启动新的控制线程执行请求；将部分工作分散给客户
    2. 分布技术：将某组件分割为多个部分，分散到系统中
    3. 复制技术（解决性能下降问题）：能增加可用性、有助于负载平衡、新问题：一致性问题、解决：全局同步机制

  • 分布式操作系统内容：

    image-20210614101443860

# 2. 体系结构

# 2.1 四种软件体系结构 ：P24

  1. 分层体系结构
  2. 基于对象的体系结构
  3. 以数据为中心的体系结构
  4. 基于事件的体系结构

# 2.2 基本概念

  • 平均响应时间（Mean Response Time）：响应时间是任

    务从提交到结束的时间，系统的平均响应时间指系统中 所有任务的平均响应时间，反映的是系统的整体性能。 设任务的到达率为 λ\lambda，系统的服务率为 μ\mu，则系统平均 响应时间为T＝1/(μ−λ\mu-\lambda)

  • 系统可用性：系统可用性定义为：平均无故障时间MTTF / (MTTF+平均维护时间MTTR)

  • 加速比（Speed Up）：定义为一个程序串行执行花费的时间和并 行执行所用时间的比值，用于衡量一个并行执行的程序效能。

    • Ts为串行执行的墙钟时间， Tp为并行执行的墙钟时间， 则 加速比 Sp＝Ts/Tp。
    • f=tp/Ts为并行化率; 即：tp=f×Ts，

  • Amdahl定律：Sp = 1/[(1-f )+f/n]当n－> 无穷 Sp－>1/ (1-f )。

    • 当程序中串行成份一定时，处理机数增加到一定时，再增加处 理机数，加速比也不会无限增大。
    • 程序的串行部分是瓶颈，为获取好的加速比，应使并行化率尽量大。

# 3. 进程迁移 （分布式进程）

# 3.1 进程概念

  • 进程是程序的一次执行

  • 进程是系统中独立存在的实体，它可以拥有自己独立的 资源，比如文件和设备描述符等。在没有经过进程本身 允许的情况下，其他进程不能访问到这些资源。这一点 上和线程有很大的不同。

  • 进程与程序的区别在于，程序只是一个静态的指令集合 ，而进程是一个正在系统中活动的指令集合。

  • 进程运行的环境称为进程上下文，进程的上下文由进程控制块PCB(process control block)、 正文段(text segment)、数据段(data segment)以及用户堆 栈(stack)组成。

# 3.2 内核级线程和用户级线程

  • 内核级线程（KLT）中的所有线程的创建、调度和管理 全部由操作系统内核负责。当一个线程想去创建一个 新线程或撤消已存在的线程时，它发出一个内核调用 ，由它完成创建和回收工作
  • 轻量级进程（Lightweight processes,LWP)，线程包完全在用户空间实现，可以由多个LWP共用，阻塞调用时，转到内核模式。不会导致整个进程阻塞。线程；创建、注销及同步开销小，不需要内核干预。如有足够多LWP，则阻塞调用不会导致整个进程挂起。 LWP是隐式执行，对程序员透明可在多处理器系统上方便地应用

# 3.3 进程选举

  • 同步环中领导者选举

    image-20210614105648974

    • 停止和非领导者输出 LCR算法无法停止 增加：选出的领导者发通知消息，收到通知进程传递消息后停止 变形：在消息上附上领导者进程下标，可以参与进程都输出领导者

      复杂度：

      时间复杂度是n轮 通信复杂度是O(n^2)

  • 算法证明：

    image-20210614105759360

    分布式中一般要有一个leader，层次结构，但leader具有分布式特征，动态选举，和固定leader不是一个概念

  • BUlly 欺负 算法

    • 将进程进行排序

      • ① P向高的进程发E 消息

        ② 如果没有响应， P选举获胜

        ③ 如果有进程Q响应,则P结束，Q 接管选举并继续 下去。

    image-20210614105939473

# 3.4 代码迁移

  • 关键研究问题：

    • 迁移进程的状态收集、传输、恢复问题；

      • 收集

        • 内部状态收集：进程主动调用状态收集函数对自身进 行状态收集。这种方式将状态收集函数直接写入程序 代码，由用户主动启动进程迁移
        • 外部状态收集：这种方法将需要迁移的进程挂起，然 后通过操作系统提供的特殊系统接口对该进程进行状 态收集
        • 触发式状态收集：由信号触发导致进程对自身进行状 态收集。这种方式中，需要在程序中设置特殊的迁移 信号及信号处理函数，当迁移进程接收到迁移信号时 ，就会进入相应的信号处理函数进行自身状态收集

      • 传输

        • 全拷贝算法：即在完全传输所有的状态信息后，再重 启迁移进程
        • 预拷贝方式：迁移发起时，先将当时的虚存空间传到 目标节点机上，而迁移进程在源节点机上继续运行。 然后挂起进程，再追加拷贝这段时间内改变过的内存 页。
        • 惰性拷贝技术：先将进程的基本状态信息传输到 目标节点机，恢复进程并在目标节点机上继续运 行时，要读内存哪一页就从源节点机上传过来。

    • 进程的远程透明执行问题；

      • 有可能由于主机状态 改变而导致一系列复杂的问题，其中较为常见的有： 由于文件访问位置改变而导致无法访问；某些和位置 有关的系统调用无法实现等。
      • 转发技术：往往针对一些与位置有关的操作，如部分 系统调用、信号处理等。转送回源结点进行处理后再 将结果返回到目的结点的方法，但是对源结点和目的 结点的性能都会造成一定的影响，并带来对源结点的 剩余依赖性。
      • 单一系统映象：使文件访问可以独立 的方法来解决，这样不管在系统的任何位置执行这类 操作，都不用关心或修改相对位置的信息，保证当进 程迁移到新位置后，不用修改访问文件的位置，可以 和迁移前一样正确的访问到文件。

    • 迁移进程的通信处理问题

      • 迁移进程新位置可识别，即迁移完成后，其它进程仍 然可以保持和迁移进程的正常通信
        • 建立进程地址映射表，在用户进程发送/接收消息 时，先进行地址匹配，引导以旧地址为目的地的消息 转向新的地址位置；
        • 采用特殊路由方式，让进程迁移后，通信地址不变 ，而增加路由信息映射表，该表中记录迁移进程的实 际位置
      • 不丢失任何消息，即在迁移过程的临界阶段不能导致 任何消息丢失；

        • 发送/发自迁移进程的用户消息分成三类：

          • 类型一：在迁移过程开始前发送，且在迁移过程开 始前能到达目的进程的消息（没丢失，过程前）。
            • 在进程迁移之前，发送特殊消息信号，通知其它进程 此进程将要迁移，并得到它们的认可保证在迁移过程 中不发送任何消息给迁移进程。
            • 消息驱赶方法：将所有的中途消息驱赶到目标进程之 后，再进行进程迁移过程，并保证在迁移过程中不再 发送任何中途消息
          • 类型二：在迁移过程完全结束后发送的消息（依赖 新位置识别，过程后）。
          • 类型三：在迁移过程前或迁移过程中发出，且尚未 被目的进程接收到的消息，以及在迁移过程中发送 的消息，这一类消息称为“中途消息”（过程中）
            • 消息重定位方法：迁移过程中，其它进程仍然发送消 息给源结点，源结点缓存所有收到的发给迁移进程的 消息，待迁移结束后，再转发这些消息到目的结点。
            • 消息丢失恢复方法：在迁移过程中发送的消息都将丢 失，待迁移完毕后，重新建立连接并重新发送消息
            • 消息丢失保护方法：由源结点通知迁移进程的新地址 ，消息先发送到新结点暂存，待迁移进程恢复执行时 ，从本地缓存中取得消息。
      • 保证接收消息的正确接收顺序
        • 消息分片标识：对于过长的消息，系统可能把它分解成多个消 息碎片传送，接收消息时，应该保证消息碎片的正确顺 序
        • 排队顺序

  • 总结：研究问题：

    • 进程迁移的步骤和实现层次

    • 迁移进程的状态收集、传输、恢复问题（进程状态收 集，传输方法）

    • 进程的远程透明执行问题（转发机制和修改）；

    • 迁移进程间的通信处理问题

      –迁移进程新位置可识别（地址映射和特殊路由）

      –不丢失任何消息（消息驱赶法和消息转发方法）

      –保证接收消息的正确接收顺序（消息分片标识和排队顺序）

    • 进程迁移算法： 异步，同步和类异步算法

# 3.5 进程迁移步骤：

[Step 1] 询问目标处理机是否可以接受迁移进程 ；

[Step 2] 得到目标处理机的肯定答复后，在目标处理机上创建恢复进程 ；

[Step 3] 中断迁移进程的运行程序；

[Step 4] 在源处理机上收集迁移进程状态 ；

[Step 5] 将迁移进程状态传输到目标处理机

# 4. 负载平衡

# 4.1 研究负载平衡的基本问题：

何时开始转移任务以平衡系统负载，即时机或触发点问题。

怎样比较不同处理机的工作负载，确定某个处理机应转移负载。

在选定要转移任务的处理机中，选择那些任务进行迁移。

那一个处理机是这些任务转移的最合适的目的处理机。

系统中那个或那些处理机负责完成搜寻目的处理机的工作。

在负载再分配时需考虑什么参数 必要的帮助决策的处理机信息是集中存储管理还是分布存储管理

是单处理机做决策还是多个处理机协同做出决策采取什么样的机制。

在完成负载平衡时，怎样找到性能和 效率的平衡点。

怎样避免使轻负载机变成重负载机， 从而引发循环任务转移

# 4.2 进程迁移的三大研究策略

  1. WHEN 传输策略

    传输策略决定负载平衡的时机，一个基本 问题是如何衡量负载的大小，

    • 衡量负载大小指标要求

      • 测量开销低，较易获得和计算，以满足频繁 测量的需要。
      • 能客观体现所有竞争资源上的负载。
      • 各个负载指标在测量及控制上彼此独立

    • 负载指标

      • Platform LSF使用资源队列长度作为负载指标。认为CPU队列长 度和I/O队列长度分别与CPU类作业和I/O类作业有密切关系。

        • Ferrari 提出使用各种资源队列长度的线性组合作为负载指标。 但其条件是假定系统处于稳定状态，并且要求资源是排队顺序的 （如FCFS）。

        • Bonomi等人使用处理机上活动的进程数的瞬时信息和周期搜集到 的平均CPU运行队列等信息的组合作为负载指标。但不能反映资源 利用率。

        • Kunz等人研究了运行队列任务数、系统调用率、进程切换率、空 闲主存大小、1分钟平均负载和空闲CPU时间 6项负载指标及其组 合。进行性能对比，但其实验规模较小（4个结点）

  2. WHERE 定位策略 选择目的处理机

    • 自定位：仅使用目的处理机的名字等属性进行定位
    • 本地定位：每个处理机存储定位信息，但这些信息不能保证和当前系统的一致，从而有可能导致失败。
    • 服务器定位：一个特殊的服务器用于完成任务到目的 处理机的映射
    • 广播方式：广播定位消息，接收合适的应答，选择处理机
    • 信息收集：
      • 集中式：集中式是把所有处理机信息收集到 机中，由此服务器负责定位和任务调度。
      • 分布式：信息存储在多个物理上分布的处理机中，定 位和调度决策由这些处理机分区域作出或协商作出。
      • 全局式：每个处理机定时广播负载信息到所有处理机 ，每个处理机各自作出定位和调度决策。
      • 集中分布式：由一个服务负责收集信息，然后广播到 所有处理机中，每个处理机各自作出定位和调度决策
    • 选择策略：
      • 随机策略：一种盲目方式，不需任何信息，随机定位 一个目的机。包括随机发送和随机服务。
      • 门槛策略：收集部分处理机信息，随机定位一个其负 载值低于给定门槛值的处理机做目的机，重复这个过 程，直到找到目的机。
      • 最短策略：收集较多的信息，随机选择一些处理机， 选择最短队列长度的处理机，如其负载低于门槛值， 则定位它为目的机，否则不迁移。
      • 聚焦策略：收集更多的信息，随机选择一批处理机， 选择其剩余资源能满足任务需要的处理机。
    • 选择处理机算法
      • 招标算法：用于在不知其它处理机信息或已有信息不能很好 找到合适处理机情况下定位目的处理机，各处理机上运行一个本地代理和一个远程代理，有任 务迁移需求的处理机的本地代理广播任务消息，同时 也接收其它处理机的任务消息。中标者还可以将任务分解再招标，它又成了招标者
      • 剃度算法：各站点周期性更新信息和邻近度信息，每个站点由低水线和高水线两个参数，当负载高于高水线是过载，低于低水线时为轻载，站点邻近度反映该点到一个轻负载点的最值，轻载点邻近度为0，其他点邻近度为到所有邻近 结点中邻近度最小值。当一个结点邻近度的新值不同于旧值时，将向所有邻 近站点广播信息，当一个站点超载，向最小邻近度的站点转移一个任务。如果一个站点邻近度大于网络直径时，系统处于饱和
      • 渗透算法：通过相邻域重叠部分扩散负载达到平衡：

  3. WHICH 选择哪一个任务 决定一个任务是否适合远程执行，是否迁 移该任务，决策依赖于任务的参数、处理机负载和其它信息。

    • 选择任务一般原则
      • 执行时间长的任务
      • 计算型任务：避免交互式和IO型任务
      • 独立型强任务
    • 先验知识：一般可根据先验知识形成可迁移进程表，当新产生一个进程而 有需求迁移时，查表决定该任务是否可远程执行。
    • 剥夺式情况，先验知识很难保有，且任务的执行情况也无法预 知，所以一般假定无先验知识可用。所谓可迁移进程是其迁移 后能使系统的平均响应时间减少的进程。
    • 预测进程生存周期：
      • Eager等人研究认为它服从指数分布，进程剩余运行 时间与过去状态无关，在这种情况下，所有进程被假 定具有相同的剩余运行时间，因此，策略采取选择具 有较小迁移开销的进程。
      • 另有假定认为进程生存周期服从对数空间的均匀分布匀分布，剩余执行时间随已运行时间增加到某点时开 始下降。这时，应选择运行时间较长而又不太长的进 程迁移

  4. 最后的目标：收益要大于开销

# 4.3 迁移方式

  • 远程执行: 是在任务调度运行时派生到远程处理机上执行的情况 一般可根据先验知识形成可迁移进程表，当新产生一个进程而有 需求迁移时，查表决定该任务是否可远程执行
  • 进程迁移: 中止当前某一进程的运行迁往另一处理机上继续运行 选择可迁移进程的标准和策略是实现动态抢先式负载分担的关 键问题。所谓可迁移进程是其迁移后能使系统的平均响应时间减 少的进程。确定一个简单实用的选择可迁移进程的预测标准是十 分重要的
  • 目标：收益要大于远程执行或迁移造成的开销

# 4.4 思考题：

  • 3W策略的主要内容
  • 该领域的主要研究点
  • 设计一个信息收集机制
  • 设计实现一个负载平衡算法

# 考试内容

  1. 名词解释：最简单的方法解释出来
  2. 简述题：稍微要展开，基本原理是什么
  3. 算法策略题（论述题）

# 5. 分布式系统通信

# 5.1 通信类型：

  • 四种通信类型
    • 持久通信：提交消息一直由通信中间件存储，直到该消息被传送给接收方。
    • 瞬时通信：通信系统只有在发送和接收程序运行时才存储消息
    • 异步通信：发送方提交传输消息后继续执行，中间件临时存储消息
    • 同步通信：发送方可能被阻塞直到知道其请求被接受，被完全处理
    • 不连续通信：各方以消息进行通信，每个消息是一个完整信息单元
    • 流通信：一个接一个发送多个消息，消息按照发送顺序相互关联
  • 持久通信与同步通信组合：消息队列系统；瞬时通信与同步通信组合：RPC

# 5.2 远程过程调用 RPC

  • RPC 原理：程序调用其他机器上进程

    机器 A 调用机器 B 上进程时， A 调用进程挂起，而 B 上被调用进程 开始执行，调用方将参数传到被调用进程，得到回传结果。

  • RPC 步骤

    1. client应用程序正常调用client stub
    2. client stub构造消息，通过trap进入核心
    3. 核心将消息发送到server的核心
    4. server核心将消息交给server stub
    5. server stub将消息解包，用相应参数调用服务例程
    6. 服务例程进行计算，将结果返回server stub
    7. server stub 构造消息，通过trap进入核心
    8. 核心将消息发送到client的核心
    9. client核心接收消息并将它交给相应stub
    10. stub解包，将调用结果返回应用程序

  • 参数传递

    • 数据格式问题：
      • 统一规范格式，简单但不灵活，效率也不高
      • 增加一个参数，或在消息中指明格式，由接收者做相应处理，效率较 高，但每个机器需配置完全的格式转换程序
    • 指针类参数问题：
      • 全部禁用，不利于用户使用
      • 复制/重新存储方法，client以实体代替指针，server生成缓冲区存 放实体，计算后将缓冲区打包发回
    • 复杂数据类型问题
      • 在GIS中，指针指向图，此时需制订专门的通信协议，详细描述数 据规格，并配置相应程序读取

  • RPC 的实现

    • 同步：客户发RPC请求后阻塞
    • 异步：客户发RPC请求后继续执行

# 5.3 消息传递机制

  • 消息类型

    • 面向消息的瞬时通信 p101

      • Berkeley套接字

        • Socket 是一个基本的通信机制

          • Socket是应用层与TCP/IP协议族通信的中间软件 抽象层，它是一组接口。

          • Socket把复杂的TCP/IP协议族隐藏在Socket接 口后面，对用户来说，一组简单的接口就是全部， 让Socket去组织数据，以符合指定的协议。

      • 消息传递接口

    • 面向消息的持久通信

      • 消息队列模型
      • IBM WebSphere MQ

# 6. 命名系统 名字服务

# 6.1 三种类型名称

  • 地址：实体访问点是一种特殊实体，其名字为地址
  • 标识符（identifier）：唯一标识实体的名称，一对一
    • 一个标识符最多引用一个实体
    • 每个实体最多由一个标识符引用
    • 一个标识符始终引用同一个实体
  • 友好名称：通常字符串表示,好记

# 6.2 结构化命名

# 6.2 递归名称解析

  • 递归查询：对于客户端的请求或发起查询的DNS 服务器转发来的请求，若本DNS服务器无法解析(本 机数据库查询无)，自行向其它DNS服务器转发，并 将获得的查询结果返回发起者。
  • 迭代查询：对于客户端或发起查询DNS服务器转 发来的请求，若本DNS服务器查询无，则告诉（返 回信息）发起者另一台DNS服务器的IP地址。

# 6.3 基于属性的命名

  • LDAP协议：轻量目录访问协议，基于IP访问X.500数据的方法
  • 基于属性和DHT的方法：把属性值对映射的基于DHT的系统，使得实体标 识符集可以实现分布性。
  • 语义覆盖网络：结点维护一个有关其他结点的本地列表，这些结点 语义上具有类似内容，这些语义列表可以有助于高 效搜索。

# 7. 同步

# 7.1 为什么要同步

  • 分布式系统特点

    • 系统由分布并行执行部件构成

      • 系统部件可能失效

      • 系统中无全局时钟

      • 通信延迟难以确定

      • 可能超时，链路崩溃等

      • 容错，多副本一致性问题

      • 可能丢失，乱序，篡改，重传等

    • 缺乏全局的系统状态

  • 分布式算法特点：

    • § 相关信息散布在多个场地上
    • 每个进程只能基于本地信息做决定
    • 应避免因单点故障造成整个系统的失败
    • 不存在公共时钟或精确的全局时间
    • 在一处收集的信息不能推断到全局信息

# 7.1 逻辑时钟

  • 什么是逻辑时钟：

    • 逻辑时钟只要保证计算机内部各时钟一致，而不是是否与真实时间接近，更近一步，能跟踪和反映计算机内部事件发生的顺序称为逻辑时钟
    • 重要的不是所有进程在时间上完全一致，而是他们在事 件发生顺序上要达成一致。

  • Lamport 逻辑时钟

    • 消息到达时, 收者时钟若比消息发送时钟小， 则立刻将其时钟调节 到比发送时间至少大一个节拍 (tick);
    • 每两个事件之间时钟必须至少跳动一个节拍。 如某进程快速连发/ 连收消息，其间时钟至少跳动一个节拍;
    • 若在同一个节拍内的两个进程同时发生了两事件， 则在各自发生时 间以小数形式分别附加它们自己的进程号i以示区别。

  • Lamport 算法规则：

    image-20210616185145051

    • 每条消息须携带发送者的时钟以示离开时刻；

    • 消息到达时, 收者时钟若比消息发送时钟小， 则立刻将其时钟调节 到比发送时间至少大一个节拍 (tick);

    • 每两个事件之间时钟必须至少跳动一个节拍。 如某进程快速连发/ 连收消息，其间时钟至少跳动一个节拍;

    • 若在同一个节拍内的两个进程同时发生了两事件， 则在各自发生时 间以小数形式分别附加它们自己的进程号i以示区别。

# 7.2 选举算法

  • 选举算法的作用：许多分布式算法需要一个进程充当协调者， 发起者，排序者或其他特定的角色。通过选举算法，可以确定出一个协调者，方便做出统一的决定
  • 欺负算法：
    • P向高的进程发E 消息
    • 如果没有响应， P选举获胜
    • 如果有进程Q响应,则P结束，Q接 管选举并继续下去。

# 8. 一致性和复制

# 8.1 为什么需要复制

  • 提高性能 ：通过对服务器进行复制，让他们分担工作负荷就可以提高性能
  • 提高系统可靠性 ：维护多个副本，当一个副本被破坏后，文件系统只需转换到另一个数据副本就可以继续运行下去。同时多个副本可以更好的保证数据的正确性
  • 提高系统效率：在使用数据的进程附近防止一份数据的副本，那么访问数据所花费的时间将会减少
  • 增强系统可扩展性

# 8.2 一致性模型

  • 严格一致性：对数据项的读操作返回的值应是 该数据项最近写入的相应值。
  • 顺序一致性：任何执行（对数据存储的一组 操作）的结果是相同的，就好像所有进程的读和写操 作按某种定序执行。要求是所有客户看到的是同一个有 效全局定序
  • 因果一致性：只要求因果关系的写操作在所有的副本上看到按同样的次序被执行，所有进程必须以相同的顺序看到具有潜在因果关系 的写操作。不同机器上可以不同的顺序看到并发写操作。
  • FIFO 一致性：它关心 一个客户的操作定序，取消了对并发操作定序的任何限制，只要求一个 客户的写操作定序在所有副本上是相同的定序（即程序规定的操作次序 ）。

# 8.3 远程主副本协议 （远程写协议） p224

  • 数据项有多个副本，但其中有一个 主副本。写操作都转发到主副本上进行，然后主副本 服务器通知其它副本对数据项进行修改。读操作是在 本地副本上执行。这种方法也称主机备份协议。

# 9. 容错性

# 9.1 基本概念

  • 故障 导致 错误 归于 失败

# 9.2 拜占庭将军问题 p241

  • 问题：有时候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论
  • 处理机个数：一个有K个故障机系统中，最少要有2k＋1个正常处 理机。处理机总数为3k+1才可以解决问题。
  • 结论：在不可信网络上无法解决

# 9.3 可靠通信 p244

# 10. 安全性

# 10.1 安全性基本概念

  • 分布式安全性要解决的两个问题：
    • 通道安全（身份、消息安全） 和授权

# 10.2 密码机制

  • 对称加密系统：使用相同的秘钥进行一个消息的加密和解密
  • 非对称加密

# 10.3 身份认证和授权工作

  • 保证消息的完整性和机密性

    image-20210614194558055

    • 使用哈希散列和消息摘要

      image-20210614194703616

# 10.4 alice 和 bob 通讯，他要做什么

  1. 身份认证，了解对方的身份：
    • 共享秘钥
    • 秘钥分发中心的身份认证
  2. 授权，检查对方是否授予执行请求操作的权限
  3. 保证消息的完整性和机密性：
    • 数字签名
    • 会话秘钥

# 11 任务分配调度 （书上无）

# 11.1 一般表调度算法：

image-20210614195751346

# 11.2 启发式算法：

image-20210614195846066

# 12 分布式文件系统

  • 什么是分布式文件系统：

    • 文件系统是负责组织﹑存储﹑提取﹑命名﹑共享和保护文件, 文件除 了其内容(字节序列)外, 还有其属性, 如文件类型﹑创建时间等。文 件的符号名到内部标识(地址)的翻译由文件系统的目录实现。
    • 文件系统对文件的管理包括对文件本身的管理, 文件属性管理和目录 管理。
    • 存储信息一般以文件形式存储在各种服务器连接的存储介质中, 客户 端通过网络访问服务器中的文件, 这就构成一种分布式文件系统。
    • 分布式文件系统的文件是通过网络传输的并为多个客户所共享, 因此 文件系统的管理功能还包括对客户的身份认证和根据客户权限对文件 执行访问控制

  • 分布式文件系统的三种体系结构

    • 客户－服务器体系结构
      • 远程访问模式
      • 上载/下载模式
    • 集群式体系结构：整个文件分布在多个服务器、对文件进行带区划分以进行并行访问 （GFS）
      • 文件非常大，每个文件包含较小对象
      • 每个GFS文件被划分为多个块，每个块64M
      • 主服务器实际上维护了一个名称空间，从文件名到块的映射
      • 可扩展性和可维护性好。
    • 对称式体系结构

  • 概论

  • 体系结构：分布式要注意的基本问题，基本特征

  • 经常喜欢出个题：谈谈分布式系统要解决什么问题

    • 都是分布式系统需要解决的问题：名字服务、进程在分布式中的特点

  • 分布式通信：

    • 分布式就是单机OS+ 通讯，通讯带来了非常多的问题
    • 通讯的手段是什么，通信带来的问题是什么
    • 最最重要的：协议问题
    • 分布式的理想目标

  • 同步的问题：

    • 逻辑时钟是什么样的

  • 一致性和复制：

    • 为什么出现一致性：复制，为什么复制：扩展性

  • 容错：

    • 完备性
      • 结果的正确性
      • 系统出错

  • 安全性：

    • 是什么，特点是什么，要强调的是什么

  • 文件系统：一个案例

# OS管理

  • 两个主线：

    • 分布式进程
    • 围绕资源管理：资源分配、一致性、安全性

  • 进程通信：

    • RPC、c/s。通信原语和协议

  • 分布式 OS 内容：图

  • 学习方法

    • 需求，提炼问题，分解问题，找出研究点，动态、静态方法，
    • 怎么解决问题：体系结构，np问题：做一点假设限制，提出算法，进行仿真、实现、分析、评测、对比、结论

  • 必考：什么是分布式操作系统 Andrew S. Tanenbaum：一组独立的计算机系统，但是对 用户 看起来像是一个 单一 的计算机

    • 巨大争议和问题
    • 分布式系统组织成中间件的形式，中间件层分布在多台计算机上

  • 基本问题、基本特点

    • 系统由并行执行部件组成
    • 无全局时钟
    • 无全局信息状态
    • 系统部件可能失效
    • 具有容错机制
    • 多副本需要一致性，保证扩展性
    • 单机操作系统与分布式操作系统的区别
      • 围绕基本特性，阐述自己的观点
    • 网络操作系统与分布式操作系统的区别

  • 基本研究方法

    • 必须做到四件事
      • 资源可访问性
      • 透明性、开放性、可扩展性
    • Trade-off Max-min、集中式vs分布式问题
    • 管理系统和数据本身是分布式的：DNS
      • 解决分布式的问题，但本身是分布式

  • 透明性

  • 可扩展性

    • 哪些技术实现可扩展性
    • 三种可扩展性技术是什么
      • 就在书上第二章：隐藏通信时间、分布、

  • 软件体系结构

    • 四种软件体系结构

  • 进程迁移

    • 技术的制高点
    • 有什么办法(处理中间消息)
      • 消息重定位
      • 消息丢失恢复
      • 消息丢失保护
    • 研究点
    • 进程迁移的图：一群节点
    • 进程选举：MIT：LCR 证明体系：代表性的分布式算法，体会算法的执行
      • 分布式中一般要有一个leader，层次结构，但leader具有分布式特征，动态选举，和固定leader不是一个概念
    • 三个方面的难点
      • 迁移过程中进程间通信的问题：给解决问题的思路

  • 负载平衡

    • 进程迁移的三大研究策略
      • 定位策略
        • 自定位、
        • 如何衡量
      • WHEN 什么时候
      • which 选择哪一个任务
        • 远程执行、进程迁移
        • 目标：受益大于开销

  • 通信

    • 强调四种通信：考名词解释，最简单的解释：持久、瞬时
    • 简述：展开描述基本原理
    • 算法策略问题，论述
    • flip 通信结构
      • 特别好的思想：分布式典型结构，给一个进程一个地址（从根本上解决了）、相当于 iP 协议（不作为考试）
    • RPC 重点：原理、参数传递、步骤、编码、同步异步
    • 消息类型：
      • 瞬时通信
      • 持久通信

  • 命名系统

    • 常见：结构化命名
    • 基于属性的命名
    • 无层次命名
    • 知道一些命名方法
    • 什么是递归名称解析，迭代名称解析

  • 同步

    • 重点：逻辑时钟问题
      • 什么是逻辑时钟
      • 核心：lamport 逻辑时钟算法，时钟是怎么走的，他给出了一个算法
    • 欺负算法
      • 写一个进程选举的算法

  • 一致性和复制

    • 为什么需要复制，复制带来的问题
    • 一致性的模型：又强变弱
      • 顺序、因果、fifo
      • 因果一致性
    • 远程主副本协议
      • 读本地、写主副本

  • 共享语义

  • 容错

    • 拜占庭将军问题
      • 几个节点能解决
      • 基本原理：四个节点
      • 结论：在不可信网络上无法解决，能解决的节点个数 3k+1
    • 检查点机制（不考试）（有用）‘
    • 可靠通信

  • 安全性问题

    • 解决：通道安全和授权两个问题
    • 密码机制
      • 对称密码、非对称密码，什么是（解决消息安全问题）
    • 身份认证、授权工作原理
      • 私钥加密，哈希，公钥解密
      • a y要 和 b 通信的话，他要做什么
      • 如何去查询是否有权限

  • 调度算法

    • 一般表调度算法：DAG
    • 启发式算法
      • Sarkar

  • 分布式文件系统

    • 什么是分布式文件系统

  • 基本方法、研究点

  • 面临的问题，具体知识点

  • 都是课堂上的基本点

  • 发挥

  • 没必要打印所有ppt

Edit this page (opens new window)
Last Updated: 6/21/2021, 11:39:11 AM