磁盘扫描算法scan实现
时间: 2023-10-15 19:02:05 浏览: 35
磁盘扫描算法scan是一种磁盘调度算法,也被称为电梯算法。它的思想是让磁头在一个方向上移动,直到遇到最远的磁道,然后改变方向,直到移动到另一个极端,重复进行。
具体实现如下:
1. 确定初始时磁头所在的磁道及移动方向(向外或向内);
2. 在一个方向上扫描磁道,将请求队列中与当前磁头位置同方向的磁道请求按磁道号从小到大排序;
3. 如果当前方向上已经扫描完所有请求,将磁头移动到另一个方向的最小磁道,并改变移动方向;
4. 重复第2、3步,直到所有的请求都被满足。
代码实现:
```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void scan(int start, vector<int> requests) {
int n = requests.size();
vector<int> left, right;
for (int i = 0; i < n; i++) {
if (requests[i] < start) {
left.push_back(requests[i]);
} else {
right.push_back(requests[i]);
}
}
sort(left.begin(), left.end());
sort(right.begin(), right.end());
int head = start, total = 0;
bool direction = true; // true: move right; false: move left
while (true) {
if (direction) {
for (int i = 0; i < right.size(); i++) {
if (right[i] >= head) {
total += right[i] - head;
head = right[i];
cout << head << " ";
}
}
if (left.size() == 0) break;
total += head - left[0];
head = left[0];
cout << head << " ";
direction = false;
} else {
for (int i = left.size() - 1; i >= 0; i--) {
if (left[i] <= head) {
total += head - left[i];
head = left[i];
cout << head << " ";
}
}
if (right.size() == 0) break;
total += right[right.size() - 1] - head;
head = right[right.size() - 1];
cout << head << " ";
direction = true;
}
}
cout << endl << "Total head movement: " << total << endl;
}
int main() {
int start = 50;
vector<int> requests = {98, 183, 37, 122, 14, 124, 65, 67};
scan(start, requests);
return 0;
}
```
上述代码实现了一个简单的磁盘扫描算法scan。其中,start表示初始磁头位置,requests为请求队列,vector left和right分别存储与当前磁头位置同方向的磁道请求,direction表示移动方向,total记录总磁头移动距离。函数scan按上述步骤实现磁盘扫描算法,并输出扫描顺序和总磁头移动距离。