操作系统-磁盘调度算法（SCAN、CSCAN）

目录

一、前言

二、要求实现的功能

三、运行结果

 四、代码

总结

---

一、前言

该系统名称为：磁盘调度算法2，使用的是C++。

二、要求实现的功能

设计主界面以灵活选择某算法，且以下算法都要实现

1、扫描算法（SCAN）

2、循环扫描算法（CSCAN）

并求出每种算法的平均寻道长度

三、运行结果

手动输入测试样例：    初始时磁头位置：45

                                    磁道序列：55 58 39 18 90 160 150 38 184

主界面:

 选择SCAN算法并手动输入磁道

 选择磁道算法并让系统自动输入磁道

 选择CSCAN算法并手动输入磁道

 选择CSCAN算法并让系统自动输入磁道

四、代码

代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include <random>
 
using namespace std;
struct node
{
	int positon;//磁道位置
	int moved;//磁道与当前磁头的距离
	int visit;//磁道是否被访问过
}que[1010];//初始磁道序列
 
void surface();
void input();//输入函数
void output2();//输出函数
int dis(int a, int b);//两个磁道距离的绝对值
void SCAN();//扫描法
void CSCAN();//循环扫描法
 
int sig, start, direction;//算法选择标志，当前磁头位置，磁头移动方向
int num;//磁道数量
int order[1010];//磁头访问的磁道序列
int total;//磁头访问的总磁道数
const int isVis = 1;//该磁道被访问过
const int noVis = 0;//该磁道没被访问过
const int bigger = 1;//向磁头号增大方向移动
const int smaller = 0;//向磁头号减小方向移动
int num3[8]={33,59,13,77,123,170,160,185};
int a1;//选择自动输入还是手动输入
 
int main()
{
    string a="yes";
    while(a=="yes")
    {
        surface();
	//程序输入
	input();
 
	//选择算法
	switch (sig)
	{
		case 1:SCAN(); break;
		case 2:CSCAN(); break;
	}
        //程序输出
    	output2();
     	cout<<"\n是否重新选择算法（yes/no）：";
    	cin>>a;
    }
 
	return 0;
}
 
void surface()
{
	printf("-------------------磁盘调度算法2-------------------\n");
	printf("---------------------------------------------------\n");
	printf("**********************功能菜单*********************\n\n");
	printf("                   1.扫描算法（SCAN）              \n\n");//每次将磁头按照电梯的方式朝一个方向移动，到顶点后按相反方向折回
	printf("                   2.循环扫描算法（CSCAN)          \n\n");
	printf("                   3.退出系统                      \n\n");
	printf("***************************************************\n");
	printf("---------------------------------------------------\n\n\n");
 
	printf("请输入您想要使用的功能：");
}
void input()
{
	//freopen("osin.txt", "r", stdin);
	//freopen("osout.txt", "w", stdout);
	cin >> sig;	//算法选择标志
 
	start = 0;
	total = 0;
	cout<<"请输入当前磁头位置：";
	cin >> start;//初始磁头位置
	cout<<"请输入磁头移动方向(磁头号增大方向为1，否则为2)：";
	cin >> direction;//磁头移动方向
 
	num = 0;
	char c;
 
    cout<<"------------------\n";
	cout<<"选择输入磁道方式\n";
	cout<<"1.手动输入\n";
	cout<<"2.自动输入\n";
	cout<<"------------------\n";
	cout<<"请输入选择的方式：";
	cin>>a1;
	if(a1==1)
    {
        cout<<"\n请输入磁道序列:";
	    while (scanf("%d", &que[num].positon))//输入磁道序列
	{
		que[num].moved = 0;
		que[num].visit = noVis;
		num++;
		c = getchar();
		if (c == '\n')//遇到换行符则输入结束
		{
			break;
		}
		else if (c == ',')//遇到逗号则继续读取
		{
			continue;
		}
	}
    }
    else
    {
        cout<<"\n自动生成的磁道序列为：";
        while(num<=7)
        {
           // cout<<num3[num]+" ";
            que[num].positon=num3[num];
            que[num].visit = noVis;
            num++;
        }
       /* for(int i=0;i<=7;i++)
        {
            cout<<num3[i]+" ";
        }*/
 
 
    }
}
 
