《操作系统原理》课程设计报告.doc

操作系统原理课程设计报告专 业 网络工程_ _ 班 级 网络12-1 _ _ _ 学 号 12034460134 _ 姓 名 _ _ 指导教师 _ _ 完成时间 2014.12.30 _ _ 成 绩 _ _ _ 题目六 模拟磁盘调度一、实验目的及内容1模拟一个磁盘调度算法；2要求能够模拟FCFS、最短寻道时间、电梯算法三个磁盘调度算法；3输入为一组作业的磁道请求；4输出为按选择的算法执行时的磁头移动轨迹。二、算法设计思想磁盘调度主要思想设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+Mi+MN）/N其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：寻找时间磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间指定扇区旋转到磁头下所需的时间。传送时间由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序（从0号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘是，应采用一种最佳调度算法，以使各种进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标，是使磁盘的平均寻道时间最少。目前常用的磁盘帝调度算法有：先来先服务、最短寻道时间优先及扫描等算法。三、主要算法分析各个算法分析 1.先来先服务算法（FCFS）最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。2.最短寻道时间优先算法（SSTF）最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当50号柱面的操作结束后，应该先处理61号柱面的请求，然后到达32号柱面执行操作，随后处理15号柱面请求，后继操作的次序应该是99、130、148、159、199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。3.扫描算法（SCAN）SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。4.实验过程与结果（1）FCFS算法（测试数据来自课本）（2）SSTF算法(3)SCAN算法5.源代码清单#include#includeusing namespace std;void fcfs(int ,int ,int );void sstf(int ,int ,int );void scan(int ,int ,int );int seekmin(int ,int ,int );void SelectSore(int ,int );int main()while(true)int trackCount,head,track20;couthead;couttrackCount;cout请依次输入访问磁道号数:;for(int i=0;itracki;cout-endl;cout-按1选择先来先服务FCFS算法-endl;cout-按2选择最短寻道时间优先SSTF算法-endl;cout-按3选择扫描SCAN算法-endl;cout-x;switch(x)case 1: fcfs(head,trackCount,track);break;case 2: sstf(head,trackCount,track);break;case 3: scan(head,trackCount,track);break;default: cout输入有误;/fcfs(head,trackCount,track);/sstf(head,trackCount,track);/scan(head,trackCount,track);void fcfs(int head,int trackCount,int track)int seektime20=0;int TotalSize=0;seektime0=abs(track0-head);for(int i=1;itrackCount;i+)seektimei=abs(tracki-1-tracki);for(int j=0;jtrackCount;j+)TotalSize+=seektimej;cout磁头访问的磁道序列为:;for(i=0;itrackCount;i+)couttracki ;coutendl;cout平均寻道长度为:(float)TotalSize/trackCountendl;void sstf(int head,int trackCount,int track)int seq20;int minIndex=-1;int TotalSize=0;int curentHead=head;int seektime20=0;for(int i=0;itrackCount;i+)minIndex=seekmin(curentHead,trackCount,track);/与当前磁头距离最小的磁道的下标seqi=trackminIndex;seektimei=abs(curentHead-trackminIndex);curentHead=trackminIndex;trackminIndex=100000;for(int j=0;jtrackCount;j+)TotalSize+=seektimej;cout磁头访问的磁道序列为:;for(i=0;itrackCount;i+)coutseqi ;coutendl;cout平均寻道长度为:(float)TotalSize/trackCountendl;int seekmin(int curentHead,int trackCount,int track ) /SSTF找出与磁头距离最近的磁道下标int size , min=100000,index=-1;for(int i=0;itrackCount;i+)size=abs(curentHead-tracki);if(sizemin)min=size;index=i;return index;void scan(int head,int trackCount,int track)SelectSore(track,trackCount);int seq20;int seektime20=0;int TotalSize=0;int i;for(i=0;itrackCount;i+)if(head=tracki)break;int index=i;seektimeindex=abs(trackindex-head);seq0=trackindex;for(i=index+1;i=0;i-,j+)seektimej=abs(tracki+1-tracki);seqtrackCount-index+j=tracki;for(j=0;jtrackCount;j+)TotalSize+=seektimej;cout磁头访问的磁道序列为:;for(i=0;itrackCount;i+)coutseqi ;coutendl;cout平均寻道长度为:(float)TotalSize/trackCountendl;void SelectSore(int r ,int n)int index,temp;for(int i=0;in-1;i+)index