1. 前言

linux 內(nèi)核有一套對(duì)系統(tǒng)負(fù)載的衡量算法，其底層使用的是指數(shù)衰退算法。

指數(shù)衰退算法從邏輯上是必須要依賴小數(shù)運(yùn)算的，然而如你所知，內(nèi)核中不允許使用浮點(diǎn)運(yùn)算，硬浮點(diǎn)會(huì)引入 FPU，這將導(dǎo)致內(nèi)核態(tài)-用戶態(tài)之間切換時(shí)，需要保存更多的浮點(diǎn)寄存器而引入額外的開銷，而軟浮點(diǎn)依賴編譯器實(shí)現(xiàn)的軟浮點(diǎn)運(yùn)算子，亦是額外的開銷。

本文的出發(fā)點(diǎn)即在此，從工程角度分析 linux 內(nèi)核負(fù)載計(jì)算所涉及到的技巧細(xì)節(jié)。這個(gè)分析是有普適價(jià)值的，可以借鑒到讀者自己的內(nèi)核態(tài)編程中，同時(shí)也適用于其他需要高效進(jìn)行小數(shù)計(jì)算的場(chǎng)景。

2. 指數(shù)衰退

本章節(jié)介紹指數(shù)衰退算法，已經(jīng)熟悉了的同學(xué)直接跳過。

2.1 是什么

假設(shè)有這樣一組系統(tǒng)的負(fù)載采樣時(shí)序：

我們希望衡量系統(tǒng)這段時(shí)間內(nèi)的負(fù)載情況，要求將過去時(shí)間點(diǎn)上的負(fù)載采樣也納入對(duì)系統(tǒng)整體負(fù)載的影響考量。

一個(gè)最容易想到的算法就是取 Tn-5 - Tn 這段時(shí)間內(nèi)的負(fù)載均值，作為系統(tǒng)負(fù)載的量化。

一定時(shí)間內(nèi)負(fù)載采樣點(diǎn)取均值，該思想的本質(zhì)是過去一段時(shí)間內(nèi)，任意采樣點(diǎn)上的值，對(duì)當(dāng)前系統(tǒng)負(fù)載的評(píng)估的影響有相同權(quán)重。

指數(shù)衰退的思想，本質(zhì)上是不同時(shí)間點(diǎn)上的采樣的對(duì)整體評(píng)估的影響權(quán)重不同，離當(dāng)前時(shí)刻越近的采樣點(diǎn)影響權(quán)重越高，反之越小，并且采樣點(diǎn)間的影響權(quán)重呈指數(shù)級(jí)衰退。該思想也常用于對(duì)曲線的濾波平滑（指數(shù)平滑）。

2.2 數(shù)學(xué)推導(dǎo)

假設(shè)當(dāng)前時(shí)刻采樣對(duì)整體評(píng)估的影響權(quán)重是 w，寫成公式(1)：

L = w * Ln + (1 - w) * w * Ln-1 + (1 - w)2 * w * Ln-2 + (1 - w)3 * w * Ln-3 + (1 - w)4 * w * Ln-4 + (1 - w)5 * w * Ln-5 + ...

記上一次采樣點(diǎn)上系統(tǒng)的整體負(fù)載為 L'，得式(2)：

L' = w * Ln-1 + (1 - w) * w * Ln-2 + (1 - w)2 * w * Ln-3 + (1 - w)3 * w * Ln-4 + (1 - w)4 * w * Ln-5 + ...

式(2) 兩邊乘上 (1 - w)，得式(3)：

(1 - w ) * L' = (1 - w) * w * Ln-1 + (1 - w)2 * w * Ln-2 + (1 - w)3 * w * Ln-3 + (1 - w)4 * w * Ln-4 + (1 - w)5 * w * Ln-5 + ...

式(3) 代入式(1)，得式(4)：

L = w * Ln + (1 - w ) * L'

2.3 工程化

對(duì)于式(4)：

w：當(dāng)前采樣值對(duì)整體負(fù)載評(píng)估的貢獻(xiàn)權(quán)重

Ln：當(dāng)前采樣值

L'：上個(gè)采樣點(diǎn)上，系統(tǒng)的整體負(fù)載評(píng)估值

L：當(dāng)前采樣點(diǎn)上，系統(tǒng)的整體負(fù)載評(píng)估值

寫成代碼：

/* curr 是當(dāng)前采樣值
 * last_load 是上一時(shí)刻的系統(tǒng)負(fù)載
 */
double cal_load(double last_load,  unsigned long long curr)
{
    // 0.6 只是隨意取的一個(gè)權(quán)重值
    static double w = 0.6;
    return w * curr + (1 - w) * last_load;
}

int main() {
    int i;
    double load;
    unsigned long long samplings[] = {
        [0] = 9,
        [1] = 8,
        [2] = 7,
        [3] = 6,
        [4] = 5,
        [5] = 7,
        [6] = 6,
        [7] = 4,
        [8] = 2,
        [9] = 1,
    };

    for (i = 0; i < sizeof(samplings) / sizeof(unsigned long long); ++i) {
        load = cal_load(load, samplings[i]);
        printf("%lfn", load);
    }
}

輸出：
5.400000
6.960000
6.984000
6.393600
5.557440
6.422976
6.169190
4.867676
3.147070
1.858828

3. 浮點(diǎn)數(shù)

3.1 浮點(diǎn)數(shù)的存儲(chǔ)

有關(guān)此話題更為嚴(yán)謹(jǐn)?shù)挠懻摚瑓⒖?《IEEE Standard 754Floating Point Numbers》Steve Hollasch 一文。

對(duì)浮點(diǎn)數(shù)在計(jì)算機(jī)的存儲(chǔ)很懂的同學(xué)直接跳過本節(jié)。

