linux 进程的pid分配策略——pid位图算法

    在研究进程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来表示。

typedef struct pidmap
{
    unsigned int nr_free;
    char page[4096];
} 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列进行对比的话，这个操作更能够减少加法操作的次数。

这些内容在程序当中对应的是这些语句：

unsigned long mask = 1UL << (offset & (sizeof(unsigned long) * BITS_PER_BYTE - 1));
unsigned long *p = ((unsigned long*)addr) + (offset >> (sizeof(unsigned long) + 1));

其实上面的话，如果在32位机子上运行的话，可以进行如下简化：

unsigned long mask = 1UL << (offset & 31);
unsigned long *p = ((unsigned long*)addr) + (offset >> 5);

说明：

offset对应于一个要处理的pid编号。

offset & 31只保留后5位的值，然后1左移这个值的大小位，这样的话，我们就在某一行中找到了具体的对应的那一位了。

offset右移５位，表示将offset的后5位屏蔽掉了。这样的话，我们就可以找到对应的具体的某一行地址了。

下面是具体的代码：

#include <stdio.h>

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

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

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

typedef struct pidmap
{
    unsigned int nr_free;
    char page[4096];
} pidmap_t;

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

static int last_pid = -1;

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

    *p = old | mask;

    return (old & mask) != 0;
}

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

static int find_next_zero_bit(void *addr, int size, int offset)
{
    unsigned long *p;
    unsigned long mask;

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

        if ((~(*p) & mask))
        {
            break;
        }
        ++offset;
    }

    return offset;
}

static int alloc_pidmap()
{
    int pid = last_pid + 1;
    int offset = pid & BITS_PER_PAGE_MASK;//把offset的最高为变为0，其他的不变

    if (!pidmap.nr_free)
    {
        return -1;
    }

    offset = find_next_zero_bit(&pidmap.page, BITS_PER_PAGE, offset);
    if (BITS_PER_PAGE != offset && !test_and_set_bit(offset, &pidmap.page))
    {
        --pidmap.nr_free;
        last_pid = offset;
        return offset;
    }

    return -1;
}

static void free_pidmap(int pid)
{
    int offset = pid & BITS_PER_PAGE_MASK;

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

int main()
{
    int i;
    for (i = 0; i < PID_MAX_DEFAULT; ++i) {
        printf("pid = %d\n", alloc_pidmap());
    }
    return 0;
}

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