1. 從一次任務(wù)調(diào)度卡頓說(shuō)起那天在調(diào)試一個(gè)基于RT-Thread的電機(jī)控制項(xiàng)目系統(tǒng)里跑了五六個(gè)線(xiàn)程有負(fù)責(zé)PID計(jì)算的有處理串口通信的還有幾個(gè)做數(shù)據(jù)采集和狀態(tài)顯示的。項(xiàng)目跑起來(lái)大部分時(shí)候都挺順暢但偶爾會(huì)出現(xiàn)一個(gè)奇怪的現(xiàn)象某個(gè)高優(yōu)先級(jí)的緊急任務(wù)比如急停響應(yīng)似乎沒(méi)有立刻被調(diào)度執(zhí)行而是延遲了那么幾微秒才反應(yīng)過(guò)來(lái)。對(duì)于一般的應(yīng)用這幾微秒可能不算什么但在高速電機(jī)控制里這點(diǎn)延遲足以讓一個(gè)完美的波形產(chǎn)生畸變或者讓保護(hù)動(dòng)作慢上半拍。排查過(guò)程很痛苦從中斷響應(yīng)時(shí)間查到任務(wù)棧溢出最后把目光投向了任務(wù)調(diào)度器本身。RT-Thread作為一款優(yōu)秀的國(guó)產(chǎn)實(shí)時(shí)操作系統(tǒng)其內(nèi)核調(diào)度器的效率直接決定了系統(tǒng)的實(shí)時(shí)性上限。而它的核心調(diào)度算法之一就是位圖調(diào)度算法。這個(gè)算法名字聽(tīng)起來(lái)有點(diǎn)“古老”甚至有些教科書(shū)里一筆帶過(guò)但在資源受限的嵌入式領(lǐng)域尤其是像Cortex-M這類(lèi)MCU上它卻是一個(gè)將“簡(jiǎn)單、高效、可靠”發(fā)揮到極致的典范。它沒(méi)有復(fù)雜的時(shí)間片輪轉(zhuǎn)沒(méi)有多級(jí)反饋隊(duì)列那些花哨的概念就是靠著對(duì)幾個(gè)整型變量的位操作實(shí)現(xiàn)了納秒級(jí)的任務(wù)調(diào)度決策。今天我們就來(lái)徹底拆解一下RT-Thread內(nèi)核中的這位“掃地僧”——位圖調(diào)度算法看看它是如何用最樸素的方式扛起實(shí)時(shí)系統(tǒng)調(diào)度的大梁的。2. 位圖調(diào)度算法的核心思想為什么是“位”在深入RT-Thread的源碼之前我們得先搞明白位圖調(diào)度到底在解決一個(gè)什么問(wèn)題以及為什么“位”這個(gè)單位如此關(guān)鍵。2.1 實(shí)時(shí)調(diào)度器的核心訴求對(duì)于一個(gè)實(shí)時(shí)操作系統(tǒng)RTOS的調(diào)度器尤其是面向嵌入式場(chǎng)景的它的設(shè)計(jì)目標(biāo)排序通常是這樣的確定性Determinism調(diào)度所花費(fèi)的時(shí)間必須是可預(yù)測(cè)、有上限的。最壞情況下的調(diào)度時(shí)間最壞情況執(zhí)行時(shí)間WCET必須明確這對(duì)于硬實(shí)時(shí)任務(wù)至關(guān)重要。高效性Efficiency調(diào)度器本身不能占用太多CPU時(shí)間和內(nèi)存資源。在MHz主頻、KB級(jí)RAM的MCU上每一個(gè)時(shí)鐘周期和每一字節(jié)內(nèi)存都彌足珍貴。簡(jiǎn)單性Simplicity代碼應(yīng)易于理解、驗(yàn)證和維護(hù)。復(fù)雜的算法往往伴隨著隱蔽的缺陷和不可預(yù)測(cè)的邊界情況。基于優(yōu)先級(jí)的搶占式調(diào)度是滿(mǎn)足這些訴求的天然選擇。系統(tǒng)為每個(gè)任務(wù)分配一個(gè)固定的優(yōu)先級(jí)通常是數(shù)值越小優(yōu)先級(jí)越高調(diào)度器永遠(yuǎn)從就緒狀態(tài)的任務(wù)中選出優(yōu)先級(jí)最高的那個(gè)來(lái)運(yùn)行。那么問(wèn)題就轉(zhuǎn)化為如何從一組任務(wù)中快速找到優(yōu)先級(jí)最高的那個(gè)就緒任務(wù)2.2 位圖的登場(chǎng)將查找復(fù)雜度降至O(1)最直觀的想法是遍歷。假設(shè)我們有32個(gè)優(yōu)先級(jí)0-31維護(hù)一個(gè)包含32個(gè)任務(wù)的列表每次調(diào)度時(shí)從優(yōu)先級(jí)0開(kāi)始掃描找到第一個(gè)狀態(tài)為就緒的任務(wù)。這個(gè)方法的時(shí)間復(fù)雜度是O(n)n是優(yōu)先級(jí)數(shù)量。在最壞情況下只有優(yōu)先級(jí)31的任務(wù)就緒需要掃描32次。對(duì)于需要頻繁調(diào)度的系統(tǒng)來(lái)說(shuō)這個(gè)開(kāi)銷(xiāo)不夠理想。位圖算法的精妙之處在于它利用了計(jì)算機(jī)CPU對(duì)位運(yùn)算與、或、非、移位的極致優(yōu)化能力這些操作通常能在單個(gè)時(shí)鐘周期內(nèi)完成。它的核心數(shù)據(jù)結(jié)構(gòu)是一個(gè)或多個(gè)整數(shù)通常是32位無(wú)符號(hào)整型rt_uint32_t將這個(gè)整數(shù)的每一個(gè)二進(jìn)制位bit映射到一個(gè)優(yōu)先級(jí)。位值為1表示該優(yōu)先級(jí)下至少有一個(gè)任務(wù)處于就緒狀態(tài)。位值為0表示該優(yōu)先級(jí)下沒(méi)有任何任務(wù)就緒。這個(gè)整數(shù)或整數(shù)數(shù)組就叫做就緒優(yōu)先級(jí)位圖rt_thread_ready_priority_group在RT-Thread中。查找最高優(yōu)先級(jí)就緒任務(wù)的過(guò)程就變成了一個(gè)硬件相關(guān)的位操作尋找一個(gè)整數(shù)中從最低位LSB開(kāi)始第一個(gè)值為1的位的位置。這個(gè)操作有高效的匯編指令支持例如在ARM Cortex-M架構(gòu)上有CLZCount Leading Zeros指令在其他平臺(tái)也有類(lèi)似的編譯器內(nèi)置函數(shù)如__builtin_clz。通過(guò)這個(gè)指令我們可以在**常數(shù)時(shí)間O(1)**內(nèi)完成查找與系統(tǒng)中有多少任務(wù)、多少優(yōu)先級(jí)無(wú)關(guān)。舉個(gè)例子假設(shè)我們的就緒位圖值是0b0010 0100二進(jìn)制。從右向左低位到高位對(duì)應(yīng)優(yōu)先級(jí)從高到低看第2位優(yōu)先級(jí)2是1第5位優(yōu)先級(jí)5是1。優(yōu)先級(jí)2比優(yōu)先級(jí)5高。所以最高就緒優(yōu)先級(jí)是2。使用__builtin_ffsFind First Set查找第一個(gè)為1的位或基于CLZ的計(jì)算能立刻得到數(shù)字2。這就是位圖調(diào)度算法效率的根源它將一個(gè)需要遍歷的查找問(wèn)題轉(zhuǎn)化為了一個(gè)硬件極度優(yōu)化的位計(jì)算問(wèn)題。3. RT-Thread中位圖調(diào)度的實(shí)現(xiàn)解剖理解了思想我們直接切入RT-Thread以最新的LTS版本為例的源碼看看它是如何具體實(shí)現(xiàn)的。相關(guān)的核心代碼通常在rt-thread/src/目錄下的scheduler.c、sched.c或類(lèi)似文件中。3.1 核心數(shù)據(jù)結(jié)構(gòu)的定義首先系統(tǒng)會(huì)定義支持的最大優(yōu)先級(jí)數(shù)量。RT-Thread中默認(rèn)的宏定義通常是#define RT_THREAD_PRIORITY_MAX 32這意味著它使用一個(gè)32位的rt_uint32_t整數(shù)就足以表示所有優(yōu)先級(jí)的就緒狀態(tài)。這也是為什么我們常說(shuō)RT-Thread默認(rèn)支持32個(gè)優(yōu)先級(jí)0-310通常為最高優(yōu)先級(jí)。核心的全局變量就是這個(gè)位圖rt_uint32_t rt_thread_ready_priority_group;有的版本或配置下它可能被命名為rt_ready_priority_group或封裝在一個(gè)結(jié)構(gòu)體內(nèi)但本質(zhì)不變。3.2 任務(wù)狀態(tài)變化如何更新位圖位圖本身不會(huì)自動(dòng)變化它需要隨著任務(wù)的狀態(tài)遷移而同步更新。這是理解調(diào)度器如何工作的關(guān)鍵。當(dāng)一個(gè)任務(wù)從其他狀態(tài)如掛起、睡眠變?yōu)榫途w態(tài)時(shí)例如調(diào)用了rt_thread_startup()或rt_thread_resume()或者任務(wù)因延時(shí)到期而被喚醒最終會(huì)調(diào)用一個(gè)內(nèi)部函數(shù)如_rt_scheduler_insert_thread()或rt_schedule_insert_thread()。這個(gè)函數(shù)的關(guān)鍵操作之一就是rt_thread_ready_priority_group | 1UL thread-current_priority;這行代碼做了什么呢thread-current_priority是任務(wù)的優(yōu)先級(jí)。1UL priority生成一個(gè)只有該優(yōu)先級(jí)對(duì)應(yīng)位為1其他位為0的掩碼。例如優(yōu)先級(jí)5就得到0b0010 0000第5位為1從0開(kāi)始計(jì)數(shù)。|位或賦值操作將這個(gè)掩碼合并到全局就緒位圖中。無(wú)論該位原來(lái)是0還是1操作后都變?yōu)?。因?yàn)椤?”代表該優(yōu)先級(jí)有任務(wù)就緒至于有幾個(gè)任務(wù)位圖不關(guān)心它只記錄“有”或“無(wú)”。相反當(dāng)一個(gè)任務(wù)從就緒態(tài)變?yōu)槠渌麪顟B(tài)時(shí)例如調(diào)用了rt_thread_suspend()、rt_thread_delay()或者任務(wù)執(zhí)行完畢在調(diào)度器將其從就緒隊(duì)列移除后需要判斷該優(yōu)先級(jí)下是否還有別的就緒任務(wù)。如果沒(méi)有就需要清除位圖中的對(duì)應(yīng)位。這個(gè)邏輯通常在一個(gè)如_rt_scheduler_remove_thread()的函數(shù)里if (rt_list_isempty(rt_thread_priority_table[priority].thread_list)) { rt_thread_ready_priority_group ~(1UL priority); }這里rt_thread_priority_table是一個(gè)數(shù)組每個(gè)優(yōu)先級(jí)對(duì)應(yīng)一個(gè)鏈表頭掛載所有處于該優(yōu)先級(jí)的就緒任務(wù)。rt_list_isempty檢查這個(gè)鏈表是否為空。如果為空說(shuō)明此優(yōu)先級(jí)已無(wú)就緒任務(wù)于是使用 ~(mask)操作將位圖中的對(duì)應(yīng)位清零。3.3 調(diào)度決策如何找到最高優(yōu)先級(jí)任務(wù)調(diào)度發(fā)生的時(shí)機(jī)有很多任務(wù)主動(dòng)放棄CPUrt_thread_yield、任務(wù)阻塞如延時(shí)、等待信號(hào)量、中斷退出等。這時(shí)會(huì)調(diào)用rt_schedule()函數(shù)。在rt_schedule()中決策核心是選擇一個(gè)就緒任務(wù)來(lái)運(yùn)行。它通過(guò)一個(gè)函數(shù)如_rt_scheduler_get_highest_priority_thread()來(lái)實(shí)現(xiàn)register rt_ubase_t highest_ready_priority; if (rt_thread_ready_priority_group 0) { // 如果沒(méi)有就緒任務(wù)則切換到空閑任務(wù) // ... return; } // 使用編譯器內(nèi)置指令或匯編找到最高優(yōu)先級(jí) #if defined(__ARMCC_VERSION) || defined(__ICCARM__) // ARM編譯器或IAR編譯器 __asm volatile(clz %0, %1 : r(highest_ready_priority) : r(rt_thread_ready_priority_group)); highest_ready_priority 31 - highest_ready_priority; #elif defined(__GNUC__) // GCC編譯器 highest_ready_priority __builtin_clz(rt_thread_ready_priority_group); highest_ready_priority 31 - highest_ready_priority; #else // 通用C語(yǔ)言實(shí)現(xiàn)效率較低用于沒(méi)有內(nèi)置指令的CPU highest_ready_priority 0; while ((rt_thread_ready_priority_group (1UL highest_ready_priority)) 0) { highest_ready_priority; } #endif這段代碼是算法的精華首先檢查位圖是否全0無(wú)就緒任務(wù)如果是則調(diào)度到空閑任務(wù)。對(duì)于ARM Cortex-M等平臺(tái)直接使用CLZ指令或GCC的__builtin_clz函數(shù)。這個(gè)函數(shù)返回的是從最高位MSB開(kāi)始連續(xù)的0的個(gè)數(shù)。例如對(duì)于0b0010 0100__builtin_clz會(huì)返回29因?yàn)榍?9位都是0。我們需要的是從最低位開(kāi)始的第一個(gè)1的位置所以用31 - __builtin_clz(value)來(lái)計(jì)算。注意這里__builtin_clz的參數(shù)為0是未定義行為所以前面必須判斷位圖是否為0。計(jì)算出highest_ready_priority后調(diào)度器就可以直接從rt_thread_priority_table[highest_ready_priority]對(duì)應(yīng)的就緒鏈表中取出第一個(gè)任務(wù)通常是該優(yōu)先級(jí)下等待時(shí)間最長(zhǎng)的任務(wù)即隊(duì)頭任務(wù)來(lái)切換執(zhí)行。整個(gè)決策過(guò)程不涉及任何循環(huán)遍歷除非在沒(méi)有硬件指令支持的CPU上使用通用C實(shí)現(xiàn)只有幾次位運(yùn)算和內(nèi)存訪問(wèn)因此速度極快且執(zhí)行時(shí)間恒定。4. 位圖調(diào)度的優(yōu)勢(shì)、局限與實(shí)戰(zhàn)配置經(jīng)過(guò)上面的源碼分析位圖調(diào)度的特點(diǎn)已經(jīng)非常清晰。但在實(shí)際項(xiàng)目中我們?nèi)绾螕P(yáng)長(zhǎng)避短呢4.1 無(wú)可比擬的優(yōu)勢(shì)極致的速度與確定性O(shè)(1)的調(diào)度決策時(shí)間最壞情況與最好情況一致這對(duì)于需要嚴(yán)格時(shí)間保障的硬實(shí)時(shí)任務(wù)來(lái)說(shuō)是基石。極低的內(nèi)存開(kāi)銷(xiāo)僅需要一個(gè)或幾個(gè)整型變量作為位圖。對(duì)于32優(yōu)先級(jí)系統(tǒng)只需4字節(jié)。相比之下維護(hù)復(fù)雜的多級(jí)隊(duì)列需要更多的控制結(jié)構(gòu)。實(shí)現(xiàn)簡(jiǎn)單魯棒性高核心邏輯就是位操作和鏈表操作代碼量小易于理解和驗(yàn)證出錯(cuò)的概率低。天然支持優(yōu)先級(jí)搶占因?yàn)榭偰芰⒖陶业阶罡邇?yōu)先級(jí)就緒任務(wù)高優(yōu)先級(jí)任務(wù)一旦就緒可以在下次調(diào)度點(diǎn)如當(dāng)前任務(wù)調(diào)用系統(tǒng)API或中斷退出時(shí)立刻搶占低優(yōu)先級(jí)任務(wù)實(shí)時(shí)響應(yīng)性高。4.2 需要了解的局限性?xún)?yōu)先級(jí)數(shù)量限制單個(gè)32位位圖只能表示32個(gè)優(yōu)先級(jí)。雖然RT-Thread可以通過(guò)定義RT_THREAD_PRIORITY_MAX為更大的值如256并使用位圖數(shù)組如rt_uint32_t rt_thread_ready_priority_group[8]來(lái)擴(kuò)展但這會(huì)增加查找最高優(yōu)先級(jí)的復(fù)雜度需要遍歷數(shù)組找到第一個(gè)非零元素再在該元素內(nèi)查找不再是嚴(yán)格的O(1)。不過(guò)對(duì)于絕大多數(shù)嵌入式應(yīng)用32個(gè)優(yōu)先級(jí)已經(jīng)綽綽有余。不支持時(shí)間片輪轉(zhuǎn)純粹的位圖調(diào)度是嚴(yán)格基于優(yōu)先級(jí)的。同一優(yōu)先級(jí)的多個(gè)就緒任務(wù)會(huì)以先來(lái)先服務(wù)FIFO的方式在一個(gè)鏈表中排隊(duì)。如果一個(gè)高優(yōu)先級(jí)任務(wù)不主動(dòng)放棄CPU如調(diào)用延時(shí)、等待資源它將一直運(yùn)行導(dǎo)致同優(yōu)先級(jí)甚至低優(yōu)先級(jí)的任務(wù)被“餓死”。這是實(shí)時(shí)系統(tǒng)的常見(jiàn)設(shè)計(jì)要求開(kāi)發(fā)者合理設(shè)計(jì)任務(wù)優(yōu)先級(jí)和阻塞點(diǎn)。優(yōu)先級(jí)反轉(zhuǎn)的經(jīng)典場(chǎng)景位圖調(diào)度本身無(wú)法解決優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題。例如一個(gè)低優(yōu)先級(jí)任務(wù)L持有一個(gè)信號(hào)量一個(gè)中優(yōu)先級(jí)任務(wù)M正在運(yùn)行此時(shí)高優(yōu)先級(jí)任務(wù)H啟動(dòng)并嘗試獲取該信號(hào)量而被阻塞。由于H在等待L釋放信號(hào)量而L又因?yàn)镸一直在運(yùn)行而得不到CPU時(shí)間導(dǎo)致H實(shí)際上被M阻塞了這就是優(yōu)先級(jí)反轉(zhuǎn)。解決這個(gè)問(wèn)題需要額外的機(jī)制如優(yōu)先級(jí)繼承Priority Inheritance或優(yōu)先級(jí)天花板Priority CeilingRT-Thread的互斥量mutex實(shí)現(xiàn)了這些機(jī)制但這已經(jīng)超出了基礎(chǔ)位圖調(diào)度的范疇。4.3 在RT-Thread項(xiàng)目中的實(shí)戰(zhàn)配置與心得理解了原理和局限我們?cè)趯?shí)際使用RT-Thread時(shí)就能有的放矢。1. 優(yōu)先級(jí)的規(guī)劃是重中之重不要隨意分配優(yōu)先級(jí)。建議采用“事件關(guān)鍵性”和“執(zhí)行頻率”兩個(gè)維度來(lái)劃分高優(yōu)先級(jí)0-5分配給對(duì)響應(yīng)時(shí)間要求極其苛刻的硬實(shí)時(shí)任務(wù)如緊急故障處理、高速PWM輸出、關(guān)鍵傳感器中斷服務(wù)線(xiàn)程IST。這類(lèi)任務(wù)執(zhí)行時(shí)間應(yīng)非常短并盡快阻塞或讓出CPU。中優(yōu)先級(jí)6-15分配給主要的業(yè)務(wù)邏輯任務(wù)如控制算法計(jì)算、通信協(xié)議解析、狀態(tài)機(jī)處理。低優(yōu)先級(jí)16-31分配給后臺(tái)任務(wù)如日志上傳、非關(guān)鍵數(shù)據(jù)的統(tǒng)計(jì)、顯示器刷新等。2. 避免創(chuàng)建大量相同優(yōu)先級(jí)的任務(wù)如果確實(shí)需要多個(gè)相同優(yōu)先級(jí)的任務(wù)務(wù)必確保每個(gè)任務(wù)都有合理的阻塞點(diǎn)如rt_thread_delay()、rt_sem_take()讓出CPU給同優(yōu)先級(jí)的其他任務(wù)。否則鏈表中第一個(gè)任務(wù)將一直運(yùn)行。3. 利用RT-Thread的鉤子函數(shù)觀察調(diào)度RT-Thread提供了rt_scheduler_sethook()函數(shù)可以設(shè)置一個(gè)鉤子在每次任務(wù)切換時(shí)被調(diào)用。你可以在這個(gè)鉤子函數(shù)里記錄切換前后的任務(wù)信息結(jié)合SystemView或SEGGER的RTT工具可以直觀地看到任務(wù)調(diào)度的時(shí)間線(xiàn)分析是否存在優(yōu)先級(jí)配置不合理導(dǎo)致的阻塞或饑餓。4. 關(guān)于優(yōu)先級(jí)數(shù)量的配置在rtconfig.h中你可以修改RT_THREAD_PRIORITY_MAX。除非有特殊需求否則不建議盲目增大。每增加32個(gè)優(yōu)先級(jí)就需要多一個(gè)32位的位圖單元并且調(diào)度查找函數(shù)會(huì)稍微復(fù)雜一點(diǎn)。保持默認(rèn)的32并做好規(guī)劃通常是完全足夠的。5. 調(diào)試調(diào)度相關(guān)問(wèn)題的技巧當(dāng)懷疑調(diào)度器出現(xiàn)問(wèn)題時(shí)比如感覺(jué)某個(gè)任務(wù)沒(méi)及時(shí)運(yùn)行可以檢查就緒位圖在調(diào)試器中查看rt_thread_ready_priority_group的值換算成二進(jìn)制看看你期望的那個(gè)任務(wù)的優(yōu)先級(jí)對(duì)應(yīng)位是否為1。檢查任務(wù)狀態(tài)使用RT-Thread的list_thread命令在FinSH控制臺(tái)或通過(guò)調(diào)試器查看任務(wù)控制塊struct rt_thread的stat字段確認(rèn)任務(wù)是否真的處于RT_THREAD_READY狀態(tài)。檢查中斷屏蔽有時(shí)全局中斷被意外長(zhǎng)時(shí)間屏蔽會(huì)導(dǎo)致即使高優(yōu)先級(jí)任務(wù)就緒了也無(wú)法觸發(fā)調(diào)度因?yàn)檎{(diào)度往往發(fā)生在中斷退出時(shí)。位圖調(diào)度算法就像嵌入式世界里的“詠春拳”沒(méi)有炫酷的招式但每一招都直擊要害在有限的資源內(nèi)將效率提升到極致。理解它不僅能讓你更深刻地理解RT-Thread乃至其他RTOS的調(diào)度行為更能幫助你在設(shè)計(jì)自己的嵌入式系統(tǒng)時(shí)做出更合理、更可靠的任務(wù)劃分與優(yōu)先級(jí)規(guī)劃。下次當(dāng)你寫(xiě)下rt_thread_create時(shí)不妨想一想你賦予這個(gè)任務(wù)的優(yōu)先級(jí)將在那個(gè)小小的位圖里如何參與這場(chǎng)對(duì)CPU時(shí)間的無(wú)聲角逐。