在linux *** 作系统内核实现里经常使用的红黑树

在linux *** 作系统内核实现里经常使用的红黑树如下：

二叉树，按中序遍历后为一递增数组，自平衡意味着树的高度有一个上限，对于红黑树，其为2log(n+1)，所以时间复杂度为最差为Olog(n)。

赋予二叉搜索树自平衡特性的方法有多种，红黑树通过一下4条约束实现自平衡:

Every node is either red or black.

All NIL nodes (figure 1) are considered black.

A red node does not have a red child.

Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.

其中根节点为黑色。

红黑树的搜索与二叉搜索树无异，但是插入和删除可能会违背上述四条原则。需要用到左旋右旋 *** 作。左旋右旋上图，可以看到左旋右旋本身不改变二叉搜索树的特性，旋转后必要时改变节点的颜色可消除插入或者删除带来的红冲突和黑冲突，有时红黑树的重新平衡需要迭代进行。

红黑树比较适合的应用场景:

需要动态插入、删除、查找的场景，包括但不限于：

某些数据库的增删改查，比如select * from xxx where 这类条件检索。

linux内核中进程通过红黑树组织管理，便于快速插入、删除、查找进程的task_struct。

linux内存中内存的管理：分配和回收。用红黑树组织已经分配的内存块，当应用程序调用free释放内存的时候，可以根据内存地址在红黑树中快速找到目标内存块。

hashmap中(key,value)增、删、改查的实现；java 8就采用了RBTree替代链表。

Ext3文件系统，通过红黑树组织目录项。

红黑树是平衡二叉树的一种，它有很好的性质，树中的结点都是有序的，而且因为它本身就是平衡的，所以查找也不会出现非常恶劣的情况，基于二叉树的 *** 作的时间复杂度是O(log(N))。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的....

这个问题很大。。。。我尽自己所能给你解释一下吧，如果你不能完全看懂，以后可以回头再翻翻来看。关于虚拟内存的事情，大概是这样的：

首先你要明确什么是虚拟内存。虚拟内存实际上是 *** 作系统对于内存管理的一种方式，比如说，对每个程序而言，它的内存编址都从0x00到0xff，但是实际上，这些内存对应的物理地址，应用程序本身是无法知道的，在这里就可以理解成 *** 作系统对内存管理的一层抽象。

比如，可能进程init的虚拟地址0x00对应了物理地址的0x10，而kthreadd的虚拟地址0x00对应物理地址0x20，etc.

而且虚拟内存也是一种有效的进程间隔离的方式，极大的提升了进程的安全性和 *** 作系统的稳定性，也就是我一个进程不管做什么，都是在它自己的地址空间里做的，不会影响到其他进程和OS。

当然这是理想情况，实际上还有进程间通信啦之类，这就不在这个问题的范围之内了。

而具体怎么把这些虚拟地址对应到物理地址上，这是 *** 作系统做的事情，估计这个也就是你的问题。

----以上是背景1-----

然后我要明确一下：地址总线4位的意思是说内存用4个bit位来表达地址，所以能够index的地址位就是2^0-2^4，也就是0x0到0xf，就是16个bit的内存空间。

然后我们再来细化一下你的例子，就比方说在你的16bit的内存的机器上有1个OS，上面跑着2个程序。一般来说OS会保留地址的高位，比如11-15bit的位置，作为kernel space；然后0-10bit是user space。

在以上的前提下，虚拟内存的效果是：在每一个程序看来，这个程序都有0x0到0xf的地址可以用，并且它们的0xb-0xf都是shared kernel space，然后0x0-0xa都是自己的user space，这样仿佛就有了32个bit的地址一样。这就是你所谓的是用虚拟地址可以使总的地址 *** 作物理地址。至于os是怎么做到这点的，继续往下看。

-----以上是背景2-----

*** 作系统对每一个进程有一个进程控制块，叫PCB，Process Control Block，里边存储了每一个进程的进程信息，比如说寄存器，file descriptor，还有我们最关心的内存映射信息。每一个进程有一个递增的id号，叫pid，也就是Process IDentifier.

-----以上是背景3-----

进程间切换，也就是说，比如说你一个系统只有1个CPU，但是有两个进程要跑，而且要让我们看起来好像是两个进程同时在跑一样。为什么我要提到这个呢，后面继续看。

-----以上是背景4-----

好，现在来讲如何把虚拟地址映射到物理地址。从程序的角度来看，从malloc开始讲起，比如，在某一时刻，一个进程调用了malloc，在堆（heap）上申请了2bits的空间。实际上这个行为的流程是，程序调用malloc，进入内核模式之后，调用mmap，如果成功， *** 作系统会从物理地址上取一块2bits的内存，交给应用程序编入虚拟地址空间。更详细一点说，每个进程对内存管理是一个红黑树的结构，也就是说，在每一个进程的PCB，里维护了一颗红黑树，然后动态的将所有的新分配的内存加到这个红黑树里边，以保证程序对每一块内存的访问时间是差不多的。然后不知道你们教材中有没有提到页表（page table），页表也是PCB中的一项，你们教材中应该会对页表有详细的讲解，将如何对内存的地址进行换算，之类的。然后你要明确，页表实际上是红黑树的cache，这样可以加速程序对于常用的内存的访问速度。

以上是 *** 作系统对内存管理的一个大致概括，就是一块物理的内存如何映射成为一块虚拟的内存。

我在背景2中说，两个程序都看到自己有16个bit的虚拟地址，总共有32bit，但是实际上硬件只有16bits，也就是说，不管你在红黑树和页表中怎么映射，一定会有冲突发生，比如，可能物理地址的0x02对应了进程1中的0x04，又在进程2的PCB中映射到了pid2的虚拟地址位0x06上。 *** 作系统如何解决这个矛盾呢，首先在进程pid 1运行的时候，这个0x02对应的是pid1中的0x04；然后这个时候进程切换发生了，pid 2开始运行。当pid2需要用到它的0x04时，os发现0x02这个地址在pid1中也有映射，于是它就把0x02这个地址上的内容存到硬盘上的一个叫swap的空间内，然后把这个地址交给pid2使用。这样就达到了扩大虚拟地址的效果。

但是这样做是有代价的，因为一旦这个page被swap出去，那么在pid1再来调用的时候会发生一系列的miss，从L1 cache miss到 L2 cache miss到L3 cache miss，然后页表miss，memory miss，会对程序的性能造成极大的影响。影响有多大呢，平均来说：

L1 cache hit: 0.5ns

L2 cache hit: 7ns

主内存引用：100ns

顺序从内存中读取1MB：250,000ns

硬盘寻道：10,000,000ns

从硬盘上顺序读取1MB：30,000,000ns

所以你就可以知道这种行为是以极大的性能为代价的。

----讲完啦-----

总的来说这个很大的话题，我刚才所写的东西的就是试图让你对虚拟内存这个东西有一个基本的概念，然后大致的了解内存是如何映射的。就我现在能想到的，对这个虚拟内存话题的讨论还包括多级页表，进程间隔离&通信以及memory fragment。

个人水平有限，如果以上有什么地方说错的或者遗漏的，还请各位多多补充和批评，谢谢。

---