正文

<span style="margin: 0px; padding: 0px; line-height: 1.6; -ms-word-wrap: break-word !important; max-width: 100%; box-sizing: border-box !important;">IO调度发生在Linux内核的IO调度层。这个层次是针对Linux的整体IO层次体系来说的。从read()或者write()系统调用的角度来说,Linux整体IO体系可以分为七层,它们分别是:</span>
  1. VFS层:虚拟文件系统层。由于内核要跟多种文件系统打交道,而每一种文件系统所实现的数据结构和相关方法都可能不尽相同,所以,内核抽象了这一层,专门用来适配各种文件系统,并对外提供统一操作接口。

  2. 文件系统层:不同的文件系统实现自己的操作过程,提供自己特有的特征,具体不多说了,大家愿意的话自己去看代码即可。

  3. 页缓存层:负责真对page的缓存。

  4. 通用块层:由于绝大多数情况的io操作是跟块设备打交道,所以Linux在此提供了一个类似vfs层的块设备操作抽象层。下层对接各种不同属性的块设备,对上提供统一的Block IO请求标准。

  5. IO调度层:因为绝大多数的块设备都是类似磁盘这样的设备,所以有必要根据这类设备的特点以及应用的不同特点来设置一些不同的调度算法和队列。以便在不同的应用环境下有针对性的提高磁盘的读写效率,这里就是大名鼎鼎的Linux电梯所起作用的地方。针对机械硬盘的各种调度方法就是在这实现的。

  6. 块设备驱动层:驱动层对外提供相对比较高级的设备操作接口,往往是C语言的,而下层对接设备本身的操作方法和规范。

  7. 块设备层:这层就是具体的物理设备了,定义了各种真对设备操作方法和规范。

    有一个已经整理好的[Linux IO结构图],非常经典,一图胜千言:https://www.thomas-krenn.com/de/wikiDE/images/b/ba/Linux-storage-stack-diagram_v4.0.png

    我们今天要研究的内容主要在IO调度这一层。

    它要解决的核心问题是,如何提高块设备IO的整体性能?这一层也主要是针对机械硬盘结构而设计的。

    众所周知,机械硬盘的存储介质是磁盘,磁头在盘片上移动进行磁道寻址,行为类似播放一张唱片。

    这种结构的特点是,顺序访问时吞吐量较高,但是如果一旦对盘片有随机访问,那么大量的时间都会浪费在磁头的移动上,这时候就会导致每次IO的响应时间变长,极大的降低IO的响应速度。

    磁头在盘片上寻道的操作,类似电梯调度,实际上在最开始的时期,Linux把这个算法命名为Linux电梯算法,即:

如果在寻道的过程中,能把顺序路过的相关磁道的数据请求都“顺便”处理掉,那么就可以在比较小影响响应速度的前提下,提高整体IO的吞吐量。

这就是我们为什么要设计IO调度算法的原因。

<span style="margin: 0px; padding: 0px; color: rgb(0, 122, 170); -ms-word-wrap: break-word !important; max-width: 100%; box-sizing: border-box !important;">**目前在内核中默认开启了三种算法/模式:noop,cfq和deadline。**</span>严格算应该是两种:

因为第一种叫做noop,就是空操作调度算法,也就是没有任何调度操作,并不对io请求进行排序,仅仅做适当的io合并的一个fifo队列。

目前内核中默认的调度算法应该是cfq,叫做完全公平队列调度。这个调度算法人如其名,它试图给所有进程提供一个完全公平的IO操作环境。

小编注:请大家一定记住这个词语,cfq,完全公平队列调度,不然下文就没法看了。

cfq为每个进程创建一个同步IO调度队列,并默认以时间片和请求数限定的方式分配IO资源,以此保证每个进程的IO资源占用是公平的,cfq还实现了针对进程级别的优先级调度,这个我们后面会详细解释。

查看和修改IO调度算法的方法是:

cat /sys/block/sda/queue/scheduler

echo&nbsp;<span style="line-height: 1.5; font-family: 微软雅黑; font-size: 14px; background-color: inherit;">noop &gt;&nbsp;<span style="text-align: left; color: rgb(62, 62, 62); font-family: &quot;Helvetica Neue&quot;, Helvetica, &quot;Hiragino Sans GB&quot;, &quot;Microsoft YaHei&quot;, Arial, sans-serif; font-size: 16px; font-style: normal; font-weight: normal; background-color: rgb(255, 255, 255);">/sys/block/sda/queue/scheduler</span></span>

&nbsp;

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的基本原理。
当然,现实生活中不可能有真正的&ldquo;公平&rdquo;,常见的应用场景下,我们很肯能需要人为的对进程的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请求来自哪个进程。<span style="margin: 0px; padding: 0px; line-height: 1.6; -ms-word-wrap: break-word !important; max-width: 100%; box-sizing: border-box !important;">关于buffer/cache,详见拙文:</span>

