那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

linux内核V2.6.11学习笔记(1)--pid位图

开始系统的学习linux内核了,手头的参考书是<<深入理解linux内核>>第三版,里面是基于2.6.11版来讲解的,所以我这里的笔记也是基于这个版本.我的目的是将该书中我觉得讲的不太详细或者可以展开讨论理解的地方写出来供别人参考.计划三个月内精读完该书,争取每周更新约三次笔记.

其它的参考资料还有:
<<深入理解计算机系统>>
<<linux内核情景分析>>上册
<<Linux内核设计与实现>>
<<Linux内核完全剖析>>
<<UNIX操作系统设计>>
这几本书都是看到相关部分时拿出来的参考资料,阅读还是以<<深入理解linux内核>>为主展开.

==================分割线=====================
熟悉unix的人都知道,进程号也就是pid实际上是整型的数据,每次创建一个新的进程就返回一个id号,这个id号一直递增,直到最大的时候开始"回绕",也就是从0开始寻找当前最小的可用的pid.

linux内核中,采用位图来实现pid的分配与释放.简单的说,就是分配一个与系统最大pid数目相同大小的位图,每次分配了一个pid,就将位图中的相应位置置1;释放则置0;回绕的时候则从0开始继续前面的查找,如果遍历了整个位图都找不到,那么返回-1.

我将内核中相关部分的代码提取出来写了一个简单的demo:
#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
#define BITS_PER_PAGE        (PAGE_SIZE * BITS_PER_BYTE)
#define BITS_PER_PAGE_MASK    (BITS_PER_PAGE - 1)

typedef 
struct pidmap 
{
    unsigned 
int nr_free;
    
char page[PID_MAX_DEFAULT];
} 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 *= ((unsigned long*)addr) + (offset >> (sizeof(unsigned long+ 1));
    unsigned 
long old = *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));    
    unsigned 
long *= ((unsigned long*)addr) + (offset >> (sizeof(unsigned long+ 1));
    unsigned 
long old = *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;

    
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 + 100++i)
    {
        printf(
"pid = %d\n", alloc_pidmap());
        
if (!(i % 100))
        {
            // 到整百时释放一次pid,看回绕的时候是不是都是使用整百的pid
            free_pidmap(i);
        }
    }

    
return 0;
}

说明几点:
1) 内核中对应的代码在pid.c和bitops.h文件中.
2) 这里的几个位操作函数实现linux内核中基于不同的CPU架构分别都做了优化,有的用到了汇编,我这里使用纯C语言完成这几个函数.但是我想,不论是C还是汇编,这里隐含的算法思想都是一样的(见下面提到的第四点),在算法确定了之后,再针对可以优化的地方去做优化.
3) 代码里面还做了一些简化,内核中pidmap对象可能是数组,但是这里的实现只有一个pidmap对象.
4) "位图"是非常常见的数据结构,一般适用于如下的场景:
首先,需要分配/释放的数据是整型相关的;其次,它们是连续的,从0开始的;最后,它们的状态只有两种:分配或者空闲.回头看看pid的这个场景,满足了使用位图的情况.在其它的一些书籍中,比如<<编程珠玑>>,也提到了位图算法,它那里的场景与这里类似.
5) 位操作我还不是很熟悉,写这几个位操作算法费了不少功夫.


posted on 2009-04-10 12:57 那谁 阅读(4014) 评论(7)  编辑 收藏 引用 所属分类: Linux/Unixlinux kernel

评论

# re: linux内核V2.6.11学习笔记(一)--pid位图  回复  更多评论   


传说中的小C
2009-04-10 15:08 | Kevin Lynx

# re: linux内核V2.6.11学习笔记(一)--pid位图[未登录]  回复  更多评论   

@Kevin Lynx
????
2009-04-10 16:38 | 那谁

# re: linux内核V2.6.11学习笔记(一)--pid位图  回复  更多评论   

《深入理解linux内核》

看了觉得翻译得不好

看1.0内核源代码还可以

"貌似几个月前你就发布过这个随笔"

对不

因为我觉得我以前也像这样发表过评论你的这个随笔
2009-04-11 10:28 | 小名阿铁

# re: linux内核V2.6.11学习笔记(一)--pid位图  回复  更多评论   

@小名阿铁
我看的英文版电子书,中文版纸书在看不懂的情况下拿来参考(目前还没有参考到).这个是我最新发布的随笔,以前没发布过.
2009-04-11 10:54 | 那谁

# re: linux内核V2.6.11学习笔记(一)--pid位图  回复  更多评论   

回帖支持你
2009-04-11 11:30 | santhtony

# re: linux内核V2.6.11学习笔记(一)--pid位图  回复  更多评论   

那个++j应该是++i吧?
2009-04-18 19:20 | 杨景

# re: linux内核V2.6.11学习笔记(1)--pid位图[未登录]  回复  更多评论   

很感谢你的程序,对我帮助很大,我把你的程序研究了1天,其中有一个很小的bug
static pidmap_t pidmap = { PID_MAX_DEFAULT, {'0'} };
不是这样对char数组进行初始化的,应该是这样的
static pidmap_t pidmap = { PID_MAX_DEFAULT, {0}};

这个问题花费了我许多时间,才找出来的
2011-09-15 08:36 | sunny

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理