哲学家进餐问题的死锁问题
\u54f2\u5b66\u5bb6\u5c31\u9910\u95ee\u9898\u3010\u6b7b\u9501\u3011 \u8981\u201cC/C++\u201d\u6765\u5b9e\u73b0\u7684\u81ea\u5df1\u641e\u5b9a\u4e86 \u6765\u6536\u5206\u6570 \u5475\u5475
\u8fd9\u91ccfork\u91cc\u7684taken\u53d8\u91cf\u4e0d\u662fstatic\u7684\uff0c\u6240\u4ee5\u5404\u5b9e\u4f8b\u7684\u8be5\u53d8\u91cf\u662f\u4e92\u76f8\u72ec\u7acb\u7684
\u56e0\u6b64\uff0c\u7b2c\u4e00\u6b21get\uff08\uff09\u4e4b\u540e\u53ea\u662fright\u8fd9\u4e2afork\u7684taken\u88ab\u4fee\u6539\u6210true\u4e86\uff0cleft\u4ecd\u7136\u662ffalse
(1)破坏请求保持条件
利用原子思想完成。即只有拿起两支筷子的哲学家才可以进餐，否则，一支筷子也不拿。
解法一：利用AND机制实现第1位哲学家的活动描述为：
philosopher (int I)
{
while(true)
{
思考;
swait(chopstick[(I+1)]%5，chopstick[I])；
进餐;
Ssignal(chopstick[I]，chopstick[(I+i)%5]);
}
}
解法二：利用记录型信号量机制实现在初始化中增加一个信号量定义：semaphore mutex=1：
第1位哲学家的活动描述：
philosopher (int I) {
while(true)
{
思考;
wait(mutex)；
wait(stiCk[I]);
wait(Stick[(I+1)%5]);
Signal(mutex)；
进餐；
signal(stick[I]);
Signal(Stick[(I+1)%5])； } }
该方法将拿两只筷子的过程作为临界资源，一次只允许一个哲学家进入。
(2)破坏环路等待条件
在上述死锁问题中，哲学家对筷子资源的申请构成了有向环路，如图2所示。
图2环路等待
解法一：奇数号哲学家先拿他左边的筷子，偶数号哲学家先拿他右边的筷子。这样破坏了同方向环路，一个哲学家拿到一只筷子后，就阻止了他邻座的一个哲学家吃饭。按此规定，将是1、2号哲学家竞争I号筷子；3、4号哲学家竞争4号筷子。两种算法描述如下：
1)第1个哲学家的活动：
philosopher (int I)
{
while(true)
{
思考;
If I%2==1 then
wait(Stick[I]);
wait(stick[(I+1)%5]);
进餐;
Signal(stick[I J)；
signal(stick[(I+1)%5])；
e1Se
wait(stick[(I+1)%5])；
wait(stick[I]);
进餐；
signal(stick[(I+1)%5])；
Signal(stick[I]);
} }
(2)第1个哲学家的活动：
philosopher(int I)
{
while(true)
{
思考;
wait(chopstick[I+(I%2)]；
wait(chopstick[(I+(I+1)%2)%5])
进餐;
signal(chopstick[I+(I%2)])；
Signal(chopstick[(I+(I+1)%2)%5])； } }
解法二：至多允许四位哲学家进餐，将最后一个哲学家停止申请资源，断开环路。最终能保证有一位哲学家能进餐，用完释放两只筷子，从而使更多的哲学家能够进餐。增加一个信号量定义semaphore count=4：算法描述第1个哲学家的活动：
philosopher (int I)
{
while(true)
思考；
wait(count)；
wait(chopstiok[I])；
wait(chopstick[I+1]mod 5)；
进餐；
signal(chopstick[I])；
signal(chopstick[I+1]mod 5)
signal(count);
}
}
解法三：哲学家申请资源总是按照资源序号先大后小的顺序，这样0．3号哲学家先右后左，但是4号哲学家
先左后右，改变方向，破坏了环路。算法描述第1个哲学家的活动：
philosopher(int I)
{
while(true)
{
思考；
if I>(I+1)%5 then
wait(chopstick[I]);
wait(chopstick[I+1]mod 5)；
else
wait(chopstick[T+1]mod 5)；
wait(chopstick[T]);/*哲学家总是先取最
大序号的筷子*/
进餐;
signal(chopstick[I])；
signal(chopstick[I+1]mod5)；
} }
绛旓細(1)鐮村潖璇锋眰淇濇寔鏉′欢鍒╃敤鍘熷瓙鎬濇兂瀹屾垚銆傚嵆鍙湁鎷胯捣涓ゆ敮绛峰瓙鐨勫摬瀛﹀鎵嶅彲浠杩涢锛屽惁鍒欙紝涓鏀瀛愪篃涓嶆嬁銆傝В娉曚竴锛氬埄鐢ˋND鏈哄埗瀹炵幇绗1浣鍝插瀹剁殑娲诲姩鎻忚堪涓猴細philosopher (int I){while(true){鎬濊;swait(chopstick[(I+1)]%5锛宑hopstick[I])锛涜繘椁;Ssignal(chopstick[I]锛宑hopstick[(I+i)%5]);}}...
绛旓細鍏堝啓涓涓細閫犳垚姝婚攣鐨勫摬瀛﹀闂銆傚綋鎵鏈夊摬瀛﹀鍚屾椂鍐冲畾杩涢锛屾嬁璧峰乏杈圭瀛愭椂鍊欙紝灏卞彂鐢熶簡姝婚攣銆傝В鍐虫柟妗堜竴锛氱牬鍧忔閿佺殑 寰幆绛夊緟鏉′欢 銆 涓嶅啀鎸夊乏鎵嬭竟鍙虫墜杈归『搴忔嬁璧风瀛愩傞夋嫨涓涓浐瀹氱殑鍏ㄥ眬椤哄簭鑾峰彇锛屾澶勭粰绛峰瓙娣诲姞id锛屾牴鎹甶d浠庡皬鍒板ぇ鑾峰彇锛(涓嶇敤鍏冲績缂栧彿鐨勫叿浣撹鍒欙紝鍙淇濊瘉缂栧彿鏄叏灞鍞竴骞朵笖鏈夊簭...
绛旓細鍥炵瓟锛氳瀹氬湪鎷垮埌宸︿晶鐨勭瀛愬悗,鍏堟鏌ュ彸闈㈢殑绛峰瓙鏄惁鍙敤銆傚鏋滀笉鍙敤,鍒欏厛鏀句笅宸︿晶绛峰瓙, 绛変竴娈垫椂闂村啀閲嶅鏁翠釜杩囩▼銆 鍒嗘瀽:褰撳嚭鐜颁互涓嬫儏褰,鍦ㄦ煇涓涓灛闂,鎵鏈夌殑鍝插瀹閮藉悓鏃跺惎鍔ㄨ繖涓畻娉,鎷胯捣宸︿晶鐨勭 瀛,鑰岀湅鍒板彸渚х瀛愪笉鍙敤,鍙堥兘鏀句笅宸︿晶绛峰瓙,绛変竴浼氬効,鍙堝悓鏃舵嬁璧峰乏渚х瀛愨︹﹀姝 杩欐牱姘歌繙閲嶅涓嬪幓...
绛旓細鍝插瀹鍏椁愰棶棰鍙互鐪嬩綔鏄竴涓粡鍏哥殑杩涚▼鍚屾闂銆傚湪杩欎釜闂涓紝鏈変簲涓摬瀛﹀鍥村潗鍦ㄤ竴寮犲渾妗屼笂锛屽彧鍋氫袱浠朵簨锛屾濊冨拰杩涢銆傛瀛愪腑澶湁涓鐩樻剰澶у埄闈紝鍝插瀹朵箣闂存湁涓鍙弶瀛愩備竴涓摬瀛﹀瑕鍚冮キ鐨璇濓紝浠栭渶瑕佸乏鍙充袱鍙弶瀛愩傞棶棰樺氨鍑虹幇浜嗭紝濡傛灉涓涓摬瀛﹀鍦ㄥ悆楗殑鏃跺欙紝鍏朵粬鐨勫摬瀛﹀鍦ㄧ瓑寰呬粬鍚冨畬锛岃繖灏卞舰...
绛旓細鍐嶈杩欎釜瑙ｅ喅鏂规硶涓殑鎯呭喌锛屽浠绘剰涓涓鏁板彿鍝插瀹A鏉ヨ锛屼粬鍦ㄤ换鎰忎竴涓椂鍒荤殑鐘舵佸彲鍒嗕负浠ヤ笅涓夌锛1. A鍦ㄦ姠宸﹁竟鐨勭瀛怷鏃舵病鏈夋姠鍒帮紝閭ｄ粬灏辨槸涓ゆ墜绌虹┖锛屽洜涓哄鏁板厛鎶㈠乏杈圭殑锛屾垚鍔熶簡鎵嶈兘鎶㈠彸杈圭殑锛屾病鎷跨潃宸﹁竟鐨勭瀛愶紝涔熻偗瀹氭病鎷跨潃鍙宠竟鐨勭瀛愩傝繖涓嶇鍚姝婚攣鍙戠敓鏃朵换浣曚汉閮藉崰鏈1鏍圭瀛愮殑鎯呭喌锛屼笉浼...
绛旓細wait(chopstick[(i+1) mod 5]);,鍐嶆垚鍔熷悗渚垮彲杩涢.杩涢瀹屾瘯,鍙堝厛鏀句笅浠栧乏杈圭殑绛峰瓙,鐒跺悗鏀句笅浠栧彸杈圭殑绛峰瓙.铏界劧,涓婅堪瑙ｆ硶鍙繚璇佷笉浼氭湁涓や釜鐩镐复鐨鍝插瀹鍚屾椂杩涢,浣嗗紩璧姝婚攣鏄彲鑳界殑.鍋囧浜斾釜鍝插瀹跺悓鏃堕ゥ楗胯屽悇鑷嬁璧峰彸杈圭殑绛峰瓙鏃,灏变細浣夸簲涓俊鍙烽噺chopstick鍧囦负0;褰撲粬浠瘯鍥惧幓鎷垮彸杈圭殑绛峰瓙鏃,閮...
绛旓細濡傛灉鍝插瀹鎷垮埌涓鍙瀛愶紝涓嶈兘鍚冮キ锛屾嬁鍒2鍙墠鑳藉悆楗備竴锛岃冭檻绗竴绉嶈嚜鐒舵儏鍐碉細瑙ｆ硶锛氭墍鏈夊摬瀛﹀鎷胯捣涓鍙瀛愶紝鍐嶆嬁鏃佽竟鐨勪竴鍙紝濡傛灉鎷夸笉鍒板氨绛夛紝绛夊埌鍙互鎷夸簡鍐嶆嬁 闂锛氭墍鏈夊摬瀛﹀閮芥嬁璧蜂竴鍙瀛愶紝閭ｅ氨閮藉悆涓嶅埌楗紝灏辨槸姝婚攣 浜岋紝瑙ｅ喅涓婅竟鐨勯棶棰 瑙ｆ硶锛氭瘡涓摬瀛﹀鍏堟嬁宸﹁竟鐨勭瀛愶紝鍐嶆嬁鍙宠竟鐨勭瀛愶紝...
绛旓細c. 褰撲竴涓鍝插瀹杩涚▼璋冪敤put_forks()鏀句笅绛峰瓙鐨勬椂鍊欙紝浼氶氳繃test()娴嬭瘯瀹冪殑閭诲眳锛屽鏋滈偦灞呭浜庨ゥ楗跨姸鎬侊紝涓旇閭诲眳鐨勯偦灞呬笉鍦鍚冮キ鐘舵侊紝鍒欒閭诲眳杩涘叆鍚冮キ鐘舵併傜敱涓婃墍杩,璇ョ畻娉曚笉浼氬嚭鐜姝婚攣锛屽洜涓轰竴涓摬瀛﹀鍙湁鍦ㄤ袱涓偦搴ч兘涓嶅湪杩涢鏃讹紝鎵嶅厑 璁歌浆鎹㈠埌杩涢鐘舵併傝绠楁硶浼氬嚭鐜版煇涓摬瀛﹀閫傜粓鏃犳硶鍚冮キ...
绛旓細1. 鍒╃敤璁板綍鍨嬩俊鍙烽噺瑙ｅ喅鍝插瀹惰繘椁愰棶棰 缁忓垎鏋愬彲鐭ワ紝鏀惧湪妗屽瓙涓婄殑绛峰瓙鏄复鐣岃祫婧愶紝鍦ㄤ竴娈垫椂闂村唴鍙厑璁镐竴浣嶅摬瀛﹀浣跨敤銆備负浜嗗疄鐜板绛峰瓙鐨勪簰鏂ヤ娇鐢紝鍙互鐢ㄤ竴涓俊鍙烽噺琛ㄧず涓鍙瀛愶紝鐢辫繖浜斾釜淇″彿閲忔瀯鎴愪俊鍙烽噺鏁扮粍銆傚叾鎻忚堪濡備笅锛歏ar chopstick: array銆0, 鈥, 4銆 of semaphore;鎵鏈変俊鍙烽噺鍧囪鍒濆鍖栦负1...
绛旓細瑙ｅ喅鍝插瀹惰繘椁愰棶棰涓洪伩鍏姝婚攣,璇炬湰涓婃湁杩欎釜瑙ｅ喅鏂规硶: 鑷冲鍙厑璁告湁鍥涗綅鍝插瀹跺悓鏃跺幓鎷垮乏杈圭殑绛峰瓙,鏈缁堣兘淇濊瘉鑷冲皯鏈変竴浣嶅摬瀛﹀鑳藉杩涢,骞惰兘鐢ㄦ瘯鏃惰兘閲婃斁鍑轰粬鐢ㄨ繃鐨勪袱鍙瀛,浠庤屼娇鏇村鐨勫摬瀛﹀鑳藉杩涢銆 鎯崇敤璁＄畻鏈烘搷浣滅郴缁熶腑鐨勪俊鍙烽噺鏈哄埗鍘昏В鍐冲畠,鍙啓鍑虹浉鍏崇畻娉曞嵆鍙(濡傛灉鑳界敤涓婅鏁板櫒鏇村ソ!)璋㈣阿銆傝寰楃紪绋嬪ソ...
