磁盘算法

noopnoop只会对请求做一些简单的排序，其本质就是一个FIFO的队列，只会简单地合并临近的IO请求后，本质还是按先来先处理的原则提交给磁盘。根据它的原理，我们可以发现它倾向于饿死读利于写，为什么呢？异步写是把数据直接放到page cache的，也就意味着可以通过page cache缓存大量的写数据，再一次性往下提交IO请求。而读呢？读一般是同步的，也就意味着必须在读完一笔后再读下一笔，两次读之间是可能被写请求插足的。cfqCFQ算法会为每个进程单独创建一个队列，保存该进程产生的所有IO请求。不同队列之间按时间片来调度，以此保证每个进程都能很好的分到I/O带宽。这IO的时间片调度跟进程调度是非常相似的，进程调度有进程优先级，而IO调度也有IO优先级。CFQ的出发点是对IO地址进行排序，以尽量少的磁盘旋转次数来满足尽可能多的IO请求。在CFQ算法下，SAS盘的吞吐量大大提高了。但是相比于NOOP的缺点是，先来的IO请求并不一定能被满足，可能会出现饿死的情况。当一个同步队列中的请求不足一定数量时，这个设备可以空闲一会，即使其它队列里可能有请求等待处理。通常，同步请求之间在磁盘上的物理位置是连续的，所以让磁盘稍等一会来接收更多连续的请求，这样做可以提高吞吐量。deadlinedeadline确保请求在一个用户可配置的时间内得到响应，避免请求饿死。其分别为读IO和写IO提供不同的FIFO队列，读FIFO队列的最大等待时间是500ms，写FIFO队列的最大等待时间是5s。deadline会把提交时间相近的请求放在一批。在同一批中，请求会被排序。当一批请求达到了大小上限或着定时器超时，这批请求就会提交到设备队列上去。对闪存等存储介质，优先使用noop调度算法个人PC使用cfq调度算法对IO压力比较重，且功能比较单一的场景，例如数据库服务器，使用deadline调度算法
为什么闪存等介质，例如固态硬盘SSD，要选择noop调度算法？noop先来先处理的做法对磁盘来说时间损耗非常大，大量浪费了磁盘磁臂移动的时间。但是对闪存设备，例如mmc、nand等，却是最好的选择，因为闪存设备的物理结构跟磁盘完全不同，其通过一些规范的命令即可读取数据，没有磁臂这东西。此时IO调度算法里的排序、合并其实没太大意义，反而浪费了CPU和内存。
为什么个人PC要用cfq调度算法？在个人PC的场景上，往往需要打开大量的程序，创建大量的进程。每个进程都可能有IO的请求。在这场景下，我们需要的是如何确保不同进程或进程组间IO资源使用的公平性。总不能因为A进程要拷贝电影，独占了IO资源，导致B进程无法打开文档不是？cfq调度算法是以进程之间公平享用IO资源为出发点设计的，所以，个人PC建议使用cfq调度算法，但cfq调度算法不仅仅用于个人PC，准确来说，cfq调度算法适用于有大量进程的多用户系统。
为什么deadline调度算法适用于数据库？deadline是一种以提高机械硬盘吞吐量为思考出发点的调度算法，所以准确来说，deadline调度算法适用于IO压力比较重，且业务功能单一的场景，而数据库毫无疑问是最为匹配的场景了。磁盘调度算法SCAN就是俗称的电梯算法，为了避免SSTF算法（最短寻道时间算法）的“饥饿”现象，SCAN要求磁头每轮朝一个固定方向移动来服务访问请求（如果该方向有请求），当磁头走到尽头后这个时候寻道方向会发生调转。所以SCAN可以看作规定了磁头移动方向的SSTF算法。//访问磁道与当前磁道的距离，更优先考虑的是磁头的当前此洞方向，颇似电梯运行，又称为电梯算法。// SCAN算法对最近扫描过的区域不公平。C-SCAN算法就是加了一个Circle规定的SCAN算法，也就是磁头移动方向始终固定，到尽头后直接返回到另一端的开始位置，继续沿着这个方向扫描。//（循环扫描）规定了磁头单向移动。LOOK和C-LOOK就是对应SCAN和C-SCAN的改进算法。因为SCAN和C-SCAN中每次磁头都要走到磁道尽头，而实际过程中并不需要要求磁头走到尽头，而是到达该方向的最后一个请求后即可返回，这样可以避免一些不必要的磁头移动。（ elevator=操作系统调度程序名）IO调度器的总体目标是希望让磁头能够总是往一个方向移动，移动到底了再往反方向走，这恰恰就是现实生活中的电梯模型，所以IO调度器也被叫做电梯。 (elevator)而相应的算法也就被叫做电梯算法。as(Anticipatory)、cfq(Complete Fairness Queueing)、deadline、noop(No Operation)。具体使用哪种算法我们可以在启动的时候通过内核参数elevator来指定，默认使用的算法是cfq一、NOOP算法NOOP算法的全写为No Operation。该算法实现了最最简单的FIFO队列，所有IO请求大致按照先来后到的顺序进行操作。之所以说“大致”，原因是NOOP在FIFO的基础上还做了相邻IO请求的合并，并不是完完全全按照先进先出的规则满足IO请求。假设有如下的io请求序列：100，500，101，10，56，1000NOOP将会按照如下顺序满足：100(101)，500，10，56，1000NOOP是在Linux2。4或更早的版本的使用的唯一调度算法。由于该算法比较简单，减了IO占用CPU中的计算时间最少。不过容易造成IO请求饿死。关于IO饿死的描述如下：因为写请求比读请求更容易。写请求通过文件系统cache，不需要等一次写完成，就可以开始下一次写操作，写请求通过合并，堆积到I/O队列中。读请求需要等到它前面所有的读操作完成，才能进行下一次读操作。在读操作之间有几毫秒时间，而写请求在这之间就到来 ，饿死了后面的读请求 。其适用于SSD， 以nvme的盘，Fusion IO环境下。二、CFQ算法// 算法的主要目标是在触发I/O请求的所有进程中确保“磁盘I/O带宽的公平分配”。// 让进程可以公平的占用IO资源， 所以对进程占用IO的时间进行调度才是相对最公平的， cfq就是试图给所有进程分配等同的块设备使用的时间片，进程在时间片内，可以将产生的IO请求提交给块设备进行处理，时间片结束，进程的请求将排进它自己的队列，等待下次调度的时候进行处理。这就是cfq的基本原理。// 原理是基于时间片的角度去保证公平。// CFQ试图为竞争块设备使用权的所有进程分配一个请求队列和一个时间片。// CFQ是默认的磁盘调度算法，对于通用服务器来说是最好的选择。它试图均匀地分布对/IO带宽的访问。CFQ为每个进程单独创建一个队列来管理该进程所产生的请求，也就是说，每个进程一个队列，各队列之间的调度使用时间片进行调度，以此来保证每个进程都能被很好地分配到I/O带宽。I/O调度器每次执行一个进程的4次请求。在传统的SAS盘上，磁盘寻道花去了绝大多数的I/O响应时间。CFQ的出发点是对I/O地址进行排序，以尽量少的磁盘旋转次数来满足尽可能多的I/O请求。在CFQ算法下，SAS盘的吞吐量大大提高了。相比于NOOP的缺点是，先来的I/O请求并不一定能被满足，可能会出现“饿死”的情况。CFQ算法的全写为Completely Fair Queuing。 绝对公平调度器
该算法的特点是按照IO请求的地址进行排序，而不是按照先来后到的顺序来进行响应。CFQ为每个进程/线程，单独创建一个队列来管理该进程所产生的请求，也就是说每个进程一个IO队列，各队列之间的调度使用时间片来调度，以此来保证每个进程都能被很好的分配到I/O带宽。假设有如下的io请求序列：
100，500，101，10，56，1000CFQ将会按照如下顺序满足：100，101，500，1000，10，56在传统的SAS盘上，磁盘寻道花去了绝大多数的IO响应时间。CFQ的出发点是对IO地址进行排序，以尽量少的磁盘旋转次数来满足尽可能多的IO请求。在CFQ算法下，SAS盘的吞吐量大大提高了。但是相比于NOOP的缺点是，先来的IO请求并不一定能被满足，也可能会出现饿死的情况，不过其作为最新的内核版本和发行版中默认的I/O调度器，对于通用的服务器也是最好的选择。CFQ是deadline和as调度器的折中，CFQ对于多媒体应用(video，audio)和桌面系统是最好的选择。三、DEADLINE算法 （4个队列，2个读写队列，2个最后期限队列）DEADLINE在CFQ的基础上，解决了IO请求饿死的极端情况。除了CFQ本身具有的IO排序队列之外，DEADLINE额外分别为读IO和写IO提供了FIFO队列。读FIFO队列的最大等待时间为500ms，写FIFO队列的最大等待时间为5s。FIFO队列内的IO请求优先级要比CFQ队列中的高，，而读FIFO队列的优先级又比写FIFO队列的优先级高。优先级可以表示如下：FIFO(Read) > FIFO(Write) > CFQDeadline确保了在一个截止时间内服务请求，这个截止时间是可调整的，而默认读期限短于写期限。这样就防止了写操作因为不能被读取而饿死的现象。Deadline对数据库环境(ORACLE RAC，MYSQL等)是最好的选择。四、ANTICIPATORY算法------适合顺序读写。（等待窗口，适应连续空间续写）CFQ和DEADLINE考虑的焦点在于满足零散IO请求上。对于连续的IO请求，比如顺序读，并没有做优化。为了满足随机IO和顺序IO混合的场景，Linux还支持ANTICIPATORY调度算法。ANTICIPATORY的在DEADLINE的基础上，为每个读IO都设置了6ms的等待时间窗口。如果在这6ms内OS收到了相邻位置的读IO请求，就可以立即满足。本质上与Deadline一样，但在最后一次读操作后，要等待6ms，才能继续进行对其它I/O请求进行调度。可以从应用程序中预订一个新的读请求，改进读操作的执行，但以一些写操作为代价。它会在每个6ms中插入新的I/O操作，而会将一些小写入流合并成一个大写入流，用写入延时换取最大的写入吞吐量。AS适合于写入较多的环境，比如文件服务器，但对对数据库环境表现很差。一.先来先服务（FCFS）1.方法　　根据进程请求访问磁盘的先后顺序进行调度。2.优点　　公平、简单、每个进程请求都能依次得到处理，不会出现某一进程的请求长期得不到满足。3.缺点　　　　平均寻道时间有点长，适用于磁盘I/O进程数目较少的场合。4.举例　　如磁道请求队列为55、58、39、18、90、160、150、38、184.二.最短寻道时间优先（SSTF）1.方法　　其要求访问的磁道与当前磁头所在的磁道距离最近。2.缺点　　优先级低的进程会发生“饥饿”现象。因为新进程请求到达，且其所要访问的磁道与磁头当前所在的磁道距离较近，必先优先满足。3.举例　　如磁道请求队列为55、58、39、18、90、160、150、38、184.三.扫描算法（电梯调度算法）（SCAN）1.方法　　1.首先自里向外访问，下一个对象是其欲访问的磁道既在当前磁道之外，又是距离最近的；　　2.直至无更外的磁道需要访问时，才将磁臂换向为自外向里移动；　　3.下一个访问的磁道在当前位置内为距离最近者；直至再无更里面的磁道要访问。2.优点　　不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑了磁头当前的移动方向；避免了出现“饥饿”现象。被广泛用于大、中、小型机器和网络中的磁盘调度。3.缺点　　当磁道刚从里向外移动而越过了某一磁道时，刚好一进程请求访问此磁道，这时此进程会等待，待磁头继续从里向外，然后从外向里扫描完处于外面的所有要访问的磁道后，才处理此进程，致使该进程的请求被大大推迟。4.举例　　如磁道请求队列为55、58、39、18、90、160、150、38、184.//=============================磁盘调度算法1.传统电梯调度算法1.1先来先服务算法(FCFS)先来先服务(FCFS-First Come First Serve)算法，是一种随即服务算法，它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，它是一种最简单的电梯调度算法。它根据乘客请求乘坐电梯的先后次序进行调度。此算法的优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求长期得不到满足的情况[12]。这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，这种算法的性能就会严重下降，甚至恶化。人们之所以研究这种在载荷较大的情况下几乎不可用的算法，有两个原因：(1)任何调度算法在请求队列长度为1时，请求速率极低或相邻请求的间隔为无穷大时使用先来先服务算法既对调度效率不会产生影响，而且实现这种算法极其简单。(2)先来先服务算法可以作为衡量其他算法的标准。1.2最短寻找楼层时间优先算法(SSTF) 最短寻找楼层时间优先(SSTF-Shortest Seek Time First) [14]算法，它注重电梯寻找楼层的优化。最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“饿死”现象。1.3扫描算法(SCAN)扫描算法(SCAN)是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。它进行寻找楼层的优化，效率比较高，但它是一个非实时算法。扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的，所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成，免去了电梯频繁的来回移动[2]。扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻找楼层时间优先算法小，从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法稳定。1.4 LOOK 算法LOOK算法[18]是扫描算法的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。但当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。1.5 SAFT 算法SATF(Shortest Access Time First)[15,19]算法与SSTF算法的思想类似，唯一的区别就是SATF算法将SSTF算法中的寻找楼层时间改成了访问时间。这是因为电梯技术发展到今天，寻找楼层的时间已经有了很大地改进，但是电梯的运行当中等待乘客上梯时间却不是人为可以控制。SATF算法考虑到了电梯运行过程中乘客上梯时间的影响。2 实时电梯调度算法2.1最早截止期优先调度算法最早截止期优先(EDF-Earliest Deadline First)[16]调度算法是最简单的实时电梯调度算法，它的缺点就是造成电梯任意地寻找楼层，导致极低的电梯吞吐率。它与FCFS调度算法类似，EDF算法是电梯实时调度算法中最简单的调度算法。它响应请求队列中时限最早的请求，是其它实时电梯调度算法性能衡量的基准和特例。2.2 SCAN-EDF 算法SCAN-EDF[16]算法是SCAN算法和EDF算法相结合的产物。SCAN-EDF算法先按照EDF算法选择请求列队中哪一个是下一个服务对象，而对于具有相同时限的请求，则按照SCAN算法服务每一个请求。它的效率取决于有相同deadline 的数目，因而效率是有限的。2.3 PI 算法PI(Priority Inversion)[16]算法将请求队列中的请求分成两个优先级，它首先保证高优先级队列中的请求得到及时响应，再搞优先级队列为空的情况下在相应地优先级队列中的请求。2.4 FD-SCAN 算法FD-SCAN(Feasible Deadline SCAN)[17]算法首先从请求队列中找出时限最早、从当前位置开始移动又可以买足其时限要求的请求，作为下一次SCAN的方向。并在电梯所在楼层向该请求信号运行的过程中响应处在与电梯运行方向相同且电梯可以经过的请求信号。这种算法忽略了用SCAN算法相应其它请求的开销，因此并不能确保服务对象时限最终得到满足。3 电梯调度的高水平研究以上两个小结介绍了几种在目前本人的能力上能进行研究的、简单的电梯调度算法。但是并不是说目前电梯调度只发展到这个层次。目前电梯的控制技术已经进入了电梯群控的时代。随着微机在电梯系统中的应用和人工智能技术的发展，智能群控技术得以迅速发展起来。由此，电梯的群控方面陆续发展出了一批新方法，包括：基于专家系统的电梯群控方法、基于模糊逻辑的电梯群控方法、基于遗产算法的电梯群控方法、基于胜景网络的电梯群控方法和基于模糊神经网络的电梯群控方法。4 电梯问题的需求分析4.1 电梯的初始状态本人设置的电梯的初始状态，是对住宅楼的电梯的设置。(1)建筑共有21层，其中含有地下一层（地下一层为停车场及货物运送场所）。(2)建筑内部设有两部电梯，编号分别为A梯、B梯。(3)电梯内部有23个按钮，其中包括开门按钮、关门按钮和楼层按钮，编号为-1，1，2，3，4……20。(4)电梯外部含有两个按钮，即向上运行按钮和向下运行按钮。建筑顶层与地下一层例外，建筑顶层只设置有向下运行按钮，地下一层只设置有向上运行按钮。(5)电梯开关门完成时间设定为1秒。电梯到达每层后上下人的时间设定为8秒。电梯从静止开始运行到下一层的时间设置为2秒，而运行中通过一层的时间为1秒。(6)在凌晨2：00——4：30之间，如若没有请求信号，A梯自动停在14层，B梯自动停在6层。(7)当电梯下到-1层后，如果没有请求信号，电梯自动回到1层4.2 电梯按钮功能电梯内部的楼层按钮：电梯内部对应每一个楼层的按钮成为楼层按钮，即本章第一结提到的编号为-1，1，2，3，4……20的按钮。当乘客进入电梯后按下楼层按钮，此按钮显示灰色，代表不可以用。这样就表示乘客将要去往此层，电梯将开往相应层。当电梯到达该层后，按钮恢复可以使用状态。电梯内部开门按钮：当电梯达到乘客想要去往的某楼层后，乘客需要准备离开电梯，当电梯停稳后，乘客可以按下开门按钮，电梯门将打开，让用户离开。如若电梯到了乘客曾经按下的楼层，但是无乘客按开门按钮，电梯将自动在停稳后1秒后自动开门。电梯内部关门按钮：当所有想要乘坐电梯的乘客都进入电梯以后，准备让电梯开始运行的时候，乘客需要按下关门按钮，让电梯门关闭，使电梯进入运行状态。设置电梯的自动关门时间为8秒。电梯外部向上按钮：此按钮表示上楼请求，当按下此按钮时，如果电梯到达按下此按钮的楼层，且电梯运行方向是向上的，那么电梯响将停下，并在电梯停稳之后自动开门，此请求被响应后，取消此请求信号。电梯外部向下按钮：此按钮表示下楼请求，当按下此按钮时，如果电梯到达按下此按钮的楼层，且电梯运行方向是向下的，那么电梯响将停下，并在电梯停稳之后自动开门，此请求被响应后，取消此请求信号转自：http://www.cnblogs.com/jianyungsun/archive/2011/03/16/1986439.html