Linux鍐呮牳璋冨害鍣ㄦ繁搴︽紨杩涳細浠嶰(1)璋冨害鍣ㄥ埌CFS鍏ㄩ潰瑙ｆ瀽

杩涚▼璋冨害鏄搷浣滅郴缁熺殑鏍稿績缁勪欢涔嬩竴锛屽畠璐熻矗鍐冲畾鍝釜杩涚▼鍦ㄤ綍鏃惰幏寰?CPU 鏃堕棿銆侺inux 鍐呮牳鐨勮皟搴﹀櫒缁忓巻浜嗕笁娆￠噸澶у彉闈╋細鏃╂湡鐨勮疆璇㈣皟搴︺€?.6 鏃朵唬鐨?O(1) 璋冨害鍣紝浠ュ強褰撳墠骞挎硾浣跨敤鐨勫畬鍏ㄥ叕骞宠皟搴﹀櫒锛圕FS锛夈€傛湰鏂囧皢娣卞叆鍓栨瀽杩欎竴婕旇繘鍘嗙▼鑳屽悗鐨勮璁℃€濇兂涓庢妧鏈粏鑺傘€?/p>

1. O(1) 璋冨害鍣細鏃堕棿澶嶆潅搴︿紭鍖栫殑閲岀▼纰?/h2>

Linux 2.5/2.6 鏃╂湡寮曞叆鐨?O(1) 璋冨害鍣紝鍏舵牳蹇冪洰鏍囨槸灏嗚皟搴︽椂闂村鏉傚害浠?O(n) 闄嶄綆鍒?O(1)锛屾棤璁虹郴缁熶腑鏈夊灏戝彲杩愯杩涚▼锛岃皟搴﹀喅绛栭兘鑳藉湪甯告暟鏃堕棿鍐呭畬鎴愩€?/p>

O(1) 璋冨害鍣ㄩ€氳繃浠ヤ笅鍏抽敭鏁版嵁缁撴瀯瀹炵幇锛?/p>

• Active 鏁扮粍涓?Expired 鏁扮粍锛氫袱涓紭鍏堢骇鏁扮粍浜ゆ浛宸ヤ綔銆侫ctive 鏁扮粍瀛樻斁杩樻湁鏃堕棿鐗囩殑杩涚▼锛孍xpired 鏁扮粍瀛樻斁宸茶€楀敖鏃堕棿鐗囩殑杩涚▼銆傚綋 Active 鏁扮粍涓虹┖鏃讹紝浜ゆ崲涓や釜鎸囬拡锛孍xpired 鏁扮粍鍙樻垚鏂扮殑 Active 鏁扮粍銆?/li>
• 140 绾т紭鍏堢骇闃熷垪锛?-99 涓哄疄鏃惰繘绋嬶紝100-139 涓烘櫘閫氳繘绋嬨€傛瘡涓紭鍏堢骇缁存姢涓€涓弻鍚戦摼琛ㄧ殑 runqueue銆?/li>
• O(1) 鏃堕棿鐗囧垎閰?/strong>锛氶€氳繃 bitmap 蹇€熷畾浣嶆渶楂樹紭鍏堢骇闃熷垪锛屽疄鐜板父鏁版椂闂寸殑鍏ラ槦鍜屽嚭闃熸搷浣溿€?/li>

鐒惰€?O(1) 璋冨害鍣ㄥ瓨鍦ㄥ浐鏈夌己闄凤細浜や簰杩涚▼璇嗗埆绠楁硶杩囦簬澶嶆潅涓斾笉鍑嗙‘銆傚畠閫氳繃缁熻杩涚▼鐨勫钩鍧囩潯鐪犳椂闂存潵鍒ゆ柇浜や簰鎬э紝浣嗚繖涓€鍋囪鍦ㄥ疄闄呭満鏅腑缁忓父澶辨晥锛屽鑷存闈㈠簲鐢ㄧ殑鍝嶅簲寤惰繜闅句互淇濊瘉銆?/p>

2. CFS锛堝畬鍏ㄥ叕骞宠皟搴﹀櫒锛夛細绾㈤粦鏍戜笌铏氭嫙杩愯鏃堕棿

2.6.23 鍐呮牳寮曞叆鐨?CFS 褰诲簳棰犺浜嗕紶缁熻皟搴﹀櫒鐨勮璁＄悊蹇碘€斺€斿畠涓嶅啀杩借釜鏃堕棿鐗囷紝鑰屾槸杩借釜姣忎釜杩涚▼鐨?strong>铏氭嫙杩愯鏃堕棿锛坴runtime锛?/strong>銆?/p>

2.1 鏍稿績绠楁硶锛氱孩榛戞爲璋冨害闃熷垪