如你所知，單精度（float）、雙精度（double）數(shù)在計(jì)算機(jī)中的存儲(chǔ)，是遵循 IEEE 標(biāo)準(zhǔn)的。這個(gè)很好理解，因?yàn)橛?jì)算只認(rèn)識(shí) 0 和 1，無論什么數(shù)存到內(nèi)存之后就是一坨 01 序列。如果不制定標(biāo)準(zhǔn)，計(jì)算機(jī)就不知道該怎么解釋這串 01 序列。

本節(jié)以單精度的表示來講解（雙精度原理一樣，只是階碼、尾數(shù)所占的比特位數(shù)與單精度不同）。

單精度在計(jì)算機(jī)中如此表示：

此單精度浮點(diǎn)數(shù)（下文簡(jiǎn)稱“浮點(diǎn)數(shù)”）的值為式(5)：

V = (-1)S x (1.M) x 2(E - 127)

這里對(duì) 式(5) 稍微解釋一下：

階碼理解為指數(shù)，尾數(shù)理解為底數(shù)。
為什么當(dāng)尾數(shù)存儲(chǔ)的是 M 時(shí)，實(shí)際的運(yùn)算使用的尾數(shù)卻是 1.M？

因?yàn)檫@里本質(zhì)上是科學(xué)計(jì)數(shù)法，科學(xué)計(jì)數(shù)法要求底數(shù)的整數(shù)部分不能為 0：

1000 = 1 x 103        這是正確的表示法  
1000 = 0.1 x 104    這是錯(cuò)誤的表示法

在浮點(diǎn)數(shù)的存儲(chǔ)中亦然，計(jì)算機(jī)使用二進(jìn)制，故尾數(shù)的整數(shù)部分必然是 1，既然必然是 1，這個(gè) 1 也就沒有必要存儲(chǔ)了，如此尾數(shù)位中可以節(jié)省一個(gè) bit 來表示更高精度的數(shù)據(jù)。

為什么當(dāng)階碼存儲(chǔ)的是 E 時(shí)，實(shí)際的運(yùn)算使用的階碼卻是 E - 127？

階碼是可能存在為負(fù)數(shù)的情況的：

0.001 = 1 x 10-3

浮點(diǎn)數(shù)亦不例外。試想：

如果 E 為 8 個(gè) 1(0xFF)，也就是 255，那么此時(shí)算出來的實(shí)際階碼為 255 - 127 = 128
如果 E 為 8 個(gè) 0(0x00)，也就是 0，那么此時(shí)算出來的實(shí)際階碼為 0 - 127 = -127

換句話說，我們?cè)谶@里加上 127 這個(gè)偏置，效果就是用 127 來表示邏輯上的 0，那么：

邏輯上的 +128，表示為 127 + 128 = 255
邏輯上的 -127，表示為 127 - 127 = 0

通過使用 127 來表示邏輯 0 這個(gè) trick，實(shí)現(xiàn)了用 8 位位寬表示邏輯上的 [-127, 128]。

3.2 進(jìn)制轉(zhuǎn)換

為了方便后面定點(diǎn)數(shù)的推導(dǎo)，本章節(jié)提一下十進(jìn)制與二進(jìn)制間的轉(zhuǎn)換算法。

已經(jīng)很懂的同學(xué)自行跳過。

十進(jìn)制整數(shù)轉(zhuǎn)二進(jìn)制

算法：除 2 取余，逆序輸出。

算法比較簡(jiǎn)單，這里直接用 python 代碼描述（挫）：

def dec_int2bin(n):
    res = ""
    while n:
        res = str(n & 1) + res
        n /= 2
    print res

# 打印十進(jìn)制數(shù) 12 的二進(jìn)制表示
dec_int2bin(12)

# output
# 1100

十進(jìn)制小數(shù)轉(zhuǎn)二進(jìn)制

這里注意十進(jìn)制的小數(shù)轉(zhuǎn)二進(jìn)制，算法與十進(jìn)制整數(shù)不同。

算法：將小數(shù)部分不斷乘以2，每次取整數(shù)部分，直到最后乘積結(jié)果為 1。

用 python 描述（挫）：

def dec_frac2bin(n):
    res = "0."
    nbits = 0
    while n:
        n *= 2
        INT = int(n)
        n = n - INT
        if nbits % 4 == 0 and nbits:
            res += " "
        nbits += 1
        res += str(INT)
    print res

# 打印 0.3125 的二進(jìn)制表示
dec_frac2bin(0.3125)

# output
# 0.0101

計(jì)算過程：

二進(jìn)制小數(shù)轉(zhuǎn)十進(jìn)制

算法：各個(gè)位乘以 2 的負(fù)次方，最后將結(jié)果相加（本質(zhì)上就是十進(jìn)制小數(shù)轉(zhuǎn)二進(jìn)制的逆運(yùn)算）。

如二進(jìn)制的小數(shù) 0.0101，轉(zhuǎn)成十進(jìn)制小數(shù)：

0 x 2-1 + 1 x 2-2 + 0 x 2-3 + 1 x 2-4 = 0.3125

用 python 描述（挫）：

def bin2dec(n, w):
    res = 0
    n = int(n * pow(10, w))


    while n:
        res += pow(2, -w) if n % 10 == 1 else 0
        w -= 1
        n /= 10

    print res


# 打印二進(jìn)制小數(shù) 0.0101 的十進(jìn)制數(shù)值
bin2dec(0.0101, 4)

# output
# 0.3125

3.3 實(shí)踐驗(yàn)證理論

根據(jù)上兩節(jié)的知識(shí)，我們來驗(yàn)證一下實(shí)際的浮點(diǎn)表示是否符合預(yù)期：

void main(void) {
    float f = 12.3125;
    assert(sizeof(f) == sizeof(uint32_t));
    printf("0x%xn", *(uint32_t *)&f);
}

