0
0

磁盘调度算法（操作系统实验 C＋＋）

磁盘调度算法

1.实验目的

通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。

2.实验内容

问题描述：
设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。
程序要求：
1）利用先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法模拟磁道访问过程。
2）模拟四种算法的磁道访问过程，给出每个磁道访问的磁头移动距离。
3）输入：磁道个数n和磁道访问序列，开始磁道号m和磁头移动方向（对SCAN和循环SCAN算法有效），算法选择1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。
4）输出：每种算法的平均寻道长度。
实现提示：
用C++语言实现提示：
1）程序中变量定义参考（根据需要可添加）如下：
const int MaxNumber=100;
int TrackOrder[MaxNumber];
int MoveDistance[MaxNumber];
double AverageDistance;
bool direction;
2）页面置换的实现过程如下：
变量初始化；

  • 接收用户输入磁道个数n和磁盘访问序列，选择算法1-FCFS，2-SSTF，3-SCAN，4-循环SCAN，输入开始磁盘号m和磁头移动方向；
  • 根据用户选择的算法进行磁道访问，输出磁盘调度算法的模拟过程；
  • 计算选择每次移动的磁头移动距离和算法的平均寻道长度；
  • 输出选择算法的平均寻道长度。

实验要求：
1）上机前认真复习磁盘调度算法，熟悉FCFS、SSTF、SCAN和循环SCAN算法的过程；
2）上机时独立编程、调试程序；
3）根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源 程序、实例运行结果截图、发现的问题以及解决方法）。

3.程序主要构成部分及其算法说明

1.FCFS（先来先服务算法）
先对队列进行初始化，计算开始磁道号和队列中的第一个磁道号的距离，然后按照输入顺序依次访问磁道，计算移动距离，最后计算平均寻道长度。

voidFCFS(){initial();  
      cout<<"FCFS"<<endl;
   
MoveDistance[0]=abs(TrackOrder[0]-StartTrack);
VisitOrder[i]= TrackOrder[i];
SumDistance = MoveDistance[0];for(int i=1;i<TrackNum;i++){
        MoveDistance[i]=abs(TrackOrder[i]-TrackOrder[i-1]);、
         VisitOrder[i]= TrackOrder[i];
        SumDistance += MoveDistance[i];}
    AverageDistance = SumDistance*1.0/TrackNum;output();}
  1. SSTF（最短寻找时间优先） 先对队列进行初始化，然后用嵌套for循环计算，内部的第一个for循环先用来计算序列中所有磁道和第一个磁道（赋值给CurrentTrack）的距离存放在数组distance中，然后用第二个for循环找到距离最近的序列号pointMin，计算距离和记录位置后将pointMin赋值给CurrentTrack，然后外部for循环这个过程，对已经访问过的磁道给其一个较大的值，防止其再次被访问。
voidSSTF(){initial();
    cout<<"SSTF"<<endl;int CurrentTrack = StartTrack;int i,j,pointMin;int distance[MaxNumber];for(i =0;i<TrackNum;i++){for(j =0;j<TrackNum;j++){if(!isVisit[j])
                distance[j]=abs(TrackOrder[j]-CurrentTrack);else
                distance[j]=1000000;}
        pointMin =0;for(j =0;j<TrackNum;j++){if(distance[pointMin]> distance[j])
                pointMin = j;}
        VisitOrder[i]= TrackOrder[pointMin];  
        MoveDistance[i]=abs(TrackOrder[pointMin]-CurrentTrack);/
        SumDistance += MoveDistance[i];   
        CurrentTrack = TrackOrder[pointMin];  
        isVisit[pointMin]=true;}
    AverageDistance = SumDistance*1.0/(TrackNum);output();}

3.SCAN（扫描算法）
先对序列初始化，然后输入磁头移动的方向，建立新数组用来存放排序后的磁道序列。使用一个冒泡循环得出从小到大的磁道号序列。设置point，让其指向找既在当前磁道之外，又是距离最近的磁道号。如果选择增加方向，则先从point开始，第一个for循环依次遍历磁道号比point大的磁道，计算移动距离和存放位置，再将 下一个磁道号赋值给currentTrack进行下一次计算。第二个for循环从磁道号比point小的磁道开始进行相同的计算。如果选择减少的方向，则与增加方向相反。

