几种常见的查找算法之比较

性质1: 每个节点要么是 黑色 ,要么是 红色 。 性质2: 根节点是 黑色 。 性质3: 每个叶子节点(NIL)是黑色。 性质4: 每个 红色 节点的两个子节点一定都是 黑色 。 性质5: 任意一个节点到每个叶子节点的路径都包含 数量相同 的 黑节点 。俗称: 黑高 ! 从性质5又可以推出: 性质5.1: 如果一个节点存在黑子节点,那么该结点肯定有两个子节点。 插入操作包括两部分工作: 注意: 插入结点,必须为 红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。 最简单的一种情景,直接把插入结点作为根结点就行 注意: 根据红黑树性质2: 根结点是黑色。还需要把插入结点设为黑色。 处理: 更新当前结点的值,为插入结点的值 由于插入的结点是红色的,当插入结点的父结点为黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。 再次回想红黑树的性质2: 根结点是黑色。如果插入结点的父结点为 红结点 ,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这一点很重要,因为后序的旋转操作肯定需要祖父结点的参与。 依据红黑树 性质4可知,红色结点不能相连===>祖父结点肯定为黑结点 因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为: 红黑红 处理: 1.将P和U结点改为黑色 2.将PP改为红色 3.将PP设置为当前结点,进行后序处理 注意: 单纯从插入前来看,叔叔结点非红即空(NIL结点),否则的话破坏了红黑树性质5,此路径比其它路径多一个黑色结点。 处理: 处理: 该情景对应情景4.2,只是方向反转,直接看图 处理: 处理:

1.C++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组，list封装了链表，map和set封装了二叉树等2.标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-BlackTree)。RB树的统计性能要好于一般的 平衡二叉树3.STL map和set的使用虽不复杂，但也有一些不易理解的地方，如： map: type pair <constKey, T> ，很多不同的 const Key 对应的 T 对象的一个集合，所有的记录集中只要 const Key 不一样就可以， T 无关！ set: type const Key. 只存单一的对 const Key ，没有 map 的 T 对像！可以看成 map 的一个特例（1）为何map和set的插入删除效率比用其他序列容器高？，树答：因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。map和set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点（2）为何每次insert之后，以前保存的iterator不会失效？答：iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。（3）为何map和set不能像vector一样有个reserve函数来预分配数据？答：我以前也这么问，究其原理来说时，引起它的原因在于在map和set内部存储的已经不是元素本身了，而是包含元素的节点。也就是说map内部使用的Alloc并不是map<Key, Data, Compare, Alloc>声明的时候从参数中传入的Alloc。例如：4.set, multiset set和multiset会根据特定的排序准则自动将元素排序，set中元素不允许重复，multiset可以重复。因为是排序的，所以set中的元素不能被修改，只能删除后再添加。 向set中添加的元素类型必须重载<操作符用来排序。排序满足以下准则： 1、非对称，若A<B为真，则B<A为假。 2、可传递，若A<B,B<C，则A<C。 3、A<A永远为假。set中判断元素是否相等： if(!(A<B || B<A))，当A<B和B<A都为假时，它们相等。 5.map，multimap map和multimap将key和value组成的pair作为元素，根据key的排序准则自动将元素排序，map中元素的key不允许重复，multimap可以重复。map<key,value>因为是排序的，所以map中元素的key不能被修改，只能删除后再添加。key对应的value可以修改。向map中添加的元素的key类型必须重载<操作符用来排序。排序与set规则一致。6. List的功能方法 实际上有两种List: 一种是基本的ArrayList,其优点在于随机访问元素，另一种是更强大的LinkedList,它并不是为快速随机访问设计的，而是具有一套更通用的方法。 List : 次序是List最重要的特点：它保证维护元素特定的顺序。List为Collection添加了许多方法，使得能够向List中间插入与移除元素(这只推荐LinkedList使用。)一个List可以生成ListIterator,使用它可以从两个方向遍历List,也可以从List中间插入和移除元素。ArrayList : 由数组实现的List。允许对元素进行快速随机访问，但是向List中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历ArrayList,而不是用来插入和移除元素。因为那比LinkedList开销要大很多。 LinkedList : 对顺序访问进行了优化，向List中间插入与删除的开销并不大。随机访问则相对较慢。(使用ArrayList代替。)还具有下列方法：addFirst(), addLast(), getFirst(),getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用7..1 hash_map和map的区别在哪里？构造函数。hash_map需要hash函数，等于函数；map只需要比较函数(小于函数).存储结构。hash_map采用hash表存储，map一般采用 红黑树(RB Tree) 实现。因此其memory数据结构是不一样的。7.2 什么时候需要用hash_map，什么时候需要用map?总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且hash_map的构造速度较慢。现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。8.一些使用上的建议： Level 1 - 仅仅作为Map使用：采用静态数组 Level 2 - 保存定长数据，使用时也是全部遍历：采用动态数组（长度一开始就固定的话静态数组也行） Level 3 - 保存不定长数组，需要动态增加的能力，侧重于寻找数据的速度：采用vector Level 3 - 保存不定长数组，需要动态增加的能力，侧重于增加删除数据的速度：采用list Level 4 - 对数据有复杂操作，即需要前后增删数据的能力，又要良好的数据访问速度：采用deque Level 5 - 对数据中间的增删操作比较多：采用list，建议在排序的基础上，批量进行增删可以对运行效率提供最大的保证 Level 6 - 上述中找不到适合的：组合STL容器或者自己建立特殊的数据结构来实现9.(1).vector - 会自动增长的数组vector<int>vec(10) //一个有10个int元素的容器 vector<float> vec(10, 0.5)//一个有10个float元素的容器，并且他们得值都是0.5 vector<int>::iterator iter; for(iter = vec.begin(); iter != vec.end(); iter++) { //. . . . . . . }vector由于数组的增长只能向前，所以也只提供了后端插入和后端删除， 也就是push_back和pop_back。当然在前端和中间要操作数据也是可以的， 用insert和erase，但是前端和中间对数据进行操作必然会引起数据块的移动， 这对性能影响是非常大的。最大的优势就是随机访问的能力。vector<T1>::iterator相关的方法有： begin()：用来获得一个指向vector第一个元素的指针 end()：用来获得一个指向vector最后一个元素之后的那个位置的指针，注意不是指向最后一个元素。 erase(vector<T1>::iterator)：用来删除作为参数所传入的那个iterator所指向的那个元素。(2).list - 擅长插入删除的链表list<string>Milkshakes; list<int> Scores;push_back, pop_backpush_front. pop_frontlist是一个双向链表的实现。 为了提供双向遍历的能力，list要比一般的数据单元多出两个指向前后的指针一个使用iterator来删除元素的例子 list<string> stringList; list<string>::iterator iter; advance(iter, 5); //将iterator指向stringList的第五个元素 stringList.erase(iterator);//删除 那么删除操作进行以后，传入erase()方法的iterator指向哪里了呢？它指向了删除操作前所指向的那个元素的后一个元素。(3).deque - 拥有vector和list两者优点的双端队列(4)．这三个模板的总结 比较和一般使用准则 这三个模板都属于序列类模板，可以看到他们有一些通用方法 size():得到容器大小 begin():得到指向容器内第一个元素的指针（这个指针的类型依容器的不同而不同） end():得到指向容器内最后一个元素之后一个位置的指针 erase():删除传入指针指向的那个元素 clear():清除所有的元素 ＝＝运算符：判断两个容器是否相等 ＝运算符：用来给容器赋值 上面的三个模板有各自的特点 vector模板的数据在内存中连续的排列，所以随机存取元素（即通过[]运算符存取）的速度最快，这一点和数组是一致的。同样由于它的连续排列，所以它在除尾部以外的位置删除或添加元素的速度很慢，在使用vector时，要避免这种操作。 list模板的数据是链式存储，所以不能随机存取元素。它的优势在于任意位置添加 删除元素的速度。 deque模板是通过链接若干片连续的数据实现的，所以均衡了以上两个容器的特点

