分布式操作系统进程同步分析.docxVIP

分布式操作系统进程同步分析 杨利辛 2015022497 2015 10 15在分布式操作系统中，为实现进程的同步，首先要对系统中发生的事件进行排序，还要有良好的分布式同步算法。本文对分布式操作系统中的一些常见算法进行了分析，从而解析才能使进程在分布式操作系统中更加正确有效地协同工作。在分布式系统中，处于不同物理位置的若干进程通过传递消息相互通信，进行协同工作完成同一任务。工作过程中，进程产生了大量的事件和消息，这些事件和消息在时间上的先后顺序对工作正确有效的完成往往是有影响的。由于进程所处的物理位置不同带来的时钟差异 如各地时钟值的差异和时钟运行精度的差异等）和网络传输延时等方面的原因，一个进程所看到的系统内事件和消息的先后顺序很可能与它们的实际顺序是不一致的，这样就带来了问题布式系统都要求系统内的事件和消息的产生时间是精确的，甚至有些系统的任务结果是否正确直接有赖于这些精确的时间值，比如大型分布式数据库系统、电子商务和证券交易等金融业服务系统、分布式文件系统等。在这些系统中，各进程间的同步就必须达到基于物理时钟同步的程度。以证券系统为例，?如果客户机的时钟与服务器的时钟不同步，那么客户按照自己的时钟所提出的服务请求将会被服务器提早或推迟执行，这可能会给客户带来巨大的损失。这时，客户的服务请求是否被顺序公平的响应已失去了意义。?在单机条件下，诸进程运行于同一个处理机和内存环境中，进程通信十分简单。进程之间可以借助于“共享存储器”进行直接通信。而在多机条件下，相互合作的进程可能在不同的处理机上运行，进程间的通信涉及处理机的通信问题。在松散耦合系统中，进程间通信还可能要通过较长的通信信道，甚至网络。因此，在多机条件下，广泛采用间接通信方式，即进程间是通过消息进行通信的。在分布式操作系统中，为了实现进程的同步，首先要对系统中发生的事件进行排序，还要有良好的分布式同步算法。?? 首先，看事件排序问题。在单处理机系统及紧密耦合的多处理机系统中，由于共有一种时钟又共享存储器，确定两个事件的先后次序比较容易。而在分布式系统中，既无共用时钟，又无共享存储器，自然也就难于确定两个事件发生的先后次序了。?这里所说的排序，既包括要确定两个事件的偏序，也要包括所有事件的全序。Lamport于1978年提出的一个算法。该方法建立在以下基础上：?（1）?事件之间存在的偏序；?（2）?为每一个进程设置一个逻辑时钟。?所谓逻辑时钟，是指能为本地启动的所有活动，赋予一个编号的机构，他可以用计数器来实现。在系统中，每一个进程都拥有自己的逻辑时钟?c。在一个系统的逻辑时钟系统，应满足条件：??对于任何活动?a(ini)和?b(inj)，如果?a-b,则相应的逻辑时钟c(i,a)??b(j,b)。其中i，j表示处于不同物理位置的进程。为了满足上述条件，必须遵循以下规则：?第一，根据活动发生的先后，赋予每个活动唯一的逻辑时钟值。?第二，若活动?a?是进程?i?发送的一条消息?m，消息?m中应包含一个时间邮戳?T(m)=c(i,a);当接受进程?j在收?到消息时，如果其逻辑时钟?c(j,b)c(i,a),则应当重置c(j,b)大于或等于c(j,b)。?这里我们对第二个规则作些说明。由于每个进程都拥有自己的逻辑时钟，这些时钟的运行并非同步，因此可能出现这种情况：一个进程?i发送的消息中所含的逻辑时钟c(m)=100，而接收进程?j在收到此消息时的逻辑时钟c(j)=?96，这显然违背了全序的要求，因为发送消息事件?A和接收事件?B?之间存在着A-B?的关系。因而提出了第二项规则，用于实现逻辑时钟的同步。根据这个规则，应该调整进程?j?的时钟，使?c(j)=c(m),例如?c(j)=c(m)+1=101。?? ?其次，看同步算法。在所有的同步算法中，都包含以下四项假设：?（1）?每个分布式系统具有N个节点，每个节点有唯一的编号，可以从1?到?N。每个节点中仅有一个进程提出访问共享资源的请求。?（2）?按序传送信息。即发送进程按序发送消息，接收进程也按相同顺序接收消息。?（3）?每个消息能在有限的时间内被正确地传送到目标进程。?（4）?在处理机间能实现直接通信，即每个进程能把消息直接发送到指定的进程，不需要通过中转处理机。?在同步算法中，相对比较著名的算法还有Ricart?and?Agrawla?算法和Mackawa(Square-Root)算法等。?1、?Ricart?and?Agrawla?算法?Ricart?等提出的分布式同步算法，同样基于Lamport?的事件排序，但又做了些修改，使每次访问共享变量时，仅需发送?2(N-1)个消息。?下面是对Ricart?and?Agrawla?算法的描述。??（1）当进程Pi要求访问某个资源时，它发送一个Request(Ti,i)消