Peterson-2互斥算法

Question

经典Peterson-2 algorithm的无争用复杂度是4(因为它对共享寄存器内存执行4次读/写操作)是否存在某种版本的Peterson-2算法，它需要更少的访问共享寄存器内存？很明显，1次访问是impossible.But，那么2次或3次访问呢？谢谢

Answer 1

每个临界区至少需要三个操作:一个write和一个read on条目(用于声明互斥对象的获取并验证其他进程是否尚未获取)，一个write on exit (释放互斥对象)。在进入时，Peterson算法中的进程id写入单写器寄存器interested[id]和多写入器寄存器turn。以将有界寄存器转换为同时包含无界版本号的寄存器为代价，对于两个进程，有两个单写寄存器模拟多写寄存器，每次写1次写，每次读1次读，允许在Peterson算法中合并这两次写操作。