1優先級查找

那么，CPU的任務從“尋找優先級最高的任務”變成了“尋找位圖中最低位的1”。如果按照上圖中依次按位查找，速度是較慢的，系統的實時性可能會有一定程度的影響，下面介紹一種較為巧妙的方法——分組查表法。? ? ? ? ? ? ? ? ? ? ?? ? ??圖2 分組查表法

const rt_uint8_t __lowest_bit_bitmap[] =
{
    /* 00 */ 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 10 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 20 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 30 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 40 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 50 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 60 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 70 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 80 */ 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 90 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* A0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* B0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* C0 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* D0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* E0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* F0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};


int __rt_ffs(int value)
{
    if (value == 0) return 0;


    if (value & 0xff)
        return __lowest_bit_bitmap[value & 0xff] + 1;


    if (value & 0xff00)
        return __lowest_bit_bitmap[(value & 0xff00) >> 8] + 9;


    if (value & 0xff0000)
        return __lowest_bit_bitmap[(value & 0xff0000) >> 16] + 17;


    return __lowest_bit_bitmap[(value & 0xff000000) >> 24] + 25;

這種方法將32位共分成4組，每組8位，那么每組的8位二進制數0x00~0xFF對應數組bitmap的序號0-255，數組中的值的含義為其對應8位二進制數最低位“1”的序號。那么通過這樣巧妙的分組查表方式，通過至多四次查找，便可得到位圖的最低位“1”的位置。除此之外，還有更為巧妙的利用匯編指令CLZ和RBIT組合實現這個目的，其中CLZ可以統計出現“1”的最高位位置，RBIT是數據進行按位反轉的指令。這樣就可以先通過RBIT進行位反轉，再通過CLZ獲取反轉后最高位“1”的位置，即原數據中最低位“1”的位置。

2臨界區保護和線程同步

在RTOS中，時常會出現多個線程訪問公用資源的情況，即都需要訪問公用的程序片段，如若沒有對應的處理機制，可能會對系統造成意想不到的混亂。常用的方法有調度器上鎖和禁止中斷，這兩者相互依賴，例如在調度器上鎖時需要禁止中斷。除此之外，還可以采用互斥機制來進行臨界區保護，如信號量和互斥量，這兩者也用于線程的同步機制。

圖3 信號量類比

圖4 互斥量類比

? ? ? ? ? ? ? ? ? ?

3優先級反轉問題

當隱入互斥量的機制后，讀者可以思考一下，這會不會和優先級機制產生沖突？

? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? 圖6? 優先級反轉

如上圖，假設我們有三個線程，它們的優先級Thread1 > Thread2 > Thread3，t0之前Thread3獲取某資源的互斥量，互斥量值變locked狀態，t0時刻Thread2線程就緒，由于優先級Thread2 > Thread3，Thread3讓出CPU執行權給Thread2，但沒有解開互斥量。到t1時刻，Thread1就緒，Thread2讓出CPU，Thread1執行過程申請Thread3所占有的互斥量，由于互斥量為locked狀態，在t2時刻Thread1被掛起等待，剩余兩個就緒態的線程Thread2優先級高于Thread1，因此繼續執行。

4線程間通信

5總結

至此，一個RTOS的內核功能基本就實現了，下面對一個RTOS Kernel應具備的功能進行分條總結：

實時性：實時系統對任務的響應時間要求較高。具備嚴格的按優先級調度任務的機制，并且一般要支持搶占式調度。

多任務調度：RTOS需要能夠同時管理多個任務，并合理分配CPU時間片給每個任務。設計任務調度算法以確保相同優先級的任務能公平使用CPU，避免優先級反轉問題，并提供優先級繼承、優先級天花板等機制。

同步和通信：多任務系統中，任務之間需要進行同步和通信。設計合適的同步機制，如信號量、互斥鎖、消息隊列等，并確保在多個任務之間實現可靠的數據傳輸和共享。

但是，這些僅僅是內核的基本功能，一個成熟的RTOS還應該具有更多的擴展功能予以支撐。例如內存管理功能、外設驅動的支持、硬件依賴性和可移植性、調試和測試功能等等。羅馬非一日而建，希望大家都能腳踏實地，樂于鉆研，樂于進步，共勉！

END

更多恩智浦AI-IoT市場和產品信息，邀您同時關注“NXP客棧”微信公眾號

NXP客棧

恩智浦致力于打造安全的連接和基礎設施解決方案，為智慧生活保駕護航。

長按二維碼，關注我們

恩智浦MCU加油站

這是由恩智浦官方運營的公眾號，著重為您推薦恩智浦MCU的產品信息、開發技巧、教程文檔、培訓課程等內容。

長按二維碼，關注我們