Map用于保存具有映射关系的数据，Map里保存着两组数据：key和value，它们都可以使任何引用类型的数据，但key不能重复。所以通过指定的key就可以取出对应的value。Map接口定义了如下常用的方法：1、void clear():删除Map中所以键值对。2、boolean containsKey(Object key):查询Map中是否包含指定key，如果包含则返回true。3、boolean containsValue(Object value):查询Map中是否包含指定value，如果包含则返回true。4、Set entrySet():返回Map中所包含的键值对所组成的Set集合，每个集合元素都是Map.Entry对象(Entry是Map的内部类)。5、Object get(Object key):返回指定key所对应的value，如Map中不包含key则返回null。6、boolean isEmpty():查询Map是否为空，如果空则返回true。7、Set keySet():返回该Map中所有key所组成的set集合。8、Object put(Object key,Object value):添加一个键值对，如果已有一个相同的key值则新的键值对覆盖旧的键值对。9、void putAll(Map m):将指定Map中的键值对复制到Map中。10、Object remove(Object key):删除指定key所对应的键值对，返回可以所关联的value，如果key不存在，返回null。11、int size():返回该Map里的键值对的个数。12、Collection values():返回该Map里所有value组成的Collection。Map中包含一个内部类：Entry。该类封装了一个键值对，它包含了三个方法：1、Object getKey():返回该Entry里包含的key值。2、Object getValeu():返回该Entry里包含的value值。3、Object setValue(V value):设置该Entry里包含的value值，并返回新设置的value值。HashMap和Hashtable实现类：HashMap与HashTable的区别：1、 同步性：Hashtable是同步的，这个类中的一些方法保证了Hashtable中的对象是线程安全的。而HashMap则是异步的，因此HashMap中的对象并不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用HashMap是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销，从而提高效率。2、 值：HashMap可以让你将空值作为一个表的条目的key或value，但是Hashtable是不能放入空值的。HashMap最多只有一个key值为null，但可以有无数多个value值为null。注意：1、用作key的对象必须实现hashCode和equals方法。2、不能保证其中的键值对的顺序3、尽量不要使用可变对象作为它们的key值。 LinkedHashMap： 它的父类是HashMap，使用双向链表来维护键值对的次序，迭代顺序与键值对的插入顺序保持一致。LinkedHashMap需要维护元素的插入顺序，so性能略低于HashMap，但在迭代访问元素时有很好的性能，因为它是以链表来维护内部顺序。TreeMap: Map接口派生了一个SortMap子接口，SortMap的实现类为TreeMap。TreeMap也是基于红黑树对所有的key进行排序，有两种排序方式：自然排序和定制排序。Treemap的key以TreeSet的形式存储，对key的要求与TreeSet对元素的要求基本一致。1、Map.Entry firstEntry():返回最小key所对应的键值对，如Map为空，则返回null。2、Object firstKey():返回最小key，如果为空，则返回null。3、Map.Entry lastEntry():返回最大key所对应的键值对，如Map为空，则返回null。4、Object lastKey():返回最大key，如果为空，则返回null。5、Map.Entry higherEntry(Object key):返回位于key后一位的键值对，如果为空，则返回null。6、Map.Entry lowerEntry(Object key):返回位于key前一位的键值对，如果为空，则返回null。7、Object lowerKey(Object key):返回位于key前一位key值，如果为空，则返回null。8、NavigableMap subMap(Object fromKey,boolean fromlnclusive,Object toKey,boolean toInciusive):返回该Map的子Map，其key范围从fromKey到toKey。9、SortMap subMap(Object fromKey,Object toKey );返回该Map的子Map，其key范围从fromkey（包括）到tokey（不包括）。10、SortMap tailMap（Object fromkey ,boolean inclusive）:返回该Map的子Map，其key范围大于fromkey（是否包括取决于第二个参数）的所有key。11、 SortMap headMap（Object tokey ,boolean inclusive）:返回该Map的子Map，其key范围小于tokey（是否包括取决于第二个参数）的所有key。WeakHashMap： WeakHashMap与HashMap的用法基本相同，区别在于：后者的key保留对象的强引用，即只要HashMap对象不被销毁，其对象所有key所引用的对象不会被垃圾回收，HashMap也不会自动删除这些key所对应的键值对对象。但WeakHashMap的key所引用的对象没有被其他强引用变量所引用，则这些key所引用的对象可能被回收。WeakHashMap中的每个key对象保存了实际对象的弱引用，当回收了该key所对应的实际对象后，WeakHashMap会自动删除该key所对应的键值对。 public static void main(String[] args) { // TODO Auto-generated method stub WeakHashMap w1=new WeakHashMap(); //添加三个键值对，三个key都是匿名字符串，没有其他引用 w1 .put("语文", "良好"); w1 .put("数学", "及格"); w1 .put("英语", "中等"); w1 .put("java", "good");//该key是一个系统缓存的字符串对象 System.out.println(w1 );//输出{java=good, 数学=及格, 英语=中等, 语文=良好} //通知系统进行垃圾回收 System.gc(); System.runFinalization(); System.out.println(w1 );//输出{java=good} }IdentityHashMap类：IdentityHashMap与HashMap基本相似，只是当两个key严格相等时，即key1==key2时，它才认为两个key是相等的 。IdentityHashMap也允许使用null，但不保证键值对之间的顺序。EnumMap类：1、EnumMap中所有key都必须是单个枚举类的枚举值，创建EnumMap时必须显示或隐式指定它对应的枚举类。2、EnumMap根据key的自然顺序，即枚举值在枚举类中定义的顺序，来维护键值对的次序。3、EnumMap不允许使用null作为key值，但value可以。

1. 数据结构的定义。 2. 栈的两个应用：括号匹配和表达式的计算。是怎么应用的？表达式计算用的是哪种表达方式？有什么好处? 3. 字符串匹配算法：朴素的匹配算法、KMP算法。 4. 二叉树前序、中序、后序递归遍历算法。二叉树前序非递归遍历算法。 5. 堆，建堆算法，堆的插入和删除算法，堆排序。 6. 哈希。哈希函数的有哪些种？余数的取法？ 处理冲突的方法？ 闭散列方法有哪些？ 7. 二叉搜索树的搜索、插入、删除。时间复杂度。 8. 二叉平衡树的插入结点的原理，有哪几种旋转方式？分别适用于哪种情况。分析二叉平衡树的时间复杂度。 9. 红黑树的定义，红黑树的性能分析和与二叉平衡树的比较。 10. 图有哪些储存表示。 11. 链表插入排序、链表归并排序。 12. 常见的有哪几种排序算法，试比较其时间复杂度，以及是否稳定，及各自使用的情形。 13. 常用分配排序有哪几种？ 基数排序的定义，分类及原理。 14. 外部排序的过程。 15. B树、B+树、Trie的概念及用途，添加删除结点的原理。

不会。计算机考研408数据结构考试内容是计算机组成原理、操作系统等，红黑树是一种特殊形式的平衡二叉搜索树。

在前文中，我们分析了内核中进程和线程的统一结构体task_struct，并分析进程、线程的创建和派生的过程。在本文中，我们会对任务间调度进行详细剖析，了解其原理和整个执行过程。由此，进程、线程部分的大体框架就算是介绍完了。本节主要分为三个部分：Linux内核中常见的调度策略，调度的基本结构体以及调度发生的整个流程。下面将详细展开说明。 Linux 作为一个多任务操作系统，将每个 CPU 的时间划分为很短的时间片，再通过调度器轮流分配给各个任务使用，因此造成多任务同时运行的错觉。为了维护 CPU 时间，Linux 通过事先定义的节拍率（内核中表示为 HZ），触发时间中断，并使用全局变量 Jiffies 记录了开机以来的节拍数。每发生一次时间中断，Jiffies 的值就加 1。节拍率 HZ 是内核的可配选项，可以设置为 100、250、1000 等。不同的系统可能设置不同的数值，可以通过查询 /boot/config 内核选项来查看它的配置值。 Linux的调度策略主要分为实时任务和普通任务。实时任务需求尽快返回结果，而普通任务则没有较高的要求。在前文中我们提到了task_struct中调度策略相应的变量为policy，调度优先级有prio, static_prio, normal_prio, rt_priority几个。优先级其实就是一个数值，对于实时进程来说，优先级的范围是 0 99；对于普通进程，优先级的范围是 100 139。数值越小，优先级越高。 实时调度策略主要包括以下几种 普通调度策略主要包括以下几种： 首先，我们需要一个结构体去执行调度策略，即sched_class。该类有几种实现方式 普通任务调度实体源码如下，这里面包含了 vruntime 和权重 load_weight，以及对于运行时间的统计。 在调度时，多个任务调度实体会首先区分是实时任务还是普通任务，然后通过以时间为顺序的红黑树结构组合起来，vruntime 最小的在树的左侧，vruntime最多的在树的右侧。以CFS策略为例，则会选择红黑树最左边的叶子节点作为下一个将获得 CPU 的任务。而这颗红黑树，我们称之为运行时队列（run queue），即struct rq。 其中包含结构体cfs_rq，其定义如下，主要是CFS调度相关的结构体，主要有权值相关变量、vruntime相关变量以及红黑树指针，其中结构体rb_root_cached即为红黑树的节点 对结构体dl_rq有类似的定义，运行队列由红黑树结构体构成，并按照deadline策略进行管理 对于实施队列相应的rt_rq则有所不同，并没有用红黑树实现。 下面再看看调度类sched_class，该类以函数指针的形式定义了诸多队列操作，如 调度类分为下面几种： 队列操作中函数指针指向不同策略队列的实际执行函数函数，在linux/kernel/sched/目录下，fair.c、idle.c、rt.c等文件对不同类型的策略实现了不同的函数，如fair.c中定义了 以选择下一个任务为例，CFS对应的是pick_next_task_fair，而rt_rq对应的则是pick_next_task_rt，等等。 由此，我们来总结一下： 有了上述的基本策略和基本调度结构体，我们可以形成大致的骨架，下面就是需要核心的调度流程将其拼凑成一个整体，实现调度系统。调度分为两种，主动调度和抢占式调度。 说到调用，逃不过核心函数schedule()。其中sched_submit_work()函数完成当前任务的收尾工作，以避免出现如死锁或者IO中断等情况。之后首先禁止抢占式调度的发生，然后调用__schedule()函数完成调度，之后重新打开抢占式调度，如果需要重新调度则会一直重复该过程，否则结束函数。 而__schedule()函数则是实际的核心调度函数，该函数主要操作包括选取下一进程和进行上下文切换，而上下文切换又包括用户态空间切换和内核态的切换。具体的解释可以参照英文源码注释以及中文对各个步骤的注释。 其中核心函数是获取下一个任务的pick_next_task()以及上下文切换的context_switch()，下面详细展开剖析。首先看看pick_next_task()，该函数会根据调度策略分类，调用该类对应的调度函数选择下一个任务实体。根据前文分析我们知道，最终是在不同的红黑树上选择最左节点作为下一个任务实体并返回。 下面来看看上下文切换。上下文切换主要干两件事情，一是切换任务空间，也即虚拟内存；二是切换寄存器和 CPU 上下文。关于任务空间的切换放在内存部分的文章中详细介绍，这里先按下不表，通过任务空间切换实际完成了用户态的上下文切换工作。下面我们重点看一下内核态切换，即寄存器和CPU上下文的切换。 switch_to()就是寄存器和栈的切换，它调用到了 __switch_to_asm。这是一段汇编代码，主要用于栈的切换， 其中32位使用esp作为栈顶指针，64位使用rsp，其他部分代码一致。通过该段汇编代码我们完成了栈顶指针的切换，并调用__switch_to完成最终TSS的切换。注意switch_to中其实是有三个变量，分别是prev, next, last，而实际在使用时，我们会对last也赋值为prev。这里的设计意图需要结合一个例子来说明。假设有ABC三个任务，从A调度到B，B到C，最后C回到A，我们假设仅保存prev和next，则流程如下 最终调用__switch_to()函数。该函数中涉及到一个结构体TSS(Task State Segment)，该结构体存放了所有的寄存器。另外还有一个特殊的寄存器TR（Task Register）会指向TSS，我们通过更改TR的值，会触发硬件保存CPU所有寄存器在当前TSS，并从新的TSS读取寄存器的值加载入CPU，从而完成一次硬中断带来的上下文切换工作。系统初始化的时候，会调用 cpu_init()给每一个 CPU 关联一个 TSS，然后将 TR 指向这个 TSS，然后在操作系统的运行过程中，TR 就不切换了，永远指向这个 TSS。当修改TR的值得时候，则为任务调度。 更多Linux内核视频教程文本资料免费领取后台私信【 内核大礼包 】自行获取。 在完成了switch_to()的内核态切换后，还有一个重要的函数finish_task_switch()负责善后清理工作。在前面介绍switch_to三个参数的时候我们已经说明了使用last的重要性。而这里为何让prev和last均赋值为prev，是因为prev在后面没有需要用到，所以节省了一个指针空间来存储last。 至此，我们完成了内核态的切换工作，也完成了整个主动调度的过程。 抢占式调度通常发生在两种情况下。一种是某任务执行时间过长，另一种是当某任务被唤醒的时候。首先看看任务执行时间过长的情况。 该情况需要衡量一个任务的执行时间长短，执行时间过长则发起抢占。在计算机里面有一个时钟，会过一段时间触发一次时钟中断，通知操作系统时间又过去一个时钟周期，通过这种方式可以查看是否是需要抢占的时间点。 时钟中断处理函数会调用scheduler_tick()。该函数首先取出当前CPU，并由此获取对应的运行队列rq和当前任务curr。接着调用该任务的调度类sched_class对应的task_tick()函数进行时间事件处理。 以普通任务队列为例，对应的调度类为fair_sched_class，对应的时钟处理函数为task_tick_fair()，该函数会获取当前的调度实体和运行队列，并调用entity_tick()函数更新时间。 在entity_tick()中，首先会调用update_curr()更新当前任务的vruntime，然后调用check_preempt_tick()检测现在是否可以发起抢占。 check_preempt_tick() 先是调用 sched_slice() 函数计算出一个调度周期中该任务运行的实际时间 ideal_runtime。sum_exec_runtime 指任务总共执行的实际时间，prev_sum_exec_runtime 指上次该进程被调度时已经占用的实际时间，所以 sum_exec_runtime - prev_sum_exec_runtime 就是这次调度占用实际时间。如果这个时间大于 ideal_runtime，则应该被抢占了。除了这个条件之外，还会通过 __pick_first_entity 取出红黑树中最小的进程。如果当前进程的 vruntime 大于红黑树中最小的进程的 vruntime，且差值大于 ideal_runtime，也应该被抢占了。 如果确认需要被抢占，则会调用resched_curr()函数，该函数会调用set_tsk_need_resched()标记该任务为_TIF_NEED_RESCHED，即该任务应该被抢占。 某些任务会因为中断而唤醒，如当 I/O 到来的时候，I/O进程往往会被唤醒。在这种时候，如果被唤醒的任务优先级高于 CPU 上的当前任务，就会触发抢占。try_to_wake_up() 调用 ttwu_queue() 将这个唤醒的任务添加到队列当中。ttwu_queue() 再调用 ttwu_do_activate() 激活这个任务。ttwu_do_activate() 调用 ttwu_do_wakeup()。这里面调用了 check_preempt_curr() 检查是否应该发生抢占。如果应该发生抢占，也不是直接踢走当前进程，而是将当前进程标记为应该被抢占。 由前面的分析，我们知道了不论是是当前任务执行时间过长还是新任务唤醒，我们均会对现在的任务标记位_TIF_NEED_RESCUED，下面分析实际抢占的发生。真正的抢占还需要一个特定的时机让正在运行中的进程有机会调用一下 __schedule()函数，发起真正的调度。 实际上会调用__schedule()函数共有以下几个时机 从系统调用返回用户态：以64位为例，系统调用的链路为do_syscall_64->syscall_return_slowpath->prepare_exit_to_usermode->exit_to_usermode_loop。在exit_to_usermode_loop中，会检测是否为_TIF_NEED_RESCHED，如果是则调用__schedule() 内核态启动：内核态的执行中，被抢占的时机一般发生在 preempt_enable() 中。在内核态的执行中，有的操作是不能被中断的，所以在进行这些操作之前，总是先调用 preempt_disable() 关闭抢占，当再次打开的时候，就是一次内核态代码被抢占的机会。preempt_enable() 会调用 preempt_count_dec_and_test()，判断 preempt_count 和 TIF_NEED_RESCHED 是否可以被抢占。如果可以，就调用 preempt_schedule->preempt_schedule_common->__schedule 进行调度。 u2003u2003 本文分析了任务调度的策略、结构体以及整个调度流程，其中关于内存上下文切换的部分尚未详细叙述，留待内存部分展开剖析。 1、调度相关结构体及函数实现 2、schedule核心函数

压缩的本质就是去冗余，去除信息冗余，使用最短的编码保存最完整的数据信息。所以对于不同的场景，压缩采用的算法也因时制宜，比如视频和图片可以采用有损压缩，而文本数据采用无损压缩。压缩率又取决于信息的冗余度，也就是内容中重复的比例。那些均匀分布的随机字符串，压缩率会降到最低，即香农限 deflate是zip文件的默认算法。它更是一种数据流压缩算法。 LZ77压缩算法采用字典的方式进行压缩，是一种简单但是很高效的数据压缩算法。其方式就是把数据中一些可以组织成短语的字符加入字典。维护三个概念： 短语字典、滑动窗口、向前缓冲区 压缩的逆过程，通过解码标记和保持滑动窗口中的符号来更新解压数据。当解码字符被标记:将标记编码成字符拷贝到滑动窗口中，一步一步直到全部翻译完成 在流式传输中，不定长编码数据的解码想要保持唯一性，必须满足唯一可以码的条件。而异前缀码就是一种唯一可译码的候选，当然这样会增加编码的长度，却可以简化解码。 huffman编码是一种基于概率分布的贪心策略最优前缀码。huffman编码可以有效的压缩数据，压缩率取决于数据本身的信息冗余度 计算数据中各符号出现的概率，根据概率从小到大，从下往上反向构建构造码树，这样最终得到的编码的平均长度是最短的。同时也是唯一可译的 解读：在一开始，每一个字符已经按照出现概率的大小排好顺序，在后续的步骤中，每一次将概率最低的两棵树合并，然后用合并后的结果再次排序（为了找出最小的两棵树）。在gzip源码中并没有专门去排序，而是使用专门的数据结构（比如最小堆或者红黑树）。 使用优先队列实现huffman树，最后基于Huffman树最终实现文件压缩。 具体步骤： gzip = gzip 头 + deflate 编码的实际内容 + gzip 尾 zlib = zlib 头 + deflate 编码的实际内容 + zlib 尾 压缩之前：初始化各种输入输出缓冲区； 压缩：我们可以不断往这些缓冲区中填充内容，然后由deflate函数进行压缩或者indeflate函数进行解压 总结：在调用deflate函数之前，应用程序必须保证至少一个动作被执行（avail_in或者avail_out被设置），用提供更多数据或者消耗更多的数据的方式。avail_out在函数调用之前千万不能为零。应用程序可以随时消耗被压缩的输出数据

1、MySQL支持的索引结构有四种：B+树，R树，HASH，FULLTEXT。B树是一种多叉的AVL树。B-Tree减少了AVL数的高度，增加了每个节点的KEY数量。2、其余节点用来索引，而B-树是每个索引节点都会有Data域。这就决定了B+树更适合用来存储外部数据，也就是所谓的磁盘数据。3、mysql的数据结构用的是b+而不是b红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

平衡二叉树（AVL）那对图 1 进行下改造，把数据重新节点重新连接下，图 2 如下：图 2 可以看到以下特性：1. 所有左子树的节点都小于其对应的父节点（4，5，6）<（7）；（4）<（5）；（8）< （9）；2. 所有右子树上的节点都大于其对应的父节点（8，9，10）>（7）；（6）>（5）；（10）>（9）；3. 每个节点的平衡因子差值绝对值 <=1；4. 每个节点都符合以上三个特征。满足这样条件的树叫平衡二叉树（AVL）树。问：那再次查找节点 5，需要遍历多少次呢？由于数据是按照顺序组织的，那查找起来非常快，从上往下找：7-5，只需要在左子树上查找，也就是遍历 2 次就找到了 5。假设要找到叶子节点 10，只需要在右子树上查找，那也最多需要 3 次，7-9-10。也就说 AVL 树在查找方面性能很好，最坏的情况是找到一个节点需要消耗的次数也就是树的层数， 复杂度为 O(logN)如果节点非常多呢？假设现在有 31 个节点，用 AVL 树表示如图 3：图 3 是一棵高度为 4 的 AVL 树，有 5 层共 31 个节点，橙色是 ROOT 节点，蓝色是叶子节点。对 AVL 树的查找来看起来已经很完美了，能不能再优化下？比如，能否把这个节点里存放的 KEY 增加？能否减少树的总层数？那减少纵深只能从横向来想办法，这时候可以考虑用多叉树。

培训机构就是速成的所以怎么会将原理，我现在在看某马的视频，引入一个新的类/方法或者概念的时候，我都会听他讲一遍我再去网上论坛理解一遍。最主要的还是需要靠自己，多敲多练，听课的时候老师进度会很快所以你先标注下不懂的，下午晚上休息的时候再去网上解答，把一天的内容巩固一遍

9 一般的评测机器是一亿次

前言：本文主要讲解Linux IO调度层的三种模式：cfp、deadline和noop，并给出各自的优化和适用场景建议。IO调度发生在Linux内核的IO调度层。这个层次是针对Linux的整体IO层次体系来说的。从read()或者write()系统调用的角度来说，Linux整体IO体系可以分为七层，它们分别是：VFS层： 虚拟文件系统层。由于内核要跟多种文件系统打交道，而每一种文件系统所实现的数据结构和相关方法都可能不尽相同，所以，内核抽象了这一层，专门用来适配各种文件系统，并对外提供统一操作接口。文件系统层： 不同的文件系统实现自己的操作过程，提供自己特有的特征，具体不多说了，大家愿意的话自己去看代码即可。页缓存层： 负责真对page的缓存。通用块层： 由于绝大多数情况的io操作是跟块设备打交道，所以Linux在此提供了一个类似vfs层的块设备操作抽象层。下层对接各种不同属性的块设备，对上提供统一的Block IO请求标准。IO调度层 ：因为绝大多数的块设备都是类似磁盘这样的设备，所以有必要根据这类设备的特点以及应用的不同特点来设置一些不同的调度算法和队列。以便在不同的应用环境下有针对性的提高磁盘的读写效率，这里就是大名鼎鼎的Linux电梯所起作用的地方。针对机械硬盘的各种调度方法就是在这实现的。块设备驱动层： 驱动层对外提供相对比较高级的设备操作接口，往往是C语言的，而下层对接设备本身的操作方法和规范。块设备层： 这层就是具体的物理设备了，定义了各种真对设备操作方法和规范。有一个已经整理好的[Linux IO结构图]，非常经典，一图胜千言：我们今天要研究的内容主要在IO调度这一层。它要解决的核心问题是，如何提高块设备IO的整体性能？这一层也主要是针对机械硬盘结构而设计的。众所周知，机械硬盘的存储介质是磁盘，磁头在盘片上移动进行磁道寻址，行为类似播放一张唱片。这种结构的特点是，顺序访问时吞吐量较高，但是如果一旦对盘片有随机访问，那么大量的时间都会浪费在磁头的移动上，这时候就会导致每次IO的响应时间变长，极大的降低IO的响应速度。磁头在盘片上寻道的操作，类似电梯调度，实际上在最开始的时期，Linux把这个算法命名为Linux电梯算法，即：如果在寻道的过程中，能把顺序路过的相关磁道的数据请求都“顺便”处理掉，那么就可以在比较小影响响应速度的前提下，提高整体IO的吞吐量。这就是我们为什么要设计IO调度算法的原因。目前在内核中默认开启了三种算法/模式：noop，cfq和deadline。严格算应该是两种：因为第一种叫做noop，就是空操作调度算法，也就是没有任何调度操作，并不对io请求进行排序，仅仅做适当的io合并的一个fifo队列。目前内核中默认的调度算法应该是cfq，叫做完全公平队列调度。这个调度算法人如其名，它试图给所有进程提供一个完全公平的IO操作环境。注：请大家一定记住这个词语，cfq，完全公平队列调度，不然下文就没法看了。cfq为每个进程创建一个同步IO调度队列，并默认以时间片和请求数限定的方式分配IO资源，以此保证每个进程的IO资源占用是公平的，cfq还实现了针对进程级别的优先级调度，这个我们后面会详细解释。查看和修改IO调度算法的方法是：cfq是通用服务器比较好的IO调度算法选择，对桌面用户也是比较好的选择。但是对于很多IO压力较大的场景就并不是很适应，尤其是IO压力集中在某些进程上的场景。因为这种场景我们需要更多的满足某个或者某几个进程的IO响应速度，而不是让所有的进程公平的使用IO，比如数据库应用。deadline调度（最终期限调度）就是更适合上述场景的解决方案。deadline实现了四个队列：其中两个分别处理正常read和write，按扇区号排序，进行正常io的合并处理以提高吞吐量。因为IO请求可能会集中在某些磁盘位置，这样会导致新来的请求一直被合并，可能会有其他磁盘位置的io请求被饿死。另外两个处理超时read和write的队列，按请求创建时间排序，如果有超时的请求出现，就放进这两个队列，调度算法保证超时（达到最终期限时间）的队列中的请求会优先被处理，防止请求被饿死。不久前，内核还是默认标配四种算法，还有一种叫做as的算法（Anticipatory scheduler），预测调度算法。一个高大上的名字，搞得我一度认为Linux内核都会算命了。结果发现，无非是在基于deadline算法做io调度的之前等一小会时间，如果这段时间内有可以合并的io请求到来，就可以合并处理，提高deadline调度的在顺序读写情况下的数据吞吐量。其实这根本不是啥预测，我觉得不如叫撞大运调度算法，当然这种策略在某些特定场景差效果不错。但是在大多数场景下，这个调度不仅没有提高吞吐量，还降低了响应速度，所以内核干脆把它从默认配置里删除了。毕竟Linux的宗旨是实用，而我们也就不再这个调度算法上多费口舌了。1、cfq：完全公平队列调度cfq是内核默认选择的IO调度队列，它在桌面应用场景以及大多数常见应用场景下都是很好的选择。如何实现一个所谓的完全公平队列（Completely Fair Queueing）？首先我们要理解所谓的公平是对谁的公平？从操作系统的角度来说，产生操作行为的主体都是进程，所以这里的公平是针对每个进程而言的，我们要试图让进程可以公平的占用IO资源。那么如何让进程公平的占用IO资源？我们需要先理解什么是IO资源。当我们衡量一个IO资源的时候，一般喜欢用的是两个单位，一个是数据读写的带宽，另一个是数据读写的IOPS。带宽就是以时间为单位的读写数据量，比如，100Mbyte/s。而IOPS是以时间为单位的读写次数。在不同的读写情境下，这两个单位的表现可能不一样，但是可以确定的是，两个单位的任何一个达到了性能上限，都会成为IO的瓶颈。从机械硬盘的结构考虑，如果读写是顺序读写，那么IO的表现是可以通过比较少的IOPS达到较大的带宽，因为可以合并很多IO，也可以通过预读等方式加速数据读取效率。当IO的表现是偏向于随机读写的时候，那么IOPS就会变得更大，IO的请求的合并可能性下降，当每次io请求数据越少的时候，带宽表现就会越低。从这里我们可以理解，针对进程的IO资源的主要表现形式有两个： 进程在单位时间内提交的IO请求个数和进程占用IO的带宽。其实无论哪个，都是跟进程分配的IO处理时间长度紧密相关的。有时业务可以在较少IOPS的情况下占用较大带宽，另外一些则可能在较大IOPS的情况下占用较少带宽，所以对进程占用IO的时间进行调度才是相对最公平的。即，我不管你是IOPS高还是带宽占用高，到了时间咱就换下一个进程处理，你爱咋样咋样。所以，cfq就是试图给所有进程分配等同的块设备使用的时间片，进程在时间片内，可以将产生的IO请求提交给块设备进行处理，时间片结束，进程的请求将排进它自己的队列，等待下次调度的时候进行处理。这就是cfq的基本原理。当然，现实生活中不可能有真正的“公平”，常见的应用场景下，我们很肯能需要人为的对进程的IO占用进行人为指定优先级，这就像对进程的CPU占用设置优先级的概念一样。所以，除了针对时间片进行公平队列调度外，cfq还提供了优先级支持。每个进程都可以设置一个IO优先级，cfq会根据这个优先级的设置情况作为调度时的重要参考因素。优先级首先分成三大类：RT、BE、IDLE，它们分别是实时（Real Time）、最佳效果（Best Try）和闲置（Idle）三个类别，对每个类别的IO，cfq都使用不同的策略进行处理。另外，RT和BE类别中，分别又再划分了8个子优先级实现更细节的QOS需求，而IDLE只有一个子优先级。另外，我们都知道内核默认对存储的读写都是经过缓存（buffer/cache）的，在这种情况下，cfq是无法区分当前处理的请求是来自哪一个进程的。只有在进程使用同步方式（sync read或者sync wirte）或者直接IO（Direct IO）方式进行读写的时候，cfq才能区分出IO请求来自哪个进程。所以，除了针对每个进程实现的IO队列以外，还实现了一个公共的队列用来处理异步请求。当前内核已经实现了针对IO资源的cgroup资源隔离，所以在以上体系的基础上，cfq也实现了针对cgroup的调度支持。总的来说，cfq用了一系列的数据结构实现了以上所有复杂功能的支持，大家可以通过源代码看到其相关实现，文件在源代码目录下的block/cfq-iosched.c。1.1 cfq设计原理在此，我们对整体数据结构做一个简要描述：首先，cfq通过一个叫做cfq_data的数据结构维护了整个调度器流程。在一个支持了cgroup功能的cfq中，全部进程被分成了若干个contral group进行管理。每个cgroup在cfq中都有一个cfq_group的结构进行描述，所有的cgroup都被作为一个调度对象放进一个红黑树中，并以vdisktime为key进行排序。vdisktime这个时间纪录的是当前cgroup所占用的io时间，每次对cgroup进行调度时，总是通过红黑树选择当前vdisktime时间最少的cgroup进行处理，以保证所有cgroups之间的IO资源占用“公平”。当然我们知道，cgroup是可以对blkio进行资源比例分配的，其作用原理就是，分配比例大的cgroup占用vdisktime时间增长较慢，分配比例小的vdisktime时间增长较快，快慢与分配比例成正比。这样就做到了不同的cgroup分配的IO比例不一样，并且在cfq的角度看来依然是“公平“的。选择好了需要处理的cgroup（cfq_group）之后，调度器需要决策选择下一步的service_tree。service_tree这个数据结构对应的都是一系列的红黑树，主要目的是用来实现请求优先级分类的，就是RT、BE、IDLE的分类。每一个cfq_group都维护了7个service_trees，其定义如下：其中service_tree_idle就是用来给IDLE类型的请求进行排队用的红黑树。而上面二维数组，首先第一个维度针对RT和BE分别各实现了一个数组，每一个数组中都维护了三个红黑树，分别对应三种不同子类型的请求，分别是：SYNC、SYNC_NOIDLE以及ASYNC。我们可以认为SYNC相当于SYNC_IDLE并与SYNC_NOIDLE对应。idling是cfq在设计上为了尽量合并连续的IO请求以达到提高吞吐量的目的而加入的机制，我们可以理解为是一种“空转”等待机制。空转是指，当一个队列处理一个请求结束后，会在发生调度之前空等一小会时间，如果下一个请求到来，则可以减少磁头寻址，继续处理顺序的IO请求。为了实现这个功能，cfq在service_tree这层数据结构这实现了SYNC队列，如果请求是同步顺序请求，就入队这个service tree，如果请求是同步随机请求，则入队SYNC_NOIDLE队列，以判断下一个请求是否是顺序请求。所有的异步写操作请求将入队ASYNC的service tree，并且针对这个队列没有空转等待机制。此外，cfq还对SSD这样的硬盘有特殊调整，当cfq发现存储设备是一个ssd硬盘这样的队列深度更大的设备时，所有针对单独队列的空转都将不生效，所有的IO请求都将入队SYNC_NOIDLE这个service tree。每一个service tree都对应了若干个cfq_queue队列，每个cfq_queue队列对应一个进程，这个我们后续再详细说明。cfq_group还维护了一个在cgroup内部所有进程公用的异步IO请求队列，其结构如下：异步请求也分成了RT、BE、IDLE这三类进行处理，每一类对应一个cfq_queue进行排队。BE和RT也实现了优先级的支持，每一个类型有IOPRIO_BE_NR这么多个优先级，这个值定义为8，数组下标为0-7。我们目前分析的内核代码版本为Linux 4.4，可以看出，从cfq的角度来说，已经可以实现异步IO的cgroup支持了，我们需要定义一下这里所谓异步IO的含义，它仅仅表示从内存的buffer/cache中的数据同步到硬盘的IO请求，而不是aio(man 7 aio)或者linux的native异步io以及libaio机制，实际上这些所谓的“异步”IO机制，在内核中都是同步实现的（本质上冯诺伊曼计算机没有真正的“异步”机制）。我们在上面已经说明过，由于进程正常情况下都是将数据先写入buffer/cache，所以这种异步IO都是统一由cfq_group中的async请求队列处理的。那么为什么在上面的service_tree中还要实现和一个ASYNC的类型呢？这当然是为了支持区分进程的异步IO并使之可以“完全公平”做准备喽。实际上在最新的cgroup v2的blkio体系中，内核已经支持了针对buffer IO的cgroup限速支持，而以上这些可能容易混淆的一堆类型，都是在新的体系下需要用到的类型标记。新体系的复杂度更高了，功能也更加强大，但是大家先不要着急，正式的cgroup v2体系，在Linux 4.5发布的时候会正式跟大家见面。我们继续选择service_tree的过程，三种优先级类型的service_tree的选择就是根据类型的优先级来做选择的，RT优先级最高，BE其次，IDLE最低。就是说，RT里有，就会一直处理RT，RT没了再处理BE。每个service_tree对应一个元素为cfq_queue排队的红黑树，而每个cfq_queue就是内核为进程（线程）创建的请求队列。每一个cfq_queue都会维护一个rb_key的变量，这个变量实际上就是这个队列的IO服务时间（service time）。这里还是通过红黑树找到service time时间最短的那个cfq_queue进行服务，以保证“完全公平”。选择好了cfq_queue之后，就要开始处理这个队列里的IO请求了。这里的调度方式基本跟deadline类似。cfq_queue会对进入队列的每一个请求进行两次入队，一个放进fifo中，另一个放进按访问扇区顺序作为key的红黑树中。默认从红黑树中取请求进行处理，当请求的延时时间达到deadline时，就从红黑树中取等待时间最长的进行处理，以保证请求不被饿死。这就是整个cfq的调度流程，当然其中还有很多细枝末节没有交代，比如合并处理以及顺序处理等等。1.2 cfq的参数调整理解整个调度流程有助于我们决策如何调整cfq的相关参数。所有cfq的可调参数都可以在/sys/class/block/sda/queue/iosched/目录下找到，当然，在你的系统上，请将sda替换为相应的磁盘名称。我们来看一下都有什么：这些参数部分是跟机械硬盘磁头寻道方式有关的，如果其说明你看不懂，请先补充相关知识：back_seek_max:磁头可以向后寻址的最大范围，默认值为16M。back_seek_penalty:向后寻址的惩罚系数。这个值是跟向前寻址进行比较的。以上两个是为了防止磁头寻道发生抖动而导致寻址过慢而设置的。基本思路是这样，一个io请求到来的时候，cfq会根据其寻址位置预估一下其磁头寻道成本。设置一个最大值back_seek_max，对于请求所访问的扇区号在磁头后方的请求，只要寻址范围没有超过这个值，cfq会像向前寻址的请求一样处理它。再设置一个评估成本的系数back_seek_penalty，相对于磁头向前寻址，向后寻址的距离为1/2(1/back_seek_penalty)时，cfq认为这两个请求寻址的代价是相同。这两个参数实际上是cfq判断请求合并处理的条件限制，凡事复合这个条件的请求，都会尽量在本次请求处理的时候一起合并处理。fifo_expire_async:设置异步请求的超时时间。同步请求和异步请求是区分不同队列处理的，cfq在调度的时候一般情况都会优先处理同步请求，之后再处理异步请求，除非异步请求符合上述合并处理的条件限制范围内。当本进程的队列被调度时，cfq会优先检查是否有异步请求超时，就是超过fifo_expire_async参数的限制。如果有，则优先发送一个超时的请求，其余请求仍然按照优先级以及扇区编号大小来处理。fifo_expire_sync:这个参数跟上面的类似，区别是用来设置同步请求的超时时间。slice_idle:参数设置了一个等待时间。这让cfq在切换cfq_queue或service tree的时候等待一段时间，目的是提高机械硬盘的吞吐量。一般情况下，来自同一个cfq_queue或者service tree的IO请求的寻址局部性更好，所以这样可以减少磁盘的寻址次数。这个值在机械硬盘上默认为非零。当然在固态硬盘或者硬RAID设备上设置这个值为非零会降低存储的效率，因为固态硬盘没有磁头寻址这个概念，所以在这样的设备上应该设置为0，关闭此功能。group_idle:这个参数也跟上一个参数类似，区别是当cfq要切换cfq_group的时候会等待一段时间。在cgroup的场景下，如果我们沿用slice_idle的方式，那么空转等待可能会在cgroup组内每个进程的cfq_queue切换时发生。这样会如果这个进程一直有请求要处理的话，那么直到这个cgroup的配额被耗尽，同组中的其它进程也可能无法被调度到。这样会导致同组中的其它进程饿死而产生IO性能瓶颈。在这种情况下，我们可以将slice_idle ＝ 0而group_idle ＝ 8。这样空转等待就是以cgroup为单位进行的，而不是以cfq_queue的进程为单位进行，以防止上述问题产生。low_latency:这个是用来开启或关闭cfq的低延时（low latency）模式的开关。当这个开关打开时，cfq将会根据target_latency的参数设置来对每一个进程的分片时间（slice time）进行重新计算。这将有利于对吞吐量的公平（默认是对时间片分配的公平）。关闭这个参数（设置为0）将忽略target_latency的值。这将使系统中的进程完全按照时间片方式进行IO资源分配。这个开关默认是打开的。我们已经知道cfq设计上有“空转”（idling）这个概念，目的是为了可以让连续的读写操作尽可能多的合并处理，减少磁头的寻址操作以便增大吞吐量。如果有进程总是很快的进行顺序读写，那么它将因为cfq的空转等待命中率很高而导致其它需要处理IO的进程响应速度下降，如果另一个需要调度的进程不会发出大量顺序IO行为的话，系统中不同进程IO吞吐量的表现就会很不均衡。就比如，系统内存的cache中有很多脏页要写回时，桌面又要打开一个浏览器进行操作，这时脏页写回的后台行为就很可能会大量命中空转时间，而导致浏览器的小量IO一直等待，让用户感觉浏览器运行响应速度变慢。这个low_latency主要是对这种情况进行优化的选项，当其打开时，系统会根据target_latency的配置对因为命中空转而大量占用IO吞吐量的进程进行限制，以达到不同进程IO占用的吞吐量的相对均衡。这个开关比较合适在类似桌面应用的场景下打开。target_latency:当low_latency的值为开启状态时，cfq将根据这个值重新计算每个进程分配的IO时间片长度。quantum:这个参数用来设置每次从cfq_queue中处理多少个IO请求。在一个队列处理事件周期中，超过这个数字的IO请求将不会被处理。这个参数只对同步的请求有效。slice_sync:当一个cfq_queue队列被调度处理时，它可以被分配的处理总时间是通过这个值来作为一个计算参数指定的。公式为：time_slice = slice_sync + (slice_sync/5 * (4 - prio))。这个参数对同步请求有效。slice_async:这个值跟上一个类似，区别是对异步请求有效。slice_async_rq:这个参数用来限制在一个slice的时间范围内，一个队列最多可以处理的异步请求个数。请求被处理的最大个数还跟相关进程被设置的io优先级有关。1.3 cfq的IOPS模式我们已经知道，默认情况下cfq是以时间片方式支持的带优先级的调度来保证IO资源占用的公平。高优先级的进程将得到更多的时间片长度，而低优先级的进程时间片相对较小。当我们的存储是一个高速并且支持NCQ（原生指令队列）的设备的时候，我们最好可以让其可以从多个cfq队列中处理多路的请求，以便提升NCQ的利用率。此时使用时间片的分配方式分配资源就显得不合时宜了，因为基于时间片的分配，同一时刻最多能处理的请求队列只有一个。这时，我们需要切换cfq的模式为IOPS模式。切换方式很简单，就是将slice_idle=0即可。内核会自动检测你的存储设备是否支持NCQ，如果支持的话cfq会自动切换为IOPS模式。另外，在默认的基于优先级的时间片方式下，我们可以使用ionice命令来调整进程的IO优先级。进程默认分配的IO优先级是根据进程的nice值计算而来的，计算方法可以在man ionice中看到，这里不再废话。2、deadline：最终期限调度deadline调度算法相对cfq要简单很多。其设计目标是：在保证请求按照设备扇区的顺序进行访问的同时，兼顾其它请求不被饿死，要在一个最终期限前被调度到。我们知道磁头对磁盘的寻道是可以进行顺序访问和随机访问的，因为寻道延时时间的关系，顺序访问时IO的吞吐量更大，随机访问的吞吐量小。如果我们想为一个机械硬盘进行吞吐量优化的话，那么就可以让调度器按照尽量复合顺序访问的IO请求进行排序，之后请求以这样的顺序发送给硬盘，就可以使IO的吞吐量更大。但是这样做也有另一个问题，就是如果此时出现了一个请求，它要访问的磁道离目前磁头所在磁道很远，应用的请求又大量集中在目前磁道附近。导致大量请求一直会被合并和插队处理，而那个要访问比较远磁道的请求将因为一直不能被调度而饿死。deadline就是这样一种调度器，能在保证IO最大吞吐量的情况下，尽量使远端请求在一个期限内被调度而不被饿死的调度器。

想象你有一个魔法箱子（HashMap），你可以把东西放进去，并且给每个东西贴上标签（键）以便稍后找到它们。箱子的内部是由一系列抽屉组成，每个抽屉都有一个唯一的标签（哈希码）。当你要放入一样东西时，首先你会生成一个标签（哈希码），这个标签会告诉你应该将东西放入哪个抽屉。假设你想放入一本书，并给它贴上标签 "科学书"，然后根据这个标签（哈希码），你找到对应的抽屉并把书放进去。现在，如果你想找回这本书，你只需要记得它的标签 "科学书"，然后根据这个标签（哈希码）再次找到对应的抽屉，从抽屉里拿出书来。这样你就能快速找到你之前放入箱子的东西。然而，有时候不同的东西可能会有相同的标签（哈希码），这就是所谓的哈希碰撞。在箱子内部，为了解决这个问题，每个抽屉都是一个链表，可以存放多个东西。当发生哈希碰撞时，新的东西会被添加到链表中，而不是新建一个抽屉。当箱子的负载（放入的东西数量）逐渐增加时，为了保持箱子的高效性能，箱子会自动增大，并重新调整抽屉的布局，确保箱子里的抽屉数量适合放入的东西的数量。这就是 Java 中 HashMap 的底层原理。它利用哈希函数将键映射到特定的索引位置，然后在该位置存储值。如果存在哈希碰撞，它会使用链表来处理冲突。当箱子内的东西越来越多时，箱子会自动调整大小，以保持高效性能。这种数据结构使得 HashMap 在大多数情况下能够快速查找和插入数据。

// 1. 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树） // 否则，若桶内元素太多时，则直接扩容，而不是树形化 // 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD static final int MIN_TREEIFY_CAPACITY = 64; // 2. 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树 static final int TREEIFY_THRESHOLD = 8; // 3. 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表 static final int UNTREEIFY_THRESHOLD = 6;

以一个生活中的例子来解释. 假设你在大学中读书,要等待一个朋友来访,而这个朋友只知道你在A号楼,但是不知道你具体住在哪里,于是你们约好了在A号楼门口见面. 如果你使用的阻塞IO模型来处理这个问题,那么你就只能一直守候在A号楼门口等待朋友的到来,在这段时间里你不能做别的事情,不难知道,这种方式的效率是低下的. 进一步解释select和epoll模型的差异. select版大妈做的是如下的事情:比如同学甲的朋友来了,select版大妈比较笨,她带着朋友挨个房间进行查询谁是同学甲,你等的朋友来了,于是在实际的代码中,select版大妈做的是以下的事情: int n = select(&readset,NULL,NULL,100); for (int i = 0; n > 0; ++i) { if (FD_ISSET(fdarray[i], &readset)) { do_something(fdarray[i]); --n; } }epoll版大妈就比较先进了,她记下了同学甲的信息,比如说他的房间号,那么等同学甲的朋友到来时,只需要告诉该朋友同学甲在哪个房间即可,不用自己亲自带着人满大楼的找人了.于是epoll版大妈做的事情可以用如下的代码表示: n = epoll_wait(epfd,events,20,500); for(i=0;i<n;++i) { do_something(events[n]); } 在epoll中,关键的数据结构epoll_event定义如下: typedef union epoll_data { void *ptr; int fd; __uint32_t u32; __uint64_t u64; } epoll_data_t; struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */ }; 可以看到,epoll_data是一个union结构体,它就是epoll版大妈用于保存同学信息的结构体,它可以保存很多类型的信息:fd,指针,等等.有了这个结构体,epoll大妈可以不用吹灰之力就可以定位到同学甲. 别小看了这些效率的提高,在一个大规模并发的服务器中,轮询IO是最耗时间的操作之一.再回到那个例子中,如果每到来一个朋友楼管大妈都要全楼的查询同学,那么处理的效率必然就低下了,过不久楼底就有不少的人了. 对比最早给出的阻塞IO的处理模型, 可以看到采用了多路复用IO之后, 程序可以自由的进行自己除了IO操作之外的工作, 只有到IO状态发生变化的时候由多路复用IO进行通知, 然后再采取相应的操作, 而不用一直阻塞等待IO状态发生变化了. 从上面的分析也可以看出,epoll比select的提高实际上是一个用空间换时间思想的具体应用. 二、深入理解epoll的实现原理：开发高性能网络程序时，windows开发者们言必称iocp，linux开发者们则言必称epoll。大家都明白epoll是一种IO多路复用技术，可以非常高效的处理数以百万计的socket句柄，比起以前的select和poll效率高大发了。我们用起epoll来都感觉挺爽，确实快，那么，它到底为什么可以高速处理这么多并发连接呢？ 先简单回顾下如何使用C库封装的3个epoll系统调用吧。int epoll_create(int size); int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout); 使用起来很清晰，首先要调用epoll_create建立一个epoll对象。参数size是内核保证能够正确处理的最大句柄数，多于这个最大数时内核可不保证效果。 epoll_ctl可以操作上面建立的epoll，例如，将刚建立的socket加入到epoll中让其监控，或者把 epoll正在监控的某个socket句柄移出epoll，不再监控它等等。 epoll_wait在调用时，在给定的timeout时间内，当在监控的所有句柄中有事件发生时，就返回用户态的进程。 从上面的调用方式就可以看到epoll比select/poll的优越之处：因为后者每次调用时都要传递你所要监控的所有socket给select/poll系统调用，这意味着需要将用户态的socket列表copy到内核态，如果以万计的句柄会导致每次都要copy几十几百KB的内存到内核态，非常低效。而我们调用epoll_wait时就相当于以往调用select/poll，但是这时却不用传递socket句柄给内核，因为内核已经在epoll_ctl中拿到了要监控的句柄列表。 所以，实际上在你调用epoll_create后，内核就已经在内核态开始准备帮你存储要监控的句柄了，每次调用epoll_ctl只是在往内核的数据结构里塞入新的socket句柄。 在内核里，一切皆文件。所以，epoll向内核注册了一个文件系统，用于存储上述的被监控socket。当你调用epoll_create时，就会在这个虚拟的epoll文件系统里创建一个file结点。当然这个file不是普通文件，它只服务于epoll。epoll在被内核初始化时（操作系统启动），同时会开辟出epoll自己的内核高速cache区，用于安置每一个我们想监控的socket，这些socket会以红黑树的形式保存在内核cache里，以支持快速的查找、插入、删除。这个内核高速cache区，就是建立连续的物理内存页，然后在之上建立slab层，简单的说，就是物理上分配好你想要的size的内存对象，每次使用时都是使用空闲的已分配好的对象。static int __init eventpoll_init(void) { ... ... /* Allocates slab cache used to allocate "struct epitem" items */ epi_cache = kmem_cache_create("eventpoll_epi", sizeof(struct epitem), 0, SLAB_HWCACHE_ALIGN|EPI_SLAB_DEBUG|SLAB_PANIC, NULL, NULL); /* Allocates slab cache used to allocate "struct eppoll_entry" */ pwq_cache = kmem_cache_create("eventpoll_pwq", sizeof(struct eppoll_entry), 0, EPI_SLAB_DEBUG|SLAB_PANIC, NULL, NULL); ... ... epoll的高效就在于，当我们调用epoll_ctl往里塞入百万个句柄时，epoll_wait仍然可以飞快的返回，并有效的将发生事件的句柄给我们用户。这是由于我们在调用epoll_create时，内核除了帮我们在epoll文件系统里建了个file结点，在内核cache里建了个红黑树用于存储以后epoll_ctl传来的socket外，还会再建立一个list链表，用于存储准备就绪的事件，当epoll_wait调用时，仅仅观察这个list链表里有没有数据即可。有数据就返回，没有数据就sleep，等到timeout时间到后即使链表没数据也返回。所以，epoll_wait非常高效。 那么，这个准备就绪list链表是怎么维护的呢？当我们执行epoll_ctl时，除了把socket放到epoll文件系统里file对象对应的红黑树上之外，还会给内核中断处理程序注册一个回调函数，告诉内核，如果这个句柄的中断到了，就把它放到准备就绪list链表里。所以，当一个socket上有数据到了，内核在把网卡上的数据copy到内核中后就来把socket插入到准备就绪链表里了。 如此，一颗红黑树，一张准备就绪句柄链表，少量的内核cache，就帮我们解决了大并发下的socket处理问题。执行epoll_create时，创建了红黑树和就绪链表，执行epoll_ctl时，如果增加socket句柄，则检查在红黑树中是否存在，存在立即返回，不存在则添加到树干上，然后向内核注册回调函数，用于当中断事件来临时向准备就绪链表中插入数据。执行epoll_wait时立刻返回准备就绪链表里的数据即可。 最后看看epoll独有的两种模式LT和ET。无论是LT和ET模式，都适用于以上所说的流程。区别是，LT模式下，只要一个句柄上的事件一次没有处理完，会在以后调用epoll_wait时次次返回这个句柄，而ET模式仅在第一次返回。 这件事怎么做到的呢？当一个socket句柄上有事件时，内核会把该句柄插入上面所说的准备就绪list链表，这时我们调用epoll_wait，会把准备就绪的socket拷贝到用户态内存，然后清空准备就绪list链表，最后，epoll_wait干了件事，就是检查这些socket，如果不是ET模式（就是LT模式的句柄了），并且这些socket上确实有未处理的事件时，又把该句柄放回到刚刚清空的准备就绪链表了。所以，非ET的句柄，只要它上面还有事件，epoll_wait每次都会返回。而ET模式的句柄，除非有新中断到，即使socket上的事件没有处理完，也是不会次次从epoll_wait返回的。三、扩展阅读（epoll与之前其他相关技术的比较）： Linux提供了select、poll、epoll接口来实现IO复用，三者的原型如下所示，本文从参数、实现、性能等方面对三者进行对比。 int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); int poll(struct pollfd *fds, nfds_t nfds, int timeout); int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout); select、poll、epoll_wait参数及实现对比 1． select的第一个参数nfds为fdset集合中最大描述符值加1，fdset是一个位数组，其大小限制为__FD_SETSIZE（1024），位数组的每一位代表其对应的描述符是否需要被检查。 select的第二三四个参数表示需要关注读、写、错误事件的文件描述符位数组，这些参数既是输入参数也是输出参数，可能会被内核修改用于标示哪些描述符上发生了关注的事件。所以每次调用select前都需要重新初始化fdset。 timeout参数为超时时间，该结构会被内核修改，其值为超时剩余的时间。 select对应于内核中的sys_select调用，sys_select首先将第二三四个参数指向的fd_set拷贝到内核，然后对每个被SET的描述符调用进行poll，并记录在临时结果中（fdset），如果有事件发生，select会将临时结果写到用户空间并返回；当轮询一遍后没有任何事件发生时，如果指定了超时时间，则select会睡眠到超时，睡眠结束后再进行一次轮询，并将临时结果写到用户空间，然后返回。 select返回后，需要逐一检查关注的描述符是否被SET（事件是否发生）。 2． poll与select不同，通过一个pollfd数组向内核传递需要关注的事件，故没有描述符个数的限制，pollfd中的events字段和revents分别用于标示关注的事件和发生的事件，故pollfd数组只需要被初始化一次。 poll的实现机制与select类似，其对应内核中的sys_poll，只不过poll向内核传递pollfd数组，然后对pollfd中的每个描述符进行poll，相比处理fdset来说，poll效率更高。 poll返回后，需要对pollfd中的每个元素检查其revents值，来得指事件是否发生。 3． epoll通过epoll_create创建一个用于epoll轮询的描述符，通过epoll_ctl添加/修改/删除事件，通过epoll_wait检查事件，epoll_wait的第二个参数用于存放结果。 epoll与select、poll不同，首先，其不用每次调用都向内核拷贝事件描述信息，在第一次调用后，事件信息就会与对应的epoll描述符关联起来。另外epoll不是通过轮询，而是通过在等待的描述符上注册回调函数，当事件发生时，回调函数负责把发生的事件存储在就绪事件链表中，最后写到用户空间。

