操作系统课程设计任务书题目: 磁盘调度算法院系:专业:班级:姓名:学号:指导教师:设计时间：2018.1.1-2018.1.5指导教师评语目录1、需求分析ﻩ41．１课题描述 (4)１．2课题目的 (4)1．3理论依据ﻩ72、概要设计ﻩ82.1设计方法 ............................................................................................... ８２.2技术ﻩ8２.3运行环境ﻩ83、详细设计ﻩ93.１流程图 (11)3.２程序主要代码ﻩ1314４、运行结果及分析ﻩ４.1运行结果ﻩ15４.2结果详细分析ﻩ6１165、总结和心得ﻩ７16、参考文献ﻩ27、附录：程序源代码ﻩ３１、需求分析1.1课题描述这次课程设计我研究的题目是:磁盘调度算法。
具体包括三种算法分别是:先来先服务算法（ＦCFS)、最短寻道时间优先算法(ＳＳＴF)、扫描算法（电梯调度算法)(SCAN）。
1.2课题目的通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务ＦＣＦS,最短寻道时间优先SSＴF,扫描ＳCＡN算法的实现方法。
１.3理论依据设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。
常用的分配策略有先请求先分配、优先级高者先分配等策略。
在多道程序系统中,低效率通常是由于磁盘类旋转设备使用不当造成的。
操作系统中，对磁盘的访问要求来自多方面，常常需要排队。
这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。
访问磁盘的时间因子由3部分构成，它们是查找（查找磁道)时间、等待（旋转等待扇区)时间和数据传输时间,其中查找时间是决定因素。
因此，磁盘调度算法先考虑优化查找策略,需要时再优化旋转等待策略。
平均寻道长度（L)为所有磁道所需移动距离之和除以总的所需访问的磁道数(N），即：L=(M1+Ｍ２+……+Mi＋……+MN)/N其中Mi为所需访问的磁道号所需移动的磁道数。
启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面,再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写,完成信息传送。
因此,执行一次输入输出所花的时间有：寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。
延迟时间——指定扇区旋转到磁头下所需的时间。
传送时间——由磁头进程读写完成信息传送的时间。
其中传送信息所花的时间，是在硬件设计就固定的。
而寻找时间和延迟时间是与信息在磁盘上的位置有关。
为了减少移动臂进行移动花费的时间,每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。
而是按柱面存放,同一柱面上的各磁道被放满信息后，再放到下一个柱面上。
所以各磁盘的编号按柱面顺序,每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。
磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘是,应采用一种最佳调度算法,以使各种进程对磁盘的平均访问时间最小。
由于在访问磁盘的时间中，主要是寻道时间,因此，磁盘调度的目标,是使磁盘的平均寻道时间最少。
目前常用的磁盘帝调度算法有:先来先服务、最短寻道时间优先及扫描等算法。
先来先服务（FＣFS）调度:按先来后到次序服务，未作优化。
最简单的移臂调度算法是“先来先服务”调度算法,这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。
例如,如果现在读写磁头正在5０号柱面上执行输出操作,而等待访问者依次要访问的柱面为１30、19９、32、1５９、15、148、６1、9９,那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面,最后到达99号柱面。
采用先来先服务算法决定等待访问者执行输入输出操作的次序时,移动臂来回地移动。
先来先服务算法花费的寻找时间较长,所以执行输入输出操作的总时间也很长。
最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的,而不管访问者到来的先后次序。
现在仍利用同一个例子来讨论，现在当50号柱面的操作结束后，应该先处理61号柱面的请求,然后到达３２号柱面执行操作,随后处理１5号柱面请求,后继操作的次序应该是99、130、１48、159、19９。
采用最短寻找时间优先算法决定等待访问者执行操作的次序时,读写磁头总共移动了200多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间,因而缩短了为各访问者请求服务的平均时间,也就提高了系统效率。
但最短查找时间优先（SSＴＦ）调度，ＦCFS会引起读写头在盘面上的大范围移动，ＳＳTF查找距离磁头最短(也就是查找时间最短)的请求作为下一次服务的对象。
SSＴF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿)。
SCAN 算法又称电梯调度算法。
SCＡN算法是磁头前进方向上的最短查找时间优先算法,它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性,但仍有利于对中间磁道的请求。
“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。
这好比乘电梯,如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。
他们的要求是:陈生在2层等待去10层;伍生在5层等待去底层;张生在8层等待1５层。
由于电梯目前运动方向是向上,所以电梯的形成是先把乘客张生从8层带到15层,然后电梯换成下行方向，把乘客伍生从5层带到底层,电梯最后再调换方向，把乘客陈生从２层送到1０层。
但是,“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置,还必须记住移动臂的当前前进方向。
2、概要设计2.1设计方法通过C语言的编程，设计程序模拟先来先服务ＦCＦS，最短寻道时间优先SSＴF，和扫描SCAN算法的工作过程。
假设有ｎ个磁道号所组成的磁道访问序列,给定开始磁道号m和磁头移动的方向(正向或者反向）,分别利用不同的磁盘调度算法访问磁道序列，给出磁头每一次移动的过程,算出磁头移动的距离,继而计算每种算法的平均寻道长度。
２.２技术C语言、操作系统磁盘调度算法、C＋+。
2.３运行环境Winｄｏw10、ＶC+＋6.0。
3、详细设计3.1流程图先来先服务算法（FCFＳ）：最短寻道时间优先算法（SSＴF)：开始结束扫描SCＡN算法:开始结束３.2程序主要代码先来先服务算法(FＣＦS)：void FCFS（vecｔor＜ｉnｔ>ｍ_ｖec,ｉnt positｉｏn）{ //先来先服务算法dis ＝０;ａveｒａge_distａｎce= 0;for(vecｔoｒ<int>：：iterator it=m＿veｃ.bｅｇｉn();ｉt！=m_vｅｃ.end(）;i ｔ+＋){diｓ+=ａｂｓ(pｏsｉtiｏn-*ｉｔ);Slｅｅp(500);cout<<＂->"<<*ｉt;pｏｓｉｔｉｏｎ= *it;｝compute＿ｄis（m_ｖec,ｄiｓ,averagｅ_ｄｉｓｔance);}最短寻道时间优先算法(ＳSTF):void SSTF（ｖeｃtｏｒ<ｉnt＞m＿veｃ,ｉnt positｉｏn){ ／/最短寻道时间算法ｄiｓ= 0;ａverａｇｅ_distance= 0；sort(ｍ＿vec.ｂｅgｉn（),m＿vec．ｅnｄ（）); //从小到大排序int i = 0;for（veｃtor<iｎt>:：iterator it=m＿ｖeｃ.bｅgin();iｔ!=m_vec.end(）；ｉt＋＋){if（poｓition >＝*it)i++;}intｃｏunｔ=０；int left =ｉ-1;iｎt riｇht =i;ｗhile(count<m＿vec.sｉze(）)｛ｉf(（left>=0 ＆& ａbｓ(m_ｖec［ｒiｇht]-position)> abs(m_ｖec[ｌｅft]-poｓｉtiｏn）) ||right＞=m_vｅc.sｉｚｅ(）){diｓ+＝abs(ｍ＿vec[ｌeｆt]-position）；Ｓleep(50０）;coｕt<＜＂－＞"＜<m_vｅc[left］;pｏsition=m_vec［left]；left--;}eｌsｅ｛diｓ+= abs(m＿veｃ[right]-ｐositiｏn);Sｌeep（５０0）;coｕt<<"->"＜<m_vec［rｉght]；poｓｉtioｎ= m_ｖec［riｇｈt];ｒight++;}cｏuｎt+＋；}ｃoｍpｕte_diｓ(m_ｖｅc,dis,aｖeｒage_disｔance);}扫描ＳCＡＮ算法：voiｄSCＡN（vector<ｉnt>m_veｃ，int poｓｉtion）{／/电梯调度算法dis= 0;ａveragｅ_diｓｔance = 0;sort（m_vec．begin(）,m_ｖec.end(）);//从小到大排序int i = 0;for(vector<int>：:itｅratｏｒit=m_vｅc.begin();it!＝m_vec.eｎd();it+＋){if（ｐositioｎ>= *it)i+＋; //找到ｐosｉtiｏn所在的磁道}inｔlｅft= i - 1；//先从外到内扫描inｔｒｉght = i;ｗhile（left ＞= 0){ｄis ＋＝abs（ｐosｉｔiｏn- m_veｃ[left]）;Sleep(50０);coｕt＜<＂->＂<<m_vec[lｅft]；ｐoｓiｔiｏｎ= m_vec［lｅft];lefｔ--;｝wｈile(rigｈt < m_vｅｃ．sｉｚe(）){dis +=aｂs(posｉtion- m_veｃ[right］）;Ｓｌｅeｐ（５00);cout＜<"->"<<m＿vec[ｒiｇhｔ];posiｔｉon ＝m_vec[right]；riｇht ++；｝ｃompute_dｉs（m_ｖeｃ,dis,averaｇe_ｄisｔａnce);}4、运行结果及分析４．1运行结果先来先服务算法（FCＦS）：最短寻道时间优先算法(SSTF）:扫描ＳＣＡＮ算法:4.2结果详细分析FCＦS ：这是一种比较简单的磁盘调度算法。
它根据进程请求访问磁盘的先后次序进行调度。
此算法由于未对寻道进行优化,在对磁盘的访问请求比较多的情况下,此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长,但各进程得到服务的响应时间的变化幅度较小。