【实验名称】磁盘调度模拟                   

【实验目的】

1、掌握FCFS、SSTF、SCAN等磁盘调度算法；

2、使用高级语言实现算法，并比较不同算法的优缺点。

【实验原理】

磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）等。

一次磁盘读写操作的时间由寻找（寻道）时间、延迟时间和传输时间决定。在磁盘存取时间的计算中，寻道时间与磁盘调度算法相关，而延迟时间和传输时间都与磁盘旋转速度相关，且为线性相关，所以在硬件上，转速是磁盘性能的一个非常重要的参数。总平均存取时间Ta可以表示为：Ta = Ts + Tr + Tt。

【实验内容】

实验内容：验证FCFS、SSTF、SCAN等磁盘调度算法。

代码（详情见代码注释）：

#include<iostream>
#include <iomanip>
using namespace std;
#define INF 2147483647
class Visit;
//进程请求类
class Request
{
public:
	Request(int num)
	{
		number = num;
		finish = false;
	}
	void reset();//复位，重新标记finish为未访问
	void achieve();//标记该请求已经完成
	friend void FCFS(Request** request, Visit** visit, int num, int begin);
	friend void SSTF(Request** request, Visit** visit, int num, int begin);
	friend void SCAN(Request** request, Visit** visit, int num, int begin, bool direction);
	friend void show_visit(Visit** visit, int num, int begin);
private:
	int number;//磁道号
	bool finish;//是否完成访问
};
void Request::reset()
{
	finish = false;
}
void Request::achieve()
{
	finish = true;
}

//磁盘访问类
//记录访问顺序和移动距离
class Visit
{
public:
	Visit()
	{
		number = -1;
		distance = -1;
	}
	void reset();//复位。记录清空
	friend void FCFS(Request** request, Visit** visit, int num, int begin);
	friend void SSTF(Request** request, Visit** visit, int num, int begin);
	friend void SCAN(Request** request, Visit** visit, int num, int begin, bool direction);
	friend void show_visit(Visit** visit, int num, int begin);
private:
	int number;//被访问的磁道号
	int distance;//移动距离
};
void Visit::reset()
{
	number = -1;
	distance = -1;
}

//FCFS算法
void FCFS(Request** request, Visit** visit, int num, int begin)
{
	for (int i = 0; i < num; i++)
	{
		//加入已访问队列
		visit[i]->number = request[i]->number;
		visit[i]->distance = abs(begin - request[i]->number);
		//跟新磁头位置，并标记已访问
		begin= request[i]->number;
		request[i]->finish = true;
	}
}

//SSTF算法
void SSTF(Request** request, Visit** visit, int num, int begin)
{
	Request *point;
	for (int i = 0; i < num; i++)
	{
		//先指向无穷大
		point = new Request(INF);
		for (int j = 0; j < num; j++)
		{
			//若当前请求距离更短且未被访问过，则指向当前请求
			if ((abs(point->number - begin) > abs(request[j]->number - begin)) && request[j]->finish == false)
			{
				point = request[j];
			}
		}
		//加入已访问队列
		visit[i]->number = point->number;
		visit[i]->distance = abs(begin - point->number);
		//跟新磁头位置，并标记已访问
		begin = point->number;
		point->finish = true;
	}
	return;
}

//SCAN算法
void SCAN(Request** request, Visit** visit, int num, int begin, bool direction)
{
	//求得边界
	int max = -INF, min = INF;
	for (int i = 0; i<num; i++)
	{
		if (max < request[i]->number)
		{
			max = request[i]->number;
		}	
		if (min > request[i]->number)
		{
			min = request[i]->number;
		}	
	}
	Request *point;
	for (int i = 0; i < num; i++)
	{
		//先指向无穷大
		point = new Request(INF);
		for (int j = 0; j < num; j++)
		{
			//若和当前访问方向相反则忽略
			if ((direction == false && request[j]->number < begin) || (direction == true && request[j]->number > begin))
			{
				continue;
			}
			//若当前请求距离更短且未被访问过，则指向当前请求
			if ((abs(point->number - begin) > abs(request[j]->number - begin)) && request[j]->finish == false)
			{
				point = request[j];
			}
		} 
		//加入已访问队列
		visit[i]->number = point->number;
		visit[i]->distance = abs(begin - point->number);
		//跟新磁头位置，并标记已访问
		begin = point->number;
		point->finish = true;
		//若到头，则掉头
		if (direction == false && point->number == max)
		{
			direction = true;
		}
		if (direction == true && point->number == min)
		{
			direction = false;
		}
	}
	return;
}

