【经典问题】现代操作系统经典问题回顾(哲学家就餐问题C#实现)

 在1971年,著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题,即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后,这个问题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死锁和资源耗尽。

哲学家就餐问题描述:五个哲学家围坐在一张圆桌周围,每个哲学家面前都有一盘通心粉。由于通心粉很光滑,所以需要两把叉子才能夹住,相邻两个盘子之间放有一把叉子。哲学家的生活中有两种交替活动时段:即吃饭和思考(一种抽象而已)。当一个哲学家觉得饿了时,他就试图分两次去取其左边和右边的叉子,每次拿到一把,但不分次序。如果成功地得到了两把叉子,就开始吃饭,吃完后放下叉子继续思考。问题是为哲学家写一段描述其行为的程序,且决不会死锁。

源码:

哲学家就餐问题

// ************************************************************
// 在1971年,著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题,
// 即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后,这个问
// 题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死
// 锁和资源耗尽。
// 
// 哲学家就餐问题描述:五个哲学家围坐在一张圆桌周围,每个哲学家面
// 前都有一盘通心粉。由于通心粉很光滑,所以需要两把叉子才能夹住,
// 相邻两个盘子之间放有一把叉子。哲学家的生活中有两种交替活动时段:
// 即吃饭和思考(一种抽象而已)。当一个哲学家觉得饿了时,他就试图
// 分两次去取其左边和右边的叉子,每次拿到一把,但不分次序。如果成功
// 地得到了两把叉子,就开始吃饭,吃完后放下叉子继续思考。问题是为
// 哲学家写一段描述其行为的程序,且决不会死锁。
// 
// ************************************************************

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace DiningPhilosophers
{
    
/// <summary>
    
/// 哲学家就餐问题是现代操作系统中很经典的问题。
    
/// 一个哲学家的封装。
    
/// </summary>
    public class Philosopher : WorkerThread
    {
        
public const int READY = 0;
        
public const int EATING = 1;
        
public const int THINKING = 2;
        
public const int FINISHED = 3;

        
public Philosopher(object data) : base(data) { }
        
public delegate void StateSwitchedHandler(Object sender, StateSwitchedEventArgs args);
        
public event StateSwitchedHandler StateSwitch;

        
protected override void Run()
        {
            PhilosopherData pd 
= (PhilosopherData)Data;
            Ran
dom rnd 
= new Random(pd.PhilosopherId);
            StateSwitch(
thisnew StateSwitchedEventArgs(READY, pd));
            WaitHandle[] forks 
= new WaitHandle[] { pd.LeftFork, pd.RightFork };

            
while (pd.TotalFood > 0)
            {
                
// 如果两边的哲学家有拿着叉子的,则等待。 
                WaitHandle.WaitAll(forks);
                
// 否则,开始吃通心粉。 
                StateSwitch(thisnew StateSwitchedEventArgs(EATING, pd));
                
// 饭吃掉一部分移除。 
                pd.TotalFood -= pd.AmountToEat;
                Thread.Sleep(rnd.Next(
1001000));// 模拟正在吃通心粉

                StateSwitch(
thisnew StateSwitchedEventArgs(THINKING, pd));
                
// 放下左边和右边的叉子开始思考。 
                pd.RightFork.ReleaseMutex();
                pd.LeftFork.ReleaseMutex();

                Thread.Sleep(rnd.Next(
1001000));// 模拟正在思考
            }

            
// 至此,通信粉都吃完了。 
            StateSwitch(thisnew StateSwitchedEventArgs(FINISHED, pd));
        }
    }

    
/// <summary>
    
/// 哲学家相当于一个线程,这是工作线程抽象类,作为对线程操作的封装。
    
/// </summary>
    public abstract class WorkerThread
    {
        
private object _threadData;
        
private Thread _rawThread;

        
public object Data
        {
            
get { return _threadData; }
            
set { _threadData = value; }
        }

        
public WorkerThread(object data)
        {
            _threadData 
= data;
        }

        
public WorkerThread()
        {
     &
nbsp;      _threadData 
= null;
        }

        
public void Start()
        {
            _rawThread 
= new Thread(new ThreadStart(this.Run));
            _rawThread.Start();
        }

        
protected abstract void Run();
    }

    
/// <summary>
    
/// 封装哲学家数据的结构。
    
/// </summary>
    public struct PhilosopherData
    {
        
public int PhilosopherId;   // 代表哲学家
        public Mutex RightFork;     // 代表右边的叉子
        public Mutex LeftFork;      // 代表左边的叉子
        public int AmountToEat;     // 吃掉的通心粉
        public int TotalFood;       // 盘中的总的通心粉
    }

    
/// <summary>
    
/// 事件:用来通知外部现在哲学家的状态。
    
/// </summary>
    public class StateSwitchedEventArgs : EventArgs
    {
        
public int type;
        
public PhilosopherData philosopherData;
        
public StateSwitchedEventArgs(int t, PhilosopherData pd)
        {
            type 
= t;
            philosopherData 
= pd;
        }
    }
}


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace DiningPhilosophers
{
    
class Program
    {
        
static void Main(string[] args)
    
    {
            
// 准备数据
            Mutex[] forks = new Mutex[N];
            
for (int i = 0; i < N; i++)
            {
                forks[i] 
= new Mutex(false);// 开始时叉子放在桌子上,没有哲学家拿到。
            }

            Philosopher[] p 
= new Philosopher[N];
            
for (int i = 0; i < N; i++)
            {
                PhilosopherData pd;
                pd.PhilosopherId 
= i;
                pd.RightFork 
= forks[(i + 1% N];// 右边的叉子编号
                pd.LeftFork = forks[(i + N  1% N];// 左边的叉子编号
                pd.AmountToEat = N_EAT;// 暂时大锅饭,大家都一样。
                pd.TotalFood = N_TOTAL;// 暂时大锅饭,大家都一样。
                p[i] = new Philosopher(pd);
                p[i].StateSwitch 
+=
                    
new Philosopher.StateSwitchedHandler(
                        (sender, data) 
=>
                        {
                            Console.WriteLine(
Philosopher:{0} IS {1}.,
                                data.philosopherData.PhilosopherId,
                                TranslateState(data.type));
                        });
            }

            
for (int i = 0; i < N; i++)
                p[i].Start();

            Console.ReadKey();
        }

        
private static string TranslateState(int state)
        {
            
switch (state)
            {
                
case Philosopher.READY:
                    
return READY;
                
case Philosopher.EATING:
                    
return EATING;
                
case Philosopher.THINKING:
                    
return THINKING;
                
case Philosopher.FINISHED:
                    
return FINISHED;
                
default:
                    
throw new Exception(*NOT* FOUND.);
            }
        }

        
public const int N = 5;// 哲学家或叉子数目。
        public const int N_EAT = 2;// 每次吃掉的通心粉数量。
        public const int N_TOTAL = 20;// 盘中通心粉总数。
    }
}

 

运行结果:

Philosopher:0 IS READY.
Philosopher:0 IS EATING.
Philosopher:1 IS READY.
Philosopher:1 IS EATING.
Philosopher:3 IS READY.
Philosopher:2 IS READY.
Philosopher:4 IS READY.
Philosopher:1 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:0 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:4 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:1 IS EATING.
Philosopher:1 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:2 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:0 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:1 IS EATING.
Philosopher:1 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:0 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:2 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:0 IS EATING.
Philosopher:0 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:3 IS THINKING.
Philosopher:1 IS EATING.
Philosopher:2 IS EATING.
Philosopher:2 IS THINKING.
Philosopher:0 IS EATING.
Philosopher:1 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:0 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:3 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:1 IS EATING.
Philosopher:1 IS THINKING.
Philosopher:2 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:0 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:1 IS EATING.
Philosopher:1 IS THINKING.
Philosopher:1 IS EATING.
Philosopher:0 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:2 IS THINKING.
Philosopher:1 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:4 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:1 IS EATING.
Philosopher:2 IS THINKING.
Philosopher:0 IS EATING.
Philosopher:0 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:1 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:2 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:0 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:1 IS EATING.
Philosopher:1 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:0 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:0 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:1 IS EATING.
Philosopher:1 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:0 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:0 IS EATING.
Philosopher:1 IS FINISHED.
Philosopher:4 IS THINKING.
Philosopher:0 IS THINKING.
Philosopher:3 IS EATING.Philosopher:2 IS EATING.
Philosopher:4 IS FINISHED.
Philosopher:2 IS THINKING.
Philosopher:3 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:3 IS FINISHED.
Philosopher:2 IS THINKING.
Philosopher:0 IS EATING.
Philosopher:0 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:0 IS FINISHED.
Philosopher:2 IS THINKING.
Philosopher:2 IS FINISHED.

 

源码下载

发表评论

电子邮件地址不会被公开。 必填项已用*标注