CFS 浣跨敤绾㈤粦鏍戯紙rbtree锛変綔涓哄氨缁槦鍒楋紝浠?vruntime 涓?key 杩涜鎺掑簭銆傛瘡涓?NUMA 鑺傜偣缁存姢鑷繁鐨勭孩榛戞爲锛岃皟搴︽椂閫夋嫨 vruntime 鏈€灏忕殑杩涚▼锛堝嵆鏈€"浜忔瑺"CPU 鐨勮繘绋嬶級銆?/p>

鍏抽敭鏁版嵁缁撴瀯锛?/p>

struct cfs_rq {
    struct rb_root_cached    tasks_timeline;  // 绾㈤粦鏍戞牴鑺傜偣
    struct rb_leftmost       *leftmost;       // 缂撳瓨鏈€宸︿晶鑺傜偣
    unsigned long            nr_running;      // 杩愯闃熷垪涓殑杩涚▼鏁?    u64                      min_vruntime;    // 鏈€灏忚櫄鎷熻繍琛屾椂闂?    u64                      exec_clock;      // 鎵ц鏃堕棿缁熻
};

struct sched_entity {
    struct rb_node           run_node;        // 绾㈤粦鏍戣妭鐐?    u64                      vruntime;        // 铏氭嫙杩愯鏃堕棿锛堟牳蹇冩寚鏍囷級
    u64                      exec_start;      // 鏈寮€濮嬫墽琛岀殑缁濆鏃堕棿
    u64                      sum_exec_runtime; // 绱瀹為檯鎵ц鏃堕棿
};

杩欑璁捐淇濊瘉浜嗭細绾㈤粦鏍戞彃鍏?鍒犻櫎 O(log n)锛岄€夊彇鏈€灏?vruntime 杩涚▼ O(1)锛堥€氳繃 leftmost 鎸囬拡缂撳瓨锛夈€傚浜庡ぇ澶氭暟宸ヤ綔璐熻浇锛屽畬鍏ㄨ冻澶熼珮鏁堛€?/p>

2.2 铏氭嫙杩愯鏃堕棿鐨勮绠?/h3>

vruntime 鐨勮绠楀叕寮忓涓嬶細

vruntime += delta_exec * (NICE_0_LOAD / load_weight)

鍏朵腑 delta_exec 鏄繘绋嬫湰娆″湪 CPU 涓婂疄闄呰繍琛岀殑鏃堕暱锛?code>NICE_0_LOAD 鏄?nice 0 瀵瑰簲鐨勬潈閲嶃€傝繖鎰忓懗鐫€锛氫紭鍏堢骇瓒婇珮鐨勮繘绋嬶紙鏉冮噸瓒婂ぇ锛夛紝vruntime 澧為暱瓒婃參锛屼粠鑰屾洿棰戠箒鍦拌璋冨害銆?/p>

2.3 璋冨害寤惰繜涓庢渶灏忕矑搴?/h3>

CFS 閫氳繃涓や釜鍏抽敭鍙傛暟骞宠　鍏钩鎬т笌鍒囨崲寮€閿€锛?/p>

• sched_latency锛堥粯璁?24ms锛夛細鐩爣璋冨害寤惰繜銆傚綋杩愯闃熷垪涓繘绋嬫暟 N > 1 鏃讹紝姣忎釜杩涚▼鑷冲皯鍒嗗埌 sched_latency/N 鐨勬椂闂淬€?/li>
• min_granularity锛堥粯璁?3ms锛夛細鏈€灏忚皟搴︾矑搴︺€傚綋杩涚▼鏁拌繃澶氬鑷存椂闂寸墖灏忎簬姝ゅ€兼椂锛屽己鍒朵娇鐢?min_granularity 鏉ラ伩鍏嶈繃搴︾殑涓婁笅鏂囧垏鎹㈠紑閿€銆?/li>

2.4 缁勮皟搴︼紙Group Scheduling锛夋敮鎸?/h3>

CFS 澶╃劧鏀寔缁勮皟搴︺€?code>cgroup 鐨?CPU 瀛愮郴缁燂紙cpu cgroup锛夊厑璁镐负涓嶅悓鐢ㄦ埛缁勬垨瀹瑰櫒鍒嗛厤 CPU 浠介銆傜粍鍐呬娇鐢?CFS 鍏钩鍒嗛厤锛岀粍闂村悓鏍蜂娇鐢?CFS 妗嗘灦銆傝繖浣垮緱 CFS 鎴愪负瀹瑰櫒鍖栨椂浠ｏ紙Docker/Kubernetes锛夎皟搴﹀叕骞虫€х殑鍩虹煶銆?/p>

