解决“哲学家进餐”问题

• 下载 DiningPhilsWPF.zip - 30.2 KB

引言

这是对优秀文章 《哲学家用餐问题》 的一个替代方案。

场景

五位哲学家围坐在一张桌子旁。他们每个人左手边都有一双筷子，面前有一碗吃不完的意大利面。每位哲学家每天都在吃饭或思考。每次吃饭或思考的时间是随机的，但只有当左右两边的筷子都不被其他任何人使用时，哲学家才能吃饭。当哲学家吃完饭开始思考时，两双筷子就会变得可用。桌子上只有五双筷子，所以并非所有哲学家都能同时吃饭。

问题

问题在于设计一个模拟程序，使所有哲学家都能在参与者之间没有任何形式的交流的情况下继续吃饭和思考。由此引申出，没有人可以饿死，也不会发生死锁。

问题分析

虽然场景只提到了哲学家可以处于两个状态，即吃饭或思考，但实际上还有一个第三个状态，那就是思考但正在寻找吃饭机会。换句话说，哲学家是饥饿的。因此，哲学家的活动可以分解为三个连续的阶段：思考、饥饿和吃饭。

解决方案

基于任务的异步模式 通过很少的额外代码，即可为每个哲学家异步执行一系列连续的Tasks。只需要一个Philosopher类和一个Fork类。Philosopher类需要有一个async方法来实现哲学家经历的三个阶段，并利用await任务完成的能力来管理从一个阶段到下一个阶段的过渡。Fork类只需要一个属性IsNotInUse，来指示筷子的可用性。

思考阶段