上面的代碼打印出 12.3125 在內(nèi)存中存儲(chǔ)的二進(jìn)制 bit 序列，直接以圖的形式展示輸出結(jié)果：

S：0，表示是正數(shù)
E：0x82 - 127 = 3
M：1.1000 101(b) = 1.5390625(d)

根據(jù) 式(5)：

V = 1.5390625 * 23 = 12.3125

3.4 “浮”的本質(zhì)

隨著尾數(shù)、階碼的變化，小數(shù)點(diǎn)在最終數(shù)值中的位置是跟著變化的，換句話說，你根本不知道它小數(shù)點(diǎn)后是精確到第幾位的。

3.5 精度的喪失

注意：本節(jié)的推導(dǎo)皆是通過工程手段進(jìn)行的，沒有嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)論證，因?yàn)槲也粫?huì)。

浮點(diǎn)的“點(diǎn)”雖然是在“浮”的，但限于計(jì)算機(jī)的離散性，無法無限精度的“浮”

浮點(diǎn)數(shù)精度的喪失從兩個(gè)角度來考慮，我們觀察 3.2 節(jié)提到的兩個(gè)算法：

十進(jìn)制小數(shù)轉(zhuǎn)二進(jìn)制算法：此算法反復(fù)乘以 2，取整數(shù)部分的值為當(dāng)前二進(jìn)制的 bit，直到這個(gè)數(shù)最終變成 0。這里存在此算法無法在有限次數(shù)內(nèi)收斂的問題，如果此算法拿到的 bit 序列，長(zhǎng)度超過尾數(shù)位寬（超出了尾數(shù)能表示的范圍），會(huì)導(dǎo)致精度喪失。
二進(jìn)制小數(shù)轉(zhuǎn)十進(jìn)制算法：根據(jù)此算法，浮點(diǎn)所能表達(dá)的最小的顆粒度為 2-23（十進(jìn)制的 0.00000011920928955078125），這個(gè)類似物理學(xué)中的普朗克常量，不可繼續(xù)切分，若想表達(dá)比這個(gè)粒度還小的精度，float 無能為力。

根據(jù)“最小的顆粒度為 2-23”，我們推定精度比 0.0000001 還小的數(shù)，float 無法表示。

從另外一個(gè)角度來驗(yàn)證這個(gè)事情：

考慮 1.00001、1.000001、1.0000001 幾個(gè)十進(jìn)制小數(shù)，根據(jù)“二進(jìn)制小數(shù)轉(zhuǎn)十進(jìn)制”的算法，我們得出幾者的二進(jìn)制表示：

1.000001（十進(jìn)制）：

1.0000 0000 0000 0000 0001 0000 1100 0110 1111 0111 1010 0000 1011 0101 1110 1101 1000 1101

1.0000001（十進(jìn)制）：

1.0000 0000 0000 0000 0000 0001 1010 1101 0111 1111 0010 1001 1010 1011 1100 1010 1111 0100 1

1.00000001（十進(jìn)制）：

1.0000 0000 0000 0000 0000 0000 0010 1010 1111 0011 0001 1101 1100 0100 0110 0001 0001 1000 0111 01

float 型尾數(shù)位寬只有 23 位（除去最前面的 1），可以看出：

1.0000001，二進(jìn)制表示的前 23 位皆已丟失。
1.00000001，二進(jìn)制表示的前 26 位皆已丟失（死的很徹底）。

這里斷言，從 1.0000001（包括）開始，更高精度的數(shù) float 型都無法表示，驗(yàn)證一下（打臉）：

/* ORIGIN 表示原數(shù)據(jù)
 * IEEE 表示實(shí)際在內(nèi)存中存儲(chǔ)的 bit 序列
 * PRINT 表示再次打印出來是啥
 */
void main(void) {
    float f = 1.0000001;
    
    printf("ORIGIN: %sn", "1.0000001");  
    // 這里不符合上述斷言的預(yù)期，從推理上來說尾數(shù)部分應(yīng)該是 0，實(shí)際為 1
    printf("IEEE  : 0x%xn", *(uint32_t *)&f);
    printf("PRINT : %.20fn", f);

    // 這里符合預(yù)期
    f = 1.00000001;
    printf("ORIGIN: %sn", "1.00000001");
    printf("IEEE  : 0x%xn", *(uint32_t *)&f);
    printf("PRINT : %.20fn", f);
}

上述程序輸出：

ORIGIN: 1.0000001
IEEE     : 0x3f800001 < PRINT  : 1.00000011920928955078
ORIGIN: 1.00000001
IEEE     : 0x3f800000 < PRINT  : 1.00000000000000000000

雖然被打臉了，但基本符合預(yù)期，作為一個(gè)工程角度的文章，就分析到這里。

如有同學(xué)知道何因，敬請(qǐng)告知。

4. 定點(diǎn)數(shù)

4.1 基本概念

工程角度來說，定點(diǎn)數(shù)的本質(zhì)就是使用整型變量實(shí)現(xiàn)小數(shù)運(yùn)算。

定點(diǎn)數(shù)“定”的本質(zhì)，就是小數(shù)點(diǎn)是固定的，小數(shù)點(diǎn)后精確的位數(shù)是固定的。

定點(diǎn)數(shù)的理解有點(diǎn)直覺，請(qǐng)牢記心法：眼中無點(diǎn)，心中有點(diǎn)。

為輔助理解，使用十進(jìn)制的定點(diǎn)數(shù)來講解。

現(xiàn)在你在一臺(tái)不支持使用浮點(diǎn)類型的計(jì)算機(jī)上工作：

如果你要執(zhí)行的算法不需要很高的精度，無需小數(shù)位。

這種情況非常簡(jiǎn)單，所有的數(shù)直接用整型表示，該做什么運(yùn)算就做什么運(yùn)算。

