关于哲学家就餐问题的思考与理解以及利用UML来看待该问题
哲学家就餐问题（dinning philosophers problem）：
最开始由荷兰科学家迪杰斯特拉提出的问题 即五台计算机同时试图访问五台共享的磁盘驱动器。
这是一个多线程同步问题，用来解释死锁和资源耗尽。
问题描述：
有五个哲学家每天都只做两件事情，吃饭（eating）和思考（thinking）。
专心的人做任何事情都会十分专注，哲学家作为一名wiser，自然也不例外，吃饭的时候便不会思考，思考的时候便不会吃饭。
餐桌上面有一份意大利面，悲剧的是啥呢，五个人每个人只有一个叉子，但是哲学家吃面喜欢用两个叉子来吃饭，没办法咯。
而且他们只思考从不交谈（废话，笛卡尔什么时侯的人，柏拉图是什么时候的人，这个面和叉子已经跨越了时空 哈哈哈。）
这就很凉凉，很有可能会发生死锁问题，如果五个大佬同时都喊饿啊饿啊，五个人都拿起了叉子，结果悲剧的发现没有一个人能吃到两个叉子的饭，吃饭不用两个叉子又怎么能叫吃饭呢？不吃了！老子等两个叉子出现！大佬气无叉而等待（线程气无资源而计算机死锁）
等时间久了谁都会腰酸背痛啊，而且有损哲学家的风范，有的人选择等一会便放弃，过一会再拿叉子。（聪明的想法，避免了死锁情况的发生，但可能会资源耗尽）
而且！还是会潜藏一种很坑的情况! 真的很坑！如果五个人选择同时放下叉子，几分钟之后又同时拿起了筷子。。。（活锁现象，真是有够作的。）
死锁（deadlock），指当两个以上的运算单元，双方都在等待对方停止运行，以获取系统资源，但是没有一方提前退出时的状况。
死锁发生的四个条件：
1、互斥条件：线程对资源的访问是排他性的，如果一个线程对占用了某资源，那么其他线程必须处于等待状态，直到资源被释放。
2、请求和保持条件：线程T1至少已经保持了一个资源R1占用,但又提出对另一个资源R2请求，而此时，资源R2被其他线程T2占用，于是该线程T1也必须等待，但又对自己保持的资源R1不释放。
3、不剥夺条件：线程已获得的资源，在未使用完之前，不能被其他线程剥夺，只能在使用完以后由自己释放。
4、环路等待条件：在死锁发生时，必然存在一个“进程-资源环形链”，即：{p0,p1,p2,...pn},进程p0（或线程）等待p1占用的资源，p1等待p2占用的资源，pn等待p0占用的资源。（最直观的理解是，p0等待p1占用的资源，而p1而在等待p0占用的资源，于是两个进程就相互等待）
产生死锁的原因主要是：
（1） 因为系统资源不足。
（2） 进程运行推进的顺序不合适。
（3） 资源分配不当等。
如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。
活锁（livelock），活锁与死锁类似，都是需要获取对方的资源而等待导致停滞不前，唯一的区别是，察觉到停滞不前时会先释放自己的资源，过一段时间再进行获取资源的尝试，但如果双方的操作同步了的话，仍然会导致停滞不前的情况。
言归正传
费的聪明人脑壳疼（哎呀妈呀，我脑壳er疼）的三种解法：
其一：服务生解法
大人物们就只管吃顿饭和思考宇宙奥秘吧，我为你们请了一个服务生来专门看着你们，只要饿了就告诉我，我来为你们分配资源， 假设哲学家依次编号为0至4。如果0和2在吃东西，则有四只餐叉在使用中。1坐在0和2之间，所以两只餐叉都无法使用，而3和4之间有一只空余的餐叉。假设这时3或者4想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。不过如果他征求服务生同意，服务生会让他进入等待队列。这样，饿肚子的哲学家就能在有两把叉子空出来时，吃到久等的面条，从而避免了死锁。
问题的关键只有两个中心人物，一个是哲学家，一个是服务生。只要把问题的原因找到这个问题就解决的了。和数学差不太多，根据已知条件推断潜在条件，然后解决问题。
哲学家会做些什么事情呢？
1，思考thinking（哲学家一个叉子都不想要，吃饱了思考人生呢~）
2，饥饿hungry（哲学家想要筷子ci饭，线程想要进入临界区获取资源）
3，吃饭eating（得到两个叉子，获得资源）
哲学家如何才能吃到好吃的意大利面呢？答案只有一个——附近的两个人没有和他抢饭吃。
也就是需 philosopher [ i ] ==EATING
且满足 philosopher（i+4）%5！=eating &&philosopher（i+1）%5！=eating；才能达到需求
具体的伪代码如下
process PHILOSOPHER[i]
while true do
{ THINK;
PICKUP(CHOPSTICK[i], CHOPSTICK[i+1 mod 5]);
EATING;
PUTDOWN(CHOPSTICK[i], CHOPSTICK[i+1 mod 5])
}下面是我写的关于服务生的一个类，可以作为参考（仅作参考啊！大概就是这个意思）
#include<iostream>
typedef int condition;
const int hungry = 0;
const int eating = -1;
const int thinking = 1;
class sever
{
int philosopher[5];
int self[5];
//哲学家准备拿叉子
void Pickup(int i)
{
// 哲学家饿了
philosopher[i] = hungry;
// 只有哲学家检测能取得周围的筷子才能吃饭
test(i);
// 如果不能通过检测，由服务生将其置入等待队列
if (philosopher[i] != eating)
self[i].wait;
}
//哲学家准备放下筷子
void Putdown(int i)
{
// 从新回归思考状态
philosopher[i] = thinking;
}
//测试能否吃到饭
void test(int i)
{
if (philosopher[(i + 1) % 5] != eating&& philosopher[(i + 4) % 5] != eating
&& philosopher[i] == hungry) {
philosopher[i] = eating;
self[i].signal();
}
}
//初始化，全部置为思考状态
void init()
{
for (int i = 0; i <=4; i++) {
philosopher[i] = thinking;
}
}
};其二：资源分级解法法
这个世界上本来是人人平等的，但是有了等级制度，一切都变了模样。
（一切居然都变得有序了 ('''_''') WTF~）
为叉子们整出一个等级制度，并且所有资源的拿取都依照规则执行，并按相反顺序进行释放，而且保证不会有两个无关资源同时被同一项工作所需要。叉子按照定下的规则分成等级为1至5，每个大佬总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。
又是一道伪代码（心虚，毕竟还不是太会多windows线程编程。。。）
class Philosopher {
void philo_class_test(fork_one, fork_two) {
if (fork_one < fork_two) {
sem_firstFork = fork_one;
Sem_secondFork = fork_two;
}
else {
sem_firstFork = fork_two;
sem_secondFork = fork_one;
}
}
};
int main() {
P(fork_one);
P(fork_two);
eating();
V(fork_one);
V(fork_two);
}
其三：
Chandy/Misra解法（脏筷子法）
对每一对竞争一个资源的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初，所有的餐叉都是脏的。当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉，他都发送一个请求。当拥有餐叉的哲学家收到请求时，如果餐叉是干净的，那么他继续留着，否则就擦干净并交出餐叉。当某个哲学家吃东西后，他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉，那他就擦干净并交出餐叉。如此循环往复~
思考：
其实到了现在的这个时候，我觉得哲学家就餐问题问题虽然解法有三种，三十区别都并不是太大，比如最后的这个脏筷子解法，怎么看都很像是信号量来实现，脏筷子的脏等价于设初始值为0，干净的筷子无非就是变成1，没有太大区别。
VS内部<program.h>
C++11的写法代码如下：
//-----------------------------------------------------------------------------
// File: Program.h
//
// Desc: Dining Philosophers sample.
//
// Demonstrates how to use Monitor object (lock) to protect critical section.
//
// Scenario is such that there are 5 philosophers and 5 tools on each side of a philosopher.
// Each philosopher can only take one tool on the left and one on the right.
// One of the philosophers must wait for a tool to become available because whoever grabs
// a tool will hold it until he eats and puts the tool back on the table.
//
// Application of the pattern could be transferring money from account A to account B.
// Important here is to pass locking objects always in the same (increasing) order.
// If the order is mixed you would encounter random deadlocks at runtime.
//
//-----------------------------------------------------------------------------
#include <algorithm>
#include <chrono>
#include <iostream>
#include <memory>
#include <mutex>
#include <string>
#include <thread>
#include <vector>
using std::cout;
using std::endl;
using std::adopt_lock;
using std::for_each;
using std::lock;
using std::mem_fn;
using std::move;
using std::to_string;
using std::exception;
using std::lock_guard;
using std::mutex;
using std::string;
using std::thread;
using std::unique_ptr;
using std::vector;
class Chopstick
{
public:
Chopstick() {};
mutex m;
};
int main()
{
auto eat = [](Chopstick* leftChopstick, Chopstick* rightChopstick,
int philosopherNumber, int leftChopstickNumber, int rightChopstickNumber)
{
if (leftChopstick == rightChopstick)
throw exception("Left and right chopsticks should not be the same!");
lock(leftChopstick->m, rightChopstick->m); // ensures there are no deadlocks
lock_guard<mutex> a(leftChopstick->m, adopt_lock);
string sl = " Philosopher " + to_string(philosopherNumber) +
" picked " + to_string(leftChopstickNumber) + " chopstick.\n";
cout << sl.c_str();
lock_guard<mutex> b(rightChopstick->m, adopt_lock);
string sr = " Philosopher " + to_string(philosopherNumber) +
" picked " + to_string(rightChopstickNumber) + " chopstick.\n";
cout << sr.c_str();
string pe = "Philosopher " + to_string(philosopherNumber) + " eats.\n";
cout << pe;
//std::chrono::milliseconds timeout(500);
//std::this_thread::sleep_for(timeout);
};
static const int numPhilosophers = 6;
// 5 utencils on the left and right of each philosopher. Use them to acquire locks.
vector< unique_ptr<Chopstick> > chopsticks(numPhilosophers);
for (int i = 0; i < numPhilosophers; ++i)
{
auto c1 = unique_ptr<Chopstick>(new Chopstick());
chopsticks[i] = move(c1);
}
// This is where we create philosophers, each of 5 tasks represents one philosopher.
vector<thread> tasks(numPhilosophers);
tasks[0] = thread(eat,
chopsticks[0].get(), // left chopstick: #1
chopsticks[numPhilosophers - 1].get(), // right chopstick: #5
0 + 1, // philosopher number
1,
numPhilosophers
);
for (int i = 1; i < numPhilosophers; ++i)
{
tasks[i] = (thread(eat,
chopsticks[i - 1].get(), // left chopstick
chopsticks[i].get(), // right chopstick
i + 1, // philosopher number
i,
i + 1
)
);
}
// May eat!
for_each(tasks.begin(), tasks.end(), mem_fn(&thread::join));
system("pause");
return 0;
}
/*
Philosopher 1 picked 1 chopstick.
Philosopher 3 picked 2 chopstick.
Philosopher 1 picked 5 chopstick.
Philosopher 3 picked 3 chopstick.
Philosopher 1 eats.
Philosopher 3 eats.
Philosopher 5 picked 4 chopstick.
Philosopher 2 picked 1 chopstick.
Philosopher 2 picked 2 chopstick.
Philosopher 5 picked 5 chopstick.
Philosopher 2 eats.
Philosopher 5 eats.
Philosopher 4 picked 3 chopstick.
Philosopher 4 picked 4 chopstick.
Philosopher 4 eats.
*/最后的最后
关于用uml的方式来思考哲学家就餐问题。
nml主要有三大种类的模型 类模型（class model），状态模型（state model），交互模型（interaction model）
类模型中 有类图，描述了系统内部对象及其关系的静态结构。
状态模型中 有状态图，描述对象随着时间发生变化的哪些方面。
交互模型有 用例图（use case diagram ）：关注系统的功能，强调系统为用户做了什么事情。
顺序图（sequence diagram）显示交互的对象以及发生交互的时间顺序。
活动图（activity diagram）：描述重要的处理步骤。
一共是五大种图。
其实这个问题我一直都很纳闷要如何去用建模的方式来去解决这个问题，虽然是学长留下的任务，但是我还是有些疑问，哲学家就餐问题并不是一个耦合度很高的问题，建模的思想是为了让事物之间的复杂关系变得简单化，清晰化，以一种面向对象的角度来思考问题。可是针对哲学家就餐问题，我并没有感觉到有什么对象来让我面。针对不同的解法，比如第一种解法 我需要去针对谁去进行建模？针对这个问题？哲学家就餐问题？用谁去进行用例？三种解法只有服务生解法可以去以面向对象的思想去考虑哲学家就餐问题，哲学家作为一个类，服务生作为一个类，两个类可以去进行交互，类图可以画出来，哲学家作为用户，“用户问题作为”一个待处理系统这个系统为哲学家这个“用户”做了帮助就餐的事情，于是一个用例图，把这个问题解决了。。。
具体的图以及分析放到下篇文章里面。