voidSCAN(){initial();
cout<<"SCAN"<<endl;int i,j,temp;int SortTrackOrder[MaxNumber];
    cout<<"选择磁头移动的方向,1-增加,2-减少: "<<endl;
    cin>>direction;for(i =0;i<TrackNum;i++){ 
        SortTrackOrder[i]= TrackOrder[i];}for(i =0;i<TrackNum;i++){for(j = i;j<TrackNum;j++){if(SortTrackOrder[i]>=SortTrackOrder[j]){
                temp = SortTrackOrder[i];
                SortTrackOrder[i]= SortTrackOrder[j];
                SortTrackOrder[j]= temp;}}}int point =0;while(StartTrack>=SortTrackOrder[point]){
        point++;}int count =0;int currentTrack = StartTrack;if(direction ==1){  
        cout<<"向磁道增加的方向访问"<<endl;for(i = point;i<TrackNum;i++){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}for(i = point -1;i>=0;i--){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}}elseif(direction ==2){  
        cout<<"向磁道减少的方向访问"<<endl;for(i = point-1;i>=0;i--){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}for(i = point;i<TrackNum;i++){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}}for(i =0;i<TrackNum;i++){
        SumDistance += MoveDistance[i];}
    AverageDistance =(SumDistance*1.0)/TrackNum;output();}
  1. CSCAN（循环扫描SCAN算法） 先对序列初始化，然后输入磁头移动的方向，建立新数组用来存放排序后的磁道序列。使用一个冒泡循环得出从小到大的磁道号序列。设置point，让其指向找既在当前磁道之外，又是距离最近的磁道号。如果选择增加方向，则先从point开始，第一个for循环依次遍历磁道号比point大的磁道，计算移动距离和存放位置，再将下一个磁道号赋值给currentTrack进行下一次计算。第二个for循环从最小的磁道号开始进行相同的计算。如果选择减少的方向，先从比point小一号的磁道号开始依次按磁道号减少遍历，再从磁道号最大的序列开始按磁道号减少计算。
initial();
    cout<<"CSCAN"<<endl;
    cout<<"选择磁头移动的方向,1-增加,2-减少: "<<endl;
    cin>>direction;int SortTrackOrder[MaxNumber];int i,j,temp;for(i =0;i<TrackNum;i++){
        SortTrackOrder[i]= TrackOrder[i];}for(i = TrackNum -1;i>0;i--){for(j =0;j<i;j++){if(SortTrackOrder[j]>=SortTrackOrder[j+1]){
                temp = SortTrackOrder[j];
                SortTrackOrder[j]= SortTrackOrder[j+1];
                SortTrackOrder[j+1]= temp;}}}int point =0;while(StartTrack>=SortTrackOrder[point]){
        point++;}int count =0;int currentTrack = StartTrack;if(direction ==1){  
        cout<<"向磁道增加的方向访问"<<endl;for(i = point;i<TrackNum;i++){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}for(i =0;i<point;i++){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}}elseif(direction ==2){ 
        cout<<"向磁道减少的方向访问"<<endl;for(i = point-1;i>=0;i--){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}for(i = TrackNum-1;i>point-1;i--){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}}for(i =0;i<TrackNum;i++){
        SumDistance += MoveDistance[i];}
    AverageDistance =(SumDistance*1.0)/TrackNum;output();}

4.运行结果

1.程序读取data中的数据并输出，输入1执行FCFS算法。输出磁盘调度算法的模拟过程，每次移动的磁头移动距离和算法的平均寻道长度。
在这里插入图片描述

2.输入2执行SSTF算法。输出磁盘调度算法的模拟过程，每次移动的磁头移动距离和算法的平均寻道长度
在这里插入图片描述

3.输入3执行SCAN算法。输入1选择磁头移动方向为增加方向，输入2选择磁头移动方向为减少方向；输出磁盘调度算法的模拟过程，每次移动的磁头移动距离和算法的平均寻道长度
在这里插入图片描述

在这里插入图片描述

4.输入4执行CSCAN算法。输入1选择磁头移动方向为增加方向，输入2选择磁头移动方向为减少方向；输出磁盘调度算法的模拟过程，每次移动的磁头移动距离和算法的平均寻道长度

在这里插入图片描述
在这里插入图片描述

