操作系统实验——移动头磁盘调度算法模拟实现与比较

1、实验目的

? 理解并掌握主要的移动头磁盘调度算法的基本设计思想和编程实现要旨。

2、实验内容

? 利用标准 C 语言，编程设计与实现关于移动头磁盘调度的先来先服务调度算法（FCFS）、最短寻道时间优先调度算法（SSTF）、电梯调度算法（SCAN）、循环式单向电梯调度算法（CSCAN）、双队列电梯调度算法（FSCAN），并随机发生一组磁盘访问事件（磁道号）序列，开展有关算法的测试及性能比较。

3、开发环境

? Vs 2021+Windows操作系统

4、算法流程和实现方法

FCFS（先来先服务）

• 关键数据结构：
  • 仅需要请求队列即可，按照请求顺序进行处理。
• 算法流程：
  • 请求按照到达的顺序依次处理。
  • 磁头从当前位置移动到下一个请求所在的磁道。
  • 移动完成后，继续处理下一个请求，直至队列中的所有请求被满足。

SSTF（最短寻道时间优先）

• 关键数据结构：
  • 请求队列，当前磁头位置。
• 算法流程：
  • 每次选择离当前磁头位置最近的请求来处理。
  • 算法优先处理离当前磁头最近的磁道，最大限度地减少寻道时间。
  • 该算法可能导致某些请求长期等待，产生"饥饿"问题。

SCAN（扫描算法）

• 关键数据结构：
  • 请求队列，当前磁头位置。
• 算法流程：
  • 磁头按照一个方向（通常是向某一方向移动）扫描所有请求。
  • 当达到最边缘时，方向改变并继续扫描，而不返回到最初的位置。
  • 这个算法可能导致某些磁道长期无法被访问到（产生"电梯"效应）。

CSCAN（循环扫描算法）

• 关键数据结构：
  • 请求队列，当前磁头位置。
• 算法流程：
  • 类似于SCAN，但是在到达最边缘后，直接回到另一端而不是返回最初的位置。
  • 这样做有助于减少某些磁道长期无法访问的情况，减少"电梯"效应。

FSCAN（双重扫描算法

• 关键数据结构：
  • 两个请求队列，分别为当前进行的队列和等待的队列。
• 算法流程：
  • 将所有请求分为两个队列，在处理当前队列的同时，后续请求进入等待队列。
  • 当前队列处理完毕后，切换到等待队列处理请求。
  • 这种方法减少了某些请求长时间等待的情况，减轻了"饥饿"和"电梯"效应。

5、技术难点及解决方案

算法效率与性能

• 难点：算法的效率和性能是关键指标，但不同算法在不同场景下的表现可能不同。

• 解决方案：进行实际测试和性能评估，比较不同算法在不同数据集和工作负载下的表现。根据实验结果优化算法选择，或者结合多种算法实现智能调度机制。

  算法的正确性

• 难点：确保算法的正确性和稳定性，避免出现错误和异常情况。

• 解决方案：进行严格的测试和验证，针对各种边界条件和极端情况对算法进行全面测试，确保算法在各种情况下都能正确运行并且表现稳定。

6、运行截图

性能比较：

FCFS：

• 优点：简单易实现。
• 缺点：可能会导致平均寻道时间较长，因为它忽略了寻找最优路径的可能性。

SSTF：

• 优点：最小化了磁头移动距离，平均寻道时间较短。
• 缺点：可能产生"饥饿"问题，某些请求长时间等待。

SCAN：

• 优点：减少了某些磁道长期无法访问的情况。
• 缺点：可能导致某些请求长时间等待，产生"电梯"效应。

CSCAN：

• 优点：减少了某些磁道长期无法访问的情况。
• 缺点：与SCAN类似，可能产生长时间等待的情况。

FSCAN：

• 优点：减轻了"饥饿"和"电梯"效应，提高了公平性。
• 缺点：实现相对复杂。

7、源代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
const int maxRightValue = 199;//磁头移动的最右边界值
const int minLeftValue = 0;//磁头移动的最左边界值
vector<int> FSCAN_SHOW;//存放FSCAN_SHOW算法的访问顺序

void getRandomNumber(vector<int>& randValue, int& pos)
{
	
	for (int i = 0; i < 100; i++)
		randValue.push_back(rand() % 200);
	pos = rand() % 200;
}
//输入 请求访问序列和磁头所在位置
//输出 移动磁道数
void Show(const string& str, const vector<int>& t)
{
	cout << str << "的访问序列为:";
	for (int i = 0; i < t.size(); i++)
	{
		if (i != t.size() - 1)
			cout << t[i] << "->";
		else
			cout << t[i] << endl;
	}
}

