C# 多线程编程 经典模型 哲学家进餐问题

来源:转载

语言:C#



总起:


今天的哲学家进餐问题是最后多线程模型,讨论的是在有限的资源里线程竞争导致死锁、饥饿等问题。



没有接触过多线程编程的同学,可以先看一下第一章。



哲学家进餐问题:


该问题说的是,有5个哲学家围在一个圆桌前进餐,每个哲学家两旁有两把叉子,一共5把叉子。每个哲学家进行进餐需要拿起左右两把叉子,吃完之后将两把叉子放回供其他人使用。



这个是wiki上的图片:



根据以上的描述,我写了如下的程序:


static Random random = new Random();
public static readonly int MAX_PHILOSOPHERS_NUM = 5;// 最大的哲学家数量
// 同步标记
static List forks = new List();
private static List philosophers = new List();
// 获取左侧的叉子
public static void WaitLeftFork(int number)
{
forks[number].WaitOne();
Console.WriteLine("哲学家" + number + "取得左侧叉子");
}
// 获取右侧的叉子
public static void WaitRightFork(int number)
{
forks[(number+1) % MAX_PHILOSOPHERS_NUM].WaitOne();
Console.WriteLine("哲学家" + number + "取得右侧叉子");
}
// 开始吃饭
public static void Eat(int number)
{
Console.WriteLine("哲学家" + number + "开始进食");
Thread.Sleep(TimeSpan.FromSeconds(random.Next(2, 3)));
}
// 释放两个叉子
public static void ReleaseTwoForks(int number)
{
forks[number].Release();
forks[(number+1)%MAX_PHILOSOPHERS_NUM].Release();
}
// 休息
public static void TakeARest(int number)
{
Console.WriteLine("哲学家" + number + "开始休息");
Thread.Sleep(TimeSpan.FromSeconds(random.Next(1, 5)));
}
static void Main(string[] args)
{
// 创建5把叉子和5个哲学家
for (int i = 0; i < MAX_PHILOSOPHERS_NUM; i++)
{
forks.Add(new Semaphore(1, 1));
philosophers.Add(new Thread(philosopher));
}
for (int i = 0; i < MAX_PHILOSOPHERS_NUM; i++)
{
philosophers[i].Start(i.ToString() as object);
}
}
// 哲学家
static void philosopher(object num)
{
int number = int.Parse(num.ToString());
while (true)
{
WaitLeftFork(number);
WaitRightFork(number);
Eat(number);
ReleaseTwoForks(number);
TakeARest(number);
}
}

这边是没有做同步,每个哲学家按照如下的顺序进行进餐:


1.获取左边的叉子


2.获取右边的叉子


3.进餐


4.释放两个叉子


5.休息



运行一下看看结果:


很明显发生了死锁,所有的哲学家都在第一时间拿取了左侧的叉子,导致所有人都无法拿取右侧的叉子。



资源层级解决方案:


导致问题的原因是只有5把叉子,但有5个哲学家尝试进餐。如果同一时间保证只有4个哲学家尝试进餐,那应该就能解决该问题了。



改进后的代码如下:


static Semaphore eatings = new Semaphore(MAX_PHILOSOPHERS_NUM - 1, MAX_PHILOSOPHERS_NUM - 1);
// 哲学家
static void philosopher2(object num)
{
int number = int.Parse(num.ToString());
while (true)
{
// eatings信号量保证最多只有4个进程尝试进餐
eatings.WaitOne();
WaitLeftFork(number);
WaitRightFork(number);
Eat(number);
ReleaseTwoForks(number);
eatings.Release();
TakeARest(number);
}
}

增加了一个信号量使一次只有4个进程尝试进餐。



结果如下:


可以看到在前4个哲学家开始进餐的时候,最后一个哲学家不会尝试进餐,从而解决了该问题。



中间人解决方案:


如果保证在拿起两把叉子的时候,这两个操作是同步的,那就保证了该哲学家必然能进行进餐,从而不会发生资源竞争的情况。



让我们来试试:


static Mutex middle = new Mutex();
// 哲学家
static void philosopher3(object num)
{
int number = int.Parse(num.ToString());
while (true)
{
// middle互斥体保证同一时间只有一个线程拿两把叉子
middle.WaitOne();
WaitLeftFork(number);
WaitRightFork(number);
middle.ReleaseMutex();
Eat(number);
ReleaseTwoForks(number);
TakeARest(number);
}
}

可以看到结果,一切是多么有序的在进行:


Chandy/Misra解决方案:


国内外网站上查了很久,关于这个解决方案的讨论者寥寥,一些文章仔细看也看不出个所以然来,而课程上最多的解决方案就是第二种。



但是第二种有个比较明显的缺陷,就是没有解决饥饿问题,其他哲学家可能已经等了很久,结果刚吃完饭的人又连续去吃,这样可能导致其他哲学家始终吃不到饭。



而Chandy/Misra的解决方案是未用餐的人优先的,所以没有以上的缺陷。



我简单描述一下该解决方案的内容:叉子有一种叫做dirty的属性,首先初始时所有的叉子都是dirty的。哲学家可以向周围的人请求叉子,这时如果手中的叉子是dirty的,那就可以洗干净之后交给请求者,否者则保留在手中。进餐之后两把叉子都会变为dirty。



因为给了一次对方后叉子洗干净了,所以不会在两个人之间来回传递叉子。



