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