int FCFS(const vector<int>& t, int pos)
{
	int sum = 0;
	Show("FCFS", t);
	for (int i = 0; i < t.size(); i++)
	{
		sum += abs(pos - t[i]);
		pos = t[i];
	}
	return sum;
}
int findClose(const vector<int>& t, int pos)
{
	int minDistance = INT_MAX;
	int index = -1;
	for (int i = 0; i < t.size(); i++)
	{
		if (t[i] == -1)continue;
		int distance = abs(pos - t[i]);
		if (minDistance > distance)
		{
			minDistance = distance;
			index = i;
		}
	}
	return index;
}
int SSTF(vector<int> t, int pos)
{
	vector<int> show;
	int sum = 0;
	for (int i = 0; i < t.size(); i++)
	{
		int index = findClose(t, pos);
		if (index == -1)
		{
			break;
		}
		else
		{
			show.push_back(t[index]);
			sum += abs(pos - t[index]);
			pos = t[index];
			t[index] = -1;
		}
	}
	Show("SSTF", show);
	return sum;
}
int FindLarger(vector<int>& t, int pos)
{
	int index = -1;
	for (int i = 0; i < t.size(); i++)
	{
		if (pos <= t[i])
		{
			index = i;
			break;
		}
	}
	return index;
}
//假设磁盘指针总是向右移动
pair<int, int> SCAN(vector<int> t, int pos, int flag = 1)
{
	int sum = 0;
	vector<int> left, right;
	vector<int> show;
	for (auto e : t)
	{
		if (e < pos)
		{
			left.push_back(e);
		}
		else
		{
			right.push_back(e);
		}
	}
	sort(left.begin(), left.end());
	sort(right.begin(), right.end());
	for (auto e : right)
	{
		show.push_back(e);
	}
	sum += maxRightValue - pos;
	if (!left.empty())
	{
		sum += maxRightValue - left[0];
		reverse(left.begin(), left.end());

		for (auto e : left)
		{
			show.push_back(e);
		}
	}
	if (flag)
	{
		Show("SCAN", show);
	}
	else
	{
		for (auto e : show)
		{
			FSCAN_SHOW.push_back(e);
		}
	}
	pair<int, int> res;
	res.first = sum;
	res.second = pos;
	return res;
}
int CSCAN(vector<int> t, int pos)
{
	int sum = 0;
	vector<int> left, right;
	vector<int> show;
	for (auto e : t)
	{
		if (e < pos)
		{
			left.push_back(e);
		}
		else
		{
			right.push_back(e);
		}
	}
	sort(left.begin(), left.end());
	sort(right.begin(), right.end());
	for (auto e : right)
	{
		show.push_back(e);
	}
	sum += maxRightValue - pos + 200;
	if (!left.empty())
	{
		for (auto e : left)
		{
			show.push_back(e);
		}
		sum += left.back();
	}
	Show("CSCAN", show);

	return sum;
}
//将前50个请求划分为当前正在进行的队列，后50个请求划分为扫描期间请求磁盘调度的进程

int FSCAN(vector<int> t, int pos)
{
	int sum = 0;
	vector<int> t1(t.begin(), t.begin() + 50);
	vector<int> t2(t.begin() + 50, t.begin() + 100);
	const pair<int, int>& temp = SCAN(t1, pos, 0);
	sum += temp.first;
	sum += SCAN(t2, temp.second, 0).first;
	Show("FSCAN", FSCAN_SHOW);
	return sum;
}
int main()
{

	int pos = 0;
	vector<int> randValue;
	srand((unsigned)time(NULL));
	getRandomNumber(randValue, pos);

	cout << "FCFS的平均寻道数为:" << FCFS(randValue, pos) / 100 << endl;
	cout << endl;

	cout << "SSTF的平均寻道数为:" << SSTF(randValue, pos) / 100 << endl;
	cout << endl;

	cout << "SCAN的平均寻道数为:" << SCAN(randValue, pos).first / 100 << endl;
	cout << endl;

	cout << "CSCAN的平均寻道数为:" << CSCAN(randValue, pos) / 100 << endl;
	cout << endl;

	cout << "FSCAN的平均寻道数为:" << FSCAN(randValue, pos) / 100 << endl;
	cout << endl;
	return 0;
}