第6章互斥问题和选举算法第章互斥问题和选举算法第6章互斥问题和选举算法第6章互斥问题和选举算法.ppt

Lamport时钟练习 假设系统中只存在消息发送和接收事件，如图所示，请给出事件a-g的逻辑时钟。 a,b,c,d,e,f,g的时间分别为3,4,7,5,7,5,9 不同进程产生的消息可能具有相同数值的Lamport时间戳。 分布式系统中的互斥 本章主要内容 分布式系统互斥目标 分布式系统互斥基本类型 分布式系统互斥算法类型 分布式系统互斥算法的实现 临界区的调度原则 临界资源：一次只允许一个进程访问的共享资源。 临界区：每个进程中访问临界资源的一段程序代码。 进程进入临界区的调度原则： ①如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。 ②任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。 ③进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。 互斥算法的目标 互斥的主要目标是保证在一个时刻只能有一个进程访问临界区。 在非基于令牌的算法中，所有进程相互通信来决定哪个进程可以执行临界区。 在基于令牌的算法中引入了令牌的概念。令牌代表了一个控制点，它在所有的进程间传递。一个进程拥有令牌时就可以进入临界区。 分布式系统中的互斥算法 在分布式系统中，经常出现多个进程请求访问同一个临界资源的问题，为了协调访问，保证访问的正确性（无死锁，无饥饿现象），需要给出一种有效的互斥算法。 互斥是分布式系统设计的关键问题。 为了保证数据一致性、逻辑一致性及时序一致性，分布式互斥算法必须具有公平、健壮和易于实现的特点。 互斥算法的控制机制 互斥算法的分类 基于令牌的算法：通过令牌拥有权来控制对共享资源的访问。 非基于令牌的算法：通过进程之间的消息交换来协商对共享资源的访问。 互斥算法的适应性 静态互斥算法：算法的行为独立于系统的状态 动态互斥算法：算法的行为依赖于系统的状态 互斥算法应满足的条件 无死锁：当资源可用时进程不应该永远等待 无饥饿现象：每个对资源的访问请求最终都应能得到满足 公平性：进程对资源访问权的获得应是相对公平的。 衡量互斥算法性能的参数 每个请求的消息数 同步延迟：一个进程离开临界区到下一个进程进入该临界区的时间间隔，对共享资源的有效访问间隔。 反应时间：进程发出访问请求到执行完访问操作的时间间隔，主要依赖于系统的负载和调度的合理性。 Lamport互斥算法 ? 为了请求资源，进程Pi发送带时标的消息r给系统中的所有进程，包括它自己； ? 任意进程Pj收到请求资源的消息时，将该消息按时标顺序放在自己的局部请求队列中并发回一个带时戳的应答； ? 进程Pi获得资源访问权的条件是 – 它已收到从其它所有进程发来的应答 – 它的请求r在它的请求队列的顶部 – 它从所有其它进程处收到的消息的时标均比r的时戳大； ? 为了释放资源，进程Pi发送一个带时戳的消息给所有的进程，包括它自己； ? 任意进程Pj收到来自Pi的资源释放消息时，要从自己的局部请求队列中清除所有来自Pi的请求。 一个例子 改进的Lamport互斥算法 Ricart和Agrawala互斥算法 （1）当进程Pi需要占用公区时，向所有进程发送请求，对于K-互斥问题，请求消息包括公区号、进程号和时间戳。 接收进程Pj收到请求消息后，执行如下操作： 如果Pj没有占用该公区也没有申请使用它，则向请求进程发送一个确认消息。 如果Pj正在使用该公区，则不发送确认消息，暂存请求消息。 如果Pj正在申请使用该公区，则比较请求消息时间戳与本身请求时间戳的大小，时间戳小者优先。若Pi的时间戳小，则Pj发送一个确认消息，若Pj的时间戳小，则Pi不发送确认消息。? ?? ?（2）当进程Pi收到所有其他进程发来的响应时，便可访问该资源。? ?（3）当进程释放该资源后，向所有被暂存的请求发送一个确认消息并删除暂存队列。 Ricart和Agrawala互斥算法 要求分布式系统的所有事件是全序的，进程按请求的顺序获得对公区的访问。 进程若未收到所有的应答，就表明有优先级更高的请求存在。 交换的消息数量降至2(n-1)个 Ricart和Agrawala互斥算法的特点 能够实现诸进程对共享资源的互斥访问。 能够保证不发生死锁，因为在进程--资源图中，不会出现环路。 不会出现饥饿现象，因为对共享资源的访问是按照邮戳时间排序的，即按照FCFS原则服务的。 每次对共享资源访问时，只要求发2(N-1)个消息 。 Ricart和Agrawala算法的缺陷 由于不应答被认为是资源被占用，所以如果有某个节点故障，会导致该算法的异常终止。 各进程对资源的使用情况缺乏了解。 Maekawa算法 基本思想 将进程分成多个请求