操作系统磁盘调度算法

《操作系统磁盘调度算法》由会员分享，可在线阅读，更多相关《操作系统磁盘调度算法（24页珍藏版）》请在装配图网上搜索。

1、操作系统课程设计任务书题 目：磁盘调度算法院系：专业：班级：姓名：学号：指导教师：设计时间：2018.1.1-201815指 导 教 师 评 语目录1、需求分析a11课题描述412课题目的41. 3理论依据7。2、概要设计8。21设计方法82 .2技术&2 .3运行环境8。3、详细设计9。31流程图113.2程序主要代码13。4、运行结果及分析14。4 .1运行结果15。4 .2 结果详细分析16。5、总结和心得16。6、参考文献17。7、附录：程序源代码23。1、需求分析1.1 课题描述这次课程设计我研究的题目是:磁盘调度算法。具体包括三种算法分别是:先来先服务算法（FCFS）、最短寻道时间

2、优先算 法（SSTF）、扫描算法（电梯调度算法）（SCAN）。1.2 课题目的通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS,最短寻道时间优先SSTF,扫描SCAN算法 的实现方法。1.3 理论依据设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中,低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问 磁盘的时间因子由 3 部分构成，它们是查找（查找磁道）时

3、间、 等待（旋转等待扇区）时间和数据传输时间,其中查找时间是决 定因素。因此，磁盘调度算法先考虑优化查找策略,需要时再优 化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数(N),即：L=(Ml+M2+Mi+,+MN)/N其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱 面,再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进 行读写,完成信息传送。因此,执行一次输入输出所花的时间有：寻找时间磁头在移动臂带动下移动到指定柱面所花的时 间。 延迟时间指定扇区旋转到磁头下所需的时间。 传送 时间由磁头进程读写完成信息

4、传送的时间。 其中传送信息所花的时间，是在硬件设计就固定的。而寻找时 间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂 进行移动花费的时间,每个文件的信息不是按盘面上的磁道顺 序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放, 同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所 以各磁盘的编号按柱面顺序,每个柱面按磁道顺序，每个磁道又 按扇区顺序进行排序。磁盘是可供多个进程共享的设备，当有多个进程都要求访问 磁盘是,应采用一种最佳调度算法,以使各种进程对磁盘的平均 访问时间最小。由于在访问磁盘的时间中，主要是寻道时间 , 因此，磁盘调度的目标,是使磁盘的平均寻道时间最少。目前常

5、 用的磁盘帝调度算法有:先来先服务、最短寻道时间优先及扫描 等算法。先来先服务（FCFS）调度:按先来后到次序服务，未作优化。最简单的移臂调度算法是“先来先服务”调度算法,这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在5 0号 柱面上执行输出操作，而等待访问者依次要访问的柱面为1 30、19 9、32、15 9、15、148、6 1、99,那么，当 50 号柱面上 的操作结束后，移动臂将按请求的先后次序先移到130 号柱面， 最后到达 99 号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次 序时，移动臂来回地移动。先

6、来先服务算法花费的寻找时间较长， 所以执行输入输出操作的总时间也很长。最短寻找时间优先调度算法总是从等待访问者中挑选寻找时 间最短的那个请求先执行的，而不管访问者到来的先后次序。现 在仍利用同一个例子来讨论，现在当 50 号柱面的操作结束后， 应该先处理61号柱面的请求，然后到达3 2号柱面执行操作， 随后处理15 号柱面请求，后继操作的次序应该是 99、130、1 48、159、199。采用最短寻找时间优先算法决定等待访问者执行操作的次序 时，读写磁头总共移动了200多个柱面的距离，与先来先服务、 算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请 求服务的平均时间，也就提高了系统效率

7、。但最短查找时间优先（SSTF ）调度，FCFS会引起读写头 在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查 找时间最短）的请求作为下一次服务的对象。SSTF查找模式有 高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖 延（又称饥饿）。SCAN算法又称电梯调度算法。SCAN算法是磁头前进方向上 的最短查找时间优先算法 ,它排除了磁头在盘面局部位置上的 往复移动，SCAN算法在很大程度上消除了 SSTF算法的不公平 性,但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方 向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动 方向无请求访问时，就改变

8、臂的移动方向再选择。这好比乘电 梯,如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、 张生在等候乘电梯。他们的要求是:陈生在 2 层等待去 10 层; 伍生在5层等待去底层;张生在8层等待15层。由于电梯目前 运动方向是向上,所以电梯的形成是先把乘客张生从 8 层带到 15 层,然后电梯换成下行方向，把乘客伍生从5层带到底层,电 梯最后再调换方向，把乘客陈生从2层送到10层。但是,“电梯调度”算法在实现时，不仅要记住读写磁头的当 前位置,还必须记住移动臂的当前前进方向。2、概要设计2.1 设计方法通过C语言的编程，设计程序模拟先来先服务FCFS,最短寻道 时间优先SSTF,和扫描SCAN

9、算法的工作过程。假设有n个磁道号 所组成的磁道访问序列,给定开始磁道号 m 和磁头移动的方向（正向 或者反向）,分别利用不同的磁盘调度算法访问磁道序列，给出磁头 每一次移动的过程,算出磁头移动的距离,继而计算每种算法的平均 寻道长度。2. 2技术C语言、操作系统磁盘调度算法、C+。2. 3运行环境Windowl0、VC+6.0。3、详细设计3.1流程图先来先服务算法（FCFS）：最短寻道时间优先算法（SSTF）：开始array m-SarrayOnciw-arfzypp结束邑慚h卞士劫扎当费鑑這号血。科国度，宇刮记叢序列列 array先为猛道寻迂、再向鑑追号诫小方向捕曲猛盘说盍字謝肘确盘调蛊字

10、列 arraytj=報的乜宣娈为 当希的位宜 n.ov!-arMyt先勻确這亏战小方方诂7.再向猛道目驹的总畳雯为当俞 的世宣 n ewauay i哺走当驹磁這左E 拝的呼列宇的也宝镒头誉幼总匣离EumLOTv-airavril隐头尊甜息医芻 sum=no xr-arravril诲恣這号从小到大拝序扫描SCAN算法:3.2程序主要代码先来先服务算法(FCFS)：/先来先服务算法void FCFS (vec t or Vi n t m_ v ec, i nt posit io n) dis =0 ;a ve ra ge_dist an ce = 0;for(vec tor ：: iterator

11、 it=m_ve c .b egi n(); i t! =m_v ec .end() ;i t +)di s += abs (p o s i ti o n-* it );Slee p(500); cout*i t; position = *it;compute_dis (m_ v ec, d i s ,averag e _ dis t ance);最短寻道时间优先算法(SSTF):void SSTF (vectorm_ve c , i nt posit io n)/ / 最短寻道时间算法d is = 0;a ver age distance = 0；sort(m_vec. begin (),m

12、_vec.e n d();从小到大排序int i = 0;for (ve c tor: iterator it=m_ vec.be gin();i t !=m_vec.end()； i t+ )if (po s ition = *it)i+;int co unt = 0；int left = i -1;in t rig ht = i;w hile(countvm_vec.s i ze() ) i f( (left =0 & abs (m_ v ec rig ht-position) abs(m_ v ec 1 e ft-po si ti o n) ) II right=m_v e c.s iz

13、e () )di s += abs(m_vec 1 e f t-position)；Sleep(500) ;co u tvVVvm_v e cleft;po sition = m_vec left；left-;e1 sedi s+= abs(m_ve c right- p ositi o n);S 1 eep ( 5 0 0);cou tV= *it)i+ ；/找到pos i tOn所在的磁道int left = i -；1 /先从外到内扫描intright = i;while(lef t= 0)dis + = abs (pos ition - m_vec left;Sleep(5G0 );c

14、outv” -m_vecleft position= m_vec left;left -;w hile(rit m_vec. size) ) dis += abs(posi tion - m_vec right)；Sleep( 5 00); coutv-m _vec r ight;position= m_vecright；right +；c ompute_d i s (m_ vec , dis,avegrae_dist ance) ;4、运行结果及分析41运行结果先来先服务算法(FCFS)： 1ugFCFS.exeX腕机丄咸;昭血庁歹， sr：_ pn r sn 厅 自團驚杲諒霸疣兄： -?(

15、=c：-?L：b-t.-?bU-? 1L：综引耳，陛丄榕塾的怕陆咼力：1皿 恣买T匀茯冬jMj医？ 37. Zress any k ey cent! mie最短寻道时间优先算法(SSTF):”F:灣作辜统口甜:93头移堑的总距奩対：89 动距禽：5. 33333扫描SCAN算法:x*F:费作垂绽心ebug匹CAMup|xex&龍机生成磁盘序列:79J.6 62 73 35 18 28 27 53 91 20 34 51詛離濾务状况:-91-79- 73-2-53- 51 - 35-34-2 8-2 8-2 7-18-16resE any bey t口 g unti mie4.2 结果详细分析F

16、CFS :这是一种比较简单的磁盘调度算法。它根据进程请求访 问磁盘的先后次序进行调度。此算法由于未对寻道进行优化, 在对磁盘的访问请求比较多的情况下 ,此算法将降低设备服 务的吞吐量，致使平均寻道时间可能较长 ,但各进程得到服 务的响应时间的变化幅度较小。SSTF：该算法选择这样的进程,其要求访问的磁道与当前磁头 所在的磁道距离最近，以使每次的寻道时间最短，该算法可 以得到比较好的吞吐量，但却不能保证平均寻道时间最短。SCAN ：扫描算法不仅考虑到欲访问的磁道与当前磁道的距离， 更优先考虑的是磁头的当前移动方向。此算法基本上克服了 最短寻道时间优先算法的服务集中于中间磁道和响应时间 变化比较大

17、的缺点，而具有最短寻道时间优先算法的优点即 吞吐量较大，平均响应时间较小,但由于是摆动式的扫描方 法，两侧磁道被访问的频率仍低于中间磁道。5、总结和心得通过这次的课程设计使我认识到要将操作系统这门计 算机专业的课学好不仅仅是要把书上的基本知识学好而且还要 不断进行实践,将所学的跟实践操作结合起来才能更好地巩固 所学,才能提高自己实践能力。通过这次的设计使我认识到只停 留在表面理解问题是很难使问题得到很好的解决的，实践能力 与理论知识同样重要。可以说此课程设计的理论难度并不大， 各种流图设计特别是算法过程图的设计很容易忽略操作性细节, 在实际调试中带来很大麻烦,需要特别注意，但是若要深入发掘 其

18、中的东西，并且实际去编程实现，就遇到了相当大的难度。 因为与之涉及的很多方面并没有学过 ,需要自己去自学和实践 检验。通过模拟磁盘调度及进程排队算法来加深对操作系统中 各个磁臂调度算法概念的理解模拟磁盘调度算法 ,实现各种不 同调度算法的过程，并计算各算法的平均寻道长度，以便于我 们判断各种算法的优劣以及各种算法使用的场合。6、参考文献1 .汤子瀛,哲凤屏,汤小丹. 计算机操作系统西安电子 科技大学出版社，20 0 5；2 .谭浩强编著.C语言程序设计（第3版）.清华大学出 版社，2005;3 .吴乃陵，况迎辉.C+程序设计（第二版）.高等教育 出版社，2 005。7、附录:程序源代码FCFS

19、:#i n c lu d e #inc 1 u d e vtime . h # i n clud e # includ e valgo rit hm#in elude #inc 1 ude v s td 1 ib. h #i n elude v c st r ing#inc 1 ude #include vfstrea musi ng na mes pace st d;int posit i on =0;当前磁道位置i n t dis = 0 ;do u ble a v erage_di s t an ce = 0;void r eque s t(vecto r &m_vec,o f stre

20、am &outfile)co u t 随机生成磁盘序列:vvendl;i nt n = 0 ;s r and (time(NUL L);添加随机数种子n = r a n d() %20 + 1；int t emp = 0;f or (i nt i=0;iv n； i+) temp = rand ()%1 00;m_ v e c. push_b a ck(tem p);cou tvvt emp v;out fi1 evt empve nd1 ;co ut ve ndl;po sitio n = rand () % 100;coutvv当前磁道:vvpos i tionvven d l;1 e &

21、 a v erag e _dist a/先来先服务算法vec .end ();it)void c o mpu t e_ d is(vecto rm_ve c ,i nt &d is,dou b nce) av erage_distance = (double)dis (doub le )m_vec.size(); v o id F CFS(vectorm_v ec ,i n t posi ti on) dis =0；a verage _di stance = 0 ;for(vectorvi nt :ite rator it=m_v ec.begin ();i t !=m_ di s += ab

22、s( pos it ion-*it)；SI eep(500);c ou tvv-vv*i t ； p o s it ion = *it;c ompu t e_dis(m_vec,dis,av e r ag e_di s tan c e);voi d p ri nt() cou t vve n d 1 m_ v ec;r equ e st(m_v e c, o ut f ile)；请求服务序列c ou tVv磁盘请求的服务状况：vvend 1 ;FCFS(m _vec， position);P r i nt ()；ou t();ret urn 0;SSTF:#include V iost rea

23、m #inc1 ude Vtim e.h #include vvect or #include vma th .h# i ncl ud e v st dli b .h#i ncludeva lg orithm#i nc lude V cst ring#i nc l u de vwindows.h #include vfstream usi ng name spac e std ;int position = 0；/当前磁道位置in t dis = 0;doub1 e averag e_d is tan ce = 0;v oid request(vectorVi ntm_vec,ofstream

24、 &o utfile)coutvv随机生成磁盘序列:vVen d l;i nt n = 0;s r an d (time(NULL) );/ /添加随机数种子n = r a nd()%20 + 1；int temp = 0;for (int i=0;ivn;i+) temp = r a nd()%100；m_vec.push_ back (temp);c o utVvt emp；ou t fil e wtempw e nd 1 ;c outvve n dl;pos i tion = ra nd () % 10 0;coutvv当前磁道:m_ ve c,in t &d is ,do u ble

25、& a v er a ge_d i s t ance) avera g e_d i stan c e =(dou b le) dis / (double) m_vec. size ();vo i d SSTF( v ectorvin t m_vec,int pos ition)/ 最短寻道时间算法d i s = 0;ave ra ge_d is t a n ce = 0;so rt (m_vec. beg in () ,m_ve c.en d()；/从小到大排序int i = 0； for(vec torvin t:ite rator it=m_vec.begi n();it !=m_vec

26、.end ();it+) if(p osi tion = *it)i+；int coun t = 0；in t left = i1;int ri ght = i； whi le(co un t=0& ab s(m_vecr ightposition) abs(m_v ecleft-p ositio n) ) II right=m_v e c.size() dis = abs(m_vec le ftposi tion ); Slee p(500);c ou tvv-vvm_vecleft;pos ition = m_vecle f t;le ft-；elsedis += a bs (m_vecr

27、igh t-posi tio n)；Sleep(5 00);co u tVv-vvm_vecrig h t; po s ition = m_ve c ri g h t ;ri gh t+；c o u nt +；com pu te_dis(m_v e c,d is,a verage_d ista nee);void pri nt ()coutendlendl；coutvV经计算，磁头移动的总距离为:vVdisvv e ndl; coutvV磁头平均移动距离:VVave r age_d i stanceVe n dl; co ute nd lendl;in t main() of s t r ea

28、m outf i l e ;out (da ta.txt)；v ectorm_vec ;request (m_vec,ou tf il e );请求服务序列co u tVin clu de vtim e.h#i nc lude vvector # i n cl ude vmath.hi nclud e vstd libhinc ludevalgo rithm#include vcstrin g#i n clude vwindo ws.h#in clude vfstreamusing n am esp ace st d;int p o s ition =0 ;当前磁道位置int dis = 0；

29、double a ve ra ge_distan c e = 0;v oid request( v ectorVi nt&m_ve c ,o f st r e am &o utf ile) coutvV随机生成磁盘序列：vvendl;i nt n = 0;srand (time(NULL) )；/添加随机数种子n = ra nd () % 20 + 1;i nt tem p = 0;fo r ( i nt i=0;ivn;i+) tem p = ran d()%1 0 0;m_v ec .pu s h_b a ck( t emp);coutvvt e mpVv ;o u tf il e wte

30、mpwendl;cou tV ve ndl;p o siti o n = ran d()%1 00;c o u t 当前磁道:Vvpos i tio n m_ v ec, in t &dis,d o ubl e &ave r age_dista n ce) aver a ge_ di s t ance = (double) di s /(double) m_vec.si z e();vo i d SC AN(v e c to rm_vec,int p osition)/ / 电梯调度算法dis = 0；a v era g e_distan c e =0 ;s o rt(m_vec.be gi

31、n(), m_vec. e nd()；从小到大排序int i = 0;f or(vecto rvin t:it erator it=m_vecbeg in() ;it！=m_vec .e nd() ;i t+)if(po sition =*it)i ntintwhilei+;/找到pos ition所在的磁道le ft = i -1;ri ght = i;( left = 0)/先从外到内扫描dis += abs (posit i o n - m_ v ec lef t); Sleep(500);co utvV-vvm_vecleft;p ositi o n = m_vec left;1 ef

32、t ；while (right vvm_vec ri gh t； positio n = m_v ec right； right +;c omp u te_d i s(m_v e c,di s, ave r ag e _ d ist a nee)； vo i d prin t() cou t vve n dlVv e n d l;coutvv 经计算，磁头移动的总距离为:di s Vendl;coutvv 磁头平均移动距离:Vvaver ag e_ di stanceVVe ndl; co ut vvend 1 m_vec;r equest (m_vec, out file);请求服务序列co u tvv磁盘请求的服务状况：vVendl；SC AN(m_v e c,po s ition);print ();out(); re tur n 0;