操作系统-磁盘调度算法实验报告.docx

操作系统实验报告实验六 磁盘调度算法班级：学号：姓名：一、 需求分析1、实验目的：通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。2、问题描述：设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。3、程序要求：1）利用先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法模拟磁道访问过程。2）模拟四种算法的磁道访问过程，给出每个磁道访问的磁头移动距离。3）输入：磁道个数n和磁道访问序列，开始磁道号m和磁头移动方向（对SCAN和循环SCAN算法有效），算法选择1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。4）输出：每种算法的平均寻道长度。二、概要设计1、程序中的变量及数据结构的定义a)自定义的整型向量类型：typedef vector vInt;b)磁道的结构体：struct OrderItem int Data;/磁道号 bool IsVisited;/磁道是否已被访问;c)磁道序列类型：typedef vector Order;d)存储待访问磁道序列：Order InitOrder;e)存储已被访问的磁道序列：vInt TrackOrder;f)移动距离序列：vInt MoveDistance;g)平均寻道长度：double AverageDistance;2、主要函数说明a) 获取用户输入的磁盘个数和磁盘的访问序列：void InitDate(int &num);参数num为磁道个数b) 先来先服务算法：void FCFS(int disk);c) 最短寻道时间优先算法：void SSTF(int disk);d) 扫描算法：void SCAN(int disk);e) 循环扫描算法：void CSCAN(int disk);f) void Show(int disk);3、 主函数的流程三、详细设计1. FCFS算法a) 说明：根据进程请求访问磁盘的先后次序进行调度。b) 具体流程如下：2. SFTF算法a) 说明：从InitOrder中找到未被访问过且与当前磁道距离最小的一个磁道进行访问。其中指针curp指向即为下一个要访问的磁道下标。b) 具体流程如下：3. SCAN算法a) 说明：用户输入开始磁道start和访问方向dir。从磁道序列中找出最大和最小的磁道号max、min。函数中cdir表示当前磁道访问方向，根据dir自里向外访问到max后改为自外向里，或者自外向里访问到min后改为自里向外。从磁道列表找出当前方向上与当前磁道距离最近的磁道号作为被访问的下一个磁道号。b) 具体流程如下：4. CSCAN算法a) 说明：用户输入开始磁道start和访问方向dir。从磁道序列中找出最大和最小的磁道号max、min及下标mmax、mmin。当dir=0，从内向外访问到max再从min开始从内往外访问未被访问过的磁盘；当dir=1则相反。从磁道列表找出当前方向上与当前磁道距离最近的磁道号作为被访问的下一个磁道号。b) 具体流程如下：四、使用说明编译执行后，根据界面给出的提示输入相应的信息，首先输入磁道个数，还有磁道序列，接着选择算法，根据选择算法，有的会直接给出结果，有的则会要求用户继续输入相应的信息，然后给出结果。用户可在结果显示完的提示给出后输入“yes”继续选择算法查看执行结果，或者输入“no”退出程序。五、结果测试1. FCFS算法测试 从不同的磁盘号开始访问2. SSTF算法测试从不同的磁盘号开始访问3. SCAN算法测试从不同的磁盘号开始访问，往不同方向访问，输入的数据同上4. CSCAN算法测试从不同的磁盘号开始访问，往不同方向访问，输入的数据同上六、附录程序完整代码#include #include #include using namespace std;typedef vector vInt;struct OrderItem int Data; bool IsVisited;typedef vector Order;Order InitOrder;vInt TrackOrder;vInt MoveDistance;double AverageDistance;void InitDate(int &num);inline void Init(int disk);void FCFS(int disk);void SSTF(int disk);void SCAN(int disk);void CSCAN(int disk);void Show(int disk);int main() int num; InitDate(num); string cmd; do cout选择算法:ntype; switch(type) case 1:FCFS(num);break; case 2:SSTF(num);break; case 3:SCAN(num);break; case 4:CSCAN(num);break; Show(num); coutcmd; while(cmd!=no); return 0;inline void Init(int disk) TrackOrder.clear(); MoveDistance.clear(); for(int i = 0; i disk; i+) InitOrderi.IsVisited = false; void InitDate(int &num) /ifstream cin(data.txt); coutnum; cout磁盘访问序列：; for(int i=0; ioi.Data; oi.IsVisited = false; InitOrder.push_back(oi); void FCFS(int disk) coutstart; coutFCFS:endl; int p = start; Init(disk); for(int i = 0 ; i 0?t:-t); InitOrderi.IsVisited = true; p = InitOrderi.Data; void SSTF(int disk) coutstart; coutSSTF:endl; Init(disk); int curp=0,dif=0; int p = start; for(int i = 0; i disk; i+) int temp = 0; for(int j = 0 ; j 0? p-InitOrderj.Data:-(p-InitOrderj.Data); if(dif=0|tempdif) dif = temp; curp = j; InitOrdercurp.IsVisited = true; TrackOrder.push_back(InitOrdercurp.Data); MoveDistance.push_back(dif); p = InitOrdercurp.Data; dif = 0; void SCAN(int disk) coutstart; coutdir; coutSSTF:endl; Init(disk); int curp=0,dif=0,cdir=dir,max=InitOrder0.Data,min=max; for(int i =1; idisk;i+) if(maxInitOrderi.Data) min = InitOrderi.Data; int p = start; for(int i = 0; i disk; i+) int temp = 0; for(int j = 0 ; j InitOrderj.Data|cdir=1&p0? p-InitOrderj.Data:-(p-InitOrderj.Data); if(dif=0|tempdif) dif = temp; curp = j; if(dir=0&InitOrdercurp.Data=max)cdir = 1; if(dir=1&InitOrdercurp.Data=min)cdir = 0; InitOrdercurp.IsVisited = true; TrackOrder.push_back(InitOrdercurp.Data); MoveDistance.push_back(dif); p = InitOrdercurp.Data; dif = 0; void CSCAN(int disk) coutstart; coutdir; coutCSSTF:endl; Init(disk); int curp=0,dif=-1,max=InitOrder0.Data,min=max,mmin=0,mmax=0; for(int i =1; idisk;i+)/找到磁道序列中最小和最大的磁道号及下标 if(maxInitOrderi.Data) min = InitOrderi.Data; mmin=i; int p = start;/p表示上一个访问的磁道号 for(int i = 0; i disk; i+) int temp = 0; for(int j = 0 ; j InitOrderj.Data|dir=1&p0? (p-InitOrderj.Data):(InitOrderj.Data-p); if(dif=-1|temp=0? p-TrackOrdermmin:TrackOrdermmin-p); curp = mmin; if(dir=1&InitOrdercurp.Data=min&InitOrdermmax.IsVisited=false) TrackOrder.push_back(max); InitOrdermmax.IsVisited = true; MoveDistance.push_back(p-TrackOrdermmin=0? p-TrackOrdermmin:TrackOrdermmin-p); curp = mmax; p = InitOrdercur