这个阶段最容易实现。它持续随机的时间。计时是异步进行的，这允许其他哲学家改变他们的状态。它也使得桌子上筷子的可用性可以得到更新。

  while (true)
            {
                Mode=PhilosopherMode.Thinking;
                int thinkingTime = random.Next(Constants.ThinkingMin, Constants.ThinkingMax);
                int eatingTime = random.Next(Constants.EatingMin, Constants.EatingMax);
                //asynchronous wait  until thinking time has passed
                await Task.Delay(TimeSpan.FromSeconds(thinkingTime), ct);
                Mode=PhilosopherMode.Hungry;
                ...

这里发生的是，大部分代码都在单线程 UI 线程上运行。唯一不在这里运行的是对await Task.Delay(TimeSpan.FromSeconds(thinkingTime), ct)的调用。这个调用是一种异步等待。UI 线程被释放，允许它运行由Philosopher类其他实例发布的delegates。延迟期过后，线程会被回调到方法，并运行继续部分，也就是await语句之后的部分。传递给Task.Delay的ct参数是CancellationToken。它允许方法被取消。

饥饿阶段

饥饿阶段包含一个循环，该循环会异步等待一小段时间，然后确定所需的两双Forks是否可用。如果可用，则跳出循环，进入吃饭阶段。

while (!isEating)
                {
                    //monitor the two forks every few millisecs to see if they are in use
                    await Task.Delay(Constants.MonitoringIntervalMilliSecs, ct);
                    //if the forks are not in use, grab them and start eating
                    if (LeftFork.IsNotInUse && RightFork.IsNotInUse)
                    {
                        LeftFork.IsNotInUse = false;
                        RightFork.IsNotInUse = false;
                        isEating = true;
                    }

                }
                 Mode=PhilosopherMode.Eating;

吃饭阶段

  await Task.Delay(TimeSpan.FromSeconds(eatingTime), ct);
                //when the eating time has passed, put down the forks and stop eating
                LeftFork.IsNotInUse = true;
                RightFork.IsNotInUse = true;
                isEating = false;

筷子是共享资源，因此它们状态的任何变化都会反映在相邻哲学家的一双筷子上。在演示应用程序中，吃饭和思考的时间范围设置得大致相同，但实际上，吃饭时间会短得多。当然，除非哲学家是一位美食家。

应用程序

该演示是一个 WPF 应用程序。每位哲学家都用一个棋子形状的图像表示。图像实际上是一个轮廓，放置在一个背景Rectangle上，这样Rectangle的颜色就形成了图像的背景色。在 Xaml 中，每个Rectangle的Fill Brush绑定到 ViewModel 中的Philosopher.Mode属性，而每个筷子图像的Visibility绑定到 ViewModel 中也存在的Fork.IsNotInUse属性。这种安排使得两种类型的图像都可以改变它们的状态。

Philosopher 类

Philosopher类有一个ModeChangedEvent和一个StartAsync方法。StartAsync方法通过在一个while循环中使用一系列有时间限制的awaits来管理思考、饥饿和吃饭的阶段。

 public async Task StartAsync(Random random, CancellationToken ct)
        {
            bool isEating = false;

            // the 'while' loop ends when the cancellation token cancels Task.Delay
            //and a TaskCanceledException is thrown
            while (true)
            {
                Mode=PhilosopherMode.Thinking;
                int thinkingTime = random.Next(Constants.ThinkingMin, Constants.ThinkingMax);
                int eatingTime = random.Next(Constants.EatingMin, Constants.EatingMax);
                //asynchronous wait  until thinking time has passed
                await Task.Delay(TimeSpan.FromSeconds(thinkingTime), ct);
                Mode=PhilosopherMode.Hungry;
                while (!isEating)
                {
                    //monitor the two forks every few millisecs to see if they are in use
                    await Task.Delay(Constants.MonitoringIntervalMilliSecs, ct);
                    //if the forks are not in use, grab them and start eating
                    if (LeftFork.IsNotInUse && RightFork.IsNotInUse)
                    {
                        LeftFork.IsNotInUse = false;
                        RightFork.IsNotInUse = false;
                        isEating = true;
                    }

                }
                 Mode=PhilosopherMode.Eating;
                 await Task.Delay(TimeSpan.FromSeconds(eatingTime), ct);
                //when the eating time has passed, put down the forks and stop eating
                LeftFork.IsNotInUse = true;
                RightFork.IsNotInUse = true;
                isEating = false;
            }
        }

这段代码看起来可以重构。但是async关键字是一个编译器指令，它会导致大量代码在后台生成。考虑到这一点，最好不要将async方法重构为一系列对其他async方法的调用。

ViewModel

ViewModel 的大部分内容涉及定义每个哲学家的PhilosopherMode属性以及每个筷子的IsNotInUse属性。通过调用OnStartAsync方法来启动模拟。此方法首先为所有哲学家调用async Task StartAsync(Random random, CancellationToken ct)方法，并将返回的Tasks存储在List中。然后，它异步等待所有Tasks完成。

     private async void OnStartAsync(object arg)
        {
            IsStarted = true;

            cts = new CancellationTokenSource();
            CancellationToken token = cts.Token;
            Random random = new Random();
            List<Task> philosopherTasks = new List<Task>();
            foreach (Philosopher philosopher in philosophers)
            {
                //start all the async methods and store the returned tasks
                philosopherTasks.Add(philosopher.StartAsync(random, token));
            }

            try
            {
                //asynchronously wait for all the tasks to end
                //the cancellation token will cancel them all
                await Task.WhenAll(philosopherTasks);
            }
            catch (TaskCanceledException)
            {
                IsStarted = false;
                InitialisePhilsMode();
                InitialiseForks();

            }


        }
 

当调用CancellationTokenSource.Cancel方法取消模拟时，模拟结束。

    private void OnCancel(object arg)
        {
            cts.Cancel();
            IsStarted = false;

        }  

结论

基于任务的异步模式是用于事件的排序和管理的强大模式。在使用Timers和BackgroundWorkers以及订阅/取消订阅大量事件之前，值得考虑基于Task的解决方案是否更容易实现且代码更易于维护。