关于节点默认是红色还是黑色，可以通过给树中插入红色节点或者黑色节点对树造成的影响大小，而判断应该将节点的默认颜色设置为红色还是黑色。 根据红黑树的性质： 插入红色节点树的性质可能不会改变，而插入黑色节点每次都会违反性质4. 通过性质发现： 将节点设置为红色在插入时对红黑树造成的影响是小的，而黑色是最大的 总结：将红黑树的节点默认颜色设置为红色，是为尽可能减少在插入新节点对红黑树造成的影响。

原理性知识之所以重要，是相对于以后的编程，学习框架来说的。懂了原理的东西，学习框架就会轻松，还可以阅读懂源代码。

红黑树的原理是通过进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而实现关联数组，存储有序的数据。它是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，其典型的用途就是实现关联数组。红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树。而由于每一颗红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。行为特征红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：性质1、节点是红色或黑色。性质2、根节点是黑色。性质3、所有叶子都是黑色。（叶子是NUIL节点）性质4、每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）性质5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树的原理是通过进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而实现关联数组，存储有序的数据。它是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，其典型的用途就是实现关联数组。红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树。而由于每一颗红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。行为特征：红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：性质1、节点是红色或黑色。性质2、根节点是黑色。性质3、所有叶子都是黑色。（叶子是NUIL节点）。性质4、每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）。性质5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

性质1: 每个节点要么是 黑色 ,要么是 红色 。 性质2: 根节点是 黑色 。 性质3: 每个叶子节点(NIL)是黑色。 性质4: 每个 红色 节点的两个子节点一定都是 黑色 。 性质5: 任意一个节点到每个叶子节点的路径都包含 数量相同 的 黑节点 。俗称: 黑高 ! 从性质5又可以推出: 性质5.1: 如果一个节点存在黑子节点,那么该结点肯定有两个子节点。 插入操作包括两部分工作: 注意: 插入结点,必须为 红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。 最简单的一种情景,直接把插入结点作为根结点就行 注意: 根据红黑树性质2: 根结点是黑色。还需要把插入结点设为黑色。 处理: 更新当前结点的值,为插入结点的值 由于插入的结点是红色的,当插入结点的父结点为黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。 再次回想红黑树的性质2: 根结点是黑色。如果插入结点的父结点为 红结点 ,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这一点很重要,因为后序的旋转操作肯定需要祖父结点的参与。 依据红黑树 性质4可知,红色结点不能相连===>祖父结点肯定为黑结点 因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为: 红黑红 处理: 1.将P和U结点改为黑色 2.将PP改为红色 3.将PP设置为当前结点,进行后序处理 注意: 单纯从插入前来看,叔叔结点非红即空(NIL结点),否则的话破坏了红黑树性质5,此路径比其它路径多一个黑色结点。 处理: 处理: 该情景对应情景4.2,只是方向反转,直接看图 处理: 处理:

首先，我们必须理解一下，在C++ 中容器被定义为：在数据存储上，有一种对象类型，它可以持有其它对象或指向其它对像的指针，这种对象类型就叫做容器。很简单，容器就是保存其它对象的对象，当然这是一个朴素的理解，这种“对象”还包含了一系列处理“其它对象”的方法，因为这些方法在程序的设计上会经常被用到，所以容器也体现了一个好处，就是“容器类是一种对特定代码重用问题的良好的解决方案”。 容器还有另一个特点是容器可以自行扩展。在解决问题时我们常常不知道我们需要存储多少个对象，也就是说我们不知道应该创建多大的内存空间来保存我们的对象。显然，数组在这一方面也力不从心。容器的优势就在这里，它不需要你预先告诉它你要存储多少对象，只要你创建一个容器对象，并合理的调用它所提供的方法，所有的处理细节将由容器来自身完成。它可以为你申请内存或释放内存，并且用最优的算法来执行您的命令。 容器是随着面向对象语言的诞生而提出的，容器类在面向对象语言中特别重要，甚至它被认为是早期面向对象语言的基础。在现在几乎所有的面向对象的语言中也都伴随着一个容器集，在C++ 中，就是标准模板库（STL）。 和其它语言不一样，C++ 中处理容器是采用基于模板的方式。标准C++ 库中的容器提供了多种数据结构，这些数据结构可以与标准算法一起很好的工作，这为我们的软件开发提供了良好的支持！ 通用容器的分类 STL对定义的通用容器分三类：顺序性容器、关联式容器和容器适配器。 顺序性容器 是一种各元素之间有顺序关系的线性表，是一种线性结构的可序群集。顺序性容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。这个位置和元素本身无关，而和操作的时间和地点有关，顺序性容器不会根据元素的特点排序而是直接保存了元素操作时的逻辑顺序。比如我们一次性对一个顺序性容器追加三个元素，这三个元素在容器中的相对位置和追加时的逻辑次序是一致的。 关联式容器 和顺序性容器不一样，关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。但是关联式容器提供了另一种根据元素特点排序的功能，这样迭代器就能根据元素的特点“顺序地”获取元素。 关联式容器另一个显著的特点是它是以键值的方式来保存数据，就是说它能把关键字和值关联起来保存，而顺序性容器只能保存一种（可以认为它只保存关键字，也可以认为它只保存值）。这在下面具体的容器类中可以说明这一点。 容器适配器是一个比较抽象的概念， C++的解释是：适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器是让一种已存在的容器类型采用另一种不同的抽象类型的工作方式来实现的一种机制。其实仅是发生了接口转换。那么你可以把它理解为容器的容器，它实质还是一个容器，只是他不依赖于具体的标准容器类型，可以理解是容器的模版。或者把它理解为容器的接口，而适配器具体采用哪种容器类型去实现，在定义适配器的时候可以由你决定。 下表列出STL 定义的三类容器所包含的具体容器类： 标准容器类 特点顺序性容器 vector从后面快速的插入与删除，直接访问任何元素 deque从前面或后面快速的插入与删除，直接访问任何元素 list双链表，从任何地方快速插入与删除 关联容器 set快速查找，不允许重复值 multiset快速查找，允许重复值 map一对多映射，基于关键字快速查找，不允许重复值 multimap一对多映射，基于关键字快速查找，允许重复值 容器适配器 stack后进先出 queue先进先出 priority_queue最高优先级元素总是第一个出列 vector ,deque 和 list顺序性容器： 向量vector： 是一个线性顺序结构。相当于数组，但其大小可以不预先指定，并且自动扩展。它可以像数组一样被操作，由于它的特性我们完全可以将vector 看作动态数组。在创建一个vector 后，它会自动在内存中分配一块连续的内存空间进行数据存储，初始的空间大小可以预先指定也可以由vector 默认指定，这个大小即capacity（）函数的返回值。当存储的数据超过分配的空间时vector 会重新分配一块内存块，但这样的分配是很耗时的，在重新分配空间时它会做这样的动作： 首先，vector 会申请一块更大的内存块； 然后，将原来的数据拷贝到新的内存块中； 其次，销毁掉原内存块中的对象（调用对象的析构函数）； 最后，将原来的内存空间释放掉。 如果vector 保存的数据量很大时，这样的操作一定会导致糟糕的性能（这也是vector 被设计成比较容易拷贝的值类型的原因）。所以说vector 不是在什么情况下性能都好，只有在预先知道它大小的情况下vector 的性能才是最优的。 vector的特点：(1) 指定一块如同数组一样的连续存储，但空间可以动态扩展。即它可以像数组一样操作，并且可以进行动态操作。通常体现在push_back() pop_back()。(2) 随机访问方便，它像数组一样被访问，即支持[ ] 操作符和vector.at() (3) 节省空间，因为它是连续存储，在存储数据的区域都是没有被浪费的，但是要明确一点vector 大多情况下并不是满存的，在未存储的区域实际是浪费的。 (4) 在内部进行插入、删除操作效率非常低，这样的操作基本上是被禁止的。Vector 被设计成只能在后端进行追加和删除操作，其原因是vector 内部的实现是按照顺序表的原理。(5) 只能在vector 的最后进行push 和pop ，不能在vector 的头进行push 和pop。(6) 当动态添加的数据超过vector 默认分配的大小时要进行内存的重新分配、拷贝与释放，这个操作非常消耗性能。所以要vector 达到最优的性能，最好在创建vector 时就指定其空间大小。 双向链表list是一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。 由于其结构的原因，list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。 虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。 list的特点：(1) 不使用连续的内存空间这样可以随意地进行动态操作；(2) 可以在内部任何位置快速地插入或删除，当然也可以在两端进行push 和pop。(3) 不能进行内部的随机访问，即不支持[ ] 操作符和vector.at()；(4) 相对于verctor 占用更多的内存。 双端队列deque是一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问，但它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque 两端添加或删除元素的开销很小。它不需要重新分配空间，所以向末端增加元素比vector 更有效。 实际上，deque 是对vector 和list 优缺点的结合，它是处于两者之间的一种容器。 deque的特点：(1) 随机访问方便，即支持[ ] 操作符和vector.at() ，但性能没有vector 好；(2) 可以在内部进行插入和删除操作，但性能不及list；(3) 可以在两端进行push、pop；三者的比较 下图描述了vector、list、deque 在内存结构上的特点： vector是一段连续的内存块，而deque 是多个连续的内存块， list 是所有数据元素分开保存，可以是任何两个元素没有连续。 vector的查询性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效地随机存储。 list是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的，而查询性能非常差；适合大量地插入和删除操作而不关心随机存取的需求。deque是介于两者之间，它兼顾了数组和链表的优点，它是分块的链表和多个数组的联合。所以它有被list 好的查询性能，有被vector 好的插入、删除性能。如果你需要随即存取又关心两端数据的插入和删除，那么deque 是最佳之选。关联容器 set, multiset, map, multimap是一种非线性的树结构，具体的说采用的是一种比较高效的特殊的平衡检索二叉树—— 红黑树结构。（至于什么是红黑树，我也不太理解，只能理解到它是一种二叉树结构）因为关联容器的这四种容器类都使用同一原理，所以他们核心的算法是一致的，但是它们在应用上又有一些差别，先描述一下它们之间的差别。 set，又称集合，实际上就是一组元素的集合，但其中所包含的元素的值是唯一的，且是按一定顺序排列的，集合中的每个元素被称作集合中的实例。因为其内部是通过链表的方式来组织，所以在插入的时候比vector 快，但在查找和末尾添加上被vector 慢。 multiset，是多重集合，其实现方式和set 是相似的，只是它不要求集合中的元素是唯一的，也就是说集合中的同一个元素可以出现多次。map，提供一种“键- 值”关系的一对一的数据存储能力。其“键”在容器中不可重复，且按一定顺序排列（其实我们可以将set 也看成是一种键- 值关系的存储，只是它只有键没有值。它是map 的一种特殊形式）。由于其是按链表的方式存储，它也继承了链表的优缺点。 multimap，和map 的原理基本相似，它允许“键”在容器中可以不唯一。关联容器的特点是明显的，相对于顺序容器，有以下几个主要特点： 1，其内部实现是采用非线性的二叉树结构，具体的说是红黑树的结构原理实现的； 2，set和map 保证了元素的唯一性，mulset 和mulmap 扩展了这一属性，可以允许元素不唯一； 3，元素是有序的集合，默认在插入的时候按升序排列。 基于以上特点， 1，关联容器对元素的插入和删除操作比vector 要快，因为vector 是顺序存储，而关联容器是链式存储；比list 要慢，是因为即使它们同是链式结构，但list 是线性的，而关联容器是二叉树结构，其改变一个元素涉及到其它元素的变动比list 要多，并且它是排序的，每次插入和删除都需要对元素重新排序； 2，关联容器对元素的检索操作比vector 慢，但是比list 要快很多。vector 是顺序的连续存储，当然是比不上的，但相对链式的list 要快很多是因为list 是逐个搜索，它搜索的时间是跟容器的大小成正比，而关联容器查找的复杂度基本是Log(N) ，比如如果有1000 个记录，最多查找10 次，1,000,000 个记录，最多查找20 次。容器越大，关联容器相对list 的优越性就越能体现；3，在使用上set 区别于vector,deque,list 的最大特点就是set 是内部排序的，这在查询上虽然逊色于vector ，但是却大大的强于list。 4，在使用上map 的功能是不可取代的，它保存了“键- 值”关系的数据，而这种键值关系采用了类数组的方式。数组是用数字类型的下标来索引元素的位置，而map 是用字符型关键字来索引元素的位置。在使用上map 也提供了一种类数组操作的方式，即它可以通过下标来检索数据，这是其他容器做不到的，当然也包括set。（STL 中只有vector 和map 可以通过类数组的方式操作元素，即如同ele[1] 方式）容器适配器 STL中包含三种适配器：栈stack 、队列queue 和优先级priority_queue。 适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。 STL中提供的三种适配器可以由某一种顺序容器去实现。默认下stack 和queue 基于deque 容器实现，priority_queue 则基于vector 容器实现。当然在创建一个适配器时也可以指定具体的实现容器，创建适配器时在第二个参数上指定具体的顺序容器可以覆盖适配器的默认实现。 由于适配器的特点，一个适配器不是可以由任一个顺序容器都可以实现的。

HashMap 散列 线程不安全HashTable 由hashmap实现 有linklist 且线程安全ConcurrentHashMap 分段式锁机制的线程安全的Map单独业务 没有共享竞争 HashMap单独业务 并发不大 并对数据先后顺序有要求 可采用 HashTable高并发ConcurrentHashMap

是否是使用了第三方的锁屏程序导致，建议您可以使用自带的锁屏后对比；

以一个生活中的例子来解释.假设你在大学中读书,要等待一个朋友来访,而这个朋友只知道你在A号楼,但是不知道你具体住在哪里,于是你们约好了在A号楼门口见面.如果你使用的阻塞IO模型来处理这个问题,那么你就只能一直守候在A号楼门口等待朋友的到来,在这段时间里你不能做别的事情,不难知道,这种方式的效率是低下的.进一步解释select和epoll模型的差异.select版大妈做的是如下的事情:比如同学甲的朋友来了,select版大妈比较笨,她带着朋友挨个房间进行查询谁是同学甲,你等的朋友来了,于是在实际的代码中,select版大妈做的是以下的事情:int n = select(&readset,NULL,NULL,100); for (int i = 0; n > 0; ++i) { if (FD_ISSET(fdarray[i], &readset)) { do_something(fdarray[i]); --n; } }epoll版大妈就比较先进了,她记下了同学甲的信息,比如说他的房间号,那么等同学甲的朋友到来时,只需要告诉该朋友同学甲在哪个房间即可,不用自己亲自带着人满大楼的找人了.于是epoll版大妈做的事情可以用如下的代码表示:n = epoll_wait(epfd,events,20,500); for(i=0;i<n;++i) { do_something(events[n]); } 在epoll中,关键的数据结构epoll_event定义如下:typedef union epoll_data { void *ptr; int fd; __uint32_t u32; __uint64_t u64; } epoll_data_t; struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */ }; 可以看到,epoll_data是一个union结构体,它就是epoll版大妈用于保存同学信息的结构体,它可以保存很多类型的信息:fd,指针,等等.有了这个结构体,epoll大妈可以不用吹灰之力就可以定位到同学甲.别小看了这些效率的提高,在一个大规模并发的服务器中,轮询IO是最耗时间的操作之一.再回到那个例子中,如果每到来一个朋友楼管大妈都要全楼的查询同学,那么处理的效率必然就低下了,过不久楼底就有不少的人了.对比最早给出的阻塞IO的处理模型, 可以看到采用了多路复用IO之后, 程序可以自由的进行自己除了IO操作之外的工作, 只有到IO状态发生变化的时候由多路复用IO进行通知, 然后再采取相应的操作, 而不用一直阻塞等待IO状态发生变化了.从上面的分析也可以看出,epoll比select的提高实际上是一个用空间换时间思想的具体应用.二、深入理解epoll的实现原理：开发高性能网络程序时，windows开发者们言必称iocp，linux开发者们则言必称epoll。大家都明白epoll是一种IO多路复用技术，可以非常高效的处理数以百万计的socket句柄，比起以前的select和poll效率高大发了。我们用起epoll来都感觉挺爽，确实快，那么，它到底为什么可以高速处理这么多并发连接呢？ 先简单回顾下如何使用C库封装的3个epoll系统调用吧。int epoll_create(int size); int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout); 使用起来很清晰，首先要调用epoll_create建立一个epoll对象。参数size是内核保证能够正确处理的最大句柄数，多于这个最大数时内核可不保证效果。epoll_ctl可以操作上面建立的epoll，例如，将刚建立的socket加入到epoll中让其监控，或者把 epoll正在监控的某个socket句柄移出epoll，不再监控它等等。epoll_wait在调用时，在给定的timeout时间内，当在监控的所有句柄中有事件发生时，就返回用户态的进程。从上面的调用方式就可以看到epoll比select/poll的优越之处：因为后者每次调用时都要传递你所要监控的所有socket给select/poll系统调用，这意味着需要将用户态的socket列表copy到内核态，如果以万计的句柄会导致每次都要copy几十几百KB的内存到内核态，非常低效。而我们调用epoll_wait时就相当于以往调用select/poll，但是这时却不用传递socket句柄给内核，因为内核已经在epoll_ctl中拿到了要监控的句柄列表。所以，实际上在你调用epoll_create后，内核就已经在内核态开始准备帮你存储要监控的句柄了，每次调用epoll_ctl只是在往内核的数据结构里塞入新的socket句柄。在内核里，一切皆文件。所以，epoll向内核注册了一个文件系统，用于存储上述的被监控socket。当你调用epoll_create时，就会在这个虚拟的epoll文件系统里创建一个file结点。当然这个file不是普通文件，它只服务于epoll。epoll在被内核初始化时（操作系统启动），同时会开辟出epoll自己的内核高速cache区，用于安置每一个我们想监控的socket，这些socket会以红黑树的形式保存在内核cache里，以支持快速的查找、插入、删除。这个内核高速cache区，就是建立连续的物理内存页，然后在之上建立slab层，简单的说，就是物理上分配好你想要的size的内存对象，每次使用时都是使用空闲的已分配好的对象。static int __init eventpoll_init(void) { ... ... /* Allocates slab cache used to allocate "struct epitem" items */ epi_cache = kmem_cache_create("eventpoll_epi", sizeof(struct epitem), 0, SLAB_HWCACHE_ALIGN|EPI_SLAB_DEBUG|SLAB_PANIC, NULL, NULL); /* Allocates slab cache used to allocate "struct eppoll_entry" */ pwq_cache = kmem_cache_create("eventpoll_pwq", sizeof(struct eppoll_entry), 0, EPI_SLAB_DEBUG|SLAB_PANIC, NULL, NULL); ... ... epoll的高效就在于，当我们调用epoll_ctl往里塞入百万个句柄时，epoll_wait仍然可以飞快的返回，并有效的将发生事件的句柄给我们用户。这是由于我们在调用epoll_create时，内核除了帮我们在epoll文件系统里建了个file结点，在内核cache里建了个红黑树用于存储以后epoll_ctl传来的socket外，还会再建立一个list链表，用于存储准备就绪的事件，当epoll_wait调用时，仅仅观察这个list链表里有没有数据即可。有数据就返回，没有数据就sleep，等到timeout时间到后即使链表没数据也返回。所以，epoll_wait非常高效。那么，这个准备就绪list链表是怎么维护的呢？当我们执行epoll_ctl时，除了把socket放到epoll文件系统里file对象对应的红黑树上之外，还会给内核中断处理程序注册一个回调函数，告诉内核，如果这个句柄的中断到了，就把它放到准备就绪list链表里。所以，当一个socket上有数据到了，内核在把网卡上的数据copy到内核中后就来把socket插入到准备就绪链表里了。如此，一颗红黑树，一张准备就绪句柄链表，少量的内核cache，就帮我们解决了大并发下的socket处理问题。执行epoll_create时，创建了红黑树和就绪链表，执行epoll_ctl时，如果增加socket句柄，则检查在红黑树中是否存在，存在立即返回，不存在则添加到树干上，然后向内核注册回调函数，用于当中断事件来临时向准备就绪链表中插入数据。执行epoll_wait时立刻返回准备就绪链表里的数据即可。最后看看epoll独有的两种模式LT和ET。无论是LT和ET模式，都适用于以上所说的流程。区别是，LT模式下，只要一个句柄上的事件一次没有处理完，会在以后调用epoll_wait时次次返回这个句柄，而ET模式仅在第一次返回。这件事怎么做到的呢？当一个socket句柄上有事件时，内核会把该句柄插入上面所说的准备就绪list链表，这时我们调用epoll_wait，会把准备就绪的socket拷贝到用户态内存，然后清空准备就绪list链表，最后，epoll_wait干了件事，就是检查这些socket，如果不是ET模式（就是LT模式的句柄了），并且这些socket上确实有未处理的事件时，又把该句柄放回到刚刚清空的准备就绪链表了。所以，非ET的句柄，只要它上面还有事件，epoll_wait每次都会返回。而ET模式的句柄，除非有新中断到，即使socket上的事件没有处理完，也是不会次次从epoll_wait返回的。三、扩展阅读（epoll与之前其他相关技术的比较）： Linux提供了select、poll、epoll接口来实现IO复用，三者的原型如下所示，本文从参数、实现、性能等方面对三者进行对比。 int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); int poll(struct pollfd *fds, nfds_t nfds, int timeout); int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout); select、poll、epoll_wait参数及实现对比 1． select的第一个参数nfds为fdset集合中最大描述符值加1，fdset是一个位数组，其大小限制为__FD_SETSIZE（1024），位数组的每一位代表其对应的描述符是否需要被检查。 select的第二三四个参数表示需要关注读、写、错误事件的文件描述符位数组，这些参数既是输入参数也是输出参数，可能会被内核修改用于标示哪些描述符上发生了关注的事件。所以每次调用select前都需要重新初始化fdset。 timeout参数为超时时间，该结构会被内核修改，其值为超时剩余的时间。 select对应于内核中的sys_select调用，sys_select首先将第二三四个参数指向的fd_set拷贝到内核，然后对每个被SET的描述符调用进行poll，并记录在临时结果中（fdset），如果有事件发生，select会将临时结果写到用户空间并返回；当轮询一遍后没有任何事件发生时，如果指定了超时时间，则select会睡眠到超时，睡眠结束后再进行一次轮询，并将临时结果写到用户空间，然后返回。 select返回后，需要逐一检查关注的描述符是否被SET（事件是否发生）。 2． poll与select不同，通过一个pollfd数组向内核传递需要关注的事件，故没有描述符个数的限制，pollfd中的events字段和revents分别用于标示关注的事件和发生的事件，故pollfd数组只需要被初始化一次。 poll的实现机制与select类似，其对应内核中的sys_poll，只不过poll向内核传递pollfd数组，然后对pollfd中的每个描述符进行poll，相比处理fdset来说，poll效率更高。 poll返回后，需要对pollfd中的每个元素检查其revents值，来得指事件是否发生。 3． epoll通过epoll_create创建一个用于epoll轮询的描述符，通过epoll_ctl添加/修改/删除事件，通过epoll_wait检查事件，epoll_wait的第二个参数用于存放结果。 epoll与select、poll不同，首先，其不用每次调用都向内核拷贝事件描述信息，在第一次调用后，事件信息就会与对应的epoll描述符关联起来。另外epoll不是通过轮询，而是通过在等待的描述符上注册回调函数，当事件发生时，回调函数负责把发生的事件存储在就绪事件链表中，最后写到用户空间。

不靠。计算机考研408数据结构考试内容是计算机组成原理、操作系统等，红黑树是一种特殊形式的平衡二叉搜索树，根据查询相关资料，2022年08考纲的修订，平衡树、红黑树、外部排序等都不被列入考核中，所以不会考红黑树。

第1章绪论11.1数据与数据结构21.1.1数据及其类型21.1.2数据结构简介41.2算法61.2.1算法的概念61.2.2算法的分析81.2.3算法的设计121.3C++语言简介181.3.1C++的产生与发展181.3.2C++与面向对象思想201.3.3C++中的类和对象231.4本章小结28第2章C++编程基础292.1开始C++编程302.1.1输入输出302.1.2预处理382.1.3名字空间442.2深入的类编程502.2.1访问控制502.2.2初始化与清除532.2.3动态创建对象572.2.4友元函数602.2.5拷贝构造函数612.3丰富的C++特性652.3.1常量652.3.2函数重载682.3.3运算符重载712.3.4异常处理772.4代码重用机制792.4.1继承802.4.2多态872.4.3模板902.5标准模板库932.5.1STL简介942.5.2STL构成952.5.3STL的不同版本972.6本章小结98第3章指针、数组与字符串993.1指针1003.1.1指针的概念1003.1.2指针的语法1023.1.3函数与参数传递1033.2数组1083.2.1数组定义与初始化1093.2.2数组与指针1133.2.3数组的抽象数据类型1163.2.4大整数乘法问题1203.2.5荷兰国旗问题1213.3字符串1243.3.1C++中的字符串1243.3.2字符串抽象数据类型1263.3.3字符串的匹配算法1283.3.4字符串指数问题1413.4动态内存管理1423.4.1关键词new和delete1433.4.2避免内存错误1463.5本章小结152第4章链表1534.1单向链表1544.1.1单向链表的结构1544.1.2单向链表类的实现1554.1.3有序链表的合并1624.1.4多项式加法问题1634.2单向循环链表1644.2.1单向循环链表的结构1644.2.2单向循环链表类的实现1664.2.3约瑟夫问题1694.2.4魔术师发牌问题1704.2.5拉丁方阵问题1724.3双向循环链表1734.3.1双向循环链表的结构1734.3.2双向循环链表类的实现1744.3.3Vigenere加密问题1824.3.4选美比赛问题1844.4游标类的设计与实现1864.4.1游标类的结构1864.4.2游标类的实现1874.5STL与链表1914.5.1STL中链表类的接口1914.5.2遍历1944.5.3元素的插入与删除1964.6本章小结196第5章栈与队列1975.1栈1985.1.1栈的结构1985.1.2栈的实现1995.1.3括号匹配问题2035.1.4停车场模拟问题2045.2队列2085.2.1队列的结构2085.2.2队列的实现2105.2.3舞伴问题2145.2.4杨辉三角形问题2155.2.5游程编码问题2165.3优先级队列2185.3.1优先级队列的结构2185.3.2优先级队列的实现2205.4STL中的栈与队列2225.4.1STL中的stack2225.4.2STL中的queue2245.4.3STL中的priority_queue2265.5本章小结229第6章递归2316.1递归的概念2326.1.1递归的定义2326.1.2应用递归的原则2356.1.3递归和非递归的转化2406.2分治法2436.2.1分治法简述2436.2.2汉诺塔问题2446.2.3传染病问题2466.3回溯法2506.3.1回溯法简述2516.3.2迷宫问题2516.3.3八皇后问题2556.3.4骑士周游问题2586.4本章小结265第7章树2677.1树的概念2687.1.1树的定义2687.1.2树的术语2717.1.3树的抽象数据类型2727.2二叉树2737.2.1二叉树的定义2737.2.2二叉树的性质2757.2.3二叉树的实现2767.2.4二叉树的遍历2857.2.5二叉树的线索化2897.3树与森林2917.3.1树的存储表示2917.3.2树的实现2947.3.3树与森林的遍历2987.3.4森林与二叉树的转换3007.4霍夫曼树3047.4.1霍夫曼树的概念3047.4.2霍夫曼树的构造方法3057.4.3霍夫曼编码及其实现3077.5堆3137.5.1堆的概念3147.5.2堆的建立3147.5.3堆的操作3167.6基于STL实现树结构3177.6.1STL中的vector3177.6.2STL中的map3217.7医院建模问题3237.8本章小结328第8章图3298.1图的基本概念3308.1.1图的定义3308.1.2图的术语3318.1.3图的运算3348.1.4图的抽象数据类型3368.2图的存储与表示3378.2.1图的邻接矩阵表示3378.2.2图的邻接表表示3398.2.3两种表示法的比较3428.3图的遍历3428.3.1欧拉路径与欧拉回路3438.3.2哈密尔顿路径与哈密尔顿回路3458.3.3广度优先遍历3468.3.4深度优先遍历3498.4最短路径问题3538.4.1固定起点最短路问题3538.4.2非固定起点最短路问题3558.4.3最短路径的动态规划解法3588.4.4旅游交通路线问题3648.5最小生成树3728.5.1最小生成树的定义3728.5.2克鲁斯卡尔算法3738.5.3普里姆算法3758.6经典问题举例3798.6.1文字游戏问题3808.6.2道路修建问题3828.6.3回家路线问题3858.6.4水塘计算问题3878.6.5棍子还原问题3898.7本章小结392第9章树形搜索结构3939.1二叉搜索树3949.1.1二叉搜索树的概念3949.1.2二叉搜索树的操作3959.1.3二叉搜索树的实现3979.1.4二叉搜索树的分析4009.2AVL树4039.2.1AVL树的概念4049.2.2AVL树的旋转4059.2.3AVL树的实现4109.3红黑树4189.3.1红黑树的概念4189.3.2红黑树的操作4219.3.3红黑树的实现4289.4Trie树4339.4.1Trie树的概念4339.4.2Trie树的表示4349.4.3Trie树的实现4359.5本章小结439第10章集合与字典44110.1集合论基础44210.1.1集合的概念44210.1.2集合的运算44410.2集合的实现44510.2.1位向量集合44510.2.2链表集合45110.3字典46010.3.1字典的概念46110.3.2搜索运算46310.4散列46710.4.1散列的概念46710.4.2散列函数46910.4.3处理散列冲突47110.4.4散列的应用47510.5经典问题举例47610.5.1拼写检查问题47610.5.2无线网络问题48510.5.3第K个数问题48810.6STL中的set49010.7本章小结493第11章排序49511.1排序问题概述49611.1.1基本概念和定义49611.1.2排序算法的分类49711.1.3排序算法分析与选择49711.2插入排序49811.2.1直接插入排序49811.2.2二分法插入排序50111.2.3希尔排序50311.3选择排序50611.3.1直接选择排序50611.3.2堆排序50811.4交换排序51211.4.1冒泡法排序51211.4.2Shaker排序51411.4.3快速排序51711.5归并排序52211.6计数排序52611.7本章小结531参考文献533……

