红黑树是一种平衡二叉树

红黑树的应用


  • Java 1.8之后HashMap的实现

  • epoll (a)

  • socket管理中的很多
  • 文件系统
  • 定时器(b)
  • 进程调度
  • 内存管理(a)
  • map(a)


无论场景多么复杂,无外乎用到rbtree的两大特性:

  • a.key/value –> 用来快速查找,如map
  • b.是顺序的,通过中序遍历,可以查找一段范围内的数据 –>诶进程调度,定时器(nginx里有用)

Linux内核中如何运用的红黑树?


进程管理 task_struct

task_struct 结构体,每一个进程,每一个线程,就是一个task_struct结构体

写时复制 Copy-On-Write,即fork出的子进程(或者pthreat_create出的线程),只有在发生更改时,才会发生分离

每个进程,一定有且仅有一个task_struct

ntyco–那个老师写的,不是佳作,但有值得借鉴之处

完全公平调度(cfs)用到了红黑树

nginx里的定时器也是这样做的,以时间戳作为key,定时去判断哪些节点超时了,然后执行相应事件



内存管理 mm_struct


(用来管理页表)

虚拟内存区域(VMA)


如何去表示一块细小的碎片内存?

答: 开始位置,大小或结束位置

我理解的 内存管理中所谓的”管理”,就是标记(占用或释放),定位/寻址


epoll的实现


epoll即EventPoll(fs),可以在Linux内核源码中搜索EventPoll,

fs即文件系统,epoll是文件系统里的一个东西,而不是网络里的内容

epoll跟网络有关? 错,半毛钱关系没有…

fd –> file descriptor,文件描述符,socket也是fd.

epoll是用来管理I/O的,socket是I/O的一种

2.6之后加入的epoll


实现原理:

用红黑树来存I/O,有1万个I/O,红黑树里就有1万个节点. key是int型的fd,value就是对应I/O的状态,如水平触发,带进来的状态等

把这成千上万个I/O里有数据的,放到一个队列里,即就绪队列.epoll_wait就是从这个队列(链表)里,拿到用户空间里

如何知道这个I/O有数据来了?

水平触发和边沿触发如何实现? 其核心原理是什么?epoll是不是线程安全的?



内核中的其他部分 如sk_buff

在内核源码中 搜一下rb_node, 就能知道内核里有多少使用到了红黑树

看内核源码,可以下一个 Source Insight

阅读内核代码时,不要去读那些和驱动,和硬件相关的.看通用型的,如进程调度,内存管理这些模块

动态规划没那么重要,相比来说,要对rbtree,btree及其排序有较好掌握



参考:
https://blog.csdn.net/guoweimelon/article/details/50904346

https://blog.csdn.net/hrn1216/article/details/51465270

https://zhuanlan.zhihu.com/p/37968599

https://www.zhihu.com/question/27840936

https://www.cnblogs.com/elwinch/articles/2040753.html