第一篇：多级反馈队列调度算法
多级反馈队列调度算法
一实验内容
以链式结构组成空闲PCB栈，以双向链式结构组成进程的就绪队列和睡眠队列，模拟UNIX的进程管理程序，实现以下操作（可用键盘命令、命令文件或由产生的随机数决定操作和参数）。
（1）创建一个新进程：如pid=newp（pri，size，time），申请空闲PCB和所需内存，填写PCB的各项初始数据，将该PCB送入就绪队列。
（2）调度和执行：自己设计多级反馈队列调度算法，在就绪队列中选择一个优先级最高的进程，使其运行若干单位时间。要求在运行期间进程的p_cpu、p_pri和p_time要变化，并在适当的时机重新调度。
（3）进程睡眠：进程运行时可调用自编的睡眠函数，主动进入睡眠状态，并转调度程序。也可由操作使进程强迫挂起，睡眠适当时间。进程睡眠时要在PCB中记录睡眠原因和优先数。
（4）进程的唤醒：根据睡眠原因，将相应的进程从睡眠队列中调出，转入就绪队列。如果该进程优先级比现在运行的优先级高，则转调度程序。
（5）进程的终止：如果一个进程运行完作业所需的时间，该进程就终止，释放所占用的内存和PCB资源，转调度程序。
二、设计思想
实现多级犯规队列调度算法，多级调度队列分别高优先级（H或h）队列、中优先级（M或m）队列和低优先级的（L或l）队列。
（1）当一个进程在一次运行中用完了时间片（100单位时间）还未完成任务或没有进入阻塞状态，降低其优先级，进入低一级的调度队列。
（2）进程没用完的时间片，就因为I/O等原因转变为阻塞状态。等到阻塞原因解除，转变为就绪状态后，仍回到原先队列。
（3）当一个进程正在运行时，在更高的优先级的队列中到来了一个进程，那么高优先级的进程可以抢占当前进程的处理机。被抢占的进程已运行了一定的时间（但没到达100单位时间），仍留在原先的队列中。（4）进程在时间片内完成了任务，被撤离系统。
三、函数和算法（1）建议使用的PCB数据结构
struct mypcb {
char p_pid;//进程标志数 char p_pstat;//进程状态
void *p_addr;//进程映像在内存中的首址 int p_size;//进程映像的长度 char p_pri;//进程优先数
int p_cpu;//进程当前运行的时间
int p_time;//作业运行的（剩余）总时间 char p_wchan;//进程睡眠原因
struct mypcb *p_next,*p_prior;//进程mypcb的双向链指针 };
（2）主程序：
初始化变量和队列
从输入文件中读入进程信息，创建进程 打印初始的3个调度队列进程 调度主循环
首先调度高优先级队列进程 IF 有进行苏醒
设定当前进程运行一段时间，进程剩余时间减去该时间
打印当前进程的信息和将要唤醒的进程
在睡眠队列唤醒进程，回到调度主循环 IF当前进程满足睡眠条件
打印当前进程的信息
进程移出调度队列
加入睡眠队列，回到调度主循环 IF 当前进程不满足睡眠条件 IF 进程总剩余时间>100
运行并用掉时间片中的剩余时间
从高优先级队列中移出，加入中优先级队列 ELSE
用掉全部剩余时间，从队列中删去
其次调度次高优先级队列进程（略）
最后调度低优先级队列进程（略）
如果3个调度队列和睡眠队列皆空，调度循环终止
（3）函数 i.ii.iii.int init（）初始化变量、初始化调度队列和睡眠队列
int printlist（struct list *List）打印调度队列中的进程和剩余运行时间
int gotosleep（struct mypcb *process）根据进程的剩余运行时间p_time,struct proc *wakeup（struct list *List）判断是否有进程苏醒，本程序设int wakeup_work（struct mypcb *p，struct list *List）苏醒进程插进原使其运行一段时间，并设置睡眠状态
iv.计调用5次，唤醒队列首进程
v.先优先级队列
vi.int newp（char pri，int size，int time）根据优先数、进程大小和运行时间的参数创建一个新进程，为新进程分配内存空间,睡眠原因为空，如进入睡眠，状态为‘s’；
vii.int addlist（struct list *List，struct mypcb *process）将进程添加到队列的尾部，包括睡眠队列;
四、测试与分析
程序输入格式为：./sched <输入文件名>
输入文件内容为：
优先级 内存大小 分配时间 H 1000 301 H 1000 200 M 1000 203 M 1000 200 H 1000 100 M 1000 102 L 1000 200
五、总结和思考
1、总结自己实验过程中的心得体会；
2、思考以下问题：
（1）如何用简单的方法模拟I/O中断或其他事件，使进程睡眠若干时间。（2）如何设计触发睡眠队列中进程的事件，使其被唤醒，转变为运行状态。
3、回答以下问题：
（1）多级反馈优先级队列调度的优点是什么？（2）比较本实验程序中使用的PCB与实际的（比如Linux/Unix系统）PCB的主要区别，有哪些信息本调度算法中没有用到？如果采用其他的调度算法，需要增加哪些信息？
第二篇：电梯优先调度算法
电梯优先调度算法
电梯调度算法(ms InterView)
移臂调度算法包括以下四种：
1）先来先服务算法：根据访问者提出访问请求的先后次序来决定执行次序。
2）最短寻找时间优先调度算法：从等待的访问者中挑选寻找时间最短的那个请求执行，而不管访问者的先后次序。
3）电梯调度扫描算法：从移动臂当前位置沿移动方向选择最近的那个柱面的访问者来执行，若该方向上无请求访问时，就改变移动方向再选择。
4）单向扫描调度算法：从0柱面开始往里单向扫描，扫到哪个执行哪个。
*/
// t1.cpp : 定义控制台应用程序的入口点。
//
#include “stdafx.h” #include“math.h” #include“stdlib.h” #include“string.h” struct Head {
int nPosition;bool bVisited;};
void Visit(struct Head *pHead){
printf(“visite cy:%dn”,pHead->nPosition);pHead->bVisited=true;} int ReadInputKeyboard(struct Head *pHead,int *pCurrentPosition,int nMaxNumber){ int i;
printf(“please input Current position:”);scanf(“%d”,pCurrentPosition);
printf(“please input will visit position:”);for(i=0;i scanf(“%d”,&pHead[i].nPosition);pHead[i].bVisited=false;if(pHead[i].nPosition<0)break;} return i;} int ReadInputFile(struct Head *pHead,int *pCurrentPosition,int nMaxNumber){ int i; char szFileName[256],*q,*p,szTemp[20];printf(“please input filename:”);scanf(“%s”,szFileName); FILE *pFile=fopen(szFileName,“r”);if(pFile==NULL){ printf(“open file %s error”,szFileName);return-1;} for(i=0;!feof(pFile)&&i p=szFileName;fgets(p,256,pFile); while(q=strchr(p,',')){ memset(szTemp,0,sizeof(szTemp)*sizeof(char));strncpy(szTemp,p,q-p);p=q+1;if(i==0) *pCurrentPosition=atoi(szTemp);else { pHead[i-1].nPosition=atoi(szTemp);pHead[i-1].bVisited=false;} i++;} memset(szTemp,0,sizeof(szTemp)*sizeof(char));pHead[i-1].nPosition=atoi(p);pHead[i-1].bVisited=false;//i++; } fclose(pFile);return i;} int FifoVisit(int nCurrentPosition,struct Head *pHead,int nNumber){ //先来先服务 int nHaveVisited=0;int nMoveDistance=0;int i;while(nHaveVisited for(i=0;i if(pHead[i].bVisited)continue; Visit(&pHead[i]);nHaveVisited++; nMoveDistance+=abs(nCurrentPosition-pHead[i].nPosition);nCurrentPosition=pHead[i].nPosition;} } printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int SsfoVisit(int nCurrentPosition,struct Head *pHead,int nNumber){ // 最短寻找时间优先 int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i; while(nHaveVisited nMinDistance=0xffff;nMinIndex=0;//找最小值 for(i=0;i if(pHead[i].bVisited)continue; if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){ nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } //访问 Visit(&pHead[nMinIndex]);nHaveVisited++; nMoveDistance+=nMinDistance; nCurrentPosition=pHead[nMinIndex].nPosition;} printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int DtVisit(int nCurrentPosition,bool bOut,struct Head *pHead,int nNumber){ //电梯调度算法 int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i; while(nHaveVisited nMinDistance=0xffff;nMinIndex=0;//找最小值 for(i=0;i if(pHead[i].bVisited)continue; if(bOut&&pHead[i].nPosition if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){ nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } } if(nMinDistance==0xffff){ bOut=!bOut;continue;} //访问 Visit(&pHead[nMinIndex]);nHaveVisited++; nMoveDistance+=nMinDistance; nCurrentPosition=pHead[nMinIndex].nPosition;} printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int DxVisit(int nCurrentPosition,struct Head *pHead,int nNumber){ //单向调度算法 int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i;while(nHaveVisited nMinDistance=0xffff;nMinIndex=0;//找最小值 for(i=0;i if(pHead[i].bVisited)continue; if(pHead[i].nPosition>nCurrentPosition){ if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){ nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } } if(nMinDistance==0xffff){ nMoveDistance+=199-nCurrentPosition;nCurrentPosition=0;continue;} //访问 Visit(&pHead[nMinIndex]);nHaveVisited++; nMoveDistance+=nMinDistance; nCurrentPosition=pHead[nMinIndex].nPosition;} printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int main(int argc, char* argv[]){ //p114 struct Head mylist[20];//={98,false,183,false,37,false,122,false,14,false,124,false,65,false,67,false}; //int nCurrentPosition=53; //int nRealNumber=8; int nCurrentPosition=0; int nRealNumber=ReadInputFile(mylist,&nCurrentPosition,20);// FifoVisit(nCurrentPosition,mylist,nRealNumber); // SsfoVisit(nCurrentPosition,mylist,nRealNumber); //DtVisit(nCurrentPosition,false,mylist,nRealNumber); DxVisit(nCurrentPosition,mylist,nRealNumber); return 0;} 1.实验题目: 磁盘调度算法。 建立相应的数据结构； 在屏幕上显示磁盘请求的服务状况； 将一批磁盘请求的情况存磁盘文件，以后可以读出并重放； 计算磁头移动的总距离及平均移动距离； 支持算法：FIFO、SSTF、SCAN、CSCAN; 2.设计目的: 调度磁盘I/O请求服务，采用好的方式能提高访问时间和带宽。本实验通过编程对磁盘调度算法的实现，加深对算法的理解，同时通过用C++语言编写程序实现这些算法，并在windos平台上实现，更好的掌握操作系统的原理以及实现方法，提高综合运用专业课知识的能力。 3.任务及要求 3.1 设计任务 编程实现下述磁盘调度算法，并求出每种算法的平均寻道长度： 1、先来先服务算法（FCFS） 2、最短寻道时间算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN） 3.2 设计要求 对用户指定的磁盘调度请求序列，基于以上四种算法，实现各自的调度顺序并输出，同时计算出各种算法下的平均寻道长度。 4.算法及数据结构 4.1算法的总体思想 queue[n] 为请求调度序列，diskrode为磁盘磁道数，headstarts为正在调度的磁道 ①先来先服务算法（FCFS）按queue[n]数组的顺序进行磁盘调度，将前一个调度磁道与下一个调度磁道的差值累加起来，得到总的寻道长度，再除以n得到平均寻道长度。 ②最短寻道时间优先算法（SSTF）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，通过循环语句找出离起始磁头最短的位置。 ③扫描算法（SCAN） 将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，再在定位处反向遍历到另一端。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁 道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。 ④循环扫描算法（CSCAN）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，反向到另一端点再以此方向进行遍历，直到queue[n]中所有都调度完。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上磁盘磁道总长度，再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。 5、源代码： #include 1、先来先服务算法（FCFS)**********”< cout<<“****** 2、最短寻道时间优先算法(SSTF)**********”< cout<<“****** 3、扫描算法(SCAN)**********”< cout<<“****** 4、循环扫描算法(CSCAN)**********”< cout<<“****** 5、退出 **********”< /*======================初始化序列=======================*/ void init(int queue[],int queue_copy[],int n){ int i;for(i=0;i //对当前正在执行的磁道号进行定位，返回磁道号小于当前磁道中最大的一个 int fix(int queue[], int n, int headstarts){ int i =0;while(i /* ====================以下是FCFS算法==================*/ void FCFS(int queue[],int n,int diskrode,int headstarts)//queue是请求调度序列，n为其个数，diskroad为磁盘磁道数，headstarts为正在调度的磁道 { cout<<“************以下为FCFS调度算法***********”< /*=====================SSTF算法====================*/ void SSTF(int queue[], int n, int diskrode, int headstarts){ int k=1;int l,r;int i,j,count=0;queue =bubble(queue,n);cout<<“************以下为SSTF调度算法***********”< -headstarts)){ cout< /*======================以下是SCAN算法====================*/ void SCAN(int queue[], int n, int diskrode, int headstarts){ int direction, i, fixi;cout<<“***********以下是SCAN调度算法*************”< /*======================以下是CSCAN算法====================*/ void CSCAN(int queue[],int n,int diskrode,int headstarts){ int direction,i,fixi;cout<<“***********以下是CSCAN调度算法*************”< void main(){ int n, i, diskrode, headstarts;//n表示调度磁盘请求序列queue的长度，diskrode表示磁盘磁道的个数，headstarts表示目前正在调度的磁道； cout<<“请输入磁盘的总磁道数:”< if(menux ==2)SSTF(queue,n,diskrode,headstarts); if(menux ==3)SCAN(queue,n,diskrode,headstarts);if(menux ==4)CSCAN(queue,n,diskrode,headstarts);if(menux ==5)cout<<“程序结束,谢谢使用！”< 1.传统电梯调度算法 1.1先来先服务算法(FCFS) 先来先服务(FCFS-First Come First Serve)算法，是一种随即服务算法，它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，它是一种最简单的电梯调度算法。它根据乘客请求乘坐电梯的先后次序进行调度。此算法的优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求长期得不到满足的情况[12]。这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，这种算法的性能就会严重下降，甚至恶化。人们之所以研究这种在载荷较大的情况下几乎不可用的算法，有两个原因： (1)任何调度算法在请求队列长度为1时，请求速率极低或相邻请求的间隔为无穷大时使用先来先服务算法既对调度效率不会产生影响，而且实现这种算法极其简单。 (2)先来先服务算法可以作为衡量其他算法的标准。 1.2最短寻找楼层时间优先算法(SSTF) 最短寻找楼层时间优先(SSTF-Shortest Seek Time First)[14]算法，它注重电梯寻找楼层的优化。最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“饿死”现象。 1.3扫描算法(SCAN) 扫描算法(SCAN)是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。它进行寻找楼层的优化，效率比较高，但它是一个非实时算法。扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的，所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成，免去了电梯频繁的来回移动[2]。扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻找楼层时间优先算法小，从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法稳定。 1.4 LOOK 算法 LOOK算法[18]是扫描算法的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。但当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。 1.5 SAFT 算法 SATF(Shortest Access Time First)[15,19]算法与SSTF算法的思想类似，唯一的区别就是SATF算法将SSTF算法中的寻找楼层时间改成了访问时间。这是因为电梯技术发展到今天，寻找楼层的时间已经有了很大地改进，但是电梯的运行当中等待乘客上梯时间却不是人为可以控制。SATF算法考虑到了电梯运行过程中乘客上梯时间的影响。实时电梯调度算法 2.1最早截止期优先调度算法 最早截止期优先(EDF-Earliest Deadline First)[16]调度算法是最简单的实时电梯调度算法，它的缺点就是造成电梯任意地寻找楼层，导致极低的电梯吞吐率。它与FCFS调度算法类似，EDF算法是电梯实时调度算法中最简单的调度算法。它响应请求队列中时限最早的请求，是其它实时电梯调度算法性能衡量的基准和特例。 2.2 SCAN-EDF 算法 SCAN-EDF[16]算法是SCAN算法和EDF算法相结合的产物。SCAN-EDF算法先按照EDF算法选择请求列队中哪一个是下一个服务对象，而对于具有相同时限的请求，则按照SCAN算法服务每一个请求。它的效率取决于有相同deadline 的数目，因而效率是有限的。 2.3 PI 算法 PI(Priority Inversion)[16]算法将请求队列中的请求分成两个优先级，它首先保证高优先级队列中的请求得到及时响应，再搞优先级队列为空的情况下在相应地优先级队列中的请求。 2.4 FD-SCAN 算法 FD-SCAN(Feasible Deadline SCAN)[17]算法首先从请求队列中找出时限最早、从当前位置开始移动又可以买足其时限要求的请求，作为下一次SCAN的方向。并在电梯所在楼层向该请求信号运行的过程中响应处在与电梯运行方向相同且电梯可以经过的请求信号。这种算法忽略了用SCAN算法相应其它请求的开销，因此并不能确保服务对象时限最终得到满足。电梯调度的高水平研究 以上两个小结介绍了几种在目前本人的能力上能进行研究的、简单的电梯调度算法。但是并不是说目前电梯调度只发展到这个层次。目前电梯的控制技术已经进入了电梯群控的时代。 随着微机在电梯系统中的应用和人工智能技术的发展，智能群控技术得以迅速发展起来。由此，电梯的群控方面陆续发展出了一批新方法，包括：基于专家系统的电梯群控方法、基于模糊逻辑的电梯群控方法、基于遗产算法的电梯群控方法、基于胜景网络的电梯群控方法和基于模糊神经网络的电梯群控方法。4 电梯问题的需求分析 4.1 电梯的初始状态 本人设置的电梯的初始状态，是对住宅楼的电梯的设置。 (1)建筑共有21层，其中含有地下一层（地下一层为停车场及货物运送场所）。 (2)建筑内部设有两部电梯，编号分别为A梯、B梯。 (3)电梯内部有23个按钮，其中包括开门按钮、关门按钮和楼层按钮，编号为-1，1，2，3，4……20。 (4)电梯外部含有两个按钮，即向上运行按钮和向下运行按钮。建筑顶层与地下一层例外，建筑顶层只设置有向下运行按钮，地下一层只设置有向上运行按钮。 (5)电梯开关门完成时间设定为1秒。电梯到达每层后上下人的时间设定为8秒。电梯从静止开始运行到下一层的时间设置为2秒，而运行中通过一层的时间为1秒。 (6)在凌晨2：00——4：30之间，如若没有请求信号，A梯自动停在14层，B梯自动停在6层。 (7)当电梯下到-1层后，如果没有请求信号，电梯自动回到1层 4.2 电梯按钮功能 电梯内部的楼层按钮：电梯内部对应每一个楼层的按钮成为楼层按钮，即本章第一结提到的编号为-1，1，2，3，4……20的按钮。当乘客进入电梯后按下楼层按钮，此按钮显示灰色，代表不可以用。这样就表示乘客将要去往此层，电梯将开往相应层。当电梯到达该层后，按钮恢复可以使用状态。 电梯内部开门按钮：当电梯达到乘客想要去往的某楼层后，乘客需要准备离开电梯，当电梯停稳后，乘客可以按下开门按钮，电梯门将打开，让用户离开。如若电梯到了乘客曾经按下的楼层，但是无乘客按开门按钮，电梯将自动在停稳后1秒后自动开门。 电梯内部关门按钮：当所有想要乘坐电梯的乘客都进入电梯以后，准备让电梯开始运行的时候，乘客需要按下关门按钮，让电梯门关闭，使电梯进入运行状态。设置电梯的自动关门时间为8秒。 电梯外部向上按钮：此按钮表示上楼请求，当按下此按钮时，如果电梯到达按下此按钮的楼层，且电梯运行方向是向上的，那么电梯响将停下，并在电梯停稳之后自动开门，此请求被响应后，取消此请求信号。电梯外部向下按钮：此按钮表示下楼请求，当按下此按钮时，如果电梯到达按下此按钮的楼层，且电梯运行方向是向下的，那么电梯响将停下，并在电梯停稳之后自动开门，此请求被响应后，取消此请求信号。 沈阳理工大学课程设计专用纸 Noi 目 录 1 课程设计目的及要求……………………………………………………错误！未定义书签。2 相关知识…………………………………………………………………错误！未定义书签。3 题目分析…………………………………………………………………2 4 概要设计…………………………………………………………………2 4.1 先来先服务（FCFS）的设计思想……………………………….2 4.2 最短寻道时间优先调度（SSTF）的设计思想…………………..2 4.3 扫描算法（SCAN）的设计思想…………………………………2 4.4 循环扫描（CSCAN）的设计思想………………………………..2 5 代码及流程………………………………………………………………3 5.1 流程图……………………………………………………………...3 5.2 源代码……………………………………………………………...8 6 运行结果…………………………………………………………………16 7 设计心得…………………………………………………………………19 参考文献…………………………………………………………………………19 沈阳理工大学 沈阳理工大学课程设计专用纸 No1 1 课程设计目的及要求 设计目的：加深对操作系统原理的进一步认识，加强实践动手能力和程序开发能力的培养，提高分析问题解决问题的能力，培养合作精神，以巩固和加深磁盘调度的概念。操作系统是一门工程性很强的课程，它不仅要求学生掌握操作系统的工作原理和理论知识，也要求学生的实际动手能力，以加深对所学习内容的理解，使学生熟练地掌握计算机的操作方法，使用各种软件工具，加强对课程内容的理解。这次课程设计，就是通过模拟磁臂调度来加深对操作系统中磁臂调度概念的理解。使学生熟悉磁盘管理系统的设计方法；加深对所学各种磁盘调度算法的了解及其算法的特点。 设计要求：编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度；要求设计主界面可以灵活选择某算法，且以下算法都要实现 1、先来先服务算法（FCFS） 2、最短寻道时间优先算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN）相关知识 数据结构：数组 now:当前磁道号; array[]:放置磁道号的数组; void FCFS(int array[],int m)先来先服务算法(FCFS)void SSTF(int array[],int m)最短寻道时间优先算法(SSTF)void SCAN(int array[],int m)扫描算法(SCAN)void CSCAN(int array[],int m)循环扫描算法(CSCAN)磁盘调度：当有多个进程都请求访问磁盘时，采用一种适当的驱动调度算法，使各进程对磁盘的平均访问（主要是寻道）时间最小。目前常用的磁盘调度算法有：1）闲来先服务2）最短寻道时间优先3）扫描算法4）循环扫描算法等 沈阳理工大学 沈阳理工大学课程设计专用纸 No2 3 题目分析 选择一个自己熟悉的计算机系统和程序设计语言模拟操作系统基本功能的设计方法及其实现过程 完成各分项功能。在算法的实现过程中，要求可决定变量应是动态可变的；同时模块应该有一个合理的输出结果。具体可参照实验的程序模拟.各功能程序要求自行编写程序实现，不得调用现有操作系统提供的模块或功能函数。磁盘调度程序模拟。先来先服务调度算法.最短寻道时间优先调度，循环（SCAN）调度算法。程序设计语言自选，最终以软件（含源代码以及执行程序）和设计报告的形式提交课程设计结果.。磁盘调度让有限的资源发挥更大的作用。在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列。概要设计 1.先来先服务（FCFS）的设计思想 即先来的请求先被响应。FCFS策略看起来似乎是相当“公平”的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间。为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候fcfs也被看作是最简单的磁盘调度算法。 2.最短寻道时间优先调度（SSTF）的设计思想 最短时间优先算法选择这样的进程。要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。 3.扫描算法（SCAN）的设计思想 扫描（SCAN）调度算法:该算法不仅考虑到欲访问 的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向里移动。这时，同样也是每次选择这样的进程来调度，也就是要访问的当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现像。 4.循环扫描（CSACN）的设计思想 循环扫描（CSCAN）算法：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该里程就必须等待，为了减少这种延迟，CSCAN算法规定磁头单向移动，而本实验过程中我们所设计的是磁头从里向外移动，而从外向里移动时只须改方向而已，本实验未实现。但本实验已完全能演示循环扫描的全过程。 沈阳理工大学 沈阳理工大学课程设计专用纸 No3 5 代码及流程 1.先来先服务（FCFS） 图 1—1 FCFS的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No4 2.最短寻道时间优先调度（SSTF） 图1—2 SSTF的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No5 3.扫描算法（SCAN） 图1—3 SCAN的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No6 4.循环扫描（CSCAN） 图1—4 CSCAN的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No7 图1—5 主函数的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No8 源代码： #include“stdio.h” #include“stdlib.h” //#include“iostream.h” #define maxsize 100 //定义最大数组域 //先来先服务调度算法 void FCFS(int array[],int m){ int sum=0,j,i;int avg;printf(“n FCFS调度结果: ”);for(i=0;i } avg=sum/(m-1);//计算平均寻道长度 printf(“n 移动的总道数： %d n”,sum);printf(“平均寻道长度： %d n”,avg);} //最短寻道时间优先调度算法 void SSTF(int array[],int m){ int temp;int k=1;int now,l,r;int i,j,sum=0;int avg;for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No9 array[i]=array[j];array[j]=temp;} } } for(i=0;i for(i=m-1;i>=0;i--)//将数组磁道号从大到小输出 printf(“%d ”,array[i]);sum=now-array[0];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { for(i=0;i printf(“%d ”,array[l]);sum+=now-array[l];//计算移动距离 now=array[l];l=l-1;} else 沈阳理工大学 沈阳理工大学课程设计专用纸 No10 { printf(“%d ”,array[r]);sum+=array[r]-now;//计算移动距离 now=array[r];r=r+1;} } if(l=-1){ for(j=r;j printf(“%d ”,array[j]);} sum+=array[m-1]-array[0];//计算移动距离 } else { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} sum+=array[m-1]-array[0];//计算移动距离 } } avg=sum/m;printf(“n 移动的总道数： %d n”,sum);printf(“平均寻道长度： %d n”,avg);} //扫描算法 void SCAN(int array[],int m)//先要给出当前磁道号和移动臂的移动方向 { int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No11 { temp=array[i];array[i]=array[j];array[j]=temp;} } } for(i=0;i printf(“n SCAN调度结果: ”);for(i=m-1;i>=0;i--){ printf(“%d ”,array[i]);//将数组磁道号从大到小输出 } sum=now-array[0];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { printf(“n SCAN调度结果: ”);for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No12 { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} for(j=r;j //循环扫描算法 void CSCAN(int array[],int m){ int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No13 { temp=array[i];array[i]=array[j];array[j]=temp;} } } for(i=0;i printf(“n CSCAN调度结果: ”);for(i=0;i printf(“%d ”,array[i]);//将磁道号从小到大输出 } sum=now-array[0]+array[m-1];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { printf(“n CSCAN调度结果: ”);for(i=0;i printf(“%d ”,array[i]);//将磁道号从小到大输出 } sum=array[m-1]-now;//计算移动距离 } else { while(array[k] 沈阳理工大学 沈阳理工大学课程设计专用纸 No14 { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} for(j=m-1;j>=r;j--){ printf(“%d ”,array[j]);} sum=2*(array[m-1]-array[0])-array[r]+now;//计算移动距离 }//磁道号减小方向 else { for(j=r;j // 操作界面 int main(){ int c;FILE *fp;//定义指针文件 int cidao[maxsize];//定义磁道号数组 int i=0,count;fp=fopen(“cidao.txt”,“r+”);//读取cidao.txt文件 if(fp==NULL)//判断文件是否存在 { printf(“n 请 先 设 置 磁 道!n”);exit(0);} while(!feof(fp))//如果磁道文件存在 沈阳理工大学 沈阳理工大学课程设计专用纸 No15 { fscanf(fp,“%d”,&cidao[i]);//调入磁道号 i++;} count=i-1;printf(“n-------------------n”);printf(“ 10-11OS课程设计--磁盘调度算法系统n”);printf(“ 计算机科学与技术二班n”);printf(“ 姓名：宋思扬n”);printf(“ 学号：0803050203n”);printf(“ 电话：************n”);printf(“ 2010年12月29日n”);printf(“n-------------------n”);printf(“n 磁道读取结果：n”);for(i=0;i 1、先来先服务算法（FCFS）n”);printf(“ 2、最短寻道时间优先算法（SSTF）n”);printf(“ 3、扫描算法（SCAN）n”);printf(“ 4、循环扫描算法（CSCAN）n”);printf(“ 5.退出n”);printf(“n”);printf(“请选择：”);scanf(“%d”,&c);if(c>5)break;switch(c)//算法选择 { case 1: FCFS(cidao,count);//先来先服务算法 printf(“n”);break;case 2: SSTF(cidao,count);//最短寻道时间优先算法 printf(“n”);break;case 3: 沈阳理工大学 沈阳理工大学课程设计专用纸 No16 SCAN(cidao,count);//扫描算法 printf(“n”);break;case 4: CSCAN(cidao,count);//循环扫描算法 printf(“n”);break;case 5: exit(0);} } return 0;} 6 运行结果 图2—1 运行界面 沈阳理工大学 沈阳理工大学课程设计专用纸 No17 图2—2 运行FCFS的界面 图2—3 运行SSTF的界面 图2—4 运行SCAN的界面 沈阳理工大学 沈阳理工大学课程设计专用纸 No18 图2—5 运行SCAN的界面 图2—6 运行CSCAN的界面 图2—7 运行CSCAN的界面 沈阳理工大学 沈阳理工大学课程设计专用纸 No19 运行结果： 四种磁盘调度运行结果正确，与预期的相符。设计心得 此次操作系统的课程设计，从理论到实践，在两个星期的日子里，可以说是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。 本次实验首先要了解磁盘调度的工作原理及四种调度方法的工作原理。在课程设计前的准备工作时，先把这部分工作做完了。在设计总的程序框架的时候，要注意各功能模块的位置，尽量做到简洁、有序；各功能模块与主程序要正确衔接。 在设计的过程中遇到许多问题，我设计的是四种调度算法中的后两种。例如：在最初程序设计时主要有两种构思：1）选用数据结构是链表的。2）选用数组。我最初尝试了用链表，觉得方便易懂，但是在循环扫描处出现了些问题，后来又转变了设计思路，选用了数组，直接进行排序，然后再联系到各功能模块。 同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，自身知识的很多漏洞，看到了自己的实践经验还是比较缺乏，理论联系实际的能力还急需提高。比如说编语言掌握得不好，应用程序编写不太会……通过这次课程设计之后，一定把以前所学过的知识重新温故。在此，也感谢在课程设计过程中帮我解惑的老师和同学。参考文献 [1] 《操作系统》 人民邮电出版社 宗大华 宗涛 陈吉人 编著 [2] 《C语言程序设计》 清华大学出版社 马秀丽 刘志妩 李筠 编著 [3] 《操作系统实验指导书》 沈阳理工大学 唐巍 菀勋 编著 沈阳理工大学第三篇：操作系统课程设计-磁盘调度算法
第四篇：电梯调度算法总结
第五篇：操作系统课程设计,磁盘调度算法范文
点击咨询 