公平隊列C/C++實現(xiàn)：從排隊論到可運行代碼的完整落地)
簡介本資源為WFQ加權(quán)公平隊列算法的C/C實現(xiàn)工程面向網(wǎng)絡(luò)協(xié)議學(xué)習(xí)者、路由與流量調(diào)度方向的開發(fā)者及課程設(shè)計人員用于理解并復(fù)現(xiàn)多路復(fù)用網(wǎng)絡(luò)中按權(quán)重公平分配帶寬的調(diào)度機制。工程同時覆蓋發(fā)送端、接收端與路由器轉(zhuǎn)發(fā)三部分將數(shù)據(jù)包分類、權(quán)重分配、隊列調(diào)度與循環(huán)監(jiān)控等關(guān)鍵環(huán)節(jié)落地為可編譯運行的代碼并與FIFO策略形成對照便于分析公平性與服務(wù)質(zhì)量差異。壓縮包共344個文件約14.98MB以cpp與c源碼、h頭文件為主體輔以obj、exe、pdb等編譯產(chǎn)物及dsp、dsw工程文件另有rc資源、txt說明與doc文檔結(jié)構(gòu)完整、便于直接打開工程調(diào)試。目前已有958人學(xué)習(xí)下載適合作為網(wǎng)絡(luò)調(diào)度算法入門實踐與二次開發(fā)的參考樣例。1. WFQ算法實現(xiàn)c/c從排隊論到可運行代碼的完整落地很多開發(fā)者第一次接觸 QoS 調(diào)度時都會被 WFQWeighted Fair Queueing加權(quán)公平隊列這個名字唬住以為它只是網(wǎng)絡(luò)設(shè)備里的黑匣子。實際上WFQ 的核心思想非常樸素給每個數(shù)據(jù)流分配一個權(quán)重按權(quán)重比例分配帶寬同時保證低權(quán)重流不會被高權(quán)重流徹底餓死。這套 C/C 實現(xiàn)把 WFQ 從論文公式拉到了可編譯、可調(diào)試、可改造的工程代碼層面適合正在做網(wǎng)絡(luò)協(xié)議棧、流量調(diào)度、嵌入式網(wǎng)關(guān)或軟交換二次開發(fā)的工程師。你拿到手就能跑改幾個參數(shù)就能看到不同權(quán)重下的調(diào)度差異不用先去啃 RFC 文檔。2. 項目架構(gòu)拆解WFQ 調(diào)度器的模塊劃分與數(shù)據(jù)結(jié)構(gòu)2.1 整體架構(gòu)與文件組織這份 WFQ 實現(xiàn)采用經(jīng)典的 C/C 混合風(fēng)格核心邏輯用 C 寫對外接口和測試用例用 C 封裝。目錄結(jié)構(gòu)大致如下wfq/ ├── include/ │ ├── wfq.h # 對外接口初始化、入隊、出隊、權(quán)重設(shè)置 │ ├── packet.h # 數(shù)據(jù)包結(jié)構(gòu)定義 │ └── queue.h # 隊列節(jié)點與鏈表操作 ├── src/ │ ├── wfq.c # WFQ 核心調(diào)度算法 │ ├── queue.c # 隊列管理入隊、出隊、排序 │ └── packet.c # 數(shù)據(jù)包構(gòu)造與銷毀 ├── test/ │ ├── test_wfq.cpp # 單元測試權(quán)重比例驗證 │ └── demo.cpp # 演示程序模擬多流調(diào)度 ├── Makefile └── README.md這種分層的好處是wfq.c只關(guān)心調(diào)度邏輯queue.c只關(guān)心數(shù)據(jù)結(jié)構(gòu)packet.c只關(guān)心數(shù)據(jù)包生命周期。二次開發(fā)時你要換調(diào)度策略只動wfq.c要換底層隊列實現(xiàn)比如從鏈表換成環(huán)形緩沖區(qū)只動queue.c。常見做法是把虛擬時間計算和隊列選擇分開這樣調(diào)試時能單獨打印每個流的虛擬時間快速定位是權(quán)重算錯了還是隊列排序錯了。2.2 核心數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)包與流隊列WFQ 的調(diào)度精度取決于兩個東西數(shù)據(jù)包的元信息是否完整以及每個流的隊列是否維護了正確的虛擬時間。先看數(shù)據(jù)包結(jié)構(gòu)// include/packet.h typedef struct Packet { int flow_id; // 流標(biāo)識用于區(qū)分不同隊列 int length; // 包長字節(jié)影響虛擬時間增量 int weight; // 該流對應(yīng)的權(quán)重 double virtual_time; // 該包到達時的虛擬時間 struct Packet *next; // 鏈表指針 } Packet;flow_id是流的唯一標(biāo)識調(diào)度器靠它找到對應(yīng)隊列。length直接參與虛擬時間計算——包越長占用帶寬越多虛擬時間推進越快。weight決定該流在總帶寬中的占比。virtual_time是 WFQ 的靈魂字段每個包入隊時都會根據(jù)當(dāng)前流的虛擬時間和包長算出一個新的虛擬時間出隊時選虛擬時間最小的包。再看流隊列結(jié)構(gòu)// include/queue.h typedef struct FlowQueue { int flow_id; int weight; double virtual_time; // 該流當(dāng)前虛擬時間 Packet *head; // 隊頭 Packet *tail; // 隊尾 int packet_count; // 隊列長度用于統(tǒng)計 } FlowQueue;每個流一個FlowQueue里面維護自己的virtual_time。這個虛擬時間不是全局時鐘而是該流“應(yīng)該”推進到的位置。權(quán)重越大虛擬時間推進越慢因為同樣的包長除以更大的權(quán)重增量更小。這樣高權(quán)重流的包虛擬時間更小更容易被優(yōu)先調(diào)度但低權(quán)重流也不會永遠排不上——因為它的虛擬時間也在推進只是慢一點。2.3 虛擬時間計算WFQ 的數(shù)學(xué)核心WFQ 的公平性全靠虛擬時間公式virtual_time_new virtual_time_old packet_length / weight這個公式的含義是包長越大虛擬時間增量越大權(quán)重越大增量越小。調(diào)度器每次從所有非空隊列中選虛擬時間最小的隊頭包出隊。// src/wfq.c double calc_virtual_time(FlowQueue *fq, int packet_len) { // 虛擬時間增量 包長 / 權(quán)重 // 權(quán)重越大增量越小該流越容易被調(diào)度 double increment (double)packet_len / (double)fq-weight; return fq-virtual_time increment; }參數(shù)說明fq是流隊列指針packet_len是當(dāng)前包長。返回值是該包的新虛擬時間。注意這里用double而不是int因為權(quán)重比可能是 1:3:5 這種非整數(shù)關(guān)系用整數(shù)會丟精度導(dǎo)致調(diào)度結(jié)果和理論值偏差越來越大。我一般會在調(diào)試時把每個包的虛擬時間打印出來和手算結(jié)果對一遍確認公式?jīng)]寫錯。2.4 入隊與出隊調(diào)度器的兩個關(guān)鍵動作入隊邏輯負責(zé)把包掛到對應(yīng)流隊列并更新該流的虛擬時間// src/wfq.c int wfq_enqueue(WFQ_Scheduler *sched, Packet *pkt) { FlowQueue *fq find_flow_queue(sched, pkt-flow_id); if (!fq) return -1; // 流不存在需要先注冊 // 計算該包的虛擬時間 pkt-virtual_time calc_virtual_time(fq, pkt-length); // 更新流隊列的虛擬時間 fq-virtual_time pkt-virtual_time; // 按虛擬時間插入隊列保持有序 insert_packet_sorted(fq, pkt); fq-packet_count; return 0; }出隊邏輯遍歷所有流隊列選虛擬時間最小的隊頭包// src/wfq.c Packet* wfq_dequeue(WFQ_Scheduler *sched) { FlowQueue *best_fq NULL; double min_vt 1e18; // 初始化為一個極大值 for (int i 0; i sched-flow_count; i) { FlowQueue *fq sched-flows[i]; if (fq-head NULL) continue; // 空隊列跳過 if (fq-head-virtual_time min_vt) { min_vt fq-head-virtual_time; best_fq fq; } } if (!best_fq) return NULL; // 所有隊列為空 Packet *pkt best_fq-head; best_fq-head pkt-next; if (best_fq-head NULL) best_fq-tail NULL; best_fq-packet_count--; return pkt; }這里有個細節(jié)insert_packet_sorted保證每個流隊列內(nèi)部按虛擬時間有序這樣出隊時只需要比較各隊頭不用遍歷整個隊列。如果流數(shù)量很多比如上千個流每次出隊都遍歷所有流會變成性能瓶頸。常見優(yōu)化是用最小堆維護各流隊頭的虛擬時間把 O(n) 降到 O(log n)。這份代碼為了可讀性先用線性掃描二次開發(fā)時可以替換。3. 編譯與運行從源碼到可執(zhí)行 Demo 的完整步驟3.1 環(huán)境準備與編譯命令這份代碼依賴很少Linux 下只需要 gcc/g 和 make。Windows 下可以用 MinGW 或 WSL。先確認工具鏈gcc --version g --version make --version進入項目根目錄直接執(zhí)行make clean makeMakefile 里默認編譯出兩個可執(zhí)行文件test_wfq和demo。test_wfq跑單元測試驗證權(quán)重比例是否正確demo模擬三個流不同權(quán)重的調(diào)度過程打印每個包的出隊順序。如果編譯報錯undefined reference to calc_virtual_time說明wfq.c沒被鏈接進去檢查 Makefile 的SRCS變量是否包含src/wfq.c。這是最常見的翻車點尤其是手動改過目錄結(jié)構(gòu)之后。3.2 運行 Demo 與結(jié)果解讀編譯成功后運行./demo輸出大致如下Flow 1 (weight1): packet 1, vt100.00 Flow 2 (weight2): packet 1, vt50.00 Flow 3 (weight3): packet 1, vt33.33 --- dequeue order --- Flow 3 packet 1 (vt33.33) Flow 2 packet 1 (vt50.00) Flow 1 packet 1 (vt100.00)這個結(jié)果說明權(quán)重 3 的流虛擬時間最小最先出隊權(quán)重 1 的流虛擬時間最大最后出隊。如果三個流持續(xù)有包長期來看出隊包的數(shù)量比會接近 3:2:1這就是 WFQ 的加權(quán)公平性。你可以改demo.cpp里的權(quán)重值重新編譯運行觀察調(diào)度順序變化。比如把 Flow 1 的權(quán)重改成 10它會變成最先出隊的流。這種即時反饋對理解 WFQ 非常有用。3.3 單元測試驗證權(quán)重比例test_wfq.cpp里構(gòu)造了固定包長的多流場景統(tǒng)計一段時間內(nèi)各流出隊包數(shù)和理論比例對比// test/test_wfq.cpp void test_weight_proportion() { WFQ_Scheduler sched; wfq_init(sched); wfq_add_flow(sched, 1, 1); // flow 1, weight 1 wfq_add_flow(sched, 2, 2); // flow 2, weight 2 wfq_add_flow(sched, 3, 3); // flow 3, weight 3 // 每個流各入隊 100 個包 for (int i 0; i 100; i) { wfq_enqueue(sched, make_packet(1, 1000)); wfq_enqueue(sched, make_packet(2, 1000)); wfq_enqueue(sched, make_packet(3, 1000)); } int count[4] {0}; Packet *pkt; while ((pkt wfq_dequeue(sched)) ! NULL) { count[pkt-flow_id]; free(pkt); } // 理論比例 1:2:3允許 5% 誤差 assert(abs(count[1] - 50) 5); assert(abs(count[2] - 100) 5); assert(abs(count[3] - 150) 5); }這個測試跑通說明虛擬時間計算和出隊選擇邏輯是對的。如果斷言失敗先檢查calc_virtual_time里的除法是不是寫成了整數(shù)除法再檢查insert_packet_sorted有沒有正確排序。4. 避坑與常見問題WFQ 實現(xiàn)里最容易翻車的幾個點4.1 虛擬時間溢出或精度丟失現(xiàn)象跑長時間仿真后調(diào)度順序開始混亂高權(quán)重流反而排不過低權(quán)重流。原因virtual_time用float而不是double累加幾千次后精度不夠或者用int存虛擬時間包長除以權(quán)重后直接截斷成整數(shù)。解決統(tǒng)一用double并且在每次入隊時檢查虛擬時間是否超過閾值比如 1e12超過就所有流的虛擬時間同時減去一個基準值防止溢出。這個操作叫“虛擬時間重歸一化”生產(chǎn)環(huán)境必須做。4.2 權(quán)重為 0 導(dǎo)致除零崩潰現(xiàn)象程序在calc_virtual_time里直接 segfault。原因注冊流的時候沒校驗權(quán)重傳了 0 進去除法直接崩。解決wfq_add_flow里加斷言或返回錯誤碼權(quán)重必須大于 0。如果業(yè)務(wù)上確實需要“暫?！蹦硞€流應(yīng)該把它從調(diào)度器里移除而不是設(shè)權(quán)重為 0。4.3 隊列排序不穩(wěn)定導(dǎo)致同虛擬時間包順序錯亂現(xiàn)象兩個包虛擬時間相同出隊順序隨機測試結(jié)果不穩(wěn)定。原因insert_packet_sorted用的是而不是導(dǎo)致相同虛擬時間的包插到了前面破壞了 FIFO 語義。解決排序時用嚴格小于相同虛擬時間的包按入隊順序排列。WFQ 本身不保證相同虛擬時間的順序但工程實現(xiàn)里保持 FIFO 更符合直覺也方便調(diào)試。4.4 流數(shù)量多時出隊性能急劇下降現(xiàn)象流數(shù)量從 10 增加到 1000 后出隊耗時從微秒級漲到毫秒級。原因wfq_dequeue每次遍歷所有流找最小虛擬時間復(fù)雜度 O(n)。解決引入最小堆或紅黑樹維護各流隊頭虛擬時間出隊復(fù)雜度降到 O(log n)。這份代碼為了可讀性先用線性掃描二次開發(fā)時如果流數(shù)量超過 100建議直接換堆實現(xiàn)。4.5 內(nèi)存泄漏出隊后忘記釋放包現(xiàn)象長時間運行后 RSS 持續(xù)上漲最終 OOM。原因wfq_dequeue返回的Packet*是堆分配的調(diào)用方用完必須free。Demo 里釋放了但集成到實際項目時經(jīng)常漏掉。解決在wfq_dequeue內(nèi)部不釋放由調(diào)用方負責(zé)或者提供wfq_dequeue_and_free接口把釋放邏輯封裝進去。我一般會在測試里用 valgrind 跑一遍確認沒有 definitely lost。5. 二次開發(fā)與改造把 WFQ 塞進你自己的項目5.1 替換底層隊列從鏈表到環(huán)形緩沖區(qū)這份代碼用鏈表實現(xiàn)流隊列好處是插入刪除 O(1)壞處是緩存不友好。如果你的場景是固定包長、高吞吐可以把FlowQueue里的鏈表換成環(huán)形緩沖區(qū)typedef struct RingBuffer { Packet *buf; int capacity; int head; int tail; int count; } RingBuffer;入隊時tail (tail 1) % capacity出隊時head (head 1) % capacity。注意環(huán)形緩沖區(qū)滿了之后要么丟包要么阻塞WFQ 本身不處理擁塞需要你在上層加策略。5.2 支持動態(tài)權(quán)重調(diào)整實際網(wǎng)絡(luò)里流的權(quán)重可能隨時變化。你可以在FlowQueue里加一個pending_weight字段入隊時如果發(fā)現(xiàn)權(quán)重變了先按舊權(quán)重把當(dāng)前隊列的虛擬時間重算一遍再切到新權(quán)重。重算邏輯void update_flow_weight(FlowQueue *fq, int new_weight) { if (new_weight 0) return; double ratio (double)fq-weight / (double)new_weight; fq-virtual_time * ratio; // 按比例縮放虛擬時間 fq-weight new_weight; }這個縮放保證權(quán)重切換時不會出現(xiàn)虛擬時間跳變調(diào)度順序平滑過渡。5.3 驗證改造是否正確三個必跑測試改完代碼后至少跑這三個測試測試項目的預(yù)期結(jié)果權(quán)重比例測試驗證調(diào)度公平性出隊包數(shù)比接近權(quán)重比空隊列測試驗證邊界條件所有隊列為空時返回 NULL不崩潰長時間運行測試驗證虛擬時間不溢出跑 100 萬包后調(diào)度順序仍正確我一般會在 CI 里掛一個 10 萬包的回歸測試每次提交都跑一遍。有一次改排序邏輯把寫成單元測試沒覆蓋到相同虛擬時間的場景結(jié)果上線后調(diào)度順序全亂。從那以后我每次改insert_packet_sorted都強制走一遍相同虛擬時間的用例確認 FIFO 語義沒丟。希望幫到你。本文還有配套的精品資源點擊獲取 WFQ加權(quán)公平隊列C/C++實現(xiàn)：從排隊論到可運行代碼的完整落地
簡介本資源為WFQ加權(quán)公平隊列算法的C/C實現(xiàn)工程面向網(wǎng)絡(luò)協(xié)議學(xué)習(xí)者、路由與流量調(diào)度方向的開發(fā)者及課程設(shè)計人員用于理解并復(fù)現(xiàn)多路復(fù)用網(wǎng)絡(luò)中按權(quán)重公平分配帶寬的調(diào)度機制。工程同時覆蓋發(fā)送端、接收端與路由器轉(zhuǎn)發(fā)三部分將數(shù)據(jù)包分類、權(quán)重分配、隊列調(diào)度與循環(huán)監(jiān)控等關(guān)鍵環(huán)節(jié)落地為可編譯運行的代碼并與FIFO策略形成對照便于分析公平性與服務(wù)質(zhì)量差異。壓縮包共344個文件約14.98MB以cpp與c源碼、h頭文件為主體輔以obj、exe、pdb等編譯產(chǎn)物及dsp、dsw工程文件另有rc資源、txt說明與doc文檔結(jié)構(gòu)完整、便于直接打開工程調(diào)試。目前已有958人學(xué)習(xí)下載適合作為網(wǎng)絡(luò)調(diào)度算法入門實踐與二次開發(fā)的參考樣例。1. WFQ算法實現(xiàn)c/c從排隊論到可運行代碼的完整落地很多開發(fā)者第一次接觸 QoS 調(diào)度時都會被 WFQWeighted Fair Queueing加權(quán)公平隊列這個名字唬住以為它只是網(wǎng)絡(luò)設(shè)備里的黑匣子。實際上WFQ 的核心思想非常樸素給每個數(shù)據(jù)流分配一個權(quán)重按權(quán)重比例分配帶寬同時保證低權(quán)重流不會被高權(quán)重流徹底餓死。這套 C/C 實現(xiàn)把 WFQ 從論文公式拉到了可編譯、可調(diào)試、可改造的工程代碼層面適合正在做網(wǎng)絡(luò)協(xié)議棧、流量調(diào)度、嵌入式網(wǎng)關(guān)或軟交換二次開發(fā)的工程師。你拿到手就能跑改幾個參數(shù)就能看到不同權(quán)重下的調(diào)度差異不用先去啃 RFC 文檔。2. 項目架構(gòu)拆解WFQ 調(diào)度器的模塊劃分與數(shù)據(jù)結(jié)構(gòu)2.1 整體架構(gòu)與文件組織這份 WFQ 實現(xiàn)采用經(jīng)典的 C/C 混合風(fēng)格核心邏輯用 C 寫對外接口和測試用例用 C 封裝。目錄結(jié)構(gòu)大致如下wfq/ ├── include/ │ ├── wfq.h # 對外接口初始化、入隊、出隊、權(quán)重設(shè)置 │ ├── packet.h # 數(shù)據(jù)包結(jié)構(gòu)定義 │ └── queue.h # 隊列節(jié)點與鏈表操作 ├── src/ │ ├── wfq.c # WFQ 核心調(diào)度算法 │ ├── queue.c # 隊列管理入隊、出隊、排序 │ └── packet.c # 數(shù)據(jù)包構(gòu)造與銷毀 ├── test/ │ ├── test_wfq.cpp # 單元測試權(quán)重比例驗證 │ └── demo.cpp # 演示程序模擬多流調(diào)度 ├── Makefile └── README.md這種分層的好處是wfq.c只關(guān)心調(diào)度邏輯queue.c只關(guān)心數(shù)據(jù)結(jié)構(gòu)packet.c只關(guān)心數(shù)據(jù)包生命周期。二次開發(fā)時你要換調(diào)度策略只動wfq.c要換底層隊列實現(xiàn)比如從鏈表換成環(huán)形緩沖區(qū)只動queue.c。常見做法是把虛擬時間計算和隊列選擇分開這樣調(diào)試時能單獨打印每個流的虛擬時間快速定位是權(quán)重算錯了還是隊列排序錯了。2.2 核心數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)包與流隊列WFQ 的調(diào)度精度取決于兩個東西數(shù)據(jù)包的元信息是否完整以及每個流的隊列是否維護了正確的虛擬時間。先看數(shù)據(jù)包結(jié)構(gòu)// include/packet.h typedef struct Packet { int flow_id; // 流標(biāo)識用于區(qū)分不同隊列 int length; // 包長字節(jié)影響虛擬時間增量 int weight; // 該流對應(yīng)的權(quán)重 double virtual_time; // 該包到達時的虛擬時間 struct Packet *next; // 鏈表指針 } Packet;flow_id是流的唯一標(biāo)識調(diào)度器靠它找到對應(yīng)隊列。length直接參與虛擬時間計算——包越長占用帶寬越多虛擬時間推進越快。weight決定該流在總帶寬中的占比。virtual_time是 WFQ 的靈魂字段每個包入隊時都會根據(jù)當(dāng)前流的虛擬時間和包長算出一個新的虛擬時間出隊時選虛擬時間最小的包。再看流隊列結(jié)構(gòu)// include/queue.h typedef struct FlowQueue { int flow_id; int weight; double virtual_time; // 該流當(dāng)前虛擬時間 Packet *head; // 隊頭 Packet *tail; // 隊尾 int packet_count; // 隊列長度用于統(tǒng)計 } FlowQueue;每個流一個FlowQueue里面維護自己的virtual_time。這個虛擬時間不是全局時鐘而是該流“應(yīng)該”推進到的位置。權(quán)重越大虛擬時間推進越慢因為同樣的包長除以更大的權(quán)重增量更小。這樣高權(quán)重流的包虛擬時間更小更容易被優(yōu)先調(diào)度但低權(quán)重流也不會永遠排不上——因為它的虛擬時間也在推進只是慢一點。2.3 虛擬時間計算WFQ 的數(shù)學(xué)核心WFQ 的公平性全靠虛擬時間公式virtual_time_new virtual_time_old packet_length / weight這個公式的含義是包長越大虛擬時間增量越大權(quán)重越大增量越小。調(diào)度器每次從所有非空隊列中選虛擬時間最小的隊頭包出隊。// src/wfq.c double calc_virtual_time(FlowQueue *fq, int packet_len) { // 虛擬時間增量 包長 / 權(quán)重 // 權(quán)重越大增量越小該流越容易被調(diào)度 double increment (double)packet_len / (double)fq-weight; return fq-virtual_time increment; }參數(shù)說明fq是流隊列指針packet_len是當(dāng)前包長。返回值是該包的新虛擬時間。注意這里用double而不是int因為權(quán)重比可能是 1:3:5 這種非整數(shù)關(guān)系用整數(shù)會丟精度導(dǎo)致調(diào)度結(jié)果和理論值偏差越來越大。我一般會在調(diào)試時把每個包的虛擬時間打印出來和手算結(jié)果對一遍確認公式?jīng)]寫錯。2.4 入隊與出隊調(diào)度器的兩個關(guān)鍵動作入隊邏輯負責(zé)把包掛到對應(yīng)流隊列并更新該流的虛擬時間// src/wfq.c int wfq_enqueue(WFQ_Scheduler *sched, Packet *pkt) { FlowQueue *fq find_flow_queue(sched, pkt-flow_id); if (!fq) return -1; // 流不存在需要先注冊 // 計算該包的虛擬時間 pkt-virtual_time calc_virtual_time(fq, pkt-length); // 更新流隊列的虛擬時間 fq-virtual_time pkt-virtual_time; // 按虛擬時間插入隊列保持有序 insert_packet_sorted(fq, pkt); fq-packet_count; return 0; }出隊邏輯遍歷所有流隊列選虛擬時間最小的隊頭包// src/wfq.c Packet* wfq_dequeue(WFQ_Scheduler *sched) { FlowQueue *best_fq NULL; double min_vt 1e18; // 初始化為一個極大值 for (int i 0; i sched-flow_count; i) { FlowQueue *fq sched-flows[i]; if (fq-head NULL) continue; // 空隊列跳過 if (fq-head-virtual_time min_vt) { min_vt fq-head-virtual_time; best_fq fq; } } if (!best_fq) return NULL; // 所有隊列為空 Packet *pkt best_fq-head; best_fq-head pkt-next; if (best_fq-head NULL) best_fq-tail NULL; best_fq-packet_count--; return pkt; }這里有個細節(jié)insert_packet_sorted保證每個流隊列內(nèi)部按虛擬時間有序這樣出隊時只需要比較各隊頭不用遍歷整個隊列。如果流數(shù)量很多比如上千個流每次出隊都遍歷所有流會變成性能瓶頸。常見優(yōu)化是用最小堆維護各流隊頭的虛擬時間把 O(n) 降到 O(log n)。這份代碼為了可讀性先用線性掃描二次開發(fā)時可以替換。3. 編譯與運行從源碼到可執(zhí)行 Demo 的完整步驟3.1 環(huán)境準備與編譯命令這份代碼依賴很少Linux 下只需要 gcc/g 和 make。Windows 下可以用 MinGW 或 WSL。先確認工具鏈gcc --version g --version make --version進入項目根目錄直接執(zhí)行make clean makeMakefile 里默認編譯出兩個可執(zhí)行文件test_wfq和demo。test_wfq跑單元測試驗證權(quán)重比例是否正確demo模擬三個流不同權(quán)重的調(diào)度過程打印每個包的出隊順序。如果編譯報錯undefined reference to calc_virtual_time說明wfq.c沒被鏈接進去檢查 Makefile 的SRCS變量是否包含src/wfq.c。這是最常見的翻車點尤其是手動改過目錄結(jié)構(gòu)之后。3.2 運行 Demo 與結(jié)果解讀編譯成功后運行./demo輸出大致如下Flow 1 (weight1): packet 1, vt100.00 Flow 2 (weight2): packet 1, vt50.00 Flow 3 (weight3): packet 1, vt33.33 --- dequeue order --- Flow 3 packet 1 (vt33.33) Flow 2 packet 1 (vt50.00) Flow 1 packet 1 (vt100.00)這個結(jié)果說明權(quán)重 3 的流虛擬時間最小最先出隊權(quán)重 1 的流虛擬時間最大最后出隊。如果三個流持續(xù)有包長期來看出隊包的數(shù)量比會接近 3:2:1這就是 WFQ 的加權(quán)公平性。你可以改demo.cpp里的權(quán)重值重新編譯運行觀察調(diào)度順序變化。比如把 Flow 1 的權(quán)重改成 10它會變成最先出隊的流。這種即時反饋對理解 WFQ 非常有用。3.3 單元測試驗證權(quán)重比例test_wfq.cpp里構(gòu)造了固定包長的多流場景統(tǒng)計一段時間內(nèi)各流出隊包數(shù)和理論比例對比// test/test_wfq.cpp void test_weight_proportion() { WFQ_Scheduler sched; wfq_init(sched); wfq_add_flow(sched, 1, 1); // flow 1, weight 1 wfq_add_flow(sched, 2, 2); // flow 2, weight 2 wfq_add_flow(sched, 3, 3); // flow 3, weight 3 // 每個流各入隊 100 個包 for (int i 0; i 100; i) { wfq_enqueue(sched, make_packet(1, 1000)); wfq_enqueue(sched, make_packet(2, 1000)); wfq_enqueue(sched, make_packet(3, 1000)); } int count[4] {0}; Packet *pkt; while ((pkt wfq_dequeue(sched)) ! NULL) { count[pkt-flow_id]; free(pkt); } // 理論比例 1:2:3允許 5% 誤差 assert(abs(count[1] - 50) 5); assert(abs(count[2] - 100) 5); assert(abs(count[3] - 150) 5); }這個測試跑通說明虛擬時間計算和出隊選擇邏輯是對的。如果斷言失敗先檢查calc_virtual_time里的除法是不是寫成了整數(shù)除法再檢查insert_packet_sorted有沒有正確排序。4. 避坑與常見問題WFQ 實現(xiàn)里最容易翻車的幾個點4.1 虛擬時間溢出或精度丟失現(xiàn)象跑長時間仿真后調(diào)度順序開始混亂高權(quán)重流反而排不過低權(quán)重流。原因virtual_time用float而不是double累加幾千次后精度不夠或者用int存虛擬時間包長除以權(quán)重后直接截斷成整數(shù)。解決統(tǒng)一用double并且在每次入隊時檢查虛擬時間是否超過閾值比如 1e12超過就所有流的虛擬時間同時減去一個基準值防止溢出。這個操作叫“虛擬時間重歸一化”生產(chǎn)環(huán)境必須做。4.2 權(quán)重為 0 導(dǎo)致除零崩潰現(xiàn)象程序在calc_virtual_time里直接 segfault。原因注冊流的時候沒校驗權(quán)重傳了 0 進去除法直接崩。解決wfq_add_flow里加斷言或返回錯誤碼權(quán)重必須大于 0。如果業(yè)務(wù)上確實需要“暫?！蹦硞€流應(yīng)該把它從調(diào)度器里移除而不是設(shè)權(quán)重為 0。4.3 隊列排序不穩(wěn)定導(dǎo)致同虛擬時間包順序錯亂現(xiàn)象兩個包虛擬時間相同出隊順序隨機測試結(jié)果不穩(wěn)定。原因insert_packet_sorted用的是而不是導(dǎo)致相同虛擬時間的包插到了前面破壞了 FIFO 語義。解決排序時用嚴格小于相同虛擬時間的包按入隊順序排列。WFQ 本身不保證相同虛擬時間的順序但工程實現(xiàn)里保持 FIFO 更符合直覺也方便調(diào)試。4.4 流數(shù)量多時出隊性能急劇下降現(xiàn)象流數(shù)量從 10 增加到 1000 后出隊耗時從微秒級漲到毫秒級。原因wfq_dequeue每次遍歷所有流找最小虛擬時間復(fù)雜度 O(n)。解決引入最小堆或紅黑樹維護各流隊頭虛擬時間出隊復(fù)雜度降到 O(log n)。這份代碼為了可讀性先用線性掃描二次開發(fā)時如果流數(shù)量超過 100建議直接換堆實現(xiàn)。4.5 內(nèi)存泄漏出隊后忘記釋放包現(xiàn)象長時間運行后 RSS 持續(xù)上漲最終 OOM。原因wfq_dequeue返回的Packet*是堆分配的調(diào)用方用完必須free。Demo 里釋放了但集成到實際項目時經(jīng)常漏掉。解決在wfq_dequeue內(nèi)部不釋放由調(diào)用方負責(zé)或者提供wfq_dequeue_and_free接口把釋放邏輯封裝進去。我一般會在測試里用 valgrind 跑一遍確認沒有 definitely lost。5. 二次開發(fā)與改造把 WFQ 塞進你自己的項目5.1 替換底層隊列從鏈表到環(huán)形緩沖區(qū)這份代碼用鏈表實現(xiàn)流隊列好處是插入刪除 O(1)壞處是緩存不友好。如果你的場景是固定包長、高吞吐可以把FlowQueue里的鏈表換成環(huán)形緩沖區(qū)typedef struct RingBuffer { Packet *buf; int capacity; int head; int tail; int count; } RingBuffer;入隊時tail (tail 1) % capacity出隊時head (head 1) % capacity。注意環(huán)形緩沖區(qū)滿了之后要么丟包要么阻塞WFQ 本身不處理擁塞需要你在上層加策略。5.2 支持動態(tài)權(quán)重調(diào)整實際網(wǎng)絡(luò)里流的權(quán)重可能隨時變化。你可以在FlowQueue里加一個pending_weight字段入隊時如果發(fā)現(xiàn)權(quán)重變了先按舊權(quán)重把當(dāng)前隊列的虛擬時間重算一遍再切到新權(quán)重。重算邏輯void update_flow_weight(FlowQueue *fq, int new_weight) { if (new_weight 0) return; double ratio (double)fq-weight / (double)new_weight; fq-virtual_time * ratio; // 按比例縮放虛擬時間 fq-weight new_weight; }這個縮放保證權(quán)重切換時不會出現(xiàn)虛擬時間跳變調(diào)度順序平滑過渡。5.3 驗證改造是否正確三個必跑測試改完代碼后至少跑這三個測試測試項目的預(yù)期結(jié)果權(quán)重比例測試驗證調(diào)度公平性出隊包數(shù)比接近權(quán)重比空隊列測試驗證邊界條件所有隊列為空時返回 NULL不崩潰長時間運行測試驗證虛擬時間不溢出跑 100 萬包后調(diào)度順序仍正確我一般會在 CI 里掛一個 10 萬包的回歸測試每次提交都跑一遍。有一次改排序邏輯把寫成單元測試沒覆蓋到相同虛擬時間的場景結(jié)果上線后調(diào)度順序全亂。從那以后我每次改insert_packet_sorted都強制走一遍相同虛擬時間的用例確認 FIFO 語義沒丟。希望幫到你。本文還有配套的精品資源點擊獲取