所有的數(shù)本質(zhì)上是小數(shù)位只有 0 位的小數(shù)。

如果你要執(zhí)行的算法需要保留小數(shù)點(diǎn)后 1 位

這情況下，我們可以使用 10 來表示邏輯上的 1，11來表示邏輯上的 1.1。

那么 35 表示邏輯上的 3.5，15 表示邏輯上的 1.5：

35 + 15 = 50（邏輯上的 5.0）  
35 - 15 = 20（邏輯上的 2.0）  
35 * 15 = 525（邏輯上的 52.5） < 35 / 15 = 2（邏輯上的 0.2） <

從直覺上看，兩個(gè)定點(diǎn)數(shù)的乘除法需要對(duì)最終結(jié)果進(jìn)行修正，但是怎么理解這里需要修正？

定點(diǎn)數(shù)乘法運(yùn)算的修正

假設(shè)計(jì)算 3.5 * 1.5，擺出算式：

試問，最終的結(jié)果 525，它的小數(shù)點(diǎn)應(yīng)該點(diǎn)在哪？有小學(xué)算術(shù)底子的應(yīng)該都知道，點(diǎn)在第一個(gè) 5 后面，結(jié)果是 5.25。

那在定點(diǎn)數(shù)場(chǎng)景下，用 35 表示 3.5，15 表示 1.5，算出來的結(jié)果 525，請(qǐng)問邏輯上的小數(shù)點(diǎn)應(yīng)該點(diǎn)在哪？當(dāng)然與上面一樣。

對(duì)于 1 位定點(diǎn)數(shù)來說，35 * 15 最終的結(jié)果要再除以 10，才是最終計(jì)算的結(jié)果，本質(zhì)上是因?yàn)?35 和 15 都是一個(gè)有一個(gè)小數(shù)位的小數(shù)（請(qǐng)默念心法），它們相乘后，會(huì)對(duì)最終的結(jié)果貢獻(xiàn)出 2 位的小數(shù)部分來（如同 3.5 x 1.5 = 5.25，5.25 其實(shí)是有兩位小數(shù)部分的）。

因而定點(diǎn)數(shù)下，需要通過再除以 10（抹去多出來的那個(gè)小數(shù)位）來對(duì)最終的結(jié)果進(jìn)行修正，也就是 52，邏輯上的結(jié)果就是 5.2。

定點(diǎn)數(shù)除法運(yùn)算的修正

除法的本質(zhì)與乘法是反著來的，乘法是多出來一個(gè)小數(shù)位，除法是少了一個(gè)小數(shù)位。

觀察到 3.5 / 1.5 = 2，其結(jié)果 2 是一個(gè)小數(shù)位長(zhǎng)度為 0 的數(shù)，它丟掉了原本應(yīng)該有的 1 位小數(shù)精度，而其本質(zhì)應(yīng)該是 2.0。

如果用 35 / 15，答案還是 2，但是這個(gè) 2 是丟掉了 1 位小數(shù)精度后的結(jié)果，通過乘以 10 來補(bǔ)回丟失的 1 位小數(shù)精度，修正結(jié)果是 20。

實(shí)際工程中，由于計(jì)算機(jī)的整型運(yùn)算會(huì)自動(dòng)取整，所以在做定點(diǎn)數(shù)運(yùn)算時(shí)，如果先算結(jié)果再修正，不可避免會(huì)喪失精度（唯一的 1 位小數(shù)精度都丟失了）。

要規(guī)避這個(gè)問題，可以先修正再做除法，其與先做除法再修正邏輯上等價(jià)，但可以保留小數(shù)部分的精度，也即：

(35 * 10) / 15 = 23，邏輯結(jié)果對(duì)應(yīng) 2.3。

定點(diǎn)數(shù)的加減法無需修正的本質(zhì)，是因?yàn)檫@此二者運(yùn)算不會(huì)對(duì)小數(shù)位精度產(chǎn)生影響。

4.2 推廣及工程實(shí)踐

將上一節(jié)的基本概念進(jìn)行推廣，假設(shè)要執(zhí)行的算法需要保留小數(shù)點(diǎn)后 N 位。

經(jīng)過上節(jié)的分析，應(yīng)該很好理解，這里羅列幾個(gè)重要的點(diǎn)即可：

將一個(gè)邏輯上的數(shù) a 轉(zhuǎn)換成定點(diǎn)表示：a * 10N
兩個(gè)定點(diǎn)數(shù)的乘法修正：a * b / 10N（兩個(gè) N 位的定點(diǎn)數(shù)相乘，結(jié)果是 2N 位的定點(diǎn)數(shù)，要抹掉多余的 N 位小數(shù)）。
兩個(gè)定點(diǎn)數(shù)的除法修正：a * 10N / b（最終結(jié)果補(bǔ)回 N 位小數(shù)）。

對(duì)于定點(diǎn)數(shù)的四則運(yùn)算方面我們已經(jīng)掌握，還剩最后一步比較 tricky 的地方：如何取出一個(gè)定點(diǎn)數(shù)的整數(shù)及小數(shù)部分（我們希望能打印出最終的邏輯值）。

下面討論小數(shù)點(diǎn)后為 3 位（N = 3）的定點(diǎn)數(shù) 3165。

取出整數(shù)部分

這個(gè)比較簡(jiǎn)單容易理解，3165 / 103 = 3。

取出小數(shù)部分

小數(shù)部分是 165，直接返回 165 不是不行，但是考慮一個(gè)場(chǎng)景：只保留小數(shù)點(diǎn)后 1 位。該場(chǎng)景下如何設(shè)計(jì)一個(gè)通用的算法將小數(shù)點(diǎn)后只保留 1 位的小數(shù)部分返回？

