文章目录
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）
c. 如果另外一个进程也要求（claim，宣称？）了资源：
- 协作员直到释放之前都不会回复（reply）
- 维护队列：服务请求按先进先出排列
d. 优点：
- 公平：所有请求按顺序处理
- 易于实现、理解和验证
- 进程不需要知道组成员，只要知道协调者
e. 问题：
- 进程不能辨别是否被一个死协调者阻塞
- 中心化服务器可能成为瓶颈
3. 令牌环算法（token ring）
a. 假定：知晓组内进程
- 某种排序能够被强加到组上（唯一进程ID）
- 软件上构建逻辑环
- 进程和其邻居沟通
b. 算法：
- 初始化：进程 0创建资源R的Token
- Token流通（circulate）于环中：从 P_i 到 P_((i+1)mod N)
- 当进程需要令牌时：
- 检查是否需要进入临界区（cirtial section）
- 如果不，则向邻居发送ring
- 如果是，则访问资源，并持有令牌直到完成
c. 总结：
- 只有一个进程能持有资源，保证了互斥访问
- 良定义顺序（不一定要先请求先服务）
- 饥饿不可能发生
- 缺少FCFS可能在某时候不期望
- 问题：
- 令牌丢失（进程死去）
- 此时令牌会重新生成
- 检测令牌丢失是一个问题（令牌时丢失还是仅仅只是被某个人使用）
- 进程丢失：当不能和邻居联系时会如何？
- 令牌丢失（进程死去）
4. 理查德（Richart）和阿格拉瓦拉（Agrawala）算法
使用可靠的广播和逻辑时钟的分布式算法
a 详情：
- 进程需要进入临界区：
- 撰写（compose）信息包含：
- 标识符（机器ID，进程ID）
- 资源名称
- 时间戳（Lamport算法全排序的的）
- 向组内所有进程发送请求
- 等待直到每个人都给了许可（permission）
- 进入临界区/使用资源
- 撰写（compose）信息包含：
- 当进程接收到请求时
- 如果接受者不感兴趣：向发送者发送一个OK
- 如果接收者在临界区中：不回复，并向队列添加一个请求
- 如果接受者也发送了一个请求：
- 比较时间戳
- 较早的赢了
- 如果接受者输了，发送OK
- 如果接受者赢了，不回复，排序
- 当临界区完成：向所有排队的请求发送OK
b. 特性：
- N点故障
- 会有很多消息传送
- 证明（demonstrates）完全的分布式系统时可能的
5. 兰伯特（Lamport）互斥
每一个进程维护一个请求队列：包含互斥请求
a. 算法：
- 请求临界区
- 进程P_i发送request(i,T_i)到所有节点，其中的时间是兰伯特时间
- 将请求放到自己的队列中
- 当进程P_j接收到请求，它返回一个确认时间戳
- 进入临界区
- $P_i$接受一个消息带着时间戳从其它的每个进程
- $P_i$的请求在队列中有最早的请求
- 释放临界区：
- 将请求从自己的队列中移除
- 发送一个带时间戳的释放消息
- 当进程接收到一个释放消息时：
- 从其队列中移除该进程
- 这可能导致其自己的条目拥有队列中最早的时间戳，允许其访问临界区
b. 不同之处：
- 每个都回应 – 总是没有阻碍
- 进程基于其请求是否是队列中最早的来决定是否执行