磁盘调度算法简述
- 格式：pdf
- 大小：125.77 KB
- 文档页数：2
磁盘调度算法简述
⼀ ⼂意义：良好的调度算法，能减少IO读取时间（磁盘读取（最慢）+读取+传输） 磁盘访问时间=寻道时间+旋转延迟时间+数据传输时间， 磁盘读写顺序：由上直下（柱⾯磁道），由外到⾥（柱⾯排序，外磁道速度最快），依次访问对应扇区（512bytes）
计算机中，各存储区域访问速度为 寄存器约等号≈cache>内存>>磁盘>其他外接物理设备
系统每进⾏⼀次IO中断，进⾏数据读写，⾸先要进⾏命中测试，若不在register，cache，memory中，则进⾏磁盘读取，先寻址，再进⾏io读⼊内存，读⼊后才能被cpu使⽤。 由磁盘中读写数据占⽤时间公式可知，其最主要的是寻道时间，旋转延迟时间，良好的磁盘调度算法，能减少IO读写时间，从⽽减少进程等待io时间，增加cpu利⽤率，防⽌磁臂黏着现象的发⽣。
⼆⼂名词解释： 1）磁臂粘着--------程序对某些磁道频繁访问，如多次访问同⼀磁道，则io队列中，多次对同⼀磁道进⾏频繁的读取，导致其他磁道的请求被搁置，即为磁臂黏着现象（类似于进程饿死）2）寻道时间：移动磁臂到对应磁道（⼀般全部磁臂同时移动，部分可以分别移动），最慢
3）旋转延迟时间：磁盘旋转到对应扇区，对应磁柱进⾏读写
4）数据传输时间：读取数据，使⽤IO总线传⼊内存供cpu使⽤
三⼂算法简述1.先来先服务算法（FCFS）----FirstComeFirstServer
可使⽤链表（若有数量上限则单设头结点记录请求数，超出则拒绝）和数组（数组长度限制为请求数量，防⽌越界），依据请求时间先后，对io请求进⾏队列排列，依次出队 优劣：公平、简单；平均寻道时间可能较长
2.最短寻道算法（SSTF）
其访问规则为距离当前磁头最近的io请求进⾏服务，由“最近”⼀词和磁盘读写顺序可知，其可能会返回对⼀个柱⾯的磁道进⾏多次读写，造成磁盘黏着现象 基本实现：动态处理IO请求，可使⽤链表（双向链表，避免越界和前置判空操作）或者数组（内存允许则最好⽤数组，减少寻址时间）实现，使⽤插⼊排序算法，对IO请求进⾏动态排序， 指针p指向磁头的当前磁道和扇区对应的线形距离数字，对前置后驱元素进⾏判定，以距离较短者作为下次磁盘访问对象。
优劣：平均寻道时间⽐FCFS算法短，但可能会出现“饥饿现象”和“磁臂粘着”现象。
3.扫描算法（电梯算法SCAN）
原理：将各磁道请求映射为线形地址，进⾏单向线形扫描，⼀⽅为空，则反向，直⾄该磁道请求为空，切换下⼀磁道
算法实现：外嵌for对各柱⾯请求进⾏扫描，内嵌while包含俩个for循环，对选择的柱⾯进⾏来回扫描（⼀个增，⼀个减，双向），请求空则break。
优劣：消除了“饥饿”现象，但可能会出现“磁臂粘着”现象
4.循环扫描算法（CSCAN）
原理：改进SCAN，不改变⽅向，单⽅向扫描，若⽆则返回到最外层需要访问的磁道（没就0）
算法实现：参考SCAN，while去除内置为单个for，设为单向
优劣： 改进了对于边缘区磁道访问的不公平，但可能会出现“磁臂粘着”现象。
5.NStepScan
原理：为避免磁臂黏着现象发⽣，算法将磁盘请求队列分成若⼲个长度为N的⼦队列，磁盘调度按FCFS算法依次处理这些⼦队列。⽽每处理⼀个⼦队列时⼜是按照SCAN算法。 当处理某⼦队列时，⼜有新的磁盘I/O请求，便将新请求进程放⼊其他队列中，从⽽避免了粘臂现象。（逻辑上依然为SCAN算法，但是限制了队列数量，强制跳出某⼀柱⾯，减少了频繁访问同⼀磁道带来的黏着现象） 算法实现：依据原理，设置⼤⼩为N的指针数组（取余访问，实现循环），循环访问各个队列
6.FSCAN算法，
算法思想是，在扫描的过程中所有新产⽣的序列放在另外的⼀个队列中，当访问完当前队列之后，再访问新产⽣的⼀个队列。这种算法可以有效防⽌磁壁粘着现象。 实现：略
四⼂其他策略 缓冲区策略：缓解⾼速读写设备与低速io设备带来的长时间数据等待，设⽴多缓冲，双缓冲等策略进⾏处理。
算法处理策略：尽量减少IO中断次数，对可批量请求读写的数据进⾏批量请求，⽽不是⼀个个数据进⾏请求读写
（如在⼤数据排序处理中，使⽤分治策略，分批处理数据，在内存允许的情况下，直接读⼀批数据进⾏处理（多⽂件IO读⼊），处理后在缓冲区保存，满后才写⼊，减少中断次数）
