先决条件: 磁盘调度算法和SCAN磁盘调度算法
给定一系列磁盘磁道编号和初始磁头位置, 我们的任务是查找为访问所有请求的磁道而执行的查找操作总数扫描使用磁盘调度算法。
什么是C-SCAN(圆形电梯)磁盘调度算法?
循环SCAN(C-SCAN)调度算法是SCAN磁盘调度算法的改进版本, 它通过更均匀地处理请求来解决SCAN算法的效率低下的问题。像SCAN(电梯算法)一样, C-SCAN将头从服务所有请求的一端移到另一端。但是, 一旦磁头到达另一端, 它将立即返回磁盘的开头, 而无需处理返回行程上的任何请求(请参见下图), 并且一旦到达起点, 便再次开始维护。这也被称为"圆形电梯算法", 因为它本质上将圆柱体视为从最终圆柱体到第一个圆柱体环绕的圆形列表。
算法:
- 让Request数组表示一个数组, 该数组存储已按其到达时间的升序请求的音轨的索引。 "磁头"是磁盘磁头的位置。
- 磁头仅在从0到磁盘大小的正确方向上服务。
- 在向左移动时, 请勿维修任何轨道。
- 当我们到达起点(左端)时, 反转方向。
- 沿正确方向移动时, 它为所有轨道提供一对一服务。
- 沿正确方向移动时, 计算轨道与头部的绝对距离。
- 以此距离增加总寻道数。
- 当前服务的轨道位置现在变为新的头位置。
- 转到步骤6, 直到到达磁盘的右端。
- 如果我们到达磁盘的右端, 请反转方向, 然后转到步骤3, 直到未维修请求数组中的所有轨道。
例子:
Input:
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50
Output:
Initial position of head: 50
Total number of seek operations = 190
Seek Sequence is
60
79
92
114
176
199
0
11
34
41
下表显示了使用SCAN服务请求的曲目的顺序。
因此, 总寻道数计算如下:
= (60-50)+(79-60)+(92-79)
+(114-92)+(176-114)+(199-176)+(199-0)
+(11-0)+(34-11)+(41-34)
实现
下面给出C-SCAN算法的实现。
注意:
距离变量用于存储磁头和当前磁道位置之间的绝对距离。 disk_size是磁盘的大小。左向量和右向量分别将所有请求轨迹存储在初始头部位置的左侧和右侧。
#include <bits/stdc++.h>
using namespace std;
// Code by Vikram Chaurasia
// C++ program to demonstrate
// C-SCAN Disk Scheduling algorithm
int size = 8;
int disk_size = 200;
void CSCAN(int arr[], int head)
{
int seek_count = 0;
int distance, cur_track;
vector<int> left, right;
vector<int> seek_sequence;
// appending end values
// which has to be visited
// before reversing the direction
left.push_back(0);
right.push_back(disk_size - 1);
// tracks on the left of the
// head will be serviced when
// once the head comes back
// to the beggining (left end).
for (int i = 0; i < size; i++) {
if (arr[i] < head)
left.push_back(arr[i]);
if (arr[i] > head)
right.push_back(arr[i]);
}
// sorting left and right vectors
std::sort(left.begin(), left.end());
std::sort(right.begin(), right.end());
// first service the requests
// on the right side of the
// head.
for (int i = 0; i < right.size(); i++) {
cur_track = right[i];
// appending current track to seek sequence
seek_sequence.push_back(cur_track);
// calculate absolute distance
distance = abs(cur_track - head);
// increase the total count
seek_count += distance;
// accessed track is now new head
head = cur_track;
}
// once reached the right end
// jump to the beggining.
head = 0;
// Now service the requests again
// which are left.
for (int i = 0; i < left.size(); i++) {
cur_track = left[i];
// appending current track to seek sequence
seek_sequence.push_back(cur_track);
// calculate absolute distance
distance = abs(cur_track - head);
// increase the total count
seek_count += distance;
// accessed track is now the new head
head = cur_track;
}
cout << "Total number of seek operations = "
<< seek_count << endl;
cout << "Seek Sequence is" << endl;
for (int i = 0; i < seek_sequence.size(); i++) {
cout << seek_sequence[i] << endl;
}
}
// Driver code
int main()
{
// request array
int arr[size] = { 176, 79, 34, 60, 92, 11, 41, 114 };
int head = 50;
cout << "Initial position of head: " << head << endl;
CSCAN(arr, head);
return 0;
}
Output:
Initial position of head: 50
Total number of seek operations = 190
Seek Sequence is
60
79
92
114
176
199
0
11
34
41