Peterson-2互斥算法

Question

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

Answer 1

每个关键部分至少需要三个操作：写入和读取条目（声明获取互斥体并验证其他进程未获取），写入退出（释放互斥）。在进入时，Peterson算法中的进程id写入单写入器寄存器interested[id]和多写入器寄存器turn。以将有界寄存器变成也包含无限版本号的代价为代价，对于两个进程，由两个单写入寄存器模拟多写寄存器寄存器，每写入1次写入，每次读取1次读取，从而允许Peterson算法中的两次写入合并在一起。