當(dāng)前位置：首頁 > 嵌入式培訓(xùn) > 嵌入式學(xué)習(xí) > 講師博文 > linux內(nèi)核-分配PID位圖算法
linux內(nèi)核-分配PID位圖算法
時(shí)間：2018-09-29 來源：未知
很多博客上解釋bitmap為位圖，我認(rèn)為這樣的解釋并不準(zhǔn)確，我認(rèn)為叫位映射比較好，因?yàn)樗锩姘擞成潢P(guān)系，當(dāng)然這里只是個(gè)人觀點(diǎn)。早在x86的時(shí)代，就有寄存器存在位圖，叫tss,可以自行百度，它的104偏移地址以上是位圖，每個(gè)位對應(yīng)一個(gè)IO端口，而提出這樣的方案目的只有一個(gè)：高效。
bitmap其實(shí)是解決id的分配的，是一種高效率的分配。比如進(jìn)程的pid的分配，還有文件描述符號的分配等。所以bitmap還是應(yīng)用很廣泛的，為了研究linux內(nèi)核中的算法，我們提供了一種解決思路，幫助我們更好地理解內(nèi)核，運(yùn)用內(nèi)核。話不多說，開始我們的主題。
在linux系統(tǒng)中運(yùn)用的是內(nèi)嵌匯編寫的，它這樣做是為了提高效率。我們的程序沒那么復(fù)雜，關(guān)鍵是要理解它的思想。
這是一個(gè)簡單的位圖算法，先貼上代碼，我們會對代碼足以分析：
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
int bitmap[10] = {0}; //0 - 320
#define SHIFT 5
#define MASK 0x1F
void set_bit(int num){
int index = num >> SHIFT;
int bitValue = 1 << (num & MASK);
bitmap[index] |= bitValue;
}
int text_set_bit(int num){
int index = num >> SHIFT;
int bitValue = 1 << (num & MASK);
return bitmap[index] & bitValue;
}
void clear_bit(int num){
int index = num >> SHIFT;
int bitValue = 1 << (num & MASK);
bitmap[index] &= (~bitValue);
}
int main(int argc, const char *argv[])
{
int num = 50;
set_bit(num);
printf("set_bit sucess\n");
if(text_set_bit(num)){
printf("match sucess! \n");
}
else{
printf("match failed! \n");
}
clear_bit(num);
printf("clear_bit sucess\n");
if(text_set_bit(num)){
printf("match sucess! \n");
}
else{
printf("match failed! \n");
}
return 0;
}
我們首先先理解一下位圖分配的思想：這里有一個(gè)32位的二進(jìn)制：1000 0110 , 它的思想是數(shù)二進(jìn)制數(shù)字中置1的二進(jìn)制的數(shù)目。比如： 1000 0110 為數(shù)字8，2， 1。（二進(jìn)制0代表未分配，1代表已分配）。注意一下：這里并不是計(jì)算二進(jìn)制的值，否則容易理解偏。
有了上面的理解，我們來分析一下怎么置位，我們看到上面用的是整形的數(shù)組。也就是每個(gè)元素是32位的，而且每個(gè)元素是連續(xù)的，正好滿足上面二進(jìn)制分配的規(guī)則。所以可以把這個(gè)數(shù)組想象成很長的二進(jìn)制數(shù)，而里面為1的就是我們需要找到數(shù)字。
如何定義數(shù)組的下標(biāo)和值，用簡單的數(shù)學(xué)知識：
數(shù)組的下標(biāo)為：index = num / 32;
數(shù)組的置位：value =1 <<( num % 32);（0 - 32 之間）
當(dāng)然對于內(nèi)核來說這樣做浪費(fèi)效率，所以為了提高效率，采取了移位操作，我們知道左移一個(gè)數(shù)字，相當(dāng)于乘以這個(gè)數(shù)的2的冪次方，右移相反，所以就是int index = num >> SHIFT;大家能理解了。
我們重點(diǎn)理解：value =1 <<( num % 32);把這句話抽取出來，value = num % 32可以轉(zhuǎn)化為(num & MASK); 這里可以做一個(gè)簡單的計(jì)算，比如這個(gè)數(shù)字為34，十六進(jìn)制0x22,二進(jìn)制為：
0010 0010
& 0001 1111
0000 0010
答案顯而易見為2，結(jié)果為這個(gè)數(shù)的第五位(由余數(shù)決定)，當(dāng)然條件是：，a，余數(shù)必須為2的n次方 b，n為掩碼的寬度。那我們?yōu)槭裁催@樣設(shè)計(jì)�？梢岳斫庖幌�，移動34位，與移動2位的效果是一樣的。
因?yàn)檫@是由于數(shù)組的長度是固定的，而且占據(jù)32位。由此證明上面的結(jié)論是正確的。
而后我們只要數(shù)移動2位后為就是要設(shè)置的比特位。這里只用一個(gè)簡單的技巧，就是左移這個(gè)數(shù)就行了。
bitmap[index] |= bitValue;后就是設(shè)置位，注意這里是或等于不是等于。設(shè)置好位后就能查詢該位是否被使用。
下面是提供的api函數(shù)：
void set_bit(int num)； 根據(jù)數(shù)字設(shè)置相應(yīng)的位
void clear_bit(int num)； 清除相應(yīng)的位
int text_set_bit(int num)； 測試相應(yīng)的位
你可以把上面的程序拷貝一下進(jìn)行測試，還可以進(jìn)行更高級的封裝，為應(yīng)用程序調(diào)用。
