Ricart and Agrawla 算法
Ricart 等提出的分布式同步算法，同样基于Lamport 的事件排序，但又做了些修改，使每次访问共享变量时，仅需发送 2(N-1)个消息。 下面是对Ricart and Agrawla 算法的描述。
（1）当进程Pi要求访问某个资源时，它发送一个Request(Ti,i)消息给所有其他进程。
（2）当进程Pj收到Request(Ti,i)消息后，执行如下操作：
●若进程Pj正处在临界区中，则推迟向进程Pi发出Reply响应；
●若进程Pj当前并不要求访问临界资源，则立即返回一个有时间邮戳的Reply消息；
●若进程Pj也要求访问临界资源，而在消息Request(Ti,i)中的邮戳时间早于(Tj,i),同样立即返回一个有时间邮戳的 Reply消息；否则，Pj保留 Pi发来的消息Request(Ti,i)，并推迟发出Reply响应。
（3）当进程Pi收到所有其他进程发来的响应时，便可访问该资源。
（4）当进程释放该资源后，仅向所有推迟发来 Reply消息的进程发送Reply消息。
该算法能够获得较好的性能：能够实现诸进程对共享资源的互斥访问；能够保证不发生死锁，因为在进程--资源图中，不会出现环路；不会出现饥饿现象，因为对共享资源的访问是按照邮戳时间排序的，即按照FCFS原则服务的；每次对共享资源访问时，只要求发2(N-1)个消息。下图说明了进程在访问共享资源时的状态转换：
当然这个算法也有一定的问题：第一，每个要求访问共享资源的进程，必须知道所有进程的名字，因此，一旦有新进程进入系统，它就将通知系统中所有进程。第二，如果系统中有一个进程失败，则必然会使发出Request消息的进程无法收到全部响应，因此，系统还应该具备这样的功能，即一旦某个进程失效，系统能将该进程的名字通知其他进程。
[此贴子已经被作者于2004-11-8 22:55:52编辑过]
| 
发表于 2004-11-8 00:00:00
发表于 2004-11-8 00:00:00