1優(yōu)先級查找

那么，CPU的任務(wù)從“尋找優(yōu)先級最高的任務(wù)”變成了“尋找位圖中最低位的1”。如果按照上圖中依次按位查找，速度是較慢的，系統(tǒng)的實時性可能會有一定程度的影響，下面介紹一種較為巧妙的方法——分組查表法。? ? ? ? ? ? ? ? ? ? ?? ? ??圖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位二進(jìn)制數(shù)0x00~0xFF對應(yīng)數(shù)組bitmap的序號0-255，數(shù)組中的值的含義為其對應(yīng)8位二進(jìn)制數(shù)最低位“1”的序號。那么通過這樣巧妙的分組查表方式，通過至多四次查找，便可得到位圖的最低位“1”的位置。除此之外，還有更為巧妙的利用匯編指令CLZ和RBIT組合實現(xiàn)這個目的，其中CLZ可以統(tǒng)計出現(xiàn)“1”的最高位位置，RBIT是數(shù)據(jù)進(jìn)行按位反轉(zhuǎn)的指令。這樣就可以先通過RBIT進(jìn)行位反轉(zhuǎn)，再通過CLZ獲取反轉(zhuǎn)后最高位“1”的位置，即原數(shù)據(jù)中最低位“1”的位置。

2臨界區(qū)保護(hù)和線程同步

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

圖3 信號量類比

圖4 互斥量類比

? ? ? ? ? ? ? ? ? ?

3優(yōu)先級反轉(zhuǎn)問題

當(dāng)隱入互斥量的機制后，讀者可以思考一下，這會不會和優(yōu)先級機制產(chǎn)生沖突？

? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? 圖6? 優(yōu)先級反轉(zhuǎn)

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

4線程間通信

5總結(jié)

至此，一個RTOS的內(nèi)核功能基本就實現(xiàn)了，下面對一個RTOS Kernel應(yīng)具備的功能進(jìn)行分條總結(jié)：

實時性：實時系統(tǒng)對任務(wù)的響應(yīng)時間要求較高。具備嚴(yán)格的按優(yōu)先級調(diào)度任務(wù)的機制，并且一般要支持搶占式調(diào)度。

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

同步和通信：多任務(wù)系統(tǒng)中，任務(wù)之間需要進(jìn)行同步和通信。設(shè)計合適的同步機制，如信號量、互斥鎖、消息隊列等，并確保在多個任務(wù)之間實現(xiàn)可靠的數(shù)據(jù)傳輸和共享。

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

END

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

NXP客棧

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

長按二維碼，關(guān)注我們

恩智浦MCU加油站

這是由恩智浦官方運營的公眾號，著重為您推薦恩智浦MCU的產(chǎn)品信息、開發(fā)技巧、教程文檔、培訓(xùn)課程等內(nèi)容。

長按二維碼，關(guān)注我們