红黑树（Red-Black Tree，RBT）是一种平衡的二叉查找树，前面的红黑树原理与实现这篇文章中详细介绍了红黑树的细节。在Linux的内核源代码中已经给我们实现了一棵红黑树，我们可以方便地拿过来进行使用。本文将参考Linux内核的源码和文档资料，介绍Linux内核中红黑树的实现细节及使用方法。
设想一个场景：有100万用户同一时候与一个进程保持着TCP连接，而每个时刻仅仅有几十个或几百个TCP连接时活跃的（接收到TCP包），也就是说，在每一时刻，进程值须要处理这100万连接中的一小部分连接。那么，怎样才干高效地处理这样的场景呢？进程是否在每次询问操作系统收集有事件发生的TCP连接时，把这100万个连接告诉操作系统，然后由操作系统找出当中有事件发生的几百个连接呢？实际上，在Linux内核2.4版本号曾经，那时的select或者poll事件驱动方式就是这样做的。
Linux内核作为一个通用的操作系统（OS），需要兼顾各种各样类型的进程，包括实时进程、交互式进程、批处理进程等。而调度器（Scheduler）作为OS的核心组件——CPU时间的管理器，主要负责选择某些就绪的进程来执行。不同的调度器根据不同的方法挑选出最适合运行的进程。目前，在Linux内核中支持的调度器有CFS调度器、Realtime调度器、Deadline调度器和Idle调度器 。本篇将简单介绍CFS调度器的设计原理。
相比于select，epoll最大的好处在于它不会随着监听fd数目的增长而降低效率。因为在内核中的select实现中，它是采用轮询来处理的，轮询的fd数目越多，自然耗时越多。 并且，在linux/posix_types.h头文件有这样的声明： #define __FD_SETSIZE 1024 表示select最多同时监听1024个fd，当然，可以通过修改头文件再重编译内核来扩大这个数目，但这似乎并不治本。
导语：掐指一算自己从研究生开始投入到Linux的海洋也有几年的时间，即便如此依然对其各种功能模块一知半解。无数次看了Linux内核的技术文章后一头雾水，为了更系统地更有方法的学Linux，特此记录。 历史 1991年，还在芬兰赫尔辛基大学上学的Linus Torvalds在自己的Intel 386计算机上开发了属于他自己的第一个程序，并利用Internet发布了他开发的源代码，将其命名为Linux，从而创建了Linux操作系统，并在同年公开了Linux的代码，从而开启了一个伟大的时代。在之后的将近30
导语：掐指一算自己从研究生开始投入到Linux的海洋也有几年的时间，即便如此依然对其各种功能模块一知半解。无数次看了Linux内核的技术文章后一头雾水，为了更系统地更有方法的学Linux，特此记录。 历史 1991年，还在芬兰赫尔辛基大学上学的Linus Torvalds在自己的Intel 386计算机上开发了属于他自己的第一个程序，并利用Internet发布了他开发的源代码，将其命名为Linux，从而创建了Linux操作系统，并在同年公开了Linux的代码，从而开启了一个伟大的时代。在之后的将近30年的
进程优先级 Linux内核中进程优先级一般分为动态优先级和静态优先级，动态优先级是内核根据进程的nice值、IO密集行为或者计算密集行为以及等待时间等因素，设置给普通的进程；静态优先级是用户态应用设置给实时进程。在调度中静态优先级的进程优先级更高。 一般应用分为IO密集型和计算密集型；I/O密集型是进程执行I/O操作时候等待资源或者事件时候，数据读取到后恢复进程的运行，这样基本出于等待IO和运行之间进行交替，由于具有这样的特性，进程调度器通常会将短的CPU时间片分配给I/O密集型进程。计算密集型是进
微信又改版了，为了方便第一时间看到我的推送，请按照下列操作，设置“置顶”：点击上方蓝色字体“程序员乔戈里”-点击右上角“…”-点击“设为星标”。加星标不迷路!
调度：就是按照某种调度的算法设计，从进程的就绪队列中选择进程分配CPU，主要是协调进程对CPU等相关资源的使用。
由于Android系统是基于Linux系统的，所以有必要简单的介绍下Linux的跨进程通信，对大家后续了解Android的跨进程通信是有帮助的，本篇的主要内容如下：
Kmemleak能够检测内核中的内存泄漏，通过检测内核中未被释放但又无法找到其使用位置的内存，进一步定位、修复内存泄漏的问题。
本系列是对 陈莉君 老师 Linux 内核分析与应用[1] 的学习与记录。讲的非常之好，推荐观看
1. 问题 ---- 红黑树是一种自平衡的二叉查找树，它可以在O(logn)时间内执行查找、插入和删除。在c++ STL，linux内核中都有使用。 红黑树本身是有序的，现在问题是对于指定的元素，如何能快速查到它在整个元素集的排名，或者根据排名快速查询对应的元素？ 2. 思路 ---- 排名分顺序和逆序，这里只讨论顺序的情况。顺序的话排名就是求比当前元素小的元素的个数，根据红黑树的性质，左子树的节点都比根节点小，右子树的节点都比根节点大，求排名就等价于求节点左子树元素的个数。 根据树的递归性质，我们只需要在
输入输出(input/output)的对象可以是文件(file)， 网络(socket)，进程之间的管道(pipe)。在linux系统中，都用文件描述符(fd)来表示。
在linux 没有实现epoll事件驱动机制之前，我们一般选择用select或者poll等IO多路复用的方法来实现并发服务程序。在大数据、高并发、集群等一些名词唱得火热之年代，select和poll的用武之地越来越有限，风头已经被epoll占尽。
首先,我们要了解IO复用模型之前,先要了解在Linux内核中socket事件机制在内核底层是基于什么机制实现的,它是如何工作的,其次,当我们对socket事件机制有了一个基本认知之后,那么我们就需要思考到底什么是IO复用,基于socket事件机制的IO复用是怎么实现的,然后我们才来了解IO复用具体的实现技术,透过本质看select/poll/epoll的技术优化,逐渐去理解其中是为了解决什么问题而出现的,最后本文将围绕上述思维导图列出的知识点进行分享,还有就是文章幅度较长且需要思考,需要认真阅读!
I/O多路复用就是通过一种机制，可以同时监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。
4月26日收到了腾讯的offer,终于安心了,很多小伙伴们要我写面经介绍下,其实自己能拿到腾讯的offer 99%是运气~, 这里就介绍下自己的面经跟总结自己的看的书跟学习方法, 自己来自一所非985垫底的211大学~大三本科,主要学习的是Linux内核/C++,投的岗位都是后台开发, 自己的项目也就2个demo,一个简易kernel,一个很简单的网络库. 因为学校位置不方便,只投了腾讯跟美团.不可以投那么多互联网公司(路费.一出疆就上千),美团各种原因放弃了, 然后就这次到西安参加腾讯面试花了1800左右
| 导语本文主要是讲Linux的调度系统, 由于全部内容太多，分三部分来讲，本篇是中篇（主要讲抢占和时钟），上篇请看（CPU和中断）：Linux调度系统全景指南(上篇)，调度可以说是操作系统的灵魂，为了让CPU资源利用最大化，Linux设计了一套非常精细的调度系统，对大多数场景都进行了很多优化，系统扩展性强，我们可以根据业务模型和业务场景的特点，有针对性的去进行性能优化，在保证客户网络带宽前提下，隔离客户互相之间的干扰影响，提高CPU利用率，降低单位运算成本，提高市场竞争力。欢迎大家相互交流学习！
在linux 没有实现epoll事件驱动机制之前，我们一般选择用select或者poll等IO多路复用的方法来实现并发服务程序。在linux新的内核中，有了一种替换它的机制，就是epoll。
关于调度时机，网上的文章也五花八门，之前在内核抢占文章已经做了详细讲解，而在本文我们从源码注释中给出依据（再次强调一下：本文的调度时机关注的是何时调用主调度器，不是设置重新调度标志的时机，之前讲解中我们知道他们都可以称为调度时机）。
epoll接口是为解决Linux内核处理大量文件描述符而提出的方案。该接口属于Linux下多路I/O复用接口中select/poll的增强。其经常应用于Linux下高并发服务型程序，特别是在大量并发连接中只有少部分连接处于活跃下的情况 (通常是这种情况)，在该情况下能显著的提高程序的CPU利用率。本篇详细解读了epoll的用法，希望大家能有所收获！
树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。先从整体上认识下二叉树及其他各种树的区别和用途。
操作系统内核提供 read(系统调用)，读文件描述符 一个client连接就是一个文件描述符fd socket为阻塞的，socket产生的文件描述符，如左边的fd8，当数据包没到的时候，上面左边read不能返回，阻塞着。 即有一个client连接，就需要开一个进程(或者线程)，读这个连接，有数据就处理，没数据就阻塞着。
在这个连接的生命周期里，绝大部分时间都是空闲的，活跃时间（发送数据和接收数据的时间）占比极少，这样独占一个服务器是严重的资源浪费。事实上所有的服务器都是高并发的，可以同时为成千上万个客户端提供服务，这一技术又被称为IO复用。
大家都知道Linux内核task调度器经历了O(n)，O(1)调度器，目前是CFS，期间也出现了几个优秀的候选调度器，但最终都没能并入内核，我们只能从一些零散的patch和文章中知道它们的存在。
http://blog.csdn.net/silangquan/article/details/18655795
引用一句经典的话：“UNIX下一切皆文件”。 文件是一种抽象机制，它提供了一种方式用来存储信息以及在后面进行读取。
作者简介 赵晨雨：西安邮电大学2018级陈莉君教授研究生，天真无邪小白一枚，已经爱上linux内核而不能自拔，正在成长为内核狂热爱好者? 跟随陈老师学习linux内核两个月了，对linux内核
为什么会写这样一篇“无效水文”，我想是由于我的这样一种强迫症，对于任何的学习，在不理解原理，无法把他与我的已知知识架构产生联系的时候，我会本能地拒绝这种知识，所以由于这种偏执，很多情况下拖慢了自己的进度，因为很多时候无法有效收集到有用的资料，软件实训的时候，老师只会丢给一个配置文件，然后在此基础上做一些修改开发，可以除了可以勉强做一个垃圾出来，没有任何意义。就连再去做一个垃圾的能力都没有。这种情况直到毕业我才感觉无法再继续这样的生活了，于是开始大量学习，阅读专业书籍。这次就想对这些原本困扰我的东西进行一次小的抛砖引玉式的总结，当然也是把别人已经写过的一些文章综合一下，让入门的人对此好奇的人产生初步印象。 总之，人生没有白走的路。五年之前你正在梦想你今天的生活。 还有，当我们在经历冬季的时候，新西兰正被春风吹拂。所以做自己认为对的事情吧。
epoll简介 epoll 是Linux内核中的一种可扩展IO事件处理机制，最早在 Linux 2.5.44内核中引入，可被用于代替POSIX select 和 poll 系统调用，并且在具有大量应用程序请求时能够获得较好的性能（ 此时被监视的文件描述符数目非常大，与旧的 select 和 poll 系统调用完成操作所需 O(n) 不同， epoll能在O(1)时间内完成操作，所以性能相当高），epoll 与 FreeBSD的kqueue类似，都向用户空间提供了自己的文件描述符来进行操作。 [cpp]
在上一节我们了解了CFS的设计原理，包括CFS的引入，CFS是如何实现公平，CFS工作原理的。本小节我们重点在分析CFS调度器中涉及到的一些常见的数据结构，对这些数据结构做一个简单的概括，梳理各个数据结构之间的关系图出来。
CFS为了实现公平，必须惩罚当前正在运行的进程，以使那些正在等待的进程下次被调度。
数据结构这门课程是计算机相关专业的基础课，数据结构指的是数据在计算机中的存储、组织方式。
需求背景： 后台业务逻辑类服务，其实现通常都会依赖其他外部服务，比如存储，或者其他的逻辑server。 有一类比较典型的问题： 假设主调方A是同步处理模型，有一个关键路径是访问B服务。 当被调服务B延迟很高时，主调方A的进程会挂起等待，导致后来的A请求也无法及时处理，从而影响整个A服务的处理能力。甚至出现A服务不可用。 当然，比较理想的是B出现过载或者故障时，A的服务能力能够降到和B同等的服务能力，而非不可用。 因此，部门会定期进行容灾演习，也期望能够验证到各个服务的"最差服务能力"。即验证被调出现较高延迟
哈喽，我是子牙。十余年技术生涯，一路披荆斩棘从技术小白到技术总监到JVM专家到创业。技术栈如汇编、C语言、C++、Windows内核、Linux内核。特别喜欢研究虚拟机底层实现，对JVM有深入研究。分享的文章偏硬核，很硬的那种。 手撸过JVM、内存池、垃圾回收算法、synchronized、线程池、NIO、三色标记算法…
前言： KVM的设备虚拟化，除了前文《PIO技术分析》，还有另外一个核心概念---MMIO。原计划这里分析一下KVM的MMIO虚拟化。考虑到MMIO比PIO复杂很多，涉及更多的概念，作者打算先分析几篇基本的Linux的内存管理概念，再来分析MMIO。 作者大概想了一下，主要由这几篇构成： 1，虚拟内存管理和内存映射。 2，物理内存管理。 3，内存回收。 分析： 1，虚拟内存概念 x86的CPU有两种运行模式---real mode和protected mode。在real mode下，CPU访问的是物理
进程和线程究竟是什么东西？传统网络服务模型是如何工作的？协程和线程的关系和区别有哪些？IO过程在什么时间发生？ 在刚刚结束的 PyCon2014 上海站，来自七牛云存储的 Python 高级工程师许智翔带来了关于 Python 的分享《Python中的进程、线程、协程、同步、异步、回调》。 一、上下文切换技术 简述 在进一步之前，让我们先回顾一下各种上下文切换技术。 不过首先说明一点术语。当我们说“上下文”的时候，指的是程序在执行中的一个状态。通常我们会用调用栈来表示这个状态——栈记载了每个调用层级执行到哪
Redis的处理速度之快相比大家都是见惯不怪的了，主要的原因时什么呢，主要时以下的三个原因：
之前我写过一篇分析 O(1)调度算法 的文章：O(1)调度算法，而这篇主要分析 Linux 现在所使用的 完全公平调度算法。
原文地址：牛客网论坛最具争议的Linux内核成神笔记，GitHub已下载量已过百万
KSM只会处理通过madvise系统调用显式指定的用户进程地址空间，因此用户程序想使用这个功能就必须在分配地址空间时显式地调用madvise（addr，length，MADV_MERGEA BLE）。如果用户想在KSM中取消某一个用户进程地址空间的合并功能，也需要显式地调用madvise（addr，length,MADV_UNMERGEABLE)。 下面是测试KSM的test.c程序的代码片段，使用mmap()：来创建一个文件的私有映射，并且调用memset()写入这些私有映射的内容缓存页面中。
继上篇中科大软件学院硕士：实习秋招百多轮面试总结（上）收获了大家一致好评后，今天继续分享其它公司的面试经验和心得体会，希望可以帮助打算找工作或跳槽的朋友们~
随着cpu技术发展，现在大部分移动设备、PC、服务器都已经使用上64bit的CPU，但是关于Linux内核的虚拟内存管理，还停留在历史的用户态与内核态虚拟内存3:1的观念中，导致在解决一些内存问题时存在误解。
Linux定时器分为低精度定时器和高精度定时器两种类型，内核对其均有实现。本文讨论的是我们在应用程序开发中比较常见的低精度定时器。作为常用的基础组件，定时器常用的几种实现方法包括：基于排序链表实现、基于小根堆实现、基于红黑树实现、基于时间轮实现。本文讲解的是时间复杂度最优，也是linux内核采用的基于时间轮的实现方式。
关于红黑树的介绍网上非常多，红黑树的应用也非常广泛。问一下度娘，她会告诉你各种各样的实现方法，C和C++版本都有，linux内核使用的版本也有。代码都大同小异，就是插入或删除时如何修正，如何搞平衡。很多文章图文并茂、写实而生动，当你在脑海里试图左旋一把，右旋一把搞平衡时，基本也到了精神崩溃的边缘。
如何知道自己的系统使用哪个Linux内核版本？以下是在Linux终端中检查内核版本的几种方法。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议
