java中几种Map在什么情况下使用，并简单介绍原因及原理

性质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的概念及用途，添加删除结点的原理。

二分法平均查找效率是O(logn)，但是需要数组是排序的。如果没有排过序，就只好先用O（nlogn)的预处理为它排个序了。而且它的插入比较困难，经常需要移动整个数组，所以动态的情况下比较慢。哈希查找理想的插入和查找效率是O(1)，但条件是需要找到一个良好的散列函数，使得分配较为平均。另外，哈希表需要较大的空间，至少要比O(n)大几倍，否则产生冲突的概率很高。二叉排序树查找也是O(logn)的，关键是插入值时需要做一些处理使得它较为平衡（否则容易出现轻重的不平衡，查找效率最坏会降到O(n)），而且写起来稍微麻烦一些，具体的算法你可以随便找一本介绍数据结构的书看看。当然，如果你用的是c语言，直接利用它的库类型map、multimap就可以了,它是用红黑树实现的，理论上插入、查找时间都是O(logn)，很方便，不过一般会比自己实现的二叉平衡树稍微慢一些。

不会。计算机考研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 容器实现。当然在创建一个适配器时也可以指定具体的实现容器，创建适配器时在第二个参数上指定具体的顺序容器可以覆盖适配器的默认实现。 由于适配器的特点，一个适配器不是可以由任一个顺序容器都可以实现的。

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

以一个生活中的例子来解释.假设你在大学中读书,要等待一个朋友来访,而这个朋友只知道你在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最大吞吐量的情况下，尽量使远端请求在一个期限内被调度而不被饿死的调度器。

在任何化学反应中，反应物分子必须超过一定的能阈，成为活化的状态，才能发生变化，形成产物。这种提高低能分子达到活化状态的能量，称为活化能。催化剂的作用，主要是降低反应所需的活化能，以致相同的能量能使更多的分子活化，从而加速反应的进行。　　酶能显著地降低活化能，故能表现为高度的催化效率。例如前述的H2O2酶的例子，可以显著地看出，酶能降低反应活化能，使反应速度增高千百万倍以上。酶作用机理　　1.趋近效应（approximation）和定向效应（oientation）酶可以将它的底物结合在它的活性部位由于化学反应速度与反应物浓度成正比，若在反应系统的某一局部区域，底物浓度增高，则反应速度也随之提高，此外，酶与底物间的靠近具有一定的取向，这样反应物分子才被作用，大大增加了ES复合物进入活化状态的机率。　　2.张力作用（distortionorstrain）　　底物的结合可诱导酶分子构象发生变化，比底物大得多的酶分子的三、四级结构的变化，也可对底物产生张力作用，使底物扭曲，促进ES进入活性状态。　　3.酸碱催化作用（acid-basecatalysis）　　酶的活性中心具有某些氨基酸残基的R基团，这些基团往往是良好的质子供体或受体，在水溶液中这些广义的酸性基团或广义的碱性基团对许多化学反应是有力的催化剂。　　4.共价催化作用（covalentcatalysis）　　某些酶能与底物形成极不稳定的、共价结合的ES复合物，这些复合物比无酶存在时更容易进行化学反应。　　例如：无酶催化的反应　RX+H2O→ROH+Hx慢　　有酶存在时　RX+E桹H→ROH+EX快　　EX+H2O→E桹H+HX快?

漂移有很多种方式，手刹漂移最容易做出，提起手刹后，四个车轮瞬间刹死，车子会因为惯性产生漂移，此时松手刹迅速提速，如果是自动挡，漂移后会失去速度，这样漂移就很难看了，手动挡漂移后可以用低挡位大扭矩迅速提速出弯，自动挡就不行，这还关系到汽车是前驱还是后驱，如果是前驱，漂移就很需要技术了，一般人做不来，总之，漂移什么车都能做，重要的事做的漂不漂亮，没有一定技术，自动挡的车漂移不好看

呃··· 要这个干什么············· 我这里只有五（上）的，不知道你要不要。young funny tall strong short Canada know principal university student strict smart active Monday Tuesday Wednesday Thursday Friday Moral Education Social Education tomorrow have do homework Saturday Sunday often play computer games do housework cabbage pork mutton eggplant potato tomato healthy lunch tasty favorite grape now have to empty the trash cook thr meals water the flowers sweep the floor do the dishes set the table have a try use a computer air-conditioner end table helpful put away the clothes kitchen living room in front of mountain building bridge forest nature park 希望对你有用。

