哈哈 尔尔 滨滨 理理 工工 大大 学学课课 程程 设设 计计（ 操操 作作 系系 统统 ）题 目： N-Step-SCAN 磁盘调度班 级： 计算机科学与技术学院 计算机系 10-8 班姓 名： 唐 楷 航 1004010825指导教师： 高 雪 瑶系主任： 林克正 2013 年 03 月 01 日- II-目目 录录1N-Step-SCAN 磁盘调度课程设计 1.1 题目分析.1 1.2 数据结构.1 1.3 流程图.1 1.4 实现技术.2 1.5 设计结论和心得.2 2 Linux 代码分析.4 2.1 功能说明.18 2.2 接口说明.18 2.3 局部数据结构.20 2.4 流程图.212.5 以实例说明运行过程.22哈尔滨理工大学课程设计报告- 1-1N-Step-SCAN 磁盘调度磁盘调度课程设计1.1 题目分析当有一个或者几个进程对某一磁道有较高的访问频率，即这些进程反复请求对某一 磁道的 I/O 操作，从而垄断整个磁盘设备。在高密度的磁盘上容易出现此情况。N 步 SCAN 算法是将磁道请求队列若干个长度为 N 的子队列。而每处理一个队列时又是按 SCAN 算法，对一个队列处理完后，再处理其他队列。1.2 数据结构N-Step-SCAN 磁盘调度中涉及的数据结构包括 N 个队列、队列缓冲区、表示空缓冲 区的信号量、表示满缓冲区的信号量等。 用伪代码表示如下：#include“stdio.h“#include“stdlib.h“/#include“iostream.h“#define maxsize 100 /定义最大数组域int now,s;void SSTF(int array,int m)int temp;int k=1;int now,l,r; /当前磁道号 now；找出的当前磁道左侧的磁道 l，右侧的磁道 rint i,j,sum=0;int avg;哈尔滨理工大学课程设计报告- 2-for(i=0;iarrayj)/两磁道号之间比较temp=arrayi;arrayi=arrayj;arrayj=temp;for( i=0;i=0;i-)/将数组磁道号从大到小输出哈尔滨理工大学课程设计报告- 3-printf(“%d “,arrayi);sum=now-array0;/计算移动距离else if(array0=now)/判断整个数组里的数是否都大于当前磁道号 for(i=0;i=0)j-) printf(“%d “,arrayj);sum+=arraym-1-array0;/计算移动距离avg=sum/m;printf(“n 移动的总道数： %d n“,sum);printf(“ 平均寻道长度： %d n“,avg);void SCAN(int array,int m,int d)/先要给出当前磁道号和移动臂的移动方向int k=1;int l,r;int i,j,sum=0;int avg;int temp; /用于排序的临时参数int q;for(i=0;iarrayj)/对磁道号进行从小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;if(arraym-1=0;i-)printf(“%d “,arrayi);/将数组磁道号从大到小输出q=arrayi;sum=now-q;/计算移动距离s=s+sum;now=q;哈尔滨理工大学课程设计报告- 7-else if(array0=now)/判断整个数组里的数是否都大于当前磁道号 printf(“n SCAN 调度结果: “);for(i=0;i=0;j-)printf(“%d “,arrayj);q=arrayj;for(j=r;j=0;j-)printf(“%d “,arrayj);q=arrayj;sum=-now-array0+2*arraym-1;/计算移动距离s=s+sum;now=q;/磁道号增加方向avg=sum/m;printf(“n 该子队列移动的总道数： %d n“,sum);printf(“ 该子队列平均寻道长度： %d n“,avg);void NStepSCAN(int array,int m) int sn,N,d; /sn 标记每一子队列的长度，N 记录子队列个数，now 标记当前磁道号int b100,c100; /b100储存前几个子队列，c100储存最后一个子队列哈尔滨理工大学课程设计报告- 10-int i=0,j=0,k=0,n=1;int ave; printf(“请输入当前磁道号：n“);scanf(“%d“,printf(“请输入子队列的个数：n“);scanf(“%d“,while(Nm)printf(“超出范围，文件中的磁道数不够分组，请重新输入：n“);scanf(“%d“,printf(“请输入当前移动臂的移动的方向 (1 磁道号增加方向，0 磁道号减小方向) : “);scanf(“%d“, sn=m/N;while(N!=1) /当不是最后一个子队列时，循环进行 SCAN 调度j=0;for(i=k;i=0(array0=now输出磁盘调度序列 arrayjim磁头移动总距离sum=arrayi-now确定当前磁道在已排的序列中的位置switch(d)case 0:移动臂向磁道号减小方向访问case 1:移动臂向磁道号增加方向访问访问输出磁盘调度序列输出磁盘调度序列输出子队列寻道总道数 sum输出子队列平均寻道长度 avg=sum/(m)流程图哈尔滨理工大学课程设计报告- 17-1.4 实现技术为实现上述设计，采用 C+语言，VS2008 开发环境。运行结果如下：哈尔滨理工大学课程设计报告- 18-1.5 设计结论和心得通过课程设计得到如下结论： 在在 N N 步扫描算法中，还出现了这样一个问题。就是，在对磁道号进行分组时，最后步扫描算法中，还出现了这样一个问题。就是，在对磁道号进行分组时，最后 一列的处理问题。在开始时由于笼统地进行了平均分组，而没有考虑无法完全分尽的情一列的处理问题。在开始时由于笼统地进行了平均分组，而没有考虑无法完全分尽的情 况，进而导致最后一个甚至一些磁道号丢失的问题。不过最后，在单列最后一组后（即况，进而导致最后一个甚至一些磁道号丢失的问题。不过最后，在单列最后一组后（即 将最后一组与前面各组分开后）问题得到了解决。将余下的一个或一些磁道号全部加至将最后一组与前面各组分开后）问题得到了解决。将余下的一个或一些磁道号全部加至 最后一列末尾，很好地处理了数据丢失问题最后一列末尾，很好地处理了数据丢失问题哈尔滨理工大学课程设计报告- 19-有如下几点心得体会： 通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不仅仅是要通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不仅仅是要 把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好 地巩固所学，才能提高自己实践能力地巩固所学，才能提高自己实践能力. .通过这次的设计使我认识到只停留在表面理解问题通过这次的设计使我认识到只停留在表面理解问题 是很难使问题得到很好的解决的，实践能力与理论知识同样重要。可以说此课程设计的是很难使问题得到很好的解决的，实践能力与理论知识同样重要。可以说此课程设计的 理论难度并不大，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当理论难度并不大，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当 大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。通过模大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。通过模 拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解。模拟磁拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解。模拟磁 盘调度算法盘调度算法(SSTF,NstepSCAN)(SSTF,NstepSCAN)，实现各种不同调度算法的过程，并计算各算法的平均寻，实现各种不同调度算法的过程，并计算各算法的平均寻 道长度，以便于我们判断各种算法的优劣以及各种算法使用的场合。道长度，以便于我们判断各种算法的优劣以及各种算法使用的场合。哈尔滨理工大学课程设计报告- 20-2 Linux 代码分析为了进一步了解操作系统内核，学习了 Linux 操作系统的进程同步程序，主要程序 源代码如下：#!/bin/sh # Author: Guo Wenx