1、C语言嵌入结构

• 实现继承（典型的Kobject）；

• 封装：通过结构体对对一类信息包装，便于后续扩展、升级，即使信息只有一个简单数据，如kref；对结构体成员的访问要通过函数来实现成员封装，使得结构体面向功能服务，易于扩展

• 抽象：通过在结构体内嵌入特殊用途的结构体（可包含相关具体函数）实现抽象设计，可以将对象看作某类对象，看作实现某种服务抽象，类似C++的virtual。如cpu均衡部分，就绪队列中，嵌入与均衡相关的结构及处理，上层在得到均衡通知时，任务下放sched_class具体处理。另一个例子是调度，他处理的是可调度实体（sched_entity)，可以是进程、也可以是进程组（不同用户）。

2、数据结构：

• 散列表在linux上的实现：定义散列区间（一般不能太大），确定数组，在每一个数组项上，通过双链表方式存储散列项相同的数据项，而散列函数的理想是等概率分布。

• 红黑树：通过深度优先搜索（DFS）生成有序队列，如调度的等待时间，通过深度优先，生成按照等待时间排序的队列，在调度时，只调度最左侧地下的一个就ok。（时间复杂度为对数）

• 双向循环链表：

• 位图辅助索引：

3、副本与写时复制技术：

• 通过复制副本获取父对象的所有资源，并使得修改副本是一个独立对象，从而不影响父对象。（进程结构：task_struct, 命名空间nsproxy）；

• fork复制了task_struct，实际上就有了2个完全相同的进程，并且都运行到了同一个地址上。在linux上进程与线程的不同仅体现在共享资源的不同上，每个线程都有唯一的task_struct，fork与clone只有细微的差别。

4、结构相关：

• 宏定义：通过宏定义进行与结构相关操作，隐藏具体细节，便于移植；如结构体中，变量相对位置不能假定，应采用宏定义的方式计算得到（container_of)，如一个数据不同位代表不