"漂移"一词一般是指汽车打侧车身过弯的动作,但其实漂移的方法是因车而异的,以下就 是一些常见的漂移方法: 手掣旋转: 这是池谷曾经苦练的招式,其原理就是以Hand Brake煞车,锁死后轮使之失去抓地力而作圆周运动,由于车辆是在一瞬间急 煞,因此车身摆动幅度很大,所以这种漂移是很好看的,不过只是仅此而已...因车辆在出弯时需要重新加速,往往得不偿失...不过这种初级的漂移总比拓海 的漂移易控制和安全. Power Drift: Power Drift是指转弯时踏尽油门,以强大的动力强迫驱动轮空 转,使其失去抓地力,而以离心力做出漂移的动作,在出弯时松油门就可使轮胎回复抓地力. 要做到Power Drift必须要有强大的驱动力,因此4WD是最适合做Power Drift的. (须藤京一和岩城清次所用的过弯 方法便是Power Drift),FR也可以做Power Drift,但必 须要有足够的马力,像86这些车就不行了. Brake Drift: Brake Drift就是拓海常用的煞车漂移技术,原理其实和Power Drift差不多,就是以煞车使重心移前,同时锁死后轮使其失去抓地力,但Brake Drift的 掌握则比较难,因为煞车的控制要掌握得很好,否则会导致转向不足而出意外... 其实若漂移掌握得好,在多弯的山路是有可能比较快,但只限于阁下有拓海般的技术及 高桥凉介般有钱,因为漂移得太多只会造成轮胎的损耗,不但减 慢车速,也要经常换胎... R32战败之迷 R32马力强劲,直路弯角同样出色,为何仍会败给 86呢?原来它的弱点在于车头太重, 它是大排气量前置往后复引擎车,先天性重心己偏前, 相比一般FR(前偈后驱)车,它需要负担多一套前轮传动系统,令车头重上加重,加上车在 下斜时重心会移前,转向不足 的情况便会出现,这是其中一个致命伤.另一个弱点是, 当车手为修正轨迹重踏脚掣煞车时,重心进一步移前,前轮负担因而过重,操控准绳度便会大幅度降低.所以,无敌 战神亦非永远不败. FF车为何不擅长漂移 FF(前偈前驱)车并不擅长漂移,原因就在于FF车的引擎放在车 头,车重集中在前面,车尾便变得很轻,而漂移的动作首先就要将车尾向外甩,车尾太 轻,甩的幅度就不会大,这样就容易做成转向不足;当然,只要扭呔扭多一点,要甩还是可以的,但由于车尾太轻,甩的时候便会摇摆不定,容易失控. 各位若对自己的驾驶技术充满信心,可即管试试用FF车漂移,不过请先为自己买保 险(人寿保险)... 牛皮胶纸死亡赛为何对FF有利 FF(前偈前驱)车不擅长漂移,但是当要绑著右手在呔盘上比赛 时,这就完全对FF有利了. 漂移本身就是要先踩Brake同时扭呔,让车尾向外甩而进入漂移状态,再大幅度向相 反方向扭呔,这样就能使车身顺著前轮的方向滑动;若将右手绑在呔盘上,即表示不 能换手扭呔,这样要回呔便难得多,回呔幅度不够,便会造成转向不足(拓海便差点在第一个弯出意外了...),因此漂移的难度大大提升;相反FF车由于车尾轻,本 身就难以做到漂移,这样反而减少汽车因漂移而出意外的机会,只要切切实实的过弯就行了.若车速太高,FF车只要用手掣或Brake去减低车速就可以;FR 就不行了,因煞车这个动作本身就是漂移的第一个步骤,若转弯时企图用Brake减低 车速,较重的车尾便会向外甩而进入漂移状态...(紧接著的就是发生交通意外);而FF 车不易漂移,因此较少机会失控. 另外,FF车的前轮兼负转向和动力传送,动力输出直接,失控的时候容易救车,这也有 利于FF车 漂移的定义 漂移(drift,drifting)是赛车术语，指让车头的指向与车身实际运动方向之间产生较大的夹角，使车身侧滑过弯的系列操作。其目的是为了克制过弯时的转向不足，提高过弯速度，同时也增加了赛车运动的观赏性。 漂移产生的条件 漂移产生的条件归咎到底就是一个：后轮失去大部分(或者全部)抓地力，同时前轮能保持抓地力(最多只能失去小部分，最好是获得额外的抓地力)；这时只要前轮有一定的横向力，车就甩尾，即可产生漂移。 令后轮失去抓地力的方法 1.行驶中使后轮与地面间有负速度差（后轮速度相对低） 2.任何情况下使后轮与地面间有正速度差（后轮速度相对高） 3.行驶中减小后轮与地面之间的正压力。 这三项里面只要满足一项就够，实际上1，2都是减小摩擦系数的方法，将它们分开，是因为应用方法不同。 保持前轮抓地力的方法 1.行驶中不使前轮与地面间有很大的速度差 2.行驶中不使前轮与地面间正压力减少太多，最好就是可以增大正压力。这两项要同时满足才行。 实际操作里面，拉手刹就一定同时满足行驶中使后轮与地面间有负速度差（后轮速度相对低）行驶中不使前轮与地面间有很大的速度差。 产生漂移的方法有 1.直路行驶中拉起手刹之后打方向 2. 转弯中拉手刹 3. 直路行驶中猛踩刹车后打方向 4. 转弯中猛踩刹车 5.功率足够大的后驱车（或前后轮驱动力分配比例趋向于后驱车的四驱车）在速度不很高时猛踩油门并且打方向。 其中3，4是利用重量转移（后轮重量转移到前轮上），是最少伤车的方法。1，2只用于前驱车和拉力比赛用的四驱车，而且可免则免，除非你不怕弄坏车。注意1和2，3和4分开，是因为车的运动路线会有很大的不同。重要说明：漂移过弯和普通过弯一样，都有速度极限，而且漂移过弯的速度极限最多只可能比普通过弯高一点，在硬地上漂移过弯的速度极限比普通过弯还低

热水器漏水，不是从进水阀前漏的，而是从进水阀后漏水，燃气热水器就认为你是在用水了，所以就点火了

开心消消乐里面的英文单词：good(好), great(很好), amazing(非常好), Excellent(好极了), crazy(不可思议), unbelievable(难以置信),bonus time(奖励 时间)。开心消消乐在挑战的时候，我们在关卡中消除，总是有许多的英文提示出现，这些英文其实这都是村长给我们的鼓励语，那在什么时候，才会出现这些英文 :1、在游戏的时候，如果消除的分数足够高的话，或者一次消除多种障碍，就会出现鼓励的情况。在打开音效的时候，除了障碍物与动物消除之后的声音，还可以听到动听的鼓励声。2、在消除关卡的时候，大量的消除就会产生大量的分数，这个时候，会出现good(好), great(很好), amazing(非常好), Excellent(好极了), 不同鼓励的单词。3、超越好友也会出现鼓励，crazy(不可思议), unbelievable(难以置信), 表示超越好友了。4、在关卡结束的时候，如果还有步数没有消除，那就会进入到奖励时间，bonus time(奖励 时间)，在进入到奖励时间之后，剩余的步数就会变成特效，可以获得更多的分数。《开心消消乐》拥有超过600个精心设计的关卡，及5大关卡类型。掉落收集、指定消除、限时关卡……在传统三消玩法基础上，还添加了多种任务目标，玩法更加丰富。30多个新奇有趣的障碍，这些障碍不仅为关卡带来难度和挑战，也带来了不少趣味和惊喜，给玩家带来不断挑战的兴趣和更多成就感；10余种炫目特效，配以悦耳音效，为玩家带来视觉和听觉的双重享受。扩展资料《开心消消乐》的界面设计明了自然，场景清新明丽，小动物Q萌生动，还有各具特色的有趣障碍。《开心消消乐》主要玩法和其他三消除游戏没多大区别，依然是3个相同图形就可以消除，也可以四连、五连、T连或L连等。游戏中丰富的特色道具和特色的开局让游戏有种百玩不厌的感觉，从而深受玩家的喜爱。当你在游戏中消除动物时，会听到一些音效。这些音效是根据你在一步中连消的动物的个数来播放的：1个连消：相当于音乐上刀瑞咪的 叨 的音，2个连消：相当于音乐上刀瑞咪的 瑞 的音,3个连消：相当于音乐上刀瑞咪的 咪 的音，另带一个短的“哇喔~”，本回合结束还有个“good~”的音，就是“好！”4个连消：相当于音乐上刀瑞咪发的 发 的音，另带一个短的“fighting~”的音，就是“战斗吧！”5个连消：相当于音乐上刀瑞咪发嗖的 嗖 的音，另带一个短的“ye!”，本回合结束还有个“great~”的音，就是“伟大！”6个连消：相当于音乐上刀瑞咪发嗖拉稀的 拉 的音，另带一个短的“哇哦~!”的音7个连消：相当于音乐上刀瑞咪发嗖拉稀的 稀 的音，另带一个短的“ye!”，本回合结束还有个“excellent~”的音，意思是“卓越！”8个连消：相当于音乐上刀瑞咪发嗖拉稀多的 多 的音，另带一个短的“animal~!”的音，这个意思不是牲口，也不是畜生……就是动物~9个连消：相当于音乐上刀瑞咪发嗖拉稀多的 多 的音，另带一个短的“animal~!”的音，本回合结束还有个“amazing~!”的音，意思是“神了！”“太神奇了!”10个连消：相当于音乐上刀瑞咪发嗖拉稀多的 多 的音，另带一个短的“animal~!”的音11个连消：相当于音乐上刀瑞咪发嗖拉稀多的 多 的音，另带一个短的“animal~!”的音，本回合结束有个“unbelievable~!”的音，意思是“不可思议！”超过11个连消的音效都和11连消一样~参考资料百度百科—开心消消乐