一種可行的手法是，先把 165 x 101（保留小數(shù)點(diǎn)后 M 位就乘以 10M），得到 1650，再將 1650 這個(gè)定點(diǎn)數(shù)取其整數(shù)部分即可。說的形象點(diǎn)，就是把想要的小數(shù)部分給“擠”到整數(shù)位去。

實(shí)現(xiàn)四舍五入

假設(shè)你有一個(gè)實(shí)實(shí)在在的小數(shù) 3.165，如何實(shí)現(xiàn)四舍五入（小數(shù)點(diǎn)后保留 1 位）？

一個(gè)可行的算法是，給這個(gè)小數(shù)，加上 0.05，如此在小數(shù)點(diǎn)后第 2 位 >= 5 時(shí)，可以產(chǎn)生進(jìn)位溢出到第 1 位上。

反之不會(huì)對(duì)第 1 位產(chǎn)生影響。

3.165 + 0.05 = 3.215，保留 1 位小數(shù)即是 3.2。

推廣到一般情況，針對(duì)一個(gè) N 位定點(diǎn)數(shù)，我們希望實(shí)現(xiàn)保留 M 位，且小數(shù)部分的第 M + 1 位四舍五入。

先看個(gè)表：

從上圖可以看出，若要實(shí)現(xiàn)保留 M 位小數(shù)點(diǎn)的四舍五入，需要加上 5 * 10N-(M+1) 。

或者，可以從另一個(gè)角度來推導(dǎo)。假設(shè)要加上的這個(gè)數(shù)在定點(diǎn)數(shù)表示法下為 x，已知定點(diǎn)數(shù)表示法下的邏輯 1 為 10N，而我們想要加上的邏輯值為 5 * 10-(M + 1)，那么必然滿足下式：

解得：

x = 5 * 10N-(M+1)

用簡(jiǎn)單的代碼表示：

// 定義 fixed-point 數(shù)類型
typedef unsigned long long fp_t;

// 3 位定點(diǎn)數(shù)
#define N               3
// 最終取值保留小數(shù)點(diǎn)后 1 位
#define M               1

// 將非定點(diǎn)數(shù)轉(zhuǎn)成定點(diǎn)數(shù)
fp_t __to_FP(unsigned long long n)
{
  return n * pow(10, N);
}

// 獲取一個(gè)定點(diǎn)數(shù)的整數(shù)部分
unsigned long long fetch_INT(fp_t n)
{
  return n / pow(10, N);
}

// 去掉定點(diǎn)數(shù)的整數(shù)部分
unsigned long long __wipe_INT(fp_t n)
{
  unsigned long long INT = fetch_INT(n);
  return n - __to_FP(INT);
}

// 獲取定點(diǎn)數(shù)的小數(shù)部分
unsigned long long fetch_FRAC(fp_t n)
{
  return fetch_INT(__wipe_INT(n) * pow(10, M));
}

// 下面是四則運(yùn)算
fp_t add0(fp_t a, unsigned long long b)
{
  return a + __to_FP(b);
}

fp_t add1(unsigned long long a, unsigned long long b)
{
  return add0(__to_FP(a), b);
}

fp_t sub0(fp_t a, unsigned long long b)
{
  return a - __to_FP(b);
}

fp_t sub1(unsigned long long a, unsigned long long b)
{
  return sub0(__to_FP(a), b);
}

fp_t mul0(fp_t a, unsigned long long b)
{
  return (a * __to_FP(b)) / pow(10, N);
}

fp_t mul1(unsigned long long a, unsigned long long b)
{
  return mul0(__to_FP(a), b);
}

fp_t div0(fp_t a, unsigned long long b)
{
  return a  * pow(10, N) / __to_FP(b);
}

fp_t div1(unsigned long long a, unsigned long long b)
{
  return div0(__to_FP(a), b);
}

// 四舍五入
fp_t fp_round(fp_t a)
{
  return a + 5 * pow(10, N - (M + 1));
}

void main() {
  /* 3 + 5 = 8
   * 8 - 1 = 7
   * 7 * 2 = 14
   * 14 / 3 = 4.666666
   */
    fp_t n = add1(3, 5);
    n = sub0(n, 1);
    n = mul0(n, 2);
    n = div0(n, 3);

    // 最終符合預(yù)期的輸出是 4.6
    printf("%llu.%llun", fetch_INT(n), fetch_FRAC(n));
    // 符合預(yù)期的輸出是 4.7
    printf("%llu.%llun", fetch_INT(fp_round(n)), fetch_FRAC(fp_round(n)));
}

4.3 二進(jìn)制定點(diǎn)數(shù)

對(duì) 10 進(jìn)制定點(diǎn)數(shù)表示法的討論可以輔助理解，實(shí)際工程中 10 進(jìn)制在運(yùn)算方面沒有 2 進(jìn)制高效（2 進(jìn)制可以使用位移代替指數(shù)運(yùn)算），內(nèi)核在定點(diǎn)數(shù)方面的實(shí)踐即如此。

假設(shè)想使用一個(gè)整型的低 N 位來表示小數(shù)部分，幾個(gè)關(guān)鍵點(diǎn)在于：

將一個(gè)邏輯上的數(shù) a 轉(zhuǎn)成定點(diǎn)數(shù)表示：a << N（等價(jià)于 a * 2N）

因?yàn)檫壿嬌系?1，在定點(diǎn)數(shù)表示法下為 1 << N，那么邏輯上的數(shù) a，其在定點(diǎn)數(shù)表示法中對(duì)應(yīng)的數(shù) x，滿足如下方程：

解得：

x = a * 2N = (a   N)

兩個(gè)定點(diǎn)數(shù)的乘法修正：(a * b) >> N（多出來 N 個(gè)二進(jìn)制位）
兩個(gè)定點(diǎn)數(shù)的除法修正：(a << N) / b（少了 N 個(gè)二進(jìn)制位）
取整數(shù)部分：a >> N（把低 N 位的小數(shù)移除掉）
取小數(shù)部分：

