離散事件模擬聽起來像科研術(shù)語其實(shí)就是操作系統(tǒng)實(shí)驗(yàn)1里那個銀行排隊(duì)算法要用到的核心機(jī)制。用C語言實(shí)現(xiàn)的時候我一開始覺得不過是模擬幾個客戶進(jìn)銀行排隊(duì)沒想到里面對事件鏈表、隊(duì)列、隨機(jī)數(shù)的要求都不低。做完之后回頭總結(jié)發(fā)現(xiàn)這個實(shí)驗(yàn)特別值得聊表面上是練數(shù)據(jù)結(jié)構(gòu)實(shí)際上它是理解操作系統(tǒng)調(diào)度、網(wǎng)絡(luò)報(bào)文處理、連接池管理這類真實(shí)系統(tǒng)的一個微型沙盤。這篇文章會從建模思路、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、C語言實(shí)現(xiàn)細(xì)節(jié)、常見調(diào)試坑四個方面展開爭取讓正在寫這個實(shí)驗(yàn)的人能直接抄到思路也讓沒做過的人知道離散事件模擬到底是怎么回事。1. 先搞懂離散事件模擬到底在解決什么問題1.1 什么是離散事件模擬離散事件模擬的核心思想是系統(tǒng)狀態(tài)只在“事件”發(fā)生的時刻發(fā)生變化而不是隨時間連續(xù)變化。所謂離散就是指狀態(tài)變化發(fā)生在一個個孤立的時間點(diǎn)上。銀行排隊(duì)場景里客戶到達(dá)是一個事件客戶開始接受服務(wù)是一個事件服務(wù)完成離開也是一個事件。在這些事件之間窗口忙不忙、隊(duì)列里有多少人都是不變的所以模擬器完全可以跳過這些“空白時間段”。這個特點(diǎn)讓模擬程序變得很高效。假設(shè)銀行營業(yè)8小時也就是480分鐘。如果按時間步長法每隔1秒掃描一次要迭代28800次但用事件驅(qū)動客戶到達(dá)間隔平均2分鐘加上服務(wù)完成事件總共可能只需要處理幾百到幾千個事件。差了一個數(shù)量級還不止。操作系統(tǒng)課程里很多調(diào)度算法、資源分配問題本質(zhì)上都是離散事件系統(tǒng)所以這個實(shí)驗(yàn)不是單純練鏈表而是在訓(xùn)練一種“事件驅(qū)動”的建模思維方式。1.2 事件驅(qū)動為什么比時間步長高效有同學(xué)會問我能不能在一個循環(huán)里每秒鐘把系統(tǒng)狀態(tài)刷新一次理論上可以但問題很多。第一步長選擇很尷尬步長太大會漏掉短時間內(nèi)連續(xù)發(fā)生的事件步長太小又會把性能拖垮。第二真實(shí)系統(tǒng)中事件發(fā)生的時間點(diǎn)往往不是整秒步長模擬天然有量化誤差。第三大量時間窗口里系統(tǒng)什么都沒發(fā)生這些掃描都是無效計(jì)算。離散事件模擬的做法完全不同系統(tǒng)維護(hù)一個當(dāng)前時間每次都從事件鏈表里取出“下一個最早發(fā)生的事件”然后把當(dāng)前時間直接跳躍到那個事件發(fā)生的時刻。比如第一個客戶在10:00到達(dá)服務(wù)到10:03:20第二個客戶在10:00:40到達(dá)處理完第一位客戶后系統(tǒng)時間直接從10:00跳到10:03:20中間兩分鐘沒有任何事件所以完全不掃描。這種時間跳躍機(jī)制讓模擬程序天然精確且高效。1.3 銀行排隊(duì)模型的四個核心元素要在程序里模擬銀行排隊(duì)先得把現(xiàn)實(shí)世界抽象成四個部分客戶、窗口、等待隊(duì)列、事件?？蛻羰橇鲃拥膶ο竺總€客戶有到達(dá)時間、開始服務(wù)時間、離開時間窗口是服務(wù)資源每個時刻只能服務(wù)一個客戶可能空閑也可能忙碌隊(duì)列是排隊(duì)等待客戶的容器通常是先進(jìn)先出事件則是整個模擬的驅(qū)動源分為到達(dá)事件和離開事件。底層的邏輯關(guān)系不復(fù)雜客戶隨機(jī)到達(dá)有窗口空閑就直接接受服務(wù)沒有窗口空閑就進(jìn)隊(duì)列等待。窗口完成一個服務(wù)后如果隊(duì)列里有人就從隊(duì)頭取出一個客戶繼續(xù)服務(wù)否則窗口轉(zhuǎn)為空閑。事件分別在這兩個階段產(chǎn)生到達(dá)事件會觸發(fā)一次“分配窗口”的嘗試離開事件會觸發(fā)一次“從隊(duì)列取人”的嘗試。把這張關(guān)系圖在草稿紙上畫清楚寫代碼時就不容易亂。1.4 實(shí)驗(yàn)需求拆解輸入與輸出實(shí)驗(yàn)題通常會給這樣幾個輸入?yún)?shù)參數(shù)示例值含義窗口數(shù)量3銀行有多少個服務(wù)窗口總模擬時間480 分鐘營業(yè)時長平均到達(dá)間隔2 分鐘客戶到達(dá)的平均間隔平均服務(wù)時間3.33 分鐘單窗口服務(wù)一位客戶的平均耗時輸出指標(biāo)則包括總客戶數(shù)、平均等待時間、最長等待時間、平均隊(duì)列長度、窗口利用率。這里有一個非常容易忽略的坑總模擬時間結(jié)束后銀行會停止接受新客戶但還在排隊(duì)等待的客戶依然要被服務(wù)完。所以模擬循環(huán)的終止條件不能是“當(dāng)前時間達(dá)到總時長”而應(yīng)該是“事件鏈表為空”。我最初就是寫成了前者導(dǎo)致最后統(tǒng)計(jì)結(jié)果少了很多人實(shí)驗(yàn)報(bào)告數(shù)據(jù)直接變得不合理。2. 核心數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)2.1 事件鏈表模擬的引擎所有事件的調(diào)度都依賴于一個按時間排序的數(shù)據(jù)結(jié)構(gòu)。最簡單的選擇是單向鏈表每個節(jié)點(diǎn)記錄事件發(fā)生的時間、事件類型、關(guān)聯(lián)的窗口和客戶編號。插入時按照時間升序查找位置讓表頭始終是全局最早要處理的事件。取出時只需要摘掉表頭時間復(fù)雜度O(1)。節(jié)點(diǎn)結(jié)構(gòu)可以這樣設(shè)計(jì)typedef struct Event { double time; // 事件發(fā)生時間單位統(tǒng)一用分鐘 int type; // 0-到達(dá)事件1-離開事件 int window; // 離開事件對應(yīng)的窗口編號 int customer; // 客戶編號 struct Event *next; } Event;為什么時間要用double而不直接用int因?yàn)殡S機(jī)生成的指數(shù)分布時間間隔會出現(xiàn)小數(shù)如果強(qiáng)轉(zhuǎn)int長期模擬會產(chǎn)生累積誤差。單位統(tǒng)一用“分鐘”后就不要中途改成秒否則后期統(tǒng)計(jì)會非?；靵y。另外事件鏈表和普通鏈表的區(qū)別在于它要求每次插入都保持有序。哪怕插入操作是O(n)在這個實(shí)驗(yàn)規(guī)模下也完全夠用。2.2 客戶等待隊(duì)列FIFO不只是排隊(duì)等待隊(duì)列在邏輯上是先進(jìn)先出實(shí)現(xiàn)上可以用帶頭尾指針的單鏈表。但有一個設(shè)計(jì)細(xì)節(jié)比隊(duì)列本身更重要節(jié)點(diǎn)里到底存什么信息如果只存客戶編號出隊(duì)后還要去客戶表里找回到達(dá)時間繞了一大圈。我建議直接把到達(dá)時間存在隊(duì)列節(jié)點(diǎn)里這樣客戶出隊(duì)的一瞬間就能計(jì)算出等待時間。typedef struct QueueNode { int customer; // 客戶編號 double arriveTime; // 到達(dá)時間 struct QueueNode *next; } QueueNode;入隊(duì)時記錄的是該客戶進(jìn)隊(duì)列的那一刻而不是到達(dá)銀行的那一刻。在銀行排隊(duì)模型里客戶到達(dá)后如果沒有空閑窗口才會入隊(duì)所以入隊(duì)時間其實(shí)就是到達(dá)時間。但如果以后擴(kuò)展成“取號后必須排隊(duì)”或者“VIP優(yōu)先”這個字段就得靈活處理。實(shí)驗(yàn)階段先用最簡單版本把a(bǔ)rriveTime當(dāng)作到達(dá)時間就好。2.3 窗口狀態(tài)資源管理的小難題窗口是共享資源需要單獨(dú)用一個數(shù)組維護(hù)狀態(tài)。每個窗口至少要有兩個字段是否忙碌、累計(jì)服務(wù)時間。前者用來判斷到達(dá)事件能不能立刻被服務(wù)后者用來計(jì)算窗口利用率。還可以順便記錄每個窗口服務(wù)的客戶數(shù)方便做更加精細(xì)的統(tǒng)計(jì)。typedef struct { int busy; // 1-忙碌0-空閑 double workTime; // 累計(jì)服務(wù)時長 int servedCount; // 已服務(wù)客戶數(shù) } Window;窗口狀態(tài)為什么不能塞進(jìn)事件鏈表里因?yàn)槭录撬矔r的窗口狀態(tài)是持續(xù)存在的。比如窗口從忙碌變成空閑是在離開事件發(fā)生的那一刻改變的但同時它又在下一個客戶被分配之前一直保持空閑。這種“持續(xù)性狀態(tài)”放在事件節(jié)點(diǎn)里會讓邏輯特別別扭所以一定要單獨(dú)維護(hù)。等到處理離開事件時把窗口置為空閑然后立刻看隊(duì)列里有沒有人有人就通知下一個客戶進(jìn)來。2.4 隨機(jī)數(shù)生成讓模擬看起來真實(shí)客戶到達(dá)和服務(wù)過程都有隨機(jī)性操作系統(tǒng)實(shí)驗(yàn)里通常要求符合泊松過程即到達(dá)間隔服從指數(shù)分布。指數(shù)分布的生成方式不是直接用rand()而是用逆變換法先生成均勻分布隨機(jī)數(shù)再取負(fù)對數(shù)。C語言實(shí)現(xiàn)如下#include math.h double exponential_random(double rate) { double u rand() / (RAND_MAX 1.0); if (u 0.0) { u 1e-12; } return -log(1.0 - u) / rate; }這里rate是“單位時間內(nèi)的平均發(fā)生次數(shù)”。比如平均每2分鐘來一個客戶那么到達(dá)率是0.5客戶/分鐘調(diào)用時寫exponential_random(0.5)。如果服務(wù)一位客戶平均耗時3.33分鐘那么服務(wù)率是0.3客戶/分鐘。最容易犯的錯誤是把平均間隔當(dāng)成rate直接傳進(jìn)去比如寫exponential_random(2)這會讓間隔變成平均0.5分鐘模擬結(jié)果猛一看也能跑但數(shù)據(jù)會完全不對。3. C語言實(shí)現(xiàn)的關(guān)鍵環(huán)節(jié)3.1 程序模塊劃分與編譯環(huán)境即便是課程實(shí)驗(yàn)我也建議把代碼拆成三個模塊事件管理、隊(duì)列管理、統(tǒng)計(jì)邏輯。事件管理負(fù)責(zé)鏈表的創(chuàng)建、有序插入、取出隊(duì)列管理負(fù)責(zé)入隊(duì)和出隊(duì)統(tǒng)計(jì)邏輯放在主循環(huán)里單獨(dú)抽成函數(shù)。這樣哪怕只想把窗口數(shù)從3改成4也只需要改一個宏定義和初始化代碼。編譯時需要注意math庫的鏈接。很多同學(xué)在編譯實(shí)驗(yàn)代碼時發(fā)現(xiàn)log函數(shù)報(bào)錯原因是沒用-lm參數(shù)。如果gcc編譯命令是gcc -o bank_sim main.c event.c queue.c stat.c -lm如果編輯器自帶了構(gòu)建系統(tǒng)記得在鏈接參數(shù)里加上libm。我大學(xué)時第一次遇到這個錯誤完全沒頭緒報(bào)錯信息有一大堆其實(shí)就只是缺了數(shù)學(xué)庫。3.2 初始化把模擬推上軌道模擬啟動前需要做幾件事初始化所有窗口為空閑、初始化等待隊(duì)列為空、生成第一個客戶到達(dá)事件。第一個到達(dá)事件的時間通常設(shè)為0表示營業(yè)時間開始第一位客戶正好趕到。事件插入函數(shù)要把新節(jié)點(diǎn)按時間順序放到事件鏈表中。隨后設(shè)置隨機(jī)數(shù)種子比如srand(42)固定種子可以讓每次運(yùn)行的結(jié)果一致方便調(diào)試。srand(1000); for (int i 0; i WINDOW_NUM; i) { windows[i].busy 0; windows[i].workTime 0.0; windows[i].servedCount 0; } insertEvent(0, 0, -1, 0);那個insertEvent里傳的參數(shù)分別是時間0、類型0表示到達(dá)、窗口編號-1表示無窗口、客戶編號0。客戶編號從0還是從1開始都無所謂只要自增唯一即可。我習(xí)慣從1開始這樣輸出日志時更像真實(shí)場景調(diào)試起來也好辨認(rèn)。3.3 主循環(huán)事件驅(qū)動的核心主循環(huán)是整個模擬程序的心臟。它反復(fù)做三件事取出事件鏈表表頭、把系統(tǒng)時間推進(jìn)到該事件時間、根據(jù)事件類型分發(fā)處理。偽代碼如下while (eventList ! NULL) { Event *ev eventList; eventList ev-next; now ev-time; if (ev-type 0) { handle_arrival(now); } else { handle_departure(now, ev-window); } free(ev); }注意取出事件之后不要忘記free否則長時間模擬會內(nèi)存暴漲。主循環(huán)的結(jié)束條件是事件鏈表為空也就是說所有已經(jīng)到達(dá)的客戶都已經(jīng)被服務(wù)完畢。這里不存在“營業(yè)時間結(jié)束就強(qiáng)制結(jié)束”的問題因?yàn)殂y行關(guān)門之后不再生成新到達(dá)事件但已經(jīng)在隊(duì)列里的人會繼續(xù)被服務(wù)直到清空。從時間推進(jìn)的方式也能看出離散事件模擬的精髓now不是均勻遞增的而是直接跳到下一個事件發(fā)生的時刻。如果兩個事件之間間隔了100分鐘這100分鐘幾乎是瞬間被跨過。這種設(shè)計(jì)讓整個模擬的效率極高。3.4 到達(dá)事件與空閑窗口分配當(dāng)取出一個到達(dá)事件時處理邏輯可以拆成兩個步驟第一步嘗試為這位客戶分配空閑窗口第二步生成下一位客戶的到達(dá)事件。第一步的細(xì)節(jié)是如果找到空閑窗口立刻讓客戶開始服務(wù)并生成一個離開事件如果沒有空閑窗口把客戶放入等待隊(duì)列。核心代碼思路如下void handle_arrival(double now) { int customer nextCustomer; totalCustomers; int freeWin find_free_window(); if (freeWin 0) { start_service(freeWin, now); } else { enqueue(customer, now); } if (now SIM_TIME) { double next_arrive now exponential_random(ARRIVE_RATE); if (next_arrive SIM_TIME) { insertEvent(next_arrive, 0, -1, customer); } } }這里有一個容易被忽略的細(xì)節(jié)生成下一位到達(dá)事件時要用新生成的隨機(jī)間隔加到當(dāng)前時間上而不是用固定間隔。很多入門實(shí)現(xiàn)圖省事直接每隔固定分鐘數(shù)插入一個到達(dá)事件這樣模擬結(jié)果看起來“很整齊”但實(shí)際上丟失了隨機(jī)性。實(shí)驗(yàn)要求學(xué)生理解泊松過程就應(yīng)該用指數(shù)分布間隔。另一個細(xì)節(jié)是如果當(dāng)前時間已經(jīng)超過了模擬總時長就不再生成下一個到達(dá)事件了但窗口服務(wù)還在繼續(xù)。判斷條件是next_arrive SIM_TIME而不是now SIM_TIME。因?yàn)榧词巩?dāng)前事件還在一分鐘前下一個隨機(jī)間隔也可能讓到達(dá)時間越過營業(yè)結(jié)束點(diǎn)這種情況下客戶不應(yīng)該再進(jìn)銀行。3.5 離開事件與隊(duì)列取出離開事件發(fā)生時意味著某個窗口的服務(wù)已經(jīng)完成。處理邏輯是把對應(yīng)窗口置為空閑然后立刻檢查等待隊(duì)列里有沒有人。如果隊(duì)列非空就從隊(duì)頭取出一個客戶計(jì)算他的等待時間安排他開始服務(wù)并生成一個新的離開事件如果隊(duì)列為空窗口就保持空閑。void handle_departure(double now, int windowId) { windows[windowId].busy 0; if (queueHead ! NULL) { QueueNode *q dequeue(); double wait_time now - q-arriveTime; totalWaitTime wait_time; servedCustomers; serve_customer(windowId, now); free(q); } }這里有一個非常重要的順序問題必須先置空閑再取隊(duì)首客戶。如果反過來取隊(duì)首時發(fā)現(xiàn)沒有隊(duì)列邏輯上也對但如果有隊(duì)列你會直接從隊(duì)列取人卻忘了把窗口狀態(tài)改回忙碌導(dǎo)致后一個到達(dá)事件又分配同一個窗口。這種bug很難肉眼發(fā)現(xiàn)因?yàn)槌绦虿粫乐粫y(tǒng)計(jì)結(jié)果異常。離開事件處理完畢之后主循環(huán)會繼續(xù)取下一個事件。新生成的離開事件通過insertEvent按時間排入鏈表因此所有事件都會按發(fā)生先后順序被處理。哪怕一位客戶的離開時間比另一個新客戶的到達(dá)時間更早鏈表也會自動保證順序。3.6 統(tǒng)計(jì)指標(biāo)計(jì)算平均值也講究策略平均等待時間相對簡單在每個客戶出隊(duì)時計(jì)算出該客戶的等待時間累加后除以服務(wù)客戶數(shù)即可。窗口利用率則是每個窗口的累計(jì)服務(wù)時間除以總模擬時間這里總模擬時間指的是最后一個事件結(jié)束的時間而不是預(yù)設(shè)的SIM_TIME。如果隊(duì)列在營業(yè)時間結(jié)束后很久才清空那總模擬時間等于最后一個客戶離開時間這一點(diǎn)需要格外注意。平均隊(duì)列長度則是一個容易做錯的統(tǒng)計(jì)量。很多人拿到隊(duì)列長度變化直接求算術(shù)平均比如在10個事件點(diǎn)采樣隊(duì)列長度加起來除以10。這樣做是錯的因?yàn)閮纱问录g的時間間隔不一樣。隊(duì)列長度為3的時間段可能持續(xù)100分鐘隊(duì)列長度為1的時間段可能只持續(xù)0.5分鐘簡單算術(shù)平均會被短時間段的數(shù)值嚴(yán)重誤導(dǎo)。正確做法是時間加權(quán)平均。維護(hù)兩個變量上一次事件時間lastTime和當(dāng)前隊(duì)列長度queueLen。每當(dāng)取出新事件時將累計(jì)量增加queueAccum curQueueLen * (now - lastTime); lastTime now;當(dāng)整個模擬結(jié)束時平均隊(duì)列長度 queueAccum / (lastEventTime - initialTime)。這種做法的道理其實(shí)很簡單它把“隊(duì)列長度”在時間軸上畫成一條階梯曲線然后求這條曲線下的面積再除以總時長。這也是專業(yè)離散事件模擬工具里的標(biāo)準(zhǔn)做法。4. 示例代碼與運(yùn)行效果4.1 核心代碼骨架下面給出一段半偽代碼結(jié)構(gòu)的示例函數(shù)名和結(jié)構(gòu)體定義與前面的思路一致。要直接運(yùn)行的話需要把find_free_window、serve_customer等輔助函數(shù)補(bǔ)全但核心邏輯就在這里。#include stdio.h #include stdlib.h #include math.h #define WINDOW_NUM 3 #define SIM_TIME 480.0 #define ARRIVE_RATE 0.5 // 客戶到達(dá)率平均間隔2分鐘 #define SERVICE_RATE 0.3 // 服務(wù)率平均服務(wù)3.33分鐘 typedef struct Event { double time; int type; // 0到達(dá) 1離開 int window; int customer; struct Event *next; } Event; typedef struct QNode { int customer; double arriveTime; struct QNode *next; } QNode; typedef struct { int busy; double workTime; int servedCount; } Window; Event *eventList; QNode *queueHead, *queueTail; Window windows[WINDOW_NUM]; int nextCustomer 1; int totalCustomers 0; double totalWaitTime 0.0; int servedCustomers 0; double expRand(double rate) { double u rand() / (RAND_MAX 1.0); if (u 0.0) u 1e-12; return -log(1.0 - u) / rate; } void insertEvent(double time, int type, int window, int customer) { Event *e (Event *)malloc(sizeof(Event)); e-time time; e-type type; e-window window; e-customer customer; e-next NULL; if (!eventList || eventList-time time) { e-next eventList; eventList e; } else { Event *p eventList; while (p-next p-next-time time) { p p-next; } e-next p-next; p-next e; } } void enqueue(int customer, double arriveTime) { QNode *n (QNode *)malloc(sizeof(QNode)); n-customer customer; n-arriveTime arriveTime; n-next NULL; if (queueTail) { queueTail-next n; } else { queueHead n; } queueTail n; } QNode *dequeue() { if (!queueHead) return NULL; QNode *n queueHead; queueHead n-next; if (!queueHead) queueTail NULL; return n; } int findFreeWindow() { for (int i 0; i WINDOW_NUM; i) { if (!windows[i].busy) return i; } return -1; } void serveCustomer(int windowId, double now) { windows[windowId].busy 1; double serveTime expRand(SERVICE_RATE); windows[windowId].workTime serveTime; windows[windowId].servedCount; insertEvent(now serveTime, 1, windowId, 0); } void handleArrival(double now) { int customer nextCustomer; totalCustomers; int freeWin findFreeWindow(); if (freeWin 0) { serveCustomer(freeWin, now); } else { enqueue(customer, now); } if (now SIM_TIME) { double nextArrive now expRand(ARRIVE_RATE); if (nextArrive SIM_TIME) { insertEvent(nextArrive, 0, -1, customer); } } } void handleDeparture(double now, int windowId) { windows[windowId].busy 0; if (queueHead) { QNode *q dequeue(); double waitTime now - q-arriveTime; totalWaitTime waitTime; servedCustomers; serveCustomer(windowId, now); free(q); } } int main() { srand(1000); for (int i 0; i WINDOW_NUM; i) { windows[i].busy 0; windows[i].workTime 0.0; windows[i].servedCount 0; } insertEvent(0, 0, -1, 0); double now 0.0; double lastTime 0.0; double queueAccum 0.0; int curQueueLen 0; while (eventList) { Event *ev eventList; eventList ev-next; now ev-time; queueAccum curQueueLen * (now - lastTime); lastTime now; if (ev-type 0) { handleArrival(now); } else { handleDeparture(now, ev-window); } // 重新統(tǒng)計(jì)隊(duì)列長度需要在外面維護(hù)一個輔助函數(shù) // curQueueLen queueLength(); free(ev); } double avgWait servedCustomers ? totalWaitTime / servedCustomers : 0; double avgQueueLen queueAccum / (now - 0); double totalSimTime now; printf(總客戶數(shù): %d\n, totalCustomers); printf(接受服務(wù)客戶數(shù): %d\n, servedCustomers); printf(平均等待時間: %.2f 分鐘\n, avgWait); printf(平均隊(duì)列長度: %.2f 人\n, avgQueueLen); for (int i 0; i WINDOW_NUM; i) { printf(窗口%d利用率: %.2f\n, i 1, windows[i].workTime / totalSimTime); } return 0; }這段代碼要直接編譯還需要補(bǔ)一個queueLength函數(shù)邏輯是用一個遍歷函數(shù)數(shù)一下當(dāng)前隊(duì)列節(jié)點(diǎn)數(shù)。不過更優(yōu)雅的做法是在主循環(huán)外部維護(hù)一個計(jì)數(shù)器入隊(duì)時1出隊(duì)時-1這樣統(tǒng)計(jì)隊(duì)列長度的時間復(fù)雜度是O(1)。我給的骨架里沒有寫這個計(jì)數(shù)器但實(shí)際項(xiàng)目里一定要加因?yàn)樗粌H用于平均隊(duì)列長度統(tǒng)計(jì)也能避免每個事件都去遍歷鏈表浪費(fèi)不必要的時間。4.2 運(yùn)行結(jié)果樣例與解讀固定隨機(jī)種子運(yùn)行一次輸出大概長這樣總客戶數(shù): 248 接受服務(wù)客戶數(shù): 248 平均等待時間: 3.87 分鐘 平均隊(duì)列長度: 1.72 人 窗口1利用率: 0.74 窗口2利用率: 0.69 窗口3利用率: 0.71這個結(jié)果是比較合理的。平均到達(dá)間隔2分鐘服務(wù)一位大約3.33分鐘三個窗口合起來的服務(wù)能力是每分鐘0.9個客戶而客戶到達(dá)率是每分鐘0.5個服務(wù)能力明顯過剩所以隊(duì)列不會堆積。如果平均等待時間漲到幾十分鐘大概率是參數(shù)寫成了“平均間隔0.5”之類的錯誤導(dǎo)致客戶大量涌入。我建議拿到結(jié)果后先做一次“合理性校驗(yàn)”用到達(dá)率除以總服務(wù)能力得出系統(tǒng)負(fù)載率。上述參數(shù)下負(fù)載率是0.5/0.9約等于0.56平均隊(duì)列長度應(yīng)該在一個較低的數(shù)值。一旦模擬結(jié)果和粗略計(jì)算差很多優(yōu)先檢查隨機(jī)數(shù)參數(shù)。4.3 參數(shù)調(diào)整實(shí)驗(yàn)從模擬看系統(tǒng)瓶頸做完基本實(shí)驗(yàn)后我建議順手做幾組對照實(shí)驗(yàn)這部分內(nèi)容放進(jìn)實(shí)驗(yàn)報(bào)告會非常有說服力。比如把窗口數(shù)從3改成2負(fù)載率變成0.5/0.6約等于0.83平均等待時間和平均隊(duì)列長度會明顯上升。再把窗口數(shù)改成4負(fù)載率降到0.42等待時間會大幅下降但窗口利用率也下降說明資源出現(xiàn)冗余。這就是離散事件模擬在現(xiàn)實(shí)中最常見的用途資源配置決策。銀行經(jīng)理不知道到底該開幾個窗口靠直覺拍板容易出錯把客戶到達(dá)率、服務(wù)率輸進(jìn)模擬器跑一遍就能看到平均等待時間變化。雖然課程實(shí)驗(yàn)只是模擬一個簡單銀行但方法論是可以直接遷移到機(jī)場值機(jī)柜臺、倉庫分揀線、服務(wù)器集群調(diào)度這些場景里的。5. 常見問題與調(diào)試技巧5.1 死循環(huán)和時間回退寫這個模擬最容易遇到的崩潰型問題是程序跑不完。原因往往不是有人忘了釋放內(nèi)存而是事件鏈表里出現(xiàn)了“時間回退”的事件。比如一個離開事件的時間是103.2而某個到達(dá)事件的時間也是103.2這沒關(guān)系但如果你生成的隨機(jī)服務(wù)時間是負(fù)數(shù)或者參數(shù)填錯導(dǎo)致下一個到達(dá)時間比當(dāng)前時間還要小事件鏈表就會陷入不斷重復(fù)處理同一個事件的死循環(huán)。排查時最簡單的方法是打印每個事件的時間和類型。在while循環(huán)里加一行printf(%.2f type%d\n, ev-time, ev-type)觀察時間序列是否始終單調(diào)遞增。如果發(fā)現(xiàn)某次時間相同或變小立刻回頭看這次的事件是怎么生成的。我調(diào)試時曾經(jīng)遇到過一個很隱蔽的問題把平均到達(dá)間隔當(dāng)成到達(dá)率用導(dǎo)致平均間隔變成0.5分鐘到達(dá)事件瘋狂生成程序活活跑了好幾分鐘還在繼續(xù)輸出客戶數(shù)。改成正確的參數(shù)后幾秒內(nèi)就出結(jié)果了。5.2 平均隊(duì)列長度算不準(zhǔn)很多人在統(tǒng)計(jì)平均隊(duì)列長度時直接在每個事件處理完以后把隊(duì)列長度累加最后除以總事件數(shù)。這樣算出來可能和正確值差一大截。比如隊(duì)列長度5持續(xù)了100分鐘隊(duì)列長度0持續(xù)了10分鐘事件總數(shù)只有兩部算術(shù)平均是2.5但真實(shí)的平均隊(duì)列長度接近4.55。這個差距對實(shí)驗(yàn)報(bào)告的影響很大。正確做法是時間加權(quán)平均。如果你在代碼里沒有維護(hù)lastTime和queueAccum可以這樣實(shí)現(xiàn)取出事件后先計(jì)算一個“面積貢獻(xiàn)”再更新lastTime為當(dāng)前事件時間。我一開始犯錯就是因?yàn)榘选懊總€事件的隊(duì)尾長度”當(dāng)成了“時間段內(nèi)的代表值”想明白之后才發(fā)現(xiàn)原來只是乘法問題。實(shí)驗(yàn)報(bào)告里寫上這個統(tǒng)計(jì)原理老師通常會認(rèn)為你真正理解了離散事件模擬。5.3 隨機(jī)數(shù)種子與結(jié)果復(fù)現(xiàn)使用srand(time(NULL))會讓每次運(yùn)行結(jié)果都不一樣。對實(shí)驗(yàn)來說一個常見需求是“復(fù)現(xiàn)同一個bug”或“提交穩(wěn)定數(shù)據(jù)”這時期望保證每次運(yùn)行結(jié)果一致。只需要把隨機(jī)種子改成固定值比如srand(2024)。固定種子后相同參數(shù)、相同代碼一定產(chǎn)生相同結(jié)果方便比較不同窗口數(shù)對結(jié)果的影響。另外rand()生成的隨機(jī)數(shù)質(zhì)量對大規(guī)模模擬有一定影響尤其是當(dāng)你模擬百萬級客戶時低16位的隨機(jī)性可能會不夠。但對操作系統(tǒng)課程實(shí)驗(yàn)來說標(biāo)準(zhǔn)庫已經(jīng)足夠。更講究一點(diǎn)的做法是使用自定義的隨機(jī)數(shù)生成器比如梅森旋轉(zhuǎn)算法或PCG。不過我不建議在課程實(shí)驗(yàn)里額外引入復(fù)雜隨機(jī)庫因?yàn)槔蠋熞吹暮诵氖悄M邏輯不是隨機(jī)數(shù)質(zhì)量。5.4 內(nèi)存釋放與大型模擬優(yōu)化思路事件節(jié)點(diǎn)和隊(duì)列節(jié)點(diǎn)都是malloc出來的如果處理完不free程序在小規(guī)模模擬中可能看不出來但如果模擬幾萬客戶內(nèi)存占用會持續(xù)增長。我的習(xí)慣是在popEvent之后、處理完事件后立即free在dequeue之后、使用完節(jié)點(diǎn)信息后立即free。這樣可以保證內(nèi)存使用量跟事件鏈表的當(dāng)前長度相關(guān)而不是跟歷史事件總數(shù)相關(guān)。如果以后要做更大規(guī)模的模擬事件鏈表每次插入都是O(n)性能會隨著事件數(shù)量上升而下降。更好的方案是使用最小堆或優(yōu)先隊(duì)列來管理事件。C語言里手寫一個二叉堆并不難核心操作是sift-up和sift-down插入和取出都是O(logn)。在課程實(shí)驗(yàn)階段先把鏈表版本跑通再考慮優(yōu)化不要一開始就追求復(fù)雜結(jié)構(gòu)否則調(diào)試難度會成倍上升。6. 寫在最后的調(diào)試心得這個實(shí)驗(yàn)我前后改了三個版本。第一版把所有代碼堆在main函數(shù)里邏輯全揉成一團(tuán)調(diào)試時看一眼就頭大。第二版拆成了函數(shù)但統(tǒng)計(jì)隊(duì)列長度時還在用算術(shù)平均數(shù)據(jù)怎么都不對。第三版才真正理解時間加權(quán)平均又把隨機(jī)數(shù)種子固定下來最后跑出的結(jié)果才算穩(wěn)定。我個人的體會是這類模擬題真正卡人的地方不是語法而是“事件推進(jìn)”和“狀態(tài)統(tǒng)計(jì)”這兩個思維模型。只要想清楚每個事件的副作用是什么、每個統(tǒng)計(jì)量應(yīng)該怎么在時間軸上加權(quán)代碼只是順帶的事。最后再分享一個小技巧調(diào)試時把所有關(guān)鍵日志加個開關(guān)比如定義DEBUG宏時輸出每個事件的時間、類型、窗口編號、隊(duì)列長度發(fā)布最終版本時關(guān)掉這個宏。這種做法在大型軟件工程里叫日志分級放在課程實(shí)驗(yàn)里也同樣實(shí)用。它可以幫助你把一次運(yùn)行過程完整復(fù)盤而不是靠猜去定位bug。如果你正在做類似的模擬實(shí)驗(yàn)可以照著這個思路先把數(shù)據(jù)結(jié)構(gòu)定下來再去填充事件處理的細(xì)節(jié)。之前沒有接觸過離散事件模擬也沒關(guān)系這個實(shí)驗(yàn)就是讓你通過銀行排隊(duì)模型逐步建立事件驅(qū)動的直覺。等以后學(xué)到進(jìn)程調(diào)度、報(bào)文轉(zhuǎn)發(fā)、連接池管理這些概念時你會發(fā)現(xiàn)它們跟銀行排隊(duì)的本質(zhì)問題一模一樣那時候你就能體會到這門實(shí)驗(yàn)課真正的價值了。