void show_option()
{
	cout << "\n****************************" << endl;
	cout << "******    算法选择    ******" << endl;
	cout << "****** 1、FCFS算法    ******" << endl;
	cout << "****** 2、SSTF算法    ******" << endl;
	cout << "****** 3、SCAN算法    ******" << endl;
	cout << "****** 4、退出        ******" << endl;
	cout << "****************************\n" << endl;
}

void show_visit(Visit** visit, int num, int begin)
{
	cout << "—————————————" << endl;
	cout << "     从" << begin << "号磁道开始" << endl;
	cout << "  ———————————  " << endl;
	cout << "被访问磁道号\t移动距离" << endl;
	for (int i = 0; i < num; i++)
	{
		cout << "    " << visit[i]->number << "\t\t  " << visit[i]->distance << endl;
	}


	float ans = 0;
	for (int i = 0; i < num; i++)
	{
		ans += visit[i]->distance;
	}
	//保留两位小数点后两位
	cout << "  ———————————  " << endl;
	cout << "   平均寻道长度：" << fixed << setprecision(2) << ans/num << endl;
	cout << "—————————————" << endl;
}

//Request和Visit复位
void reset(Request** request, Visit** visit, int num)
{
	for (int i = 0; i < num; i++)
	{
		request[i]->reset();
		visit[i]->reset();
	}
	return;
}

int main()
{
	int num, temp, begin;
	Request* request[100];
	Visit* visit[100];
	cout << "请输入请求总数：";
	cin >> num;
	cout << "请输入请求序列：";
	for (int i = 0; i < num; i++)
	{
		cin >> temp;
		request[i] = new Request(temp);
		visit[i] = new Visit();
	}
	cout << "请输入开始磁道号：";
	cin >> begin;

	int flag;
	while (true)
	{
		show_option();
		cout << "请选择功能：";
		cin >> flag;
		if (flag == 1)
		{
			//FCFS算法
			reset(request, visit, num);
			FCFS(request, visit, num, begin);
			show_visit(visit, num, begin);
		}
		else if (flag == 2)
		{
			//SSTF算法
			reset(request, visit, num);
			SSTF(request, visit, num, begin);
			show_visit(visit, num, begin);
		}
		else if (flag == 3)
		{
			//SCAN算法
			bool direction;
			cout << "请输入移动方向（0.由里向外 1.由外向里）：";
			cin >> direction;
			reset(request, visit, num);
			SCAN(request, visit, num, begin, direction);
			show_visit(visit, num, begin);
		}
		else if (flag == 4)
		{
			//退出
			cout << "成功退出！" << endl;
			break;
		}
	}
	return 0;
}

运行演示：

【小结或讨论】

FCFS、SSTF、SCAN三个磁盘调度算法的难度是依次递增的，理解它们的原理并不困难，但是要代码实现却有很多细节之处需要考虑。在这次实验中，我建立了两个类：一是进程请求类Request，包含两个成员变量，磁道号int number、是否完成访问bool finish；二是磁盘访问类Visit，包含两个成员变量，被访问的磁道号int number、移动距离int distance，这个类的作用是记录访问顺序和移动距离。

我想在这记录一下SCAN算法的实现思路，因为这可以说是三个算法中最难的了。首先要找到最小和最大的磁道号，这表示是边界，如果我们扫描到边界就需要转头了。接着对于visit的每一个值，我们需要遍历整个request，找出符合当前方向的、最近的一个要求访问的磁道号。这里我主要在SSTF算法基础上加了一个if语句，即如果是由里向外且该请求磁道号小于磁头所在磁道号或者由外向里且该请求磁道号大于磁头所在磁道号，那么就跳过这一个请求。在找到符合当前方向的、最近的一个要求访问的磁道号后，我们除了要访问该磁道并作标记后，还要检查是不是到了边界，如果到了边界还需要反转扫描方向。SCAN的大致思路就是如此。

对于三者优缺点的比较。对于FCFS算法，即先来先服务，是最直接、简单、公平的，但是这显然不够合理。所以我们有了SSTF算法，即最短寻道优先，每次访问离当前磁头所在磁道最近的要求访问磁道。书中的例子举的其实不是很好，即没有显示出“饥饿”现象，也显示得和SCAN算法很相似，容易让人误解。言归正传，FCFS存在“饥饿”现象，即如果有新请求不断出现在磁头附近，这就导致一直在处理磁头附近的请求，而远处的请求会处于等待状态。为了解决这个现象，我们又有了SCAN算法，这个说白了就是来回扫描整个磁盘，固定一个方向直到遇到边界才回头，很好简单也很好理解但是却解决了“饥饿”现象这个大问题。

今天的文章操作系统实验6 磁盘调度模拟分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。