分兩步走：1. 去掉整數(shù)部分，也即把整數(shù)部分掩掉：a & ((1 << N) - 1)，2. 把想要保留的小數(shù)部分“擠”到整數(shù)位，因?yàn)槲覀円〉氖鞘M(jìn)制下的 M 位，所以需要對(duì)去掉整數(shù)部分后的數(shù)，乘上 10M，再取整，即 fetch_INT(__wipe_INT(a) * 10M)

四舍五入：

與十進(jìn)制類似，要加上二進(jìn)制定點(diǎn)數(shù)下的邏輯值 5 * 10-(M+1)，將十進(jìn)制下小數(shù)點(diǎn)后第 M + 1 位溢出到第 M 位上。

這里的關(guān)鍵在于求出 N 位二進(jìn)制定點(diǎn)數(shù)表示法下，對(duì)應(yīng)邏輯值 5 * 10-(M+1) 的定點(diǎn)數(shù)的值。實(shí)際上，這個(gè)值滿足下面的方程：

解得：

x = 2N * 5 * 10-(M+1)

代碼實(shí)現(xiàn)如下：

// 定義 fixed-point 數(shù)類型
typedef unsigned long long fp_t;

// 第 N 位用來表示小數(shù)位
// 本質(zhì)上是用 (1 < < 11) 表示 1
#define N               11
// 最終取值保留小數(shù)點(diǎn)后 1 位
#define M               1

// 將非定點(diǎn)數(shù)轉(zhuǎn)成定點(diǎn)數(shù)
fp_t __to_FP(unsigned long long n)
{
  return n < < N;
}

// 獲取定點(diǎn)數(shù)的整數(shù)部分
unsigned long long fetch_INT(fp_t n)
{
  return n > > N;
}

// 去掉定點(diǎn)數(shù)的整數(shù)部分
unsigned long long __wipe_INT(fp_t n)
{
  return n & ((1 < < N) - 1);
}

// 獲取定點(diǎn)數(shù)的小數(shù)部分
unsigned long long fetch_FRAC(fp_t n)
{
  return fetch_INT(__wipe_INT(n) * pow(10, M));
}

// 下面是四則運(yùn)算
fp_t add0(fp_t a, unsigned long long b)
{
  return a + __to_FP(b);
}

fp_t add1(unsigned long long a, unsigned long long b)
{
  return add0(__to_FP(a), b);
}

fp_t sub0(fp_t a, unsigned long long b)
{
  return a - __to_FP(b);
}

fp_t sub1(unsigned long long a, unsigned long long b)
{
  return sub0(__to_FP(a), b);
}

fp_t mul0(fp_t a, unsigned long long b)
{
  return (a * __to_FP(b)) > > N;
}

fp_t mul1(unsigned long long a, unsigned long long b)
{
  return mul0(__to_FP(a), b);
}

fp_t div0(fp_t a, unsigned long long b)
{
  return (a < < N) / __to_FP(b);
}

fp_t div1(unsigned long long a, unsigned long long b)
{
  return div0(__to_FP(a), b);
}

// 四舍五入
fp_t fp_round(fp_t a)
{
  return a + __to_FP(1) * (5 * pow(10, -(M + 1)));
}

void main() {
    /* 3 + 5 = 8
   * 8 - 1 = 7
   * 7 * 2 = 14
   * 14 / 3 = 4.6
   */
    fp_t n = add1(3, 5);
    n = sub0(n, 1);
    n = mul0(n, 2);
    n = div0(n, 3);
    // 符合預(yù)期的輸出是 4.6
    printf("%llu.%llun", fetch_INT(n), fetch_FRAC(n));
    // 符合預(yù)期的輸出是 4.7
    printf("%llu.%llun", fetch_INT(fp_round(n)), fetch_FRAC(fp_round(n)));
}

4.4 內(nèi)核的工程實(shí)踐

內(nèi)核的工程實(shí)踐中，固定使用 11 位的定點(diǎn)數(shù)，且固定保留小數(shù)點(diǎn)后 2 位，4.3 節(jié)中的通用算法將進(jìn)一步得到簡(jiǎn)化：

// 相當(dāng)于 N，11 位二進(jìn)制定點(diǎn)數(shù)
#define FSHIFT    11    /* nr of bits of precision */

// 用 (1 < < N) 表示邏輯上的 1
// 相當(dāng)于 __to_FP(1)
#define FIXED_1    (1

要實(shí)現(xiàn)定點(diǎn)數(shù)小數(shù)部的四舍五入，原理是給定點(diǎn)數(shù)加上一個(gè)值，使其對(duì)應(yīng)小數(shù)位溢出。內(nèi)核中一個(gè)使用四舍五入的地方：

/* avenrun[*] 是定點(diǎn)數(shù)表示的當(dāng)前負(fù)載
 * offset 是要進(jìn)行四舍五入傳入的溢出值
 */
void get_avenrun(unsigned long *loads, unsigned long offset, int shift)
{
  loads[0] = (avenrun[0] + offset) < < shift;
  loads[1] = (avenrun[1] + offset) < < shift;
  loads[2] = (avenrun[2] + offset) < < shift;
}

static int loadavg_proc_show(struct seq_file *m, void *v)
{
    unsigned long avnrun[3];

    /* 傳入 FIXED_1/200，保留 2 位小數(shù)下的四舍五入。
     * 定點(diǎn)數(shù)下的 FIXED_1/200，表示邏輯上的 0.005
     */
    get_avenrun(avnrun, FIXED_1/200, 0);
 
    seq_printf(m, "%lu.%02lu %lu.%02lu %lu.%02lun",
               LOAD_INT(avnrun[0]), LOAD_FRAC(avnrun[0]),
               LOAD_INT(avnrun[1]), LOAD_FRAC(avnrun[1]),
               LOAD_INT(avnrun[2]), LOAD_FRAC(avnrun[2]));
    return 0;
}

