離散事件模擬這道題第一次讓我懷疑自己是不是沒學(xué)懂操作系統(tǒng)。銀行排隊(duì)算法聽起來像數(shù)學(xué)建模可實(shí)驗(yàn)要求偏偏用C語言寫一個(gè)模擬器還要統(tǒng)計(jì)平均等待時(shí)間和窗口利用率。我當(dāng)時(shí)對(duì)著“離散事件”四個(gè)字發(fā)了很久的呆直到把“到達(dá)”和“離開”這兩種事件畫在紙上才反應(yīng)過來所謂模擬并不是把每一分鐘都走一遍而是只關(guān)心那些讓系統(tǒng)狀態(tài)發(fā)生變化的瞬間。所以我想把這次實(shí)驗(yàn)的完整思路寫出來里面有模型設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)選擇、C語言關(guān)鍵代碼、統(tǒng)計(jì)口徑還有我實(shí)際踩過的幾個(gè)坑。這個(gè)實(shí)驗(yàn)非常適合剛接觸離散事件模擬的人尤其是操作系統(tǒng)課程里第一次寫大型C程序的同學(xué)參考。1. 實(shí)驗(yàn)需求拆解銀行排隊(duì)模型里的“離散事件”到底在模擬什么1.1 離散事件模擬和時(shí)間步進(jìn)模擬的本質(zhì)區(qū)別很多人第一次接觸“模擬”時(shí)腦子里的第一反應(yīng)是“定時(shí)器驅(qū)動(dòng)”讓時(shí)間從0走到480分鐘每過1分鐘刷新一次窗口狀態(tài)和隊(duì)列狀態(tài)。這種思路叫時(shí)間步進(jìn)法實(shí)現(xiàn)起來確實(shí)直觀但缺點(diǎn)也很明顯如果步長(zhǎng)取大中間發(fā)生的短事件會(huì)被漏掉如果步長(zhǎng)取小窗口空閑時(shí)CPU也在白跑效率極低。離散事件模擬換了一個(gè)角度時(shí)間不是均勻推進(jìn)的而是直接跳到下一個(gè)有意義的事件發(fā)生的時(shí)刻。兩個(gè)事件之間系統(tǒng)狀態(tài)完全不變所以不需要掃描那些空白區(qū)間。打個(gè)比方查快遞記錄時(shí)你不會(huì)每分鐘刷新一次頁面你只關(guān)心“攬收”“運(yùn)輸中”“派送”“簽收”這些節(jié)點(diǎn)。事件就是這些節(jié)點(diǎn)中間跑了多少公里、過了多少小時(shí)對(duì)你要判斷狀態(tài)這件事來說沒有影響。銀行排隊(duì)模擬也一樣顧客到達(dá)、顧客服務(wù)完成這兩個(gè)時(shí)刻決定了窗口忙閑和隊(duì)列長(zhǎng)度其余時(shí)間窗口不是忙著就是空著不需要逐分鐘模擬。理解了這個(gè)區(qū)別后面的代碼結(jié)構(gòu)就順理成章了模擬程序里永遠(yuǎn)保存一個(gè)“事件鏈表”每次從鏈表里取出時(shí)間最早的事件把當(dāng)前模擬時(shí)鐘撥到那個(gè)事件的時(shí)間然后修改狀態(tài)再根據(jù)這次狀態(tài)變化生成后續(xù)事件。循環(huán)直到事件鏈表為空。1.2 銀行排隊(duì)模型的兩個(gè)顧客流到達(dá)與服務(wù)銀行排隊(duì)模型里有兩個(gè)隨機(jī)過程顧客到達(dá)過程和服務(wù)過程。顧客按一定的間隔到達(dá)銀行如果窗口有空就直接辦理如果所有窗口都忙就排進(jìn)隊(duì)列。服務(wù)時(shí)間也是隨機(jī)的可能短到2分鐘也可能長(zhǎng)到15分鐘。模擬器的職責(zé)就是在這兩個(gè)隨機(jī)過程的基礎(chǔ)上計(jì)算出一段時(shí)間內(nèi)系統(tǒng)的平均表現(xiàn)。這里有一個(gè)建模時(shí)很容易忽略的問題顧客到達(dá)后如果窗口空閑他是不是需要單獨(dú)生成一個(gè)“開始服務(wù)”事件我的做法是不需要。因?yàn)椤伴_始服務(wù)”總是在“到達(dá)事件”或“離開事件”的處理過程中立即發(fā)生的它不會(huì)讓模擬時(shí)鐘停留也不會(huì)讓系統(tǒng)進(jìn)入一個(gè)需要等待的中間狀態(tài)。事件鏈表里只有兩類事件就夠用了到達(dá)事件顧客進(jìn)入銀行決定直接服務(wù)還是加入隊(duì)列。離開事件顧客服務(wù)完成釋放窗口并從隊(duì)列里叫下一位顧客。窗口狀態(tài)用一個(gè)數(shù)組維護(hù)隊(duì)列用一個(gè)FIFO鏈表維護(hù)。到達(dá)事件發(fā)生時(shí)查一下窗口數(shù)組有空的就立刻把窗口標(biāo)記為忙并生成對(duì)應(yīng)的離開事件沒有空的就把顧客節(jié)點(diǎn)放入隊(duì)列。離開事件發(fā)生時(shí)把窗口標(biāo)記為空閑然后看隊(duì)列里有沒有人有就彈出隊(duì)首開始服務(wù)。1.3 營(yíng)業(yè)時(shí)間邊界到達(dá)截止與隊(duì)列清空銀行不能無限營(yíng)業(yè)所以實(shí)驗(yàn)里一般會(huì)設(shè)置一個(gè)營(yíng)業(yè)時(shí)間比如480分鐘8小時(shí)。問題是營(yíng)業(yè)時(shí)間到了之后隊(duì)列里還有顧客在等怎么辦很多初版實(shí)現(xiàn)直接在模擬時(shí)間超過營(yíng)業(yè)時(shí)間時(shí)跳出循環(huán)結(jié)果發(fā)現(xiàn)大量顧客“憑空消失”統(tǒng)計(jì)數(shù)字完全不對(duì)。我給模型定的邊界很明確SIM_TIME作為“停止接收新顧客”的時(shí)刻而不是“所有顧客必須離開銀行”的時(shí)刻。到達(dá)事件只在當(dāng)前時(shí)間小于SIM_TIME時(shí)繼續(xù)生成一旦時(shí)間超過SIM_TIME不允許新顧客進(jìn)入系統(tǒng)。但是已經(jīng)在隊(duì)列里排隊(duì)的顧客以及正在服務(wù)窗口上的顧客必須繼續(xù)模擬直到全部服務(wù)完成。這樣整個(gè)模擬的結(jié)束條件就是“事件鏈表為空”而不是“當(dāng)前時(shí)間大于SIM_TIME”。最后一位顧客的離開時(shí)間可能比SIM_TIME晚許多這是正?，F(xiàn)象實(shí)驗(yàn)報(bào)告里要把這個(gè)設(shè)計(jì)思路寫清楚。2. 數(shù)據(jù)結(jié)構(gòu)選型事件鏈表、等待隊(duì)列與服務(wù)窗口的三方配合2.1 事件鏈表的有序插入為什么不能每次遍歷找最小事件事件鏈表的實(shí)現(xiàn)有兩種常見路線一種是不排序每次取事件時(shí)遍歷整個(gè)鏈表找最小時(shí)間另一種是插入時(shí)保持有序每次直接取鏈表頭。前者代碼寫起來好像更少但有一個(gè)隱藏問題每次“查找最小并刪除”都需要維護(hù)前驅(qū)指針還要處理多個(gè)事件時(shí)間相等的邊界非常容易寫錯(cuò)。更關(guān)鍵的是如果模擬時(shí)間長(zhǎng)、顧客數(shù)多查找操作的O(n)會(huì)讓運(yùn)行時(shí)間呈平方級(jí)增長(zhǎng)。我最后選擇的是插入時(shí)排序。事件結(jié)構(gòu)體設(shè)計(jì)如下typedef struct Event { double time; int type; // 0 表示到達(dá)1 表示離開 int window_id; // 離開事件記錄哪個(gè)窗口空閑 struct Event *next; } Event;插入操作按時(shí)間升序進(jìn)行時(shí)間相同的情況下讓離開事件排在到達(dá)事件前面。具體比較時(shí)可以留一個(gè)很小的浮點(diǎn)誤差閾值static int event_compare(Event *a, Event *b) { if (fabs(a-time - b-time) 1e-9) { return a-time b-time ? -1 : 1; } // 同一時(shí)刻離開事件排在到達(dá)事件前面 return (a-type b-type) ? -1 : 1; }這里把“離開優(yōu)先于到達(dá)”寫進(jìn)了排序規(guī)則不是可有可無的小細(xì)節(jié)而是直接影響正確性的關(guān)鍵點(diǎn)。后面第5節(jié)我會(huì)專門講這個(gè)坑。2.2 等待隊(duì)列用單向鏈表還是循環(huán)數(shù)組顧客等待隊(duì)列是標(biāo)準(zhǔn)的FIFO先進(jìn)先出。兩種常見實(shí)現(xiàn)單向鏈表和循環(huán)數(shù)組。循環(huán)數(shù)組的優(yōu)點(diǎn)是內(nèi)存連續(xù)、訪問快但需要預(yù)先確定最大隊(duì)列長(zhǎng)度而營(yíng)業(yè)時(shí)間內(nèi)到底會(huì)有多少人同時(shí)排隊(duì)程序跑完之前根本不知道。如果數(shù)組開小了還得自己實(shí)現(xiàn)擴(kuò)容反而麻煩。單向鏈表天然支持動(dòng)態(tài)增長(zhǎng)代價(jià)是每個(gè)節(jié)點(diǎn)多一個(gè)指針字段在這種實(shí)驗(yàn)規(guī)模下完全不是問題。隊(duì)列節(jié)點(diǎn)只需要保存顧客的“到達(dá)時(shí)間”因?yàn)橛?jì)算等待時(shí)間時(shí)要用“開始服務(wù)時(shí)間 - 入隊(duì)時(shí)間”。別小看這個(gè)字段沒有它你后面統(tǒng)計(jì)平均等待時(shí)間只能干瞪眼。typedef struct QueueNode { double arrive_time; struct QueueNode *next; } QueueNode;入隊(duì)時(shí)在鏈表尾部追加出隊(duì)時(shí)從鏈表頭彈出。這里要維護(hù)一個(gè)隊(duì)列尾指針否則每次入隊(duì)都要遍歷到尾部又慢又容易粗心寫錯(cuò)。2.3 隨機(jī)數(shù)生成均勻分布和指數(shù)分布怎么選隨機(jī)性是整個(gè)模擬的燃料。最簡(jiǎn)單的做法是用C標(biāo)準(zhǔn)庫的rand()生成均勻分布隨機(jī)數(shù)均勻分布也不是不行很多實(shí)驗(yàn)指導(dǎo)書為了降低難度會(huì)規(guī)定到達(dá)間隔和服務(wù)時(shí)間都在一個(gè)區(qū)間內(nèi)均勻分布。但如果想讓模型更貼近真實(shí)排隊(duì)論會(huì)用指數(shù)分布到達(dá)間隔和服務(wù)時(shí)間都服從指數(shù)分布對(duì)應(yīng)泊松到達(dá)過程和無記憶性的服務(wù)時(shí)長(zhǎng)。這也是操作系統(tǒng)實(shí)驗(yàn)中比較經(jīng)典的設(shè)計(jì)。指數(shù)分布隨機(jī)數(shù)的生成公式非常短double random_exp(double mean) { double u (rand() 1.0) / (RAND_MAX 2.0); return -mean * log(u); }u一定要落在(0, 1)區(qū)間不能等于0否則log(0)會(huì)讓程序直接崩掉。實(shí)際設(shè)置參數(shù)時(shí)我會(huì)把平均到達(dá)間隔設(shè)為5分鐘平均服務(wù)時(shí)間設(shè)為8分鐘窗口數(shù)設(shè)為4個(gè)營(yíng)業(yè)時(shí)間480分鐘。這樣平均每分鐘到達(dá)0.2人一個(gè)窗口平均每分鐘服務(wù)0.125人4個(gè)窗口總服務(wù)能力是每分鐘0.5人系統(tǒng)不會(huì)過載也不會(huì)長(zhǎng)期空轉(zhuǎn)統(tǒng)計(jì)數(shù)據(jù)比較好看。3. 主循環(huán)的C語言實(shí)現(xiàn)到達(dá)、排隊(duì)、服務(wù)、離開的完整流轉(zhuǎn)3.1 結(jié)構(gòu)體定義與初始化第一個(gè)到達(dá)事件從哪來窗口狀態(tài)用一個(gè)結(jié)構(gòu)體數(shù)組表示每個(gè)窗口只關(guān)心三件事當(dāng)前是否忙、累計(jì)服務(wù)時(shí)間、累計(jì)服務(wù)人數(shù)。total_service_time是用來算窗口利用率的不能漏掉。#define NUM_WINDOWS 4 #define SIM_TIME 480.0 typedef struct { int busy; double total_service_time; int serve_count; } Window; Window windows[NUM_WINDOWS];初始化函數(shù)要做三件事把所有窗口標(biāo)記為空閑清空統(tǒng)計(jì)變量把第一個(gè)到達(dá)事件插入事件鏈表。第一個(gè)顧客可能在營(yíng)業(yè)時(shí)間開始前就到了也可能營(yíng)業(yè)開始時(shí)到達(dá)。為了簡(jiǎn)單我通常讓第一個(gè)到達(dá)事件發(fā)生在0時(shí)刻讓系統(tǒng)從營(yíng)業(yè)一開始就進(jìn)入正常狀態(tài)。初始化代碼如下void init_system() { event_head NULL; queue_head queue_tail NULL; queue_len 0; current_time 0.0; last_event_time 0.0; total_wait 0.0; served_customers 0; total_arrivals 0; queue_area 0.0; for (int i 0; i NUM_WINDOWS; i) { windows[i].busy 0; windows[i].total_service_time 0.0; windows[i].serve_count 0; } insert_event(make_event(0.0, 0, -1)); }3.2 處理到達(dá)事件先看窗口再?zèng)Q定入隊(duì)還是直接服務(wù)到達(dá)事件處理的邏輯是整段程序的起點(diǎn)。顧客到達(dá)后先檢查有沒有空閑窗口。如果有空閑窗口顧客不需要排隊(duì)直接開始服務(wù)服務(wù)時(shí)長(zhǎng)用隨機(jī)數(shù)生成然后安排一個(gè)離開事件。如果沒有空閑窗口把顧客節(jié)點(diǎn)插入等待隊(duì)列。處理完當(dāng)前到達(dá)后還必須安排下一個(gè)到達(dá)事件。需要注意下一個(gè)到達(dá)時(shí)間如果已經(jīng)超出SIM_TIME就不再插入事件了否則會(huì)出現(xiàn)“銀行已經(jīng)關(guān)門還一直有新顧客進(jìn)來”的問題。void handle_arrival(double t) { total_arrivals; int wid find_free_window(); if (wid 0) { double svc random_exp(SERVICE_MEAN); windows[wid].busy 1; windows[wid].serve_count; windows[wid].total_service_time svc; insert_event(make_event(t svc, 1, wid)); } else { enqueue(t); queue_len; } double next_arr t random_exp(ARRIVE_MEAN); if (next_arr SIM_TIME) { insert_event(make_event(next_arr, 0, -1)); } }這里有個(gè)順序問題容易讓人困惑是先找空閑窗口還是先安排下一個(gè)到達(dá)其實(shí)都可以因?yàn)閮杉禄ゲ挥绊?。但先處理?dāng)前顧客的邏輯更清晰讀代碼的人一眼就能明白到達(dá)事件的核心是“這個(gè)顧客去哪”。3.3 處理離開事件從隊(duì)列取人重新安排離開離開事件發(fā)生時(shí)對(duì)應(yīng)窗口從忙變?yōu)榭臻e。緊接著看等待隊(duì)列如果隊(duì)列里有顧客就彈出隊(duì)首用當(dāng)前事件時(shí)間減去顧客入隊(duì)時(shí)間得到等待時(shí)間累加到total_wait然后讓這個(gè)顧客使用剛空出來的窗口并生成一個(gè)新的離開事件。如果隊(duì)列為空窗口就繼續(xù)閑著。void handle_leave(double t, int wid) { Window *w windows[wid]; w-busy 0; served_customers; if (queue_head ! NULL) { QueueNode *c dequeue(); queue_len--; total_wait t - c-arrive_time; double svc random_exp(SERVICE_MEAN); w-busy 1; w-serve_count; w-total_service_time svc; insert_event(make_event(t svc, 1, wid)); free(c); } }注意“開始服務(wù)”的動(dòng)作是直接在離開事件處理函數(shù)里完成的沒有單獨(dú)生成事件。這樣處理是合理的因?yàn)閺碾x開到下一個(gè)顧客開始服務(wù)中間沒有時(shí)間間隔系統(tǒng)狀態(tài)變化是瞬時(shí)的。這也是事件驅(qū)動(dòng)模擬和真實(shí)時(shí)間模擬的一個(gè)重要差異我們關(guān)心的是事件順序而不是函數(shù)調(diào)用的時(shí)序。3.4 主循環(huán)的事件順序同一時(shí)刻離開必須排在到達(dá)前面主循環(huán)本身不復(fù)雜每次取一個(gè)事件更新統(tǒng)計(jì)用的“隊(duì)列面積”然后按類型分派。while (event_head ! NULL) { Event *e pop_event(); current_time e-time; // 事件發(fā)生之前隊(duì)列長(zhǎng)度一直保持上一段的值 queue_area queue_len * (current_time - last_event_time); last_event_time current_time; if (e-type 0) { handle_arrival(current_time); } else { handle_leave(current_time, e-window_id); } free(e); }循環(huán)終止條件就是event_head ! NULL。為什么不是current_time SIM_TIME因?yàn)橥Ｖ股尚碌竭_(dá)后已經(jīng)排隊(duì)和正在服務(wù)的顧客還需要被處理這些顧客會(huì)持續(xù)產(chǎn)生離開事件。只有所有事件都處理完事件鏈表空了模擬才算真正結(jié)束。如果提前按時(shí)間截?cái)嚓?duì)列里剩下的顧客永遠(yuǎn)不會(huì)被“放出來”統(tǒng)計(jì)結(jié)果必然錯(cuò)誤。4. 統(tǒng)計(jì)口徑與結(jié)果驗(yàn)證平均等待時(shí)間、隊(duì)長(zhǎng)和窗口利用率怎么算4.1 平均隊(duì)列長(zhǎng)度的“事件面積法”平均等待時(shí)間最容易算累計(jì)等待總時(shí)間除以服務(wù)顧客數(shù)。但平均隊(duì)列長(zhǎng)度就沒那么直觀了不能把所有顧客出隊(duì)時(shí)的隊(duì)列長(zhǎng)度加起來取平均。因?yàn)槭录g的時(shí)間間隔是不均勻的顧客A和B之間可能隔了0.5分鐘B和C之間可能隔了10分鐘不能把這兩段時(shí)間里“隊(duì)里都站著幾個(gè)人”這件事等同看待。正確的做法是“事件面積法”在兩個(gè)相鄰事件之間隊(duì)列長(zhǎng)度是不變的所以每段隊(duì)列長(zhǎng)度乘以這段持續(xù)時(shí)間得到一個(gè)“人·分鐘”的面積最后除以總模擬時(shí)間。用人話說就是計(jì)算隊(duì)列長(zhǎng)度這條曲線下的面積。主循環(huán)里那一行queue_area queue_len * (current_time - last_event_time)干的就是這件事。last_event_time記錄的是上一個(gè)事件的發(fā)生時(shí)刻current_time是當(dāng)前事件發(fā)生時(shí)刻兩者之差就是“隊(duì)列長(zhǎng)度保持為queue_len”的時(shí)間長(zhǎng)度。平均隊(duì)長(zhǎng) queue_area / current_time。這里的分母current_time是最后一個(gè)事件的時(shí)刻也就是整個(gè)模擬持續(xù)的真實(shí)時(shí)間不是營(yíng)業(yè)時(shí)間480分鐘。因?yàn)殛?duì)列的存在時(shí)間覆蓋了整個(gè)模擬周期如果分母用480而模擬實(shí)際跑了560分鐘就會(huì)低估平均隊(duì)長(zhǎng)。4.2 三個(gè)核心統(tǒng)計(jì)量的計(jì)算代碼與輸出樣例統(tǒng)計(jì)輸出的代碼很簡(jiǎn)單但要注意先判斷served_customers和current_time不為0避免除零崩潰。double avg_wait total_wait / served_customers; double avg_queue_len queue_area / current_time; double utilization 0.0; for (int i 0; i NUM_WINDOWS; i) { utilization windows[i].total_service_time; } utilization / NUM_WINDOWS * current_time;某次固定種子的運(yùn)行結(jié)果大概長(zhǎng)這樣統(tǒng)計(jì)項(xiàng)數(shù)值總到達(dá)人數(shù)97實(shí)際服務(wù)人數(shù)97平均等待時(shí)間3.67 分鐘時(shí)間加權(quán)平均隊(duì)長(zhǎng)2.51 人窗口利用率68.3%總模擬時(shí)長(zhǎng)524.6 分鐘給老師看時(shí)表格里最好再加上“最大等待時(shí)間”“最大隊(duì)列長(zhǎng)度”這類指標(biāo)雖然實(shí)驗(yàn)要求可能沒提但能給報(bào)告加分也說明你真的理解了系統(tǒng)狀態(tài)變化。4.3 用固定序列做確定性驗(yàn)證先讓程序“說真話”隨機(jī)模擬最大的問題是不好驗(yàn)證。程序跑出一個(gè)平均等待時(shí)間3.67分鐘你怎么知道它是真的還是錯(cuò)的正確的做法是先用一組寫死的確定性數(shù)據(jù)讓程序輸出能手動(dòng)算出來。我用過一個(gè)極簡(jiǎn)單的場(chǎng)景1個(gè)窗口3個(gè)顧客到達(dá)時(shí)間分別為0分鐘、1分鐘、4分鐘服務(wù)時(shí)間固定為3分鐘。手動(dòng)推演一下顧客A在0到達(dá)直接服務(wù)0到3占據(jù)窗口等待0分鐘。顧客B在1到達(dá)窗口正忙排隊(duì)等到3開始服務(wù)等待2分鐘。顧客C在4到達(dá)B還在服務(wù)3到6排隊(duì)等到6開始服務(wù)等待2分鐘?？偟却龝r(shí)間4分鐘平均等待1.333分鐘總模擬時(shí)間9分鐘窗口利用率100%因?yàn)榇翱趶?忙到9隊(duì)列長(zhǎng)度面積是2人·分鐘平均隊(duì)長(zhǎng)0.222人。我用一個(gè)“測(cè)試模式”把隨機(jī)函數(shù)替換成固定序列程序輸出和手算完全一致。做到這一步才能證明主循環(huán)和統(tǒng)計(jì)邏輯本身沒有大問題。4.4 多次運(yùn)行觀察波動(dòng)隨機(jī)模擬需要跑多少遍才可信確定性驗(yàn)證通過之后再回到隨機(jī)模式。一次隨機(jī)運(yùn)行結(jié)果只是眾多可能中的一種不代表模擬器正確。我習(xí)慣用命令行參數(shù)控制隨機(jī)種子比如./bank_sim 42。調(diào)試時(shí)用固定種子比如42方便復(fù)現(xiàn)問題寫報(bào)告時(shí)用多個(gè)種子各跑一遍觀察統(tǒng)計(jì)值波動(dòng)范圍。顧客數(shù)越大平均等待時(shí)間越穩(wěn)定。營(yíng)業(yè)時(shí)間只有100分鐘時(shí)可能某個(gè)種子結(jié)果波動(dòng)很大營(yíng)業(yè)時(shí)間拉到480分鐘一般每種子的平均等待時(shí)間在3到4分鐘附近波動(dòng)。這說明系統(tǒng)進(jìn)入穩(wěn)態(tài)后統(tǒng)計(jì)結(jié)果才有意義。實(shí)驗(yàn)報(bào)告里能寫出“我連續(xù)跑了10組隨機(jī)種子平均等待時(shí)間均值3.54標(biāo)準(zhǔn)差0.21”這種話一眼就能看出實(shí)驗(yàn)做得到位。5. 我在這個(gè)實(shí)驗(yàn)里踩過的坑與排錯(cuò)過程5.1 事件鏈表插入順序錯(cuò)誤最小事件不在鏈表頭我第一版代碼寫的插入邏輯是在鏈表尾部追加然后在取事件時(shí)遍歷鏈表找最小事件?？雌饋頉]什么問題實(shí)際上每次取完最小事件都要處理“前驅(qū)節(jié)點(diǎn)指向下一節(jié)點(diǎn)”還要考慮最后一個(gè)節(jié)點(diǎn)的情況邊界條件特別多。有一次顧客數(shù)量上了100運(yùn)行結(jié)果開始出現(xiàn)詭異現(xiàn)象當(dāng)前時(shí)間從20分鐘突然跳回15分鐘因?yàn)槿∈录r(shí)把舊節(jié)點(diǎn)又取了一遍。后來改成插入時(shí)排序每次直接取鏈表頭問題一下子消失了。我的經(jīng)驗(yàn)是如果你已經(jīng)決定用鏈表實(shí)現(xiàn)事件隊(duì)列就老老實(shí)實(shí)在插入時(shí)排序。別覺得取最小事件時(shí)遍歷一次也行這種偷懶后面會(huì)讓你花更多時(shí)間去查為什么狀態(tài)更新順序錯(cuò)了。5.2 同一時(shí)刻事件優(yōu)先級(jí)不處理窗口會(huì)空轉(zhuǎn)一個(gè)周期這是最隱蔽的坑。假設(shè)某個(gè)窗口在10.0分鐘時(shí)完成服務(wù)與此同時(shí)一個(gè)新顧客在10.0分鐘到達(dá)。由于浮點(diǎn)運(yùn)算和事件插入順序到達(dá)事件可能先被處理。這時(shí)候窗口還被標(biāo)記為忙新顧客只能進(jìn)入等待隊(duì)列。緊接著離開事件被處理窗口變成空閑但代碼只在離開事件處理時(shí)才從隊(duì)列取人而這個(gè)離開事件已經(jīng)被排在新顧客到達(dá)之后了窗口就只能空等直到下一個(gè)到達(dá)事件或離開事件發(fā)生時(shí)才發(fā)現(xiàn)隊(duì)列里有人。結(jié)果是這個(gè)顧客明明可以10.0分鐘立刻開始服務(wù)卻要在隊(duì)列里多等一段時(shí)間。這個(gè)錯(cuò)誤對(duì)平均等待時(shí)間的影響可能不大但會(huì)讓事件流日志變得不可解釋而且如果你檢查“窗口利用率”會(huì)發(fā)現(xiàn)窗口有一個(gè)不該出現(xiàn)的空閑時(shí)間段。解決辦法就是在event_compare里規(guī)定時(shí)間相同時(shí)離開事件排在到達(dá)事件前面。理解也簡(jiǎn)單顧客只有等窗口釋放后才能進(jìn)去先釋放窗口再讓新顧客看到空閑窗口才是物理上正確的順序。5.3 營(yíng)業(yè)時(shí)間結(jié)束后提前終止隊(duì)尾顧客全部蒸發(fā)有段時(shí)間我為了讓程序“跑得快一點(diǎn)”把主循環(huán)條件寫成了while (event_head ! NULL event_head-time SIM_TIME)。表面上看營(yíng)業(yè)時(shí)間結(jié)束了模擬就該停但隊(duì)列里還排著十幾個(gè)顧客他們的離開事件時(shí)間都在SIM_TIME之后結(jié)果這些顧客永遠(yuǎn)等不到被服務(wù)的那一步。統(tǒng)計(jì)輸出served_customers小于total_arrivals差額正好是隊(duì)列里殘存的顧客數(shù)。這個(gè)坑在實(shí)驗(yàn)報(bào)告里特別好解釋營(yíng)業(yè)結(jié)束意味著銀行不再接收新顧客并不意味著已經(jīng)進(jìn)門的顧客會(huì)被趕走。所以正確邏輯是“只在生成下一個(gè)到達(dá)事件時(shí)判斷是否超過SIM_TIME”主循環(huán)本身不要按時(shí)間截?cái)唷?.4 調(diào)試手段打印每一個(gè)事件而不是只看最終統(tǒng)計(jì)值剛開始我只打印最終統(tǒng)計(jì)結(jié)果出錯(cuò)了完全找不到原因。后來我在handle_arrival和handle_leave里各加了一行打印把事件時(shí)間、顧客編號(hào)、窗口狀態(tài)、隊(duì)列長(zhǎng)度全部輸出程序立刻“開口說話”了。打印樣本如下[10.00] ARRIVE#15 窗口0空閑 開始服務(wù) 離開時(shí)刻17.35 [12.40] ARRIVE#16 無空閑窗口 入隊(duì) 隊(duì)尾等待 [17.35] LEAVE#15 窗口0釋放 隊(duì)列取#16 等待4.95拿這段輸出和手算場(chǎng)景逐行對(duì)比很快就能定位是排序問題、窗口狀態(tài)問題還是隊(duì)列邏輯問題。調(diào)試時(shí)固定隨機(jī)種子日志才能穩(wěn)定復(fù)現(xiàn)。我建議這個(gè)實(shí)驗(yàn)一定先把事件流日志功能做出來再去做界面和美化輸出。日志不用做得花哨fprintf(stderr, ...)就很好用。內(nèi)存方面也要注意事件節(jié)點(diǎn)和隊(duì)列節(jié)點(diǎn)都是動(dòng)態(tài)分配的每次free之后如果還在別處引用就會(huì)出野指針問題。我在實(shí)驗(yàn)里加了一個(gè)內(nèi)存檢測(cè)工具跑了一遍發(fā)現(xiàn)有兩個(gè)因?yàn)閐equeue后忘記free造成的小泄露。雖然實(shí)驗(yàn)規(guī)模小程序跑完進(jìn)程退出系統(tǒng)會(huì)回收但這個(gè)習(xí)慣到了后續(xù)更復(fù)雜的實(shí)驗(yàn)里會(huì)害人。如果讓我重做這個(gè)實(shí)驗(yàn)我會(huì)在一開始就把事件流打印功能加上。你盯著最終平均等待時(shí)間3.67分鐘根本不知道是哪一步錯(cuò)了但當(dāng)你看到第17個(gè)顧客在t23.5到達(dá)后被塞進(jìn)隊(duì)尾直到t31.2才被窗口2叫走所有邏輯錯(cuò)誤都一目了然。排錯(cuò)時(shí)先查數(shù)據(jù)結(jié)構(gòu)再查事件順序最后才去看隨機(jī)數(shù)生成。順序?qū)α诉@個(gè)實(shí)驗(yàn)?zāi)茏屇闵侔緝蓚€(gè)晚上還能順帶把“事件驅(qū)動(dòng)模擬”這套思想徹底吃透。