A simple local-spin group mutual exclusion algorithm
A simple local-spin group mutual exclusion algorithm
复制标题
DOI：
10.1145/301308.301319
复制
发表时间：
1999-05
期刊：
影响因子：
--
通讯作者：
P. Keane;Mark Moir
中科院分区：
文献类型：
--
作者：
P. Keane;Mark Moir
本文针对 Joung 最近提出的群体互斥问题提出了一种新的解决方案。在此问题中，进程重复请求访问各种“会话”。要求不同的进程不能同时处于不同的会话中，多个进程可以同时处于同一个会话中，并且每个尝试进入会话的进程最终都能够这样做。这个问题是互斥和读者-作者问题的概括。我们的算法及其正确性证明比 Joung 的简单得多。这种简单性是通过建立更具体的互斥问题的已知解决方案来实现的。与 Joung 的算法相比，我们的算法还具有多种优势，具体取决于所使用的互斥算法的选择。这些优点包括在没有争用的情况下在恒定时间内允许进程进入其会话、在高速缓存一致性 (CC) 和非均匀内存访问 (NUMA) 系统中本地旋转，以及 Joung 提出的复杂性度量的改进。
This paper presents a new solution to the group mutual exclusion problem recently posed by Joung. In this problem, processes repeatedly request access to various "sessions." It is required that distinct processes are not in different sessions concurrently, that multiple processes may be in the same session concurrently, and that each process that tries to enter a session is eventually able to do so. This problem is a generalization of the mutual exclusion and readers-writers problems. Our algorithm and its correctness proof are substantially simpler than Joung's. This simplicity is achieved by building upon known solutions to the more specific mutual exclusion problem. Our algorithm also has various advantages over Joung's, depending on the choice of mutual exclusion algorithm used. These advantages include admitting a process to its session in constant time in the absence of contention, spinning locally in Cache Coherent (CC) and Nonuniform Memory Access (NUMA) systems, and improvements in the complexity measures proposed by Joung.