磁盘调度算法
学生姓名:
学生学号:
专业班级:
指导老师:
2013年6月20日
1、实验目的:
通过这次实验,加深对磁盘调度算法的理解,进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。
2、问题描述:
设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN 和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列,给定开始磁道号m和磁头移动的方向(正向或者反向),分别利用不同的磁盘调度算法访问磁道序列,给出每一次访问的磁头移动距离,计算每种算法的平均寻道长度。
3、需求分析
通过这次实验,加深对磁盘调度算法的理解,进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。
通过已知开始磁道数、访问磁道总数、磁道号访问序列、访问方向及访问方式得到访问序列及移动距离和平均移动距离!
(1)输入的形式;
int TrackOrder[MaxNumber];//被访问的磁道号序列 int direction;//寻道方向
int Num;//访问的磁道号数目
int start;//
(2)输出的形式;
int MoveDistance[MaxNumber]={0};//移动距离
double AverageDistance=0;//平均寻道长度
移动的序列!
(3)程序所能达到的功能;
模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列,给定开始磁道号m和磁头移动的方向(正向或者反向),分别利用不同的磁盘调度算法访问磁道序列,给出每一次访问的磁头移动距离,计算每种算法的平均寻道长度。
(4)测试数据,包括正确的输入及其输出结果和含有错误的输入及其输出结果。
开始磁道号:100
磁道号方向:内(0)和外(1)
磁道号数目:9
页面序列:55 58 39 18 90 160 150 38 184
4、概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。
int TrackOrder[MaxNumber];//被访问的磁道号序列int MoveDistance[MaxNumber]={0};//移动距离
double AverageDistance=0;//平均寻道长度
int direction;//寻道方向
int Num;//访问的磁道号数目
int start;//开始磁道号
5、详细设计
实现程序模块的具体算法。
6、调试分析
(1)调试过程中遇到的问题以及解决方法,设计与实现的回顾讨论和分析;
在SCAN_CSAN算法中在访问不同的数组时没有注意到上一个磁道号和要访问的磁道号的大小比较导致结果不对,后来在分析结果中找出原因。
(2)算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改进设想;
FCFS:时间复杂度为O(1)空间复杂度为:O(1)
SSTF:时间复杂度为O(n^2)空间复杂度为:O(1)
SCAN_CSAN:时间复杂度为O(n^2)空间复杂度为:O(1)
7、用户使用说明
程序的使用说明,列出每一步的操作步骤。
(1)输入开始磁道号
(2)输入访问磁道号总数
(3)输入访问磁道号序列序列
(4)选择算法
(5)选择方向
(6)得出结果
8、测试结果
9、存在问题
在求移动距离时,若调用C++的库函数求绝对值会更方便!
10、心得体会
首先要明确磁盘调度的原理,画出算法流程图!这样在解决问题时更容易!
11、附录
程序源代码:
#include
#define MaxNumber 100
void FCFS(int TrackOrder[MaxNumber],int MoveDistance[MaxNumber], double AverageDistance,int start,int Num)
{
int i,temp=start,sum=0;
cout<<"移动顺序移动距离"< for(i=0;i { if(TrackOrder[i]>temp) MoveDistance[i]=TrackOrder[i]-temp; else MoveDistance[i]=temp-TrackOrder[i]; sum+=MoveDistance[i]; temp=TrackOrder[i]; cout< } cout< AverageDistance=sum*1.0/Num; cout<<"平均寻道长度:"< } void SSTF(int TrackOrder[MaxNumber],int MoveDistance[MaxNumber], double AverageDistance,int start,int Num) { int temp=start, sum=0,s,count=0,min; int kind[MaxNumber]={0}; cout<<"移动顺序移动距离"< while(count { for(int i=0;i { if(kind[i]==0) { if(TrackOrder[i]>temp) min=TrackOrder[i]-temp; else min=temp-TrackOrder[i]; s=i; break; } } int temp1; for( i=0;i { if(TrackOrder[i]>temp) temp1=TrackOrder[i]-temp; else temp1=temp-TrackOrder[i]; if(temp1 { min=temp1; s=i; } } MoveDistance[count]=min; sum+=MoveDistance[s]; temp=TrackOrder[s]; cout< kind[s]=1; count++; } cout< AverageDistance=sum*1.0/Num; cout<<"平均寻道长度:"< } void paixu(int a[MaxNumber],int n,int TrackOrder[MaxNumber])//从小到大排序{ int sym=0; while(sym==0) { int kind=0; for(int i=0;i { int s1=a[i]; int s2=a[i+1]; i f(TrackOrder[s1]>TrackOrder[s2]) { int s=a[i+1]; a[i+1]=a[i]; a[i]=s; kind=1; } } if(kind==0) sym=1; } } void SCAN_CSAN(int TrackOrder[MaxNumber],int MoveDistance[MaxNumber], double AverageDistance,int start,int Num,int direction,int chioce) { int sum=0; int a[MaxNumber],b[MaxNumber]; int temp=start; int i,num1=0,num2=0; cout<<"移动顺序移动距离"< for(i=0;i { if(TrackOrder[i]> temp) { a[num1]=i; num1++; } else { b[num2]=i; num2++; } } paixu(a,num1,TrackOrder);//将数组按从小到达排序 paixu(b,num2,TrackOrder);//将数组按从小到达排序 int s; if(direction==0) //访问方向向外 { for(i=0;i { s=a[i]; MoveDistance[s]=TrackOrder[s]-temp; sum+=MoveDistance[s]; temp=TrackOrder[s]; cout< } if(chioce==3)//SCAN算法 { for(i=num2-1;i>=0;i--) //再访问num2并且从后往前访问 { s=b[i]; MoveDistance[s]=temp-TrackOrder[s]; sum+=MoveDistance[s]; temp=TrackOrder[s]; cout< } } else //CSAN算法 { s=b[0]; MoveDistance[s]=temp-TrackOrder[s]; sum+=MoveDistance[s]; temp=TrackOrder[s]; cout< for(i=1;i { s=b[i]; MoveDistance[s]=TrackOrder[s]-temp; sum+=MoveDistance[s]; temp=TrackOrder[s]; cout< } } } else //访问方向向内 { for(i=num2-1;i>=0;i--)//先访问num2并且从后往前访问 { s=b[i]; MoveDistance[s]=temp-TrackOrder[s]; sum+=MoveDistance[s]; temp=TrackOrder[s]; cout< } if(chioce==3) //SCAN算法 { f or(i=0;i { s=a[i]; MoveDistance[s]=TrackOrder[s]-temp; sum+=MoveDistance[s]; temp=TrackOrder[s]; cout< } } else //CSAN算法 { s=a[num1-1]; MoveDistance[s]=TrackOrder[s]-temp; sum+=MoveDistance[s]; temp=TrackOrder[s]; cout< f or(i=num1-2;i>=0;i--)//再访问num1并且从后往前访问 { s=a[i]; MoveDistance[s]=temp-TrackOrder[s]; sum+=MoveDistance[s]; temp=TrackOrder[s]; cout< } } } cout< AverageDistance=sum*1.0/Num; cout<<"平均寻道长度:"< } void main() { int TrackOrder[MaxNumber];//被访问的磁道号序列 int MoveDistance[MaxNumber]={0};//移动距离 double AverageDistance=0;//平均寻道长度 int direction;//寻道方向 int Num;//访问的磁道号数目 int start;//开始磁道号 int kind=0,chioce; cout<<"请输入开始磁道号:"; cin>>start; cout<<"请输入访问的磁道号数目:"; cin>>Num; cout<<"请输入被访问的磁道号序列:"; for(int i=0;i cin>>TrackOrder[i]; while(kind==0) { cout<<"请选择算法:1-FCFS,2-SSTF,3-SCAN,4-循环SCAN: "; cin>>chioce; if(chioce==1) FCFS(TrackOrder,MoveDistance,AverageDistance,start, Num); else { if(chioce==2) SSTF(TrackOrder,MoveDistance,AverageDistance,start, Num); else { cout<<"请输入磁道号访问方向,0:增加;1:减少: "; c in>>direction; SCAN_CSAN(TrackOrder,MoveDistance, AverageDistance,start,Num,direction,chioce); } } cout<<"**********************************************"< cout<<"请选择继续还是结束,0:继续;1:结束 "; cin>>kind; } } 《操作系统原理》 课程设计报告书 题目:磁盘调度 专业:网络工程 学号: 学生姓名: 指导教师: 完成日期: 目录 第一章课程设计目的 (1) 1.1编写目的 (1) 第二章课程设计内容 (2) 2.1设计内容 (2) 2.1.1、先来先服务算法(FCFS) (2) 2.1.2、最短寻道时间优先算法(SSTF) (2) 2.1.3、扫描算法(SCAN) (3) 2.1.4、循环扫描算法(CSCAN) (3) 第三章系统概要设计 (4) 3.1模块调度关系图 (4) 3.2模块程序流程图 (4) 3.2.1 FCFS算法 (5) 3.2.2 SSTF算法 (6) 3.2.3 SCAN算法 (7) 3.2.4 CSCAN算法 (8) 第四章程序实现 (9) 4.1 主函数的代码实现 (9) 4.2.FCFS算法的代码实现 (11) 4.3 SSTF算法的代码实现 (13) 4.4 SCAN算法的代码实现 (15) 4.5 CSCAN算法的代码实现 (17) 第五章测试数据和结果 (20) 第六章总结 (23) 第一章课程设计目的 1.1编写目的 本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统,从而使磁盘调度算法更加形象化,容易使人理解,使磁盘调度的特点更简单明了,能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解 1 第二章课程设计内容 2.1设计内容 系统主界面可以灵活选择某种算法,算法包括:先来先服务算法(FCFS)、最短寻道时间优先算法(SSTF)、扫描算法(SCAN)、循环扫描算法(CSCAN)。 2.1.1、先来先服务算法(FCFS) 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单,且每个进程的请求都能依次得到处理,不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化,在对磁盘的访问请求比较多的情况下,此算法将降低设备服务的吞吐量,致使平均寻道时间可能较长,但各进程得到服务的响应时间的变化幅度较小。 2.1.2、最短寻道时间优先算法(SSTF) 该算法选择这样的进程,其要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短,该算法可以得到比较好的吞吐量,但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的,因而导致响应时间的变化幅度很大。在服务请求很多的情况下,对内外边缘磁道的请求将会无限期的被延迟,有些请求的响应时间将不可预期。 2 操作系统上机 实验报告 成绩 教师: 2012 年 12月 5日 班级: 学号: 姓名: 实验地点: 实验时间: 实验一进程的建立 【实验目的】 创建进程及子进程 在父子进程间实现进程通信 【实验软硬件环境】 Linux 、Windows98、Windows2000 【实验内容】 创建进程并显示标识等进程控制块的属性信息; 显示父子进程的通信信息和相应的应答信息。 (进程间通信机制任选) 【实验程序及分析】 编程思路:首先本程序在Linux用C语言完成的,父子进程的创建用fork函数来实现,然后是父子进程间的通信,这里用pipe实现。可以定义chan1[2], chan1[2],chanx[0]表示读,chanx[1]表示写。他们配合使用。 【实验截图】 【实验心得体会】 通过这次上机练习,我熟悉了用c++实现进程的创建,销毁,父子进程间的通讯等一系列课程中需要学习的内容。本来进程的概念在一开始我始终无法清晰地理解,但是通过自己用mfc的方法去实现它后,我开始慢慢地理解操作系统的进程的运作机制。 虽然,我只是实现了一个父子进程的创建和通讯,但是,管中窥豹,我想自己开始明白一个操作系统正是由很多这种进程实现功能的。其中,系统整体的进程调度,管理等等还有很多东西等着我们去进一步学习、理解。 实验二进程间的同步 【实验目的】 理解进程同步和互斥模型及其应用 【实验软硬件环境】 Linux 、Windows98、Windows2000 【实验内容】 利用通信API实现进程之间的同步: 建立司机和售票员进程; 并实现他们间的同步运行。 【实验程序及分析】 程序总体思路:由于本次试验时用PV操作实现的互斥与同步模型,所以先实现P、V操作的函数,然后在主程序中利用PV操作函数实现司机和售票员的同步。司机和售票员分别为父进程和子进程,假设司机停车开门,此时为父进程中运行,然后申请开车,但是此时乘客没上车,所以只能阻塞。此时进入子进程,乘客上车,关门,售票员检票,释放开车,然后死机开车,到站,释放开车门。如此循环。 示意图 #include 实验名 称 作业调度 实验内容1、设计可用于该实验的作业控制块; 2、动态或静态创建多个作业; 3、模拟先来先服务调度算法和短作业优先调度算法。 3、调度所创建的作业并显示调度结果(要求至少显示出各作业的到达时间,服务时间,开始时间,完成时间,周转时间和带权周转时间); 3、比较两种调度算法的优劣。 实验原理一、作业 作业(Job)是系统为完成一个用户的计算任务(或一次事物处理)所做的工作总和,它由程序、数据和作业说明书三部分组成,系统根据该说明书来对程序的运行进行控制。在批处理系统中,是以作业为基本单位从外存调入内存的。 二、作业控制块J C B(J o b C o nt r o l Bl o ck) 作业控制块JCB是记录与该作业有关的各种信息的登记表。为了管理和调度作业,在多道批处理系统中为每个作业设置了一个作业控制块,如同进程控制块是进程在系统中存在的标志一样,它是作业在系统中存在的标志,其中保存了系统对作业进行管理和调度所需的全部信息。在JCB中所包含的内容因系统而异,通常应包含的内容有:作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。 三、作业调度 作业调度的主要功能是根据作业控制块中的信息,审查系统能否满足用户作业的资源需求,以及按照一定的算法,从外存的后备队列中选取某些作业调入内存,并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列,准备执行。 四、选择调度算法的准则 1).面向用户的准则 (1) 周转时间短。通常把周转时间的长短作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。所谓周转时间,是指从作业被提交给系统开始,到作业完成为止的这段时间间隔(称 操作系统磁盘调度算法 实验报告 Company number:【0089WT-8898YT-W8CCB-BUUT-202108】 目录 1.课程设计目的 编写目的 本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统,从而使磁盘调度算法更加形象化,容易使人理解,使磁盘调度的特点更简单明了,能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。 2.课程设计内容 设计内容 系统主界面可以灵活选择某种算法,算法包括:先来先服务算法(FCFS)、最短寻道时间优先算法(SSTF)、扫描算法(SCAN)、循环扫描算法(CSCAN)。 1、先来先服务算法(FCFS) 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单,且每个进 程的请求都能依次得到处理,不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化,在对磁盘的访问请求比较多的情况下,此算法将降低设备服务的吞吐量,致使平均寻道时间可能较长,但各进程得到服务的响应时间的变化幅度较小。 2、最短寻道时间优先算法(SSTF) 该算法选择这样的进程,其要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短,该算法可以得到比较好的吞吐量,但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的,因而导致响应时间的变化幅度很大。在服务请求很多的情况下,对内外边缘磁道的请求将会无限期的被延迟,有些请求的响应时间将不可预期。 3、扫描算法(SCAN) 扫描算法不仅考虑到欲访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向。例如,当磁头正在自里向外移动时,扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外,又是距离最近的。这样自里向外地访问,直到 人和以吟实验报告学院(系)名称:计算机与通信工程学院 【实验过程记录(源程序、测试用例、测试结果及心得体会等) 】 #include 实验报告学院(系)名称:计算机与通信工程学院 【实验过程记录(源程序、测试用例、测试结果及心得体会等)】 #include 实验二作业调度 一. 实验题目 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业调度算法:分别采用先来先服务(FCFS,最短作业优先(SJF)、响应 比高者优先(HRN的调度算法。 (1)先来先服务算法:按照作业提交给系统的先后顺序来挑选作业, 先提交的先被挑选。 (2)最短作业优先算法:是以进入系统的作业所提出的“执行时间”为标准, 总是优先选取执行时间最短的作业。 (3)响应比高者优先算法:是在每次调度前都要计算所有被选作业(在后备队列中)的响应比,然后选择响应比最高的作业执行。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法:采用基于先来先服务的调度算法。可以参考课本中的方法进 行设计。 对于多道程序系统,要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 二. 实验目的: 本实验要求用高级语言(C语言实验环境)编写和调试一个或多个作业调度的模拟程序,了解作业调度在操作系统中的作用,以加深对作业调度算法的理解 三. 实验过程 < 一>单道处理系统作业调度 1)单道处理程序作业调度实验的源程序: zuoye.c 执行程序: zuoye.exe 2)实验分析: 1、由于在单道批处理系统中,作业一投入运行,它就占有计算机的一切资 源直到作业完成为止,因此调度作业时不必考虑它所需要的资源是否得到 满足,它所占用的CPU时限等因素。 2、每个作业由一个作业控制块JCB表示,JCB可以包含如下信息:作业名、 提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业 的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一 每个作业的最初状态总是等待W 3、对每种调度算法都要求打印每个作业幵始运行时刻、完成时刻、周转时 间、带权周转时间,以及这组作业的平均周转时间及带权平均周转时间 3) 流程图: .最短作业优先算法 三.高响应比算法 图一.先来先服务流程图 4) 源程序: #in elude 操作系统实验报告课程名称:计算机操作系统 实验项目名称:磁盘调度实验时间: 班级:姓名:学号: 实验目的: 对操作系统的磁盘调度基础理论和重要算法的理解,加强动手能力。 实验环境: PC机 win7 Visual C++ 实验内容: 编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度,要求设计主界面以灵 活选择某算法,且以下算法都要实现: 1、先来先服务算法(FCFS) 2、最短寻道时间优先算法(SSTF) 3、扫描算法(SCAN) 4、循环扫描算法(CSCAN) 实验过程: 1.依次输入8个磁道数:123 45 31 67 20 19 38,并以0 结束 2.选择调度算法: (1)先来先服务算法(FCFS) (2)最短寻道时间优先算法(SSTF) 成绩: 指导教师(签名): (3)扫描算法(SCAN) (4)循环扫描算法(CSCAN) 实验心得: 通过本次实验,学习了解磁盘调度的工作原理及四种调度方法的工作原理,并且在当中操作系统磁盘调度算法实验报告
操作系统实验报告模板
作业调度_实验报告
操作系统磁盘调度算法实验报告
天津理工大学操作系统实验3:磁盘调度算法的实现
天津理工大学 操作系统实验3:磁盘调度算法地实现
作业调度实验报告
磁盘调度实验报告