弹离合（初学级）：能够比较理想的直接破坏掉轮胎的抓地力。通过对离合踏板的踩击导致扭力在传动系统的不均匀传递来使后轮失去牵引力。所谓的踩击的意思就是说：迅速而有力的将离合踏板踹到底，然后再迅速的抬起。一般运用在比较窄，没有足够的空间利用重心转移造成甩尾的入弯处。在低速时进行强力的弹离合，是最直接有效能够在瞬间使节流阀完全开启的办法。而在有一定的速度的基础下或这是正在侧滑的过程中，则要轻而柔和的弹离合。只可能运用在后驱车。 手刹（初学级）：最早是在拉力赛中被运用。在拉起手刹锁住后轮的同时，导致了整个后车身的侧滑开始。因为需要使车尾发生侧滑而刚好甩到一个正确的入弯角度，所以一个很流畅，力度和时间刚好的手刹使用过程是很难掌握的。拉手刹时不要太紧张，不用太狠，也不用太高，足够就好，任何时候都不要松开手刹扣，因为拉手刹的过程并不长，要保证在适当的时候，手刹能够顺畅而快速的放掉。这个基础的技术能够运用在任何速度，任何弯角，任何车，即便是专业的漂移车手也经常会运用手刹在侧滑的过程中来纠正车身侧滑的角度。 锁档（中级）：这是一个在减速过程中的弹离合。以适当的引擎转速接近弯道，迅速的踩击离合器，并且降档，利用引擎的出力来使后轮急剧的减速以致发生侧滑。当然，这对你车子的传动系统来说会比较辛苦。而车子具体的动作，反映和程度，完全取决于车子的种类以及引擎的不同。因为需要有较好的技术控制引擎转速的掉落以及动力回升来达到使车身滑行，所以相对于手刹来说更难于使用。同弹离合一样，只能运用在后驱车！重刹车（中级）：一般运用于较窄的弯位和中速弯。在重踩煞车的情况下冲入弯道，使车子大绝大部分重力抛到前面，而使后轮不受重力而失去抓地力。这项技术经常被运用在赛车场上以来提高入弯的回头性，尤其是四驱（Evo和STI）。在柏油路面练习时如果发现你的车子在合适的入弯速度下严重的出现转向过度的话，那你可能在避震的设定或轮胎的选择上没有搞好，或者你应该换一台更适合的车子。 Lift off 转向过度（上级）：被广泛地运用在高速弯的滑行。利用重力转移使车子从拥有抓地里的状态转变到漂移状态。和重刹车是同样的物理原理—重量转移，但不同的是这项技术被运用在非常高速的情况下，这就需要车手对车子在高速的平衡有着很好地掌握。顶级的D1车手会在漂移的过程中运用具有进攻性的lift off 转向过度来削减动力输出。 钟摆效应（上级）：对头文字D熟悉的朋友应该对“钟摆”这个词有所了解了，这也是一项由拉力技术而衍生出来的。顾名思义，钟摆的意思就是说在入弯之前先将车子向弯的外侧摆动，然后再大幅度转向内侧，在重力转移的作用下破坏轮胎地抓地力而使车身发生侧抛，一般使用在入口的弧度比较小的弯位。配合lift off 转向过度，可以增强彼此的效果。在拉力过程中，钟摆是为了在没有摩擦力的路面上尽可能的增强抓地力，而漂移比赛中使用钟摆则完全因为相反的原因--让车身发生侧抛。钟摆的价值和实用性在于既可以在入弯的时候有效的减速，同时还能保证整个过程的高速状态！ 摆动漂移（上级）：钟摆的最终形态。速度并不快，在道路的两边进行来回的侧摆，是一种直线上的飘移，也叫做“鱼摆尾”（神龙摆尾？），但是这种摆动最难的部分不只是能将车身在高速状态下的重力装移掌握得炉火纯青，还要能够让车身的摆动角度刚好在入弯的时候处于正确的入弯角度和速度。而这一动作的熟练运用也标志着车手技术的全面以及高水准。 打滑（专业）：顶级车手的伎俩，这个技术是指将车子的后轮使入赛道外的土地或者是草地上面，使之在瞬间丧失原有的抓地力，以获得更大的角度。这种特殊而有效的方法一般被运用在那些无法依靠本身引擎马力和速度来破坏抓地力的车子和情况下，或者在入弯时做出更具有攻击性的角度。更多地被运用在后驱车上面。 勤练。

耐克倒钩的车子是迈凯伦。迈凯伦这个被广大车迷俗称“倒钩耐克”的超级跑车，车钥匙的造型当然也不能逊色。作为迈凯伦豪门的创始人。布鲁斯·迈凯伦对F1世界的巨大影响，远远超过了他作为车手取得的所有成绩的总和。50年代中期，迈凯伦在家乡开始了车手生涯。很快，他在1958年赢得了去欧洲参加F2比赛的奖金，迅速上升为单座车手。迈凯伦起源迈凯伦F1其实就是著名的迈凯伦F1跑车,而非一级方程式赛车。Mclaren F1能在3.2秒内从静止加速到100km/h，极速突破386km/h直到2005年。来自瑞典的Koenigsegg公司的CCR终止了Mclaren F1全球最快速度量产跑车的纪录。Mclaren F1曾经是世界上跑的最快的量产跑车，这个纪录从它1994年进入批量生产一直保持到2005年停产，这也使它创造了保持世界最速跑车纪录最久的纪录Mclaren F1由英国著名的赛车研发制造公司迈凯伦（Mclaren）公司打造。公司工程技术人员将大量的F1赛车技术应用到该跑车上，所以其F1的名字也由此而来，可以说它是一台地地道道的街道F1。虽说当今业界有不少车在极速上可以超越Mclaren F1，但是至今它仍然保持着全球最速自然吸气引擎跑车的名号。Mclaren F1搭载了一台6.1升60°夹角V12引擎，这具引擎由宝马公司提供，编号S70/2，这具引擎是当初宝马高端跑车8系所用的发动机衍生过来的。经过特殊的强化调校，专门提供给迈凯伦。据官方资料显示，Mclaren F1一共制造了107台，其中65台作为街道跑车出售，6台供LM型号，3台加长尾翼的GT街道跑车，5台街道原型车，28台GTR型号以及一台勒芒赛车原型车。

酶是动植物和微生物产生的具有催化能力的一类特殊的蛋白质，酶有如此高的活性是因为酶具有特殊的络合物结构排列，即有特定反应的适宜部位。也就是酶在反应中先与反应物结合生成一个中间络合物，然后把应生成产物，而酶又复原，总之还是通过中间络合物降低了反应的活化能。

Jensen不等式，又名琴森不等式或詹森不等式（均为音译）。它是一个在描述积分的凸函数值和凸函数的积分值间的关系的不等式。它的一般形态是：1、当且仅当f ( x ) f(x)f(x)为下凸函数时有2、当且仅当f ( x ) f(x)f(x)为上凸函数时有相关信息数学是人类对事物的抽象结构与模式进行严格描述的一种通用手段，可以应用于现实世界的任何问题，所有的数学对象本质上都是人为定义的。从这个意义上，数学属于形式科学，而不是自然科学。不同的数学家和哲学家对数学的确切范围和定义有一系列的看法。在人类历史发展和社会生活中，数学发挥着不可替代的作用，同时也是学习和研究现代科学技术必不可少的基本工具。

