红黑树（Red-Black Tree，RBT）是一种平衡的二叉查找树，前面的红黑树原理与实现这篇文章中详细介绍了红黑树的细节。在Linux的内核源代码中已经给我们实现了一棵红黑树，我们可以方便地拿过来进行使用。本文将参考Linux内核的源码和文档资料，介绍Linux内核中红黑树的实现细节及使用方法。
调度器 的 主要职责 就是 对 " 进程 " 进行 " 调度管理 " , 调度时 进程 是放在 " 调度队列 " 中的 ,
Linux内核作为一个通用的操作系统（OS），需要兼顾各种各样类型的进程，包括实时进程、交互式进程、批处理进程等。而调度器（Scheduler）作为OS的核心组件——CPU时间的管理器，主要负责选择某些就绪的进程来执行。不同的调度器根据不同的方法挑选出最适合运行的进程。目前，在Linux内核中支持的调度器有CFS调度器、Realtime调度器、Deadline调度器和Idle调度器 。本篇将简单介绍CFS调度器的设计原理。
之前我写过一篇分析 O(1)调度算法 的文章：O(1)调度算法，而这篇主要分析 Linux 现在所使用的 完全公平调度算法。
严格来说，Linux 不是实时操作系统，但 Linux 却支持实时调度算法。与通用调度算法（如完全公平调度算法）相比，实时调度算法更注重任务（进程）的实时性。为什么 Linux 支持实时调度算法，却不是实时操作系统呢？有兴趣的同学可以去网上查阅相关的文献或者资料。
Linux 内核源码 linux-5.6.18\kernel\sched\sched.h 中 , 定义的 struct sched_class 调度类结构体 , 就是 " 调度器 " 对应的类 ;
epoll有EPOLLLT和EPOLLET两种触发模式，水平触发和边缘触发. 此处略
由于Android系统是基于Linux系统的，所以有必要简单的介绍下Linux的跨进程通信，对大家后续了解Android的跨进程通信是有帮助的，本篇的主要内容如下：
在 【Linux 内核】实时调度类 ③ ( 实时调度类 rt_sched_class 源码 | 调度类 sched_class 源码 ) 博客中 , 简单介绍了 实时调度类 rt_sched_class 结构体 , 下面开始分析该结构体的具体字段含义 ,
树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。先从整体上认识下二叉树及其他各种树的区别和用途。
本系列是对 陈莉君 老师 Linux 内核分析与应用[1] 的学习与记录。讲的非常之好，推荐观看
这两天和同事讨论起linux进程调度的问题，比如进程统计、那些进程优先运行、怎么调度等，对此在这里和大家一同复习一下。先来说说怎么查看进程。在使用Linux操作系统的过程中，掌握如何查看和管理进程是系统管理的重要技能之一。进程管理不仅有助于监控系统资源的使用情况，还能帮助排查问题和优化系统性能。
红黑树在很多地方有应用，在阅读《STL源码剖析》的时候遇到红黑树，费了一番功夫才看明白。
红黑树是算法领域中一个著名的二叉查找树实现，它能够以较小的开销保持二叉查找树的平衡。具备平衡性质的二叉查找树能够极大地提高节点的查询速度。举个形象一点的例子：从一个十亿节点的红黑树中查找一个节点，所需要的查询次数不到 30，这不禁让人感叹算法的魅力。
中 , 介绍了 调度类 sched_class 结构体的源码 , 重要的 字段 以及 函数指针 ;
（1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！] （4）如果一个节点是红色的，则它的子节点必须是黑色的。 （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
在上一节我们了解了CFS的设计原理，包括CFS的引入，CFS是如何实现公平，CFS工作原理的。本小节我们重点在分析CFS调度器中涉及到的一些常见的数据结构，对这些数据结构做一个简单的概括，梳理各个数据结构之间的关系图出来。
本篇博客中 , 开始分析 struct sched_class rt_sched_class 结构体变量 中的各个 函数指针 指向的 函数源码 ;
红黑树，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
KSM只会处理通过madvise系统调用显式指定的用户进程地址空间，因此用户程序想使用这个功能就必须在分配地址空间时显式地调用madvise（addr，length，MADV_MERGEA BLE）。如果用户想在KSM中取消某一个用户进程地址空间的合并功能，也需要显式地调用madvise（addr，length,MADV_UNMERGEABLE)。 下面是测试KSM的test.c程序的代码片段，使用mmap()：来创建一个文件的私有映射，并且调用memset()写入这些私有映射的内容缓存页面中。
在这个连接的生命周期里，绝大部分时间都是空闲的，活跃时间（发送数据和接收数据的时间）占比极少，这样独占一个服务器是严重的资源浪费。事实上所有的服务器都是高并发的，可以同时为成千上万个客户端提供服务，这一技术又被称为IO复用。
前言 红黑树是算法领域中一个著名的二叉查找树实现，它能够以较小的开销保持二叉查找树的平衡。具备平衡性质的二叉查找树能够极大地提高节点的查询速度。举个形象一点的例子：从一个十亿节点的红黑树中查找一个节点，所需要的查询次数不到 30，这不禁让人感叹算法的魅力。 红黑树是工程中最常见的二叉查找树的实现，例如在 Linux 的内存管理和进程管理中就用到了红黑树；Java 语言的集合包、C++语言的标准模板库中均提供了红黑树的实现类。 红黑树本身的设计很复杂，多数情况下我们也不需要自己去实现红黑树，但研究红黑树还
算法是基础，小蓝同学准备些总结一系列算法分享给大家，这是第8篇《平衡查找树概述》，非常赞！希望对大家有帮助，大家会喜欢！ 前面系列文章： 归并排序 #算法基础#选择和插入排序 由快速排序到分治思想 算法基础：优先队列 二分查找 二叉树查找 平衡查找树概述 我们在上一节写了平衡树的一些理念和具体的实现名（算法基础7：平衡查找树概述），为了解决其查找成本较高的这个问题，我们采取了扩大节点来减少层级的方式来达到这个目标。根据这个理念，我们找到了平衡查找树树。 一、 下面我们来一起聊一聊平衡树的具体实现红黑
CFS为了实现公平，必须惩罚当前正在运行的进程，以使那些正在等待的进程下次被调度。
AVL树是一种自平衡的二叉查找树，又称平衡二叉树。AVL用平衡因子判断是否平衡并通过旋转来实现平衡，它的平衡的要求是：所有节点的左右子树高度差不超过1。AVL树是一种高平衡度的二叉树，执行插入或者删除操作之后，只要不满足上面的平衡条件，就要通过旋转来保持平衡，而的由于旋转比较耗时，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况。 由于维护这种高度平衡所付出的代价可能比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。 红黑树(Red Black Tree)，它一种特殊的二叉查找树，是AVL树的特化变种，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 红黑树的平衡的要求是：从根到叶子的最长的路径不会比于最短的路径的长超过两倍。 因此，红黑树是一种弱平衡二叉树，在相同的节点情况下，AVL树的高度<=红黑树。 红黑树是用弱平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，降低了对旋转的要求，从而提高了性能，所以对于查询，插入，删除操作都较多的情况下，用红黑树。
输入输出(input/output)的对象可以是文件(file)， 网络(socket)，进程之间的管道(pipe)。在linux系统中，都用文件描述符(fd)来表示。
不知道前端小伙伴们都了解“红黑树”吗？本瓜，之前听是听过，但是它到底是干嘛的，并不十分清楚。在认识了平衡二叉树、AVL 树之后，现在已经来到了这个节点，必须来看下“红黑树”了！
红黑树是一颗二叉搜索树，通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。 树的每个结点包含5个属性，color，key，left，right，p。如果一个结点没有子结点或父结点，则该结点的响应指针属性的指为NIL。我们可以把这些NIL视为指向二叉搜索树的叶结点（外部节点）的指针，把带关键字的结点视为树的内部结点。 一颗红黑树是满足下面红黑性质的二叉搜索树： 1.每个结点或是红色的，或是黑色的。 2.根结点是黑色的。 3.每个叶子结点（NIL）是黑色的。 4.如果一个结点是红的，那么它的两个子结点都是黑的。 5.对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑结点。 ——引用自《算法导论》 第十三章 红黑树 红黑树的性质
在《你真的理解内存分配》一文中，我们介绍了 malloc 申请内存的原理，但其在内核怎么实现的呢？所以，本文主要分析在 Linux 内核中对堆内存分配的实现过程。
首先需要思考的问题是：什么是调度器（scheduler）？调度器的作用是什么？调度器是一个操作系统的核心部分。可以比作是CPU时间的管理员。调度器主要负责选择某些就绪的进程来执行。不同的调度器根据不同的方法挑选出最适合运行的进程。目前Linux支持的调度器就有RT scheduler、Deadline scheduler、CFS scheduler及Idle scheduler等。我想用一系列文章呈现Linux 调度器的设计原理。
epoll接口是为解决Linux内核处理大量文件描述符而提出的方案。该接口属于Linux下多路I/O复用接口中select/poll的增强。其经常应用于Linux下高并发服务型程序，特别是在大量并发连接中只有少部分连接处于活跃下的情况 (通常是这种情况)，在该情况下能显著的提高程序的CPU利用率。本篇详细解读了epoll的用法，希望大家能有所收获！
1. 问题 ---- 红黑树是一种自平衡的二叉查找树，它可以在O(logn)时间内执行查找、插入和删除。在c++ STL，linux内核中都有使用。 红黑树本身是有序的，现在问题是对于指定的元素，如何能快速查到它在整个元素集的排名，或者根据排名快速查询对应的元素？ 2. 思路 ---- 排名分顺序和逆序，这里只讨论顺序的情况。顺序的话排名就是求比当前元素小的元素的个数，根据红黑树的性质，左子树的节点都比根节点小，右子树的节点都比根节点大，求排名就等价于求节点左子树元素的个数。 根据树的递归性质，我们只需要在
回顾一下 通俗易懂的红黑树图解(上)，上篇首先介绍了二叉树的定义以及二叉树的查找，然后介绍了红黑树的五点性质以及红黑树的变色、左旋以及右旋等操作，最后结合变色、左旋及右旋详细讲解了插入节点的五种场景。而本篇通俗易懂的红黑树图解(下)是在上篇的基础上讲解红黑树最后一种操作-删除节点，删除节点相对插入节点会复杂一点，但通过分类归纳出不同的场景，能更容易理解和记忆。
http://blog.csdn.net/silangquan/article/details/18655795
还在为智商过多而烦恼吗？还在为无处装逼而郁闷吗？赶紧抓起手上的电话，打开微信秘籍酷，查看今天的装逼巅峰话题红黑树！今天林药师亲自调制，无色无味，居家旅行装逼必备良品，服一剂神清气爽，服两剂目瞪口呆！
调度：就是按照某种调度的算法设计，从进程的就绪队列中选择进程分配CPU，主要是协调进程对CPU等相关资源的使用。
前言： KVM的设备虚拟化，除了前文《PIO技术分析》，还有另外一个核心概念---MMIO。原计划这里分析一下KVM的MMIO虚拟化。考虑到MMIO比PIO复杂很多，涉及更多的概念，作者打算先分析几篇基本的Linux的内存管理概念，再来分析MMIO。 作者大概想了一下，主要由这几篇构成： 1，虚拟内存管理和内存映射。 2，物理内存管理。 3，内存回收。 分析： 1，虚拟内存概念 x86的CPU有两种运行模式---real mode和protected mode。在real mode下，CPU访问的是物理
在早期的 linux 操作系统中，2.4 版本到 2.6 版本之间，linux 采用了实现起来十分简单的 O(n) 调度器。
本文是《Linux内核设计与实现》第四章的阅读笔记，代码则是摘自最新的4.6版本linux源码(github)，转载请注明出处。
最近有小伙伴拿到了一线互联网企业如美团、拼多多、极兔、有赞、希音的面试资格，遇到一几个很重要的面试题：
设想一个场景：有100万用户同一时候与一个进程保持着TCP连接，而每个时刻仅仅有几十个或几百个TCP连接时活跃的（接收到TCP包），也就是说，在每一时刻，进程值须要处理这100万连接中的一小部分连接。那么，怎样才干高效地处理这样的场景呢？进程是否在每次询问操作系统收集有事件发生的TCP连接时，把这100万个连接告诉操作系统，然后由操作系统找出当中有事件发生的几百个连接呢？实际上，在Linux内核2.4版本号曾经，那时的select或者poll事件驱动方式就是这样做的。
操作系统内核提供 read(系统调用)，读文件描述符 一个client连接就是一个文件描述符fd socket为阻塞的，socket产生的文件描述符，如左边的fd8，当数据包没到的时候，上面左边read不能返回，阻塞着。 即有一个client连接，就需要开一个进程(或者线程)，读这个连接，有数据就处理，没数据就阻塞着。
相比于select，epoll最大的好处在于它不会随着监听fd数目的增长而降低效率。因为在内核中的select实现中，它是采用轮询来处理的，轮询的fd数目越多，自然耗时越多。 并且，在linux/posix_types.h头文件有这样的声明： #define __FD_SETSIZE 1024 表示select最多同时监听1024个fd，当然，可以通过修改头文件再重编译内核来扩大这个数目，但这似乎并不治本。
前言 红黑树是数据结构中比较复杂的一种，最近与它交集颇多，于是花了一周的空闲时间跟它死磕，终于弄明白并实现了红黑树。写文总结一下，希望能给试图理解红黑树的同学一些灵感，也让我能记得更深刻。 在研究红黑树时吃了不少苦头，原因有二： 红黑树的插入和删除非常复杂，很多人并没有理解或完全实现，或实现了的没有任何注释，让人很难参考； 网络上红黑树的理解方式较为单一，一般是 双黑、caseN 法，而插入和删除的情况很多，每种都有对应的处理方式，如果死记硬背的话，再过一段时间再回忆各种情况可能就一头雾水了。 网络上讲红黑
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
实时音视频
