看病排队候诊问题.ppt

《看病排队候诊问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、看病排队候诊问题问题描述医院某科室，有医生m名现有病人n名，先后到达病人病情轻重各有不同（分k级），重的先就诊；病症相同的，先来的先就诊相关理论依据多级反馈队列调度算法调整多线程的共享资源问题排序算法：直接插入排序最简单的排序方法，它的基本操作是将一个记录直接插入已排好序的有序表中，从而得到一个新的、记录数增加1的有序表多级反馈队列调度算法多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。目的是使高优先级的作业得到响应又能使短作业(进程)迅速完成。多级(假设为N级)反馈队列调度

2、算法可以如下原理：1、设有N个队列（Q1,Q2....QN），其中各个队列中的作业(进程)的优先级也是不一样的。2、对于某个特定的队列来说，里面是遵循时间片轮转法。它们的运行时间是通过Q2这个队列所设定的时间片来确定的。3、各个队列的时间片是不一样的。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。多级反馈队列调度算法描述：1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队

3、列中的进程。3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。我们的系统用的方法结合多级反馈队列算法，我们系统根据实际情况，稍作调整。就是队列只有一个，是按照优先级由高到底，分段排队。就是最开头的是优先级最高的病人，同样优先级的在一

4、个分段中（“呈现梯队方式”），由按照其到医院的时间先后来排队。程序功能介绍程序模拟医院排队候诊，主线程一开始生成m个线程，每个线程中有一个医生对象；主线程随机生成病人，并对病人按照病情级别由高到低，时间先后将病人放入共享队列中。m个线程并发执行，如果队列中有病人在等候，就从队列头部取病人。结构介绍病人Patient类，属性有：intpid;//病人id号，从1开始编号inttime_series;//病人到达时间序列intlevel;//病人病情级别，1-4，数值越大，级别越高inttaketime;//病人需要就

5、诊时间，3-10分钟队列Queues类，属性：Patientpatient_Queues[maxN];//病人队列inthead;//头标志，医生读取病人时候，从来这个标志开始读取Inttail;//尾标志，每次有新病人，先暂时将其添加在尾部，再根据其病情优先级，以及时间先后，进行排序数据结构：队列对象中，由一个存放Patient类型的顺序表也就是数组。队列Queues类，主要方法：intinsert_Queues(Patientpatient)//新来病人，先暂时放最后一位intarrange()//每次有新病人

6、到来，都按他的到来时间和病情，排队算法：采用直接插入排序。数据结构与算法分析在队列中设置一个“头”和“尾”标志，从头部读取病人，在尾部写入病人。当有新的病人到来时：设置一个TEMP变量，先将病人暂时放在队列尾部，TEMP指向新病人之前一个病人，TEMP依次向前移动，满足条件新加入的病人病情级别更高（如果是排序的话，时间也要靠前）。终止条件是，新病人病情比TEMP低或者相同而且时间靠后，这时找到新病人的位置，将它放置在TEMP之后。完成写入排序过程。医师Doctor类属性：intpid;//医生编号intfree;/

7、/医生状态，1表示空闲，可以为接诊；0表示忙；-1表示不值班主要方法：inttreatment(Queues&queue)//从队列头部取病人当医生读取病人后，读取其属性中需要治疗的时间，队列“头”部标志向后移动一个位置。我们为了模拟，就采用阻塞的方式，阻塞时间为病人需要治疗的时间。共享队列数据Queuesqueues;//全局病人队列不管医生并发读取病人信息，还是主线程随机生成病人放入队列，多个线程同时请求同一资源时候，构成竞争条件。因此如果不采取有效的控制，那肯定处理结果跟我们预想大相径庭。针对这一情况，我们组

8、内人员展开了充分的讨论，最后采用林志春同学提出的加一个读写锁，来控制并发读写操作。并发处理解决思路：用软件的方法加锁。具体操作如下：设置一全局标志变量boolsign，//对病人队列的读写锁，如果要从队列头部插入病人，或者从队列尾部读取病人，都要先查询sign标志，如果为true,则表示可以取得读写权，相应线程立刻设置sign为false,待读写操作完成后，