qqid身份卡名字大全1、I-AM-名字缩写：使用【I-AM-名字缩写】的格式当做QID，可以告诉别人自己的名字简称，既简单又大方;2、星座缩写：用自己星座的英文名当做QID，这样的微信号简单又有创意。白羊座Aries ;金牛座Taurus ;双子座Gemini ;巨蟹座Cancer ;狮子座Leo;处女座 Virgo ;天秤座Libra ;天蝎座Scorpio ;射手座Sagittarius ;魔羯座Capricorn;水瓶座 Aquarius ;双鱼座Pisces;3、插入特殊字符：可以在自己的名字中穿插一个下划线，例如韩梅梅：han_meimei，简单又创意，撞QID的几率也比较小;4、拟声词：可以在你的名字缩写后面添加生动的拟声词，表羡慕，满意 ah;表满意，愉快 aha;形容巨响 boom;表惊奇，喜悦 hey;表惊奇 mercy;表惊奇，诧异 oh;表惊奇，高兴 wow;5、英文单词：Shmily：它来源于一个爱情故事，这句话的意思是“See How much I Love You”。Colorful：读出来的口型是“I love you”。Sonder：是指恍然意识到生命中的芸芸过客都有自己波澜壮阔的一生，或坎坷，或惊喜，或惊奇，或神伤，只是我们从未了解。

要用手刹，《头文字D》你仔细看的话里面提到要用手刹的！原理是：后轮失去大部分或者全部抓地力，同时前轮要能保持尽量最多的抓地力，最好当然是能够获得额外的抓地力了，这时只要前轮有一定的横向力，就会产生漂移。实际操作直路行驶中拉起手刹之后打方向盘产生漂移。转弯中拉手刹产生漂移。直路行驶中猛踩刹车后打方向盘产生漂移。转弯中猛踩刹车产生漂移。功率足够大的后驱车（或前后轮驱动力分配比例趋向于后驱车的四驱车）在速度不很高时猛踩油门并且打方向盘产生漂移。

在一个反应体系中，任何反应物分子都有进行化学反应的可能，但并非全部反应物分子都进行反应。因为在反应体系中各个反应物分子所含的能量高低不同。只有那些含能达到或超过某一定限度(称为“能阈”)的活化分子才能在碰撞中发生化学反应。显然，活化分子越多，反应速度越快。活泼态与常态之间的能量差，也就是分子由常态转变为活化状态所需的能量，称为活化能。使反应达到其一定的能阈的途径有二：(1)对反应体系加热或用光照射，从而使反应物分子获得所需的活化能；(2)使用适当的催化剂，降低反应的能阈，使反应沿着一个活化能阈较低的途径进行。酶和一般催化剂的作用一样，就是能降低底物分子所必须具有的活化能。

是生物催化剂酶是活细胞所产生的具有催化能力的一类特殊的蛋白质。提示:取甲、乙两支洁净的试管，分别注入3ml浆糊。然后，在甲试管中注入1ml～2ml新鲜的小麦淀粉酶滤液，在乙试管中注入1ml～2ml清水作为对照。振荡两支试管，将甲、乙两支试管的下半部浸在35℃左右的温水里，保温约5分钟。然后同时取出这两支试管，分别滴入一滴碘液。结果，乙试管内浆糊变成蓝色，而甲试管内的浆糊则不变蓝色。遇着碘液变成蓝色，这是淀粉的特性。甲试管内的浆糊遇碘液不变蓝色，这说明甲试管内的淀粉已经转变成其他物质了。原来，在适宜的温度条件下，小麦淀粉酶能够促使淀粉迅速地水解为麦芽糖。因此，甲试管内的浆糊遇到碘液不变蓝色。以上实验证明酶在适宜的温度和其他条件下，能够使生物体内的许多复杂的化学反应顺利而迅速地进行，而酶本身却不发生变化。因此，酶是生物催化剂

表示问候的英文1.一般性招呼问候语Morning! 早上好!你好! (不如Good morning 正式)Afternoon! 下好!你好! (不如Good afternoon 正式)Evening! 晚上好 / 你好! (不如Good evening 正式)Good morning. 早上好 / 你好!Good afternoon. 下午好 / 你好!Hello [Hallo, Hullo, Hi]. 你好!How are you? 你好吗?How do you do? 你好! (用于第一次见面)Good [Nice] to see you again. 很高兴又见到你!What a pleasant surprise! 真没想到会见到你!2.问候久别朋友,表达好久未见这一含义Haven"t seen you for some time. 好久不见了。Haven"t seen you for a long time. 好久不见了。Haven"t seen you for ages. 好久不见了。Long time no see. 好久不见了。3.问候工作、学习、生活、身体等情况How are you? 你身体好吗?How are you doing? 你过得怎么样?How are things with you? 你好吗?How"s everything with you? 你一切都好吗?How are you getting on? 你过得怎样?How are you keeping? 你过得怎样?How are you ma-ki-ng out? 你过得怎样?How are things going (with you)? 你过得怎样?How"s everything going (with you)? 你一切都好吗?How"s life with you? 你生活过得怎样?How"s life treating you? 你生活过得怎样?How have you been? 近来可好?What"s new (with you)? (你)近况如何?What"s the (good) news? 有什么(好)消息?Anything new? 近来怎样?

