磁盘驱动调度算法的模拟

编写目的熟悉磁盘的结构以及磁盘的驱动调度算法的模拟， 编程实现简单常用的磁盘 驱动调度算法先来先服务（FIFO）、电梯调度算法、最短寻找时间优先算法、 扫描（双向扫描）算法、单向扫描（循环扫描）算法等。编程只需实现两个算法。题目可以选取教材或习题中的相关编程实例。编程语言建议采用c/c+或Java。模拟程序鼓励采用随机数技术、动态空间 分配技术，有条件的最好能用图形界面展现甚至用动画模拟。实验性质：验证型。二.课程设计内容1）掌握使用一门语言进行磁盘驱动调度算法的模拟；2）编写程序将磁盘驱动调度算法的过程和结果能以较简明直观的方式展 现出来。三.设计、方法和步骤1.设计磁盘驱动调度对磁盘的效率有重要影响。 磁盘驱动调度算法的好坏 直接影响辅助存储器的效率，从而影响计算机系统的整体效率。常用的磁盘驱动调度算法有：最简单的磁盘驱动调度算法是先入先 出（FIF O）法。这种算法的实质是，总是严格按时间顺序对磁盘请求予 以处理。算法实现简单、易于理解并且相对公平，不会发生进程饿死现 象。但该算法可能会移动的柱面数较多并且会经常更换移动方向，效率 有待提高。最短寻找时间优先算法：总是优先处理最靠近的请求。该算法移动的柱面 距离较小，但可能会经常改变移动方向，并且可能会发生进程饥饿现象。电梯调度：总是将一个方向上的请求全部处理完后， 才改变方向继续处理 其他请求。扫描（双向扫描）：总是从最外向最里进行扫描，然后在从最里向最外扫描。 该算法与电梯调度算法的区别是电梯调度在没有最外或最里的请求时不会移动 到最外或最里柱面，二扫描算法总是移到最外、最里柱面。两端的请求有优先服 被务的迹象。循环扫描（单向扫描）：从最外向最里进行柱面请求处理，到最里柱面后，直接跳到最外柱面然后继续向里进行处理。 该算法与扫描算法的区别是，回来过程不处理请求，基于这样的事实，因为里端刚被处理。2. 设计方法1）使用流程图描述演示程序的设计思想；2）选取C/C+、Java等计算机语言，编程调试，最终给出运行正确的程序3. 程序步骤参考程序：1） C/C+版的驱动调度算法-电梯调度模拟程序 #i nclude #in elude #i nclude #in clude vconi o.h typedef struct _proc char name32;int team;int ci;int rec;struct _proc *prior; struct _proc *n ext;/*定义进程名称*/*定义柱面号*/*定义磁道面号*/*定义记录号*/PROC;PROC *g_head=NULL,*g_curr=NULL,*local;int record=0;int yi=1;void init()/*初PROC *p;始化链表(初始I/O表)*/g_head = (PROC*)malloc(sizeof(PROC);g_head-next = NULL; g_head-prior = NULL;p = (PROC*)malloc(sizeof(PROC);strcpy(p- name, P1);p-team=100;p-ci=10;p-rec=1;p-n ext = NULL;p-prior = g_head;g_head-n ext = p; g_curr=g_head-n ext;p = (PROC*)malloc(sizeof(PROC);strcpy(p- name, P2); p-team=30;p-ci=5;p-rec=5;p-n ext = NULL;p-prior = g_curr;g_curr- n ext = p;g_curr=p;p = (PROC*)malloc(sizeof(PROC);strcpy(p- name, P3);p-team=40;p-ci=2;p-rec=4;p-n ext = NULL;p-prior = g_curr;g_curr- n ext = p;g_curr=p;p = (PROC*)malloc(sizeof(PROC);strcpy(p- name, P4); p-team=85;p-ci=7;p-rec=3;p-n ext = NULL; p-prior = g_curr; g_curr- n ext = p;g_curr=p;p = (PROC*)malloc(sizeof(PROC);strcpy(p-n ame, P5);p-team=60;p-ci=8;p-rec=4;p-n ext = NULL;p-prior = g_curr;g_curr- n ext = p;/*选中进程*/*打印I/O表*/g_curr=g_head-n ext;local = (PROC*)malloc(sizeof(PROC);strcpy(local- name, PO);local-team=0;local-ci=0;local-rec=0;local- next=NULL;local-prior=NULL;void Printlnit()PROC *t = g_head- next;printf(/n);printf( I/O LIST/n);prin tf( processteam ci rec/n);while(t!=NULL)printf(%4s %8d %8d %5d/n, t-name, t-team, t-ci, t-rec );t = t-n ext;prin tf(/n/n Curre nt process is :/n ”)；printf(/n/n);prin tf( processteam ci rec/n);prin tf(%4s %8d %8d %5d/n, local-name, local-team, local-ci, local-rec );switch(yi)case 1:pri ntf(curre nt direct ion is UP/n);break;case 0:pri ntf(curre nt direct ion is dow n/n );break;void acceptreq()/* 接受请求函数 */PROC *p;p = (PROC*)malloc(sizeof(PROC);prin tf(please in put the in formatio n of the newprocess/nprocess-n ame:/nprocess-team/nprocess-ci/nprocess-rec/n);prin tf(1. name/n ”);scan f(%s,p-n ame);prin tf(2.team 0-199/n);scanf(%d,&p-team);/*输入请求进程信息 */prin tf(3.ci 0-19/n);scan f(%d,&p-ci);prin tf(4.rec 0-7/n);scan f(%d,&p-rec);getchar();g_curr=g_head;/*将此节点链入I/O请求表*/while(g_curr- next!=NULL) g_curr=g_curr- n ext;p-n ext=NULL;p-prior=g_curr;g_curr- n ext=p; g_curr=g_head-n ext;printf(NEW I/O LIST/n/n);Printlni t();void qddd()PROC *out;int min;int max=g_head-n ext-team; if (g_head- next=NULL); else switch (yi)/*将新的I/O请求表输出*/*驱动调度函数*/*若已全部调度，则空操作*/case 1:min=g_head-n ext-team;out=g_head-n ext;team进程，模拟启动此进程*/*选出最小的strcpy(local-n ame,out- n ame);local-team=out-team;local-ci=out-ci;local-rec=out-rec;for (g_curr=g_head-n ext;g_curr!=NULL;g_curr=g_curr- n ext)if (g_curr-team record) min = g_curr-team;break;for (g_curr=g_head-n ext;g_curr!=NULL;g_curr=g_curr- n ext)if (min=g_curr-team&g_curr-teamrecord)min=g_curr-team;out=g_curr;strcpy(local-n ame,out- n ame);local-team=out-team;local-ci=out-ci;local-rec=out-rec;printf(/n/n);prin tf(the process choosed :/n);prin tf( processteam ci rec /n);printf(%4s %8d %8d %5d/n, out-name, out-team, out-ci,out-rec );record = local-team;prin tf(%d,record);for (g_curr=g_head-n ext;g_curr!=NULL;g_curr=g_curr- n ext)if (maxteam)max=g_curr-team;if(max=record)yi=0;record=1000;break;break;/*case 1的对称过程/*case 1*/case 0:*/strcpy(local-n ame,out- n ame);local-team=out-team;local-ci=out-ci;local-rec=out-rec;for (g_curr=g_head-n ext;g_curr!=NULL;g_curr=g_curr- n ext)if (g_curr-team team;break;for (g_curr=g_head-n ext;g_curr!=NULL;g_curr=g_curr- n ext)if (maxteam&g_curr-teamteam;out=g_curr;strcpy(local-n ame,out- n ame);local-team=out-team;local-ci=out-ci;local-rec=out-rec;printf(/n/n);prin tf(the process choosed :/n);prin tf( process team ci rec /n);printf(%4s %8d %8d %5d/n, out-name, out-team, out-ci,out-rec ); min=g_head-n ext-team;for (g_curr=g_head-n ext;g_curr!=NULL;g_curr=g_curr- n ext)if (mi n g_curr-team)min=g_curr-team;record = local-team;if(min=record)yi=1;record=0;break;break;default : return -1;/*将选中的进程从I/O/*switch*/if (out- n ext=NULL)请求表中删除*/out-prior- n ext=NULL;free(out); elseout-prior- n ext=out- n ext;out- n ext-prior=out-prior;free(out);/*else*/void acceptnum()/* 通过输入 OT 选择驱动调度或是接受请求*/float num;char c;while(1)printf(/n);prin tf(please in put a nu mber betwee n 0 and 1/nnum0.5:qud ong diaodu/n/nnum=2:1/0 LIST/ n/nnum=?/n); scan f(%f,&nu m);getchar();while( num 1)&n um!=2)/* 过滤不合法数据注意：本程序其他输入数据可能未过滤*/prin tf( nu mber ERROR!I nput aga in please!/nnum=?/n );scan f(%f,&nu m);getchar();if(n um0.5&nu m!=2)if (g_head- next=NULL)prin tf(/n/n);printf(/n);prin tf(I/O list is empty!/n); else/*驱动调度*/*请求表为空无需调度*/*调用函数进行调度*/prin tf(qudo ng diaodu/n); qddd();/*接受请求*/*通过输入2显示当前else if (num=0.5)prin tf(accept request/n/n);acceptreq();else if (num=2)请求I/O表*/prin tf(I/O LIST;);printf(/n);Printlni t();prin tf(/n);/*输入prin tf(choose n to quit else to continue/n);n离开本程序*/if(strcmp(c=getchar(), n)=O|strcmp(c=getchar(),N)=O)clrscr();prin tf(/n/n/n/n/n/n);prin tf(tha nk you for test ing my program!/n);printf( -by01/n);sleep(2);prin tf(/n/nBYEbye!);sleep(2);return -1;elseclrscr();main ()/* 主程序 */ini t();Printlni t();accept num();设计体会能够将磁盘驱动调度算法在各种情况下都能得出正确的结论。对FIFO、最短寻找时间优先或电梯调度算法能够在多次模拟数据下得出平均移动柱面数，并进行效率比较分析。2011 -2012学年第一学期操作系统课程设计报告班级学号姓名成绩指导教师 于复兴