操作系统中的通用双向循环链表

《操作系统中的通用双向循环链表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、操作系统中的通用双向循环链表马洪兵清华大学电子工程系1.引言操作系统内核维护了大量的核心数据，为了方便、高效地管理这些数据，必须以某种适当的方式将它们组织起来。考虑到操作系统内核中很多数据需要动态调整，所以现代操作系统广泛地使用双向循环链表。例如，将处于活动状态的进程控制块组织成双向循环链表，将进程的线程控制块组织成双向循环链表等等。在数据结构课或者C/C++语言课上，我们学习了将某个结构体组织成双向循环链表的方法。一般是在结构体中定义两个指向该结构体的指针变量，例如：typedefstruct_FOO{…//其他字段struct_FOO*Prev;stru

2、ct_FOO*Next;…//其他字段}FOO,*PFOO;然后再编写一组用于管理该链表的函数，实现插入、删除等操作。然而，在操作系统内核中，需要组织成双向循环链表的结构体实在太多，如果每一个结构体都像上面定义，则每种结构体都需要编写一组用于管理该链表的函数，这样的设计方法显然存在问题。为此，操作系统的开发者需要一种新的设计方法，使用统一的方式定义需要使用双向循环链表组织的结构体，并且定义一组统一的函数实现插入、删除等操作。这里的基本思路是将指针Prev和Next从具体的结构体中提取出来，构成一种通用的双向循环链表结构体。与此同时，定义一组通用的函数该管理该

3、链表，实现插入、删除等操作。实现如果需要构造某种结构体类型的特定双向循环链表，则在其结构体（称为宿主结构体）中嵌入通用的双向循环链表结构体作为其成员，通过这个成员将这类结构体连接起来，形成所需双向循环链表，并通过通用链表函数对其进行操作。这种设计方法的优点是只需编写通用双向循环链表结构体和链表操作函数，即可构造和操作不同结构体组成的链表，而无需为每类结构体的每种链表编写专用函数，实现了代码的重用。Linux和Windows操作系统内核都采用了这样的设计方法。2.Linux的通用双向循环链表在Linux源代码树的include/linux/list.h文件中，

4、定义一个类型为list_head类型的结构体：structlist_head{structlist_head*next,*prev;};在具体使用时，通常使用带头结点的双向循环链表形式。当用list_head类型定义一个独立的变量时，其为头结点。头结点是一个占位结点，其直接后继是双向循环链表中的第一个有效结点。当list_head类型为某个结构体的一个成员时，其为普通结点。Linux提供了一组函数(或宏)可以对此通用双向循环链表进行操作，包括：INIT_LIST_HEAD表头初始化list_empty判段链表是否为空list_is_last判段是否表尾lis

5、t_add在表头插入新结点list_add_tail在表尾插入新结点list_del删除指定的结点list_replace替换指定的结点list_move把指定的结点移到表首list_move_tail把指定的结点移到表尾list_splice合并链表list_for_each遍历结点以上函数(或宏)的定义都在Linux源代码树的include/linux/list.h文件中。以list_head成员作为连接件，可以把宿主结构体链接起来，形成双向循环链表。例如：typedefstructfoo{…//其他字段structlist_headlist;…//其他

6、字段};然而，如何通过list_head成员访问到宿主结构体呢？毕竟list_head不过是一个个连接件，而我们需要的是一个特定的结构体类型组成的链表。为此，Linux定义了一个宏list_entry，可以根据宿主结构体的类型和list_head成员变量的地址获取宿主结构体本身的地址。list_entry的定义如下：#definelist_entry(ptr,type,member)container_of(ptr,type,member)而container_of的定义如下：#definecontainer_of(ptr,type,member)({c

7、onsttypeof(((type*)0)->member)*__mptr=(ptr);(type*)((char*)__mptr-offsetof(type,member));})offsetof的定义如下：#defineoffsetof(TYPE,MEMBER)((size_t)&((TYPE*)0)->MEMBER)扩展替换即为：#definelist_entry(ptr,type,member)((type*)((char*)(ptr)-(unsignedlong)(&((type*)0)->member)))(type*)为指向type类型的结

8、构体的指针，(type*)0使结构体的起始地址为0。