[**我就是认真:Linux 内存中的Cache,真的能被回收么?**](http://mp.weixin.qq.com/s?__biz=MzA4Nzg5Nzc5OA==&amp;mid=2651659553&amp;idx=1&amp;sn=6a14ef45ef79dffbdd302f882eb0d096&amp;scene=21#wechat_redirect)

所以,除了针对每个进程实现的IO队列以外,还实现了一个公共的队列用来处理异步请求。

当前内核已经实现了针对IO资源的cgroup资源隔离,所以在以上体系的基础上,cfq也实现了针对cgroup的调度支持。关于cgroup的blkio功能的描述,请看我之前的文章<a style="margin: 0px; padding: 0px; color: rgb(96, 127, 166); text-decoration: none; -ms-word-wrap: break-word !important; max-width: 100%; box-sizing: border-box !important;">Cgroup &ndash; Linux的IO资源隔离</a>。

总的来说,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资源占用&ldquo;公平&rdquo;。

当然我们知道,cgroup是可以对blkio进行资源比例分配的,其作用原理就是,分配比例大的cgroup占用vdisktime时间增长较慢,分配比例小的vdisktime时间增长较快,快慢与分配比例成正比。

这样就做到了不同的cgroup分配的IO比例不一样,并且在cfq的角度看来依然是&ldquo;公平&ldquo;的。

选择好了需要处理的cgroup(cfq_group)之后,调度器需要决策选择下一步的service_tree。

service_tree这个数据结构对应的都是一系列的红黑树,主要目的是用来实现请求优先级分类的,就是RT、BE、IDLE的分类。每一个cfq_group都维护了7个service_trees,其定义如下:

![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAP4AAAAkCAYAAACpM4cYAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsQAAA7EAZUrDhsAADG2SURBVHhe7Z0JlF1Vlfd3zVWv5lRVUpkHCEMwgRASkEFlCqMDgkpsFZSWST+7ddm2Cq62l3a3dqvt0AOiKNqtgsgQEQmQMGSe55DKBJmnSs2p8b2q+v6/fd9JXl4qI4mtLjfr5tW7795z9tnDf+997jmXjKampl47AerJ6En+dXooM8lNT0b0acn+wvnweZDS+clMfh6Jz/D7yRL391iG+OgNPPZ57s+V0uUX5Bw+w+/RZ0ZvdL43I/p+JK38qdABuzwGYafhWmwC2ziUInlkJuUT6Hjbf6uUrsU/IzrNQxMgZciMe9TPn7ox/4VOD+H8JxoIDg9sp4f+KB0f1OuVY/mh7xw4mPWmsou7HcvlUq/n77c+3KP2eJqzoT9eOnzcfUniT0E6DuPSIzZ4SPRFt6lHOiXPY7OH/s7fB88BBGQ/hwCCfqPf0HfUTnTtAUqeP1V0wp6QlXXwlp6eU8dIX+QAkJk6+uOl4OSpx6mjzMzMQ1K0nmQa++dPfY8zQzrq7km4vuKZ2dZlOUmZyIB7u/3o8c8TD2fZ2dnW3d2d/CZ7OIk2ToaC4/XqHx/1IUHnyBT4S3XinsxUPzmYIfY1lhDxDwIPtuanTimdsMVmZ+f45/6WFjl+pMzU461QZoaP1OIdndbeFZfgI2TE+TM1+gwOXZOpJBtj6/PQ735Yliurvb1L37N0vwyyK0EvyePkKIwR5493tFu3evpDU3ZOjrW2tWk8XckzfwiSzDD+cIhcF5KDO31v3Hqysqwru8g6swr1PcP279/v16XSidpL1H637W+N2qLPE7n/ZMkdD0vTWItiZX6uU/bT1NgifiJAov8QCHt0sjuRkA32Wk5OlnSUZVkq7JkTc/DrifhNECwzsywjeV9eXp716L7O9jbrjndaVrZkqjHqH12TLaeXDwj3OjvkD37HqaETntzLzsuOPrOzrLm5WQOPvgdCMSdLIFuW7s/OzbW4/LYrIWOSoHD0bEXYLAAUbhFmX924QUYC5e9u3dvdnXChowh4PmgwqSh8fIQREsl6xJc4lJKzrV1/YeT+nQj3FkDleAj5Mq7CWMxl09nZmfzldJLGlHT2A+RpZ48VxPKssbFeBpxjWbESa+yOiUdd3tJosczEgcwIuSGbdPs4mr0A5BBOlSXd5SjoxCX77sTBDOCt2FtfxCjhGPvDHnPiAhr6j6lv/ZIBEMlRs/VJECQbicfllHin+MU/cgUKWTizdNPaE5eP5FpOT6Z1xZX5yLZzc/J1v/pJKCjpvly1lSHw5HoCSVZevjInHL7HYsqeZGDWm5tpHV0ChlOUXZ6w42fIz/ftq7NBAwdGjIJgKXTSipAhCQf10WudUmxCA89SZMsEGXHc3oRlyYjC7Ohhjp/q9IF0rra2zlasWCkFddlZZ4+2ESOG64cTd/oDBNAJTDqa66yhqcXKqodZZrYUK7MA4U+340NZiqxtivgAUY5kdDKEno4/YmpMR3B8ALVlf5PFCvJs7Rtbbe/+LLtgwoWW3d5i+VkCQzkA1A1g6kDHqXQ0e4E/fscGcP6ueJdlKVoy7kCn2vEjknOrC55IlKjvrVu22pJ1NdamiH/JpElWXlJqhUUxj/b19Q3OA3/3CilixTFbs3KF7du5zYoKi2zAyFFWWVEtxzer3Vdvm7Zvt5b2VhtUOcDGnHOWAEB6kENnZnZbXm6B7dizz8rKK9z+m+rrbFtNjdXV7bNzJ1xs1YMGK4gpq0gpM0+WDrPSYxlDQk65ft06271njxQiWDyF5IqW8LZu3WxbtmyXQHM00CwpnV8jQ/PJk6M5bjDQDBmcrp32/HSrr2uy/PxYMjU+fqH1iB+OVGpva7ccoXZjU5PNnjPHtkuRCRk3vJNZpFMw0vR2TpYSAp2CwmJbtXq17di5M3n2dJNk5nI/nFqVzucowhGJX57xsj0/bZpKoLjl5Od5aZVaq54oBafG6ffJ+F9//fVDnP50kGd0SSwhy+yNt9qe3Vts1px5irgCOkXv0tIyU8C0F154wb7zne/Yc8/9zvbu2evnsY/yfqUqxZrtt88+o1KTjAyee6yto8VefPFFXdOpa0vdbtqV4j//wu/tW//2LfvWt76la7qcBygucC/My7C1r6+0TZu3EFr8/KmgrC996UtfTf7thAHn5+dba2urD47I0tjY6JGF88tXLLPXXptpgwYNdMaJPlX9qlTPtcgou5UN7PPUh9olVw5Cncd1BQUFqlM63Ploi9+4l+u5pre7V0LYr2yp256Z+ozElG/9+w+1ttZOGVaGlRfnqbSoV3qVKx4lGPxIB31lSlA7d+2wDtXzXfEeKy4uViTqlXM22EsvzrJPfvI+O2P0MBs2fLC1i4c2ja2uvt7H1quMBafMgx8ZMGNINu2y6NF3+I/r8LHICAsLY9bZ1mJra9bZsJGj9Vu3tTU3Sj55GtOhpQ9tcm+vjIj74Zcsaa+Ak76QAbLYtXu3XwdveZIz8yekkfDIfaSY+ZJpS3OL1e2rddDBPrkXB0HetAXxPRwxlQTokvsZO+MmU+M87ba0tHgfXeKL6+mTNjt0LQfXM35SrHg84ddxDaltpyIV9SwRGQOuGDDQxl90qVVU9rN2tZsjNeWKJ1LzfXVK/RUBewRcwR74rG+o173tVlFR4dE8dSIvECXNjh07bPHixX4d3+GRY4/kWFRc5HbU2BTZKXJgLMF22zvaFaEL3X4ZO30ydkCEawtiES/U3vsamtROs8WUbpcVSg/t9d5GUyLXbrv9o1ZVKadv2Ge7pS8AaeKkibZzx05vt7Kqv2r4bisuKrBhQ6rE226rqj7DKvoNUDbYKVnW2uZtu+2DH5hipSUlXhqSKZTInsZfcL6Va2yvzJpng4cOl8PHrLIkZlWlOeK3zrKKqmzQiDNUfsgeOyM/QlbMNZwMHeb4EEKYO3euTZ061ZYuXap0udaGDRtmOxVh/uu//9N279pt69dvcGEjuP4D+jv6vfbaq379Sy+95MoZOnSIPfzwj6yqqsoqKyts/Yb1+m26jRs3zpoFKj/60Y9s1qxZtlrRa6ADSacQ8TlbuGiJ7avdb4uWLJehJeycM8+weFezFcdy5TSYexKSRQz+8V8/btOmvWBLlyyTkWXa8GHDbd2G5bZs2Qpbumit9Jljb26usRIJMqH2lixZYr979llbrM8XxffZZ58t/irdyVMzHowHhT799NNC3dftRY1r5cpVViAHLyrItbnzF9ju2gabNXu2LVu8wPprnP0HDEjeHRHOnS0ZxbviNn/BAps5c6bNmDHDecDwBg8Z4n8/oz7mqJ3ZOiijKvpVWI0yq1/96lcu098//7yAsL877BNPPGGLFi50o58jPWHsAwcN8ro/3XHy5GA498MPP+w6WiLnKS0rc302yKBpF1ksW77cx48sAKFf//rXtkT9wtP8efPsjDPOsHVKd2e+NsvOl/7o5+c//7kDTj9FuF9LB09Nfc46JP+RI8+yfiWFUk7cli1dbE+orcXSzdqa9TZyxAj1X2ILJItHH33UnXnLli1WXlYuwBN4yflSCX3s2r3LfvjQD+3NN9+U3a235fAq+zrzzDNlKwulwxfdXhcuWKi0uM7OO+8827Rpk/3iF7+whZLTNGUhQyTnUqXo/A7f8+bPs1dffVXOWukpOSDx0A9/ZK/NnmWLFi+18qJSKxZyFeV22J66Wntzb7udd/4E61RZk6MCHXsZKhmWlZXa9h3bbfPmzTbpookKGBmWm6cx9LS4vfevPltgVSXHb7dGAc76jVttwkWTNM4MB8Z86S47S/fkZFuOZLn2jW129jnnWpGAJ19Za2ai0TZs2mAZxYNsyPBRVsBch65Hfv/5H/9hk6+7LimpE6PD4AJjRzgbN260K664ws4//3xFuEI3UoT34INfkYO/Zm9/+9tlJGd5VMA5mERrbW2zKVNuVxuZ9vhjj9kFF1zgxopB7d/f6u1zLUpbtnyZkLrY7rjzTjceqEACG1RdYdm5MRt15gQbO26iT6RkKM3kmnh3m67KOSRtpv4i3f7c5z4n4cWsvLRajt4jRN4hfpoFJr1qo0d1eFxO2GW7du7xMuVv/vZv/f4f//jHHjlQPE5KJEol+gf4ALfPfvaz9tzz09xQhw0a4A597rnn2Ac+8AFbvGCObZCizxs7LnnnQSINZiZ+jxyqTmB55x13uDNikJdLxq+88op98IMftOFyCtLZFStWWHV1tc2YPt3+6q/+SoBVYnv37rWnn3nGPvWpT9n999/vf+OM48ePdx4hABv9IV+IvzE2+N+9a5d95Stf8YyjrLxcemu35cuW+TUP6jyZBrK49LLLXF8NivQXTZxo7xB/jzzyiPM7TIC6adNmL3M6OtoE+tkO6ujxrrvusjNmL7SaLbXSQ6YANm57Nd43lKK+4x1X2vgJF0l/inDCbHS2eMlim/LhKTZKNfBvnvyNrVy10h05/UkF/AHkClDuqNgUfZZrDGQaAMVuRdZ777nXMwdAkc+Xpr+kft9hF110kUrHrfbLX/5S9jTWU21kdumllzpwPvb4Y3aReFuzZo3L6fNf/KIVxYqttz1hFaVyj/0bLbMnLk5UAujfkqIiCbrd5YgMoY0bNto5557rdskshtiyju4O6SG6z3rVjsYdHm0GojTEH+Bjwby5tnn7Lhsz6QrPnGLSYU+bQMa6dKtKpmT/9QLrotwM1/37b701augkSFwdShGC97NJkya5g//DP/yDPfXUU/4bAmUmn/QCZ6EU4DuUm5PrSumnSFWh+++5916hYZkbJTUxDsUsKDPr1IRr19Y4eFRU9HNll6k+6lA9VFxc6g6FYTUrfS4rzyMDc+fp7IwfVivv3LXT+62uHqBoWOBRjNToookT7IYbr9P5Krv66mv8GCBnAiQG6jM3VymhwIxaK1djJv3Oy8tNtnqQPB0UvxOF5oznve99r1155ZUeiQYOHGIjhg11Jz0SIU/qPtJMDPbCCy+0akX0c845xz50++3ucDg2ERuHGzF8uPhv8FQSUOVaeKxQhKFPHJhPUmuMpl2AFRMwow9S79SMBUIv9IsTfOHv/97++6GHrGbtWjc6SgCyjS9/+cv21a9+1cHea3aBFPyiHx4b3j5lipxytJd3yA0Q2rlzh5yvxPnrUZlG7cs4CvNjlqF0l4nOfkpd0e0QyYhEjYlAHDmm1Jbo/IPv/8C+/MCXBXAzfKzBllIJXriHdBx761HJlK3oCLg1NjS6fM8fd77spEwZ5lC7+5673SkB0J/85CcO1tTh3Lu/Zb+D9vPTnrfP/93n7dvf+baXEDj8iJEjfLwPPvCgA+Re6UCGKw54HMeEmmxBRyIelX7YDvYMkKAH9Ong0JvhY6Yk4sjswcWiJxrR/JRf5UegoUOGK8COtxtvfo8tWb5Cmc0WT+fzJGufyNN9rCcAMvhExwOUWcJvoKD3dP0fiQ5zfJhG0GPHjnWU/drXvuY1zvz5893hMYh6RQMUVVBAapmMxnJM6lgMkOjGOTdGCQWhU3e/+eYbiqztHlkxkgVqE6FDCaWFTI7wzL2lhegbVyTJt45OoV2P6sLuTNWpqu/DzIuznikeimzN6rX+fLVHxkzaWVQUkyHmeN9xlQ/CEScABwOivutS6g3Kr6up8eempMnZimBEqtQDA6uWkHNyo+e2gFq2kIi/QXz62Fu72x2mTL8x+Ranjk0eyImsJ+Il4QDD2JEzKT2OExllixvKOqWyyA7FIj+cASBAB4CElyTqOz9fdamup11KLtqDUhXP38gaZ71Cjv9PX/+6XaAM7re//a3kEPN6GRDD6f/93//dfvrTn9qgwYOdH3jADopUG3Pk5Wfre6adqzR0p5wFvog68MB5ZApgd8VVf3a2CzBVL9c3SDZ11ipAJ50mcGTJaXPzCjwd/8zffMYntR764UN22623uW7gmTIiHAAvjs443bakI0CL8QIKnOc6fuORHyBZpKgMn2QhP/jBD+y73/2ufV1jpx2PlLe83/t9RBkOJYTfK37f++6b7KsCouuvv8H+59mp1iDb6ZS+4An9NDVFWU68i0dvcXvpxem2Yf0mgc196rdcQY6I3qMysCgqu8jAmLVP2iygkBrx0SMyg0aNHOnlV4lKh+b9LQ6cmLh6t4TGmxD4yJzc/gB7dEB5k5DfccBjyPQgbLqvI9BhNT5pPUp8/PHHPeITIXF2oqpPmskBamv3eo2B4wxQCozzU/8zUTFSqVsqsfBiutIunJx0EaWcN2aMp2qvK/IAKLsUxXhGm5Wb5REK/h9XyrbpzU0uqLLSYg24VJFFYpAQMEjPnURMymGor6l2Xi60rK+vs8GDB1p+QbYMrdNWLF+nkuVygYgMRpiZm5OnmnyO14lNOJVAjLEVii+UwJwFABcODGuLUkUm9Pr3r1RW0mExyaNRzvi86uOde/ba8qXLJFTziZ4SZQU87QAcwqMnXDEep8zY5U6PgnFIfiPqIvMnfvMbl+cGOf548fO2t73NIxfzLGsUvZDfe97zHivW/eiD+5gf2awIFlM2RTaCs0GRfCLDwmCpPxeo1p2p6zGaETKyMUpNAWgiPn1SXryp68YJ8OFtub5Ty+MsB0jGWF7eT7qfL7022zvf+U7nfceOna7jOfPm24pVrwvczPqVKosReJGZzFUa+/LLL3sWM7B6oI+hW8BOpF+6bKmtW7dO8st0uWC8pPDhoH/GQynGpNwrL7/itsZ5MhmyFOQ0ctRIy1ddDGFj6I75lNVrVruuW9tavW/uoQxgDgCZoN/Ro0c7bz9/9FHbsWW77VBGc65KhKr+5ZbVvs8a6xptZ0O39HuJIniX+uvwgPHjHz9iQ4YOsVUrV/pTlgHKOsvKdE8WQaHe1tZsUHl8npUrC87Ialf5tM82rt9i11w92Qpz86yjq8MDxmw5MPNii5eusBFnj1G5O8AGS0aZiTbLLM2V/rZbb94ABYkR1tVWb+UlRT4v9iMBFzoAeJn4ZQIT8An674tCWOjzOT6GtWrVKv/EqRDWQEUmkDU/lqf0epdHGZCS34qLiyS4Pe74GEYqgUSrV9NWgc8RgIgYKFGECcIWOR9IP3jQYI9CTFwwO795xzZdl+0IO2ToIJ8EqVUtV5HWfq7Ot0h4b76xWcrOcV4GVPeXQWZbmxy/vrbdeWxrb1HqWezzEIBDfX0U1aij33fLLdZPQESEBngC4QBENMYQK1T2oehdVFhiTUox4XOnjEWZn6exo0YMV3s5MvpInAA2RBQn04gVldj2bVvcETFwlEO7yJiZ823bth34TobBJB4ZwoYNGzy6UZ6QHfB34Im5CtobOWqURzp0xf2pRNQhXUfOgAWgRKZB+RJF6Lhq7i3OT74AhDqbTKZB0RqQIoqmUklxmYx+nQbY4xOByIRIzhOUnbKB8v5DFU5yrF+Z0v6CPGtT9MJW4BlwZdKS7BDZ47TtrS0CrpjriANHTCW+B4OmxPDZeNlZZUWlX0//nCerYgwlJWXKjur93i1blTLHEx58+sluzjrrrAhAJG8cHeK+6oHVyhibrF58ZnZnWL3kNEqlXW5mh1Umaq1mTY3NWLzDPvDhv5YdKrPqpXY3Bw/6RxfYzbDhw3ztSSLO05LN9sK0l+ztl37ARow6U3Jssk0b1ttzv3/FPvP/PqvvmdatrJOUHzm0NKl2L6uwwupBliebr1Y7OYkmybLZnn5+umVVjLNJl11lBaasqbfL7/mnf/q6lzH4VpEAGD+irDwahVL5MMdHeBxEIz5xdgyGT6JKs5AeojanxiKVKeQxDUitexBEKqFgfqN+bZERDBhQ7ZGfWp90mz4gjBCmEjJslNTY0uyLdOiX6Jmj36FeOSeCDhQMCsLIcVaMpaiowD/b2+JuwJQB2SyHVDtEPT75/ec/+5mjJm2SUpOipRITQiBqp9LXHEUZVl21CzxKhLqkezy+ySvId0cno1ixao3fRz0IMVacktSWPnBCnBPQhF9Sfx7dAYbIinQsofNELB6/8RuZjj8O9YUeWT4e0n5kxz3IyAFBn1CQKf1FqXhGlM5qzIwbIKJ0IINj/oVyq1y6hVf0SR84M8aEkwZCDiyF9pQyo9uzNNoOKWY7czDZuRpfoS9DZZ4GAiThhXaRIXz64zzx1io9V1RWKPK1+ix4uuMzvsEqP7AJ7ItFPIWxQgfpNumBccM3NT7XUgrUCdiLi5Sdapws9yXzisYeTQaSMRCd6RO5tCkrIZNk1aiulDEq64wJ6NvrrSqnwxbNX2xTX1hm1737/Xb2WcM1nl5F/YTrgUyCsaFTwIk0vbm5Vsd2mzVzjk2+foqN5DFcZrttemODHH+G3XTjzQ68I4Yq81M5kaMAx5OADPWblVNoLWozR5lldqLV1m1cajPmzrPBoy+x6266xbK6O2zJgrk2Y8Z0u/mmm230WaNdTsg2+oyq99S0PpWO6viBGFDqJ41Sa/A9XBc+Q0eh4SPRkRgKZ0FolORLPJMnmeBwR2JyJBlRA6W2F/pmAiY7O098yhFYyOMkgRxY3BMZKgRykiqvVdlBJoNTpBKz6i5M3YMDEt5xxgPP68nxU+ipqc/4Z4j4GDLRmtqSCbxATA4hx8BzulyCXIPsU/UC8Z3f0ttIlX+4F0rXU3p7ENcDROE3eAxgciTKktECqsiHCazuDH2X7sIKvYykIBxQ/M9Ih6GPpuYGZSCDPGrPmzfPP1OJSTd+5xOnJa0P5EEhWYrgdPztOhKF5b6BjjReHJ7PiE3sI1maZVHbt1pVcb6tU8RfsnK7dSkbuGbyOy1P0ZqIzSpTbANAYezegkBubc0qZaBrPHO94d23SeYqV6xL7fWopJvqIHHmqDNsjEreQCxcwz67aa9HJY6GwdOEaS89bu2y53PHXmHnjhmv8bVr3Mo60vyAMaAv9H8kH4OCfZyQ40PdPrd48LrwGTpLNby+6EhMhbMoAjrU8XWfhHZ0x48W4kCs9vNHKFCmog739SqFT112mnR++CdSMFmVmj0c5iDhep+lVVNhnGkGFuYe0SP3hvuJitxzJPmkyyXcF/o5wEeS+M5vR2sTSr//sHGlULg2tb1w7khEjIz+OH7HD6AY8Q9IKwtQhgBIch0ODjGDj0NDYWFOOqU7eLCfE3X8iKRbtxvZUmaX6nJm5ZXFyOFjsWpr60jI+dujZbbd0cKxVMfHeZnvSiR0jbICJjK7uzP9MabP5GtcbLwhSwE0CB5Bj+74gcSDciOdF8hlRSsjW1uVsWQrs0R4KX7g/fcxtiNR0G2KJ/xfE46lI+lgTr5CL53F5HVHI28jeZ//Ha6PypdwgJAIjfKEqM+MOakf58I16RTAKJVPnB3lsUsNQwVAUC6GTA0drdxLCryPNv+kCTmkyeIgRefd6AHu5HdkyJEhRw5OzyfyxxH5zoHM0IeXRcqykGcoKyCcuy8dnSgFXae2Bc84pwpE6+6NHi8DUoASZSu8ZcoJ2WwTUY8cXGFR48zNzVcDuYr4CYvLDli7QJnkZZuiN488KY8BDIh+2YUXgJGDf9mwkxDodHQJ3PWN/ljtx+adQPBxNOA/EqV71QlTMOhTSe5IHCArR1IfqaB4qgnkDAL0ehBQ0HEISTkoyWMbl8rgo3XV0XkmN9m1Rf1GhCKTYPIRZ6dep76nNn0rdDrkfdwUgDgNjFmoQjBmCyqxzVRm+fZTiHJLBg/f6bzjCDg4DkAKT5rPNXznYA6B9B09AKik9gCAZw9JpzlVhM2lgpYHVh2sUciRI2dKpz7G5DiYS0Dn0biirAQ+92gMcd3DYjLfDp7CZ4ZABJvwtQ4aAxOKfZLkiM2zdZconyk5FKg84LF2lDkedPyTpaNKLyAgn6l/g8AwwBHOI5CTQZ5DSWYj4bL3ni2M0X58jxcuDH73CRgdONOh0ZPoHaWCzq/a4CCqxwqiddosCMrEaHQ+3IuySKVQIJGaw5+3Y2Q6DlAwdmpaXZufn2vNDfWe4nFAbixqlzSXT+RDG1yPwpnQAvn7onT5RQbV93ciH3/vb41WQwZZ9HW4LHSkU3r7ULiur/t9VJLvgcO/Z1hJaamPkykP7KI9LpuQPIlWORiujBQN4vwa4MF+k4AA+WNanQuTnj4ZR1rsPJBCZ/hvyA8wgPy8focO8MihazkChfN9Ubg+lYLduC0p5S4sLBM49VpLa5tlCwDwucxMAZLU6PvtE12W6Ozy8dbW1Vv/AQNdNswz8fweZ+c7T6gAAVa4MkGOnZWXlx3oPwS5A/ymZFEs2sE2DpRNSRsK40J26fZzLOrbCo9AOAmdMcuPIaMMotypIoSAsUGFJcWYy8HIITpURUeiwA+RtcdaWtpt1aoaW7hggQwUQzvY3vHQAUNNEhEKoMhIrvJjdteB6TgpKOtkiWwExyerwBH+IOSgF8YY/o6+93Sz4CuSz776OqttkFFjtxqnZzfu4AEa+fNwA0W+fckFQEHePCrjUZWv4pONABTU/zj/qSVsI8U+BD48ucGByUZYLovThUwQnnkygh/s2b3HYrFi+UWBrzdgsrihsVmZQcQzsx4cR6eDcj3ASzLgUALRH32H/t8KnVALKIjHPCx7xPggJjOOh4JDH40YXK4QfcPGjVYn9CRaBoOgBjpAqch4gPg9KSSMzbflJuyFaTPstVfn2Jw5861lf3N0H6h+2P19E7PcqQRq81hty7p19uyzz6r2O/pz01NNGD8Lb1avWuWP5P6vKTwWbGlp8hWBU599zpr3d1usKObP01Nr+4jSvx+dAuiSFtfU1HjKz9oCPnH+U0E4ZsgkA38O5rI533YtAGOzFHsFMgj1SfuDmBQGFF59daY11Df634sWLvE9A2yuglIdPmRMbqtq37MqtXeQIjumoIwO3ZNq+0k6Hts9Gh3e4jGIZ74sXGARBM9PTzUx07ls8RLbuH6913OBqAE9wTwW2klI1GVhP/7qVa/bh6d8zO7/1L02dOhgP9cXHUmQTOSkErvsiED5BdFCmd17ar00OBZF2capIRyNlXBvvPFG8ozaT4mk4e/0yJpKR/vtuEmy5lk2i2pY2XjlVVfau971LkVAXhTS7r+lE8tLT5RYS8ACJ1Z5skPPH/kmnf9U0ZHaqh5Q7fX8TTfd5CszsZMc6poksUGJ7JeNQuyZ4O9b3n+LXXrpZe4fx9LD/xUd9jiPiMIsNyv3nntO6C1EY4XUlClTrKGhwX7y6CO+QIIBDh06zD70oQ/Z8GHDbOasmbZz5y5bv36dp7+3vO99viHlF7/8hW8mYO0020x5Vnvbbbe6UfzPz//H72ON/p0f+4iVFRfZtBdesJdmvGwVA4dZa1uXXX/DDTb5yndYTKVdf9VEvH6om5mPJBGRZ82c6dtIeXZ/+WVX2Hvfd5Oizm7bumW7PfnEDN//XFDUa8OHD1IWYTKghfbyjBlC2kxXzj13321jx43zuiudyGx+97vf+XifevppO+9t43xNd5kYevLpqVZYMcTWrquxAf2K7cO3f9Cq+h/csBOilS/SUcds6GD2mqW5OMsNN95okyZOtGXLlvlv++rqPG1kBx7y2Swjp896nQf4vvCFL/gnkZWtwCxsoexg5WHqho1UECspLbe9e3a5fFauWGFtytg++tGP2iWXXOJ6ZuUi23V5jDn52mvdwFmizHkAZoYAZsTwkfbXd93t+whYIclOQkGH/fqJx6y6ur9dfMkEmzr1aZu9aJmNvvAq+4h0mdUmo29vtMba3c7vpi07bPCw4Xb/PXf7GFlyOuPlGRrjZt8Xcs8997is+wJgtuV+/3vf94U3zAEMHzHcF129++b32DPPPO0rFrdu2+rgcOMNN9rkyZN9Uc7DP3zYN+EQUe+/734bMWKE7zxlvLNmz/Lx3XP3Pb5GADChrAiAHgj+Hv7xI/4OSJZMT5o4yYoFch3NDbZ44Vx79nfPWovstEth6atf+7r7CovQ5qp9Vj+++z03ejCDx1WrVtoM2TYlzAUXnG/XXHOtb3TCPl6S/gmo9953X7LnvungXpWI0uV1rMw6gNBha/UxcIySdeAY00c+8hHf2siSXdZlT5g4wQX20Y9+zIXPaj7qzQXzF8go3nAgYGcfe89xJhTMrqmqyio37DVrVtt1112ndGiR76B64IEH7YbJ11mZDL28X7nunSgFmF17/Q3q4w5fsz6osp91tLdabl6Oav4ko0liyyX75B948EG7+aZ327ixF1hnvF39v6z0frbV7u605qb9tn3nG1LwUNu9a48L+L5777OJcjrWko8XQDFrymKVdMHxOI496Sjun//5Gx7ht2zebGfIiObMm2tnnDXG7vz4x23rmxvlYLuNvdQQTo+QUYz/LeUSoVk/zqIglrsCgiwj/a1Khquvusru+NjHXJ5Ec7ZDP/bYY3brrbfaByXTCdLB1GeesauuvtojD21eeeVV/tvIkSMVlaKVj9GM78ExMMGGw7N//xvf+IY7BQ7A9axhZ7cf23IBb9aLs8KQDOYZ9VXVv7/dK4fcJZlRT7OpZ82a123kiJHW3tGmVHaJjR9/voy9wsaMOdeKSipsT0OHvW3cWMtKdFlvAmB50TcG3fHxu3zLL1ktM/VPPvmkXQX/AhH2EuzYucN3ORJ4UolxsioPeVHb3n777Xb99df7dl72P2zbvs2mC6Sm3D7FwezVV161MeeNsUd/+qivurzzjjv9MSFbnydcNMHfrcBKwS9/6UF/YQiBZ9zYcdHEofoOYB2I0u66ydcrYKDPnuQeii5bvmSBbdyw3u3oXVdfpUy43saNH++AzZQHuxd5lMc7KWIxlqevt0WLFtldd33CswH8pbikWMGI1XsJX7PPc372DRyVUoIelO74fQFnKoXRHZY3M3A20LBmG+f/3ve+584bHnHxvLu1db87P9fhMIAF68gvnHCh70sG9djvzDWBQh2DENibDzpffc013iZrsVmCCju8TZS6saOtzYqY0JHgWzu7/DqejacTYHO5DIrf/MWa4h8e33fLzfZ3X/i8eKy0T3/6szo+bf0ELPQbLflUHarrWlr2u9D9bTICsHRiWS075XAY5jcAwcsuu9wf/Zwx6kyN8+2Wn5vnew1C6QMPR0rv2CXHngVW8hFBiEDsfR82fLgvR2VPPpnHG5RTyrCQK0tnWSLNLD6OSqlBVkU/GBo8hjkXXyQi5YcDuQDA9PeP//iP9ujPfuZZHMQ8wYqVK+3BBx7wrdds1GEMRGT2CwDQ7N1n/zr24LvHiku87uWgb7KO0Hdf+unojFu/yv6+bJnIl5ObI+Dc4qD/y1/90v7tW/9m02dM17h2ux2lEyDBDD+gw/JYvtMvjkoJwBiJwqNGjXK7o9wgNcfRiOzf/OY37YVpL/hmJPqF75mvzbQvfvELPkezauUqn6wm+2Hc6cSuQuyYYMjEHtu+WSrc1LzfBg0earxvEbvFnng7NAfyCAf2DiFz3n/wnW9/x997sGDhAjl8tDaBJxUXX3yx28PxzIWdCjrM8b0uUXQC2YhMNyjVZlKD+oqIz4YSNrqE3XikKQgFx2Vyjhqc68bq/mBgqYSxcj0CJPKWySCgflWVHoWok1AgwkbRviZbDodSqMO4P5UApM1bNvt2RXZlQT4h15stRW/XNx6pCRRIFZhMEX84JX2xeYRddggfhyGNTCcMC3nwmSOHq1SUIIPxTT1yuLjuJWvg3sqK/kd1esi3/yqyME6cOoyVUgCHBoQwalLvShl7ZOAJN1pki6NhpPDPa8NwesbNdWFhSSpxbygH7lMaeY4i5+NK+8nScGqWjX78E5/wl3t8+9vfVtbVL2mwbFPmsVRc2V61lZYVex0PgPgmJwEWf2PwvEV2//62yLl5q75E7Y/wRGRK9MUnJWJ4NwFAQpS++5N3279+8189s8HJ0gkwIdJiM+yuY0NPcCpkDlgQlXn9ljvQpItdpoDrbbfd5uP61Kc/5dkOGSUZ1bWTr/V9+2Sz//Iv/+Iyxc76sleoobFOMo657jh4woBNsC2dbIQMMF3ugZAZeiHIAMBkh3fccYe/i4AXv1K6NTY2+MtNeLfE8U6Wv1U6LNUPz6+J9kzkgYbUpYMGDfIXdPSv6m8b1m+wbVu32Y7tO62yX6UcyvT3DstT5CMNlHvJKEkzc2QgDfbqy6/azh27bN6ceRbLj/mLE0aNGGXTfj/Nf+fNNPwPFzAQJvQaBT6LF/PKrzo38kopjJdsdAgA2LCjWEYKIW55nFJqs2fPkdJafOKHTxyJd/NlZxXY4kVL7JJLJ6h2y/EUjXXTzLY2C7HnK92qrd0nY7nEsxccmx1+rD3vVJbR0RFFsJqa9XL4KhnIEH9pR2FhgdXpvrlz59jGN7fajl07bLtKjgvHXyAHqXAwYvwAQ4St0Su8mAMpKioWaFRYaUmZdSkaRr/FFZGWqR7dpfJkrtL/s22cZNTQ0CTQfc1ni1cqMo+QzEaPPssjBRuc5s6d508/4LVYkZgtoewVB9yITuFYt26Dz4jT/2YBCNedd95YySfbli1d7jquVx9kEZR0zY3NqkdXqxS6+AAgYui8PLNYAEB6XNdQb++88h1WqTS/dl+trV231l+SuuH1GsvPypDOSsRLp79xiC2se/bWWlvbfgcpAgOTYbx5prml2V9USRTHgQEF5BcOttrSN3bBTkXGAYAAkuh5/br1DnpDhwz1bALbwGZw8qVLpGe1T52PDZOV4ai8FJTJaeybYEUpALBHjx8FNpIn32mXGn/2rNm2SZnlLgU7Sp5K+QHbwae/NN3lv3DhYtujtiYKdPCdeQqSq1eusJ3yiYRk5luRpfdalYnU/9vlO20KakwcFuQJYDOzPSt56L8fspvZwMPMv1L6vg7m+1MP8oPUw3P5oxzhusMcHwGBQmxb5BMhUm+SAbClEaNiKyPGgjET/YgO1EekgvydSqTJEAol/Sclo8ZE+aAvaT3LF1EIW2orK6o82vEm2Wal4Wx15MWEedlEn+j1yihF/3i7GMewocP8LawIfdCgIe4EOH4i3uuRiv35AAuLKEpkLABYa2u7XXjheE+1qR/h0w0suZgE8dA233mJ5vDhI9wBmpqb9AtLNZUB5CniFBQ5GFysEmCYPzWIXhgZGU5M97DGPNvHRnu8oYhxM8tPhPFrJDt2rRHdqJUvv5zSpdP5AqzQGDy/7/23esSkPXjB8DuUWhJpS0pKHbQiDR8kztEPWQlj4d2Hl6k0Ql9MqvLmooQACrBDRwMHDlL7ma7XsK/9IPUq2vFijiLpcJgNHjJYv2d5BogeKYUGKzuoqiiXoRc6X0MUMABVyhaAnUjMTjvPUgTmvDwUuSN/bMAf0+l7OOCNIVGecQ3vt+P9fJ4pqUYuyC/wfigFmKCjpKRk4o1OvOmHrI6AhM32U7lE4EIPZBGepcnpfamw/uM813IfdsZ4yFTQZ4nag3fkOUyyqRCw5GjsyP/tkif1PS/LRD9sty3R+AmW8IWe4BGZbty0wcEDmaDT0rJS9ymyVsqQq66+yvs+3XTYrD5MIAAcm08cFCMJaRDCYBKGTwRCCgYyQnwCDpA7Z5JoM4AG52mPtgN5etwT1ayATUJKiRWVelQjlaWGzpX9sdWT1D2iqEohSnMfjrNLdSKGSPqHc4TzRC1Aiu84IpEN4+YdAr///XP+WirawfB53MT1tAO/KI37GBv88HYdVmzl58nJVDpk6/ye3bU2cECVtbY0+bv2mcPgegyLfuEBo0Fm0fZggViyvuNvnB9+GDs1IdEAHkvlCJ3tbM2N/scZGA+lmJdYcmLmNCD4hZAtv6VSlB1Eb6sJ4MJ4GBcOSypKv2QG6BKHpH8icEMDbw4+WPfSdlYOux4xmaj84T2G2EHQS5EAm/cg0A8G7HIStSt7wqZwdgwf2Qa5UqsjKwyf+1KJNnByojHROQARfYcj7O9PfSSHzJgPgDhPf/RBn2QPlAVsE2d8OCuBg764jr7IhvgN+0c+vfzm/SkDks74n6pEco2W4UbzUNE2Zfqg1OHvME6OiN/I3chu6I9ylglfJh95wkDZkeobp4sOcXyYpFMUCaMYG4PD0UmNguAwIq4JSuIeF7zOhXsZJBQGj0EBHrTJtQgVJYLowXCCcplB5VE8LzWgHu7VNb41140rROSDBg4K0w8GS9s4DRT1nSGH6/BP+uRevvNJ1F2wYKG/MPN///d/XdlEi/CcnnZ5fRPX4fTcnyUE6lb6xjoO5NCldroTZABmHer/iSef8iwCHnBqxjxC5c8NN1wvGUTPfCGciL+RB1kVvNI+Bou8cEqcj+sC6EKRnCMZYHQAHBQmNtOJc0EXECDBtZwL5xkbbTFegA9+4BWCv0DIsNcXn4iS6yFS16ljyA2NTR6dec5OBOZlHA5WAgz0G4w92ABjw7H5fPqpp61mXY23FwjAZJIR0MNZkUmkux53yNAm5+AhjAnHCsRv4XEd52kH28N+AZ7lK5Z72s53QIFFOLzog8nqyddO9nuYImK+gw048c4On3Sm/GS9AllZXkGh5Sr7YBwO5HJwZJfqU7Qfj3d6n9hOKv/IgheG8Pcf3PGDMaQaUOrfRyKuCQJPvz6cT/+EuDYcODQCjlCbNfoHoxgGh+MjzPT20yn8TmTlPj4hjB1h017qNVBqm6G/oxHXhP+biVxI/zKrQWp67PZC/xgEn3zHiNMJo4Df0GYg2sLx0yN7aO94KfR9LKIvKIwhcBqe0gDU0d9JQFYWlMoHq8+gsGg3/Bb6PvCZIqPjJfr2T7UZADN9TKm8QMcz5iNTNAbPJg4VP9brT3rCrHwysB9GASgDpfPH91Qe3xq/R6ZD2KfTdEaOh04Vc+ElCk6pK+yEwtCJ8JbuvERGnCi1Da7h8BQ2eaTfl06pY2UDUaoAj7c92gh89OX0EE7fFzGGvuR9ono7VTo7GYc9HYTTn36KdJXeV98a/OOm0yYtDOt4jSu6lkm7cMiBZMdE0Si9j4hvfyyE0wdK5fHPjQKYBcLR+3Z2yUPRPp2I9CHa/zlRZJnREdwImyXSHynaHw+dKkA+Fv35aeQv9Bf6Cx2DzP4/W0oGV0lIquUAAAAASUVORK5CYII=)

其中service_tree_idle就是用来给IDLE类型的请求进行排队用的红黑树。

而上面二维数组,首先第一个维度针对RT和BE分别各实现了一个数组,每一个数组中都维护了三个红黑树,分别对应三种不同子类型的请求,分别是:SYNC、SYNC_NOIDLE以及ASYNC。

我们可以认为SYNC相当于SYNC_IDLE并与SYNC_NOIDLE对应。idling是cfq在设计上为了尽量合并连续的IO请求以达到提高吞吐量的目的而加入的机制,我们可以理解为是一种&ldquo;空转&rdquo;等待机制。

空转是指,当一个队列处理一个请求结束后,会在发生调度之前空等一小会时间,如果下一个请求到来,则可以减少磁头寻址,继续处理顺序的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请求队列,其结构如下:

![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAScAAAAgCAYAAABQKL5NAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsQAAA7EAZUrDhsAADXUSURBVHhe7Z0JmF1Vle/Xvbfq1q25klSGSlIZCJkIEOZRUAEFERBEZdCvtVtbUbS1bX1PtD9fv+739fBEbWdoZRRCgIgDgRAgZJ5IQuaJDCSQoTLVkJrrDvX+v3XuqdzcVJICwe72seDk3HPOPntYw3+vtc/euyKHDx/utj9XimSyP0TdUYt2F/jZSc8ykdQxaXqjqCmt/u2OBM8j3TnvnIiOypuydSgni3Ycuad8j1Af8z0ORSXJTCT43a1z5L+ZZEM+Q/A64LOuJZfuqJ5Fu3SdspgOeNfdXeLPMlFd82a2vVkWZCmjvDK6R15BmozB9yPkciUfvXgkj2Nl0X2UrP770tH8OQ65LfTWXvEzy+9Qv5FZlPQ6wrxD1XN9zLw1RXzHuB2JHGFB7u8/KWUZFjAagqEAUpa50DFpAuru7p2hofH0iY7KOyybcrkO8+E6PP54wrgApuNRLBbL/vrj6Hj8+WMJgAo7gYDgW8AbQCWjZ1GBVhSA4t5RaXujI7z2d3r4D7h1O69SkQI/wvwBJuoRUzkcb5ds/vzoCG8y4mWu2r0dFh+76667/iH7+yiKx+PW2tpqhYWF1t7ebv369bNMJuO/OXd1dblwAR6uOUhbUFDQcw/ityuBDp5zbmtrcyOJRqUuqZR1dnb6dZh3Op32/PkdpsulsrIya2lp8XQVFRX+PJlMWlFRkckT9HKamprs97//vf385/fYxldftUEDq5W21IqL45bOJF1JYWe0IO6Mpc8OPQ3yo54dHR1KX2zdmbRSdltaCgxfCmNqX6rL0qp7TFWLRGM97eR52D7aQF7wJGhXl9Kp/43ElV9M6TPHpCef8AiJNOTT2Njo7du8ebMlEgm/z3ttnR2qY8ZKS0qsQ7xsFR95Rv1oU6I4YYcOHepJD39CnkOh7GgvRwn5ZNsOj2kX/IbXEHWgTbzPs9y6QvnpKYv6JooS1trWagsWLJBcfm4zZsywYcOG2eCaYdbW2mJF8UA/IrG4v5NJpyzdlbTCAulAgfRQ16hCIpK01a+stH/4x+/bilVrrXb4UKsoK7WUdKBFOnu4sUltT/vhdVDP/fwLM+zuf/tH275tq9WOGG8V5VUqq9M2bdls/+v/3G1LV6y2EbXDbFD1AGttbLD25ibramm2Fp3bxd/K/v28bknlubdur/RW+aOf4gM8OnjwoMtvz5490oeoDaweqLa2Wb343ixe1Dc0WKn0VsxSHVusubnZ77crDed4UVwH+ttkh5sO22E9h2dQNI+/rq860JsG6URTU6N+t1tK9SgpLbEu8QEZ1dcfkmy7vV7wE0q4Ph8Nti0qr8v5nRFfyq1J/Esl05aIF9mBffutSXm1tbZZcaJU70o+0Yht3LTe7rvvl7KxP9igwTU2eOBg1VMdR0a2KJlFYwXiW6dVVfVT+UHZb5Z6BadcZYVBGD3AgYL/4Q9/sP79+ztAcCCw0MBIi8KSFoIpEGkg7qPUIbhQBgfvAS4AyrPPPqsGVfXkT11yCUNAGXgPgw0NmrpyTT1QyFWrVkkxGu2OL95hV155lVVVVAkQMlKMZrUnJkMosrb2pLvqQf0ECLoK60peDijJTosLgeIyrJb2AJDbpLQxPY/LmCg7JaHShtDgAVwMOxKJyUAyEmy7lDhqRQkpGfVPRWWopdbZBSip504nlT6hR0GZIWiE5HVVu7Zu3ert2rFjh+3evdvLGT58uAwmaSXFJUrT6u9GOKRAGGWB6tmZDECyXIpHHckLmcIzeJkoKhEgFWfvF0oWpA+ABy8jqrxoD/ILO4Twd2lpqZ9zibLC9MiHfDiaZei08dFHH7M77vii3XbbrQ5OGFUBdRb/ea+1vdMqKyt1LypgilpHe5u1Sw7pwoQVqH6l1maH9u+3pH795V/faVXlxQLmhBv0lEcftRdffNE2bNhgg4cMtsqKStfPsWNG21lnT3CArx0xUbyoFK+l0wKNpo6I3fk3X1fbpb9C85bGgzb11w/ZE49NEb9X2r5D9XbaGWfY/v0H7NlnZtjcOXPslRUrrG7fPps0aZItX7bMfnXfr2zjho0266WX7I033rDRp4z283333WcrV76i9K84qI0ZM8Z58uSTT9jjjz9hCxYutE7JYdLpk5xfzzzzrD09fbotWbzYAQ/5lognuRQTWCckv9XShfvJX+c1a9ZYXV2djR49WvLI2E9+8hNbunSpp2kS4NXUDHVeO1AEKt5DC+Yv8PTjxo2zwYMH2xNPPGkNDfUOcj/72c9t2fJlaoP4ULdf7Rpl6e60DR06xCafNckOHNxvQ2pq1fkPEe/kmCi/in5VrltF2IR0SYgWFPQmqVdwAjgeeeQRmzVrllcKhmIMv/3tb13omzZtstdee82VsLa21hlTX1/vPeK8efOsurralYv7KG9xcZEEu0/C2mUjRoxwA1m+fLlNm/aUrVq52oYOq9Hz/fa73/3Oy3tVng75Y/ikzwcorgG5BinW+vXrJegn/T3KGjt2rHt85KHX7bSJkwQsxW6M9EAvzJwh4U+zxUuWSmkrpMDDlaOkFZF3lBWa99oqA3B8fuZz6h1+p/QvWyxRpvQ1tnHdGlcOlB5Fe3nZchcq5WMYTzzxhO3cudNOl8IVxRO2Zt16K4wLEIsE2DKyZUvW2+BBQ628NC4eP2+PSxl27nxD6U/3euYbewj8Q4cOtRUyimnTprkne+2113od2juSNvulOTZPhrFoyWI757xzFa4IbKUUs158wWY8N9PWrVvnhj9gwABbKIOgfQMHDpQyxdS+pz2/117bKjnUqT5TbcXyFV7HQYOGCLgStmXLFpsyZYq98sor3pHU1NR4e8NOIZcAwTA9ckmnuqVDp8jT6HKZrV2z0d7//iuUMiNZNVtSHtEG8ejxKY/YwkVLbNOrW2zCaZP0OG0b1q62qVMesrXSudVbdtqE8eOsKpGyvTtesx17W+3Ciy9x8CovFTiphx8/frxd/+HrVFbadknfzjzzTOuSl5NKy1hiSdu27TUZ/EQrE2h1dwfgtLOuycaMn2SlxQI+gV9RrNuueN9llulqtw988Ep7/1XXSM5pe3bGTPd47rzzTps8ebJ0eJn4M8jtBX3//Oc/b2eddZa98MILdopAgs4DI/+rv/qsjTn1VFu0aJFdcP75nvaSSy7xzuSaq6+xaz70If1ul6xedDv60pe+5M9fFQ/LxONqyQnVDI9kMhV4iGovnfRtt93murZu3VqbOPE07+RxJG6++Wa78qqrbPy48ValMtFrOh70PFdm++sOqH0p17GRI0e6TRXJkxs2bKg11DfYJ2691e1qy6tbpedDbFhtjfRHXnk0I/tdZTVDR7ieFEqXAKd5s+faps2brHb0KM+fTuet0NFalaXZs2e7a3+rKvWRj3zEPRmU8dJLL3Uwuvrqq6Vc73fgQFgAyQMPPODKj4HNnTvXmbZY6N/U1KDfMXtNyrR+3WY3pvUbVtuixfM8n1tuuU2GMcBOOeUU++AHP2ijRo3qyR9GkX8+YVj0xADm/Pnz7UMS7kc/+lEHUbyL7373u16fB3/9sP2Pu/6nPfzww1LgDntq2u/VczbYxz9xk118yfnqWZbJrVaIl0e0A3r66aflpu+1Wz5+s1188cW29OWl3quv37hJvdReKWWzKwLtxEhnzpzpoHTLLbc4sAGaKfUym7dsk9EfVLjQaM1SvvmLl1iz0j8381nb+dp2uy0nfT4wQQAWHhFeE+CC8l500UW2ZMkS1aHN9u07IKAosWs//EGrGTzAHvn1VAFzoe3atct2vr7DbrjhOgcyFIx8AAhCQ4yHzob3K+RZ7q3bbVOmPmyXXX6xnX7GaQIK5NdsW7dst4ceesh5cM0117hcIDqPfC8PQgZH0l8ruYx1o3vwwV/aP/7Td+3lpcvtzi991b75zW/KC4jYmtXSBxnuDTfcYO+RUW4RgGA827Ztk3zn2O23fszOOesM1Xm7lZdVqvcQ0BQWOF9kUwLDMjdUPDruUS86OzyMwHuXZyvPFK+pta3FugU+hF6k4ygkLwGwnFxrl2cRk+4iT1M65JvJyqRYHuzZZ58t3Qsii3EyejpqwAbDJowDmOmcIcCgQOEoddsnLyu8TyeZEXhCpEHH2wQ2hInjBb7oNyHgGfLWNm7a6OlyCcCiPGypQPUgNDwk7w79h+g04MOBAwe8Y4PwpLlXLA8bvvRQN5FDxD3X1auXK8RssHhhiTqmYV7vjg55re2tzkc8Odp3SGfywqOm/DCfkPAYkR1l0pG9VeoVnOhRMXwMDUJQNJieGwbjHp6qnmDIkCF+HwW98sor7YILLnCQAWBwUUNhoIBRuXyWKbGmhqS8kLl2xVUXqZc5040iVCrKpScCCCdOnNjjjYRhQXhQHsq+Wkp9+eWXe3m4vwga8PzBD35gt33qk3b7Jz9pd/9Qv3VmkHXlilV2yYWX2pBB/a1/P4WkgvmUQh/OuUQZlLtM7vp733u5t7V/VYVsgnGtYhl3o4854G0AeoAZSg4oUz5hFwqL14DSHGpQDK84fHBZuY9jtEu5MzKWhQK1YTWDnc/wgPbQrvz2AiIIecKECc5n+E85F154ob83cuRoGVTM1m2Qd1eQsv37GhUOlcow4jKKvbZ9q8Cxbp/LBIW+/vrr3atF4bZu3W4XXfgepSfMa7Prb7jazj5nkoBsjO3ds88V9Y03dtvZZ53tIQzAhHxQUvIK+ZV7EE7gwcC3cWPH2cDqwT4U8KU7P2//6x++I6/jXPvRj35mP/7xj61YRrZJQPmeSy/3d4Yq734KCzB++HHJxRfaKafWKpyoVehWZnV7DyrUVuek0CWpM7qPoZaVlFqhQtEhAwd5zw84TZww0esHYWDoGCFwtzqM7u5UT307OxnrVGhZKHOQQaUkn5J+Q61ZYX9xeYUDWYc8m65kh9UOrXGPLqIjqfciyivZ1WGbN26wWS/MtOeenW6VZbIVhZQMqm+VB/Gr//gPe/Lxx+XRfdiq+w+wZhl9JqmQOFFiLQKmQQOq5bWVWOvhZutf2c9BUEhlB/ft93EfPnLkHkkAV8/5vWHtOnvg/vtV7rNWrLC0NFHsfODdxx97zH74/e/bb+Rpd3V0WqvKSuocgnJ4FBWX2qCagfbhG6+0+YtmW6a7UIAp3ogXO3fjeNznnc2NN97ocqwsr5I+d1mM91WJaCQYc2UYIyrv6aabbrQvKmyPxQpcjgHM5B59o15T0ju8733v817jqaee8jOKjYGEXgsAgevIb9A5HH8AkN773ve64qIgEKCBYpSWVsrQuJORoNs8r8qqYh9swwDJE4+NvGgsyE+afCJvDtJxRjkhvA+uqSdjQtEY4y0ShhhYL/eU8KK6epDKrJDh7bKyHAPLJcqklyUf2tMh9xtDLhKgtOg3AmK8iXEZBiYJMak3Z3qNvXv3Os/gIb0yAIKQCgSQhULC0opya2xt8Ta+/vrrDkjwF+AJvbZ8gj8Q/GZsgI6BdlPHtWvWyvNYaB2dLertGgVURVIecyC5VV4ZvTbhIF4m7YXPlLN27Vp/f/iwEcpZqhDJWFt7i+rC0Sq5Mj4R9Y4KojxkDCFz2kh98ikEa/jk3oN4wDVeC3z0OkQLvU3wL14YyI+gIBjobbe2jiAETCkMSUpXDh7c73kNlCEzjkeoxjkjgGo41OgdKHKD/3wIGTVylI0YOcLBKK0QhLLQF3QATyglcOIMKDHmlUp39egdLWpq3mdJ1aWls8ui7mkIDKRTjBuhy/CCgePw4wHPCuUlUYfbP3m7dKvMy5x81mT7++/8vV16yaXupTIYjj5UKKxsUzhaKlCtV+jX3tHu+kt9C6Vb8BDPhbHEfMLz4jnvnzn5TPv2Xd+2T6oDJnTHW6Y+dI5f/Zuv2j//8z/bLZ+4Re1Oi+eyL3nY+XS4+bDyarfhtUOs6XCDooU68SLqZZ9yykj7xje/4R4zHRoh7MmIeuMFAqIdkp9U/i1Rr+CEoeBSEsbhkRC2odAoJgrDNQYFk13ZCuMuMJSOM4Rg6N1Rlt17dvtAemMj7mChwsFRtmL5ancTd+864G4mwkXRES6eB+BA/hhPPmEYCJK6EYIyxgSQoVjUnee4mygLAoQymaT3/Js3bFRvttVDsFChKTf3gKg/6Tdt2uwCZxypublNzyMODIQh1HG6Qj/KIy9AGWUl1ifsIjzt16+/DR4y0L2JBvWM0599zlqaGq1UMT3jFgn1noSzIb9Rut7qExJ8gseAHcZEe19e9rLC6TPsqiuuFkAWWWdXuzW2HPY2VMkLITRnrMPDB9UVImzGiBlA7T+gv/PJwUfGUsIhJebrH0Q4OHvObJc9suFMPaDe5INHiSGiI3ydQ0doB/LgjOHQTnQK/tOe1WtWOwjOmfOS+NrkwIcnzXAA4dI8hXcHBQyth1v9C2u0gI8v6qTUAfVXGxkjoTN88KEHne8cfD2CyN+PeLF7IoXFhbrWkeDMM4GBAMHv6ZpwBCBsbG5xoKdjo8548oTWjMPs2LnDXt3yqodStGG8OowPX/dhu/2229yosRXAAL2AzjvvPA//vZNTGfv21bkRA0ypZMrbihwWLljo+dPuza9udu8zVxc48glgA3wK5KkQvmIHyId2UIeTEXJh0L2qstq93Dfe2CkdanXZlagd2DW2TPi/d+++7FtQ4DgwlwmvCQKHFi9cZD/+0Y/cOehL+cejXgfEp0+f7oOuhDUoGoIOvRLc+ZdfftkHy+kZeQ7yYiyABcIgHYzn+VO//Y2HN9dee50aPkQCrrYxpw6XIu6xqY/9xjZu2GT9+lfJqGKeF4JmLGXOnDmuEIyx4JHkEooNMBAGIOxf/epXHvsTblBP6tIoACiQwg0XU2NiXGG0wIYPHmJTpjxkGzauVJs+5K7rBRdd4L0mX/JCgMfoARmUccqvH7Stm9bJmK+yPY0tdtnl77Ohg/rJhX/eFi5cYDfc8BH1dEWupISXDDY/LhceJaYtg1TmELn4c2e/aMsWL7BrrrvOoiVVNlF1nzRujG3etNGenPYbWyP3HKViHO9EhHICCOSNcScUZo5XuDftiak276UXBXKTrd+gWpt0xiRbvnSB3SfeLF68xA4qvLxVhhN6TbQPABk3doJ4PFBya5UcD6m+A23woBrlW6ZOaJfyO1OKOVSGU2X//u//7h4YRg+oIS94lU/IgfCc9LNnz5FMKiWTiMqMCwQ75bXW2/nnny3jSVuXeD/6lLG2ZtVqW7ponp0+6XR7bc9+B+xxY0YpFF9is2bPsLPOO992vt5gH7jyCispSAowGm3vvg55Jmd4vWPyjgHONavXSL4bvDPgAw2hL19K0wrJ2tsaXd9GnjrJSqXH3erVDx44ZFte322ni2+CSoVKQSj2sECu+XCTbd+2TUC0U2HtOTakZqi9IU/36elPuxdx6y232liBR714C7DXKOTrlD5iI8jpwMEDbvijxCv4DegAIADvczOe88HkbQq5+XhA2DzmlDEejdBprFu/zm679bZe9SEET7yYl156SR3kdAeyyy+7XJ2Q9FmdEh0WH2fwlvHk6Qj5SACIARpHKPjSzRSX4bWyn9IKe33nPrtQdlHVr9iHLYg28K4PHWqwxoZGGzd+jMBPXmt3l61eu1qd7wgbPLCGITp5O0QDu2zFyhU2buIEG1k7Ujaq6CVbWkDHAmxv9EfPEEc5UfheKTt5zsknI8ZlVCn1esEgJddHO2/HhnAYIUbLAZ2oB4G4T6+RFgNIwaS6mP6LphV+Ka9opMOKSyL2ioxh3qLNduunPq3eoUC1COYEQQg9mKeiXloeV1mxwrVde+3+p2bZZz/3eSuLdSo8C6YwAGlpeVNQWMeQmMoXEuMPvMO9rmjCz1xzPyTuhe09HtG+8Dm9FfNOGBvIz586eR1lbNSCUsLJjRgKIMpA94033SgDKvLxFIY6SIknS/hjmVA+2Tpm5entVj2RPQCF1wrg0SlhGEdkk20/so/ofqZDIKKOpjvwejKRTutMdfoYB+M4iXS7y+vffnaffflvvmbl0ZSVJNLW1lVvh5pa7J5fPm1f/cpXrDLRYetWr7Xlq/baTTffovrKG4x2IWWvW88hvuCVxIvjMrJGs44Ge2bGTDvj4g/Y6FGnWqTrsG3Zut0Wrtli19/0MZ9wmSgQ3yyp39KHbLu7fZqz2pDnBYRyOCnlDBa/GaL+fs6W4wPp4i1tApzCaMOfZb0U7vGbd3JthDlM3OsSIJeXlfu9dnUUOBHI0GUbkf6or+lOF+ldlalrWbjyZMoMQXcQFcWEQthwc9tee3TKVBs74Xy75ILLrSgTs6ULFsm5WGRnnHOWTTjnTKUrsH6V5T22FVBWn05Cf8LlKzkC8hnaWXLBhc9OXmkYHh4nIvSJFD6jOFPgilfgYNCluL7dNiq0W/rKqzaoptZeePEZ3ZfwslniARL24Ip3tDSpp+62XXUH7NdPz7OvfPUrFk+1CugQHAobgNPJ6sPgZWjcqXD5hK65789EbgOik+WVT7xHHoUCDH53CQBodyEKqXbRNkoOwemnP/2pe56f+tSn1POPD0Izr1s+/5U+17Cy9cdbZaoGg6SEiozLEVLhMfGFji+DR+iIbHuA2JftUO+MDz5numX0OeB09z0P2Gf/+g4bVFFkyY5GS0farOlwi/3yl0/Zt771bYFQs61Zudb+9V/utTHjxtu3vvO3KqZ3cIJS6hCXL1tgTzx8rw0dPspu++u/9Ymfsc4mdTp77Dv/+kMrqaiyL3/hCzZq+DB52epAqa/qFnx2L3RgEAp6fn3Rv6PoLYJTSF//+tezvwICmBg2+MQnPuFhHGBFe8NQLp8Yf21pabUf/vCH7rUhP8a2iEyGyhu888t3ZlMeLZ8jOpHVA3cmGFY5bHvqtttDv/6pTwD+y8/+nU049XSLC9i2bXrVvzxOOlueWjxmSclVjut/VXA6opyhcvc0vo+VzKXeFKM3RekdnOQdCPUZj+qSZ5C0hCWViPCCyXcwMMzfvS95BimFO9WVCWs43G4dRTUy8Jg8p1YrFMBGIniCcpV7qVNIucDjPox4UECzdfbrXuh4eR2PyJt+rVD5knWnCuUe17lKkXXwvG2EvoCSG7G8LwYw03nVoe7Ok+x7IREGML2EXhdgIp8gNIi494RXhQcVEqBIPm7sWZkz+ZU68vmeu4BTPMOXpKh1FpZZRL1/RuBRXsKqA2Y5M2dIXmxZheSX1O/DVlJUrXqUKoRvVkWRR9DYXHAijAIEk13NVqL34vFS29OUttISeQ/JJm9DZc1o61B1i+R5pLvkhSnUjCqvEEyjAnvASbl5aBTqSJ/pjwSn3gCHwXjGE/GIINIAQr1RowCJUJOxrnD8z6dkqH2MH/LB4qTk4BSkK4wLCIl+oi3WIN53JoutomSAg1NbU6M8sf5KGrU2eV1oOWLh6yaE59dX+uO4dlLKzx6F1ZHT0B7AehsJ5mOAUAgOEIzqEpOiJWVuFOl0UkbCFxsZk4AIMOJdFBshYmCFRcXW3sFzqWqqQyEQMXtQZ1fQEyieK3dP+wR2AB6GqvvZLNxAAz4dP59cOtooJHhJnvoGV0fyCQ2rN0IhMUpCuUS8wD/LO6ktmCQHvwNAURNyiqQswkL4w/gexgH/ACgG2/GkQmAC1PKBDUoplEvLi4UYcA5r6mkxMhWYVvjBp+h2gV5HexBu0KaSIr7GZtzzKUrI4/L8j9dW5NZlBw7uc4CJF/ezhsY2K00EXxxpo3+ASKes5XCjTw0gNIorFInHYgI2AaMO95pILnA9mv9/GnIe5xxlpQLvLGDRGYRhHITxc3hnkz0gnre3BQPnDH43KyLgyxyTg8N3A7sM9bAXnqLLOpB9c3OrdXbwtTxhleUVPc8qFCIm5amiC3h4XV2MjwZfZd8MMEF/Ws+J1fg0PsNXIIFTRNc9xivqYcyJCQU5kZJgLHgG8QQ9Bev0UpaS+xkRMMZ9zlWhior19N5hHUIgC/MGrAqUNqJEjOukBUy4PXEBGvci3XxZE9T4+zntCEn3PU+1Cw+uCyWSgidkDHhPnboOjDdod7jbwYnaxjMPw0RMbnXFYixE3k8sE+SXisqIVDbXUNgu2hrmHZzVFj42dAWeFvVzfoh4Jy5DABBSvKej54tMVpk5H51fQPTQjPk1t7RZZVUwMxmvibATGTBNAVBqkdtaWVXtXlJ7a4t4IvnI2JIqrENyK4gJ5NSBYIc+h0YHkxpZEsE7jCZSLnIKCLAOvKZApgGYIJ9CgYwcZ2vDRZJuRAujFpc+Ms0kGUm4LvAeCzB8gTD8FEjyPt5yb+3sM/VRr/tKuZ5U6C3lGr7XWfUPiWsALPceRNsDytYvrGePPof1zv7OPmeeGGmIOPwaW9YzBsTDjkycP6I3RxfbZwpL/7MhVzAZHArb2a4wTu5leXmpozlKHU+UiI9SNjEtNMTjEQP9hCTdAihYFYnIKDJMP2BwNwuQJ1I8nvU8zwrcBZ//TvZZH4g64bFwhDN9Q8WkTWE+fVUIlkLkEjwJ+NK3+vRGgBHeDhNW99QFc90CAizSDl7UnY8OAC1TBeClK3QqqSMbZqsiEdZrZUER6tLznq9N8BIjAYyOQ0wA5ktwslMdVCamcKa/+cRfn6/F2kz16ik+HCgr3QkMO8jP5Suis/P6Zc//lQjPqDdg8nP2gPC4+kSun71RwOue567bgFIATHAMtqGDblu6BvveKjBB77DnlGOEPgjOoXsZJt3pzL1jBsdPTvkKknvNb5Q1nAfkMXaga1YgUGIiJETP7szU7+xjH7eBUEKnnvpwlhHE8FhSQc8lofBdx4XTI9DwHFBPxyRiPAePxj2SVIGf07rOHecJBZnfvlyibrSLsBWgoq1h+/ryfvjM+ZRNRrvhRUp1ydql1w/vjnN4z10YUQgGXnZOfiHB84g8laQMorJflUKzNnGq278eKoj0tB2Kq+tbOy1RWmGJRLEPmjIumFJISPuC/AJ+5pbn55x6kK6no8iSp3OZBCEnoS8z3aPRhHV1ZoI5VIP6+bgJy6ti8RK1kc5H3pmyoR54eoFHTNuC8igDnvlXs+CWn3nnhNRHve4r5XpOUMgXKORHLoW8yU0H5edzfDpar4+bn67DZ+EZCoYb3jwdd8uUt4eoYHioId6Y7JFVnp5rP46l3Eb2hWAQCsnBfKl77rnH55sw72bokBr/7E3PTXHoXG6pAf4HZWIk0RgJVD511Zkh0cCUBUhcAXTeDnrVYHZxLgVeF+DBm3KtI0nPIdKNqcYsI7c4ovd5xkGeJyPK2Lhxo3sctIPJfgzS+jP/t+/krj7/oaReMXgQHNnLAPiyR9i+Y9opfuXKyef0yOhZKJ4oLrEqhXayGHUMaqvzNm3N8pbmzl9op46baCzf+dlPf2Lz5s2xEbW1/hUpoCDP3HJ7M6hjwhVPr0P/s/6LxdaMOS1fvtLu++UDtmjRApVRYaNGjRbAK4hTmM0bhIlQVI3mOsCkAIj8Go8uO20mfO5p1KZ8nhxNJ3r25im/rGPKPpodPXTS945LvWfY1/zQ7rdCvUIag5qERngfCAMD8On66nEee+wx35qBrzMoJGd6Slz5lAya9HwZoPfjN3lxdqHKy2hqbNU7LTJmBjxjPe+Rnhnj5L99+3af+cw9QCYfoLjPgYEyaY164kmEoMIzZuOyxuprX/uafzKnTighs86J0ykXV5d3vLfMY6C3hfEpcYhQpLWtWekVBnSq/FTMe2KaxGxsAIpQDx7BC87MEk4pXOAa7KAdHkrwJShezEwarxMAzUQ9lnPAKwarEXLuQXsgdnJgfhJ7BjHhkImGzMli3RdjJJQbhrTwhrbynHEcBijJi4HwkFjgGi9OuPGVyVjLFYaVxuJWLA8i0yEvh8FWhUQsQeCM/KEQ/OFdb/KhzZRJe+r27O5JD/izpqxTdeloafPlFoWFURtZO8y+8c1v2uhTTvHVBxB17VAdABVAmDlnlMN995SygBR6TcgWnYEHgK4f2fEY2tza0uoLuf/i039hd931Hd/SZP+BvQE/pAd8qasoLfcxRoZUUqmgLDxs9jZiciIhJiaDh4VIWGvJkQ+O/5lEnXvzrDhC4nnfvaZj6Zj8cq5zz7n33wr16jlhuMw8ZTYwngY9IbNM2WuJXhtAYlkKBhBOwsNgAAPmv0B4Ki8vW2L9qqqsvKJMxvSG7d61zwYNHiQD6ratW7fY88+/aNu37bBKpeHLzJIli31mNXNwUGxAh0/W+cQ9jA2lpVxmq7PKnoXJGCZKST34EsNMZhS1vLzCMl1pW7Rwsa14Zbm9vnOHtbR1+LR82NcbE9NS+IWL5gsUltrePXXWUN+q/E5VWVv1tFs9cruUu955E7aBWdeAyPbXtssrGOe9xvoNmy0tnpYmUj5LeM2G1y2eKLN0stlWr1puC+RB7Hhtp5026TSvcz6FdWPB73PPPWe/+MUvXCa33367ywpAAtDZvI3FsqypYzwHkOCaGf8sDQGsGKtiTR2/2XispbXdXpozx6oH9LeG/Qdtz+tv2OIFC22tgCNRXmoDJS8Wvu7etctmvTjLAYXyAFbqytIh73hyCL1YuniJ6lhmY8eN9TWMwERZSbEtnDvXy1+1do3t3nfAzjr3PN9+hukMm8U76kc7kSHyZ+b/3LmzrW5vnesU83p6wFCnELBYj8Y7yJ8tSzZJTwG06moWeQ/wTdlWr2am/5Ve36oqlkbRqbb7gl32RNq0aYvP1epXUWlbt7xqM8TrTZs3Wv2hBqseNNAX5KL7GzZs9F0pTp0wTnWMC5yCzuP49NYNtDfK19VeAeAEeNlr+hPSicH3ZPm9rZ4TU/OZVMd6H5SFJSQcLEfJPfvRf4CDEivMMRSUg3VneAAL5i9y4OLzZX39QQHRdp93Urevzp6dMd3dd6bn09ux5xNnDjw1FB/wCb2GXKKHJA3T/lmzx1wb3kNx8L6oC0DK+jl2XJz2myd8LdPcufNlAJuttma4PKC0rVzJeq465RiwASZz0OtT9uJFS317iCE11T7/bvHipba/rlGGK4VtbLJCgR6DqSyOxvNhryM8G7wuQPxZgQKbuK3fsMn2HzoogOrwRcQvzJptJWXlDqBrV68MdoHYu8eefeZZB5R8Cj/LAnwsqfnMZz7joMuyIOTDdiwA5KRJE23f/r0287kXxPdDzh8MG89k8MDqYL2XDBNwwLNkU7LGxsO2UUbJIPCaVa/Y1EcfUVvkOXR12MpXVvuUC9YUTn38SZd7uF1KPoW840BmgNdaARDrEt0L17F+7TrVaZueVfqgNGkC7/FoAnCQAW2ig2QPIfRo+jPTfcIhz8MDovOBP/Duxz/5sd/roe6ob/jGZmqrV622f/qn/2133/1/fRnGvrp9vkyLtYTksV5AyPq79ZLv3NnzbOgw9rIqtbkLF6gudSpDHmGs0OYLYNesWas6SabqwP6zKZcfIU9C7+iP8ZD6Sr2V/3ZQr+CE18KBMmIEKBdA8p73vMd7L7YzYa0ORsV4DhXiGWvwWKgIYdz0fCghi0pRNqbO437Pnzffzj//fLvpppt8c64hQwa50bDlCtuCnHPOOf4bQyAcyCfKQxnZM4ZZ3GzMxVosFuSySPWOO+7wPZXOPfdc+9wXPm83fvSj1k9tWbRwie8ZdOll5/n6PsK7yqr+2bGFI4SSAwiMWU0+40y7/JIL7QwZfjKj9EMG2sGmYNV1ojBmxYm4VQpoMEg8l9NOO815xixpQJo1hOHuDQBokXpawqnWjnZ5NH/w9XjwkR0JWPwKwOYTvKQjYP0ebYJ3l112ma8thK/M8iUPvkqytorOwicOqn1dHW02fuypNlKdwIDBQ620sr9dcfkltmvHNpfxQgHuOeec55/mOxSzXnTphXbjzTfaB6652r2/zs6kbRfIMRZEmaGMXJ7Z8C2fAEH0YPToU3wBMfVnc7R5kjsyYhuaK6640relxQPMpzBMB0ChUaNH+U4ZtCtcyJ1LLMdgMzU6h5EjRroeXnf99XrnXHlUcd8z7HOf+5yddfZZ9uWvfNm++MUv+tdC9kpiix92j+Cgnkl1LDvkhbJKAN287LL3uJdJBID82GXiM5/+tH384x/39IyfvUvvDPUKTggK5WLF//333+/bemBcCMMNLKtUKCFnekuMA0XlPYCBeygZBoC3hPvP3t0I2r2y6sFutBkGSgV+gBB5h+NQgAMGz5mycw+ek57QMqwD5fi4hpQab4I0uOj9+/X352yV29jYbBUy4I7O/VZQ1OafsKWL3rvmEp4PdaI+QwWc5QmFWsovonfb5EEVJGRszU2+XW9GYBICCu/hOeGxsdkdG++Rx8BBA5xnzO3KsMavIKI6JhTWJW2RvEvCkAcffNB5R7n57eUe/CMPjAYApJOgXZSNh4T3Nv2ZP9jM52fofplClrQbHstwpj3xuD32xJP2hxcX2KHmDhs1dJDcsXrb9fpOAUxKncBogWbC2rvarayyzLpSncqjSHXNWESuE3xmNT8yhuAxRHuRMTLL9ZwI62g3n/DZDgcvGiCKSA9qR47yOUx8yWNqB2M+4a4UeFG0kUmGjJXRdry8KY9OtaeffkayrPbxu0BtjxwsSGWJSVq8ZfO9ttZgPh1f1ZIqC2+rsrKfl0Ub8D6pJ3WDGBSvEM861GFQJjOq0SF0tVR16ZCnDkjz1Q5HPpEode+PdqNzeJ1+ZOX1TlM45hYe+fRmn5/8yLbvOEe+PPKfM6b7lg7ldgwhlA984AO+pocem3EgjIBQC6MHCBAuZ9ISZqFcnDEkFIznKCjeDffZvpfZtw31h6y2dqTyXOPvFsvwGWjlffLmN0pPHuSPEeYToEX+ABPKi+FSTxSFsnhG3hy4tQysstn6yOEjBbSvyYNrsd9Mm2oJhVzhXkK5hGJCtGXPrj3WWV9vjzz8a+btW5dkUShwYtJgqfjBuBm9M7zB02Prk29961v27W9/27dOGTx4oJQ4Yps3b7T9+w7KW5rhoR3LI8aOnWCXXnp5XvrBXnbfKWqzXprlHQreAZ4k4zKABiDBNi533XWXez2vbt9p6e6YlQpkr77ivb57Ah4VYyzwjHf44wh4dQ2SQ6PajQGyQdryZcsdZJApckIGgCNy4r1cQpZ0VBwADmfCJrZgCfShzQGcfabC2dfIDh0jb7xx8qZzwUv7xje+4R820MfexiApn3FKymJAnXbTqeHVlJaVylsbJiPp9ufhfB/Ko+5NCu/4oEB9dry2w+dR0QEwlgmYMca3W7/Dfc7JlzE8hhPYr4j0bp/v0ttOvQ6IswXJ1KlTPR7HDf/Yxz7mSoriYLAoNUIDEOiJABF+EwaSDrAIhc/2D88//0Kwv46UtnYEu2iOlQu+0heOznrpRd88DWVEiTk/+uij7rWRJ+Xn90YoH8aEZ4Cr//DDD7tyEU6hWBgO3h7pRggwonLFWUs1bFCN/eB7/2ovL5tnF19yma8JmnDaZIsXMGR3JHyk18YIAZt7f/4TWzx/jp17wSX2Rn2HXfX+C6xSveyPvv8vtmrZErvwoos93DvjzDM97IIvjHEAxp3qsfFKRo6otWni53Tx4twLLrJueRCTJ59pE8aNsRflNd1z73/YgvlzrbMr6WFePtHW3inoW/gQ8Itf/Fx8numDyQWxhEKSyb46/N57f6Fyf2eNza127UduVghaYiXd/MGFAlu0Yo2NHDPOhg8dYhHJq6Gp3orF/2HDa63xcIu8wza7SPUdMKC/y/3737/bt8uh88DLw9gxVmRNHcODDwJ33323rZNslq9YYfvkKV96ycU2uH+1vTDzBfFmgQ0XTzICrPMVhrJ1yL333GubNm7wAXf0Ca8TcMIrxKtEH5BpsE3u0foQEnygw/re977n24U0Nx92mbRKnqWl5T5ONFlyqqxUGK46DxtWY4sWLLDfPTXNv0wWlVTY5Ze930bW1NqCuXPs+ZdmWlmF9LKoxM46c7J7dJU6+DCwZfs2O+2MSfKKBwrw0pIEbT+erN5h9IIducefmt6h8o87CRMmh0qA8oUuPIbP75BQ2pDCd3LTAlDhPYALgKKHRInYpK6hUS6/FIM0jGHwnLSAFO9zP1/goQfHgXcECPEO6SmD9ByeH8BUWeWblEXalV+qxfoPKbBVq9fbjFmr7TN/eYeVFgFOR9pE3eg1qVdn62HrVxyx7Tvr7KHnltgdX/6Cxbs6LNKp58IGdsRsau1UD5p2j4t2Ux8O+EZ7qBPb9DLR0JfUCMyoG7OgfavTiNoczlXSNekh3oXy2x/KJSTKgaf86StmC3dnVJ6AkakQxEHd6S5iUWtKxqwkEbfSZINtWLvGZi1ZaTd+7DYbVjPEt29taz8svgeblQF8bKVC2B2ATyAHeB5SvscU1hPQYgC7oqqfQq56K+9fpfwVMgqUI+IT4zrx0mJrUJ3LJZsOASf1HzKo2sEul3fwCb7yoYMvw2HHkUvoQ+gx8x7jowFoBnroS4x0X/+7zh08dDD7xbfFykriAvNu23+w3n507wP2t1/5OxtUXmXNTYessKJAIN1g9z34iH32039lFQKput17vCMcLED/4A3XKURt79lKN5jz1gu9zZMw/3+hPs0QxxgQLkbDObzXG4VgwhGmCZU2pPzr8B2UErA7Xt657+X+Pl56iNk1LLhFeVgrFjOFDl1NHuLMnL3SJk6abOtXLzsKnFDoK664wkO0ZHuzFUt5N21/w+as2GI3f+LjVhHt8H2e2PMoXAoDhXXKb19I1AUqUFmEHIUFrNJTHqp/b204WX4h9bwbGkEk+KKVO6mUCaHJiAxRSR5/6Je2b+9u++B1H/FP+e1sxyti36sjJEByiwsot354NkycJKTmDIiHITjjYXycoLNwQFAV4I9PXdU1s85pDzPjk5ILzymGua5QWE547gF35QcwAlb33nuvPwuJNGwhgldFXY7wLaxzwBfmJ+W2g/lrLve0wkCF/vdPmWaf/cznrTRaqE4jbZ0RhYbdSbv/gSn2ketvtCFV/e2V5Su8XRMmnWbl1ZViufQ8nToKnPLlFYzLvEtvlvoMTiHlK09fKF9YxwgvL6/j5X28fE5UFwenCJvJZSzOxE9Ww8t4Y+oFt7x+yPoNGGz1B3ZLuY70evTOhIyEle2tzZaRp5SRwu5p5I+L9rdia7W4ik51F7JmVoYVjIGF9QnPlBmSzFJAJC9TChzPCNz0HnkyZ5z6c4Tpj9fOYylI7+1nGY3PXNc9/3PnOvu9YHIqwMUSDe43HKjzOg+rHWkt7fIo3VNj4WawhjAgwAlvLneSZfAMbxgeMc7DGe+V34AIYT7h/dsFTiFxTX54x0wCziXACW8JD4tyQ2/+RODki1dFLLYmrGfKREM7ux6UWUEXHYfqV9Dh4NSm+2XF5T45lT8YyR8l4I9spvVeN21IyUMn23fB6W2lNw1O0Mmu8+lkxtbX/I6Xz4nKPxqcOmSAKR90L+9X7TtGsh91JN3pSgqFoSQK7l6crgGublbDsyma8ilUaOh7IMVKWGkX9JwYc7Y+ufXkPkQ98FzCenBORYt6NqoL0/VG+e0+mkLwkAH6ZmDKpwecdC1QCvmDJxSCBnnyRY65OxnxpCBGWo7AsAFwB6esFxZ4ZUdm4UMhjwAHvBru43XivTgw5YAT5RUqO1+5rt8BOHk2JwSnEJAoIzzyifIICymf+uTzK/c6P3/fJSJe4J5TFX8ZpV3tO9xqRYXyqQrVJvGGjwgVJeUWEWjx14TLykpVaT2PSbekAV4j6YPzvBd6F5zeGh0r6T9D8l4tJClVaXmFtbYEYxJ8NWOWL0bFwXgGB8pLCJHKGhhhS8vhw9auc0g8g/KNIZfCUO5EdCJgOjkdP3/qnWsXAACLn/k40NzKH4IItnrla+Jxx0t6IQca8QoPioPxOUCE34ADv0Pjz6cQrPpK5MNBnpSLdxaOyYXE8xCYjqzL6xtRF764tXa02f76JvGEpVuMAWbbIFDmiyLTTvjjn+Tvfw1ZfFOp2VzepXeC3vSuBKHShee3QicyZuhkeZ/s/aMJ08eACazkDeAFSSMDjyow7HxwCPOnHvzuuc6GRbF0sJ9Sl9x8xUR6gHflt5zy60f+oQcHFXUHYzxce54MWue0+c21D6L+yqdnhwQZDecwrPNeXbeohfImvCMVA/KkI8Shd+cPcfZ4TqSQ1xTkHVLgOeV6L2G9c+sfPueeg6M6hNA78rOuyRVg4Hmu5wTl5gXhOUHk2xtv8u8BZLmU/zw3/2DcSfJRZZBHRGBU4BWThxlL99Sf+hUqZVhPkrDbI7wNWnN8etdzemt0RMv+bAnFCeEJpQrACuU6yqPqhXo1BL0T7DYQGEpocH0h0jo4AkjvBOtzvR8Pw6DsveyzwE7y0vWkhXimIzevN0kYfwgA8OZE/MkHpt4IUMoFvLeXjrQ/AJksWOdUOqwfTx2UdDh3sqD/Lr0TZPb/AM1CWELTR9NjAAAAAElFTkSuQmCC)

异步请求也分成了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机制,实际上这些所谓的&ldquo;异步&rdquo;IO机制,在内核中都是同步实现的(本质上冯诺伊曼计算机没有真正的&ldquo;异步&rdquo;机制)。

我们在上面已经说明过,由于进程正常情况下都是将数据先写入buffer/cache,所以这种异步IO都是统一由cfq_group中的async请求队列处理的。

那么为什么在上面的service_tree中还要实现和一个ASYNC的类型呢?

这当然是为了支持区分进程的异步IO并使之可以&ldquo;完全公平&rdquo;做准备喽。

实际上在最新的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进行服务,以保证&ldquo;完全公平&rdquo;。

选择好了cfq_queue之后,就要开始处理这个队列里的IO请求了。这里的调度方式基本跟deadline类似。

cfq_queue会对进入队列的每一个请求进行两次入队,一个放进fifo中,另一个放进按访问扇区顺序作为key的红黑树中。

默认从红黑树中取请求进行处理,当请求的延时时间达到deadline时,就从红黑树中取等待时间最长的进行处理,以保证请求不被饿死。

这就是整个cfq的调度流程,当然其中还有很多细枝末节没有交代,比如合并处理以及顺序处理等等。

###
1.2 cfq的参数调整

理解整个调度流程有助于我们决策如何调整cfq的相关参数。所有cfq的可调参数都可以在/sys/class/block/sda/queue/iosched/目录下找到,当然,在你的系统上,请将sda替换为相应的磁盘名称。我们来看一下都有什么:

<span style="text-align: left; color: rgb(62, 62, 62); font-family: &quot;Helvetica Neue&quot;, Helvetica, &quot;Hiragino Sans GB&quot;, &quot;Microsoft YaHei&quot;, Arial, sans-serif; font-size: 16px; font-style: normal; font-weight: normal; background-color: rgb(255, 255, 255);">#echo&nbsp;</span><span style="text-align: left; color: rgb(62, 62, 62); font-family: 微软雅黑; font-size: 14px; font-style: normal; font-weight: normal; background-color: rgb(255, 255, 255);">cfq &gt;&nbsp;<span style="text-align: left; color: rgb(62, 62, 62); font-family: &quot;Helvetica Neue&quot;, Helvetica, &quot;Hiragino Sans GB&quot;, &quot;Microsoft YaHei&quot;, Arial, sans-serif; font-size: 16px; font-style: normal; font-weight: normal; background-color: rgb(255, 255, 255);">/sys/block/sda/queue/scheduler</span></span>


#ls /sys/class/block/sda/queue/iosched/
<div style="background-color: inherit;">
    back_seek_max&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fifo_expire_sync&nbsp;&nbsp;quantum&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;slice_idle
</div>

<div style="background-color: inherit;">
    back_seek_penalty&nbsp;&nbsp;group_idle&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;slice_async&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;slice_sync
</div>

<div style="background-color: inherit;">
    fifo_expire_async&nbsp;&nbsp;low_latency&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;slice_async_rq&nbsp;&nbsp;target_latency
</div>

这些参数部分是跟机械硬盘磁头寻道方式有关的,如果其说明你看不懂,请先补充相关知识:

**back_seek_max**:磁头可以向后寻址的最大范围,默认值为16M。

**back_seek_penalty**:向后寻址的惩罚系数。这个值是跟向前寻址进行比较的。

以上两个是为了防止磁头寻道发生抖动而导致寻址过慢而设置的。基本思路是这样,一个io请求到来的时候,cfq会根据其寻址位置预估一下其磁头寻道成本。
  1. 设置一个最大值back_seek_max,对于请求所访问的扇区号在磁头后方的请求,只要寻址范围没有超过这个值,cfq会像向前寻址的请求一样处理它。

  2. 再设置一个评估成本的系数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最大吞吐量的情况下,尽量使远端请求在一个期限内被调度而不被饿死的调度器。

###
2.1 deadline设计原理

为了实现上述目标,deadline调度器实现了两类队列,一类负责对请求按照访问扇区进行排序。这个队列使用红黑树组织,叫做sort_list。另一类对请求的访问时间进行排序。使用链表组织,叫做fifo_list。

由于读写请求的明显处理差异,在每一类队列中,又按请求的读写类型分别分了两个队列,就是说deadline调度器实际上有4个队列:
  1. 按照扇区访问顺序排序的读队列;

  2. 按照扇区访问顺序排序的写队列;

  3. 按照请求时间排序的读队列;

  4. 按照请求时间排序的写队列。

    deadline之所以要对读写队列进行分离,是因为要实现读操作比写操作更高的优先级。

    从应用的角度来看,读操作一般都是同步行为,就是说,读的时候程序一般都要等到数据返回后才能做下一步的处理。

    而写操作的同步需求并不明显,一般程序都可以将数据写到缓存,之后由内核负责同步到存储上即可。

    所以,对读操作进行优化可以明显的得到收益。当然,deadline在这样的情况下必然要对写操作会饿死的情况进行考虑,保证其不会被饿死。

    deadline的入队很简单:当一个新的IO请求产生并进行了必要的合并操作之后,它在deadline调度器中会分别按照扇区顺序和请求产生时间分别入队sort_list和fifo_list。并再进一步根据请求的读写类型入队到相应的读或者写队列。

    deadline的出队处理相对麻烦一点:

  5. 首先判断读队列是否为空,如果读队列不为空并且写队列没发生饥饿(starved < writes_starved)则处理读队列,否则处理写队列(第4部)。

  6. 进入读队列处理后,首先检查fifo_list中是否有超过最终期限(read_expire)的读请求,如果有则处理该请求以防止被饿死。

  7. 如果上一步为假,则处理顺序的读请求以增大吞吐。

  8. 如果第1部检查读队列为空或者写队列处于饥饿状态,那么应该处理写队列。其过程和读队列处理类似。

  9. 进入写队列处理后,首先检查fifo_list中是否有超过最终期限(write_expire)的写请求,如果有则处理该请求以防止被饿死。

  10. 如果上一步为假,则处理顺序的写请求以增大吞吐。

    整个处理逻辑就是这样,简单总结其原则就是,读的优先级高于写,达到deadline时间的请求处理高于顺序处理。正常情况下保证顺序读写,保证吞吐量,有饥饿的情况下处理饥饿。

###
2.2 deadline的参数调整

deadline的可调参数相对较少,包括:

<span style="text-align: left; color: rgb(62, 62, 62); font-family: &quot;Helvetica Neue&quot;, Helvetica, &quot;Hiragino Sans GB&quot;, &quot;Microsoft YaHei&quot;, Arial, sans-serif; font-size: 16px; font-style: normal; font-weight: normal; background-color: rgb(255, 255, 255);">#echo&nbsp;</span><span style="text-align: left; color: rgb(62, 62, 62); font-family: 微软雅黑; font-size: 14px; font-style: normal; font-weight: normal; background-color: rgb(255, 255, 255);">deadline &gt;&nbsp;<span style="text-align: left; color: rgb(62, 62, 62); font-family: &quot;Helvetica Neue&quot;, Helvetica, &quot;Hiragino Sans GB&quot;, &quot;Microsoft YaHei&quot;, Arial, sans-serif; font-size: 16px; font-style: normal; font-weight: normal; background-color: rgb(255, 255, 255);">/sys/block/sda/queue/scheduler</span></span>


#ls /sys/class/block/sda/queue/iosched/


fifo_batch  front_merges  read_expire  write_expire  writes_starved
#####

**read_expire**:读请求的超时时间设置,单位为ms。当一个读请求入队deadline的时候,其过期时间将被设置为当前时间+read_expire,并放倒fifo_list中进行排序。

**write_expire**:写请求的超时时间设置,单位为ms。功能根读请求类似。

**fifo_batch**:在顺序(sort_list)请求进行处理的时候,deadline将以batch为单位进行处理。

每一个batch处理的请求个数为这个参数所限制的个数。在一个batch处理的过程中,不会产生是否超时的检查,也就不会产生额外的磁盘寻道时间。

这个参数可以用来平衡顺序处理和饥饿时间的矛盾,当饥饿时间需要尽可能的符合预期的时候,我们可以调小这个值,以便尽可能多的检查是否有饥饿产生并及时处理。

增大这个值当然也会增大吞吐量,但是会导致处理饥饿请求的延时变长。

**writes_starved**:这个值是在上述deadline出队处理第一步时做检查用的。用来判断当读队列不为空时,写队列的饥饿程度是否足够高,以时deadline放弃读请求的处理而处理写请求。

当检查存在有写请求的时候,deadline并不会立即对写请求进行处理,而是给相关数据结构中的starved进行累计。

如果这是第一次检查到有写请求进行处理,那么这个计数就为1。如果此时writes_starved值为2,则我们认为此时饥饿程度还不足够高,所以继续处理读请求。

只有当starved &gt;= writes_starved的时候,deadline才回去处理写请求。可以认为这个值是用来平衡deadline对读写请求处理优先级状态的,这个值越大,则写请求越被滞后处理,越小,写请求就越可以获得趋近于读请求的优先级。

**front_merges**:当一个新请求进入队列的时候,如果其请求的扇区距离当前扇区很近,那么它就是可以被合并处理的。

而这个合并可能有两种情况:
  1. 是向当前位置后合并

  2. 是向前合并。

    在某些场景下,向前合并是不必要的,那么我们就可以通过这个参数关闭向前合并。默认deadline支持向前合并,设置为0关闭。

##
3、noop调度器

noop调度器是最简单的调度器。它本质上就是一个链表实现的fifo队列,并对请求进行简单的合并处理。调度器本身并没有提供任何可疑配置的参数。

##
4、各种调度器的应用场景选择

<span style="margin: 0px; padding: 0px; line-height: 1.6; font-weight: bold; -ms-word-wrap: break-word !important; max-width: 100%; box-sizing: border-box !important;">根据以上几种io调度算法的分析,我们应该能对各种调度算法的使用场景有一些大致的思路了。</span>

&nbsp;

<span style="margin: 0px; padding: 0px; line-height: 1.6; -ms-word-wrap: break-word !important; max-width: 100%; box-sizing: border-box !important;">从原理上看,cfq是一种比较通用的调度算法,它是一种以进程为出发点考虑的调度算法,保证大家尽量公平。</span>

<span style="margin: 0px; padding: 0px; line-height: 1.6; -ms-word-wrap: break-word !important; max-width: 100%; box-sizing: border-box !important;">deadline是一种以提高机械硬盘吞吐量为思考出发点的调度算法,尽量保证在有io请求达到最终期限的时候进行调度。**非常适合业务比较单一并且IO压力比较重的业务,比如数据库。**</span><span style="color: rgb(62, 62, 62); font-family: &quot;Hiragino Sans GB&quot;, &quot;Microsoft YaHei&quot;, Arial, sans-serif; font-size: 16px; font-style: normal; font-weight: normal; background-color: rgb(255, 255, 255);">Deadline对数据库环境(ORACLE RAC,MYSQL等)是最好的选择.</span>

而noop呢?其实如果我们把我们的思考对象拓展到固态硬盘,那么你就会发现,无论cfq还是deadline,都是针对机械硬盘的结构进行的队列算法调整,而这种调整对于固态硬盘来说,完全没有意义。

<span style="font: 16px/24px &quot;Hiragino Sans GB&quot;, &quot;Microsoft YaHei&quot;, Arial, sans-serif; color: rgb(62, 62, 62); text-transform: none; text-indent: 0px; letter-spacing: normal; word-spacing: 0px; float: none; display: inline !important; white-space: normal; font-size-adjust: none; font-stretch: normal; background-color: rgb(255, 255, 255); -webkit-text-stroke-width: 0px;">NOOP对于闪存设备,RAM,嵌入式系统是最好的选择.(推荐虚拟化环境中使用noop)</span>

对于固态硬盘来说,IO调度算法越复杂,额外要处理的逻辑就越多,效率就越低。

**<font color="#3e3e3e" face="Helvetica">所以,固态硬盘这种场景下使用noop是最好的,deadline次之,而cfq由于复杂度的原因,无疑效率最低。</font>**

###
 I/O调度方法的查看与设置

&nbsp;
  • 1) 查看当前系统的I/O调度
`[root@localhost ~]# cat /sys/block/sda/queue/scheduler
noop anticipatory deadline [cfq] 
`
  • 2) 临时更改I/O调度 例如:想更改到noop电梯调度算法:
`[root@localhost ~]# echo noop > /sys/block/sda/queue/scheduler
`
  • 3) 永久更改I/O调度 修改内核引导参数,加入elevator=调度程序名
