磁盘调度算法的模拟实现
1、先来先服务法（FCFS）
实现思路： 这是一种最简单但也是效率最低的磁盘调度算法，通过依次读取要访问的磁盘序号即可实现。
void FCFS(int*seq, int start)
{
int mov = 0;
//移动的总磁道数
int temp;
//当前磁头的位置
cout << "------FCFS------" << endl;
cout << "磁头移动的轨迹：" << endl;
temp = start;
for(int i=0;
i;
i++)
{
cout << temp << ' ';
mov+= abs(seq[i] - temp);
temp = seq[i];
}
cout << temp << endl;
cout << "磁头移动的总磁道数：" << mov << endl;
}
【磁盘调度算法的模拟实现】2、最短寻道时间优先法（SSTF）
实现思路： 先对要访问的磁盘序列按磁盘序号升序的方式进行排序，其次每次访问与当前磁头的相对位置最小的磁盘，直至序列访问完毕。
实现举例：
文章图片
void SSTF(int*seq, int start)
{
int min;
//当前序号最小的磁道
int left;
//往左的第一个位置
int right;
//往右的第一个位置
int location;
//磁道序列中不大于开始磁道的位置
int temp;
int mov = 0;
//移动的总磁道数
int check_seq[10];
//为了复制请求访问的磁道序列
for (int i = 0;
i < seq_sum;
i++)//复制请求访问的磁道序列
check_seq[i] = seq[i];
for (int i = 0;
i < seq_sum;
i++)//对请求访问的磁道序列按升序进行排序
{
min = check_seq[i];
for (int j = i;
j < seq_sum;
j++)
{
if (check_seq[j] < min)
{
temp = min;
min = check_seq[j];
check_seq[j] = temp;
}
}
check_seq[i] = min;
}
location = -1;
for (int i = 0;
i < seq_sum;
i++)//查找start在该序列中的位置
{
if (check_seq[i] > start)
break;
location++;
}
temp = start;
left = location;
right= location + 1;
cout << "------SSTF------" << endl;
cout << "磁头移动的轨迹：" << endl;
while (left >= 0 && right < seq_sum)//左边或右边寻道完毕
{
if (abs(temp - check_seq[left]) <= abs(temp - check_seq[right]))
{
mov += abs(temp - check_seq[left]);
cout << temp << ' ';
temp = check_seq[left];
left--;
}
else
{
mov += abs(temp - check_seq[right]);
cout << temp << ' ';
temp = check_seq[right];
right++;
}
}
while (left >=0)//一直左寻
{
mov += abs(temp - check_seq[left]);
cout << temp << ' ';
temp = check_seq[left];
left--;
}
while (right < seq_sum)//一直右寻
{
mov += abs(temp - check_seq[right]);
cout << temp << ' ';
temp = check_seq[right];
right++;
}
cout <3、电梯法（扫描法）
实现思路： 先对要访问的磁盘序列按磁盘序号升序进行排序，其次只需一次找寻与开始磁头的相对位置最小的磁盘，然后，一直往该方向访问需要访问的磁盘，直至访问完毕。接着，访问另一方向要访问的磁盘，直至访问完毕。
实现举例：
文章图片
特点： 与最短寻道时间优先算法的实现基本一样，但它解决了磁头回溯的问题，即只需在刚开始时，一次判断要访问的是哪个磁盘（判断初始的访问方向），接着往该方向依次访问所需访问的磁盘。
void ElEV(int*seq, int start)
{
int min;
//当前序号最小的磁道
int location;
//磁道序列中不大于开始磁道的位置
int temp;
int mov = 0;
//移动的总磁道数
int check_seq[10];
//为了复制请求访问的磁道序列
for (int i = 0;
i < seq_sum;
i++)//复制请求访问的磁道序列
check_seq[i] = seq[i];
for (int i = 0;
i < seq_sum;
i++)//对请求访问的磁道序列按升序进行排序
{
min = check_seq[i];
for (int j = i;
j < seq_sum;
j++)
{
if (check_seq[j] < min)
{
temp = min;
min = check_seq[j];
check_seq[j] = temp;
}
}
check_seq[i] = min;
}
location = -1;
for (int i = 0;
i < seq_sum;
i++)//查找start在该序列中的位置
{
if (check_seq[i] > start)
break;
location++;
}
temp = start;
cout << "------ELEV------" << endl;
cout << "磁头移动的轨迹：" << endl;
if (location == -1)//磁头在最左边
{
for (int i = 0;
i < seq_sum;
i++)
{
cout << temp << ' ';
mov += abs(temp - check_seq[i]);
temp = check_seq[i];
}
cout << temp << endl;
}
else if (location == 9)//磁头在最右边
{
for (int i = seq_sum - 1;
i >= 0;
i--)
{
cout << temp << ' ';
mov += abs(temp - check_seq[i]);
temp = check_seq[i];
}
cout << temp << endl;
}
else//在中间
{
if (abs(check_seq[location] - start) <= abs(check_seq[location + 1] - start))//先往左扫描
{
for (int i = location;
i >= 0;
i--)
{
cout << temp << ' ';
mov += abs(temp - check_seq[i]);
temp = check_seq[i];
}
for (int i = location + 1;
i < seq_sum;
i++)
{
cout << temp << ' ';
mov += abs(temp - check_seq[i]);
temp = check_seq[i];
}
cout << temp << endl;
}
else//先往右扫描
{
for (int i = location + 1;
i < seq_sum;
i++)
{
cout << temp << ' ';
mov += abs(temp - check_seq[i]);
temp = check_seq[i];
}
for (int i = location;
i >= 0;
i--)
{
cout << temp << ' ';
mov += abs(temp - check_seq[i]);
temp = check_seq[i];
}
cout << temp << endl;
}
}
cout << "磁头移动的总磁道数：" << mov << endl;
}4、主函数代码
#include
#include
using namespace std;
void FCFS(int*, int);
//先来先服务法
void SSTF(int*, int);
//最短寻道时间优先法
void ElEV(int*, int);
//电梯法int seq_sum;
//序列中请求访问的磁道总数int main()
{
int seq[] = { 45,23,67,2,9,89,165,49,80,77 };
//要请求访问的磁道序列
int start;
//磁道的开始位置
seq_sum =sizeof(seq)/sizeof(int);
start = rand() % 200+1;
//随机选择一个磁道开始位置
FCFS(seq, start);
//先来先服务法
SSTF(seq, start);
//最短寻道时间优先法
ElEV(seq, start);
//电梯法
}
5、运行结果
文章图片
6、总结
磁盘调度算法比较容易理解，实现也比较容易。
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 简谈迪克斯特拉算法