Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1478126
  • 博文数量: 217
  • 博客积分: 4362
  • 博客等级: 上校
  • 技术积分: 4179
  • 用 户 组: 普通用户
  • 注册时间: 2009-09-20 09:31
文章分类

全部博文(217)

文章存档

2017年(1)

2015年(2)

2014年(2)

2013年(6)

2012年(42)

2011年(119)

2010年(28)

2009年(17)

分类: LINUX

2011-09-14 22:14:34

    在研究进程fork()的时候,这个调用了do_fork(),其中do_fork()又涉及到进程的pid分配,这个东西的源代码有许多个版本,而且各自都不是一样的。昨天晚上研究了一晚上,今天从下午研究到现在,总算把内核中pid位图算法有一个整体的把握了。明天早上继续完成这篇博客,现在小小的庆祝一下,明天完成。
    首先我们先看一个程序,这个程序是我从网上找的,这个程序的主要部分也是内核中的代码,下面我们就来分析一下这个程序。
注:原程序有许多bug虫,下面的程序是我修改正确之后的程序,也算是有一点自己的共享吧,另外,原程序没有解释,我的解释估计还算详细吧,不废话了,我们一起来分析一下程序吧。
小知识:进程当中的pid号的分配是从0——32767之间的,其中0—299的进程号是分配给demo(守护进程)的。剩下的pid号是分配给普通进程的。

    要分析这个程序首先我们得明白其中结构体的含义。
struct pidmap这个结构体主要是为了标志pid是不是已经分配出去了。在page这个变量当中表示着,每一个char类型占一个字节—8位,也就是说,为了表示32768个进程号是不是分配出去没有,我们要占用32768/8=4096个字节,这个也是为什么page要申请占用4096个大小的原因。另外,为了表示现在还有多少个pid号没有分配出去,我们还可以使用的话,使用nr_free来表示。
  1. typedef struct pidmap
  2. {
  3.     unsigned int nr_free;
  4.     char page[4096];
  5. } pidmap_t;
我们继续来分析有关的函数。
这里涉及到的主要有5个函数。

static int test_and_set_bit(int offset, void *addr);
这个函数的作用主要是将offset在pidmap变量当中相应的位置为1,也就是申请到一个pid号之后,修改位标志。其中addr是pidmap.page变量的地址。

static void clear_bit(int offset, void *addr);
这个函数的作用主要是将offset在pidmap变量当中相应的位置为0,也就是释放一个pid号之后,修改位标志。其中addr是pidmap.page变量的地址。

static int find_next_zero_bit(void *addr, int size, int offset);
从offset开始,找下一个是0(也就是可以分配)的pid号。其中addr是pidmap.page变量的地址,size是一个页的大小。

static int alloc_pidmap();
分配一个pid号。

static void free_pidmap(int pid);
回收一个pid号。

这里还有一个变量:last_pid,这个变量表示的是上一次飞配出去的pid编号。

注意了,关键的地方开始了。
这个算法的思想主要是如何根据一个pid号找到它在pidmap.page变量当中找到相应位的地址。这个可能也是这个算法当中的主要的一个小技巧吧。
好了,如果让我们自己来设计这样的算法——根据pid号找到它在pidmap.page变量当中找到相应位的地址,我们会怎么来写呢?
我首先会给pid除以8,然后取整,即int a=(pid/8),将得到的a的值作为pidmap.page的下标,也就是pidmap.page[a],然后用int b=(pid%8)得到对应位的0—7之间的编号,这样的话,就唯一确定了一个pid编号在pidmap.page中的具体位置。

这个可能是大多数人的想法,但是内核当中是通过移位操作来实现的。我们可以抽象出一张表,这个表有32列,1024行,这个刚好是一个页的大小。这个时候,我们可以通过pid的后5位值(变化范围在0—31之间)来确定在某一行的具体的列。通过pid的高27位(pid本身是32位的)来表示在具体的某一行。所以我们可以通过移位操作来实现。
这里为什么每一行要设置成32列,而不是8列,或者是64列呢?我是这么考虑的,这个算法是在32位机子上运行的,如果是32位的话,刚好是一个unsigned int所占的空间的大小,这样对它的地址的加一操作会跳跃4个字节,和每行8列进行对比的话,这个操作更能够减少加法操作的次数。
这些内容在程序当中对应的是这些语句:
  1. unsigned long mask = 1UL << (offset & (sizeof(unsigned long) * BITS_PER_BYTE - 1));
  2. unsigned long *p = ((unsigned long*)addr) + (offset >> (sizeof(unsigned long) + 1));
其实上面的话,如果在32位机子上运行的话,可以进行如下简化:
  1. unsigned long mask = 1UL << (offset & 31);
  2. unsigned long *p = ((unsigned long*)addr) + (offset >> 5);