我来把我这一年多来练习漂移的经验和知道的要领在这里系统的说一下。首先，我来说说为什么要漂移。 漂移不只是因为好看才发明的，而车辆在失控时的“漂移”现象，也只是能称为侧滑 而已，正如我经常提及的那句话，POWER IS NOTHING WITH OUT CONTROL。漂移也是如此。 只有你能随心所欲的控制了这个技术动作，那时才叫你会漂移，如若不然，只能说你是在练习漂移。而我自己目前，也只是练习漂移而已。那为什么要漂移呢？那就是另车更快的过弯的一种方法，当然，漂移也是一种特技动作，不可否认漂移的确从视觉上和感官上很有吸引力。 也有一种说法，说只有四个轮胎紧咬地面，靠走线位，切APEX，才是最快的过弯方法，漂移过弯比这种走线位的方法慢。其实未必，首先看是什么地面，如果是柏油路，速度非常快，一般走线位比较好，因为这样最安全，速度越快漂移越不好控制。其实只要是高速过弯轮胎多少都会产生漂移，甚至你察觉不到。 这就涉及一个轮胎与地面摩擦力的临界状态，什么是临界状态呢？经过实验。轮胎与地面保持滚动摩擦，也就是基本不打空转的时候摩擦力最大。当轮胎开始打空转，变成滑动摩擦时，摩擦力反而下降20%。所以，当轮胎保持在要滑，又没滑的时候，这就是摩擦力发挥到大极限的时候，ABS也就是根据这发明的。 所以，当你觉得你的轮胎还是紧咬地面时候，说明你还没有把轮胎的的摩擦力发挥到极限。当车漂移的时候，当然是已经超越了最大摩擦力，所以这时速度比咬地时快，如果你能很好的控制漂移的路线，用漂移走出线位来，当然比单纯的咬地要快。这还涉及一个角速度和线速度的问题，太深了就不提了。不过人家真正的高手可以确保用轮胎的临界状态去走线位，那真是最快，咱们普通人就先别要求那么多了。 再说说什么车可以练习漂移，重心高的车不行，比如越野车，SUV，这样的车最好别试，即使是后驱也别试，容易翻车。减震特别软的车，没改装的车不行。也是容易翻，还特别不好控制。还有就是特贵的车，不建议呵呵。撞了心疼。 说完了车，该说地面了，什么地面比较合适呢，本人觉得土路最好，其次是水路，沙石不太好，首先北京就没有沙子路，石头这玩意就算了，除非轮胎不想要了。如果你选择比较平整的柏油路也行，就是需要胆量和技术好一点，因为柏油路需要比较高的速度才行。 对轮胎的磨损也最大。雪路比较特殊，其实雪路我认为是最好玩，难度也比较大的。因为要想漂起来，雪路最容易。最后说说什么车比较适合练习漂移。首选当然是后驱，如果您拥有一台高性能的后驱车，又对漂移有兴趣，那么我恭喜您，这是最好的选择。您也不需要考虑惯性漂移，您只要练会POWERSLIP就够厉害的了，方法N简单，入弯，减档，弯中前段猛加油，产生OVERSTEER(转向过度)后控制方向。 绝对够潇洒。如果您有台比如WRX一般的或者EVO一样的四驱车，那么漂移的方法和前驱基本相同，直接参考前驱就差不多了，其实有的四驱系统和后驱十分相似，是偏向后驱的，可以做和后驱基本一样的动作，这里就不说了，前面都是废话，现在就说前驱吧。 前驱要想做漂移没有足够的速度是不行的，所以比较费劲。首先从拉手刹方法说起,手刹这玩意我现在已经很少用了，用的时候也很小心，主要是因为用手刹不但是笨方法，而且占了一只手，只留一个手扶方向盘。很危险，我那次撞到了弯外的台阶上，就是因为只有一只手扶着方向盘。结果坏了左前避震，左前左后两条轮胎 前保险杠也牺牲了。继续说别的方法，重量转移法。也可以叫负重转移啦，也就是之前我提过的弯前制动和弯内制动法。当你高速入弯之前，车的重量是几乎平均分配在四个轮子的，所以，当你在入弯时，大力踩下刹车。这时车身由于惯性，把部分负重转移到两个前轮，后轮这时的负重就相当的小，摩擦力自然也小了，这时猛打方向，车尾就会甩起来。其实所说的弯中弯前收油门，道理和这两个一样，都是靠前轮增加负重后轮减小负重。 然后我再说说惯性漂移，这里也直接引用我以前写的--这里补充一点，开始向右打的原因也和负重有关，目的就是给右前轮增加负重，然后靠惯性，让车身以右前轮为基准旋转。 一般柏油路使用惯性漂移比较吓人，我问看我漂移的的朋友什么感觉，人家说反正比较可怕，车身突然扭过去，四个轮子一起冒烟，横着滑过去。最后，给大家说说雪地漂移，雪地可以说是练习漂移的最有意思的地方，因为即使是前驱，也可以轻易做出和后驱一样的感觉来。 而且用之前的笨方法就是拉手刹最好玩。入弯，打方向的瞬间，或刚打方向就马上拉手刹，尾部侧滑，松开手刹控制方向，要领是让车平稳的过弯，回轮的时候速度要稳，不能太快。试几次我相信有心的朋友就能练好，那种过90度弯，过弯时车头直指弯心，你必须看着侧面车窗控制方向的感觉绝对爽：)不过我也付出过代价，速度太快，横着滑到弯外，撞上台阶，最后造成后桥变形，不得不花银子换新的。 (选读篇)最最后，给大家说说最高级的漂移方法。这些都是我基本没在生活中试过的。方法一scandinavianflick参赛车都是没有ABS的。刹车一脚就可以抱死，选手在一般是土路上，反正不是柏油路，高速冲入弯内，根据经验判断切弯的路线，然后一次性把轮子抱死，这时抱死的前轮基本没有导向力，所以无论你怎么打都不会改变车的方向。 然后这是开始打轮，比如是朝右，打到一定程度时也基本滑到了要入弯的地方，迅速松开刹车，这时由于前轮胎突然恢复导向力，迅速把车身拉向右侧，车身高速向右侧旋转，产生漂移，说起来复杂。做起来并不复杂。但是要想掌握好时机，和前后的速度。真不是简单的事。我只在雪地上试过，因为轿车有ABS不能锁死，所以只有雪地和没ABS时比较相象>。 方法二连续漂移法，其实我觉得更应该叫S弯漂移法。道理和前面的基本一样，其实是上面的方法的延伸。熟悉比赛的朋友都知道该如何过S弯吧。就是切两个连续弯的APEX，尽量走直线，这样速度最快，但如果是土路，雪路，弯度大，肯定会产生漂移，怎么办呢，这个方法就是来解决这个问题的。 如果你觉得，完成第一个漂移后紧接着打反方向，去做另一个漂移，那就错了，有两点你没考虑到，第一，S弯一般比较急，没时间等车身慢慢的去旋转回来，第二，干打方向只是单纯的等车转过来，你没办法决定车什么时候转过来，这时你就错过了第二个漂移的切入点。 好了，这个方法就是来对付这个问题的。假设一个土路S弯，先右转，紧跟着左转，高速入弯，先让车产生向右的漂移，如果弯很窄就需要用走惯性漂移的路线，先往左打，然后猛的朝右打，这时车开始入第一个右弯，当漂移到一定位置时，这时车身已经有点转向过度了，然后保持大油门(关键)，把前轮猛的打向左边，别以为这时车会马上左转，绝对不会，当你保持大油门时，前轮驱动力过大，打滑后导向力同样很小，跟上面一样，这时车身只会很慢的旋转，这时是最奇怪的时候，因为车正在朝右漂移，但轮子朝左，而且车身几乎没改变方向。 哈哈这时已经漂到第二个弯了，需要左转了，当你到达第二个切弯点时，迅速减小油门(关键)，这时原来已经打好方向的朝左的前轮迅速获得导向力，快速的带着车身朝左旋转。开始进行第二个漂移，这样就成果的完成了连续漂移过S弯。整个动作是由两个漂移甚至是惯性漂移完成的。神奇吧，嘿嘿，快找个游戏试试吧，生活中我看咱们就算了吧。 说了一大堆，好累，希望大家研究的同时，也注意安全，多思考，开始同学习。要多用脑啦，千万别光是傻做哦。 补充一点，关于HEELANDTOE趾跟动作，想流畅的过弯，不会这个动作是不行的，懂的朋友我就不说了，给不懂的朋友说两句，就是入弯前要换档，换底档，但高速入低档变速箱里齿轮的速度就会不匹配，生挂就会拽车，也废离合器片，就需要哄油门提高另一端的齿轮速度。但入弯前又要减速，所以右脚就忙不过来，就需要这个动作，用脚尖踩刹车，脚跟哄油门，一次到位，挂档，入弯。 我是采用TOEANDTOE用前脚掌左侧和右侧同时控制刹车和油门。根据你的踏板位置和习惯来决定。其实前驱过弯还有一种左脚制动技术，太深太深，这里讲漂移就不多说了。 汽车产生漂移的原理 归咎到底就是一种：后轮失去大部分（或者全部）抓地力，同时前轮要能保持抓地力（最多只能失去小部分，最好当然是获得额外的抓地力了），这时只要前轮有一定的横向力，车就甩尾，便会产生漂移。 令后轮失去抓地力的方法： 1.行驶中使后轮与地面间有负速度差（后轮速度相对低） 2.任何情况下使后轮与地面间有正速度差（后轮速度相对高） 3.行驶中减小后轮与地面之间的正压力。 这三项里面只要满足一项就够 实际上1，2都是减小摩擦系数的方法，将它们分开，是因为应用方法不同。 保持前轮抓地力的方法： 1.行驶中不使前轮与地面间有很大的速度差 2.行驶中不使前轮与地面间正压力减少太多，最好就是可以增大正压力。这两项要同时满足才行。 实际操作里面，拉手刹就一定同时满足行驶中使后轮与地面间有负速度差（后轮速度相对低） 行驶中不使前轮与地面间有很大的速度差 ; 漂移初状态的简单操作: 产生漂移的方法有： 1.直路行驶中拉起手刹之后打方向 2. 转弯中拉手刹 3. 直路行驶中猛踩刹车后打方向 4. 转弯中猛踩刹车 5.功率足够大的后驱车（或前后轮驱动力分配比例趋向于后驱车的四驱车）在速度不很高时猛踩油门并且打方向 其中3，4是利用重量转移（后轮重量转移到前轮上），是最少伤车的方法。 1，2只用于前驱车和拉力比赛用的四驱车，而且可免则免，除非你不怕弄坏车。 注意1和2，3和4分开， 是因为车的运动路线会有很大的不同。重要说明：漂移过弯和普通过弯一样，都有速度极限，而且漂移过弯的速度极限最多只可能比普通过弯高一点，在硬地上漂移过弯的速度极限比普通过弯还低！ 至于最终能不能甩尾，跟轮胎与路面间的摩擦系数、车的速度、刹车力度、油门大小、前轮角度大小、车重分配、轮距轴距、悬挂软硬等多个因素有关。例如雨天、雪地上行车想甩尾很容易，想不甩尾反而难些；行车速度越高越容易甩尾（所以安全驾驶第一条就是不要开快车哦）；打方向快，也容易甩尾（教我驾驶的师傅就叫我打方向盘不要太快哦）；轮距轴距越小、车身越高，重量转移越厉害，越容易甩尾（也容易翻车！）；前悬挂系统的防倾作用越弱，越容易甩尾。 有人提到多种漂移方式，实际上都在上面五种之内。 甩尾中的控制: 如果是用手刹产生漂移的，那么当车旋转到你所希望的角度后，就应该放开手刹了。 漂移的中途的任务就是要调整车身姿势。因为路面凹凸、路线弯曲程度、汽车的过弯特性等因素是会经常变化的。所以车手经常要控制方向盘、油门、刹车、甚至离合器（不推荐），以让汽车按照车手所希望的路线行驶。 先说明一点原理：要让车轮滑动距离长，就应尽量减小车轮与地面间的摩擦力；要让车轮少滑动，就应尽量增大摩擦力。减小摩擦力的方法前面说过，一个是让车轮太快或太慢地转动，一个是减小车轮与地面间正压力；增大摩擦力的方法就是相反了。 其中，让车轮太慢转动的方法即是踩脚刹或者拉手刹了（再强调一次：脚刹是作用于四个车轮，手刹是作用于后轮的。不管是否有手刹作用于其他车轮的车，我所知道的有手刹的赛车全都是我所说的情况） 踩脚刹：四个车轮都会减速，最终是前轮失去较多摩擦力还是后轮失去较多摩擦力不能一概而论。 拉手刹：前轮不会失去摩擦力而后轮就失去大量摩擦力，所以就容易产生转向过度了。因为无论脚刹、手刹都有减速的作用，所以车很快就会停止侧滑。 汽车产生漂移的原理 归咎到底就是一种：后轮失去大部分（或者全部）抓地力，同时前轮要能保持抓地力（最多只能失去小部分，最好当然是获得额外的抓地力了），这时只要前轮有一定的横向力，车就甩尾，便会产生漂移。 令后轮失去抓地力的方法： 1.行驶中使后轮与地面间有负速度差（后轮速度相对低） 2.任何情况下使后轮与地面间有正速度差（后轮速度相对高） 3.行驶中减小后轮与地面之间的正压力。 这三项里面只要满足一项就够 实际上1，2都是减小摩擦系数的方法，将它们分开，是因为应用方法不同。 保持前轮抓地力的方法： 1.行驶中不使前轮与地面间有很大的速度差 2.行驶中不使前轮与地面间正压力减少太多，最好就是可以增大正压力。这两项要同时满足才行。 实际操作里面，拉手刹就一定同时满足行驶中使后轮与地面间有负速度差（后轮速度相对低） 行驶中不使前轮与地面间有很大的速度差 ; 漂移初状态的简单操作: 产生漂移的方法有： 1.直路行驶中拉起手刹之后打方向 2. 转弯中拉手刹 3. 直路行驶中猛踩刹车后打方向 4. 转弯中猛踩刹车 5.功率足够大的后驱车（或前后轮驱动力分配比例趋向于后驱车的四驱车）在速度不很高时猛踩油门并且打方向 其中3，4是利用重量转移（后轮重量转移到前轮上），是最少伤车的方法。 1，2只用于前驱车和拉力比赛用的四驱车，而且可免则免，除非你不怕弄坏车。 注意1和2，3和4分开， 是因为车的运动路线会有很大的不同。重要说明：漂移过弯和普通过弯一样，都有速度极限，而且漂移过弯的速度极限最多只可能比普通过弯高一点，在硬地上漂移过弯的速度极限比普通过弯还低！ 至于最终能不能甩尾，跟轮胎与路面间的摩擦系数、车的速度、刹车力度、油门大小、前轮角度大小、车重分配、轮距轴距、悬挂软硬等多个因素有关。例如雨天、雪地上行车想甩尾很容易，想不甩尾反而难些；行车速度越高越容易甩尾（所以安全驾驶第一条就是不要开快车哦）；打方向快，也容易甩尾（教我驾驶的师傅就叫我打方向盘不要太快哦）；轮距轴距越小、车身越高，重量转移越厉害，越容易甩尾（也容易翻车！）；前悬挂系统的防倾作用越弱，越容易甩尾。 有人提到多种漂移方式，实际上都在上面五种之内。 甩尾中的控制: 如果是用手刹产生漂移的，那么当车旋转到你所希望的角度后，就应该放开手刹了。 漂移的中途的任务就是要调整车身姿势。因为路面凹凸、路线弯曲程度、汽车的过弯特性等因素是会经常变化的。所以车手经常要控制方向盘、油门、刹车、甚至离合器（不推荐），以让汽车按照车手所希望的路线行驶。 先说明一点原理：要让车轮滑动距离长，就应尽量减小车轮与地面间的摩擦力；要让车轮少滑动，就应尽量增大摩擦力。减小摩擦力的方法前面说过，一个是让车轮太快或太慢地转动，一个是减小车轮与地面间正压力；增大摩擦力的方法就是相反了。 其中，让车轮太慢转动的方法即是踩脚刹或者拉手刹了（再强调一次：脚刹是作用于四个车轮，手刹是作用于后轮的。不管是否有手刹作用于其他车轮的车，我所知道的有手刹的赛车全都是我所说的情况） 踩脚刹：四个车轮都会减速，最终是前轮失去较多摩擦力还是后轮失去较多摩擦力不能一概而论。 拉手刹：前轮不会失去摩擦力而后轮就失去大量摩擦力，所以就容易产生转向过度了。因为无论脚刹、手刹都有减速的作用，所以车很快就会停止侧滑。 真正的漂移: 而如果想车轮长距离侧滑，唯一的方法就是让驱动轮高速空转，必须要装有LSD的、功率足够大的车才可以这样做。为什么要有LSD呢？因为车漂移时车身会倾斜，外侧车轮对地面的压力大，内侧的车轮压力小。没有LSD的车会出现内侧驱动轮空转，外侧驱动轮转得很慢的情况。这个转得慢的车轮与地面间摩擦力大，车的侧滑就会很快停止。 车分为前驱、后驱、四驱，没有驱动力的车轮是不可能高速空转的。那么前驱车的后轮就不能做长距离的侧滑，如果驱动轮（即是前轮）高速空转，侧滑比后轮多，漂移角度就减小，所以前驱车是不能做长距离漂移的。四驱的车很显然是可以的。后驱车呢？后驱车前轮没有驱动力，但前轮可以向车身滑动的方向摆一个角度，所以后驱车也可以作长距离漂移。 侧滑距离与侧滑开始前的速度有关，通常会越滑越慢，最后还是停下来，但如果场地允许、控制得好，理论上可以做无限长的侧滑。因为打滑的车轮仍有一定的加速所用，而侧滑的轮胎也受到地面的阻力，当这两个作用平衡时，车的速度就不会降低了。例如 Doughnut（原地转圈）就是无限长漂移中的一种，当然也可以做出转弯半径较大的无限长漂移。 上面说的都是控制驱动轮侧滑长度的方法。知道这些原理之后，再说-- 调整车身姿势用到的方法: 1.控制前轮的角度，不能太大或太小，特别是对于后驱车 2.调节油门、刹车，令车有加速或减速的趋势，就产生重量转移，通过重量转移控制车头向外滑更多还是车尾向外滑更多 3.利用手刹再次产生转向过度。 注意:2中，后驱车（或动力分配比趋向于后驱的四驱车）加油所产生的效果不一定是加速，如果加油太猛，就有可能因为后轮转速太高而减小摩擦力，车尾向外滑得更多。 重要讲解: 最大漂移角度 : 最大漂移角度--在漂移中途，车头指向与车身运动方向之间夹角如果大于这个角度，就必须要停车（不停的话就撞出去）。注意不包括漂移产生时。 后轮驱动车来说，因为前轮没有驱动力，不能产生高速空转向外滑，只是*地面对前轮的侧向力控制车头运动。所以车头指向与车身运动方向之间的夹角最多只能和前轮最大摆角相等（不同的车前轮摆角不同，一般轿车的前轮摆角可以有30度左右），再大一点的话，除了停车再起步之外就没有任何方法恢复正确行驶。注意平常人提到的“大角度漂移”不是指车头指向与车身运动方向之间的夹角，而是附图红色标志出的角度，弯越急，显得角度越大。 后驱车也有前轮抓地力不够、转向不足的情况。在这样的情况下，车头指向与车身运动方向之间的夹角同样不能超越最大漂移角度，否则也必须停车才能恢复正常行驶。 前驱车因为可以保持后轮的抓地力而加大油门让前轮向外滑，所以前驱车的最大漂移角度很大，可以接近90度。 四驱车因为前后轮都可以高速空转，加油时有前轮向外滑得更多的可能性（为什么？因为加油时重量转移到后轮，前轮与地面间摩擦力小）再加上前轮可以向外摆，那么四驱车的最大漂移角度就比后驱车大。( DRIIFT : 反对意见出现,后驱车在完整的车架SET UP 下漂移角度比4WD大.) 比较三种驱动形式的车，前驱车是最容易驾驶、最安全的。(DRIIFT: 反对意见出现 ,呵呵我觉得FR最好开,停车的时候真是"感觉好极了") 漂移的出弯: 出弯的时候就应该结束漂移了，结束方法与漂移过程中减小漂移角度的方法一样。 对于前驱车， 1.加油使车头向外滑动（因为除了漂移产生的时候，前驱车基本上是转向不足的） 2.通过前轮向外摆修正车头角度 3.也可以前轮向外摆之后放一点油门。 对于四驱车，2通常是必要的，3也很有效，1则不一定奏效。 对于后驱车，最主要*2。视具体情况而定，车的重量分配、驱动力分配、之前漂移角度、路面状况等多种因素都有影响。 注意整个漂移过程中（包括产生、中途、结束）车身都是在向外滑的，所以准备出弯的时候不要把车头指向路外侧，而是应该指向内一点，让车滑到路最外侧时横向速度刚好为零，这就是完美的出弯。 后记: 开不同的车做漂移都要有一段适应过程，了解车的特性；在不同路面上也要有适应过程。在拉力赛中，因为每个弯的具体情况都是不知道的，即使在上一赛季已经跑过这赛段，路面也不会与以前相同。所以拉力赛中过弯都崇尚“慢进快出”的原则--进弯前速度慢一点，看清楚弯道之后就可以加大油门出弯。用这个原则过弯不但不会慢很多，而且安全性大大提高。

