看病排隊候診問題.ppt

《看病排隊候診問題.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、看病排隊候診問題問題描述醫(yī)院某科室，有醫(yī)生m名現有病人n名，先后到達病人病情輕重各有不同（分k級），重的先就診；病癥相同的，先來的先就診相關理論依據多級反饋隊列調度算法調整多線程的共享資源問題排序算法：直接插入排序最簡單的排序方法，它的基本操作是將一個記錄直接插入已排好序的有序表中，從而得到一個新的、記錄數增加1的有序表多級反饋隊列調度算法多級反饋隊列調度算法是一種CPU處理機調度算法，UNIX操作系統采取的便是這種調度算法。目的是使高優(yōu)先級的作業(yè)得到響應又能使短作業(yè)(進程)迅速完成。多級(假設為N級)反饋隊列調度

2、算法可以如下原理：1、設有N個隊列（Q1,Q2....QN），其中各個隊列中的作業(yè)(進程)的優(yōu)先級也是不一樣的。2、對于某個特定的隊列來說，里面是遵循時間片輪轉法。它們的運行時間是通過Q2這個隊列所設定的時間片來確定的。3、各個隊列的時間片是不一樣的。各個隊列的時間片是隨著優(yōu)先級的增加而減少的，也就是說，優(yōu)先級越高的隊列中它的時間片就越短。多級反饋隊列調度算法描述：1、進程在進入待調度的隊列等待時，首先進入優(yōu)先級最高的Q1等待。2、首先調度優(yōu)先級高的隊列中的進程。若高優(yōu)先級中隊列中已沒有調度的進程，則調度次優(yōu)先級隊

3、列中的進程。3、對于同一個隊列中的各個進程，按照時間片輪轉法調度。比如Q1隊列的時間片為N，那么Q1中的作業(yè)在經歷了N個時間片后若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完后作業(yè)還不能完成，一直進入下一級隊列，直至完成。4、在低優(yōu)先級的隊列中的進程在運行時，又有新到達的作業(yè)，那么在運行完這個時間片后，CPU馬上分配給新到達的作業(yè)（搶占式）。我們的系統用的方法結合多級反饋隊列算法，我們系統根據實際情況，稍作調整。就是隊列只有一個，是按照優(yōu)先級由高到底，分段排隊。就是最開頭的是優(yōu)先級最高的病人，同樣優(yōu)先級的在一

4、個分段中（“呈現梯隊方式”），由按照其到醫(yī)院的時間先后來排隊。程序功能介紹程序模擬醫(yī)院排隊候診，主線程一開始生成m個線程，每個線程中有一個醫(yī)生對象；主線程隨機生成病人，并對病人按照病情級別由高到低，時間先后將病人放入共享隊列中。m個線程并發(fā)執(zhí)行，如果隊列中有病人在等候，就從隊列頭部取病人。結構介紹病人Patient類，屬性有：intpid;//病人id號，從1開始編號inttime_series;//病人到達時間序列intlevel;//病人病情級別，1-4，數值越大，級別越高inttaketime;//病人需要就

5、診時間，3-10分鐘隊列Queues類，屬性：Patientpatient_Queues[maxN];//病人隊列inthead;//頭標志，醫(yī)生讀取病人時候，從來這個標志開始讀取Inttail;//尾標志，每次有新病人，先暫時將其添加在尾部，再根據其病情優(yōu)先級，以及時間先后，進行排序數據結構：隊列對象中，由一個存放Patient類型的順序表也就是數組。隊列Queues類，主要方法：intinsert_Queues(Patientpatient)//新來病人，先暫時放最后一位intarrange()//每次有新病人

6、到來，都按他的到來時間和病情，排隊算法：采用直接插入排序。數據結構與算法分析在隊列中設置一個“頭”和“尾”標志，從頭部讀取病人，在尾部寫入病人。當有新的病人到來時：設置一個TEMP變量，先將病人暫時放在隊列尾部，TEMP指向新病人之前一個病人，TEMP依次向前移動，滿足條件新加入的病人病情級別更高（如果是排序的話，時間也要靠前）。終止條件是，新病人病情比TEMP低或者相同而且時間靠后，這時找到新病人的位置，將它放置在TEMP之后。完成寫入排序過程。醫(yī)師Doctor類屬性：intpid;//醫(yī)生編號intfree;/

7、/醫(yī)生狀態(tài)，1表示空閑，可以為接診；0表示忙；-1表示不值班主要方法：inttreatment(Queues&queue)//從隊列頭部取病人當醫(yī)生讀取病人后，讀取其屬性中需要治療的時間，隊列“頭”部標志向后移動一個位置。我們?yōu)榱四M，就采用阻塞的方式，阻塞時間為病人需要治療的時間。共享隊列數據Queuesqueues;//全局病人隊列不管醫(yī)生并發(fā)讀取病人信息，還是主線程隨機生成病人放入隊列，多個線程同時請求同一資源時候，構成競爭條件。因此如果不采取有效的控制，那肯定處理結果跟我們預想大相徑庭。針對這一情況，我們組

8、內人員展開了充分的討論，最后采用林志春同學提出的加一個讀寫鎖，來控制并發(fā)讀寫操作。并發(fā)處理解決思路：用軟件的方法加鎖。具體操作如下：設置一全局標志變量boolsign，//對病人隊列的讀寫鎖，如果要從隊列頭部插入病人，或者從隊列尾部讀取病人，都要先查詢sign標志，如果為true,則表示可以取得讀寫權，相應線程立刻設置sign為false,待讀寫操作完成后，