void output2()
{
	double sum;
    if(a1==2)
    {
        for(int i=0;i<=7;i++)
        {
            printf("%d ",num3[i]);
        }
    }
	if(sig==1)
	{
		cout<<"\n-----------SCAN-----------\n";
		printf("      (从%d磁道开始）\n",order[0]);
		cout<<"  下一磁道号    移动距离\n" ;
		for (int i = 1; i <= num; i++)//磁头移动经过的磁道序列
	{
		if (i != num)
		{
			printf("    %-10d     %-10d\n", order[i],abs(order[i]-order[i-1]));
		}
		else
		{
			printf("    %-10d     %-10d\n", order[i],abs(order[i]-order[i-1]));
		}
 
		sum=i;
	}
	printf("平均寻道长度:%.1lf\n", total/(sum));//磁头移动经过的总磁道数
	cout<<"-----------SCAN结束------------";
	}
	if(sig==2)
	{
		cout<<"\n-----------CSCAN----------\n";
		printf("      (从%d磁道开始）\n",order[0]);
		for (int i = 1; i <= num; i++)//磁头移动经过的磁道序列
	{
		if (i != num)
		{
			printf("    %-10d     %-10d\n", order[i],abs(order[i]-order[i-1]));
		}
		else
		{
			printf("    %-10d     %-10d\n", order[i],abs(order[i]-order[i-1]));
		}
		sum=i;
	}
     	printf("平均寻道长度:%.1lf\n", total/(sum));//磁头移动经过的总磁道数
     	cout<<"-----------CSCAN结束------------";
	}
}
int dis(int a, int b)
{
	return abs(a - b);
}
 
void SCAN()
{
	order[0] = start;
	//构造电梯
	int sorted[1010];
	for (int i = 0; i < num; i++)
	{
		sorted[i] = que[i].positon;
	}
	sort(sorted, sorted + num);
 
	//距当前磁头距离最短的磁道号
	int mini = 0;
	while (start >= sorted[mini])//统计出大于初始磁道号的刺刀个数
	{
		mini++;
	}
 
	//开始运行电梯
	int ans = 1;
	if (direction == bigger)//向磁头号增大方向移动
	{
		//电梯上升
		for (int i = mini; i < num; i++)
		{
			order[ans] = sorted[i];//order是将要访问的磁道序列
			ans++;
		}
		total += (sorted[num - 1] - start);
		//电梯下降
		for (int i = mini - 1; i >= 0; i--)
		{
			order[ans] = sorted[i];
			ans++;
		}
		total += (sorted[num - 1] - sorted[0]);
	}
	else//向磁头号减小方向移动
	{
		//电梯下降
		for (int i = mini - 1; i >= 0; i--)
		{
			order[ans] = sorted[i];
			ans++;
		}
		total += (start - sorted[0]);
		//电梯上升
		for (int i = mini; i < num; i++)
		{
			order[ans] = sorted[i];
			ans++;
		}
		total += (sorted[num - 1] - sorted[0]);
	}
}
void CSCAN()
{
	order[0] = start;
	//构造电梯
	int sorted[1010];
	for (int i = 0; i < num; i++)
	{
		sorted[i] = que[i].positon;
	}
	sort(sorted, sorted + num);
 
	//距当前磁头距离最短的磁道号
	int mini = 0;
	while (start > sorted[mini])
	{
		mini++;
	}
 
	//开始运行电梯
	int ans = 1;
	if (direction == bigger)//向磁头号增大方向移动
	{
		//电梯上升
		for (int i = mini; i < num; i++)
		{
			order[ans] = sorted[i];
			ans++;
		}
		//电梯循环
		for (int i = 0; i < mini; i++)
		{
			order[ans] = sorted[i];
			ans++;
		}
		//推导可得，total等于两端长度的两倍减去中间没有覆盖到的一段
		total += (2 * (sorted[num - 1] - sorted[0]) - (start - sorted[mini - 1]));
	}
	else//向磁头号减小方向移动
	{
		//电梯下降
		for (int i = mini - 1; i >= 0; i--)
		{
			order[ans] = sorted[i];
			ans++;
		}
		//电梯循环
		for (int i = num - 1; i >= mini; i--)
		{
			order[ans] = sorted[i];
			ans++;
		}
		//推导可得，total等于两端长度的两倍减去中间没有覆盖到的一段
		total += (2 * (sorted[num - 1] - sorted[0]) - (sorted[mini] - start));
	}
}

---

总结

本次课设题目是磁盘调度算法，使我更加理解了磁盘调度算法的全过程。要实现该算法首先要了解算法的过程，最短寻道算法（SSTF）就是总会从等待访问者中挑选寻找时间最短的那个请求先执行的，无论是在磁盘的里面还是外面，只要离他近的就先执行。而循环扫描算法就和我们平时坐的电梯有点类似，先往一个方向运行。这次的实验里对总道数的计算一开始理解的不够全，尤其是循环扫描算法，但用电梯实例来想象模拟后我很快弄明白了怎么回事。

但是程序仍然有很多改进的地方，资源可以更加节约，算法也还有优化的余地，但是时间和精力有限，我会在课余的时间加深对磁盘调度的理解同时加上其他的算法，例如扫描调度（SCAN）算法，先来先服务（FCFS）等。这次实验也让我感觉到了算法才是程序的灵魂，没有好的算法就像巧妇难为无米之炊，即使有再好的工具和基本功，没有算法和基本思想也是不可行的。

通过实现磁盘调度算法的动态实现过程，让我更加清楚了算法的流程，非常深刻地了解了这几种调度算法的异同以及优缺点。不仅仅是上述四种调度算法，由于时间原因，没能实现C-LOOK调度算法。等有时间，我会亲自实现一遍C-LOOK算法，更加深入的了解磁盘调度算法的实际应用。