二叉树没有度为1的点，至少情况应该如下（除根节点外每一层都是两个结点）o/oo/oo根据上述二叉树情况，其结点数公式为2h-1所以本题至少有2h-1个结点

前言：本文主要讲解Linux IO调度层的三种模式：cfp、deadline和noop，并给出各自的优化和适用场景建议。IO调度发生在Linux内核的IO调度层。这个层次是针对Linux的整体IO层次体系来说的。从read()或者write()系统调用的角度来说，Linux整体IO体系可以分为七层，它们分别是：VFS层： 虚拟文件系统层。由于内核要跟多种文件系统打交道，而每一种文件系统所实现的数据结构和相关方法都可能不尽相同，所以，内核抽象了这一层，专门用来适配各种文件系统，并对外提供统一操作接口。文件系统层： 不同的文件系统实现自己的操作过程，提供自己特有的特征，具体不多说了，大家愿意的话自己去看代码即可。页缓存层： 负责真对page的缓存。通用块层： 由于绝大多数情况的io操作是跟块设备打交道，所以Linux在此提供了一个类似vfs层的块设备操作抽象层。下层对接各种不同属性的块设备，对上提供统一的Block IO请求标准。IO调度层 ：因为绝大多数的块设备都是类似磁盘这样的设备，所以有必要根据这类设备的特点以及应用的不同特点来设置一些不同的调度算法和队列。以便在不同的应用环境下有针对性的提高磁盘的读写效率，这里就是大名鼎鼎的Linux电梯所起作用的地方。针对机械硬盘的各种调度方法就是在这实现的。块设备驱动层： 驱动层对外提供相对比较高级的设备操作接口，往往是C语言的，而下层对接设备本身的操作方法和规范。块设备层： 这层就是具体的物理设备了，定义了各种真对设备操作方法和规范。有一个已经整理好的[Linux IO结构图]，非常经典，一图胜千言：我们今天要研究的内容主要在IO调度这一层。它要解决的核心问题是，如何提高块设备IO的整体性能？这一层也主要是针对机械硬盘结构而设计的。众所周知，机械硬盘的存储介质是磁盘，磁头在盘片上移动进行磁道寻址，行为类似播放一张唱片。这种结构的特点是，顺序访问时吞吐量较高，但是如果一旦对盘片有随机访问，那么大量的时间都会浪费在磁头的移动上，这时候就会导致每次IO的响应时间变长，极大的降低IO的响应速度。磁头在盘片上寻道的操作，类似电梯调度，实际上在最开始的时期，Linux把这个算法命名为Linux电梯算法，即：如果在寻道的过程中，能把顺序路过的相关磁道的数据请求都“顺便”处理掉，那么就可以在比较小影响响应速度的前提下，提高整体IO的吞吐量。这就是我们为什么要设计IO调度算法的原因。目前在内核中默认开启了三种算法/模式：noop，cfq和deadline。严格算应该是两种：因为第一种叫做noop，就是空操作调度算法，也就是没有任何调度操作，并不对io请求进行排序，仅仅做适当的io合并的一个fifo队列。目前内核中默认的调度算法应该是cfq，叫做完全公平队列调度。这个调度算法人如其名，它试图给所有进程提供一个完全公平的IO操作环境。注：请大家一定记住这个词语，cfq，完全公平队列调度，不然下文就没法看了。cfq为每个进程创建一个同步IO调度队列，并默认以时间片和请求数限定的方式分配IO资源，以此保证每个进程的IO资源占用是公平的，cfq还实现了针对进程级别的优先级调度，这个我们后面会详细解释。查看和修改IO调度算法的方法是：cfq是通用服务器比较好的IO调度算法选择，对桌面用户也是比较好的选择。但是对于很多IO压力较大的场景就并不是很适应，尤其是IO压力集中在某些进程上的场景。因为这种场景我们需要更多的满足某个或者某几个进程的IO响应速度，而不是让所有的进程公平的使用IO，比如数据库应用。deadline调度（最终期限调度）就是更适合上述场景的解决方案。deadline实现了四个队列：其中两个分别处理正常read和write，按扇区号排序，进行正常io的合并处理以提高吞吐量。因为IO请求可能会集中在某些磁盘位置，这样会导致新来的请求一直被合并，可能会有其他磁盘位置的io请求被饿死。另外两个处理超时read和write的队列，按请求创建时间排序，如果有超时的请求出现，就放进这两个队列，调度算法保证超时（达到最终期限时间）的队列中的请求会优先被处理，防止请求被饿死。不久前，内核还是默认标配四种算法，还有一种叫做as的算法（Anticipatory scheduler），预测调度算法。一个高大上的名字，搞得我一度认为Linux内核都会算命了。结果发现，无非是在基于deadline算法做io调度的之前等一小会时间，如果这段时间内有可以合并的io请求到来，就可以合并处理，提高deadline调度的在顺序读写情况下的数据吞吐量。其实这根本不是啥预测，我觉得不如叫撞大运调度算法，当然这种策略在某些特定场景差效果不错。但是在大多数场景下，这个调度不仅没有提高吞吐量，还降低了响应速度，所以内核干脆把它从默认配置里删除了。毕竟Linux的宗旨是实用，而我们也就不再这个调度算法上多费口舌了。1、cfq：完全公平队列调度cfq是内核默认选择的IO调度队列，它在桌面应用场景以及大多数常见应用场景下都是很好的选择。如何实现一个所谓的完全公平队列（Completely Fair Queueing）？首先我们要理解所谓的公平是对谁的公平？从操作系统的角度来说，产生操作行为的主体都是进程，所以这里的公平是针对每个进程而言的，我们要试图让进程可以公平的占用IO资源。那么如何让进程公平的占用IO资源？我们需要先理解什么是IO资源。当我们衡量一个IO资源的时候，一般喜欢用的是两个单位，一个是数据读写的带宽，另一个是数据读写的IOPS。带宽就是以时间为单位的读写数据量，比如，100Mbyte/s。而IOPS是以时间为单位的读写次数。在不同的读写情境下，这两个单位的表现可能不一样，但是可以确定的是，两个单位的任何一个达到了性能上限，都会成为IO的瓶颈。从机械硬盘的结构考虑，如果读写是顺序读写，那么IO的表现是可以通过比较少的IOPS达到较大的带宽，因为可以合并很多IO，也可以通过预读等方式加速数据读取效率。当IO的表现是偏向于随机读写的时候，那么IOPS就会变得更大，IO的请求的合并可能性下降，当每次io请求数据越少的时候，带宽表现就会越低。从这里我们可以理解，针对进程的IO资源的主要表现形式有两个： 进程在单位时间内提交的IO请求个数和进程占用IO的带宽。其实无论哪个，都是跟进程分配的IO处理时间长度紧密相关的。有时业务可以在较少IOPS的情况下占用较大带宽，另外一些则可能在较大IOPS的情况下占用较少带宽，所以对进程占用IO的时间进行调度才是相对最公平的。即，我不管你是IOPS高还是带宽占用高，到了时间咱就换下一个进程处理，你爱咋样咋样。所以，cfq就是试图给所有进程分配等同的块设备使用的时间片，进程在时间片内，可以将产生的IO请求提交给块设备进行处理，时间片结束，进程的请求将排进它自己的队列，等待下次调度的时候进行处理。这就是cfq的基本原理。当然，现实生活中不可能有真正的“公平”，常见的应用场景下，我们很肯能需要人为的对进程的IO占用进行人为指定优先级，这就像对进程的CPU占用设置优先级的概念一样。所以，除了针对时间片进行公平队列调度外，cfq还提供了优先级支持。每个进程都可以设置一个IO优先级，cfq会根据这个优先级的设置情况作为调度时的重要参考因素。优先级首先分成三大类：RT、BE、IDLE，它们分别是实时（Real Time）、最佳效果（Best Try）和闲置（Idle）三个类别，对每个类别的IO，cfq都使用不同的策略进行处理。另外，RT和BE类别中，分别又再划分了8个子优先级实现更细节的QOS需求，而IDLE只有一个子优先级。另外，我们都知道内核默认对存储的读写都是经过缓存（buffer/cache）的，在这种情况下，cfq是无法区分当前处理的请求是来自哪一个进程的。只有在进程使用同步方式（sync read或者sync wirte）或者直接IO（Direct IO）方式进行读写的时候，cfq才能区分出IO请求来自哪个进程。所以，除了针对每个进程实现的IO队列以外，还实现了一个公共的队列用来处理异步请求。当前内核已经实现了针对IO资源的cgroup资源隔离，所以在以上体系的基础上，cfq也实现了针对cgroup的调度支持。总的来说，cfq用了一系列的数据结构实现了以上所有复杂功能的支持，大家可以通过源代码看到其相关实现，文件在源代码目录下的block/cfq-iosched.c。1.1 cfq设计原理在此，我们对整体数据结构做一个简要描述：首先，cfq通过一个叫做cfq_data的数据结构维护了整个调度器流程。在一个支持了cgroup功能的cfq中，全部进程被分成了若干个contral group进行管理。每个cgroup在cfq中都有一个cfq_group的结构进行描述，所有的cgroup都被作为一个调度对象放进一个红黑树中，并以vdisktime为key进行排序。vdisktime这个时间纪录的是当前cgroup所占用的io时间，每次对cgroup进行调度时，总是通过红黑树选择当前vdisktime时间最少的cgroup进行处理，以保证所有cgroups之间的IO资源占用“公平”。当然我们知道，cgroup是可以对blkio进行资源比例分配的，其作用原理就是，分配比例大的cgroup占用vdisktime时间增长较慢，分配比例小的vdisktime时间增长较快，快慢与分配比例成正比。这样就做到了不同的cgroup分配的IO比例不一样，并且在cfq的角度看来依然是“公平“的。选择好了需要处理的cgroup（cfq_group）之后，调度器需要决策选择下一步的service_tree。service_tree这个数据结构对应的都是一系列的红黑树，主要目的是用来实现请求优先级分类的，就是RT、BE、IDLE的分类。每一个cfq_group都维护了7个service_trees，其定义如下：其中service_tree_idle就是用来给IDLE类型的请求进行排队用的红黑树。而上面二维数组，首先第一个维度针对RT和BE分别各实现了一个数组，每一个数组中都维护了三个红黑树，分别对应三种不同子类型的请求，分别是：SYNC、SYNC_NOIDLE以及ASYNC。我们可以认为SYNC相当于SYNC_IDLE并与SYNC_NOIDLE对应。idling是cfq在设计上为了尽量合并连续的IO请求以达到提高吞吐量的目的而加入的机制，我们可以理解为是一种“空转”等待机制。空转是指，当一个队列处理一个请求结束后，会在发生调度之前空等一小会时间，如果下一个请求到来，则可以减少磁头寻址，继续处理顺序的IO请求。为了实现这个功能，cfq在service_tree这层数据结构这实现了SYNC队列，如果请求是同步顺序请求，就入队这个service tree，如果请求是同步随机请求，则入队SYNC_NOIDLE队列，以判断下一个请求是否是顺序请求。所有的异步写操作请求将入队ASYNC的service tree，并且针对这个队列没有空转等待机制。此外，cfq还对SSD这样的硬盘有特殊调整，当cfq发现存储设备是一个ssd硬盘这样的队列深度更大的设备时，所有针对单独队列的空转都将不生效，所有的IO请求都将入队SYNC_NOIDLE这个service tree。每一个service tree都对应了若干个cfq_queue队列，每个cfq_queue队列对应一个进程，这个我们后续再详细说明。cfq_group还维护了一个在cgroup内部所有进程公用的异步IO请求队列，其结构如下：异步请求也分成了RT、BE、IDLE这三类进行处理，每一类对应一个cfq_queue进行排队。BE和RT也实现了优先级的支持，每一个类型有IOPRIO_BE_NR这么多个优先级，这个值定义为8，数组下标为0-7。我们目前分析的内核代码版本为Linux 4.4，可以看出，从cfq的角度来说，已经可以实现异步IO的cgroup支持了，我们需要定义一下这里所谓异步IO的含义，它仅仅表示从内存的buffer/cache中的数据同步到硬盘的IO请求，而不是aio(man 7 aio)或者linux的native异步io以及libaio机制，实际上这些所谓的“异步”IO机制，在内核中都是同步实现的（本质上冯诺伊曼计算机没有真正的“异步”机制）。我们在上面已经说明过，由于进程正常情况下都是将数据先写入buffer/cache，所以这种异步IO都是统一由cfq_group中的async请求队列处理的。那么为什么在上面的service_tree中还要实现和一个ASYNC的类型呢？这当然是为了支持区分进程的异步IO并使之可以“完全公平”做准备喽。实际上在最新的cgroup v2的blkio体系中，内核已经支持了针对buffer IO的cgroup限速支持，而以上这些可能容易混淆的一堆类型，都是在新的体系下需要用到的类型标记。新体系的复杂度更高了，功能也更加强大，但是大家先不要着急，正式的cgroup v2体系，在Linux 4.5发布的时候会正式跟大家见面。我们继续选择service_tree的过程，三种优先级类型的service_tree的选择就是根据类型的优先级来做选择的，RT优先级最高，BE其次，IDLE最低。就是说，RT里有，就会一直处理RT，RT没了再处理BE。每个service_tree对应一个元素为cfq_queue排队的红黑树，而每个cfq_queue就是内核为进程（线程）创建的请求队列。每一个cfq_queue都会维护一个rb_key的变量，这个变量实际上就是这个队列的IO服务时间（service time）。这里还是通过红黑树找到service time时间最短的那个cfq_queue进行服务，以保证“完全公平”。选择好了cfq_queue之后，就要开始处理这个队列里的IO请求了。这里的调度方式基本跟deadline类似。cfq_queue会对进入队列的每一个请求进行两次入队，一个放进fifo中，另一个放进按访问扇区顺序作为key的红黑树中。默认从红黑树中取请求进行处理，当请求的延时时间达到deadline时，就从红黑树中取等待时间最长的进行处理，以保证请求不被饿死。这就是整个cfq的调度流程，当然其中还有很多细枝末节没有交代，比如合并处理以及顺序处理等等。1.2 cfq的参数调整理解整个调度流程有助于我们决策如何调整cfq的相关参数。所有cfq的可调参数都可以在/sys/class/block/sda/queue/iosched/目录下找到，当然，在你的系统上，请将sda替换为相应的磁盘名称。我们来看一下都有什么：这些参数部分是跟机械硬盘磁头寻道方式有关的，如果其说明你看不懂，请先补充相关知识：back_seek_max:磁头可以向后寻址的最大范围，默认值为16M。back_seek_penalty:向后寻址的惩罚系数。这个值是跟向前寻址进行比较的。以上两个是为了防止磁头寻道发生抖动而导致寻址过慢而设置的。基本思路是这样，一个io请求到来的时候，cfq会根据其寻址位置预估一下其磁头寻道成本。设置一个最大值back_seek_max，对于请求所访问的扇区号在磁头后方的请求，只要寻址范围没有超过这个值，cfq会像向前寻址的请求一样处理它。再设置一个评估成本的系数back_seek_penalty，相对于磁头向前寻址，向后寻址的距离为1/2(1/back_seek_penalty)时，cfq认为这两个请求寻址的代价是相同。这两个参数实际上是cfq判断请求合并处理的条件限制，凡事复合这个条件的请求，都会尽量在本次请求处理的时候一起合并处理。fifo_expire_async:设置异步请求的超时时间。同步请求和异步请求是区分不同队列处理的，cfq在调度的时候一般情况都会优先处理同步请求，之后再处理异步请求，除非异步请求符合上述合并处理的条件限制范围内。当本进程的队列被调度时，cfq会优先检查是否有异步请求超时，就是超过fifo_expire_async参数的限制。如果有，则优先发送一个超时的请求，其余请求仍然按照优先级以及扇区编号大小来处理。fifo_expire_sync:这个参数跟上面的类似，区别是用来设置同步请求的超时时间。slice_idle:参数设置了一个等待时间。这让cfq在切换cfq_queue或service tree的时候等待一段时间，目的是提高机械硬盘的吞吐量。一般情况下，来自同一个cfq_queue或者service tree的IO请求的寻址局部性更好，所以这样可以减少磁盘的寻址次数。这个值在机械硬盘上默认为非零。当然在固态硬盘或者硬RAID设备上设置这个值为非零会降低存储的效率，因为固态硬盘没有磁头寻址这个概念，所以在这样的设备上应该设置为0，关闭此功能。group_idle:这个参数也跟上一个参数类似，区别是当cfq要切换cfq_group的时候会等待一段时间。在cgroup的场景下，如果我们沿用slice_idle的方式，那么空转等待可能会在cgroup组内每个进程的cfq_queue切换时发生。这样会如果这个进程一直有请求要处理的话，那么直到这个cgroup的配额被耗尽，同组中的其它进程也可能无法被调度到。这样会导致同组中的其它进程饿死而产生IO性能瓶颈。在这种情况下，我们可以将slice_idle ＝ 0而group_idle ＝ 8。这样空转等待就是以cgroup为单位进行的，而不是以cfq_queue的进程为单位进行，以防止上述问题产生。low_latency:这个是用来开启或关闭cfq的低延时（low latency）模式的开关。当这个开关打开时，cfq将会根据target_latency的参数设置来对每一个进程的分片时间（slice time）进行重新计算。这将有利于对吞吐量的公平（默认是对时间片分配的公平）。关闭这个参数（设置为0）将忽略target_latency的值。这将使系统中的进程完全按照时间片方式进行IO资源分配。这个开关默认是打开的。我们已经知道cfq设计上有“空转”（idling）这个概念，目的是为了可以让连续的读写操作尽可能多的合并处理，减少磁头的寻址操作以便增大吞吐量。如果有进程总是很快的进行顺序读写，那么它将因为cfq的空转等待命中率很高而导致其它需要处理IO的进程响应速度下降，如果另一个需要调度的进程不会发出大量顺序IO行为的话，系统中不同进程IO吞吐量的表现就会很不均衡。就比如，系统内存的cache中有很多脏页要写回时，桌面又要打开一个浏览器进行操作，这时脏页写回的后台行为就很可能会大量命中空转时间，而导致浏览器的小量IO一直等待，让用户感觉浏览器运行响应速度变慢。这个low_latency主要是对这种情况进行优化的选项，当其打开时，系统会根据target_latency的配置对因为命中空转而大量占用IO吞吐量的进程进行限制，以达到不同进程IO占用的吞吐量的相对均衡。这个开关比较合适在类似桌面应用的场景下打开。target_latency:当low_latency的值为开启状态时，cfq将根据这个值重新计算每个进程分配的IO时间片长度。quantum:这个参数用来设置每次从cfq_queue中处理多少个IO请求。在一个队列处理事件周期中，超过这个数字的IO请求将不会被处理。这个参数只对同步的请求有效。slice_sync:当一个cfq_queue队列被调度处理时，它可以被分配的处理总时间是通过这个值来作为一个计算参数指定的。公式为：time_slice = slice_sync + (slice_sync/5 * (4 - prio))。这个参数对同步请求有效。slice_async:这个值跟上一个类似，区别是对异步请求有效。slice_async_rq:这个参数用来限制在一个slice的时间范围内，一个队列最多可以处理的异步请求个数。请求被处理的最大个数还跟相关进程被设置的io优先级有关。1.3 cfq的IOPS模式我们已经知道，默认情况下cfq是以时间片方式支持的带优先级的调度来保证IO资源占用的公平。高优先级的进程将得到更多的时间片长度，而低优先级的进程时间片相对较小。当我们的存储是一个高速并且支持NCQ（原生指令队列）的设备的时候，我们最好可以让其可以从多个cfq队列中处理多路的请求，以便提升NCQ的利用率。此时使用时间片的分配方式分配资源就显得不合时宜了，因为基于时间片的分配，同一时刻最多能处理的请求队列只有一个。这时，我们需要切换cfq的模式为IOPS模式。切换方式很简单，就是将slice_idle=0即可。内核会自动检测你的存储设备是否支持NCQ，如果支持的话cfq会自动切换为IOPS模式。另外，在默认的基于优先级的时间片方式下，我们可以使用ionice命令来调整进程的IO优先级。进程默认分配的IO优先级是根据进程的nice值计算而来的，计算方法可以在man ionice中看到，这里不再废话。2、deadline：最终期限调度deadline调度算法相对cfq要简单很多。其设计目标是：在保证请求按照设备扇区的顺序进行访问的同时，兼顾其它请求不被饿死，要在一个最终期限前被调度到。我们知道磁头对磁盘的寻道是可以进行顺序访问和随机访问的，因为寻道延时时间的关系，顺序访问时IO的吞吐量更大，随机访问的吞吐量小。如果我们想为一个机械硬盘进行吞吐量优化的话，那么就可以让调度器按照尽量复合顺序访问的IO请求进行排序，之后请求以这样的顺序发送给硬盘，就可以使IO的吞吐量更大。但是这样做也有另一个问题，就是如果此时出现了一个请求，它要访问的磁道离目前磁头所在磁道很远，应用的请求又大量集中在目前磁道附近。导致大量请求一直会被合并和插队处理，而那个要访问比较远磁道的请求将因为一直不能被调度而饿死。deadline就是这样一种调度器，能在保证IO最大吞吐量的情况下，尽量使远端请求在一个期限内被调度而不被饿死的调度器。

