磁盘的调度算法
- 格式：doc
- 大小：127.50 KB
- 文档页数：18
整理为word格式 实验七 磁盘的调度算法
一.实验要求
设计五个算法,分别是先来先服务算法,最短寻道时间优先算法,扫描(SCAN)算法,循环扫描(CSCAN)算法,NStepSCAN算法.由人工输入当前的磁道数,由系统随即生成要访问的磁道.
二、开发环境
操作系统:Rad Hat Linux ,开发环境:C语言.
三、分析设计
（一）实验原理.
磁盘是可被多个进程共享的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法，以使各进程对磁盘的平均访问(主要是寻道)时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标应是使磁盘的平均寻道时间最少。
(1) 先来先服务．(First-Come，First-Served，FCFS):
这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。
(2) 最短寻道时间优先(ShortestSeekTimeFirst，SSTF):
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。
(3) 扫描(SCAN)算法:
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。
(4) 循环扫描(CSCAN)算法:
处理该进程的请求，致使该进程的请求被严重地推迟。为了减少这种
整理为word格式 延迟，CSCAN算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。
整理为word格式 (5) N_Step_SCAN算法:
N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按FCFS算法依次处理这些子队列.而每处理一个队列时又是按SCAN算法,对一个队列处理完后,再处理其他队列.当正在处理某子队列时,如果又出现新的磁盘I/O请求,便将新请求进程放进其他队列.
（二）程序结构
第一部分:程序的主要流程
(1) 手动输入当前的磁道号,该磁道号在0
(2) 手动输入要寻找磁道的范围.
(3) 主菜单,选择要进行磁道调度算法,此时会随机生成一个在第二步生成磁道范围以内的10个磁道数,由SetDI方法生成,再将生成的随机磁道号以数组形式作为参数被某个算法调用.例如,选择了case 1,则先调用SetDI方法,再执行FCFS算法.如下:
case 1:
SetDI(DiscLine); //随机生成磁道数
FCFS(Hand,DiscLine); //先来先服务算法(FCFS)
break;
第二部分: 部分的代码实现
(1) 就每个算法而言,都有调用一个子算法CopyL把函数SetDI随机生成的磁道数数组复制给RLine[],为什么要复制,原因是在整个程序中的最后一项功能是实现5种算法对一次随即生成的磁道数的比较,所以在每次调用一种算法时需要设置一个临时的数组Rline[]来存放.
(2)在这5个算法中都有一个字函数DelInq，该函数的作用是使每个磁道数向前移动一位，简单地以FCFS算法为例，这里只FCFS其中的核心代码：
All=Han-RLine[0];
for(i=0;i<=9;i++)
{
Temp=RLine[0]-RLine[1];//求出移动磁道数,前一个磁道数减去后一个磁道数得出临时的移动距离
if(Temp<0)
Temp=(-Temp);//移动磁道数为负数时,算出相反数作为移动磁道数
整理为word格式 printf("%5d",RLine[0]);
All=Temp+All;//求全部磁道数的总和
DelInq(RLine,0,k);//每个磁道数向前移动一位
k--;
}
Han是当前磁道数，RLine[0]是第一个随机磁道数，Han-RLine[0]得到的是一次磁头移动的距离，再赋予All，即All是存放磁头移动的距离总和，for循环是执行10次，Temp变量是求出移动磁道数,前一个磁道数减去后一个磁道数得出临时的移动距离，All=Temp+All是求全部磁道数的总和之后是DelInq函数，使每个磁道数向前移动一位。例如随机生成的磁道数数组RLine是：
583 286 177 115 593 535 586 492 249 421
因为当前的磁道数是500，通过All=Han-RLine[0]语句得到All等于83，接下来是Temp=RLine[0]-RLine[1]，是583-286=297，此时All等于83+297=380，再通过DelInq整个RLine数组的每个元素向前移一位，如下图所示：
(3) 如果选择”case 6: 各类算法的比较”,该比较是比较这5种算法的寻道长度的总和,由小到大的排序.算法由PaiXu()函数实现.具体是每种算法的最后都设置Best[][]的二维数组, Best[Jage][1]=All,All是磁道数总和,Jage视每种算法而定,例如FCFS为1,则Jage为1, SSTF为2,则Jage为2,Best[Jage][0]=1(用来唯一标识某个算法) .最后以PaiXu()算法,用冒泡法排序把5个算法的磁道数综合由小到大排序.
（三）数据结构：
Hand:当前磁道号;
DiscLine[10]:随机生成的磁道号;
void SetDI(int DiscL[])生成随机磁道号算法;
void CopyL(int Sour[],int Dist[] ,int x) 数组Sour复制到数组Dist，复制到x个数（四）详细设计;
void DelInq(int Sour[],int x,int y) 数组Sour把x位置的数删除,x后的数组元素向前挪一位.
void PaiXu()寻道长度由低到高排序
void FCFS(int Han,int DiscL[])先来先服务算法(FCFS)
void SSTF(int Han,int DiscL[])最短寻道时间优先算法(SSTF)
int SCAN(int Han,int DiscL[],int x,int y) 扫描算法(SCAN)
void CSCAN(int Han,int DiscL[])循环扫描算法(CSCAN)
void N_Step_SCAN(int Han1,int DiscL[])N步扫描算法(NStepScan)
整理为word格式 ****************************************
* 课题：磁盘调度算法 *
*****************************************
#include "stdio.h"
#include "stdlib.h"
void CopyL(int Sour[],int Dist[] ,int x); //数组Sour复制到数组Dist，复制到x个数
void SetDI(int DiscL[]); //随机生成磁道数
void Print(int Pri[],int x); //打印输出数组Pri
void DelInq(int Sour[],int x,int y); //数组Sour把x位置的数删除，并把y前面的数向前移动，y后的数保持不变(即会出现2个y)
void FCFS(int Han,int DiscL[]); //先来先服务算法(FCFS)
void SSTF(int Han,int DiscL[]); //最短寻道时间优先算法(SSTF)
int SCAN(int Han,int DiscL[],int x,int y); //扫描算法(SCAN)
void CSCAN(int Han,int DiscL[]); //循环扫描算法(CSCAN)
void N_Step_SCAN(int Han1,int DiscL[]); //N步扫描算法(NStepScan)
void PaiXu(); //寻道长度由低到高排序
void Pri();
int NAll=0;
int Best[5][2]; //用作寻道长度由低到高排序时存放的数组
int Limit=0; //输入寻找的范围磁道数i
int Jage;
float Aver=0;
int main()
{
int i;
int DiscLine[10]; //声明准备要生成的随机磁道号的数组
int Hand; //磁道数
int Con=1;
int n;
while(Con==1)
{
Jage=0;
printf(" 请输入初始的磁道数(0
scanf("%d",&Hand);
printf(" + 输入寻找的范围:");
整理为word格式 scanf("%d",&Limit);
if(Limit>65536){
printf("超出范围!");
}
else{
printf(" ╭═══════════════╮
");
printf(" ║ 操作系统课程设计 ║
");
printf(" ╭═════┤ 磁盘调度算法 ├═════╮ ");
printf(" ║ ║ ║
║ ");
printf(" ║ ╰═══════════════╯
║ ");
printf(" ║ 1.先来先服务算法(FCFS)
║ ");
printf(" ║
║ ");
printf(" ║ 2.最短寻道时间优先算法(SSTF)