Jensen不等式，又名琴森不等式或詹森不等式（均为音译）。它是一个在描述积分的凸函数值和凸函数的积分值间的关系的不等式。它的一般形态是：1.当且仅当f ( x ) f(x)f(x)为下凸函数时有2.当且仅当f ( x ) f(x)f(x)为上凸函数时有它的最简单形态是：1.当且仅当f ( x ) f(x)f(x)为下凸函数时有一般采用数学归纳法进行Jensen不等式的推导和证明。以下凸函数为例，先看n = 2 n=2n=2时的情形。

汽车产生漂移的原理 归咎到底就是一种：后轮失去大部分（或者全部）抓地力，同时前轮要能保持抓地力（最多只能失去小部分，最好当然是获得额外的抓地力了），这时只要前轮有一定的横向力，车就甩尾，便会产生漂移。 令后轮失去抓地力的方法： 1.行驶中使后轮与地面间有负速度差（后轮速度相对低） 2.任何情况下使后轮与地面间有正速度差（后轮速度相对高） 3.行驶中减小后轮与地面之间的正压力。 这三项里面只要满足一项就够 实际上1，2都是减小摩擦系数的方法，将它们分开，是因为应用方法不同。 保持前轮抓地力的方法： 1.行驶中不使前轮与地面间有很大的速度差 2.行驶中不使前轮与地面间正压力减少太多，最好就是可以增大正压力。这两项要同时满足才行。 实际操作里面，拉手刹就一定同时满足行驶中使后轮与地面间有负速度差（后轮速度相对低） 行驶中不使前轮与地面间有很大的速度差 ; 漂移初状态的简单操作: 产生漂移的方法有： 1.直路行驶中拉起手刹之后打方向 2. 转弯中拉手刹 3. 直路行驶中猛踩刹车后打方向 4. 转弯中猛踩刹车 5.功率足够大的后驱车（或前后轮驱动力分配比例趋向于后驱车的四驱车）在速度不很高时猛踩油门并且打方向 其中3，4是利用重量转移（后轮重量转移到前轮上），是最少伤车的方法。 1，2只用于前驱车和拉力比赛用的四驱车，而且可免则免，除非你不怕弄坏车。 注意1和2，3和4分开， 是因为车的运动路线会有很大的不同。重要说明：漂移过弯和普通过弯一样，都有速度极限，而且漂移过弯的速度极限最多只可能比普通过弯高一点，在硬地上漂移过弯的速度极限比普通过弯还低！ 至于最终能不能甩尾，跟轮胎与路面间的摩擦系数、车的速度、刹车力度、油门大小、前轮角度大小、车重分配、轮距轴距、悬挂软硬等多个因素有关。例如雨天、雪地上行车想甩尾很容易，想不甩尾反而难些；行车速度越高越容易甩尾（所以安全驾驶第一条就是不要开快车哦）；打方向快，也容易甩尾（教我驾驶的师傅就叫我打方向盘不要太快哦）；轮距轴距越小、车身越高，重量转移越厉害，越容易甩尾（也容易翻车！）；前悬挂系统的防倾作用越弱，越容易甩尾。 有人提到多种漂移方式，实际上都在上面五种之内。 甩尾中的控制: 如果是用手刹产生漂移的，那么当车旋转到你所希望的角度后，就应该放开手刹了。 漂移的中途的任务就是要调整车身姿势。因为路面凹凸、路线弯曲程度、汽车的过弯特性等因素是会经常变化的。所以车手经常要控制方向盘、油门、刹车、甚至离合器（不推荐），以让汽车按照车手所希望的路线行驶。 先说明一点原理：要让车轮滑动距离长，就应尽量减小车轮与地面间的摩擦力；要让车轮少滑动，就应尽量增大摩擦力。减小摩擦力的方法前面说过，一个是让车轮太快或太慢地转动，一个是减小车轮与地面间正压力；增大摩擦力的方法就是相反了。 其中，让车轮太慢转动的方法即是踩脚刹或者拉手刹了（再强调一次：脚刹是作用于四个车轮，手刹是作用于后轮的。不管是否有手刹作用于其他车轮的车，我所知道的有手刹的赛车全都是我所说的情况） 踩脚刹：四个车轮都会减速，最终是前轮失去较多摩擦力还是后轮失去较多摩擦力不能一概而论。 拉手刹：前轮不会失去摩擦力而后轮就失去大量摩擦力，所以就容易产生转向过度了。因为无论脚刹、手刹都有减速的作用，所以车很快就会停止侧滑。 真正的漂移: 而如果想车轮长距离侧滑，唯一的方法就是让驱动轮高速空转，必须要装有LSD的、功率足够大的车才可以这样做。为什么要有LSD呢？因为车漂移时车身会倾斜，外侧车轮对地面的压力大，内侧的车轮压力小。没有LSD的车会出现内侧驱动轮空转，外侧驱动轮转得很慢的情况。这个转得慢的车轮与地面间摩擦力大，车的侧滑就会很快停止。 车分为前驱、后驱、四驱，没有驱动力的车轮是不可能高速空转的。那么前驱车的后轮就不能做长距离的侧滑，如果驱动轮（即是前轮）高速空转，侧滑比后轮多，漂移角度就减小，所以前驱车是不能做长距离漂移的。四驱的车很显然是可以的。后驱车呢？后驱车前轮没有驱动力，但前轮可以向车身滑动的方向摆一个角度，所以后驱车也可以作长距离漂移。 侧滑距离与侧滑开始前的速度有关，通常会越滑越慢，最后还是停下来，但如果场地允许、控制得好，理论上可以做无限长的侧滑。因为打滑的车轮仍有一定的加速所用，而侧滑的轮胎也受到地面的阻力，当这两个作用平衡时，车的速度就不会降低了。例如 Doughnut（原地转圈）就是无限长漂移中的一种，当然也可以做出转弯半径较大的无限长漂移。 上面说的都是控制驱动轮侧滑长度的方法。知道这些原理之后，再说— 调整车身姿势用到的方法: 1.控制前轮的角度，不能太大或太小，特别是对于后驱车 2.调节油门、刹车，令车有加速或减速的趋势，就产生重量转移，通过重量转移控制车头向外滑更多还是车尾向外滑更多 3.利用手刹再次产生转向过度。 注意:2中，后驱车（或动力分配比趋向于后驱的四驱车）加油所产生的效果不一定是加速，如果加油太猛，就有可能因为后轮转速太高而减小摩擦力，车尾向外滑得更多。

