1. AI技术聚合首页
  2. IT

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

青葱年少 • • IT • 阅读 42

磁盘调度算法

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

void FCFS(){
    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循环这个过程，对已经访问过的磁道给其一个较大的值，防止其再次被访问。
void SSTF(){
    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小的磁道开始进行相同的计算。如果选择减少的方向，则与增加方向相反。

void SCAN(){
    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++;
        }
    }
    else if (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++;
        }
    }
    else if (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>
using namespace std;
 
#define MaxNumber 100
int TrackOrder[MaxNumber];//初始磁道序列
int MoveDistance[MaxNumber];//磁头移动距离（磁道数）
double AverageDistance;//磁头平均移动距离
int direction;//选择磁头方向 
int TrackNum;//磁道数
int StartTrack;//开始磁道号m 
int VisitOrder[MaxNumber];//访问磁道序列
bool isVisit[MaxNumber];//标记是否被访问过
int SumDistance;//磁头移动的总距离
int choose;

void input();//输入起始磁道号、磁道顺序
void initial();
void output();
void FCFS();//先来先服务，先进先出
void SSTF();//最短寻道时间优先
void SCAN();//扫描，从开始磁道沿选择方向扫描，直到没有要访问的磁道在沿反方向扫描
void CSCAN();//循环扫描，自开始磁道始终沿一个方向扫描，直到没有要访问的磁道再从最里圈或最外圈扫描
void chooseAlgorithm();
 
int main(){
    input();
    chooseAlgorithm();
    return 0;
}
 
void input(){
    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;
}
void initial(){
    for (int i=0;i<TrackNum;i++){
        MoveDistance[i] = 0;
        VisitOrder[i] = TrackOrder[i];
        isVisit[i] = false;
    }
    SumDistance = 0;
    AverageDistance = 0;
}

void output(){
    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;
}
 
//先来先服务，先进先出
void FCFS(){
    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();
}
 
//最短寻道时间优先
void SSTF(){
    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();
}
 
//扫描，从开始磁道沿选择方向扫描，直到没有要访问的磁道在沿反方向扫描
void SCAN(){
    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++;
        }
    }
    else if (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();
}
 
//循环扫描，自开始磁道始终沿一个方向扫描，直到没有要访问的磁道再从最里圈或最外圈扫描
void CSCAN(){

	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++;
        }
    }
    else if (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();
}


void chooseAlgorithm()
{
	cout<<"请选择算法“1-FCFS，2-SSTF，3-SCAN，4-循环SCAN ,0-退出”"<<endl;
	cin>>choose;
	if (choose==1)
	{
		FCFS();
		chooseAlgorithm();
	}
		else if(choose==2)
		{
			SSTF();
			chooseAlgorithm();
		}
		else if(choose==3){
            SCAN();
        	chooseAlgorithm();
		}
		else if(choose==4){
            CSCAN();
            chooseAlgorithm();
		}
		else if(choose==0){
          exit(0);
		}
	else
	{
		cout<<"请输入正确的选择“1-FCFS，2-SSTF，3-SCAN，4-循环SCAN ,0-退出”"<<endl;
		chooseAlgorithm();  
	}
}

输入数据格式

10
78 30 9 15 102 140 156 54 45 125
100

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
青葱年少的头像青葱年少普通用户
0
上一篇 2023年12月26日
下一篇 2023年12月26日

相关推荐