资源管理
- 全集中管理方式：所有资源都由一个服务员管理；
- 集中分布管理方式：一个资源由一个服务员管理；
- 全分布管理方式：一个资源是由多个服务员共同管理。
同步
同步点：为了达到合作，各个进程在执行的过程中必须存在若干点，超过这些点时，一个进程在另一个进程执行完某一活动前不能继续执行，这些点称为这两个进程之间的同步点。
分布计算系统中共享资源的两类：一类是各进程可以同时访问的，如中央处理机(允许多个进程交叠使用一个处理机)、只读文件和不允许修改的存放子程序和数据的主存区域等；另一类是不允许多个进程同时访问的，每次只允许一个进程使用，如大多数外部设备(如打印机)、可写的文件以及主存中可修改的区域等。同步机构在互斥控制中的作用是对活动的执行进行排序。
一致状态：一个计算系统应该在所有时间内满足一定的外部规定或约束，如果一个计算系统确实在所有时间内满足了一定的外部规定或约束，这时我们称系统状态是一致的。同步机构的目的就是给进程提供某种手段，使系统保持一致状态。
同步实体：物理时钟、事件计数器、逻辑时钟、循环令牌和顺序器、进程等。
集中式同步机构和分布式同步机构：
在集中式同步机构中，每个生产者每次发动一个操作时均要访问该同步实体。集中式同步实体有一个为所有必须相互同步的进程都知道的名字，任何时候这些进程的任何一个均可访问这一同步实体。执行每个功能如进程调度、数据访问控制等均要经过集中的同步实体进行控制 。
分布式同步机构不存在一个集中的同步实体，执行各种功能时是分散控制的。
优缺点
集中式同步机构最大的缺点是不可靠，一旦出故障就可能造成全局不工作；另外在性能方面也大大下降，因为集中会产生一个瓶颈。但实现简单。 分布式同步机构在可靠性和性能方面优于集中式同步机构，也有很多种，主要有多重物理时钟、多重逻辑时钟、循环令牌等。但实现复杂。
逻辑时钟 a -> b
标量逻辑时钟
每个进程Pi有一个逻辑时钟LCi，LCi被初始化为init(init≥0)并且它是一个非减的整数序列。进程Pi发送的每个报文m都被标上LCi的当前值和进程的标号i，从而形成一个三元组(m,LCi,i)。任何一个逻辑时钟LCi基于以下两条规则更新它的逻辑时钟值：
- 当发生一个事件(一个外部发送或内部事件)之前，我们更新LCi： LCi:=LCi+d (d>0)
- 当收到一个带时间戳的报文(m,LCj,j)时，我们更新LCi： LCi:=max(LCi,LCj)+d (d>0)
向量逻辑时钟
有几个进程就有几维向量，对于第i个进程，进程上的报文向量第i位递增，其他位要么不变，要么和有关联的其他进程的比较取较大值
全局状态
d. P1没发送，但是P2收到了，所以不一致（定义）
c. 不是d情况，所以是一致的，但是有传送中报文
b和a. 一致的 + 非传送中的 = 强一致的
快照算法
- 假如启动算法的进程为P，那么它首先记录自己的局部状态，然后它沿着它的输出通道发送一个标志(marker)，指示接收者应该参与记录一个全局状态的工作。
- 当接收者Q通过它的输入通道C收到一个标志，它将依据不同条件执行以下不同操作：
- 如果Q还没有记录自己的局部状态，它首先记录自己的局部状态，并记录通道C的状态为空报文序列，然后也沿着它自己的输出通道发送一个标志。
- 如果Q已经记录了自己的局部状态，通过通道C收到的标志用来指示Q应该记录通道的状态。通道的状态是Q记录它的局部状态以来到收到这个标志前所收到的报文系列。
- 如果一个进程已经沿它的每个输入通道接收到一个标志，并对每个标志进行了处理，就称它已经完成了它的那部分算法。
- 一个进程的局部状态，连同它的所有输入通道的状态将被发送到这个快照的发起进程。
互斥
互斥算法的主要目标是保证在任一个时刻只能有一个进程访问临界区。一个正确的互斥算法必须避免冲突(死锁和饿死)和保证公平性。为此，算法应满足以下三个条件：
- 已获得资源的进程必须先释放资源之后，另一个进程才能得到资源；
- 不同的请求应该按照这些请求的产生顺序获得满足，请求应该按照某种规则进行排序，例如使用逻辑时钟确定请求的顺序；
- 若获得资源的每个进程最终都释放资源，则每个请求最终都能满足。
集中式互斥算法
一个进程作为协调者
- 临界区无进程 -> 同意请求
- 临界区有进程 -> 不同意请求
- 临界区被释放 -> 同一缓冲区第一个请求
Lamport时间戳互斥算法
- 进程申请资源时向其他进程发送含有当前时间戳的申请报文，并加入到自己的申请队列中
- 其他进程收到申请报文后，把申请报文加入自己的申请队列中，立刻发送带有时间戳的承认报文（除非正在临界区或正发送报文
- 进程用完资源后，先删除申请队列中的报文，再向其他进程发送带时间戳的释放报文
- 其他进程收到释放报文后就把对应申请报文删去
- 当且仅当自己的申请队列中自己的申请报文排最前并且收到了所有的承认报文时，进程获得资源
Ricart-Agrawala互斥算法
收到申请报文后，要是比自己的申请报文晚，就使用完资源后再发回答报文，所以也不需要释放报文
Maekawa互斥算法
进程只向使用该资源的进程组（请求子集）发送请求，对应进程收到释放报文后再给回答报文，释放报文只发给请求子集的进程
要求两两请求子集交集非空
每个进程的请求子集只有同一个进程时，退化为集中式互斥算法
每个进程的请求子集都是全集时，退化成完全分布式的互斥算法
简单令牌环互斥算法
所有进程组成一个逻辑环，令牌在进程间传递，给谁谁就能进临界区，不进就给下一个
问题：
- 令牌丢了咋办，很难检测
- 进程崩溃了咋办，这个倒是容易检测
- 轻负载时出现很多不必要的报文传递
Ricart-Agrawala令牌环互斥算法
每个进程有请求队列，想进临界区就往下发请求报文，令牌存每个进程最后一次持有令牌的时间
用完资源了就把令牌往下传，找到第一个符合条件的进程（？）
基于时间戳的令牌互斥算法
每个进程保持一张进程状态表，记录它所知的进程状态，进程状态包括该进程是否为请求进程，以及得到该状态的时间。令牌是一个特殊的报文，该报文中包含了发送该令牌的进程的进程状态表。
进程想进入临界区，向其他所有进程发送有时间戳的请求报文，自己的进程状态表改为请求态并记录时钟值
收到请求报文后，进程比较发来的时间戳，如果更大（新来的请求），就修改自己状态表中发送进程为请求态，并记录时间
使用完资源的进程将自己的状态表中自己改为非请求态，时钟+1，记录为当前时间，找有没有请求态的进程，发给时间戳最小的
拿到令牌的进程根据令牌修改自己的进程状态表，时间戳和状态，然后进临界区
bully选举算法
从进程集中选出一个进程执行特别的任务。大部分选举算法是基于全局优先级的，就是说给每个进程预先分配一个优先级，选举算法选择一个具有最高优先级的进程作为协调者
P发送选举报文给高于自己优先级的进程，没收到响应报文，P就是协调者，向低于自己优先级进程发通知报文
如果收到响应报文，P停止选举，启动计时器，等不到通知报文就再选
如果收到选举报文，就发响应报文，没启动选举就启动选举
环选举算法
选举报文往下送，失效就再下一个，后继进程也把自己的进程号加进选举报文中
绕环一周回到自己，发送协调者报文往下送，最后进程号大的协调者算协调者
自稳定算法（dijkstra）
一个系统，如果无论它的初始状态是什么，总是能在有限的步骤内达到一个合法的状态，那么它是自稳定的
- 终止性(closure)。P在S的执行下是终止的(closed)，也就是说，一旦P在S中被建立，它就不能被再被证明为假。
- 收敛性(convergence)。从任意全局状态开始，S能保证在有限次状态转换内达到一个满足P的全局状态。
Dijkstra自稳定系统
没看懂