前言：本文主要讲解Linux IO调度层的三种模式：cfp、deadline和noop，并给出各自的优化和适用场景建议。IO调度发生在Linux内核的IO调度层。这个层次是针对Linux的整体IO层次体系来说的。从read()或者write()系统调用的角度来说，Linux整体IO体系可以分为七层，它们分别是：VFS层： 虚拟文件系统层。由于内核要跟多种文件系统打交道，而每一种文件系统所实现的数据结构和相关方法都可能不尽相同，所以，内核抽象了这一层，专门用来适配各种文件系统，并对外提供统一操作接口。文件系统层： 不同的文件系统实现自己的操作过程，提供自己特有的特征，具体不多说了，大家愿意的话自己去看代码即可。页缓存层： 负责真对page的缓存。通用块层： 由于绝大多数情况的io操作是跟块设备打交道，所以Linux在此提供了一个类似vfs层的块设备操作抽象层。下层对接各种不同属性的块设备，对上提供统一的Block IO请求标准。IO调度层 ：因为绝大多数的块设备都是类似磁盘这样的设备，所以有必要根据这类设备的特点以及应用的不同特点来设置一些不同的调度算法和队列。以便在不同的应用环境下有针对性的提高磁盘的读写效率，这里就是大名鼎鼎的Linux电梯所起作用的地方。针对机械硬盘的各种调度方法就是在这实现的。块设备驱动层： 驱动层对外提供相对比较高级的设备操作接口，往往是C语言的，而下层对接设备本身的操作方法和规范。块设备层： 这层就是具体的物理设备了，定义了各种真对设备操作方法和规范。有一个已经整理好的[Linux IO结构图]，非常经典，一图胜千言：我们今天要研究的内容主要在IO调度这一层。它要解决的核心问题是，如何提高块设备IO的整体性能？这一层也主要是针对机械硬盘结构而设计的。众所周知，机械硬盘的存储介质是磁盘，磁头在盘片上移动进行磁道寻址，行为类似播放一张唱片。这种结构的特点是，顺序访问时吞吐量较高，但是如果一旦对盘片有随机访问，那么大量的时间都会浪费在磁头的移动上，这时候就会导致每次IO的响应时间变长，极大的降低IO的响应速度。磁头在盘片上寻道的操作，类似电梯调度，实际上在最开始的时期，Linux把这个算法命名为Linux电梯算法，即：如果在寻道的过程中，能把顺序路过的相关磁道的数据请求都“顺便”处理掉，那么就可以在比较小影响响应速度的前提下，提高整体IO的吞吐量。这就是我们为什么要设计IO调度算法的原因。目前在内核中默认开启了三种算法/模式：noop，cfq和deadline。严格算应该是两种：因为第一种叫做noop，就是空操作调度算法，也就是没有任何调度操作，并不对io请求进行排序，仅仅做适当的io合并的一个fifo队列。目前内核中默认的调度算法应该是cfq，叫做完全公平队列调度。这个调度算法人如其名，它试图给所有进程提供一个完全公平的IO操作环境。注：请大家一定记住这个词语，cfq，完全公平队列调度，不然下文就没法看了。cfq为每个进程创建一个同步IO调度队列，并默认以时间片和请求数限定的方式分配IO资源，以此保证每个进程的IO资源占用是公平的，cfq还实现了针对进程级别的优先级调度，这个我们后面会详细解释。查看和修改IO调度算法的方法是：cfq是通用服务器比较好的IO调度算法选择，对桌面用户也是比较好的选择。但是对于很多IO压力较大的场景就并不是很适应，尤其是IO压力集中在某些进程上的场景。因为这种场景我们需要更多的满足某个或者某几个进程的IO响应速度，而不是让所有的进程公平的使用IO，比如数据库应用。deadline调度（最终期限调度）就是更适合上述场景的解决方案。deadline实现了四个队列：其中两个分别处理正常read和write，按扇区号排序，进行正常io的合并处理以提高吞吐量。因为IO请求可能会集中在某些磁盘位置，这样会导致新来的请求一直被合并，可能会有其他磁盘位置的io请求被饿死。另外两个处理超时read和write的队列，按请求创建时间排序，如果有超时的请求出现，就放进这两个队列，调度算法保证超时（达到最终期限时间）的队列中的请求会优先被处理，防止请求被饿死。不久前，内核还是默认标配四种算法，还有一种叫做as的算法（Anticipatory scheduler），预测调度算法。一个高大上的名字，搞得我一度认为Linux内核都会算命了。结果发现，无非是在基于deadline算法做io调度的之前等一小会时间，如果这段时间内有可以合并的io请求到来，就可以合并处理，提高deadline调度的在顺序读写情况下的数据吞吐量。其实这根本不是啥预测，我觉得不如叫撞大运调度算法，当然这种策略在某些特定场景差效果不错。但是在大多数场景下，这个调度不仅没有提高吞吐量，还降低了响应速度，所以内核干脆把它从默认配置里删除了。毕竟Linux的宗旨是实用，而我们也就不再这个调度算法上多费口舌了。1、cfq：完全公平队列调度cfq是内核默认选择的IO调度队列，它在桌面应用场景以及大多数常见应用场景下都是很好的选择。如何实现一个所谓的完全公平队列（Completely Fair Queueing）？首先我们要理解所谓的公平是对谁的公平？从操作系统的角度来说，产生操作行为的主体都是进程，所以这里的公平是针对每个进程而言的，我们要试图让进程可以公平的占用IO资源。那么如何让进程公平的占用IO资源？我们需要先理解什么是IO资源。当我们衡量一个IO资源的时候，一般喜欢用的是两个单位，一个是数据读写的带宽，另一个是数据读写的IOPS。带宽就是以时间为单位的读写数据量，比如，100Mbyte/s。而IOPS是以时间为单位的读写次数。在不同的读写情境下，这两个单位的表现可能不一样，但是可以确定的是，两个单位的任何一个达到了性能上限，都会成为IO的瓶颈。从机械硬盘的结构考虑，如果读写是顺序读写，那么IO的表现是可以通过比较少的IOPS达到较大的带宽，因为可以合并很多IO，也可以通过预读等方式加速数据读取效率。当IO的表现是偏向于随机读写的时候，那么IOPS就会变得更大，IO的请求的合并可能性下降，当每次io请求数据越少的时候，带宽表现就会越低。从这里我们可以理解，针对进程的IO资源的主要表现形式有两个： 进程在单位时间内提交的IO请求个数和进程占用IO的带宽。其实无论哪个，都是跟进程分配的IO处理时间长度紧密相关的。有时业务可以在较少IOPS的情况下占用较大带宽，另外一些则可能在较大IOPS的情况下占用较少带宽，所以对进程占用IO的时间进行调度才是相对最公平的。即，我不管你是IOPS高还是带宽占用高，到了时间咱就换下一个进程处理，你爱咋样咋样。所以，cfq就是试图给所有进程分配等同的块设备使用的时间片，进程在时间片内，可以将产生的IO请求提交给块设备进行处理，时间片结束，进程的请求将排进它自己的队列，等待下次调度的时候进行处理。这就是cfq的基本原理。当然，现实生活中不可能有真正的“公平”，常见的应用场景下，我们很肯能需要人为的对进程的IO占用进行人为指定优先级，这就像对进程的CPU占用设置优先级的概念一样。所以，除了针对时间片进行公平队列调度外，cfq还提供了优先级支持。每个进程都可以设置一个IO优先级，cfq会根据这个优先级的设置情况作为调度时的重要参考因素。优先级首先分成三大类：RT、BE、IDLE，它们分别是实时（Real Time）、最佳效果（Best Try）和闲置（Idle）三个类别，对每个类别的IO，cfq都使用不同的策略进行处理。另外，RT和BE类别中，分别又再划分了8个子优先级实现更细节的QOS需求，而IDLE只有一个子优先级。另外，我们都知道内核默认对存储的读写都是经过缓存（buffer/cache）的，在这种情况下，cfq是无法区分当前处理的请求是来自哪一个进程的。只有在进程使用同步方式（sync read或者sync wirte）或者直接IO（Direct IO）方式进行读写的时候，cfq才能区分出IO请求来自哪个进程。所以，除了针对每个进程实现的IO队列以外，还实现了一个公共的队列用来处理异步请求。当前内核已经实现了针对IO资源的cgroup资源隔离，所以在以上体系的基础上，cfq也实现了针对cgroup的调度支持。总的来说，cfq用了一系列的数据结构实现了以上所有复杂功能的支持，大家可以通过源代码看到其相关实现，文件在源代码目录下的block/cfq-iosched.c。1.1 cfq设计原理在此，我们对整体数据结构做一个简要描述：首先，cfq通过一个叫做cfq_data的数据结构维护了整个调度器流程。在一个支持了cgroup功能的cfq中，全部进程被分成了若干个contral group进行管理。每个cgroup在cfq中都有一个cfq_group的结构进行描述，所有的cgroup都被作为一个调度对象放进一个红黑树中，并以vdisktime为key进行排序。vdisktime这个时间纪录的是当前cgroup所占用的io时间，每次对cgroup进行调度时，总是通过红黑树选择当前vdisktime时间最少的cgroup进行处理，以保证所有cgroups之间的IO资源占用“公平”。当然我们知道，cgroup是可以对blkio进行资源比例分配的，其作用原理就是，分配比例大的cgroup占用vdisktime时间增长较慢，分配比例小的vdisktime时间增长较快，快慢与分配比例成正比。这样就做到了不同的cgroup分配的IO比例不一样，并且在cfq的角度看来依然是“公平“的。选择好了需要处理的cgroup（cfq_group）之后，调度器需要决策选择下一步的service_tree。service_tree这个数据结构对应的都是一系列的红黑树，主要目的是用来实现请求优先级分类的，就是RT、BE、IDLE的分类。每一个cfq_group都维护了7个service_trees，其定义如下：其中service_tree_idle就是用来给IDLE类型的请求进行排队用的红黑树。而上面二维数组，首先第一个维度针对RT和BE分别各实现了一个数组，每一个数组中都维护了三个红黑树，分别对应三种不同子类型的请求，分别是：SYNC、SYNC_NOIDLE以及ASYNC。我们可以认为SYNC相当于SYNC_IDLE并与SYNC_NOIDLE对应。idling是cfq在设计上为了尽量合并连续的IO请求以达到提高吞吐量的目的而加入的机制，我们可以理解为是一种“空转”等待机制。空转是指，当一个队列处理一个请求结束后，会在发生调度之前空等一小会时间，如果下一个请求到来，则可以减少磁头寻址，继续处理顺序的IO请求。为了实现这个功能，cfq在service_tree这层数据结构这实现了SYNC队列，如果请求是同步顺序请求，就入队这个service tree，如果请求是同步随机请求，则入队SYNC_NOIDLE队列，以判断下一个请求是否是顺序请求。所有的异步写操作请求将入队ASYNC的service tree，并且针对这个队列没有空转等待机制。此外，cfq还对SSD这样的硬盘有特殊调整，当cfq发现存储设备是一个ssd硬盘这样的队列深度更大的设备时，所有针对单独队列的空转都将不生效，所有的IO请求都将入队SYNC_NOIDLE这个service tree。每一个service tree都对应了若干个cfq_queue队列，每个cfq_queue队列对应一个进程，这个我们后续再详细说明。cfq_group还维护了一个在cgroup内部所有进程公用的异步IO请求队列，其结构如下：异步请求也分成了RT、BE、IDLE这三类进行处理，每一类对应一个cfq_queue进行排队。BE和RT也实现了优先级的支持，每一个类型有IOPRIO_BE_NR这么多个优先级，这个值定义为8，数组下标为0-7。我们目前分析的内核代码版本为Linux 4.4，可以看出，从cfq的角度来说，已经可以实现异步IO的cgroup支持了，我们需要定义一下这里所谓异步IO的含义，它仅仅表示从内存的buffer/cache中的数据同步到硬盘的IO请求，而不是aio(man 7 aio)或者linux的native异步io以及libaio机制，实际上这些所谓的“异步”IO机制，在内核中都是同步实现的（本质上冯诺伊曼计算机没有真正的“异步”机制）。我们在上面已经说明过，由于进程正常情况下都是将数据先写入buffer/cache，所以这种异步IO都是统一由cfq_group中的async请求队列处理的。那么为什么在上面的service_tree中还要实现和一个ASYNC的类型呢？这当然是为了支持区分进程的异步IO并使之可以“完全公平”做准备喽。实际上在最新的cgroup v2的blkio体系中，内核已经支持了针对buffer IO的cgroup限速支持，而以上这些可能容易混淆的一堆类型，都是在新的体系下需要用到的类型标记。新体系的复杂度更高了，功能也更加强大，但是大家先不要着急，正式的cgroup v2体系，在Linux 4.5发布的时候会正式跟大家见面。我们继续选择service_tree的过程，三种优先级类型的service_tree的选择就是根据类型的优先级来做选择的，RT优先级最高，BE其次，IDLE最低。就是说，RT里有，就会一直处理RT，RT没了再处理BE。每个service_tree对应一个元素为cfq_queue排队的红黑树，而每个cfq_queue就是内核为进程（线程）创建的请求队列。每一个cfq_queue都会维护一个rb_key的变量，这个变量实际上就是这个队列的IO服务时间（service time）。这里还是通过红黑树找到service time时间最短的那个cfq_queue进行服务，以保证“完全公平”。选择好了cfq_queue之后，就要开始处理这个队列里的IO请求了。这里的调度方式基本跟deadline类似。cfq_queue会对进入队列的每一个请求进行两次入队，一个放进fifo中，另一个放进按访问扇区顺序作为key的红黑树中。默认从红黑树中取请求进行处理，当请求的延时时间达到deadline时，就从红黑树中取等待时间最长的进行处理，以保证请求不被饿死。这就是整个cfq的调度流程，当然其中还有很多细枝末节没有交代，比如合并处理以及顺序处理等等。1.2 cfq的参数调整理解整个调度流程有助于我们决策如何调整cfq的相关参数。所有cfq的可调参数都可以在/sys/class/block/sda/queue/iosched/目录下找到，当然，在你的系统上，请将sda替换为相应的磁盘名称。我们来看一下都有什么：这些参数部分是跟机械硬盘磁头寻道方式有关的，如果其说明你看不懂，请先补充相关知识：back_seek_max:磁头可以向后寻址的最大范围，默认值为16M。back_seek_penalty:向后寻址的惩罚系数。这个值是跟向前寻址进行比较的。以上两个是为了防止磁头寻道发生抖动而导致寻址过慢而设置的。基本思路是这样，一个io请求到来的时候，cfq会根据其寻址位置预估一下其磁头寻道成本。设置一个最大值back_seek_max，对于请求所访问的扇区号在磁头后方的请求，只要寻址范围没有超过这个值，cfq会像向前寻址的请求一样处理它。再设置一个评估成本的系数back_seek_penalty，相对于磁头向前寻址，向后寻址的距离为1/2(1/back_seek_penalty)时，cfq认为这两个请求寻址的代价是相同。这两个参数实际上是cfq判断请求合并处理的条件限制，凡事复合这个条件的请求，都会尽量在本次请求处理的时候一起合并处理。fifo_expire_async:设置异步请求的超时时间。同步请求和异步请求是区分不同队列处理的，cfq在调度的时候一般情况都会优先处理同步请求，之后再处理异步请求，除非异步请求符合上述合并处理的条件限制范围内。当本进程的队列被调度时，cfq会优先检查是否有异步请求超时，就是超过fifo_expire_async参数的限制。如果有，则优先发送一个超时的请求，其余请求仍然按照优先级以及扇区编号大小来处理。fifo_expire_sync:这个参数跟上面的类似，区别是用来设置同步请求的超时时间。slice_idle:参数设置了一个等待时间。这让cfq在切换cfq_queue或service tree的时候等待一段时间，目的是提高机械硬盘的吞吐量。一般情况下，来自同一个cfq_queue或者service tree的IO请求的寻址局部性更好，所以这样可以减少磁盘的寻址次数。这个值在机械硬盘上默认为非零。当然在固态硬盘或者硬RAID设备上设置这个值为非零会降低存储的效率，因为固态硬盘没有磁头寻址这个概念，所以在这样的设备上应该设置为0，关闭此功能。group_idle:这个参数也跟上一个参数类似，区别是当cfq要切换cfq_group的时候会等待一段时间。在cgroup的场景下，如果我们沿用slice_idle的方式，那么空转等待可能会在cgroup组内每个进程的cfq_queue切换时发生。这样会如果这个进程一直有请求要处理的话，那么直到这个cgroup的配额被耗尽，同组中的其它进程也可能无法被调度到。这样会导致同组中的其它进程饿死而产生IO性能瓶颈。在这种情况下，我们可以将slice_idle ＝ 0而group_idle ＝ 8。这样空转等待就是以cgroup为单位进行的，而不是以cfq_queue的进程为单位进行，以防止上述问题产生。low_latency:这个是用来开启或关闭cfq的低延时（low latency）模式的开关。当这个开关打开时，cfq将会根据target_latency的参数设置来对每一个进程的分片时间（slice time）进行重新计算。这将有利于对吞吐量的公平（默认是对时间片分配的公平）。关闭这个参数（设置为0）将忽略target_latency的值。这将使系统中的进程完全按照时间片方式进行IO资源分配。这个开关默认是打开的。我们已经知道cfq设计上有“空转”（idling）这个概念，目的是为了可以让连续的读写操作尽可能多的合并处理，减少磁头的寻址操作以便增大吞吐量。如果有进程总是很快的进行顺序读写，那么它将因为cfq的空转等待命中率很高而导致其它需要处理IO的进程响应速度下降，如果另一个需要调度的进程不会发出大量顺序IO行为的话，系统中不同进程IO吞吐量的表现就会很不均衡。就比如，系统内存的cache中有很多脏页要写回时，桌面又要打开一个浏览器进行操作，这时脏页写回的后台行为就很可能会大量命中空转时间，而导致浏览器的小量IO一直等待，让用户感觉浏览器运行响应速度变慢。这个low_latency主要是对这种情况进行优化的选项，当其打开时，系统会根据target_latency的配置对因为命中空转而大量占用IO吞吐量的进程进行限制，以达到不同进程IO占用的吞吐量的相对均衡。这个开关比较合适在类似桌面应用的场景下打开。target_latency:当low_latency的值为开启状态时，cfq将根据这个值重新计算每个进程分配的IO时间片长度。quantum:这个参数用来设置每次从cfq_queue中处理多少个IO请求。在一个队列处理事件周期中，超过这个数字的IO请求将不会被处理。这个参数只对同步的请求有效。slice_sync:当一个cfq_queue队列被调度处理时，它可以被分配的处理总时间是通过这个值来作为一个计算参数指定的。公式为：time_slice = slice_sync + (slice_sync/5 * (4 - prio))。这个参数对同步请求有效。slice_async:这个值跟上一个类似，区别是对异步请求有效。slice_async_rq:这个参数用来限制在一个slice的时间范围内，一个队列最多可以处理的异步请求个数。请求被处理的最大个数还跟相关进程被设置的io优先级有关。1.3 cfq的IOPS模式我们已经知道，默认情况下cfq是以时间片方式支持的带优先级的调度来保证IO资源占用的公平。高优先级的进程将得到更多的时间片长度，而低优先级的进程时间片相对较小。当我们的存储是一个高速并且支持NCQ（原生指令队列）的设备的时候，我们最好可以让其可以从多个cfq队列中处理多路的请求，以便提升NCQ的利用率。此时使用时间片的分配方式分配资源就显得不合时宜了，因为基于时间片的分配，同一时刻最多能处理的请求队列只有一个。这时，我们需要切换cfq的模式为IOPS模式。切换方式很简单，就是将slice_idle=0即可。内核会自动检测你的存储设备是否支持NCQ，如果支持的话cfq会自动切换为IOPS模式。另外，在默认的基于优先级的时间片方式下，我们可以使用ionice命令来调整进程的IO优先级。进程默认分配的IO优先级是根据进程的nice值计算而来的，计算方法可以在man ionice中看到，这里不再废话。2、deadline：最终期限调度deadline调度算法相对cfq要简单很多。其设计目标是：在保证请求按照设备扇区的顺序进行访问的同时，兼顾其它请求不被饿死，要在一个最终期限前被调度到。我们知道磁头对磁盘的寻道是可以进行顺序访问和随机访问的，因为寻道延时时间的关系，顺序访问时IO的吞吐量更大，随机访问的吞吐量小。如果我们想为一个机械硬盘进行吞吐量优化的话，那么就可以让调度器按照尽量复合顺序访问的IO请求进行排序，之后请求以这样的顺序发送给硬盘，就可以使IO的吞吐量更大。但是这样做也有另一个问题，就是如果此时出现了一个请求，它要访问的磁道离目前磁头所在磁道很远，应用的请求又大量集中在目前磁道附近。导致大量请求一直会被合并和插队处理，而那个要访问比较远磁道的请求将因为一直不能被调度而饿死。deadline就是这样一种调度器，能在保证IO最大吞吐量的情况下，尽量使远端请求在一个期限内被调度而不被饿死的调度器。