说明:
offset对应于一个要处理的pid编号。
offset & 31只保留后5位的值,然后1左移这个值的大小位,这样的话,我们就在某一行中找到了具体的对应的那一位了。
offset右移5位,表示将offset的后5位屏蔽掉了。这样的话,我们就可以找到对应的具体的某一行地址了。
下面是具体的代码:

  1. #include <stdio.h>

  2. /* max pid, equal to 2^15=32768 */
  3. #define PID_MAX_DEFAULT 0x8000

  4. /* page size = 2^12 = 4K */
  5. #define PAGE_SHIFT 12
  6. #define PAGE_SIZE (1UL << PAGE_SHIFT)

  7. #define BITS_PER_BYTE 8
  8. //4k*8 32768
  9. #define BITS_PER_PAGE (PAGE_SIZE * BITS_PER_BYTE)
  10. //7fff
  11. //0111 1111 1111 1111
  12. #define BITS_PER_PAGE_MASK (BITS_PER_PAGE - 1)

  13. typedef struct pidmap
  14. {
  15.     unsigned int nr_free;
  16.     char page[4096];
  17. } pidmap_t;

  18. static pidmap_t pidmap = { PID_MAX_DEFAULT, {0}};

  19. static int last_pid = -1;

  20. static int test_and_set_bit(int offset, void *addr)
  21. {
  22.     unsigned long mask = 1UL << (offset & (sizeof(unsigned long) * BITS_PER_BYTE - 1));
  23.     unsigned long *p = ((unsigned long*)addr) + (offset >> (sizeof(unsigned long) + 1));
  24.     unsigned long old = *p;

  25.     *p = old | mask;

  26.     return (old & mask) != 0;
  27. }

  28. static void clear_bit(int offset, void *addr)
  29. {
  30.     unsigned long mask = 1UL << (offset & (sizeof(unsigned long) * BITS_PER_BYTE - 1));//取offset的后31位数据,并左移
  31.     unsigned long *p = ((unsigned long*)addr) + (offset >> (sizeof(unsigned long) + 1));//+优先级高于>>
  32.     unsigned long old = *p;
  33.     *p = old & ~mask;
  34. }

  35. static int find_next_zero_bit(void *addr, int size, int offset)
  36. {
  37.     unsigned long *p;
  38.     unsigned long mask;

  39.     while (offset < size)
  40.     {
  41.         p = ((unsigned long*)addr) + (offset >> (sizeof(unsigned long) + 1));
  42.         mask = 1UL << (offset & (sizeof(unsigned long) * BITS_PER_BYTE - 1));

  43.         if ((~(*p) & mask))
  44.         {
  45.             break;
  46.         }
  47.         ++offset;
  48.     }

  49.     return offset;
  50. }

  51. static int alloc_pidmap()
  52. {
  53.     int pid = last_pid + 1;
  54.     int offset = pid & BITS_PER_PAGE_MASK;//把offset的最高为变为0,其他的不变
  55.     
  56.     if (!pidmap.nr_free)
  57.     {
  58.         return -1;
  59.     }

  60.     offset = find_next_zero_bit(&pidmap.page, BITS_PER_PAGE, offset);
  61.     if (BITS_PER_PAGE != offset && !test_and_set_bit(offset, &pidmap.page))
  62.     {
  63.         --pidmap.nr_free;
  64.         last_pid = offset;
  65.         return offset;
  66.     }

  67.     return -1;
  68. }

  69. static void free_pidmap(int pid)
  70. {
  71.     int offset = pid & BITS_PER_PAGE_MASK;

  72.     pidmap.nr_free++;
  73.     clear_bit(offset, &pidmap.page);
  74. }

  75. int main()
  76. {
  77.     int i;
  78.     for (i = 0; i < PID_MAX_DEFAULT; ++i) {
  79.         printf("pid = %d\n", alloc_pidmap());
  80.     }
  81.     return 0;
  82. }

    小结:面试的时候爱问海量数据的操作,其实许多海量数据都用到了这个位操作对应的算法,所以知道这个pid位图算法,不失为一件好事。


阅读(8233) | 评论(5) | 转发(3) |
给主人留下些什么吧!~~

8191710112013-06-26 15:26:32

http://blog.csdn.net/u011153070/article/details/9165737
我对两个bug进行了修改,代码也有所改动

8191710112013-06-06 16:29:59

alloc_pidmap有一处BUG
出现情景:
1.首先申请完所有pid
2.释放第15个pid
3.申请pid(会申请到第二步释放的pid)
4.再释放第10个pid
5.当再次申请pid时,虽然尚有一个空位,但原有代码申请不到这个空位。

建议修改:
当find_next_zero_bit返回BITS_PER_PAGE时,应判断nr_free,此时如果nr_free不为0,应当将offset手动设为0,从page起始处查找(空位位于last_id之前)

8191710112013-06-06 16:22:18

建议使用
unsigned long *p = ((unsigned long*)addr) + (offset >> __builtin_ctz(~(sizeof(unsigned long) * BITS_PER_BYTE - 1)));
代替原有代码

8191710112013-06-05 17:36:46

楼主您好,请教一个问题,在LP64的操作系统中
unsigned long *p = ((unsigned long*)addr) + (offset >> (sizeof(unsigned long) + 1));
中的offset会右移9位,但正确的应该是右移6位吧