Peterson-2 mutual exclusion algorithm

问题:

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

回答1:

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.