操作系统课设报告----磁盘调度算法

课 程 设 计 报 告 课程名称 操作系统课程设计 课题名称 磁盘调度算法 学 院 软件学院 班 级 学生姓名 学 号 指导教师 磁盘调度算法磁盘调度算法 一 系统需求分析一 系统需求分析 磁盘存储器不仅容量大 存取速度快 而且可以实现随机存取 是当前存放大量程序 和数据的理想设备 所以在现代计算机中都配备了磁盘存储器 以他为主存放文件 这样对文件的读 写 操作都涉及到了对磁盘存储器的访问 磁盘 I O 速度的高低和磁盘系统的可靠性 都直接 影响到系统的性能 因此改善磁盘系统的性能成为现代操作系统的重要任务之一 磁盘性能有数据的组织 磁盘的类型和访问时间等 可以通过选择好的磁盘调度算法 以减少磁盘的寻道时间 为了减少对文件的访问时间 应采用一种最佳的磁盘调度算法 以使各进程对磁盘的 平均访问时间最少 由于在访问磁盘的时间中主要是寻道时间 因此 磁盘调度的目标是 使磁盘的寻道时间最少 所以本课程设计对各个算法进行模拟 进而比较分析了解 二 实验内容和目的二 实验内容和目的 2 1 实验内容实验内容 模拟电梯调度算法 实现对磁盘的驱动调度 设计要求 编程序实现下述磁盘调度算法 并求出每种算法的平均寻道长度 要求设计 主界面可以灵活选择某算法 且以下算法都要实现 1 先来先服务算法 FCFS 2 最短寻道时间优先算法 SSTF 3 扫描算法 SCAN 4 循环扫描算法 CSCAN 2 2 实验原理实验原理 模拟电梯调度算法 对磁盘调度 磁盘是要供多个进程共享的存储设备 但一个磁盘每个时刻只能为一个进程服务 当有进程在访问某个磁盘时 其他想访问该磁盘的进程必须等待 直到磁盘一次工作结束 当有多个进程提出输入输出请求处于等待状态 可用电梯调度算法从若干个等待访问 者中选择一个进程 让它访问磁盘 当存取臂仅需移到一个方向最远的所请求的柱面后 如 果没有访问请求了 存取臂就改变方向 三 总体设计及分类简介三 总体设计及分类简介 3 1 算法介绍算法介绍 磁盘调度中常用的有四种算法 功能分别如下 1 先来先服务 FCFS 算法 即先来的请求先被响应 FCFS 策略看起来似乎是相当 公平 的 但是当请求的频率过 高的时候 FCFS 策略的响应时间就会大大延长 FCFS 策略为我们建立起一个随机访问机制 的模型 但是假如用这个策略反复响应从里到外的请求 那么将会消耗大量的时间 为了 尽量降低寻道时间 看来我们需要对等待着的请求进行适当的排序 而不是简单的使用 FCFS 策略 这个过程就叫做磁盘调度管理 有时候 FCFS 也被看作是最简单的磁盘调度算 法 2 最短寻道时间优先 SSTF 算法 要求访问的磁道 与当前磁头所在的磁道距离最近 以使每次的寻道时间最短 3 扫描调度 SCAN 算法 该算法不仅考虑到欲访问的磁道与当前磁道间的距离 更优先考虑的是磁头当前的移 动方向 例如 当磁头正在自里向外移动时 SCAN 算法所考虑的下一个访问对象 应是 其欲访问的磁道 既在当前磁道之外 又是距离最近的 这样自里向外的访问 直至再无 更外的磁道需要访问时 才将磁道换向自外向里移动 这时 同样也是每次选择这样的进 程来调度 也就是要访问的当前位置内距离最近者 这样 磁头又逐步地从外向里移动 直至再无更里面的磁道要访问 从而避免了出现 饥饿 现像 4 循环扫描 C SCAN 算法 当磁头刚从里向外移动而越过了某一磁道时 恰好又有一进程请求访问此磁道 这时 该里程就必须等待 为了减少这种延迟 CSCAN 算法规定磁头单向移动 而本实验过程 中我们所设计的是磁头从里向外移动 而从外向里移动时只须改方向而已 本实验未实现 但本实验已完全能演示循环扫描的全过程 磁盘调度模拟系统 先 来 先 服 务 算 法 最 短 寻 道 时 间 优 先 扫 描 算 法 循 环 扫 描 算 法 退 出 3 2 详细设计详细设计 3 2 1 功能模块设计功能模块设计 1 先来先服务算法 先来先服务算法 FCFSFCFS 开始 输入磁道号 按顺序将磁道号输出 输入磁道名称 求每次磁道移动距离和 平均磁道长度 输出磁道移动距离及平均磁道长度 结束 3 3 环境要求环境要求 软件要求 Microsoft Visual Stdio 4 程序运行测试程序运行测试 首先输入九个磁道名称以及要访问的磁道号和当前磁道号首先输入九个磁道名称以及要访问的磁道号和当前磁道号 选择要执行的算法 选择要执行的算法 2 2 先来先服务算法 先来先服务算法 FCFSFCFS 3 3 最短寻道时间优先算法 最短寻道时间优先算法 SSTFSSTF 继续调度其他算法 选择是继续调度其他算法 选择是 1 1 选择扫描算法 选择扫描算法 SCANSCAN 2 2 4 4 扫描算法 扫描算法 SCANSCAN 5 5 循环扫描算法 循环扫描算法 CSCANCSCAN 附 代码附 代码 include stdafx h include include define process Num 9 using namespace std struct Track int current Tracknum 0 当前磁道号 int next Track 0 被访问的下一个磁道号 int move Distance 0 移动距离 char process Name Track track process Num float track aveLength 0 平均寻道长度 int now Tracknum 0 最初开始磁道号 int select num 0 int count Num 0 调度算法次数 void Scanf data printf 请输入要访问磁盘的进程 n for int i 0 i track i process Name printf 请输入当前的磁道号 scanf s d printf 请输入进程要访问的磁道号 n for int i 0 i process Num i scanf s d void Select printf 请选择磁盘调度算法 n printf 1 先来先服务算法 FCFS n printf 2 最短寻道时间优先算法 SSTF n printf 3 扫描算法 SCAN n printf 4 循环算法 CSCAN n scanf s d void Print 打印访问磁盘顺序 printf 进程访问磁盘的先后顺序 for int i 0 i process Num i printf c track i process Name printf n for int i 0 i process Num i printf d track i next Track printf n void Print Data printf 打印表格 n printf t t 从 d 磁道开始 n now Tracknum printf t 磁道名 t 磁道号 t 移动距离 n for int i 0 i process Num i printf t c t d t d n track i process Name track i next Track track i move Distance printf n printf t 平均寻道长度为 2f n track aveLength printf n void Count data int nownum 0 当前计算次数 for int i 0 i process Num i if nownum 0 track i move Distance abs now Tracknum track i next Track track i current Tracknum track i next Track nownum else track i move Distance abs track i next Track track i 1 current Tracknum track i current Tracknum track i next Track int sum 0 计算平均寻道长度时需要的总和 printf 每次磁头移动距离为 for int i 0 i process Num i printf d track i move Distance cout track i move Distance for int i 0 i process Num i sum sum track i move Distance printf n track aveLength float sum process Num printf 平均寻道长度为 2f track aveLength printf n void FCFS count Num printf 按进程提出请求的先后次序进行排队 n Print Count data printf n Print Data void SSTF count Num int nownum 0 当前计算次数 int x 10 int xtemp 0 int tempint 冒泡排序时需要的临时 int 型变量 对进程访问磁道号进行排序 int tempchar 冒泡排序时需要的临时 char 型变量 对进程名进行排序 printf 按进程访问磁道与当前磁头所在的磁道距离进行排队 n for int i 0 i process Num i x i now Tracknum track i next Track for int i 0 i process Num 1 i for int j 0 j 0 x j x j 1 x j 1 xtemp tempint track j next Track track j next Track track j 1 next Track track j 1 next Track tempint tempchar track j process Name track j process Name track j 1 process Name track j 1 process Name tempchar if x j 0 x j x j 1 x j 1 xtemp tempint track j next Track track j next Track track j 1 next Track track j 1 next Track tempint tempchar track j process Name track j process Name track j 1 process Name track j 1 process Name tempchar else continue Print Count data printf n Print Data void SCAN count Num int nownum 0 当前计算次数 int x 10 int xtemp 0 int tempint 冒泡排序时需要的临时 int 型变量 对进程访问磁道号进行排序 int tempchar 冒泡排序时需要的临时 char 型变量 对进程名进行排序 printf SCAN 算法按磁头当前的移动方向和进程访问磁道与当前磁头所在的磁道距离进行排队 n for int i 0 i process Num i x i now Tracknum track i next Track for int i 0 i process Num 1 i for int j 0 j 0 x j x j 1 x j 1 xtemp tempint track j next Track track j next Track track j 1 next Track track j 1 next Track tempint tempchar track j process Name track j process Name track j 1 process Name track j 1 process Name tempchar if x j 0 x j x j 1 x j 1 xtemp tempint track j next Track track j next Track track j 1 next Track track j 1 next Track tempint tempchar track j process Name track j process Name track j 1 process Name track j 1 process Name tempchar else continue Print Count data printf n Print Data void CSCAN count Num int nownum 0 当前计算次数 int x 10 int xtemp 0 int tempint 冒泡排序时需要的临时 int 型变量 对进程访问磁道号进行排序 int tempchar 冒泡排序时需要的临时 char 型变量 对进程名进行排序 printf SCAN 算法按磁头当前的移动方向和进程访问磁道与当前磁头所在的磁道距离进行排队 n for int i 0 i process Num i x i now Tracknum track i next Track for int i 0 i process Num 1 i for int j 0 j 0 x j x j 1 x j 1 xtemp tempint track j next Track track j next Track track j 1 next Track track j 1 next Track tempint tempchar track j process Name track j process Name track j 1 process Name track j 1 proc