彼得森-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屋！