一 丶意义: 良好的调度算法, 能减少 IO 读取时间(磁盘读取(最慢)+ 读取 + 传输) 磁盘访问时间 = 寻道时间 + 旋转延迟时间 + 数据传输时间,
磁盘读写顺序: 由上直下(柱面磁道), 由外到里(柱面排序, 外磁道速度最快), 依次访问对应扇区(512bytes)
计算机中, 各存储区域访问速度为 寄存器约等号≈cache > 内存>>磁盘>其他外接物理设备
系统每进行一次 IO 中断, 进行数据读写, 首先要进行命中测试, 若不在 register,cache,memory 中, 则进行磁盘读取, 先寻址, 再进行 io 读入内存, 读入后才能被 CPU 使用.
由磁盘中读写数据占用时间公式可知, 其最主要的是寻道时间, 旋转延迟时间, 良好的磁盘调度算法, 能减少 IO 读写时间, 从而减少进程等待 io 时间, 增加 CPU 利用率, 防止磁臂黏着现象的发生.
参考资料: https://blog.csdn.net/hguisu/article/details/7408047
二丶名词解释:
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 设备带来的长时间数据等待, 设立多缓冲, 双缓冲等策略进行处理.
https://product.pconline.com.cn/itbk/software/dnyw/1707/9613894.html
算法处理策略: 尽量减少 IO 中断次数, 对可批量请求读写的数据进行批量请求, 而不是一个个数据进行请求读写
(如在大数据排序处理中, 使用分治策略, 分批处理数据, 在内存允许的情况下, 直接读一批数据进行处理(多文件 IO 读入), 处理后在缓冲区保存, 满后才写入, 减少中断次数)
来源: http://www.bubuko.com/infodetail-3027523.html