红黑树被广泛应用在内核的内存管理和进程调度中，用户将排序的元素组织到树中，在速度和实现复杂度之间得到了很好的平衡。 红黑树是具有以下特征的二叉树： 节点或红或黑； 根
红黑树被广泛应用在内核的内存管理和进程调度中，用户将排序的元素组织到树中，在速度和实现复杂度之间得到了很好的平衡。
红黑树是具有以下特征的二叉树：
- 节点或红或黑；
- 根节点是黑色的；
- 所有叶子节点（NULL）是黑色的；
- 如果节点是红色的，那么两个子节点是黑色的；
- 从任意节点到对应每个叶子的所有路径都包含相同数量的黑色节点；
所有重要的操作（插入、删除、搜索）都可以在对数时间内完成。
malloc、kmalloc、vmalloc
kmalloc和vmalloc是设备驱动程序或者内核模块中动态开辟内存，malloc分配的是用户的内存，释放内存用的是kfree,vfree，或free_pages。kmalloc保证分配的内存在物理上是连续的，这对于要进行DMA的设备十分重要，vmalloc保证的是在虚拟地址空间上的连续，malloc不保证任何东西。kmalloc函数返回的是虚拟地址(线性地址)。kmalloc特殊之处在于它分配的内存是物理上连续的。而用vmalloc分配的内存只是线性地址连续，物理地址不一定连续,不能直接用于DMA.kmalloc能分配的大小有限，vmalloc和malloc能分配的大小相对较大内存只有在要被DMA访问的时候才需要物理上连续。vmalloc比kmalloc要慢。
【文章原创作者：
香港显卡服务器 http://www.558idc.com/hkgpu.html 网络转载请说明出处】
