中职课件计算机操作系统课件：项目六 网络和分布式操作系统.pptVIP

⑤ 申请者获得所有邻节点发来的回声消息后，将按上一条规则选定S的方法选中一个资源提供者，然后向它发申请消息。 ⑥ 当一个节点接到申请消息后，就把申请消息登记下，并在可能时将资源分配给它。 ⑦ 使用完毕后通知资源分配者去分配。 三、分布式进程同步 实现分布式进程同步比实现集中式进程同步复杂得多，必须先要解决对不同计算机中发生的事件进行排序的问题，然后设计出性能优越的分布式同步算法。 进程同步的实质是对多个进程在执行顺序上的规定，为此，应对系统中所发生的事件进行排序。1978年，Lamoprt提出了不使用物理时钟，而对分布式系统中所发生的事件进行排序的方法。Lamport指出时钟同步不需要绝对同步。如果两个进程是无关的，那么它们的时钟根本无需同步。此外，对于相交进程来说，通常并没有必要让进程在绝对时间上完全一致，而只要限定它们执行的先后次序一致就行了。 1.事件排序 先定义一个关系称作“先发生”，表达为“a→b”，读作“a在b之前发生”，意思是指系统中所有进程认为事件a先于事件b发生。有两三种情况会产生“先发生”关系。 情况（1）：如果a和b是同一进程中的两个事件，且a发生在b之前，则a→b为真； 情况（2）：如果a是一个进程发送消息事件，b为另一个进程接收该消息事件，则a→b为真； 情况（3）：存在某个事件c，若有a→c并且c→b，则a→b为真。 构造逻辑时钟函数的方法很多，任何满足上述映射关系的正整数函数都可作为逻辑时钟，下面是一种简单的逻辑时钟函数构造方法。定义在某系统集合上的逻辑时钟函数C如下： （1）对任一进程P中的非接收消息事件ej，若ej 是P 的第1个事件，则C(ej)=1，ej是P的第j个事件，而第j-1个事件是ej-1，则 C(ej)=C(ej-1)+1 （2）对于任一进程P中的接收消息事件er，若er是P的笫1个事件，则 C(er)=1+C(es) 定义了逻辑时钟后，可以对一个系统中的所有事件人为地排出一个前后关系，对于由n个进程组成的网络系统，逻辑时钟可用于对由消息传输所组成的事件进行排序。网络中的每个节点i都维护了一个本地计数器Ci，其功能相当于本地时钟。 每次系统发送消息时，它首先把时钟加1，然后发送一个消息，其形式为：(m,Ti,i) 。因为分布式系统中的进程可拥有自己的逻辑时钟（各个节点上的本地时钟），而这些时钟并非是同步运行的。 可能出现这种情况：一个进程发送的消息中所含的逻辑时钟大于接收进程收到此消息时它所具有的逻辑时钟值，由于发送消息事件必定出现在接收消息事件之前，故而需要调整接收进程的逻辑时钟。所以，当接收消息时，接收进程j按照上述规则（2）应把它的时钟设为其当前值和到达的逻辑时钟值这两者取最大值再加1。 Lamport算法利用事件排序方法，对要求访问临界资源的全部事件进行排序，按照FCFS次序，对事件进行处理。 ① （request，Ti，i）：进程Pi发出的访问资源的请求消息。 ② （reply，Tj，j）：进程Pj同意请求进程访问其控制的资源的回答消息。 ③ （release，Tk，k）：占有资源的进程Pk释放资源时给各进程的释放消息。每个消息的内容包括：消息类型、时间戳、节点号。 2.分布式同步算法——Lamport算法简介 该算法用到了3种类型的消息： （1）当进程Pi要求访问临界资源时，它向其他各进程分别提交带有本地时间戳的申请消息（reguest,Ti,i），同时也把此申请消息放入自己的请求队列中的applicationstack[i]位置。 Lamport算法描述如下： （2）当其他节点进程Pj接收到申请消息（reguest,Ti,i）时，它把这条消息放入自己队列的applicationstack[i]位置。若进程Pj在收到（reguest,Ti,i）时，发生了申请事件且还未发完申请消息，那么要在接收进程Pj发完所有申请消息后才发回答消息，否则立即发回答消息。 （3）若满足以下条件，则允许进程Pi进入临界区访问资源： ① Pi申请请求访问资源的消息，即applicationstack中的request是队列中最早的申请请求消息，因为消息在所有节点一致排序，故在任意时刻只有一个进程访问资源。 ② 进程Pi已收到了所有其他进程的回答消息reply，都同意其访问资源，而且响应消息上的时间戳晚于（Ti,i）。此条件表明其他进程要么不访问资源，要么要求访问但其时间戳较晚。 （4）为了释放该资源，Pi从自己的请求队列applicationsta