(第五讲 磁盘调度算法).doc

操作系统实 验 报 告课程名称操作系统实验实验项目名称磁盘调度算法学号2010061304班级20100613姓名王鸿运专业计算机学生所在学院计算机科学与技术指导教师王红滨实验室名称地点计算机基础第七实验室 哈尔滨工程大学计算机科学与技术学院一、实验概述1. 实验名称 磁盘调度算法2. 实验目的 （1）通过学习EOS实现磁盘调度算法的机制，掌握磁盘调度算法执行的条件和时机。 （2）观察EOS实现的FCFS、SSTF和 SCAN磁盘调度算法，了解常用的磁盘调度算法。 （3）编写CSCAN和N-Step-SCAN磁盘调度算法，加深对各种扫描算法的理解。3. 实验类型 验证，设计4. 实验内容（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.开始调试.* 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: 67 Offset: 57 +TID: 39 Cylinder: 12 Offset: 55 -TID: 40 Cylinder: 10 Offset: 2 -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: 10 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: 36 Cylinder: 41 Offset: 20 +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. 实验指导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: 35 Cylinder: 11 Offset: 3 +TID: 39 Cylinder: 12 Offset: 1 +TID: 32 Cylinder: 21 Offset: 9 +TID: 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”命令执行完，再输入第二次“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 +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: 47 Cylinder: 10 Offset: 0 =TID: 50 Cylinder: 10 Offset: 0 =TID: 43 Cylinder: 9 Offset: 1 -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 offset: 8（2） 饥饿状态，两次输入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: 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 Cylinder: 10 Offset: 0 =TID: 43 Cylinder: 9 Offset: 1 -TID: 44 Cylinder: 8 Offset: 1 -TID: 45 Cylinder: 11 Offset: 3 +TID: 49 Cylinder: 12 Offset: 1 +TID: 42 Cylinder: 21 Offset: 9 +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命令后，该次搜索的指针方向被保存，但是和初始值相比，搜索的方向发生了变化。根据SCAN算法，按一个方向访问磁盘，一个方向访问到尽头后再换一个方向继续访问。下次访问，按上次访问结束时的方向继续访问。于是第二次访问的方向会与第一次不同，造成两次DS命令输出的结果不同。（2） 实验代码及解释实验结果：制作软盘镜像.正在启动 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 +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: 47 Cylinder: 10 Offset: 0 =TID: 50 Cylinder: 10 Offset: 0 =TID: 43 Cylinder: 9 Offset: 1 -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 offset: 8源代码：PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQUEST pRequest;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest0 = NULL,pNextRequest1=NULL,pNextRequest2=NULL;/ 需要遍历请求队列一次或两次/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) / 记录向外移动距离最短的线程/