algorithm - Peterson-2 互斥算法

Question

经典Peterson-2 算法的无争用复杂度为4（因为它对共享寄存器内存执行 4 次读/写操作）是否存在 Peterson-2 算法的某个版本，它需要较少访问共享寄存器内存？很明显，1 次访问是不可能的。但是 2 次或 3 次访问呢？谢谢

Answer 1

每个临界区至少需要三个操作：入口时写入和读取（声明获取互斥锁并验证其他进程尚未获取），退出时写入（释放互斥锁）。在进入时，id彼得森算法中的进程写入单写寄存器interested[id]和多写寄存器turn。以将有界寄存器转换为还保存无界版本号的寄存器为代价，对于两个进程，有一个由两个单写寄存器模拟的多写寄存器，每次写入 1 次写入，每次读取 1 次读取，允许两者的合并写入彼得森算法。