(第五讲磁盘调度算法)

1、操作系统实验报告课程名称操作系统实验实验项目名称磁盘调度算法学号2010061304班级20100613姓名王鸿运专业计算机学生所在学院计算机科学与技术指导教师王红滨实验室名称地点计算机基础第七实验室哈尔滨工程大学计算机科学与技术学院一、实验概述1. 实验名称 磁盘调度算法2. 实验目的(1) 通过学习 EOS 实现磁盘调度算法的机制， 掌握磁盘调度算法执行的条 件和时机。(2) 观察EOS实现的FCFS、SSTF和SCAN磁盘调度算法，了解常用的 磁盘调度算法。( 3)编写 CSCAN 和 N-Step-SCAN 磁盘调度算法，加深对各种扫描算法 的理解。3. 实验类型 验证，设计4. 实验

2、内容( 1)准备实验(2) 验证先来先服务(FCFS)磁盘调度算法(3) 验证最短寻道时间优先(SSTF)磁盘调度算法(4) 验证 SSTF 算法造成的线程“饥饿”现象(5.1) 验证扫描(SCAN)磁盘调度算法(5.2) 验证 SCAN 算法能够解决“饥饿”现象( 6 ) 改写 SCAN 调度算法二、实验环境EOS 操作系统与 IDE 环境组成的“操作系统集成实验环境 OS Lab ”。三、实验过程（一）实验问题及解答1. 实验指导P176-3.2验证先来先服务（FCFS）磁盘调度算法，要求请给出 在“输出”窗口中的结果。答：输出结果复制如下：制作软盘镜像 .正在启动 Virtual PC.

3、开始调试.* Disk schedule start working *Start Cylinder: 10TID: 31 Cylinder: 8 Offset: 2 -TID: 32 Cylinder: 21 Offset: 13 +TID: 33 Cylinder: 9 Offset: 12 -TID: 34 Cylinder: 78 Offset: 69 +TID: 35 Cylinder: 0 Offset: 78 -TID: 36 Cylinder: 41 Offset: 41 +TID: 37 Cylinder: 10 Offset: 31 -TID: 38 Cylinder: 6

4、7 Offset: 57 +TID: 39 Cylinder: 12 Offset: 55 -Total offset: 360 Transfer times: 10 Average offset: 362. 实验指导P177-3.3验证验证最短寻道时间优先（SSTF）磁盘调度算法, 要求请给出在“输出”窗口中的结果。答：输出结果复制如下：制作软盘镜像 .正在启动 Virtual PC.开始调试.* Disk schedule start working *Start Cylinder: 10TID: 37 Cylinder: 10 Offset: 0 =TID: 40 Cylinder: 1

5、0 Offset: 0 =TID: 33 Cylinder: 9 Offset: 1 -TID: 31 Cylinder: 8 Offset: 1 -TID: 39 Cylinder: 12 Offset: 4 +TID: 32 Cylinder: 21 Offset: 9 +TID: 38 Cylinder: 67 Offset: 26 +TID: 34 Cylinder: 78 Offset: 11 +TID: 35 Cylinder: 0 Offset: 78 -Total offset: 150 Transfer times: 10 Average offset: 153. 实验指导

6、P178-3.4 验证 SSTF 算法造成的线程“饥饿”现象，要求请给 出在“输出”窗口中的结果。答：输出结果复制如下：制作软盘镜像 .正在启动 Virtual PC.开始调试 .* Disk schedule start working *Start Cylinder: 10TID: 37 Cylinder: 10 Offset: 0 =TID: 40 Cylinder: 10 Offset: 0 =TID: 33 Cylinder: 9 Offset: 1 -TID: 34 Cylinder: 8 Offset: 1 -TID: 32 Cylinder: 21 Offset: 9 +TID

7、: 36 Cylinder: 41 Offset: 20 +TID: 38 Cylinder: 67 Offset: 26 +TID: 31 Cylinder: 78 Offset: 11 +Total offset: 72 Transfer times: 10 Average offset: 74. 实验指导 P179-3.5 验证扫描（ SCAN ）磁盘调度算法， 要求在非饥饿 （即 实验指导 P176-3.2 节中的数据）和饥饿（即实验指导 P178-3.4 节中的 数据）请给出在“输出”窗口中的结果，并且要求在每次输入两次“ds”命令（注 意不要连续输入，要等第一次“ ds ”命令执行

8、完，再输入第二次“ ds ”命令）， 分析结果为什么不同。答：输出结果复制如下：（ 1 ）非饥饿状态，两次输入 ds 指令制作软盘镜像 .正在启动 Virtual PC.开始调试 .* Disk schedule start working *Start Cylinder: 10TID: 37 Cylinder: 10 Offset: 0 =TID: 40 Cylinder: 10 Offset: 0 =TID: 39 Cylinder: 12 Offset: 2 +TID: 32 Cylinder: 21 Offset: 9 +TID: 36 Cylinder: 41 Offset: 20

