Hi,欢迎来到中国优发娱乐手机版高端品牌 - 华清远见嵌入式学院<北京总部官网>,专注嵌入式工程师培养13年!
  • 全国咨询热线:400-611-6270
  • 新浪微博
  • 微信
  • 北京
    校区
  • 上海
    校区
  • 深圳
    校区
  • 成都
    校区
  • 南京
    校区
  • 武汉
    校区
  • 西安
    校区
  • 广州
    校区
  • 沈阳
    校区
  • 济南
    校区
  • 重庆
    校区
  • 长沙
    校区
  • 研发
    中心
  • 当前位置: > 嵌入式学院 > 嵌入式学习 > 讲师博文 > linux内核-分配PID位图算法
    linux内核-分配PID位图算法
    时间:2017-09-12作者:华清远见
    很多博客上解释bitmap为位图,我认为这样的解释并不准确,我认为叫位映射比较好,因为它里面包含了映射关系,当然这里只是个人观点。早在x86的时代,就有寄存器存在位图,叫tss,可以自行百度,它的104偏移地址以上是位图,每个位对应一个IO端口,而提出这样的方案目的只有一个:高效。  bitmap其实是解决id的分配的,是一种高效率的分配。比如进程的pid的分配,还有文件描述符号的分配等。所以bitmap还是应用很广泛的,为了研究linux内核中的算法,我们提供了一种解决思路,帮助我们更好地理解内核,运用内核。话不多说,开始我们的主题。  在linux系统中运用的是内嵌汇编写的,它这样做是为了提高效率。我们的程序没那么复杂,关键是要理解它的思想。  这是一个简单的位图算法,先贴上代码,我们会对代码足以分析:  #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;  我们首先先理解一下位图分配的思想:这里有一个32位的二进制:1000 0110 , 它的思想是数二进制数字中置1的二进制的数目。比如: 1000 0110 为数字8,2, 1。(二进制0代表未分配,1代表已分配)。注意一下:这里并不是计算二进制的值,否则容易理解偏。    有了上面的理解,我们来分析一下怎么置位,我们看到上面用的是整形的数组。也就是每个元素是32位的,而且每个元素是连续的,正好满足上面二进制分配的规则。所以可以把这个数组想象成很长的二进制数,而里面为1的就是我们需要找到数字。  如何定义数组的下标和值,用简单的数学知识:  数组的下标为:index = num / 32;  数组的置位:value =1 <<( num % 32);(0 - 32 之间)  当然对于内核来说这样做浪费效率,所以为了提高效率,采取了移位操作,我们知道左移一个数字,相当于乘以这个数的2的幂次方,右移相反,所以就是int index = num >> SHIFT;大家能理解了。  我们重点理解:value =1 <<( num % 32);把这句话抽取出来,value = num % 32可以转化为(num & MASK); 这里可以做一个简单的计算,比如这个数字为34,十六进制0x22,二进制为:  0010 0010  & 0001 1111  0000 0010    答案显而易见为2,结果为这个数的第五位(由余数决定),当然条件是:,a,余数必须为2的n次方 b,n为掩码的宽度。那我们为什么这样设计。可以理解一下,移动34位,与移动2位的效果是一样的。  因为这是由于数组的长度是固定的,而且占据32位。由此证明上面的结论是正确的。  而后我们只要数移动2位后为就是要设置的比特位。这里只用一个简单的技巧,就是左移这个数就行了。    bitmap[index] |= bitValue;最后就是设置位,注意这里是或等于不是等于。设置好位后就能查询该位是否被使用。  下面是提供的api函数:  void set_bit(int num); 根据数字设置相应的位  void clear_bit(int num); 清除相应的位  int text_set_bit(int num); 测试相应的位  你可以把上面的程序拷贝一下进行测试,还可以进行更高级的封装,为应用程序调用。

    发表评论
    全国咨询电话:400-611-6270,双休日及节假日请致电值班手机:15010390966 在线咨询: 曹老师QQ(3337544669), 徐老师QQ(1462495461), 刘老师 QQ(3108687497) 企业培训洽谈专线:010-82600901,院校合作洽谈专线:010-82600350,在线咨询:QQ(248856300) Copyright 2004-2017 华清远见教育集团 版权所有 ,沪ICP备10038863号,京公海网安备110108001117号

    优发娱乐手机版

    百度360搜索搜狗搜索

    优发娱乐手机版

    百度360搜索搜狗搜索