分布式系统 – 互斥算法

1. 进程同步

a. 概念:在进程之间协调执行的技术

  • 一个线程可能需要等待另一个
  • 共享资源(例如临界区,critical)可能需要排他性(exclusive)访问

b. 互斥算法的要求

一个互斥算法必须满足以下属性:

  • 安全属性:安全属性指出(state),在任何时刻(at any instant),只有一个进程可以执行临界区
  • 活力(liveness)属性:该属性表明不应该有(the absence of)死锁(deadlock)和饥饿(starvation)
  • 公平性(fairness):意味着每个进程都能够得到执行临界区的公平机会。

c. 中心化系统:取得互斥通过:

  • 硬件 Test & set
  • 信号量 Semaphores
  • 消息 Messages(inter-process)
  • 条件变量 Condition Variables

d. 分布式互斥:

  • 假设就如何识别资源达成共识:
    • 随着请求传递标识符
    • lock(“printer”),lock(table:employees),lock(table:employees;row:15)
    • 每个进程都会唯一的辨识自己
  • 目标:创建一个算法,允许进程获取对网络上可用资源的独占访问

2. 集中式(centralized)算法

a. 概要:

模仿(mimic)单进程系统,每个进程选择一个协调员(coordinator)

b. 过程:

  • 请求(request)资源
  • 等待响应
  • 获得权限(grant)
  • 访问资源
  • 释放资源(release resource)

centralized_alg

c. 如果另外一个进程也要求(claim,宣称?)了资源:

  • 协作员直到释放之前都不会回复(reply)
  • 维护队列:服务请求按先进先出排列

d. 优点:

  • 公平:所有请求按顺序处理
  • 易于实现、理解和验证
  • 进程不需要知道组成员,只要知道协调者

e. 问题:

  • 进程不能辨别是否被一个死协调者阻塞
  • 中心化服务器可能成为瓶颈

3. 令牌环算法(token ring)

a. 假定:知晓组内进程

  • 某种排序能够被强加到组上(唯一进程ID)
  • 软件上构建逻辑环
  • 进程和其邻居沟通

b. 算法:

  • 初始化:进程 0创建资源R的Token
  • Token流通(circulate)于环中:从 P_iP_((i+1)mod N)
  • 当进程需要令牌时:
    • 检查是否需要进入临界区(cirtial section)
    • 如果不,则向邻居发送ring
    • 如果是,则访问资源,并持有令牌直到完成

c. 总结:

  • 只有一个进程能持有资源,保证了互斥访问
  • 良定义顺序(不一定要先请求先服务)
    • 饥饿不可能发生
    • 缺少FCFS可能在某时候不期望
  • 问题:
    • 令牌丢失(进程死去)
      • 此时令牌会重新生成
      • 检测令牌丢失是一个问题(令牌时丢失还是仅仅只是被某个人使用)
    • 进程丢失:当不能和邻居联系时会如何?

4. 理查德(Richart)和阿格拉瓦拉(Agrawala)算法

使用可靠的广播和逻辑时钟的分布式算法

a 详情:

  1. 进程需要进入临界区:
    1. 撰写(compose)信息包含:
      • 标识符(机器ID,进程ID)
      • 资源名称
      • 时间戳(Lamport算法全排序的的)
    2. 向组内所有进程发送请求
    3. 等待直到每个人都给了许可(permission)
    4. 进入临界区/使用资源
  2. 当进程接收到请求时
    1. 如果接受者不感兴趣:向发送者发送一个OK
    2. 如果接收者在临界区中:不回复,并向队列添加一个请求
    3. 如果接受者也发送了一个请求:
      • 比较时间戳
      • 较早的赢了
      • 如果接受者输了,发送OK
      • 如果接受者赢了,不回复,排序
    4. 当临界区完成:向所有排队的请求发送OK

ra_alg

b. 特性:

  • N点故障
  • 会有很多消息传送
  • 证明(demonstrates)完全的分布式系统时可能的

5. 兰伯特(Lamport)互斥

每一个进程维护一个请求队列:包含互斥请求

a. 算法:

  • 请求临界区
    • 进程P_i发送request(i,T_i)到所有节点,其中的时间是兰伯特时间
    • 将请求放到自己的队列中
    • 当进程P_j接收到请求,它返回一个确认时间戳
  • 进入临界区
    • $P_i$接受一个消息带着时间戳从其它的每个进程
    • $P_i$的请求在队列中有最早的请求
  • 释放临界区:
    • 将请求从自己的队列中移除
    • 发送一个带时间戳的释放消息
    • 当进程接收到一个释放消息时:
      • 从其队列中移除该进程
      • 这可能导致其自己的条目拥有队列中最早的时间戳,允许其访问临界区

b. 不同之处:

  • 每个都回应 – 总是没有阻碍
  • 进程基于其请求是否是队列中最早的来决定是否执行
Tagged with:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据