9、+TID: 38 Cylinder: 67 Offset: 26 +TID: 34 Cylinder: 78 Offset: 11 +TID: 33 Cylinder: 9 Offset: 69 -TID: 31 Cylinder: 8 Offset: 1 -TID: 35 Cylinder: 0 Offset: 8 -Total offset: 146 Transfer times: 10 Average offset: 14 * Disk schedule stop working * Disk schedule start working *Start Cylinder: 10TID:

10、47 Cylinder: 10 Offset: 0 =TID: 41 Cylinder: 8 Offset: 1 -TID: 45 Cylinder: 0 Offset: 8 -TID: 49 Cylinder: 12 Offset: 12 +TID: 42 Cylinder: 21 Offset: 9 +TID: 46 Cylinder: 41 Offset: 20 +TID: 48 Cylinder: 67 Offset: 26 +TID: 44 Cylinder: 78 Offset: 11 +Total offset: 88 Transfer times: 10 Average off

11、set: 82）饥饿状态，两次输入 ds 指令制作软盘镜像 .正在启动 Virtual PC.开始调试 .* Disk schedule start working *Start Cylinder: 10TID: 37 Cylinder: 10 Offset: 0 =TID: 40 Cylinder: 10 Offset: 0 =TID: 35 Cylinder: 11 Offset: 1 +TID: 39 Cylinder: 12 Offset: 1 +TID: 32 Cylinder: 21 Offset: 9 +TID: 36 Cylinder: 41 Offset: 20 +TID:

12、38 Cylinder: 67 Offset: 26 +TID: 31 Cylinder: 78 Offset: 11 +TID: 33 Cylinder: 9 Offset: 69 -TID: 34 Cylinder: 8 Offset: 1 -Total offset: 138 Transfer times: 10 Average offset: 13* Disk schedule stop working * Disk schedule start working *Start Cylinder: 10TID: 47 Cylinder: 10 Offset: 0 =TID: 50 Cyl

13、inder: 10 Offset: 0 =TID: 43 Cylinder: 9 Offset: 1 -TID: 44 Cylinder: 8 Offset: 1 -TID: 45 Cylinder: 11 Offset: 3 +TID: 46 Cylinder: 41 Offset: 20 +TID: 48 Cylinder: 67 Offset: 26 +TID: 41 Cylinder: 78 Offset: 11 +Total offset: 72 Transfer times: 10 Average offset: 7分析两次结果为何不同：执行完一次 ds 命令后，该次搜索的指针方向

14、被保 存，但是和初始值相比，搜索的方向发生了变化。根据 SCAN 算法，按一个方 向访问磁盘，一个方向访问到尽头后再换一个方向继续访问。下次访问， 按上次 访问结束时的方向继续访问。 于是第二次访问的方向会与第一次不同， 造成两次 DS 命令输出的结果不同。（二）实验代码及解释实验结果：制作软盘镜像 .正在启动 Virtual PC.开始调试 .* Disk schedule start working *Start Cylinder: 10TID: 37 Cylinder: 10 Offset: 0 =TID: 39 Cylinder: 12 Offset: 2 +TID: 32 Cylin

15、der: 21 Offset: 9 +TID: 36 Cylinder: 41 Offset: 20 +TID: 38 Cylinder: 67 Offset: 26 +TID: 34 Cylinder: 78 Offset: 11 +TID: 33 Cylinder: 9 Offset: 69 -TID: 31 Cylinder: 8 Offset: 1 -TID: 35 Cylinder: 0 Offset: 8 -Total offset: 146 Transfer times: 10 Average offset: 14* Disk schedule stop working * Di

16、sk schedule start working *Start Cylinder: 10TID: 47 Cylinder: 10 Offset: 0 =TID: 50 Cylinder: 10 Offset: 0 =TID: 43 Cylinder: 9 Offset: 1 -TID: 49 Cylinder: 12 Offset: 12 +TID: 42 Cylinder: 21 Offset: 9 +TID: 46 Cylinder: 41 Offset: 20 +TID: 48 Cylinder: 67 Offset: 26 +TID: 44 Cylinder: 78 Offset:

17、11 +Total offset: 88 Transfer times: 10 Average offset: 8 源代码：PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQUEST pRequest;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest0 =NULL,pNextRequest1=NULL,pNextRequest2=NULL;/ 需要

18、遍历请求队列一次或两次/for (pListEntry = RequestListHead.Next;/ 请求队列中的第一个请求是链表头指向的下一个请求。pListEntry != &RequestListHead;/ 遍历到请求队列头时结束循环。pListEntry = pListEntry-Next) / 根据链表项获得请求的指针/pRequest = CONTAINING_RECORD(pListEntry, REQUEST,ListEntry);/ 计算请求对应的线程所访问的磁道与当前磁头所在磁道的偏移 方向由正负表示)/Offset = pRequest-Cylinder - CurrentCylinder;if (0 = Offset) / 如果线程要访问的磁道与当前磁头所在磁道相同，可立即返回/pNextRequest0 = pRequest;return pNextRequest0; if (Offset 0) / 记录向内移动距离最短的线程/if (Offset InsideShortestDistance) InsideShortestDistance = Offset; pNextRequest1 = pRequest; if ( Offset 0) / / 记录向外移动距离最短的线程/if (-Offset OutsideShortestDistance)