5.程序源码

#include<iostream>#include<fstream>#include<iomanip>#include<cmath>#include<stdlib.h>usingnamespace std;#define MaxNumber 100int TrackOrder[MaxNumber];//初始磁道序列int MoveDistance[MaxNumber];//磁头移动距离（磁道数）double AverageDistance;//磁头平均移动距离int direction;//选择磁头方向 int TrackNum;//磁道数int StartTrack;//开始磁道号m int VisitOrder[MaxNumber];//访问磁道序列bool isVisit[MaxNumber];//标记是否被访问过int SumDistance;//磁头移动的总距离int choose;voidinput();//输入起始磁道号、磁道顺序voidinitial();voidoutput();voidFCFS();//先来先服务，先进先出voidSSTF();//最短寻道时间优先voidSCAN();//扫描，从开始磁道沿选择方向扫描，直到没有要访问的磁道在沿反方向扫描voidCSCAN();//循环扫描，自开始磁道始终沿一个方向扫描，直到没有要访问的磁道再从最里圈或最外圈扫描voidchooseAlgorithm();intmain(){input();chooseAlgorithm();return0;}voidinput(){
    ifstream readData;
    readData.open("data.txt");
    readData>>TrackNum;//磁道个数for(int i=0;i<TrackNum;i++){
        readData>>TrackOrder[i];//磁道访问序列}
    readData>>StartTrack;//开始磁道号
    cout<<"磁道个数 = "<<TrackNum<<endl;
    cout<<"磁道访问序列：";for(int i=0;i<TrackNum;i++){
        cout<<TrackOrder[i]<<" ";}
    cout<<endl;
    cout<<"开始磁道号m= "<<StartTrack<<endl;
    cout<<"------------------------------------"<<endl;}voidinitial(){for(int i=0;i<TrackNum;i++){
        MoveDistance[i]=0;
        VisitOrder[i]= TrackOrder[i];
        isVisit[i]=false;}
    SumDistance =0;
    AverageDistance =0;}voidoutput(){
    cout<<"从"<<StartTrack<<"号磁道开始"<<endl;
    cout<<"被访问的下一个磁道号"<<"\t"<<"移动距离"<<"\t"<<endl;for(int i=0;i<TrackNum;i++){
        cout<<VisitOrder[i]<<"\t\t\t"<<MoveDistance[i]<<"\t"<<endl;}
    cout<<"平均寻道长度: "<<setprecision(4)<<AverageDistance<<endl;
    cout<<endl;}//先来先服务，先进先出voidFCFS(){
    cout<<endl;
    cout<<"FCFS"<<endl;initial();//按照输入顺序依次访问磁道
    MoveDistance[0]=abs(TrackOrder[0]-StartTrack);
    SumDistance = MoveDistance[0];
    VisitOrder[0]= TrackOrder[0];for(int i=1;i<TrackNum;i++){
        MoveDistance[i]=abs(TrackOrder[i]-TrackOrder[i-1]);
        SumDistance += MoveDistance[i];
        VisitOrder[i]= TrackOrder[i];}
 
    AverageDistance = SumDistance*1.0/TrackNum;output();}//最短寻道时间优先voidSSTF(){
    cout<<endl;
    cout<<"SSTF"<<endl;initial();int CurrentTrack = StartTrack;int i,j,pointMin;int distance[MaxNumber];for(i =0;i<TrackNum;i++){for(j =0;j<TrackNum;j++){if(!isVisit[j])
                distance[j]=abs(TrackOrder[j]-CurrentTrack);else
                distance[j]=10000;//表示无穷远，即访问过的磁道就不再访问}
        pointMin =0;for(j =0;j<TrackNum;j++){if(distance[pointMin]> distance[j])
                pointMin = j;//指向最小的位置}
        VisitOrder[i]= TrackOrder[pointMin];//给访问序列赋值
        MoveDistance[i]=abs(TrackOrder[pointMin]-CurrentTrack);//计算每次的移动距离
        SumDistance += MoveDistance[i];//累计移动距离
        CurrentTrack = TrackOrder[pointMin];//改变当前的磁道号
        isVisit[pointMin]=true;//将当前的磁道号设置为已访问}
    AverageDistance = SumDistance*1.0/(TrackNum);output();}//扫描，从开始磁道沿选择方向扫描，直到没有要访问的磁道在沿反方向扫描voidSCAN(){
    cout<<endl;
    cout<<"SCAN"<<endl;
    cout<<"选择磁头移动的方向,1-增加,2-减少: "<<endl;
    cin>>direction;initial();int i,j,temp;int SortTrackOrder[MaxNumber];for(i =0;i<TrackNum;i++){//初始化
        SortTrackOrder[i]= TrackOrder[i];}//冒泡排序for(i =0;i<TrackNum;i++){for(j = i;j<TrackNum;j++){if(SortTrackOrder[i]>=SortTrackOrder[j]){
                temp = SortTrackOrder[i];
                SortTrackOrder[i]= SortTrackOrder[j];
                SortTrackOrder[j]= temp;}}}//找到既在当前磁道之外，又是距离最近的磁道号int point =0;while(StartTrack>=SortTrackOrder[point]){
        point++;}int count =0;int currentTrack = StartTrack;if(direction ==1){//向磁道增加的方向访问
        cout<<"向磁道增加的方向访问"<<endl;for(i = point;i<TrackNum;i++){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}for(i = point -1;i>=0;i--){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}}elseif(direction ==2){//向磁道减少的方向访问
        cout<<"向磁道减少的方向访问"<<endl;for(i = point-1;i>=0;i--){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}for(i = point;i<TrackNum;i++){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}}for(i =0;i<TrackNum;i++){
        SumDistance += MoveDistance[i];}
    AverageDistance =(SumDistance*1.0)/TrackNum;output();}//循环扫描，自开始磁道始终沿一个方向扫描，直到没有要访问的磁道再从最里圈或最外圈扫描voidCSCAN(){initial();
    cout<<"CSCAN"<<endl;
    cout<<"选择磁头移动的方向,1-增加,2-减少: "<<endl;
    cin>>direction;int SortTrackOrder[MaxNumber];int i,j,temp;for(i =0;i<TrackNum;i++){
        SortTrackOrder[i]= TrackOrder[i];}//冒泡排序for(i = TrackNum -1;i>0;i--){for(j =0;j<i;j++){if(SortTrackOrder[j]>=SortTrackOrder[j+1]){
                temp = SortTrackOrder[j];
                SortTrackOrder[j]= SortTrackOrder[j+1];
                SortTrackOrder[j+1]= temp;}}}//找到既在当前磁道之外，又是距离最近的磁道号int point =0;while(StartTrack>=SortTrackOrder[point]){
        point++;}int count =0;int currentTrack = StartTrack;if(direction ==1){  
        cout<<"向磁道增加的方向访问"<<endl;for(i = point;i<TrackNum;i++){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}for(i =0;i<point;i++){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}}elseif(direction ==2){//向磁道减少的方向访问
        cout<<"向磁道减少的方向访问"<<endl;for(i = point-1;i>=0;i--){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}for(i = TrackNum-1;i>point-1;i--){
            VisitOrder[count]= SortTrackOrder[i];
            MoveDistance[count]=abs(VisitOrder[count]-currentTrack);
            currentTrack = VisitOrder[count];
            count++;}}for(i =0;i<TrackNum;i++){
        SumDistance += MoveDistance[i];}
    AverageDistance =(SumDistance*1.0)/TrackNum;output();}voidchooseAlgorithm(){
    cout<<"请选择算法“1-FCFS，2-SSTF，3-SCAN，4-循环SCAN ,0-退出”"<<endl;
    cin>>choose;if(choose==1){FCFS();chooseAlgorithm();}elseif(choose==2){SSTF();chooseAlgorithm();}elseif(choose==3){SCAN();chooseAlgorithm();}elseif(choose==4){CSCAN();chooseAlgorithm();}elseif(choose==0){exit(0);}else{
        cout<<"请输入正确的选择“1-FCFS，2-SSTF，3-SCAN，4-循环SCAN ,0-退出”"<<endl;chooseAlgorithm();}}

输入数据格式

1078309151021401565445125100
标签： 算法 数据结构 c++
本文转载自: https://blog.csdn.net/weixin_51080803/article/details/129912007
版权归原作者 落灬枫 所有， 如有侵权，请联系我们删除。
登录后发布评论

“磁盘调度算法（操作系统实验 C＋＋）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航