哲學(xué)家聚餐問題的計算機仿真.docx

哲學(xué)家聚餐仿真實驗 2008011464 楊盛哲學(xué)家聚餐實驗報告2008011464 楊盛一實驗內(nèi)容哲學(xué)家用餐問題是由E.J.Dijkstra提出，目的是解決資源的共享與訪問控制。五位“哲學(xué)家”均勻地圍坐在一張圓桌周圍，他們一邊討論一邊用餐。每人面前有一盤佳肴，每個盤子之間有一把叉子，如下圖所示：1）說話（思考）時不吃也不占用叉子；2）吃食物時不說話也不思考；3）等待時不說話也不思考；4）任何一個哲學(xué)家在任何時候要么處于說話（思考）狀態(tài)，要么處于吃食物狀態(tài)，要么處于等待叉子的狀態(tài)；允許同時有多人說話（思考）或多人吃食物；5）當(dāng)某人要吃食物時，必須同時占用靠近他的兩把叉子，當(dāng)不夠兩把叉子時，他處于等待叉子的狀態(tài)；叉子一旦被某人占用，就處于被占用狀態(tài)，直到該人的吃食物的活動完成后才被釋放；6）任何一把叉子，均可被靠近它的哲學(xué)家占用，也只能被靠近它的哲學(xué)家占用，按FIFO規(guī)則；7）食物充足，也不考慮吃飽了不想吃的問題。設(shè)每一位哲學(xué)家每一次說話或思考的時間長度服從正態(tài)分布N(5,4)，每次吃食物的時間長度x服從如下形式的分布的隨機變量。二實驗要求設(shè)每一位哲學(xué)家每一次說話或思考的時間長度服從正態(tài)分布N(5,4)，每次吃食物的時間長度x服從如下形式的分布的隨機變量。自行編制程序，仿真時，采用如下隨機數(shù)： ，種子值為1。初始狀態(tài)為：哲學(xué)家1、3、5為說話或思考狀態(tài)，2、4吃食物狀態(tài)。1）可任選采用事件調(diào)度法或活動掃描法建模； 2）仿真運行時間長度：24小時，仿真計算在24小時內(nèi)，每位哲學(xué)家的平均說話或思考時間、等待用餐時間和吃食物時間； 3）自行確定仿真運行時間長度，用批均值法，統(tǒng)計估計每位哲學(xué)家的穩(wěn)態(tài)平均說話或思考時間、等待用餐時間和吃食物時間，以及相應(yīng)的置信區(qū)間三項目目的1）掌握用事件調(diào)度法或活動掃描法進(jìn)行仿真建模的方法2）掌握離散事件系統(tǒng)仿真方法3）掌握用批均值法進(jìn)行離散事件系統(tǒng)仿真輸出數(shù)據(jù)分析的方法四仿真程序流程圖事件判斷五部分程序說明本次仿真采用的是事件調(diào)度法。隨機數(shù)發(fā)生器采用題目要求的線性同余法隨機數(shù)發(fā)生器/*線性同余法生成隨機數(shù)*/double Random_Z()double z=16807*z1;z1=z-B*(int)(z/B);return (z1/B);用舍選法產(chǎn)生符合實驗要求的分布/* 舍選法用U(0,1)生成F(x) */double Random_F()double u1,u2;while(1)u2=2+Random_Z()*2;/2-4均勻分布u1=Random_Z()*2/3;/0-2/3均勻分布if(u2=2.5)if(u1=(u2-2)*(2.0/3)+(1.0/3) return u2;elseif(u1=(2.0/3-(u2-2.5)*(2.0/9) return u2;/*舍選法用U(0,1)生成N(u,th2) */double Random_N(double u,double th)if (s=1) s=0;return N;double v1,v2,w;while(1)v1=Random_Z()*2-1;v2=Random_Z()*2-1;w=v1*v1+v2*v2;if(w=1)s=1;N=(v2*sqrt(-2*log(w)/w)*th+u;return (v1*sqrt(-2*log(w)/w)*th+u;定義哲學(xué)家的三種狀態(tài)enum stateeating,talkingOrThinking,waiting;/枚舉狀態(tài)定義哲學(xué)家類型typedef struct Philosopher state NowState;double timeToFinishCurrentFair;/如果在吃，還要多久吃完；如果在思考，還要思考多久；如果在等，等了多少時間(負(fù)數(shù)表示)double totalTimeOfEating;/吃飯總時間double totalTimeOfThinking;/思考總時間double totalTimeOfWaiting;/等待總時間Philosopher;/哲學(xué)家類型哲學(xué)家類型包含：當(dāng)前狀態(tài)NowState，timeToFinishCurrentFair表示結(jié)束當(dāng)前狀態(tài)還需要的時間，應(yīng)當(dāng)注意的是，當(dāng)哲學(xué)家A處于等叉狀態(tài)時，何時退出等叉狀態(tài)取決于相鄰的兩位哲學(xué)家的狀態(tài)，即當(dāng)兩個哲學(xué)家均處于說話狀態(tài)或等叉但是等待時間不及哲學(xué)家A/*為分析設(shè)置的記錄resi0k是第i位哲學(xué)家第k批仿真的吃飯時間resi1k是第i位哲學(xué)家第k批仿真的思考時間resi2k是第i位哲學(xué)家第k批仿真的等待時間k=0時是相應(yīng)的總時間resInPercenti0k是第i位哲學(xué)家第k批仿真的吃飯時間的百分比resInPercenti1k是第i位哲學(xué)家第k批仿真的思考時間的百分比resInPercenti2k是第i位哲學(xué)家第k批仿真的等待時間的百分比*/double res63100=0;double resInPercent63100=0;switch(desireTurns)case 10:tp=1.8331;break;case 20:tp=1.7291;case 30:tp=1.6991;case 40:tp=1.6849;default:tp=6.3138;為了減少批均值法結(jié)果分析的計算量，程序里直接給出置信度為0.9的置信區(qū)間。輸入了預(yù)定的仿真批次后，查表確定t分布分位數(shù)。for (int i=0;ideltaT)if(activePher=-1) activePher=i;else if(pheri.timeToFinishCurrentFairpheractivePher.timeToFinishCurrentFair)activePher=i;程序用的是事件調(diào)度法，定義事件：開始吃飯/開始說話/開始等叉。上面的程序段用于確定下一個發(fā)生的事件。這里的deltaT有些講究。a) 初始化后，deltaT的值為負(fù)無窮；b) 某個事件處理完后，若這個哲學(xué)家進(jìn)入了吃飯狀態(tài)或講話狀態(tài)，則deltaT置為負(fù)無窮，也就是說，下一輪確定將要發(fā)生的事件時，會從所有哲學(xué)家中選出timeToFinishCurrentFair最小的一個，包括負(fù)數(shù)；c) 某個事件處理完后，若這個哲學(xué)家想吃飯卻沒能吃上，即進(jìn)入了等待狀態(tài)，則deltaT置為0,也就是說，下一輪確定將要發(fā)生的事件時，不可能由處于等待狀態(tài)的哲學(xué)家觸發(fā)；d) 若被處理的哲學(xué)家剛剛為等叉狀態(tài)，事件處理的結(jié)果他仍然是等叉狀態(tài)，則下一輪確定將要發(fā)生的事件時，不可能由他和比他等得久得更久的哲學(xué)家來觸發(fā)。六結(jié)果分析進(jìn)行了40個批次的仿真，單次仿真時長為24小時可見，在實驗給定的條件下，各哲學(xué)家在24小時的聚餐中，吃飯的時間約為30%，思考的時間占51%，等叉時間為19%。精確的置信區(qū)間參見上面截圖。七總結(jié)和感想這次的仿真跟前面兩次有很大的不同。我三次作業(yè)都是用的事件調(diào)度法，給我的感覺是，單服務(wù)臺排隊系統(tǒng)和庫存系統(tǒng)仿真中，