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