5. 定點(diǎn)數(shù)實(shí)現(xiàn)的指數(shù)衰退

5.1 通用算法

有了前面詳實(shí)的鋪墊，這一節(jié)簡(jiǎn)單明了，將 2.3 節(jié)程序中的浮點(diǎn)型變量，換成定點(diǎn)數(shù)。

值得注意的點(diǎn)在于，2.3 節(jié) cal_load 中定義的衰退系數(shù) w = 0.6，要換算成定點(diǎn)數(shù)表示下的值（1229），具體轉(zhuǎn)換方法參考 4.3 節(jié)，不再贅述。

typedef unsigned long long fp_t;

#define N               11
#define M               1

fp_t __to_FP(unsigned long long n)
{
    return n < < N;
}

unsigned long long fetch_INT(fp_t n)
{
    return n > > N;
}

unsigned long long __wipe_INT(fp_t n)
{
    return n & ((1 < < N) - 1);
}

unsigned long long fetch_FRAC(fp_t n)
{
    return fetch_INT(__wipe_INT(n) * pow(10, M));
}

fp_t add(fp_t a, fp_t b)
{
    return a + b;
}

fp_t add0(fp_t a, unsigned long long b)
{
    return a + __to_FP(b);
}

fp_t add1(unsigned long long a, unsigned long long b)
{
    return add0(__to_FP(a), b);
}

fp_t mul(fp_t a, fp_t b)
{
    return (a * b) > > N;
}

fp_t mul0(fp_t a, unsigned long long b)
{
    return (a * __to_FP(b)) > > N;
}

fp_t mul1(unsigned long long a, unsigned long long b)
{
    return mul0(__to_FP(a), b);
}

fp_t fp_round(fp_t a)
{
    return a + __to_FP(1) * (5 * pow(10, -(M + 1)));
}

fp_t cal_load(fp_t last_load, unsigned long long curr)
{
    // 1229 是邏輯值 0.6 的定點(diǎn)數(shù)表示
    static fp_t w = 1229;
    return add(mul0(w, curr), mul(__to_FP(1) - w, last_load));
}

void main() {
    int i;
    fp_t load = 0;
    unsigned long long samplings[] = { 
        [0] = 9,
        [1] = 8,
        [2] = 7,
        [3] = 6,
        [4] = 5,
        [5] = 7,
        [6] = 6,
        [7] = 4,
        [8] = 2,
        [9] = 1,
    };  

    for (i = 0; i < sizeof(samplings) / sizeof(unsigned long long); ++i) {
        load = cal_load(load, samplings[i]);
        printf("%llu.%llu(%llu.%llu)n", fetch_INT(load), fetch_FRAC(load), fetch_INT(fp_round(load)), fetch_FRAC(fp_round(load)));
    }   
}

# 輸出，與浮點(diǎn)運(yùn)算一致，括號(hào)內(nèi)是四舍五入后的數(shù)值
5.4(5.4)
6.9(7.0)
6.9(7.0)
6.3(6.4)
5.5(5.6)
6.4(6.4)
6.1(6.2)
4.8(4.9)
3.1(3.1)
1.8(1.9)

5.2 內(nèi)核的工程實(shí)踐

內(nèi)核的相關(guān)約束更 specific，因而代碼反而更簡(jiǎn)單：

// 11 位定點(diǎn)數(shù)
#define FSHIFT    11    /* nr of bits of precision */

// 邏輯 1 在定點(diǎn)數(shù)下的表示
#define FIXED_1    (1

CALC_LOAD 中采用的是歷史值“乘以”EXP，而不是當(dāng)前值“乘以”EXP，實(shí)際上當(dāng)前值乘的是 (1 - EXP)，這個(gè)注意與我們前面代碼中對(duì)衰退系數(shù)的使用是反著來的。

5.3 內(nèi)核衰退系數(shù)的設(shè)計(jì)

注意看這三個(gè)宏內(nèi)核的代碼的注釋：

EXP_1，5 秒鐘采樣一次，1 分鐘周期的衰退系數(shù)。  
EXP_5，5 秒鐘采樣一次，5 分鐘周期的衰退系數(shù)。  
EXP_15，5 秒鐘采樣一次，15 分鐘周期的衰退系數(shù)。

對(duì)應(yīng)的邏輯值：

EXP_1 = 1884 / 2048 = 0.92  
EXP_5 = 2014 / 2048 = 0.98  
EXP_15 = 2037 / 2048 = 0.99

拿 EXP_1 來說，5 秒鐘一次采樣，1 分鐘內(nèi)采樣 12 次，根據(jù) 2.2 節(jié) 式(1)，當(dāng)前 1 分鐘采樣周期內(nèi)，最前面一次的采樣對(duì)當(dāng)前系統(tǒng)負(fù)載的影響權(quán)重為：

![image.png](/img/bVbLEs)

同理，EXP_5、EXP_15，在采樣周期內(nèi)最前面一次采樣的影響權(quán)重為：

![image.png](/img/bVbLEu)

內(nèi)核衰退系數(shù)的設(shè)計(jì)，使得每周期最前面的采樣值，對(duì)當(dāng)前整體評(píng)估的影響忽略不計(jì)。

6. 總結(jié)

本文分析了定點(diǎn)數(shù)和指數(shù)衰退算法的底層原理及方法論實(shí)踐，至于具體這些函數(shù)怎么被用來計(jì)算負(fù)載，調(diào)用關(guān)系拉一拉即可。

聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請(qǐng)聯(lián)系本站處理。舉報(bào)投訴

二進(jìn)制

二進(jìn)制

+關(guān)注

關(guān)注
2

文章
795

