Coordination

• 前提条件

• 分布式互斥访问的三种方法

  • Token based approaches：只有一个token，只有拿到token的进程才能访问临界资源，访问完之后释放token

  • Non-Token based approaches：没有token，例如所有人投票，谁能进入临界区

  • Quorum-based approaches：明确有多少人投票，大部分得票的可以进入临界区

• Requirements

• 评价算法的四条准则：cs=critical section（应该very short，因为会block everything）

  • Message complexity：多个进程协调需要发送多少消息

  • Synchronization delay：一个进程离开临界区到下一个进程进入临界区的上下文切换时间

  • Response time：一个进程要求进入临界区到临界区执行完毕

  • System Throughput：处理对临界区请求的速度= 1/（Synchronization delay+平均临界区运行时间）

• 使用一个中心server来分发token：

  • server把要token的进程排成队列（取决于server收到请求的顺序），当有进程执行完临界区，归还token时，把token给队首的哪个进程，

  • 问题：单点问题，并且并发量很小

• 每个进程在释放token之后传给ring中的下一个进程

  • ordering不保证，因为取决于这个ring，并不是请求的顺序

  • progress保证，因为总会传到自己这边，不会发生饥饿

  • safety保证，因为只有一个token，意味着只有一个进程可以访问临界区

• Lamport 算法（non-token based）需要FIFO channel

  • Pi进程向其他所有进程发送自己的request，自己的id，自己的timestamp，并且把自己的request放到自己的request queue中

  • Pj进程在收到这个request之后，把它放到自己的request queue中，并且回应Pi自己的timestamp（我在这个时刻收到了你的request）

  • Pi会进入临界区当且仅当他收到了其他所有进程的timestamp都比自己的请求大

  • Pi的请求在自己的request queue的最上面

  • 当执行完毕之后，Pi会把自己的请求remove掉，并且通知其他的进程

  • 其他的进程收到pi执行完毕的消息后，在自己的request queue中remove掉Pi的请求

  • Example：在timestamp相同的情况下，会把process id 小的排在前面

    • （1，1）标识进程号是1，timestamp是1

  • Correctness： Yes

  • Liveliness： Yes，因为在queue中的请求迟早会被执行

  • Faireness：No，因为在例子中，P2先产生了请求但是晚执行临界区

• Ricart and Agrawala算法

  • Released：不需要进入临界资源

  • Wanted：需要进入临界资源

  • Held：在临界资源中，并保持临界资源

  • 把自己要访问临界区的请求发给别的进程，和自己的timestamp一起

  • 当收到n-1个回复之后，访问临界区

  • 当进程收到别的进程要访问临界区的请求之后

    • 如果自己的状态是held，即在访问临界区，或者自己的状态是wanted，并且自己的timestamp小于请求中的timestamp，那么把这个请求存到队列中，并且不回复

    • 否则马上回复

  • 当进程访问完临界区之后，会通知队列中所有的其他进程

  • example

  • 分析：公平based on logical time

• Maekawa's algorithm：（可能会有死锁）

  • 每个进程维护一个voting set，并且自己也在这个voting set中，因为这样投票给别人之后自己就不能执行了，只有在被投票的那个进程执行完之后，才能投票给别的进程

  • 当进程想要进入临界区的时候，问voting set中的其他进程，当都收到vote之后进入临界区

  • 当其他进程收到request时

    • 如果自己以及为其他进程投过票或者自己在临界区的时候，把request放到队列中，不回复

    • 否则给这个进程vote并把自己的voted设为true

  • 当结束了自己访问临界区，把自己设置为released，并且通知所有的进程自己以及released，在其他进程收到released消息时，会给队列中第一个request投票

  • 建立voting set的方法：

    • 是一个完全二叉树

    • 在树中寻找自己的voting set

      • 如果树中的一个节点同意成为voting set中的一员，那么继续从他的左子树或者右子树中寻找

      • 如果一个节点不同意成为voting set中的一员，那么同时从他的左右子树中开始找，并把最后的结果并起来

      • 所以父节点可以fail，但是叶子节点必须在

    • 当一个进程收到了timestamp比请求队列首进程造早的请求，则询问队列首进程的请求发起人，请求发起人如果已经接受到了所有的投票，那么进入临界区，忽略此询问，否则等新请求先执行，把它放到队列自己之前的位置

    • example：3完成之后会通知5和6，然后4又实现了5和6的互斥访问