因为网上没有权威的参考,所以这边的代码按照自己的想法进行组织,有不对的地方,希望大家能一起讨论一下。



以下是我自己理解的代码:


//Fork.cs
class Fork
{
private Mutex mutex = new Mutex();
private Philosopher owner;
private bool dirty = true;
// 初始化设置所有者
public void SetOwner(Philosopher owner)
{
this.owner = owner;
}
// 判断当前叉子是否是自己的
public bool IsOwner(Philosopher p)
{
return p == owner;
}
// 锁住当前叉子
public void Lock()
{
mutex.WaitOne();
}
// 解锁当前叉子
public void Unlock()
{
mutex.ReleaseMutex();
}
// 使用完之后叉子变脏
public void DoingUse()
{
dirty = true;
}
// 请求一个叉子
public void request(Philosopher wanter)
{
// 当前叉子不是自己的情况下
while (owner != wanter)
{
Philosopher.mutex.WaitOne();
Lock();
// 如果叉子是脏的,则向对方请求获取叉子
if (dirty)
{
Console.WriteLine("哲学家" + wanter.id + "向" + owner.id + "请求叉子成功");
dirty = false;
owner = wanter;
}
Unlock();
Philosopher.mutex.ReleaseMutex();
}
}
}
// Philosopher.cs
class Philosopher
{
static Random random = new Random();
public static readonly Mutex mutex = new Mutex();
public readonly int id;
private Fork leftFork;
private Fork rightFork;
private Thread thread;
public Philosopher(int id, Fork leftFork, Fork rightFork)
{
this.id = id;
this.leftFork = leftFork;
this.rightFork = rightFork;
thread = new Thread(run);
}
public void Start()
{
thread.Start();
}
void run()
{
while (true)
{
// 尝试请求左叉子
leftFork.request(this);
// 尝试请求右叉子
rightFork.request(this);
// 判断两个叉子是否都到手
mutex.WaitOne();
if (leftFork.IsOwner(this) && rightFork.IsOwner(this))
{
// 两个叉子到手,赶紧锁住
leftFork.Lock();
rightFork.Lock();
mutex.ReleaseMutex();
}
else
{
// 被人拿走了一个叉子,重新开始请求
mutex.ReleaseMutex();
continue;
}
// 吃
Eat(id);
// 释放叉子
leftFork.DoingUse();
rightFork.DoingUse();
leftFork.Unlock();
rightFork.Unlock();
// 休息一下
TakeARest(id);
}
}
// 开始吃饭
public static void Eat(int number)
{
Console.WriteLine("哲学家" + number + "开始进食");
Thread.Sleep(TimeSpan.FromSeconds(random.Next(2, 3)));
}
// 休息
public static void TakeARest(int number)
{
Console.WriteLine("哲学家" + number + "开始休息");
Thread.Sleep(TimeSpan.FromSeconds(random.Next(1, 5)));
}
}
// Program.cs
class Program
{
public static readonly int MAX_PHILOSOPHERS_NUM = 5;// 最大的哲学家数量static void Main(string[] args)
{
List forks = new List();
List philosophers = new List();
// 创建5把叉子
for (int i = 0; i < MAX_PHILOSOPHERS_NUM; i++)
{
forks.Add(new Fork());
}
// 创建5个哲学家
for (int i = 0; i < MAX_PHILOSOPHERS_NUM; i++)
{
philosophers.Add(new Philosopher(i, forks[i], forks[(i+1) % MAX_PHILOSOPHERS_NUM]));
}
// 初始化叉子,这边是关键
for (int i = 0; i < MAX_PHILOSOPHERS_NUM; i++)
{
// 设置叉子的初始主人,如果单纯的将叉子设置为对应id的主人,
// 每个叉子被抢一次后,所有人都拥有一个干净的叉子,那么就又陷入第一个死锁问题了
// 所以这边叉子初始主人初始化为id最低的主人
// 第一个可能的主人
int oneP = i - 1;
while (oneP < 0) oneP += MAX_PHILOSOPHERS_NUM;
oneP = oneP % MAX_PHILOSOPHERS_NUM;
// 第二个可能的主人
int otherP = i;
// 设置id最低的主人
forks[i].SetOwner(philosophers[Math.Min(oneP, otherP)]);
}
// 开始跑
for (int i = 0; i < MAX_PHILOSOPHERS_NUM; i++)
{
philosophers[i].Start();
}
}
}

结果如下:


可以看出能够很好的运行。该方案主要针对没有吃过的哲学家优先进行优化,如果没有必要的话其实第二种方案绝对是足够了,不然为什么课程上教的都是第二种方案(笑)。



总结:


多线程的课程到此结束了,在多线程问题中,很多都是运行1小时、1天、甚至好几天才会出一次的问题,但如果纵容这种错误是一种不专业的行为。



多线程编程始终算作是一种比较难的编程,所以尽量编写单线程,避免不了的情况下请多使用资源复制的方式,如果还是不行就最好参考多线程的这三种模型,大多数多线程的问题都是这三个模型或其变种。



总之完成多线程编程后一定要多多测试,这边给出几个多线程的测试工具:Aspect-Oriented Framework、CGLIB、ASM和ConTest。



如果以后有机会接触多线程的话,会继续研究,现在就到此为止。



分享给朋友:
您可能感兴趣的文章:
随机阅读: