A New Self-Stabilizing k-out-of-l Exclusion Algorithm on Rings
A New Self-Stabilizing k-out-of-l Exclusion Algorithm on Rings
复制标题
一种新的环自稳定k-out-of-l排除算法
DOI：
10.1007/3-540-45032-7_9
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
V. Villain
中科院分区：
文献类型：
--
作者：
A. Datta;Rachid Hadid;V. Villain
我们提出了一种有效的自稳定解决方案来解决环上的 κ-out-l 排除问题。 κ-out-of-ℓ排除问题是众所周知的互斥问题的推广——共享资源有ℓ个单位，任何进程最多可以请求κ(1≤κ≤ℓ)个单位的共享资源，并且任何资源单位不能同时分配给多个进程。该解决方案基于ℓ代币在环上的循环。请求 NEED(NEED≤κ≤l) 单位资源的处理器只有在收到 NEED 令牌后才能进入临界区。我们提出了一种简单且悲观的方法来处理死锁问题。因此，稳定后，不需要任何机制来检测死锁。此外，在本文中，我们给出了一个新的效率属性的正式定义，称为 (κ,ℓ)-活性，这是任何 κ-out-of-ℓ 排除解决方案的理想属性。此属性允许尽可能多的处理器同时执行其关键部分，而不会违反安全属性。我们推广[6]中引入的技术，以在系统中维护正确数量（ℓ）的代币。除一个称为“根”的处理器外，所有处理器均无需使用任何计数器变量即可对令牌进行计数。该解决方案通过保持合理的稳定时间来改善早期解决方案 [4] 的等待时间。等待时间从 (ℓ+ 2)(n− 1) 减少到 2(n− 1)，其中 是环的大小。稳定时间为 8nin，而不是 4nin [4]。我们的算法的一个很好的特点是，它的空间需求与除根之外的所有处理器无关。
We present an efficient self-stabilizing solution to theκ-outof-ℓexclusion problem on a ring. Theκ-out-of-ℓexclusion problem is a generalization of the well-known mutual exclusion problem — there areℓunits of a shared resource, any process can request at mostκ(1 ≤κ≤ℓ) units of the shared resource, and no resource unit can be allocated to more than one process at one time. This solution is based on the circulation ofℓtokens around the ring. A processor requestingNEED(NEED≤κ≤ℓ) units of the resource can enter the critical section only upon receipt ofNEEDtokens. We propose a simple and pessimistic method to handle the deadlock problem. So, after stabilization, no mechanism is needed for the deadlock detection. Moreover, in this paper, we give a formal definition of a new efficiency property, called (κ,ℓ)-liveness, which is a desirable property of anyκ-out-of-ℓexclusion solution. This property allows as many processors as possible to execute their critical sections simultaneously without violating the safety property. We generalize the technique introduced in [6] to maintain the right number (ℓ) tokens in the system. The tokens are counted without using any counter variable for all processors except one, called the Root. This solution improves the waiting time of an earlier solution [4] by maintaining a reasonable stabilization time. The waiting time is reduced from (ℓ+ 2)(n− 1) to 2(n− 1), wherenis the size of the ring. The stabilization time is 8ninstead of 4nin [4]. One nice characteristic of our algorithm is that its space requirement is independent ofℓfor all processors except the Root.