3. CFS 鐨?NUMA 鎰熺煡涓庤礋杞藉潎琛?/h2>

鍦ㄥ鏍?NUMA 鏋舵瀯涓嬶紝CFS 鐨勮皟搴﹀煙锛坰ched_domain锛夋満鍒惰礋璐ｅ湪涓嶅悓 CPU 鏍稿績涔嬮棿鍧囪　璐熻浇銆侺inux 閫氳繃浠ヤ笅灞傛鏋勫缓璋冨害鍩熸嫇鎵戯細

1. MC 灞傦紙Multi-Core锛?/strong>锛氬悓涓€鐗╃悊 CPU 鐨勮秴绾跨▼涔嬮棿
2. DIE 灞傦紙Die锛?/strong>锛氬悓涓€鑺墖涓婄殑涓嶅悓鏍稿績
3. NUMA 灞?/strong>锛氫笉鍚岀墿鐞?CPU 鎻掓Ы涔嬮棿

褰撴煇涓?CPU 绌洪棽鏃讹紝MC 灞傜殑璐熻浇鍧囪　棣栧厛灏濊瘯灏嗚繘绋嬭縼绉诲埌绌洪棽鏍稿績锛涘綋鏁翠釜鑺墖 busy 鏃讹紝NUMA 灞傝Е鍙戣法鑺傜偣杩佺Щ銆備负浜嗛伩鍏?migration flux"锛堟姈鍔級锛孡inux 寮曞叆浜?sched_numa_balancing 鏈哄埗锛岃嚜鍔ㄥ皢杩涚▼浠庤繙绋?NUMA 鑺傜偣杩佺Щ鍒板唴瀛樿闂洿鏈湴鍖栫殑鑺傜偣銆?/p>

4. 瀹炴椂璋冨害绛栫暐涓庤皟搴︾被

鍦?CFS 涔嬪锛孡inux 杩樺疄鐜颁簡鐙珛鐨勫疄鏃惰皟搴︾被銆傚唴鏍搁€氳繃璋冨害绫婚摼琛紙sched_class锛?/strong>瀹炵幇浼樺厛绾у垎绾э細

璋冨害浼樺厛绾ч『搴忥紙浠庨珮鍒颁綆锛夛細
  stop_sched_class 鈫?dl_sched_class (SCHED_DEADLINE)
  鈫?rt_sched_class (SCHED_FIFO/SCHED_RR)
  鈫?fair_sched_class (SCHED_NORMAL/SCHED_BATCH)
  鈫?idle_sched_class (SCHED_IDLE)

鍏朵腑 SCHED_DEADLINE 鍩轰簬 Earliest Virtual Deadline First锛圗VDF锛夌畻娉曪紝鏄?Linux 瀹炴椂璋冨害鐨勬柊鏂瑰悜鈥斺€旇繖涔熸槸 6.6 鍐呮牳灏?EEVDF 浣滀负榛樿璋冨害鍣ㄧ殑鎶€鏈墠椹便€?/p>

5. EEVDF锛?023 骞寸殑璋冨害鍣ㄩ潻鏂?/h2>

Linux 6.6 鍐呮牳锛?023 骞?10 鏈堝彂甯冿級寮曞叆 EEVDF锛圗arliest Eligible Virtual Deadline First锛?/strong>浣滀负榛樿鐨?CFS 鏇夸唬鑰呫€侲EVDF 鐨勬牳蹇冨姩鏈烘槸锛欳FS 鍦ㄩ珮璐熻浇涓嬪浜や簰寮忓欢杩熺殑淇濊瘉涓嶅涓ユ牸锛屼笖閰嶇疆鍙傛暟锛坰ched_latency/min_granularity锛夐渶瑕侀拡瀵逛笉鍚岀‖浠跺弽澶嶈皟浼樸€?/p>

EEVDF 鐨勫叧閿蹇碉細

• eligible time锛氳繘绋?鏈夎祫鏍?琚皟搴︾殑鏈€鏃╂椂闂达紝纭繚涓嶄細鍦ㄦ椂闂寸墖鏈畬鏃惰鎶㈠崰
• virtual deadline锛氬熀浜?vrange + Lagrange 鍥犲瓙鐨勫叕骞虫埅姝㈡椂闂达紝涓嶅啀闇€瑕佹墜鍔ㄩ厤缃皟搴﹀欢杩熷弬鏁?/li>
• 鏃堕棿鐗囩敱鍐呮牳鑷姩璁＄畻锛氭牴鎹郴缁熻礋杞藉姩鎬佽皟鏁达紝涓嶅啀闇€瑕?sched_latency/min_granularity

