彼得森-2互斥算法 [英] Peterson-2 mutual exclusion algorithm
问题描述
的无争用复杂的经典彼得森-2算法是4(因为它执行4的读/写操作,共享寄存器内存)是否有彼得森-2算法,这需要共享寄存器较少的内存访问一些优化版本? 显而易见的是1存取是impossible.But什么约2或3个存取? 谢谢
The contention-free complexity for classic Peterson-2 algorithm is 4 (because it performs 4 read/write operations to shared-registers memory)Is there some verion of Peterson-2 algorithm, which requires less accesses to shared-registers memory ? It is obvious that 1 access is impossible.But what about 2 or 3 accesses? Thank you
推荐答案
需要每个关键部分至少有三种操作:写以及进入读(宣布收购互斥的,验证等过程中没有取得),在退出写(释放互斥)。在入口处,工艺 ID
在彼得森的算法写单写寄存器兴趣[ID]
和多作家寄存器打开
。在把一个有限寄存器到一个还拥有一个无限的版本号,两个过程的成本,有两个单写寄存器,这使得每写1写入和每读1读模拟的多作家寄存器,允许这两个写在Peterson算法的合并。
At least three operations per critical section are needed: a write and a read on entry (to declare acquisition of the mutex and verify that the other process has not acquired), a write on exit (to release the mutex). On entry, process id
in Peterson's algorithm writes the single-writer register interested[id]
and the multi-writer register turn
. At the cost of turning a bounded register into one that also holds an unbounded version number, for two processes, there's a simulation of a multi-writer register by two single-writer registers that makes 1 write per write and 1 read per read, allowing the merger of the two writes in Peterson's algorithm.
这篇关于彼得森-2互斥算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!