`[root@localhost ~]# vim /boot/grub/menu.lst`
<font size="3" style="background-color: inherit;">更改到如下内容:</font>
`kernel /boot/vmlinuz-2.6.18-8.el5 ro root=LABEL=/ elevator=deadline rhgb quiet`
<font size="3" style="background-color: inherit;">重启服务器后,查看调度方法:</font>
`[root@localhost ~]# cat /sys/block/sda/queue/scheduler
noop anticipatory [deadline] cfq 
[root@localhost ~]#`
<font size="3" style="background-color: inherit;">可以看见已经是deadline了</font>

###
四、 ionice

<font size="3" style="background-color: inherit;">ionice可以更改任务的类型和优先级,不过只有cfq调度程序可以用ionice.</font>

<font size="3" style="background-color: inherit;">有三个例子说明ionice的功能:</font>

<font size="3" style="background-color: inherit;">采用cfq的实时调度,优先级为7</font>
`[root@localhost ~]# ionice -c1 -n7  -ptime dd if=/dev/sda1 f=/tmp/test bs=2M count=300&`
<font size="3" style="background-color: inherit;">采用缺省的磁盘I/O调度,优先级为3</font>
`[root@localhost ~]# ionice -c2 -n3  -ptime dd if=/dev/sda1 f=/tmp/test bs=2M count=300&`
<font size="3" style="background-color: inherit;">采用空闲的磁盘调度,优先级为0</font>
`[root@localhost ~]# ionice -c3 -n0  -ptime dd if=/dev/sda1 f=/tmp/test bs=2M count=300&`
ionice的三种调度方法,实时调度最高,其次是缺省的I/O调度,最后是空闲的磁盘调度.

ionice的磁盘调度优先级有8种,最高是0,最低是7.

**注意:磁盘调度的优先级与进程nice的优先级没有关系.

一个是针对进程I/O的优先级,一个是针对进程CPU的优先级.**

&nbsp;

http://mp.weixin.qq.com/s?__biz=MzA4Nzg5Nzc5OA==&mid=2651659684&idx=1&sn=0768ce70e51ddb2e1314ca3c2b02dd8d&scene=0#rd
&nbsp;