瀏覽量
41669
十進(jìn)制

十進(jìn)制

+關(guān)注

關(guān)注
0

文章
67

瀏覽量
13224
FPU

FPU

+關(guān)注

關(guān)注
0

文章
42

瀏覽量
21331
python

python

+關(guān)注

關(guān)注
56

文章
4797

瀏覽量
84742
LINUX內(nèi)核

LINUX內(nèi)核

+關(guān)注

關(guān)注
1

文章
316

瀏覽量
21654

評(píng)論

相關(guān)推薦

為行業(yè)找路徑，為商業(yè)筑壁壘，解碼容聯(lián)云的大模型“方法論”

為行業(yè)找路徑，為商業(yè)筑壁壘，解碼容聯(lián)云的大模型“方法論”

發(fā)表于 12-21 21:56 ?1297次閱讀

為行業(yè)找路徑，為商業(yè)筑壁壘，解碼容聯(lián)云的大模型“<b class='flag-5'>方法論</b>”

非常經(jīng)典的FPGA設(shè)計(jì)方法論

非常經(jīng)典的FPGA設(shè)計(jì)方法論

發(fā)表于 08-07 16:11

據(jù)說是經(jīng)典的FPGA設(shè)計(jì)方法論

據(jù)說是經(jīng)典的FPGA設(shè)計(jì)方法論

發(fā)表于 05-09 08:30

無線充電的基本原理是什么

一、無線充電基本原理無線充電的基本原理就是我們平時(shí)常用的開關(guān)電源原理，區(qū)別在于沒有磁介質(zhì)耦合，那么我們需要利用磁共振的方式提高耦合效率，具體方法是在發(fā)送端和接收端線圈串并聯(lián)電容，是發(fā)送線圈處理諧振

發(fā)表于 09-15 06:01

FPGA基本原理及設(shè)計(jì)思想和驗(yàn)證方法看完你就懂了

發(fā)表于 09-18 07:08

EXTI的使用方法及基本原理

介紹EXTI的使用方法及基本原理并且包括實(shí)驗(yàn)通過按鍵中斷控制led燈的亮滅

發(fā)表于 12-06 07:57

主要介紹SysTick系統(tǒng)定時(shí)器的基本原理

SysTick 淺談摘要：本章主要介紹SysTick系統(tǒng)定時(shí)器的基本原理，然后實(shí)現(xiàn)了毫秒定時(shí)器1. SysTick Timer （STK）系統(tǒng)定時(shí)器，是CM3 內(nèi)核的外設(shè)，內(nèi)嵌在 NVIC 中

發(fā)表于 02-18 07:14

淺談TD-SCDMA智能天線基本原理和測(cè)試方法

淺談TD-SCDMA智能天線基本原理和測(cè)試方法 1 引言作為第三代移動(dòng)通信系統(tǒng)標(biāo)準(zhǔn)之一的TD-SCDMA，采用了兩項(xiàng)最為關(guān)鍵的技術(shù)，即智能天線技術(shù)和聯(lián)合檢測(cè)技術(shù)。

發(fā)表于 02-02 11:22 ?1709次閱讀

淺談變頻器矢量變換控制的基本原理及應(yīng)用

淺談變頻器矢量變換控制的基本原理及應(yīng)用

發(fā)表于 01-21 11:54 ?8次下載

電磁鐵基本原理與應(yīng)用設(shè)計(jì)計(jì)算方法

電磁鐵基本原理與應(yīng)用設(shè)計(jì)計(jì)算方法

發(fā)表于 09-15 09:51 ?58次下載

華為數(shù)據(jù)治理和數(shù)字化轉(zhuǎn)型的實(shí)踐和方法論

125頁P(yáng)PT讀懂華為數(shù)據(jù)之道。下文從技術(shù)、流程、管理等多個(gè)維度系統(tǒng)地講解了華為數(shù)據(jù)治理和數(shù)字化轉(zhuǎn)型的實(shí)踐和方法論。 ? ? ? ? 原文標(biāo)題：華為內(nèi)部數(shù)據(jù)治理PPT，請(qǐng)收好！文章出處：【微信公眾號(hào)：智能制造】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。責(zé)任編輯:haq

發(fā)表于 04-08 11:36 ?5607次閱讀

Classic AUTOSAR的軟件架構(gòu)和方法論

隨著汽車電子軟件規(guī)模的不斷擴(kuò)大，Classic AUTOSAR（以下簡(jiǎn)稱CP）的軟件架構(gòu)和方法論已被越來越多的 OEM 和供應(yīng)商認(rèn)可。與此同時(shí)，CP 也面臨著巨大的挑戰(zhàn)，無法滿足汽車對(duì)高級(jí)自動(dòng)駕駛

發(fā)表于 05-24 17:12 ?3039次閱讀

愛立信的5G方法論

第29屆中國國際廣播電視信息網(wǎng)絡(luò)展覽會(huì)（CCBN）在北京首鋼園會(huì)議中心開啟，愛立信中國區(qū)技術(shù)部副總經(jīng)理張永濤、愛立信東北亞無線網(wǎng)絡(luò)產(chǎn)品部硬件總監(jiān)唐黎明，就“釋放5G潛能”、“打造綠色5G”，分享了愛立信的方法論和最新實(shí)踐。

發(fā)表于 04-23 14:27 ?2204次閱讀

LLC基本原理及設(shè)計(jì)方法

LLC基本原理及設(shè)計(jì)方法

發(fā)表于 06-25 10:05 ?7次下載

非常經(jīng)典的FPGA設(shè)計(jì)方法論.zip

非常經(jīng)典的FPGA設(shè)計(jì)方法論

發(fā)表于 12-30 09:22 ?3次下載

色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

搜索歷史

淺談內(nèi)核負(fù)載計(jì)算中的基本原理及方法論實(shí)踐