1. 前言

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

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

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

2. 指數(shù)衰退

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

2.1 是什么

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

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

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

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

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

2.2 數(shù)學推導

假設當前時刻采樣對整體評估的影響權(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 + ...

記上一次采樣點上系統(tǒng)的整體負載為 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 工程化

對于式(4)：

w：當前采樣值對整體負載評估的貢獻權(quán)重

Ln：當前采樣值

L'：上個采樣點上，系統(tǒng)的整體負載評估值

L：當前采樣點上，系統(tǒng)的整體負載評估值

寫成代碼：

/* curr 是當前采樣值
 * last_load 是上一時刻的系統(tǒng)負載
 */
double cal_load(double last_load,  unsigned long long curr)
{
    // 0.6 只是隨意取的一個權(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. 浮點數(shù)

3.1 浮點數(shù)的存儲

有關(guān)此話題更為嚴謹?shù)挠懻?，參?《IEEE Standard 754Floating Point Numbers》Steve Hollasch 一文。

對浮點數(shù)在計算機的存儲很懂的同學直接跳過本節(jié)。

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

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

單精度在計算機中如此表示：

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

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

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

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

因為這里本質(zhì)上是科學計數(shù)法，科學計數(shù)法要求底數(shù)的整數(shù)部分不能為 0：

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

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

為什么當階碼存儲的是 E 時，實際的運算使用的階碼卻是 E - 127？

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

0.001 = 1 x 10-3

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

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

換句話說，我們在這里加上 127 這個偏置，效果就是用 127 來表示邏輯上的 0，那么：

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

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

3.2 進制轉(zhuǎn)換

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

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

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

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

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

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

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

# output
# 1100

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

這里注意十進制的小數(shù)轉(zhuǎ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 的二進制表示
dec_frac2bin(0.3125)

# output
# 0.0101

計算過程：

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

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

如二進制的小數(shù) 0.0101，轉(zhuǎ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


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

# output
# 0.3125

3.3 實踐驗證理論

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

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

上面的代碼打印出 12.3125 在內(nèi)存中存儲的二進制 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ù)點在最終數(shù)值中的位置是跟著變化的，換句話說，你根本不知道它小數(shù)點后是精確到第幾位的。

3.5 精度的喪失

注意：本節(jié)的推導皆是通過工程手段進行的，沒有嚴謹?shù)臄?shù)學論證，因為我不會。

浮點的“點”雖然是在“浮”的，但限于計算機的離散性，無法無限精度的“浮”

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

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

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

從另外一個角度來驗證這個事情：

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

1.000001（十進制）：

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

1.0000001（十進制）：

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

1.00000001（十進制）：

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，二進制表示的前 23 位皆已丟失。
1.00000001，二進制表示的前 26 位皆已丟失（死的很徹底）。

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

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

    // 這里符合預期
    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

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

如有同學知道何因，敬請告知。

4. 定點數(shù)

4.1 基本概念

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

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

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

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

現(xiàn)在你在一臺不支持使用浮點類型的計算機上工作：

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

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

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

如果你要執(zhí)行的算法需要保留小數(shù)點后 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） <

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

定點數(shù)乘法運算的修正

假設計算 3.5 * 1.5，擺出算式：

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

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

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

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

定點數(shù)除法運算的修正

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

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

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

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

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

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

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

4.2 推廣及工程實踐

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

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

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

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

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

取出整數(shù)部分

這個比較簡單容易理解，3165 / 103 = 3。

取出小數(shù)部分

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

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

實現(xiàn)四舍五入

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

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

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

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

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

先看個表：

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

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

解得：

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

用簡單的代碼表示：

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

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

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

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

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

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

// 下面是四則運算
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);

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

4.3 二進制定點數(shù)

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

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

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

因為邏輯上的 1，在定點數(shù)表示法下為 1 << N，那么邏輯上的數(shù) a，其在定點數(shù)表示法中對應的數(shù) x，滿足如下方程：

解得：

x = a * 2N = (a   N)

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

分兩步走：1. 去掉整數(shù)部分，也即把整數(shù)部分掩掉：a & ((1 << N) - 1)，2. 把想要保留的小數(shù)部分“擠”到整數(shù)位，因為我們要取的是十進制下的 M 位，所以需要對去掉整數(shù)部分后的數(shù)，乘上 10M，再取整，即 fetch_INT(__wipe_INT(a) * 10M)

四舍五入：

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

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

解得：

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

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

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

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

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

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

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

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

// 下面是四則運算
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);
    // 符合預期的輸出是 4.6
    printf("%llu.%llun", fetch_INT(n), fetch_FRAC(n));
    // 符合預期的輸出是 4.7
    printf("%llu.%llun", fetch_INT(fp_round(n)), fetch_FRAC(fp_round(n)));
}

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

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

// 相當于 N，11 位二進制定點數(shù)
#define FSHIFT    11    /* nr of bits of precision */

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

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

/* avenrun[*] 是定點數(shù)表示的當前負載
 * offset 是要進行四舍五入傳入的溢出值
 */
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ù)下的四舍五入。
     * 定點數(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. 定點數(shù)實現(xiàn)的指數(shù)衰退

5.1 通用算法

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

值得注意的點在于，2.3 節(jié) cal_load 中定義的衰退系數(shù) w = 0.6，要換算成定點數(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 的定點數(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)));
    }   
}

# 輸出，與浮點運算一致，括號內(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)核的工程實踐

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

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

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

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

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

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

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

對應的邏輯值：

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)，當前 1 分鐘采樣周期內(nèi)，最前面一次的采樣對當前系統(tǒng)負載的影響權(quán)重為：

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

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

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

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

6. 總結(jié)

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

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

二進制

二進制

+關(guān)注

關(guān)注
2

文章
795

瀏覽量
41701
十進制

十進制

+關(guān)注

關(guān)注
0

文章
67

瀏覽量
13246
FPU

FPU

+關(guān)注

關(guān)注
0

文章
42

瀏覽量
21347
python

python

+關(guān)注

關(guān)注
56

文章
4801

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

LINUX內(nèi)核

+關(guān)注

關(guān)注
1

文章
316

瀏覽量
21688

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

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

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

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

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

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

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

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

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

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

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

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

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

EXTI的使用方法及基本原理

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

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

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

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

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

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

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

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

淺談變頻器矢量變換控制的基本原理及應用

淺談變頻器矢量變換控制的基本原理及應用

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

電磁鐵基本原理與應用設計計算方法

電磁鐵基本原理與應用設計計算方法

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

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

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

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

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

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

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

愛立信的5G方法論

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

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

LLC基本原理及設計方法

LLC基本原理及設計方法

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

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

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

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

搜索歷史

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