HackMD2025q1 第 9 週測驗題
目的: 檢驗學員對 CPU 排程器和〈Concurrency Primer〉的認知
測驗 1
考慮 schedsort不用去Google搜尋，此乃獨創 作為相當特別的資料排序實作，將傳統的排序問題轉化為 CPU 排程模型，將每個數值映射至一個優先權等級（bucket）。這裡的 bucket 可被視為一個對應優先權的分類空間，與作業系統排程器中的 real-time scheduling class 有密切對應關係 (務必詳閱《Demystifying the Linux CPU Scheduler》第 2 章)。
schedsort 中的 MAX_PRIO 可視為對此範圍的模擬，用於決定 bucket 數量，即分層的解析度。在 Linux 核心中，SCHED_FIFO 排程類別（定義於 kernel/sched/rt.c）會依據行程設定的靜態優先權值（在範圍 1 到 99 之間）進行排程。該優先權範圍符合 POSIX 規格，可藉由 sched_get_priority_min(SCHED_FIFO) 與 sched_get_priority_max(SCHED_FIFO) 查詢，分別定義於 <sched.h>。Linux 的即時行程會進入 rt_rq（real-time runqueue）中，並由核心中函式如 pick_next_task_rt() 根據最高靜態優先權挑選下個行程，且高優先權行程不會被低優先權行程搶佔，形成嚴格的優先權排程策略。
schedsort 模擬這種行為，將每筆資料映射至離散的 bucket (類比優先權層級)，資料一旦寫入後，便不會被後續較小值覆蓋，並在合併階段依 bucket 順序輸出。schedsort 採取相同概念：透過將資料值經由 stable code 計算後正規化，映射到 MAX_PRIO 個 bucket 中，每個 bucket 就類似於一個靜態優先權佇列。
程式以 C11 Atomics 實作多執行緒，確保安全地將資料寫入 bucket，schedsort 可視為模擬 Linux 核心的靜態優先權排程邏輯，不同的是我們排程的是「資料值的排序」而非「行程的執行」。資料被分派至相應的 bucket 中，再依 bucket 順序進行線性合併，形成排序結果。
為了將原始數值（例如整數）映射到有限個 bucket，schedsort 採用 normalization（正規化）技巧：
該設計的特點如下：
- 穩定性 (stability）：相同值將保留原始順序（index 較小者優先）
- 均勻分布：透過將原始資料值減去最小值後左移 32 位元，並與原始索引結合，產生 64-bit 的
stable_code，再進行線性正規化，此映射手法有助於將偏態分布轉化為近似均勻分布。
在理想情況下，這種策略的 bucket 佔用可視為指數衰減模型下的累積分布，對應於自然對數之特性。若將每個值的出現頻率視為某機率密度函數的結果，則其分配至 bucket 的期望密度約呈現 型態之平滑轉換，透過 stable code 可緩和 cluster 效應。
延伸閱讀: 歐拉數 : 描述連續變化的基石
所謂 cluster (叢集) 效應，指在資料正規化過程中，若原始資料分布不均 (例如呈偏態或有尖峰)，過多資料會集中映射到少數 bucket 中，形成 bucket 熱點，導致 contention 或排序效能不穩。從統計觀點來看，這相當於某些資料叢集在分佈尾端累積出極端密度。在傳統排序中這會影響比較成本，在 schedsort 中則反映為執行緒間對少數 bucket 中 atomic 操作的競爭。
透過 stable code 正規化技巧，這種集中效應能夠被平滑轉換至更平均的 bucket 分布，減少極端 cluster 的效應，提升排序流程的穩定性與並行效率，進一步降低熱點競爭 (contention) 的機率。
所有執行緒共同寫入共享的 bucket 陣列。若不採取同步機制，複數執行緒可能同時讀取 bucket 的大小，並將資料寫入相同的位置，導致資料覆寫或遺失，這就是典型的競爭條件（race condition）。為解決此問題，schedsort 採用 C11 Atomics，以保證每個執行緒都能取得唯一的寫入位置，意味著即使多個執行緒同時存取 bucket_sizes[bucket]，每個執行緒都能獲得互不相同的 index 值，因此不會有二個執行緒同時寫入 buckets 的相同位置，也就不會發生資料覆蓋、毀損或 race condition。這項特性讓 schedsort 在不使用 mutex 一類同步機制的情況下，仍可保證資料一致性 (consistency)，提升在多核環境下的並行效能。
當所有元素皆完成 bucket 分派後，schedsort 根據每個 bucket 的計數資訊建立 prefix sum，再將所有 bucket 資料依序寫入最終結果陣列。所有寫入具備已知範圍，因此每個執行緒可以在合併階段直接依據 bucket 的偏移量（prefix sum）進行連續寫入。這種線性寫入方式符合記憶體層級快取（如 L1、L2）與硬體 prefetch 的存取模式，能有效提升快取命中率並降低記憶體延遲。
例如，若某筆輸入資料經過 bucket 化後位於 bucket[42]，而 bucket[42] 的 offset 是 3200，執行緒可直接從 output[3200] 開始線性寫入，而不需查詢或搬移資料區段，從而避免跳躍式存取。
這種 coalesced write 模式對於處理大型資料陣列時具有明顯的效能優勢，因為它避免隨機寫入造成的 cache line thrashing 與寫入延遲（如觸發頻繁的 cache eviction），同時可維持每條執行緒的連續記憶體區塊操作，對 NUMA 結構亦具 locality 效益，特別是在每條執行緒僅寫入特定 bucket 區段時可最大化 DRAM 預取效能。
schedsort 可對應至作業系統的 real-time 排程策略：
- 每個 bucket 相當於一個固定優先權等級佇列 (如 Linux
SCHED_FIFO) - 最終的合併步驟就像是排程器自最高（或最低）優先佇列開始執行各任務
- 此外，
schedsort概念類似多階層回饋佇列 (MLFQ)，都具備離散層級映射對應行為
可行改進方向：
- thread-local bucket + 合併：避免 atomic 競爭，最終合併時依 offset 輸出
- 細緻的 bucket 分析：預先掃描資料分布，調整 bucket 範圍與解析度
- bucket 自動擴張機制：支援 lock-free dynamic resizing
- SIMD 與對齊寫入支援：提升合併階段的記憶體吞吐量
程式碼可見 sort.c (部分遮蔽)，使用案例:
作答規範：
AAAA和BBBB為 C11 Atomics 函式CCCC為有效表達式- 使用一致的程式縮排風格
延伸問題：
- 解釋上述程式碼運作原理，並提出對應的數學模型，描述隨著資料排序數量增長，對於
schedsort排序的成本變化討論，注意統計模型的建立和考慮 CPU 排程器的內部運作機制 - 在維持
schedsort關鍵概念的前提，改善資料排序效率，特別留意記憶體存取的成本 - 建立 lock-free 程式設計的運算模型及其數學分析，並善用 perf, ftrace, eBPF 等機制去驗證實際行為