1、开机线路不正常：使用外接电源给手机供电，使用电联表检测看看示数是否有变化，如果没有变化的话很可能就是开机线断了或者开机键接触不良。 2、电池的供电电路不正常：使用外部接口对手机进行供电，看看开机时候恢复正常，如果正常的话就确定是手机的供电电路不正常。 3、手机电源的IC不正常：对照电路原理图在电源IC的外 围电路的测试点上进行测试，看测试值是否正常。 4、手机的系统时钟和复位不正常：可以使用双总示波器来对手机的CPU电源进行检测，查看复位之中的波形图是否正确。 5、逻辑电路出现问题：也就是手机电路版出现的"故障，一般可以通过补焊来解决这个问题。 6、软件冲突：安装的软件与手机的系统不相符也可能会造成手机开机不了的情况，可以将手机连接电脑将程序删除。以上就是oppo 手机开不了机的原因，建议大家可以携带手机、保修卡、发票前往当地客户服务中心进行检测和维修。

简森(JENSEN) L-TRON DTX 滚筒烘干机是大容量的滚筒式烘干机，这类烘干机一般是用于全自动烘干通道和独立的洗衣房。能效方面，烘干机内循环时间短，采用轴向气流，进入的空气通过压篮前后侧，这样便于向烘干产品传热，不必使用刷板。结构方面，整套烘干机安装在一副钢架上，用来确保部件之间正确对齐。前后门的垂直引导动作降低了热量损失，消除压篮装卸过程中的机械干扰。安全性方面，该烘干机采用直接驱动，因此，没有皮带，也不需要更换皮带。另外集中的润滑位置，减少维护时间，维护也方便些。