前言：本文主要讲解Linux IO调度层的三种模式：cfp、deadline和noop，并给出各自的优化和适用场景建议。IO调度发生在Linux内核的IO调度层。这个层次是针对Linux的整体IO层次体系来说的。从read()或者write()系统调用的角度来说，Linux整体IO体系可以分为七层，它们分别是：VFS层： 虚拟文件系统层。由于内核要跟多种文件系统打交道，而每一种文件系统所实现的数据结构和相关方法都可能不尽相同，所以，内核抽象了这一层，专门用来适配各种文件系统，并对外提供统一操作接口。文件系统层： 不同的文件系统实现自己的操作过程，提供自己特有的特征，具体不多说了，大家愿意的话自己去看代码即可。页缓存层： 负责真对page的缓存。通用块层： 由于绝大多数情况的io操作是跟块设备打交道，所以Linux在此提供了一个类似vfs层的块设备操作抽象层。下层对接各种不同属性的块设备，对上提供统一的Block IO请求标准。IO调度层 ：因为绝大多数的块设备都是类似磁盘这样的设备，所以有必要根据这类设备的特点以及应用的不同特点来设置一些不同的调度算法和队列。以便在不同的应用环境下有针对性的提高磁盘的读写效率，这里就是大名鼎鼎的Linux电梯所起作用的地方。针对机械硬盘的各种调度方法就是在这实现的。块设备驱动层： 驱动层对外提供相对比较高级的设备操作接口，往往是C语言的，而下层对接设备本身的操作方法和规范。块设备层： 这层就是具体的物理设备了，定义了各种真对设备操作方法和规范。有一个已经整理好的[Linux IO结构图]，非常经典，一图胜千言：我们今天要研究的内容主要在IO调度这一层。它要解决的核心问题是，如何提高块设备IO的整体性能？这一层也主要是针对机械硬盘结构而设计的。众所周知，机械硬盘的存储介质是磁盘，磁头在盘片上移动进行磁道寻址，行为类似播放一张唱片。这种结构的特点是，顺序访问时吞吐量较高，但是如果一旦对盘片有随机访问，那么大量的时间都会浪费在磁头的移动上，这时候就会导致每次IO的响应时间变长，极大的降低IO的响应速度。磁头在盘片上寻道的操作，类似电梯调度，实际上在最开始的时期，Linux把这个算法命名为Linux电梯算法，即：如果在寻道的过程中，能把顺序路过的相关磁道的数据请求都“顺便”处理掉，那么就可以在比较小影响响应速度的前提下，提高整体IO的吞吐量。这就是我们为什么要设计IO调度算法的原因。目前在内核中默认开启了三种算法/模式：noop，cfq和deadline。严格算应该是两种：因为第一种叫做noop，就是空操作调度算法，也就是没有任何调度操作，并不对io请求进行排序，仅仅做适当的io合并的一个fifo队列。目前内核中默认的调度算法应该是cfq，叫做完全公平队列调度。这个调度算法人如其名，它试图给所有进程提供一个完全公平的IO操作环境。注：请大家一定记住这个词语，cfq，完全公平队列调度，不然下文就没法看了。cfq为每个进程创建一个同步IO调度队列，并默认以时间片和请求数限定的方式分配IO资源，以此保证每个进程的IO资源占用是公平的，cfq还实现了针对进程级别的优先级调度，这个我们后面会详细解释。查看和修改IO调度算法的方法是：cfq是通用服务器比较好的IO调度算法选择，对桌面用户也是比较好的选择。但是对于很多IO压力较大的场景就并不是很适应，尤其是IO压力集中在某些进程上的场景。因为这种场景我们需要更多的满足某个或者某几个进程的IO响应速度，而不是让所有的进程公平的使用IO，比如数据库应用。deadline调度（最终期限调度）就是更适合上述场景的解决方案。deadline实现了四个队列：其中两个分别处理正常read和write，按扇区号排序，进行正常io的合并处理以提高吞吐量。因为IO请求可能会集中在某些磁盘位置，这样会导致新来的请求一直被合并，可能会有其他磁盘位置的io请求被饿死。另外两个处理超时read和write的队列，按请求创建时间排序，如果有超时的请求出现，就放进这两个队列，调度算法保证超时（达到最终期限时间）的队列中的请求会优先被处理，防止请求被饿死。不久前，内核还是默认标配四种算法，还有一种叫做as的算法（Anticipatory scheduler），预测调度算法。一个高大上的名字，搞得我一度认为Linux内核都会算命了。结果发现，无非是在基于deadline算法做io调度的之前等一小会时间，如果这段时间内有可以合并的io请求到来，就可以合并处理，提高deadline调度的在顺序读写情况下的数据吞吐量。其实这根本不是啥预测，我觉得不如叫撞大运调度算法，当然这种策略在某些特定场景差效果不错。但是在大多数场景下，这个调度不仅没有提高吞吐量，还降低了响应速度，所以内核干脆把它从默认配置里删除了。毕竟Linux的宗旨是实用，而我们也就不再这个调度算法上多费口舌了。1、cfq：完全公平队列调度cfq是内核默认选择的IO调度队列，它在桌面应用场景以及大多数常见应用场景下都是很好的选择。如何实现一个所谓的完全公平队列（Completely Fair Queueing）？首先我们要理解所谓的公平是对谁的公平？从操作系统的角度来说，产生操作行为的主体都是进程，所以这里的公平是针对每个进程而言的，我们要试图让进程可以公平的占用IO资源。那么如何让进程公平的占用IO资源？我们需要先理解什么是IO资源。当我们衡量一个IO资源的时候，一般喜欢用的是两个单位，一个是数据读写的带宽，另一个是数据读写的IOPS。带宽就是以时间为单位的读写数据量，比如，100Mbyte/s。而IOPS是以时间为单位的读写次数。在不同的读写情境下，这两个单位的表现可能不一样，但是可以确定的是，两个单位的任何一个达到了性能上限，都会成为IO的瓶颈。从机械硬盘的结构考虑，如果读写是顺序读写，那么IO的表现是可以通过比较少的IOPS达到较大的带宽，因为可以合并很多IO，也可以通过预读等方式加速数据读取效率。当IO的表现是偏向于随机读写的时候，那么IOPS就会变得更大，IO的请求的合并可能性下降，当每次io请求数据越少的时候，带宽表现就会越低。从这里我们可以理解，针对进程的IO资源的主要表现形式有两个： 进程在单位时间内提交的IO请求个数和进程占用IO的带宽。其实无论哪个，都是跟进程分配的IO处理时间长度紧密相关的。有时业务可以在较少IOPS的情况下占用较大带宽，另外一些则可能在较大IOPS的情况下占用较少带宽，所以对进程占用IO的时间进行调度才是相对最公平的。即，我不管你是IOPS高还是带宽占用高，到了时间咱就换下一个进程处理，你爱咋样咋样。所以，cfq就是试图给所有进程分配等同的块设备使用的时间片，进程在时间片内，可以将产生的IO请求提交给块设备进行处理，时间片结束，进程的请求将排进它自己的队列，等待下次调度的时候进行处理。这就是cfq的基本原理。当然，现实生活中不可能有真正的“公平”，常见的应用场景下，我们很肯能需要人为的对进程的IO占用进行人为指定优先级，这就像对进程的CPU占用设置优先级的概念一样。所以，除了针对时间片进行公平队列调度外，cfq还提供了优先级支持。每个进程都可以设置一个IO优先级，cfq会根据这个优先级的设置情况作为调度时的重要参考因素。优先级首先分成三大类：RT、BE、IDLE，它们分别是实时（Real Time）、最佳效果（Best Try）和闲置（Idle）三个类别，对每个类别的IO，cfq都使用不同的策略进行处理。另外，RT和BE类别中，分别又再划分了8个子优先级实现更细节的QOS需求，而IDLE只有一个子优先级。另外，我们都知道内核默认对存储的读写都是经过缓存（buffer/cache）的，在这种情况下，cfq是无法区分当前处理的请求是来自哪一个进程的。只有在进程使用同步方式（sync read或者sync wirte）或者直接IO（Direct IO）方式进行读写的时候，cfq才能区分出IO请求来自哪个进程。所以，除了针对每个进程实现的IO队列以外，还实现了一个公共的队列用来处理异步请求。当前内核已经实现了针对IO资源的cgroup资源隔离，所以在以上体系的基础上，cfq也实现了针对cgroup的调度支持。总的来说，cfq用了一系列的数据结构实现了以上所有复杂功能的支持，大家可以通过源代码看到其相关实现，文件在源代码目录下的block/cfq-iosched.c。1.1 cfq设计原理在此，我们对整体数据结构做一个简要描述：首先，cfq通过一个叫做cfq_data的数据结构维护了整个调度器流程。在一个支持了cgroup功能的cfq中，全部进程被分成了若干个contral group进行管理。每个cgroup在cfq中都有一个cfq_group的结构进行描述，所有的cgroup都被作为一个调度对象放进一个红黑树中，并以vdisktime为key进行排序。vdisktime这个时间纪录的是当前cgroup所占用的io时间，每次对cgroup进行调度时，总是通过红黑树选择当前vdisktime时间最少的cgroup进行处理，以保证所有cgroups之间的IO资源占用“公平”。当然我们知道，cgroup是可以对blkio进行资源比例分配的，其作用原理就是，分配比例大的cgroup占用vdisktime时间增长较慢，分配比例小的vdisktime时间增长较快，快慢与分配比例成正比。这样就做到了不同的cgroup分配的IO比例不一样，并且在cfq的角度看来依然是“公平“的。选择好了需要处理的cgroup（cfq_group）之后，调度器需要决策选择下一步的service_tree。service_tree这个数据结构对应的都是一系列的红黑树，主要目的是用来实现请求优先级分类的，就是RT、BE、IDLE的分类。每一个cfq_group都维护了7个service_trees，其定义如下：其中service_tree_idle就是用来给IDLE类型的请求进行排队用的红黑树。而上面二维数组，首先第一个维度针对RT和BE分别各实现了一个数组，每一个数组中都维护了三个红黑树，分别对应三种不同子类型的请求，分别是：SYNC、SYNC_NOIDLE以及ASYNC。我们可以认为SYNC相当于SYNC_IDLE并与SYNC_NOIDLE对应。idling是cfq在设计上为了尽量合并连续的IO请求以达到提高吞吐量的目的而加入的机制，我们可以理解为是一种“空转”等待机制。空转是指，当一个队列处理一个请求结束后，会在发生调度之前空等一小会时间，如果下一个请求到来，则可以减少磁头寻址，继续处理顺序的IO请求。为了实现这个功能，cfq在service_tree这层数据结构这实现了SYNC队列，如果请求是同步顺序请求，就入队这个service tree，如果请求是同步随机请求，则入队SYNC_NOIDLE队列，以判断下一个请求是否是顺序请求。所有的异步写操作请求将入队ASYNC的service tree，并且针对这个队列没有空转等待机制。此外，cfq还对SSD这样的硬盘有特殊调整，当cfq发现存储设备是一个ssd硬盘这样的队列深度更大的设备时，所有针对单独队列的空转都将不生效，所有的IO请求都将入队SYNC_NOIDLE这个service tree。每一个service tree都对应了若干个cfq_queue队列，每个cfq_queue队列对应一个进程，这个我们后续再详细说明。cfq_group还维护了一个在cgroup内部所有进程公用的异步IO请求队列，其结构如下：异步请求也分成了RT、BE、IDLE这三类进行处理，每一类对应一个cfq_queue进行排队。BE和RT也实现了优先级的支持，每一个类型有IOPRIO_BE_NR这么多个优先级，这个值定义为8，数组下标为0-7。我们目前分析的内核代码版本为Linux 4.4，可以看出，从cfq的角度来说，已经可以实现异步IO的cgroup支持了，我们需要定义一下这里所谓异步IO的含义，它仅仅表示从内存的buffer/cache中的数据同步到硬盘的IO请求，而不是aio(man 7 aio)或者linux的native异步io以及libaio机制，实际上这些所谓的“异步”IO机制，在内核中都是同步实现的（本质上冯诺伊曼计算机没有真正的“异步”机制）。我们在上面已经说明过，由于进程正常情况下都是将数据先写入buffer/cache，所以这种异步IO都是统一由cfq_group中的async请求队列处理的。那么为什么在上面的service_tree中还要实现和一个ASYNC的类型呢？这当然是为了支持区分进程的异步IO并使之可以“完全公平”做准备喽。实际上在最新的cgroup v2的blkio体系中，内核已经支持了针对buffer IO的cgroup限速支持，而以上这些可能容易混淆的一堆类型，都是在新的体系下需要用到的类型标记。新体系的复杂度更高了，功能也更加强大，但是大家先不要着急，正式的cgroup v2体系，在Linux 4.5发布的时候会正式跟大家见面。我们继续选择service_tree的过程，三种优先级类型的service_tree的选择就是根据类型的优先级来做选择的，RT优先级最高，BE其次，IDLE最低。就是说，RT里有，就会一直处理RT，RT没了再处理BE。每个service_tree对应一个元素为cfq_queue排队的红黑树，而每个cfq_queue就是内核为进程（线程）创建的请求队列。每一个cfq_queue都会维护一个rb_key的变量，这个变量实际上就是这个队列的IO服务时间（service time）。这里还是通过红黑树找到service time时间最短的那个cfq_queue进行服务，以保证“完全公平”。选择好了cfq_queue之后，就要开始处理这个队列里的IO请求了。这里的调度方式基本跟deadline类似。cfq_queue会对进入队列的每一个请求进行两次入队，一个放进fifo中，另一个放进按访问扇区顺序作为key的红黑树中。默认从红黑树中取请求进行处理，当请求的延时时间达到deadline时，就从红黑树中取等待时间最长的进行处理，以保证请求不被饿死。这就是整个cfq的调度流程，当然其中还有很多细枝末节没有交代，比如合并处理以及顺序处理等等。1.2 cfq的参数调整理解整个调度流程有助于我们决策如何调整cfq的相关参数。所有cfq的可调参数都可以在/sys/class/block/sda/queue/iosched/目录下找到，当然，在你的系统上，请将sda替换为相应的磁盘名称。我们来看一下都有什么：这些参数部分是跟机械硬盘磁头寻道方式有关的，如果其说明你看不懂，请先补充相关知识：back_seek_max:磁头可以向后寻址的最大范围，默认值为16M。back_seek_penalty:向后寻址的惩罚系数。这个值是跟向前寻址进行比较的。以上两个是为了防止磁头寻道发生抖动而导致寻址过慢而设置的。基本思路是这样，一个io请求到来的时候，cfq会根据其寻址位置预估一下其磁头寻道成本。设置一个最大值back_seek_max，对于请求所访问的扇区号在磁头后方的请求，只要寻址范围没有超过这个值，cfq会像向前寻址的请求一样处理它。再设置一个评估成本的系数back_seek_penalty，相对于磁头向前寻址，向后寻址的距离为1/2(1/back_seek_penalty)时，cfq认为这两个请求寻址的代价是相同。这两个参数实际上是cfq判断请求合并处理的条件限制，凡事复合这个条件的请求，都会尽量在本次请求处理的时候一起合并处理。fifo_expire_async:设置异步请求的超时时间。同步请求和异步请求是区分不同队列处理的，cfq在调度的时候一般情况都会优先处理同步请求，之后再处理异步请求，除非异步请求符合上述合并处理的条件限制范围内。当本进程的队列被调度时，cfq会优先检查是否有异步请求超时，就是超过fifo_expire_async参数的限制。如果有，则优先发送一个超时的请求，其余请求仍然按照优先级以及扇区编号大小来处理。fifo_expire_sync:这个参数跟上面的类似，区别是用来设置同步请求的超时时间。slice_idle:参数设置了一个等待时间。这让cfq在切换cfq_queue或service tree的时候等待一段时间，目的是提高机械硬盘的吞吐量。一般情况下，来自同一个cfq_queue或者service tree的IO请求的寻址局部性更好，所以这样可以减少磁盘的寻址次数。这个值在机械硬盘上默认为非零。当然在固态硬盘或者硬RAID设备上设置这个值为非零会降低存储的效率，因为固态硬盘没有磁头寻址这个概念，所以在这样的设备上应该设置为0，关闭此功能。group_idle:这个参数也跟上一个参数类似，区别是当cfq要切换cfq_group的时候会等待一段时间。在cgroup的场景下，如果我们沿用slice_idle的方式，那么空转等待可能会在cgroup组内每个进程的cfq_queue切换时发生。这样会如果这个进程一直有请求要处理的话，那么直到这个cgroup的配额被耗尽，同组中的其它进程也可能无法被调度到。这样会导致同组中的其它进程饿死而产生IO性能瓶颈。在这种情况下，我们可以将slice_idle ＝ 0而group_idle ＝ 8。这样空转等待就是以cgroup为单位进行的，而不是以cfq_queue的进程为单位进行，以防止上述问题产生。low_latency:这个是用来开启或关闭cfq的低延时（low latency）模式的开关。当这个开关打开时，cfq将会根据target_latency的参数设置来对每一个进程的分片时间（slice time）进行重新计算。这将有利于对吞吐量的公平（默认是对时间片分配的公平）。关闭这个参数（设置为0）将忽略target_latency的值。这将使系统中的进程完全按照时间片方式进行IO资源分配。这个开关默认是打开的。我们已经知道cfq设计上有“空转”（idling）这个概念，目的是为了可以让连续的读写操作尽可能多的合并处理，减少磁头的寻址操作以便增大吞吐量。如果有进程总是很快的进行顺序读写，那么它将因为cfq的空转等待命中率很高而导致其它需要处理IO的进程响应速度下降，如果另一个需要调度的进程不会发出大量顺序IO行为的话，系统中不同进程IO吞吐量的表现就会很不均衡。就比如，系统内存的cache中有很多脏页要写回时，桌面又要打开一个浏览器进行操作，这时脏页写回的后台行为就很可能会大量命中空转时间，而导致浏览器的小量IO一直等待，让用户感觉浏览器运行响应速度变慢。这个low_latency主要是对这种情况进行优化的选项，当其打开时，系统会根据target_latency的配置对因为命中空转而大量占用IO吞吐量的进程进行限制，以达到不同进程IO占用的吞吐量的相对均衡。这个开关比较合适在类似桌面应用的场景下打开。target_latency:当low_latency的值为开启状态时，cfq将根据这个值重新计算每个进程分配的IO时间片长度。quantum:这个参数用来设置每次从cfq_queue中处理多少个IO请求。在一个队列处理事件周期中，超过这个数字的IO请求将不会被处理。这个参数只对同步的请求有效。slice_sync:当一个cfq_queue队列被调度处理时，它可以被分配的处理总时间是通过这个值来作为一个计算参数指定的。公式为：time_slice = slice_sync + (slice_sync/5 * (4 - prio))。这个参数对同步请求有效。slice_async:这个值跟上一个类似，区别是对异步请求有效。slice_async_rq:这个参数用来限制在一个slice的时间范围内，一个队列最多可以处理的异步请求个数。请求被处理的最大个数还跟相关进程被设置的io优先级有关。1.3 cfq的IOPS模式我们已经知道，默认情况下cfq是以时间片方式支持的带优先级的调度来保证IO资源占用的公平。高优先级的进程将得到更多的时间片长度，而低优先级的进程时间片相对较小。当我们的存储是一个高速并且支持NCQ（原生指令队列）的设备的时候，我们最好可以让其可以从多个cfq队列中处理多路的请求，以便提升NCQ的利用率。此时使用时间片的分配方式分配资源就显得不合时宜了，因为基于时间片的分配，同一时刻最多能处理的请求队列只有一个。这时，我们需要切换cfq的模式为IOPS模式。切换方式很简单，就是将slice_idle=0即可。内核会自动检测你的存储设备是否支持NCQ，如果支持的话cfq会自动切换为IOPS模式。另外，在默认的基于优先级的时间片方式下，我们可以使用ionice命令来调整进程的IO优先级。进程默认分配的IO优先级是根据进程的nice值计算而来的，计算方法可以在man ionice中看到，这里不再废话。2、deadline：最终期限调度deadline调度算法相对cfq要简单很多。其设计目标是：在保证请求按照设备扇区的顺序进行访问的同时，兼顾其它请求不被饿死，要在一个最终期限前被调度到。我们知道磁头对磁盘的寻道是可以进行顺序访问和随机访问的，因为寻道延时时间的关系，顺序访问时IO的吞吐量更大，随机访问的吞吐量小。如果我们想为一个机械硬盘进行吞吐量优化的话，那么就可以让调度器按照尽量复合顺序访问的IO请求进行排序，之后请求以这样的顺序发送给硬盘，就可以使IO的吞吐量更大。但是这样做也有另一个问题，就是如果此时出现了一个请求，它要访问的磁道离目前磁头所在磁道很远，应用的请求又大量集中在目前磁道附近。导致大量请求一直会被合并和插队处理，而那个要访问比较远磁道的请求将因为一直不能被调度而饿死。deadline就是这样一种调度器，能在保证IO最大吞吐量的情况下，尽量使远端请求在一个期限内被调度而不被饿死的调度器。

手机不属于耐摔产品，不同下落的高度以及着地的角度给手机带来的损伤可能会不同。若使用的vivo手机，可及时携带手机及购机凭证前往客户服务中心检测处理，客户服务中心地址：进入vivo官网/vivo商城APP--我的--服务网点/售后网点--选择省市进行查询客户服务中心地址，建议提前致电客户服务中心，确认相关事宜和了解上班时间在前往，以免耽误宝贵时间。注：设备摔伤摔坏不属于保修范围，不能保修也不能更换新机。

这种水龙头的原理就是在水管儿上安装了一圈电热丝，不过没有必要安装。

热水器不出热水怎么办？原因方法要了解在我们的日常家庭生活中,热水器的使用次数是比较多的,热水器是家庭的常用家电之一.但是许多家庭在使用热水器的过程中有时会出现不出热水的情况。针对这种问题，今天小编就来给您支招儿。一、热水器不出热水原因1、检查下你的热水器的设置问题，这种情况比较多，很多用户在使用电热水器的时候在温度的调节上调到了，或者没调节，这样就根本不会出热水。2、电热水器的电源显示是否亮，如果不亮，可能是温控器出了问题，或者加热棒出了问题，根据自己品牌打售后服务的。热水器效果图3、还有就是温控器跳闸的问题，一般好点的电热水器都有双温控器，也就是常温温控和超温温控，这两种温控是一种控制你热水器水温的显示和控制的，一种是避免常温温控出问题的时候，给你跳闸用的。也就是双保险，有些因为温控跳闸也会直接导致无法烧热水。叫专业人员开机很快就弄好了。4、还有就是看热水管是否堵塞(或者停水)，停水会直接导致热水器无法使用，因为电热水器的原理就是冷水顶着热水跑的，看下热水器的进水口是否堵住。热水器效果图二、热水器不出热水解决方法还有就是如果出现了温控器跳闸的问题，一般好点的电热水器都有双温控器，也就是常温温控和超温温控，这两种温控是一种控制你热水器水温的显示和控制的，一种是避免常温温控出问题的时候，给你跳闸用的。还有就是看热水管是否堵塞或者停水，停水会直接导致热水器无法使用，因为电热水器的原理就是冷水顶着热水跑的，看下热水器的进水口是否堵住。有些因为温控跳闸也会直接导致无法烧热水。叫专业人员开机很快就弄好了。关于电热水器不出热水的信息就为大家介绍到这里了，希望这篇文章对大家有所帮助。更多资讯，请继续关注。即热式饮水机不出水怎么办 即热式饮水机原理是什么即热式饮水机偶尔也会出现不出水的状况。小编为大家介绍一下 即热式饮水机不出水该怎么办，以及介绍即热式饮水机的原理。一、即热式饮水机不出水怎么办1、饮水机热水口出不了水，多半是出现了故障所造成的，需要进行仔细的排查，确定不出水的原因，然后针对性的进行解决，如果自己解决不了，最好是到购买饮水机的地方找专业的维修工进行修理。2、热水口不出水，首先想到的原因应该是水龙头堵塞，这个时候自己是没有工具进行清理的，可以找维修工人进行处理;如果打开饮水机后盖发现，内部的水管打结了，那么就需要更换新的水管了，完成后热水口才会继续出水。3、出水口堵塞，这是由于在长期使用过程中没有及时对饮水机进行清理的缘故，很多水垢会附着在上面，造成出水困难，所以平时应该每隔一段时间就及时清理出水口或者其它有水渍的地方。二、即热式饮水机原理是什么1、即热式饮水机是一种热水无需等待，即按即出，不用反复加热区别于传统饮水机的一种高科技智能创新饮水机。一般使用时电压大约为：220v左右，功率大约为2200W左右。即热式开水器能在高功率状态下，利用一种导热性较强的加热体，通过电能转化为热能，热能再把热量传递到水中，利用强大的热量可以将水迅速加热。2、即热式饮水机的工作原理是利用控制模块控制水泵工作，向加热器不断的注入冷水，同时控制模块接通加热器的加热电源，冷水流过加热器的同时就被加热了，通过管道流出的就是热水。3、当水箱注满时，冷水箱与煮水箱平衡，加热时，煮水箱水温沸腾到沸点，开水沸腾至开水箱，同时煮水箱水位降低，冷水箱自动补水，如此循环，保证连续不断的提供一次性沸腾新鲜开水，绝无生水混合，无需保温耗电，比传统的开水器节能60%。当遇到即热式饮水机不出水的状况时，可以尝试以上办法。

