为什么彼得森的锁在这个测试中失败了?
本文关键字:测试 失败 为什么 | 更新日期: 2023-09-27 18:05:41
我正在试验不需要原子指令的锁。彼得森的算法似乎是最简单的起点。然而,经过足够多的迭代,就会出现问题。
代码:public class Program
{
private static volatile int _i = 0;
public static void Main(string[] args)
{
for (int i = 0; i < 1000; i++)
{
RunTest();
}
Console.Read();
}
private static void RunTest()
{
_i = 0;
var lockType = new PetersonLock();
var t1 = new Thread(() => Inc(0, lockType));
var t2 = new Thread(() => Inc(1, lockType));
t1.Start();
t2.Start();
t1.Join();
t2.Join();
Console.WriteLine(_i);
}
private static void Inc(int pid, ILock lockType)
{
try
{
for (int i = 0; i < 1000000; i++)
{
lockType.Request(pid);
_i++;
lockType.Release(pid);
}
}
catch (Exception ex)
{
Console.WriteLine(ex);
}
}
}
public interface ILock
{
void Request(int pid);
void Release(int pid);
}
public class NoLock : ILock
{
public void Request(int pid) { }
public void Release(int pid) { }
}
public class StandardLock : ILock
{
private object _sync = new object();
public void Request(int pid)
{
Monitor.Enter(_sync);
}
public void Release(int pid)
{
Monitor.Exit(_sync);
}
}
public class PetersonLock : ILock
{
private volatile bool[] _wantsCs = new bool[2];
private volatile int _turn;
public void Request(int pid)
{
int j = pid == 1 ? 0 : 1;
_wantsCs[pid] = true;
_turn = j;
while (_wantsCs[j] && _turn == j)
{
Thread.Sleep(0);
}
}
public void Release(int pid)
{
_wantsCs[pid] = false;
}
}
当我运行这个时,我总是得到<2000000年。这是怎么呢
这里的问题是这两句话:
_wantsCs[pid] = true;
_turn = j;
. net和c#的内存模型允许这两次写操作被重新排序。
要强制它们不被重新排序,在它们之间添加一个内存屏障:
_wantsCs[pid] = true;
Thread.MemoryBarrier();
_turn = j;
,您每次都会得到预期的输出。
请注意,这个问题在维基百科页面彼得森算法的注释部分中有描述(此处缩短,请阅读文章以获取完整注释):
指出
…大多数现代cpu重新排序内存访问以提高执行效率(请参阅内存排序以了解允许的重新排序类型)。这样的处理器总是在内存访问流中提供一些强制排序的方法,通常是通过内存屏障指令。在对内存访问进行重排序的处理器上实现Peterson's和相关算法通常需要使用这些操作来正确工作,以防止顺序操作以错误的顺序发生
(我强调)