哲学家聚餐问题的计算机仿真.docx

哲学家聚餐仿真实验 2008011464 杨盛哲学家聚餐实验报告2008011464 杨盛一实验内容哲学家用餐问题是由E.J.Dijkstra提出，目的是解决资源的共享与访问控制。五位“哲学家”均匀地围坐在一张圆桌周围，他们一边讨论一边用餐。每人面前有一盘佳肴，每个盘子之间有一把叉子，如下图所示：1）说话（思考）时不吃也不占用叉子；2）吃食物时不说话也不思考；3）等待时不说话也不思考；4）任何一个哲学家在任何时候要么处于说话（思考）状态，要么处于吃食物状态，要么处于等待叉子的状态；允许同时有多人说话（思考）或多人吃食物；5）当某人要吃食物时，必须同时占用靠近他的两把叉子，当不够两把叉子时，他处于等待叉子的状态；叉子一旦被某人占用，就处于被占用状态，直到该人的吃食物的活动完成后才被释放；6）任何一把叉子，均可被靠近它的哲学家占用，也只能被靠近它的哲学家占用，按FIFO规则；7）食物充足，也不考虑吃饱了不想吃的问题。设每一位哲学家每一次说话或思考的时间长度服从正态分布N(5,4)，每次吃食物的时间长度x服从如下形式的分布的随机变量。二实验要求设每一位哲学家每一次说话或思考的时间长度服从正态分布N(5,4)，每次吃食物的时间长度x服从如下形式的分布的随机变量。自行编制程序，仿真时，采用如下随机数： ，种子值为1。初始状态为：哲学家1、3、5为说话或思考状态，2、4吃食物状态。1）可任选采用事件调度法或活动扫描法建模； 2）仿真运行时间长度：24小时，仿真计算在24小时内，每位哲学家的平均说话或思考时间、等待用餐时间和吃食物时间； 3）自行确定仿真运行时间长度，用批均值法，统计估计每位哲学家的稳态平均说话或思考时间、等待用餐时间和吃食物时间，以及相应的置信区间三项目目的1）掌握用事件调度法或活动扫描法进行仿真建模的方法2）掌握离散事件系统仿真方法3）掌握用批均值法进行离散事件系统仿真输出数据分析的方法四仿真程序流程图事件判断五部分程序说明本次仿真采用的是事件调度法。随机数发生器采用题目要求的线性同余法随机数发生器/*线性同余法生成随机数*/double Random_Z()double z=16807*z1;z1=z-B*(int)(z/B);return (z1/B);用舍选法产生符合实验要求的分布/* 舍选法用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;定义哲学家的三种状态enum stateeating,talkingOrThinking,waiting;/枚举状态定义哲学家类型typedef struct Philosopher state NowState;double timeToFinishCurrentFair;/如果在吃，还要多久吃完；如果在思考，还要思考多久；如果在等，等了多少时间(负数表示)double totalTimeOfEating;/吃饭总时间double totalTimeOfThinking;/思考总时间double totalTimeOfWaiting;/等待总时间Philosopher;/哲学家类型哲学家类型包含：当前状态NowState，timeToFinishCurrentFair表示结束当前状态还需要的时间，应当注意的是，当哲学家A处于等叉状态时，何时退出等叉状态取决于相邻的两位哲学家的状态，即当两个哲学家均处于说话状态或等叉但是等待时间不及哲学家A/*为分析设置的记录resi0k是第i位哲学家第k批仿真的吃饭时间resi1k是第i位哲学家第k批仿真的思考时间resi2k是第i位哲学家第k批仿真的等待时间k=0时是相应的总时间resInPercenti0k是第i位哲学家第k批仿真的吃饭时间的百分比resInPercenti1k是第i位哲学家第k批仿真的思考时间的百分比resInPercenti2k是第i位哲学家第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;为了减少批均值法结果分析的计算量，程序里直接给出置信度为0.9的置信区间。输入了预定的仿真批次后，查表确定t分布分位数。for (int i=0;ideltaT)if(activePher=-1) activePher=i;else if(pheri.timeToFinishCurrentFairpheractivePher.timeToFinishCurrentFair)activePher=i;程序用的是事件调度法，定义事件：开始吃饭/开始说话/开始等叉。上面的程序段用于确定下一个发生的事件。这里的deltaT有些讲究。a) 初始化后，deltaT的值为负无穷；b) 某个事件处理完后，若这个哲学家进入了吃饭状态或讲话状态，则deltaT置为负无穷，也就是说，下一轮确定将要发生的事件时，会从所有哲学家中选出timeToFinishCurrentFair最小的一个，包括负数；c) 某个事件处理完后，若这个哲学家想吃饭却没能吃上，即进入了等待状态，则deltaT置为0,也就是说，下一轮确定将要发生的事件时，不可能由处于等待状态的哲学家触发；d) 若被处理的哲学家刚刚为等叉状态，事件处理的结果他仍然是等叉状态，则下一轮确定将要发生的事件时，不可能由他和比他等得久得更久的哲学家来触发。六结果分析进行了40个批次的仿真，单次仿真时长为24小时可见，在实验给定的条件下，各哲学家在24小时的聚餐中，吃饭的时间约为30%，思考的时间占51%，等叉时间为19%。精确的置信区间参见上面截图。七总结和感想这次的仿真跟前面两次有很大的不同。我三次作业都是用的事件调度法，给我的感觉是，单服务台排队系统和库存系统仿真中，