酶为什么要低温保存：特征物理常数　　温度对酶反应速率有很大的影响，有一个最适温度，在最适温度两侧，反应速率都比较低。　　温度对酶促反应速率的影响有两方面：一方面是当温度升高时，反应速度也加快，这与一般化学反应一样。另一方面，随温度升高而使酶逐步变性，即通过减少有活性的酶而降低酶的反应速度。酶的最适温度就是这两种过程平衡的结果，在低于最适温度时，前一种效应为主，在高于最适温度时，后一种效应为主，因而酶活性迅速丧失，反应速率很快下降。　　最适温度不是酶的特征物理常数，而是上述影响的综合结果，它不是一个固定值，而与酶作用时间的长短有关，酶可以短时间耐受较高的温度，然后当酶反应时间延长时，最适温度向温度降低的方向移动。因此，严格地说，仅仅在酶反应时间已经规定了的情况下，才有最适温度。　　解释：最适温度不是酶的特征物理常数，而是上述影响的综合结果，它不是一个固定值，而与酶作用时间的长短也有关，也就是说，对酶的活性来说保存时间长，最适温度会变低，所以可以解释低温更有利于保存。　　另外，酶在干燥的情况下，比潮湿情况下，对温度的耐受力要高，所以制成干粉的酶制剂更易于保存。　酶的不同保存方法：　　⑴低温下保存：由于多数蛋白质和酶对热敏感，通常35℃～40℃以上就会失活，冷藏于冰箱一般只能保存一周左右，而且蛋白质和酶越纯越不稳定，溶液状态比固态更不稳定。因此通常要保存于-5℃～-20℃，如能在-70℃下保存则最为理想。极少数酶可以耐热：如核糖核酸酶可以短时煮沸;胰蛋白酶在稀HCl中可以耐受90℃;蔗糖酶在50℃～60℃可以保持15 min～30 min不失活。还有少数酶对低温敏感，如鸟肝丙酮酸羧化酶25℃稳定，低温下失活，过氧化氢酶要在0℃～4℃保存，冰冻则失活，羧肽酶反复冻融会失活等　　⑵制成干粉或结晶保存：蛋白质和酶固态比在溶液中要稳定的多。固态干粉制剂放在干燥剂中可长期保存，例如葡萄糖氧化酶干粉0℃下可保存2年，-15℃下可保存8年。通常，酶与蛋白质含水量大于10%，室温低温下均易失活，含水量小于5%时，37℃活性会下降，如要抑制微生物活性，含水量要小于10%，抑制化学活性，含水量要小于3%。此外要特别注意酶在冻干时往往会部分失活。　　⑶在保护剂下保存：很早就有人观察到，在无菌条件下，室温保存了45年的血液，血红蛋白仅有少量改变，许多酶仍保留部分活性，这是因为血液中有蛋白质稳定的因素，为了长期保存蛋白质和酶，常常要加入某些稳定剂：例如：　　①惰性的生化或有机物质：如糖类、脂肪酸、牛血清白蛋白、氨基酸、多元醇等，以保持稳定的疏水环境。　　②中性盐：有一些蛋白质要求在高离子强度(1 mol/L～4mol/L或饱和的盐溶液)的极性环境中才能保持活性。最常用的是：MgSO4、NaCl、(NH4)SO4等。使用时要脱盐。　　③巯基试剂：一些蛋白质和酶的表面或内部含有半胱氨酸巯基，易被空气中的氧缓馒氧化为磺酸或二硫化物而变性，保存时可加入半胱氨酸或巯基乙醇。

记得有位老师讲过alone和lonely的区别：身处人群，你不是alone,但你却可能longly。在加点不那么浪漫的解释吧alone和lonely首先要从意思上来做一个区别。aloneadj.单独的,独一无二的,孤独的,独自的adv.独自地lonelyadj.孤独的,寂寞的,偏僻的,人迹罕至的可见,两者的共同点在于都表示"单独",而不是"一起"但是，在表示单独的同时，还有更深入的区别，即lonely还表示一种心理上的感觉——“孤独”。而alone没有这一层意思。例如：shelivesalone,butshedoesn"tfeellonely.她独自住着，但并不感到孤独。lonely指人孤独寂寞，指地方荒芜人烟，有浓厚的伤感色彩，可做定语或表语。alonelyvillage孤寂的村庄。alonelyman一个孤独的人另外需要特别注意的一点是：alone是一个表语形容词，就是说它只能做表语，而不能作定语修饰名词或代词。例如：analoneman，这个说法是错误的。lone,可以指人孤独，物是单独一个，但它是一个定语形容词，即只能做定语。例如，alonetreeinthegardenalonefiguretrudgingthroughthesnow一个步履艰难独自走在雪地中的人。

耐克标志是迈凯伦汽车。迈凯伦(McLaren)，是属于英国豪华超级跑车品牌；迈凯伦的标志，在车身外是“McLaren”字母为主，在汽车内饰是以“弯月设计”形状为主；迈凯伦最早标志设计于1963年，厂徽设计成通用电气鸟，布鲁斯·迈凯伦家乡新西兰的国鸟。迈凯伦汽车的特点迈凯伦汽车使用了迈凯伦轻量化碳纤维架构（MCLA），同时加入了Ultimate系列车型中的混动系统。除此之外，由空气动力学决定的外观、高级驾驶辅助系统等技术一应俱全，追求科技的迈凯伦再一次将其旗下的超级跑车武装到脚，而它背后传递出的信息也似乎颇有深意。以上内容参考：百度百科-迈凯伦

I"m sorry for everythingOh everything I"ve doneI am out of touchI am out of my place when I keep saying that I"m looking for an empty spaceOh I"m wishing you"re here but I"m wishing you"re goneI can"t have you and I"m only gonna do you wrongOh I"m going to mess this up oh this is just my luck over and over and over againI"m sorry for everything oh everythingI"ve done from the second that I was born it seems I had a loaded gunAnd then I shot shot shot a hole through everything I loveDo I shot shot shot a hole through every single thing that I lovedI am out of luck I am waiting to breakWhen I keep saying that I"m looking for a way to escapeOh I m wishing I had what I"d taken for grantedI can"t help you when I"m only gonna do you wrongIn the meantime can we let it go at the road side that we used to knowWe can let this drift awayWe let this drift away at the bayside where you used to show in the moon lightWhere we let it go we can let this drift awayOh we let this drift away and there"s always time to change your mindOh there"s always time to change your mindOh love can you hear me oh let it drift away

惊喜、惊吓。英文怎么写 surprise scare 惊吓这个英文单词怎么写 frightened scare frighten惊吓的英语怎么说 shock 英语中所以有关惊吓。恐惧的词有那些 terror fright scare spooky horror 惊吓的英语翻译 惊吓用英语怎么说 惊吓_有道词典 惊吓 scare；frighten更多释义>> [网络短语] 惊吓 startle;scare;frighten 惊吓展示 startle displays 收到惊吓 Shock received;Received a fright;Receive a shock 详细用法>> 受惊吓的英语翻译 受惊吓用英语怎么说 受惊吓_有道词典 受惊吓 sweat from every pore更多释义>> [网络短语] 受惊吓 scare;sweat from every pore;frighten 受了惊吓的 terrorstricken 未受惊吓的 unscared

惯性吧?

燃气热水器你的事3个旋钮的吗？如果是有个水温调节时管过水量的，再者本身燃气热水器冷水进口有过滤网，也有可能是滤网堵塞，本身冷水进去再绕个圈水流量就会减少~~希望可以帮到你，，，，，，

酶制剂是一类比较特殊的食品添加剂，主要成分是具有各种催化活性的酶蛋白。酶制剂是食品添加剂中发展迅速的行业，作为一种食品添加剂，与传统的化学法，如酸法、碱法加工食品相比，酶技术具有显著的优越性，一是酶本身无毒、无味、无嗅，不会影响食品的安全性和食用价值；二是酶具有高度催化性，低浓度的酶也能使反应快速进行；三是酶作用时所要求的温度、pH值等条件温和，不会影响食品质量；四是酶有严格的专一性，在成分复杂的原料中可避免引起不必要的化学变化；五是酶反应终点易控制必要时通过简单的加热方法就能使酶制剂失活，终止其反应。因此，酶工程技术在食品的各个领域得到了广泛应用，如在食品制造、品质改良、提高产品附加值等方面。1．酶制剂在食品加工上的应用利用凝乳酶生产奶酪，淀粉酶可液化、糖化淀粉，促进酵母菌的生长，进而生产啤酒、酒精，如果利用棕榈油与硬脂酸进行酶交酯化，就可制得类似可可脂的产品—类可可脂或代可可脂。通过不同的淀粉酶分解淀粉，可以生产出麦芽糊精、麦芽糖浆、麦芽糖和果糖等甜味剂，分别用于糖果、冰淇淋、饮料等各类食品的加工。用橙皮苷酶和橙皮苷反应可以生产橙皮素—F—葡萄糖苷二氢查耳酮，其是对人体安全的甜味剂，甜度为蔗糖的70～100倍[1]。酶制剂还可以用于异麦芽低聚糖、海藻糖、帕拉金糖、低聚果糖、低聚木糖、大豆低聚糖等功能性低聚糖的制造。酶制剂在起酥油和人造奶油的生产方面也有很好的应用。以大豆油为原料氢化生产出来的人造奶油会产生反式酸，已证明其对人体有害。利用酶制剂进行酯交换生产则可以避免产生反式脂肪酸，目前已有企业开始利用此技术进行不含反式脂肪酸的人造奶油的生产[2，3]。2．酶制剂在食品保鲜中的应用酶制剂保鲜的原理是利用酶的催化作用，防止或消除外界因素对食品的不良影响，从而保持食品原有的品质。酶制剂本身的一系列特性使其在食品保鲜中的应用较其他方法有优势。目前应用较多的是葡萄糖氧化酶和溶菌酶的保鲜技术。葡萄糖氧化酶对食品有多种作用，作为在食品保鲜及包装中最大的作用是除氧，延长食品的保鲜保质期。很多食品，尤其是生食品，其保藏过程中或加工过程中，氧的存在使其保鲜受到很大影响，除氧是食品保藏中的必要手段。很多除氧方法效果都不佳，从选择抗氧剂的特性来说，利用葡萄糖氧化酶除氧是一种理想的方法。如在啤酒加工过程中加入适量的葡萄糖氧化酶可以除去啤酒中的溶解氧和瓶颈氧，阻止啤酒的氧化变质，而且不会对啤酒中的其他物质产生作用。因此葡萄糖氧化酶在防止啤酒老化、保持啤酒风味、延长保质期有显著的效果

you are not alone michael jacksonanother day has gonei"m still all alonehow could this beyou"re not here with meyou never said goodbyesomeone tell me whydid you have to goand leave my world so coldeveryday i sit and ask myselfhow did love slip awaysomething whispers in my ear and saysthat you are not alonefor i am here with youthough you"re far awayi am here to staybut you are not alonefor i am here with youthough we"re far apartyou"re always in my heartbut you are not alone"lone,"lonewhy,"lonejust the other nighti thought i heard you cryasking me to comeand hold you in my armsi can hear your prayersyour burdens i will bearbut first i need your handthen forever can begineveryday i sit and ask myselfhow did love slip awaysomething whispers in my ear and saysthat you are not alonefor i am here with youthough you"re far awayi am here to stayfor you are not alonefor i am here with youthough we"re far apartyou"re always in my heartfor you are not alonewhisper three words and i"ll come runnin"and girl you know that i"ll be therei"ll be thereyou are not alonefor i am here with youthough you"re far awayi am here to stayfor you are not alonefor i am here with youthough we"re far apartyou"re always in my heartfor you are not alonefor i am here with youthough you"re far awayi am here to stayfor you are not alonefor i am here with youthough we"re far apartyou"re always in my heartfor you are not alone...

《Shots》是美国乐队Imagine Dragons于2015年发行的新单曲，收录在他们的第二张录音室专辑《Smoke + Mirrors》中，是本专辑的第三支单曲。

一个浓度？

1868年，在英国伦敦有位叫本杰明莫恩的画家发明了第一台不使用固体燃料的瞬时热水器，并命名为“间歇泉”。1899年，意大利人——德尔.奥斯卡研发出世界第一台oscaritaly牌直排式燃气热水器。20世纪70年代初期，周总理去欧洲访问，回途经香港时一位进步人士送他两台5升直排式热水器。回到北京后责成相关人士开发此产品，在周总理的关注下，现代热水器进入普通百姓家的大门慢慢被打开了；1979年，中国第一台燃气热水器在南京市玉环热水器厂研制成功，标志着中国人民用锅烧水洗澡的时代已经结束了，老百姓的洗浴生活进入了一个新的时代；中国燃气热水器经历了直排，烟道，强排，平衡，户外式5个阶段，每步都是一次技术突破，都是在洗浴“安全”和“舒适”上的一次迈进。其中直排式热水器到2000年6月完成了历史使命，被国家强行禁止销售，使用；中国的燃气热水器执行标准也经历了“86标准，94标准，2001标准，2007标准”四个标准，每一次标准的更新，都标志着中国在燃气热水器的设计和制造水平上了一个新的台阶，同时也提高了行业的进入门槛发展前景节能减排是国家倡导的发展方向，具有更少能源消耗量的产品将是未来发展的一个方向。太阳能热水器和空气能热水器作为低能耗的产品发展势头较好。然而，由于产品自身的一些限制，产品在满足消费者需求上有一定的局限，于是综合能源利用成为了热水器发展的另一个方向。前瞻网认为，作为新能源产品的太阳能热水器和空气能热水器正展现出强劲的发展势头，两种品类因其独特的性能迅速拓展市场，在消费者当中有较强烈的反响。工作原理燃气热水器的基本工作原理是冷水进入热水器，流经水气联动阀体在流动水的一定压力差值作用下，推动水气联动阀门，并同时推动直流电源微动开关将电源接通并启动脉冲点火器，与此同时打开燃气输气电磁阀门，通过脉冲点火器继续自动再次点火，直到点火成功进入正常工作状态为止，此过程约连续维持5~10秒时间，当燃气热水器在工作过程或点火过程出现缺水或水压不足、缺电、缺燃气、热水温度过高、意外吹熄火等故障现象时，脉冲点火器将通过检测感应针反馈的信号，自动切断电源，燃气输气电磁阀门的缺电供给的情况下立刻回复原来的常闭阀状态，也就是说此时已切断燃气通路，关闭燃气热水器起安全保护作用。通常一台合格的燃气热水器，指各项性能指标符合GB6932-2001《家用燃气快速热水器》国家标准要求的燃气热水器，从点火状态到进入正常工作状态的整个过程是全自动控制，无需人为调整或附加设置，只要打开冷水开关或接通冷水水源，通过水量调节装置和气量调节装置调节得到合适的水量与水温，燃气热水器就立刻在5~10秒较短的时间内进入正常工作状态，同时产出热水，一旦出现以上意外故障，燃气热水器将会在10秒内自动停止工作，并立刻切断燃气通路，防止燃气继续流出，且不能自动重新开启，除非人为地排除以上故障后再重新启动燃气热水器，方能正常工作状态，因此，其工作性能较为安全可靠。结构编辑基本结构主要是由阀体总成、主燃烧器、小火燃烧器、热交换器、安全装置等组成。（还包括烟道式热水器烟道、强排式热水器的强排装置。阀体总成控制着整个热水器的工作程序，它包括水阀、气阀、微动开关和点火器等。热水器安装时，进水管、出水管、燃气管上都应该安装阀门。使用热水器时，先打开燃气阀和进水阀。当打开出水阀时，点火器和微动开关控制先点燃小火，再点燃主火。采用电子脉冲点火器，该种点火器方便省时，只需用手指按动就可以，并且安全性高，不会出现因意外熄火出现的安全事故，一旦出现熄火的状态，控制系统能及时关闭电磁阀，关断燃气通路。而有的热水器不设小火，可直接点燃主火。燃气在燃烧室内燃烧，热量通过热交换器将水加热，热水从出水口源源不断流出。关断出水阀，热水器停止工作。燃气热水器一般包括：外壳、给排气装置、燃烧器、热交换器（俗称水箱）、气控装置、水控装置、水气联动装置和电子控制系统等。具体结构组成主要如外壳、面壳、开关旋钮、烟管（强排烟管）、风扇电动机（可选）、风压开关、热交换器、温控器、燃烧器、水气联动阀门、电磁阀、排风罩、点火机、离子火焰感应针、脉冲发生器、底壳固定板、电控器、 底壳等。家用燃气热水器的控制系统是一个电子控制系统，一般带有一个火焰检测装置和一个控制装置。控制系统具有电子点火、熄火保护、安全中断、出水恒温、过热保护、不完全燃烧保护功能，还具有再点火、人机电话显示、报警功能和遥控功能，燃气热水器有时序控制器、数字控制器和模糊控制器三种。燃气热水器的感应元器有水流量传感器、离子火焰感应器、温度传感器、热电偶、微动开关、干簧管、霍尔传感器等。其作用是将反应热水器工作情况的有关信息转换成电信号，以便实现对热水器工作状态的控制。内部结构1、集烟罩：顾名思义，收集烟气专用。冷凝式产品的集烟罩较长，并且被进水管包围，这样用烟气的热量预热了冷水。2、底壳：没什么好说的，固定内部配件和挂墙专用。3、CO报警装置：有的产品是自带的，有的产品没有。4、加热防冻保护装置：这个保护装置的原理就是一个电加热丝，一旦检测到环境温度达到冰点，立即开始加热，保护水箱不被冻坏。5、燃烧器：火排在里面，不锈钢制成。6、分配器：就是咱们前面说的分段燃烧，就是用这个控制的，一个电磁阀控制一段火焰。7、比例阀：调节燃气输出的比例，以前的机械式旋钮产品没有这个，那个是用的水气联动控制的。8、风机：将空气鼓入燃烧室内，这张图是强鼓式的，强抽式的产品只不过风机在顶端，效果就是强鼓式的鼓风强些，抽烟弱些，强抽式的反之，我个人更喜欢强鼓式产品。9、温度传感器：检测出水温度。10、出水接头：连接热水软管。11、泄压放水塞：可以将内部的残留的水放掉。12、电源插头：大家尽量选择带漏电保护器的产品。13、进气接头：连接高气管。14、进水接头：连接冷水软管。15、调水旋钮：可以调节进水的大小。16、水量传感器：是由霍尔传感器和水流转子组件构成。17、变压器：调节到合适的电压供给电机和内部电路使用。18、点火器：这个其实也相当于调试器。19、点火针：前面很尖，电离空气产生火花从而点燃燃气。20、感应针：检测火焰是否燃烧。21、控制器：里面有电路板和电子元件，用来实现自动控制。22、热交换器：又称为水箱，但它不储水，铜制的最好，由盘管、翅片和外壳组成。23、防干烧温控器：当温度超过限定温度后，就会自动断开电路。24、防冻温控器：当温度低于限定温度后，就会自动断开电路。优点与缺点燃气热水器就是采用燃气作为主要能源材料，通过燃气燃烧产生的高温热量传递到流经热交换器的冷水中以达到制备热水目的的一种热水器。燃气型热水器是曾经占领热水器市场的主流热水器，其优点就是即开即用，无需等待，而且占地面积较小，对于在天朝蜗居的同志们来说能节省很多空间；不足就是相比较电热水器和太阳能热水器来说，安全系数不够高，尤其是在密闭的空间里发生燃气泄漏的话，后果将非常严重，这也就成了燃气型热水器使用率逐年下降，电热水器后来者居上的主要原因。这种热水器安装不方便，如今北京必须由燃气管理部门安装才能使用，否则安全无保障。燃气热水器的缺点也是很明显的。首先不宜装在浴室或离厨房较远的地方，因为原则上燃气热水器不装在浴室，如果距厨房较远的话，热水管道太长，中间就会白白消耗大量的水资源。另外，不便之处是使用者不能在洗浴过程中自己调节温度，而必须在进入浴室前先将温度调好，并且温度会忽冷忽热，不过出现的恒温燃气热水器解决了这个问题。燃气热水器偶尔还会出现打不着火的问题。

限制性核酸内切酶（以下简称限制酶）：限制酶主要存在于微生物（细菌、霉菌等）中。一种限制酶只能识别一种特定的核苷酸序列，并且能在特定的切点上切割DNA分子。是特异性地切断DNA链中磷酸二酯键的核酸酶（“分子手术刀”）。发现于原核生物体内，现已分离出100多种，几乎所有的原核生物都含有这种酶。是重组DNA技术和基因诊断中重要的一类工具酶。例如，从大肠杆菌中发现的一种限制酶只能识别GAATTC序列，并在G和A之间将这段序列切开。目前已经发现了200多种限制酶，它们的切点各不相同。苏云金芽孢杆菌中的抗虫基因，就能被某种限制酶切割下来。在基因工程中起作用。DNA连接酶：主要是连接DNA片段之间的磷酸二酯键，起连接作用，在基因工程中起作用。DNA聚合酶：主要是连接DNA片段与单个脱氧核苷酸之间的磷酸二酯键，在DNA复制中起做用。DNA聚合酶只能将单个核苷酸加到已有的核酸片段的3′末端的羟基上，形成磷酸二酯键；而DNA连接酶是在两个DNA片段之间形成磷酸二酯键，不是在单个核苷酸与DNA片段之间形成磷酸二酯键。DNA聚合酶是以一条DNA链为模板，将单个核苷酸通过磷酸二酯键形成一条与模板链互补的DNA链；而DNA连接酶是将DNA双链上的两个缺口同时连接起来。因此DNA连接酶不需要模板。RNA聚合酶（又称RNA复制酶、RNA合成酶）的催化活性：RNA聚合酶以完整的双链DNA为模板，转录时DNA的双链结构部分解开，转录后DNA仍然保持双链的结构。真核生物RNA聚合酶：真核生物的转录机制要复杂得多，有三种细胞核内的RNA聚合酶：RNA聚合酶I转录rRNA，RNA聚合酶II转录mRNA，RNA聚合酶III转录tRNA和其它小分子RNA。在RNA复制和转录中起作用。反转录酶：RNA指导的DNA聚合酶，具有三种酶活性，即RNA指导的DNA聚合酶，RNA酶，DNA指导的DNA聚合酶。在分子生物学技术中，作为重要的工具酶被广泛用于建立基因文库、获得目的基因等工作。在基因工程中起作用。解旋酶：是一类解开氢键的酶，由水解ATP来供给能量它们常常依赖于单链的存在，并能识别复制叉的单链结构。在细菌中类似的解旋酶很多，都具有ATP酶的活性。大部分的移动方向是5"→3"，但也有3"→5"移到的情况，如n"蛋白在φχ174以正链为模板合成复制形的过程中，就是按3"→5"移动。在DNA复制中起做用。DNA限制酶作用于磷酸二酯键DNA连接酶作用于磷酸二酯键DNA聚合酶作用于磷酸二酯键DNA解旋酶作用于氢键酶有的是蛋白质，有的是RNA大部分是蛋白质高中涉及到的……DNA连接酶：基因工程中用到RNA聚合酶：遗传信息转录中，DNA-->mRNA的过程中DNA解旋酶：DNA复制时，解开双链用到限制性内切酶：基因工程剪切粘性末端。一种对应一种碱基序列胰蛋白酶：胰腺分泌的消化蛋白质的酶

惯性

迈凯伦汽车商标设计理念：迈凯伦汽车标志从设计上看由英文名称Mclaren和代表速度的抽象光束图形的组合构成，代表速度的光束很好的诠释了迈凯伦汽车跑车的定位，光束图形为应用在汽车上的标志。整体以红色为识别色，红色寓意激情。

找个万用表 试试就知道了

感应器灯亮出水关不了怎么办