(h, k) -Arbiters for h -out-of- k mutual exclusion problem
(h, k) -Arbiters for h -out-of- k mutual exclusion problem
复制标题
(h, k) - h -out-of- k 互斥问题的仲裁者
DOI：
10.1016/sj.tcs.2003.08.003
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
N. Tajima
中科院分区：
文献类型：
--
作者：
Yoshifumi Manabe;N. Tajima
h- out -k互斥是1-互斥问题的推广，其中共享资源有k个单元，每个进程同时请求h（1≥h≤k）个单元。虽然k-arbiter已被证明是该问题的基于群体的解决方案，但对于1互斥，k-arbiter中的群体比1-coterie中的群体大得多。因此，基于k-arbiter的算法需要大量的消息。本文引入了一个新概念，即每个请求根据其请求的单元数使用不同的quorum。基于这一概念，本文定义了h-out- k互斥的两个(h,k)-仲裁器：一个均匀(h,k)-仲裁器和一个(k+1)-立方(h,k)-仲裁器。每个(h,k)- arbitrator中的仲裁人数不大于对应的k- arbitrator中的仲裁人数；因此，使用(h,k)-仲裁者比使用k-仲裁者更有效。一个统一的(h,k)-仲裁者是对1-互斥多数群体的推广。A (k+1)-cube (h,k)-arbiter是1-互斥方形网格的推广。
h-Out-of-k mutual exclusion is a generalization of the 1-mutual exclusion problem, where there are k units of shared resources and each process requests h (1⩽h⩽k) units at the same time. Though k-arbiter has been shown to be a quorum-based solution to this problem, quorums in k-arbiter are much larger than those in the 1-coterie for 1-mutual exclusion. Thus, the algorithm based on k-arbiter needs many messages. This paper introduces the new notion that each request uses different quorums depending on the number of units of its request. Based on the notion, this paper defines two (h,k)-arbiters for h-out-of-k mutual exclusion: a uniform (h,k)-arbiter and a (k+1)-cube (h,k)-arbiter. The quorums in each (h,k)-arbiter are not larger than the ones in the corresponding k-arbiter; consequently, it is more efficient to use (h,k)-arbiters than the k-arbiters. A uniform (h,k)-arbiter is a generalization of the majority coterie for 1-mutual exclusion. A (k+1)-cube (h,k)-arbiter is a generalization of square grid coterie for 1-mutual exclusion.