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