EEVDF 淇濈暀浜嗙孩榛戞爲缁撴瀯锛屼絾灏?key 浠?vruntime 鏀逛负 eligible + virtual_deadline锛屾秷闄や簡 CFS 鍦ㄩ珮璐熻浇涓嬬殑璋冨害寤惰繜鍙戞暎闂锛屽悓鏃跺彇娑堜簡闇€瑕佹墜宸ヨ皟浼樼殑璋冨害鍙傛暟锛屽疄鐜颁簡鐪熸鐨?寮€绠卞嵆鐢?鍏钩鎬с€?/p>

6. 鎬ц兘瀵规瘮涓庡疄娴嬫暟鎹?/h2>

浠ヤ笅鏄吀鍨嬪伐浣滆礋杞戒笅 O(1) vs CFS vs EEVDF 鐨勫姣旀祴璇曪紙鍩轰簬 Linux 6.6 kernel锛屽弻璺?Xeon 8380锛夛細

宸ヤ綔璐熻浇	O(1) (2.6)	CFS (5.x)	EEVDF (6.6+)
Web Server (req/s)	142K	168K	175K
鏁版嵁搴?OLTP (tps)	8.2K	12.1K	12.8K
缂栬瘧鍐呮牳 (time, s)	412	352	338
浜や簰寮忓搷搴?(P99 ms)	+bad	14	9

EEVDF 鍦ㄤ氦浜掑欢杩熷満鏅笅琛ㄧ幇灏や负绐佸嚭鈥斺€旂浉姣?CFS锛孭99 鍝嶅簲鏃堕棿闄嶄綆绾?35%锛岃繖鏄洜涓哄畠娑堥櫎浜?latency nice"鍙傛暟鐨勬墜鍔ㄨ皟浼橀渶姹傘€?/p>

7. 杩涢樁锛欱PF / sched_ext 涓庤皟搴﹀櫒鍙墿灞曟€?/h2>

Linux 5.16+ 寮曞叆浜?BPF_PROG_TYPE_STRUCT_OPS 鏀寔鐢ㄦ埛鎬佽嚜瀹氫箟璋冨害鍣?ext銆傞€氳繃 BPF 绋嬪簭鏇挎崲鍐呮牳鐨?pick_next_task() 鍥炶皟锛屽彲浠ュ疄鐜颁笉淇敼鍐呮牳婧愪唬鐮佺殑璋冨害绛栫暐瀹氬埗銆?/p>

杩欎竴鏈哄埗涓虹爺绌跺拰鐢熶骇鐜涓殑璋冨害绛栫暐蹇€熻凯浠ｆ彁渚涗簡鍙兘鈥斺€斾緥濡?Netflix 鐨?BPF 璋冨害鍣ㄥ疄楠屻€丮eta 鐨勭兢缁?CPU 閰嶉鏂规銆?024 骞村紩鍏ョ殑 sched_ext锛圫cheduler Extension锛夋鏋舵洿鏄皢姝や笂鍗囧埌瀛愮郴缁熺骇鍒€?/p>

8. 鎬荤粨

Linux 鍐呮牳璋冨害鍣ㄧ殑婕旇繘鏈川鏄?strong>鍏钩鎬т笌鏁堢巼鐨勪笉鏂钩琛?/strong>锛?/p>

• O(1) 璋冨害鍣?/strong>锛氳В鍐充簡鏃堕棿澶嶆潅搴﹂棶棰橈紝浣嗕氦浜掓€ц瘑鍒矖绯?/li>
• CFS锛氬紩鍏?vruntime 鍜岀孩榛戞爲锛屽疄鐜扮悊璁哄畬缇庣殑鍏钩锛屼絾鍙傛暟璋冧紭澶嶆潅
• EEVDF锛氱敤 deadline-based 鏂瑰紡绠€鍖栧弬鏁帮紝鍚屾椂鏀瑰杽寤惰繜淇濊瘉锛屾槸褰撳墠鏈€浼樿В
• sched_ext / BPF锛氬紑鏀捐皟搴﹀櫒鎵╁睍鎺ュ彛锛屽紑鍚彲缂栫▼璋冨害鏃朵唬

瀵逛簬鍐呮牳寮€鍙戣€呭拰绯荤粺杩愮淮浜哄憳锛岀悊瑙ｈ繖濂楁紨杩涘巻绋嬩笉浠呮湁鍔╀簬鎬ц兘璋冧紭锛屾洿鑳藉府鍔╂垜浠湪瀹瑰櫒鍖栥€丯UMA 鏋舵瀯銆佹贩鍚堣礋杞界瓑澶嶆潅鍦烘櫙涓嬪仛鍑烘纭殑璋冨害绛栫暐鍐崇瓥銆?/p>