操作系统磁盘调度算法

-.z.操作系统课程设计任务书题目：磁盘调度算法院系：专业：班级：姓名：学号：指导教师：设计时间：指导教师评语成绩评定：指导教师签字：年月日目录1、需求分析41.1课题描述41.2课题目的41.3理论依据72、概要设计82.1设计方法82.2技术82.3运行环境83、详细设计93.1流程图113.2程序主要代码134、运行结果及分析144.1运行结果154.2结果详细分析165、总结和心得166、参考文献177、附录：程序源代码231、需求分析1.1课题描述这次课程设计我研究的题目是：磁盘调度算法。具体包括三种算法分别是：先来先效劳算法〔FCFS〕、最短寻道时间优先算法(SSTF)、扫描算法〔电梯调度算法〕(SCAN)。1.2课题目的通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先效劳FCFS，最短寻道时间优先SSTF，扫描SCAN算法的实现方法。1.3理论依据设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的要求来自多方面，常常需要排队。这时，对众多的要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。磁盘的时间因子由3局部构成，它们是查找〔查找磁道〕时间、等待〔旋转等待扇区〕时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度〔L〕为所有磁道所需移动距离之和除以总的所需的磁道数〔N〕，即：L=〔M1+M2+„„+Mi+„„+MN〕/N其中Mi为所需的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进展读写，完成信息传送。因此，执行一次输入输出所花的时间有：寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间——指定扇区旋转到磁头下所需的时间。传送时间——由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进展移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序，每个柱面按磁道顺序，每个磁道又按扇区顺序进展排序。磁盘是可供多个进程共享的设备，当有多个进程都要求磁盘是，应采用一种最正确调度算法，以使各种进程对磁盘的平均时间最小。由于在磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标，是使磁盘的平均寻道时间最少。目前常用的磁盘帝调度算法有：先来先效劳、最短寻道时间优先及扫描等算法。先来先效劳〔FCFS〕调度:按先来后到次序效劳，未作优化。最简单的移臂调度算法是"先来先效劳〞调度算法，这个算法实际上不考虑者要求的物理位置，而只是考虑者提出请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待者依次要的柱面为130、199、32、159、15、148、61、99，则，当50号柱面上的操作完毕后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。采用先来先效劳算法决定等待者执行输入输出操作的次序时，移动臂来回地移动。先来先效劳算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。最短寻找时间优先调度算法总是从等待者中挑选寻找时间最短的那个请求先执行的，而不管者到来的先后次序。现在仍利用同一个例子来讨论，现在当50号柱面的操作完毕后，应该先处理61号柱面的请求，然后到达32号柱面执行操作，随后处理15号柱面请求，后继操作的次序应该是99、130、148、159、199。采用最短寻找时间优先算法决定等待者执行操作的次序时，读写磁头总共移动了200多个柱面的距离，与先来先效劳、算法比拟，大幅度地减少了寻找时间，因而缩短了为各者请求效劳的平均时间，也就提高了系统效率。但最短查找时间优先〔SSTF〕调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短〔也就是查找时间最短〕的请求作为下一次效劳的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的效劳，甚至引起无限拖延〔又称饥饿〕。SCAN算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。"电梯调度〞算法是从移动臂当前位置开场沿着臂的移动方向去选择离当前移动臂最近的那个柱者，如果沿臂的移动方向无请求时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。但是，"电梯调度〞算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。2、概要设计2.1设计方法通过C语言的编程，设计程序模拟先来先效劳FCFS，最短寻道时间优先SSTF，和扫描SCAN算法的工作过程。假设有n个磁道号所组成的磁道序列，给定开场磁道号m和磁头移动的方向〔正向或者反向〕，分别利用不同的磁盘调度算法磁道序列，给出磁头每一次移动的过程，算出磁头移动的距离，继而计算每种算法的平均寻道长度。2.2技术C语言、操作系统磁盘调度算法、C++。2.3运行环境Window10、VC++6.0。3、详细设计3.1流程图先来先效劳算法〔FCFS〕：完毕Avg=sum/(m)j<m目前的位置变为当前的位置j++输出磁盘调度序列array[j]磁头移动总距离Sum+=abs(array[j]-array[i])磁头移动距离Sum=abs(now-array[0])输入当前磁道号now开场完毕Avg=sum/(m)j<m目前的位置变为当前的位置j++输出磁盘调度序列array[j]磁头移动总距离Sum+=abs(array[j]-array[i])磁头移动距离Sum=abs(now-array[0])输入当前磁道号now开场最短寻道时间优先算法(SSTF)：开场开场完毕完毕扫描SCAN算法：开场开场完毕完毕3.2程序主要代码先来先效劳算法〔FCFS〕：voidFCFS(vector<int>m_vec,intposition){//先来先效劳算法dis=0;average_distance=0;for(vector<int>::iteratorit=m_vec.begin();it!=m_vec.end();it++){dis+=abs(position-*it);Sleep(500);cout<<"->"<<*it;position=*it;}pute_dis(m_vec,dis,average_distance);}最短寻道时间优先算法(SSTF)：voidSSTF(vector<int>m_vec,intposition){//最短寻道时间算法dis=0;average_distance=0;sort(m_vec.begin(),m_vec.end());//从小到大排序inti=0;for(vector<int>::iteratorit=m_vec.begin();it!=m_vec.end();it++){if(position>=*it)i++;}intcount=0;intleft=i-1;intright=i;while(count<m_vec.size()){if((left>=0&&abs(m_vec[right]-position)>abs(m_vec[left]-position))||right>=m_vec.size()){dis+=abs(m_vec[left]-position);Sleep(500);cout<<"->"<<m_vec[left];position=m_vec[left];left--;}else{dis+=abs(m_vec[right]-position);Sleep(500);cout<<"->"<<m_vec[right];position=m_vec[right];right++;}count++;}pute_dis(m_vec,dis,average_distance);}扫描SCAN算法：voidSCAN(vector<int>m_vec,intposition){//电梯调度算法dis=0;average_distance=0;sort(m_vec.begin(),m_vec.end());//从小到大排序inti=0;for(vector<int>::iteratorit=m_vec.begin();it!=m_vec.end();it++){if(position>=*it)i++;//找到position所在的磁道}intleft=i-1;//先从外到内扫描intright=i;while(left>=0){dis+=abs(position-m_vec[left]);Sleep(500);cout<<"->"<<m_vec[left];position=m_vec[left];left--;}while(right<m_vec.size()){dis+=abs(position-m_vec[right]);Sleep(500);cout<<"->"<<m_vec[right];position=m_vec[right];right++;}pute_dis(m_vec,dis,average_distance);}4、运行结果及分析4.1运行结果先来先效劳算法〔FCFS〕：最短寻道时间优先算法(SSTF)：扫描SCAN算法：4.2结果详细分析FCFS：这是一种比拟简单的磁盘调度算法。它根据进程请求磁盘的先后次序进展调度。此算法由于未对寻道进展优化，在对磁盘的请求比拟多的情况下，此算法将降低设备效劳的吞吐量，致使平均寻道时间可能较长，但各进程得到效劳的响应时间的变化幅度较小。SSTF：该算法选择这样的进程，其要求的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比拟好的吞吐量，但却不能保证平均寻道时间最短。SCAN：扫描算法不仅考虑到欲的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。此算法根本上克制了最短寻道时间优先算法的效劳集中于中间磁道和响应时间变化比拟大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被的频率仍低于中间磁道。5、总结和心得通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的根本知识学好而且还要不断进展实践，将所学的跟实践操作结合起来才能更好地稳固所学，才能提高自己实践能力。通过这次的设计使我认识到只停留在外表理解问题是很难使问题得到很好的解决的，实践能力与理论知识同样重要。可以说此课程设计的理论难度并不大，各种流图设计特别是算法过程图的设计很容易忽略操作性细节，在实际调试中带来很大麻烦，需要特别注意，但是假设要深入开掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。通过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解模拟磁盘调度算法，实现各种不同调度算法的过程，并计算各算法的平均寻道长度，以便于我们判断各种算法的优劣以及各种算法使用的场合。6、参考文献[1].汤子瀛，哲凤屏，汤小丹."计算机操作系统".**电子科技大学,2005;[2].谭浩强编著."C语言程序设计〔第3版〕".清华大学，2005;[3].吴乃陵，况迎辉."C++程序设计〔第二版〕".高等教育，2005。7、附录：程序源代码FCFS：#include<iostream>#include<time.h>#include<vector>#include<algorithm>#include<math.h>#include<stdlib.h>#include<cstring>#include<windows.h>#include<fstream>usingnamespacestd;intposition=0;//当前磁道位置intdis=0;doubleaverage_distance=0;voidrequest(vector<int>&m_vec,ofstream&outfile){cout<<"随机生成磁盘序列："<<endl;intn=0;srand(time(NULL));//添加随机数种子n=rand()%20+1;inttemp=0;for(inti=0;i<n;i++){temp=rand()%100;m_vec.push_back(temp);cout<<temp<<"";outfile<<temp<<endl;}cout<<endl;position=rand()%100;cout<<"当前磁道："<<position<<endl;}voidpute_dis(vector<int>m_vec,int&dis,double&average_distance){average_distance=(double)dis/(double)m_vec.size();}voidFCFS(vector<int>m_vec,intposition){//先来先效劳算法dis=0;average_distance=0;for(vector<int>::iteratorit=m_vec.begin();it!=m_vec.end();it++){dis+=abs(position-*it);Sleep(500);cout<<"->"<<*it;position=*it;}pute_dis(m_vec,dis,average_distance);}voidprint(){cout<<endl<<endl;cout<<"经计算，磁头移动的总距离为:"<<dis<<endl;cout<<"磁头平均移动距离:"<<average_distance<<endl;cout<<endl<<endl;}intmain(){ ofstreamoutfile;outfile.open("data.t*t");vector<int>m_vec;request(m_vec,outfile);//请求效劳序列cout<<"磁盘请求的效劳状况："<<endl;FCFS(m_vec,position); print(); outfile.close();return0;}SSTF:#include<iostream>#include<time.h>#include<vector>#include<math.h>#include<stdlib.h>#include<algorithm>#include<cstring>#include<windows.h>#include<fstream>usingnamespacestd;intposition=0;//当前磁道位置intdis=0;doubleaverage_distance=0;voidrequest(vector<int>&m_vec,ofstream&outfile){cout<<"随机生成磁盘序列："<<endl;intn=0;srand(time(NULL));//添加随机数种子n=rand()%20+1;inttemp=0;for(inti=0;i<n;i++){temp=rand()%100;m_vec.push_back(temp);cout<<temp<<"";outfile<<temp<<endl;}cout<<endl;position=rand()%100;cout<<"当前磁道："<<position<<endl;}voidpute_dis(vector<int>m_vec,int&dis,double&average_distance){average_distance=(double)dis/(double)m_vec.size();}voidSSTF(vector<int>m_vec,intposition){//最短寻道时间算法dis=0;average_distance=0;sort(m_vec.begin(),m_vec.end());//从小到大排序inti=0;for(vector<int>::iteratorit=m_vec.begin();it!=m_vec.end();it++){if(position>=*it)i++;}intcount=0;intleft=i-1;intright=i;while(count<m_vec.size()){if((left>=0&&abs(m_vec[right]-position)>abs(m_vec[left]-position))||right>=m_vec.size()){dis+=abs(m_vec[left]-position);Sleep(500);cout<<"->"<<m_vec[left];position=m_vec[left];left--;}else{dis+=abs(m_vec[right]-position);Sleep(500);cout<<"->"<<m_vec[right];position=m_vec[right];right++;}count++;}pute_dis(m_vec,dis,average_distance);}voidprint(){cout<<endl<<endl;cout<<"经计算，磁头移动的总距离为:"<<dis<<endl;cout<<"磁头平均移动距离:"<<average_distance<<endl;cout<<endl<<endl;}intmain(){ofstreamoutfile;outfile.open("data.t*t");vector<int>m_vec;request(m_vec,outfile);//请求效劳序列cout<<"磁盘请求的效劳状况："<<endl;SSTF(m_vec,position); print(); outfile.close();return0;}SCAN:#include<iostream>#include<time.h>#include<vector>#include<math.h>#include<stdlib.h>#include<algorithm>#include<cstring>#include<windows.h>#include<fstream>usingnamespacestd;intposition=0;//当前磁道位置intdis=0;doubleaverage_distance=0;voidrequest(vector<int>&m_vec,ofstream&outfile){cout<<"随机生成磁盘序列："<<endl;intn=0;srand(time(NULL));//添加随机数种子n=rand()%20+1;inttemp=0;for(inti=0;i<n;i++){temp=rand()%100;m_vec.push_back(temp);cout<<temp<<"";outfile<<temp<<endl;}cout<<endl;position=rand()%100;cout<<"当前磁道："<<position<<endl;}voidpute_dis(vector<int>m_vec,int&dis,double&average_distance){average_distance=(double)dis/(double)m_vec.size();}void