当前位置:和仁网 >休闲 > 正文

lamport分布式互斥算法和Ricart-Agrawala 算法的区别是什么

2020-11-18 19

我来回答一下吧在这些参考资料还真不多

Lamport 算法

请求临界区时:有其他进程发送 $REQUEST(t_i, i)$,将这个请求保存到本地请求队列里;

如果收到了一个请求,那么按时间戳将请求加入到本地请求队列,然后返回一个 $REPLY(t_j)$,也是当前的时间戳;

了请求以后进程就等啊等啊,直到

  • 收到了所有其他进程返回的 $REPLY(t*)$,期望是对本地的 $t_i$进行相应,所以要求 $t* > t_i$,也就是说,是我发了消息后,对方才回复的消息;

  • 并且本地的 $t_i$ 在本地队列的队头

    那么就执行,可以进入临界区

    退出临界区时,从本地队列里删掉自己的请求,带着时间戳发一个广播,通知所有队列都可以删掉$i$ 请求了;

因此Lamport算法的消息开销为3(N-1),分别是对除自己以外的其他进程进行资源请求、接收通知、和通知释放


Ricart-Agrawala 算法

主要就是来优化上一个算法里的消息通信机制的

上一个算法的冗余主要有:

  • 1.没有申请临界区资源的进程是没必要知道你是否进行了 $RELEASE$ 操作的;

    1.1 同样,早早的回复REPLY也是没用的,回复了也进不去

    1.2 所以,不如等到RELEASE的时候再REPLY

  • 2.同样,它们也是没必要知道你是否要申请临界区资源的,这和它没有任何关系;

    这个算法就针对1进行了优化

这个算法去掉了 $RELEASE$ 消息,$RELEASE$ 不需要发送了;

为什么呢?根据我们前边的分析,将$RELEASE$发送给那些未申请临界区的进程是没有必要的,因此我们不想给他们发送,而申请临界区的进程就是给我们发送了$REQUEST$ 消息的进程。因此我们只需要给我们需要$REPLY$的那些进程发送$RELEASE$就可以了。

继续分析一下,其实马上回复$REPLY$也是没必要的,反正回复了它也不能马上进行访问,不如等到它可以访问的时候再回复他(对请求方进程来说没差别,对吧)。

基于这样的想法,我们把 $REPLY$ 延迟到释放资源时再发送。我们可以发现,但凡是我们发送 $REPLY$ 时,都没有在继续占用临界区资源了,也就是说,将这两个消息合并成了一个消息,减少了 1/3 的消息复杂度。

因此,算法消息开销减少为2(N-1)

本周热门
本月热门