操作系统实验4—磁盘调度

文章目录

操作系统实验4—磁盘调度

实验描述

实验内容：

编写一个磁盘调度程序，模拟操作系统对磁盘的调度。

实验目的：

本实验要求学生独立设计并实现磁盘调度模拟程序，以加深对磁盘调度特点和各种磁盘调度算法的理解。

实验要求：

可以随机输入磁道请求序列，当前磁头位置和磁头移动方向，支持先来先服务、最短寻道时间优先、扫描、循环扫描调度算法，能够输出磁头移动经过的磁道序列。具体信息见测试用例格式说明。

测试用例格式如下：

输入：

磁盘调度算法
当前磁头位置
磁头移动方向
磁道请求序列（磁道1,磁道2,磁道3,...)              

其中：
(1) 调度算法选项为：
    1----先来先服务
    2----最短寻道时间优先
    3----扫描法
    4----循环扫描法

(2) 磁头移动方向选项为：
    1----向磁头号增大方向移动
    0----向磁头号减小方向移动

输出：

磁头移动经过的磁道序列（磁道1，磁道2，磁道3）
磁头移动经过的总磁道数

	测试输入	期待的输出	时间限制	内存限制
测试用例 1	1 53 1 98,183,37,122,14,124,65,67	53,98,183,37,122,14,124,65,67 640	1秒	64M
测试用例 2	2 53 1 98,183,37,122,14,124,65,67	53,65,67,37,14,98,122,124,183 236	1秒	64M
测试用例 3	3 53 1 98,183,37,122,14,124,65,67	53,65,67,98,122,124,183,37,14 299	1秒	64M
测试用例 4	4 53 1 98,183,37,122,14,124,65,67	53,65,67,98,122,124,183,14,37 322	1秒	64M

设计思路

虽然每次输入的磁道数据只有磁道位置，但是在算法中需要计算每个磁道距离当前磁头的位置，以及最短寻道时间优先算法中还有记录该磁道是否已经访问过，所以依然采用结构体数组的形式将需要用到的信息全部存储起来。

struct node
{
	int positon;//磁道位置
	int moved;	//磁道与当前磁头的距离
	int visit;	//磁道是否被访问过
}que[1010];		//初始磁道序列

程序概要设计如下：

main（）函数是主程序的入口，控制程序流程，按照输入的调度信号选择相应的算法模块进行运行，并输出相应的结果
input（）函数是输入函数，接受程序输入
output（）函数是输出函数，将磁头移动的信息进行输出
dis（）函数是计算两个磁道之间绝对值的函数
FCFS（）函数是先来先服务算法，磁头按照磁道到来的顺序进行移动
SSTF（）函数是最短寻道时间优先算法，每次找出距当前磁头距离最短的磁道进行移动
SCAN（）是扫描法，又称“电梯法”。每次将磁头按照电梯的方式朝一个方向移动，到顶点后按相反方向折回
CSCAN（）函数是循环扫描法，每次将磁头按照电梯的方式朝一个方向移动，到顶点后直接移动到相反方向的顶点，继续沿着此方向移动

int main();		//主程序入口
void input();	//输入函数
void output();	//输出函数
int dis(int a, int b);//两个磁道距离的绝对值
void FCFS();//先来先服务
void SSTF();//最短寻道时间优先
void SCAN();//扫描法
void CSCAN();//循环扫描法

上机代码

代码使用 C++ 语言进行编写

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node
{
	int positon;//磁道位置
	int moved;//磁道与当前磁头的距离
	int visit;//磁道是否被访问过
}que[1010];//初始磁道序列
void input();//输入函数
void output();//输出函数
int dis(int a, int b);//两个磁道距离的绝对值
void FCFS();//先来先服务
void SSTF();//最短寻道时间优先
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 main()
{
	//程序输入
	input();

	//选择算法
	switch (sig)
	{
		case 1:FCFS(); break;
		case 2:SSTF(); break;
		case 3:SCAN(); break;
		case 4:CSCAN(); break;
	}
	//程序输出
	output();

	return 0;
}
void input()
{
	//freopen("osin.txt", "r", stdin);
	//freopen("osout.txt", "w", stdout);

	sig = 0;
	cin >> sig;	//算法选择标志

	start = 0;
	total = 0;
	cin >> start;//初始磁头位置
	cin >> direction;//磁头移动方向

	num = 0;
	char c;
	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;
		}
	}
}
void output()
{
	for (int i = 0; i <= num; i++)//磁头移动经过的磁道序列
	{
		if (i != num)
		{
			printf("%d,", order[i]);
		}
		else
		{
			printf("%d\n", order[i]);
		}
	}
	printf("%d\n", total);//磁头移动经过的总磁道数
}
int dis(int a, int b)
{
	return abs(a - b);
}
void FCFS()
{
	order[0] = start;
	for (int i = 0; i < num; i++)
	{
		que[i].moved = dis(que[i].positon, start);//计算磁头移动距离
		order[i + 1] = que[i].positon;//更新访问序列
		total += que[i].moved;//计算移动的总磁道数
		start = order[i + 1];//更新当前磁头位置
	}
}
void SSTF()
{
	int mini;//距磁头距离最短的磁道号
	
	order[0] = start;
	//选择num次最短距离
	for (int i = 0; i < num; i++)
	{
		//计算本次距离
		for (int j = 0; j < num; j++)
		{
			if (que[j].visit == noVis)//磁道没被访问过则与当前位置计算距离
			{
				que[j].moved = dis(que[j].positon, start);
			}
			else//否则把距离置为无穷大0x3f3f3f
			{
				que[j].moved = 0x3f3f3f;
			}
		}
		//找到本次的最短磁道
		mini = 0;
		for (int k = 0; k < num; k++)
		{
			if (que[k].moved == 0x3f3f3f)//遇到0x3f3f3f就跳过
			{
				continue;
			}
			if (que[mini].moved > que[k].moved)//找到最短距离的磁道
			{
				mini = k;
			}
		}
		//更新访问信息
		order[i + 1] = que[mini].positon;
		que[mini].moved = dis(que[mini].positon, start);
		total += que[mini].moved;
		que[mini].visit = isVis;
		start = que[mini].positon;
	}
}
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];
			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));
	}
}

测试结果

程序采用黑盒测试的方式，提交到 OJ 系统上进行在线评测

可以看到，OJ 的测试用例全部通过

心得体会

通过本次实验，上机代码模拟实现了四种磁盘调度算法，对操作系统内部的磁盘调度方式有了更深刻的认识和感受。SCAN 扫描法，从当前磁道沿着选定方向一直扫描到最外/内圈，直到没有要访问的磁道在沿反方向扫描，再沿反方向扫描。CSCAN 循环扫描法，自开始磁道始终沿一个方向扫描，直到没有要访问的磁道再从最里圈或最外圈扫描。因为计算磁头每次的距离一定是正数，所以特别写了一个计算距离的绝对值函数保证了计算数据的可靠性。计算循环扫描时，由数学逻辑推导出了相应的计算公式，让程序显得更加地简洁和高效。