使用C语言完成磁盘调度算法中的 最短寻道时间优先调度算法 和 电梯调度算法 ！
假设进程请求的访问磁盘的磁道序列号为：100 55 58 39 18 90 160 150 38 184
请输出采用不同算法时访问的磁道号，并计算平均寻道长度。
挑了两个相对简单的磁盘调度算法, 模拟可解, 不考虑时间复杂度的情况下都可以暴力搜索.
(天天都在写暴力, 只会暴力了QAQ.
借这个实验作业来书写一下磁盘的两个调度算法 – 最短寻道时间优先调度算法
(
S
S
T
F
)
(SSTF)
(SSTF)和电梯调度算法
(
S
C
A
N
)
(SCAN)
(SCAN).
平均寻道长度: 总共走的磁道数 / 更改磁道的次数.
平均寻道时间: 平均寻道长度 * 移动每道的单位时间
一. 最短寻道时间优先调度
(
S
S
T
F
)
(SSTF)
(SSTF)
怎么个实现过程? 从最开始的磁道开始时, 每次都寻找到离当前位置最近的磁道. (你没有看错, 就是这么简单. 过程可结合输出来理解. 那么直接贴上代码.
#include#define getpch(type) (type*)malloc(sizeof(type)) using namespace std; struct _list{ //构造能够双向遍历的链表结构体 struct _list* left; int val; struct _list* right; }; struct _list* ide; //确定“头”指针 int cnt, first; double run; //步长记录 vector nums; //存储磁道号 void _input(){ //输入 cin >> first; vector vec(1, first); while(cin >> cnt) vec.emplace_back(cnt); nums = vec; //vec可删除 } void left_work(){ ide = ide->left; //输出操作 cout << setw(14) << ide->val; cout << " "; cout << setw(8) << ide->right->val-ide->val << endl; run += ide->right->val-ide->val; //删除节点（如果从节点A离开，那么A节点被删除 struct _list* p = ide->right; if(ide->right->right) ide->right->right->left = ide; ide->right = ide->right->right; free(p); //释放指针空间 } void right_work(){ ide = ide->right; //输出操作 cout << setw(14) << ide->val; cout << " "; cout << setw(8) << ide->val-ide->left->val << endl; run += ide->val-ide->left->val; //删除节点（如果从节点A离开，那么A节点被删除 struct _list* p = ide->left; if(ide->left->left) ide->left->left->right = ide; ide->left = ide->left->left; free(p); //释放指针空间 } // void debug(){ // struct _list* head = ide; // while(head->left) head=head->left; // while(head) {cout << head->val << ' '; head=head->right;} // cout << endl; // } void Print(){ int n = nums.size() - 1; cout << "start: " << ide->val << endl; cout << "the next place len nums" << endl; while(ide->left || ide->right){ //因为当左右都不具有节点时，我们没法离开，所以会“死”，那么我提前结束就好了，反正也遍历完成了 int cnt = ide->val; //寻找left和right近的那个, 并基于相应的操作 if(!ide->left && ide->right) right_work(); //如果没有更小的了 else if(!ide->right && ide->left) left_work(); //如果没有更大了了 else if(ide->right && ide->left) cnt-ide->left->val < ide->right->val-cnt?left_work():right_work(); //存在小的节点并且存在大的节点 // debug(); } cout << setiosflags(ios::fixed) << setprecision(1) << "平均寻道时间: " << run / (nums.size()-1) << endl; } void _work(){ sort(nums.begin(), nums.end()); struct _list* l = NULL; // for(auto ao : nums) cout << ao << " "; for(auto ao : nums){ struct _list* _list_ = getpch(struct _list); if(ao == first) ide = _list_; //标记head节点 _list_->val = ao; //赋值 //链表的建立, 左右索引指针的赋值（能够双向遍历的链表 if(l) l->right = _list_; _list_->left = l; l = _list_; }l->right = NULL; // debug(); Print(); } signed main(void){ //这样书写的优点，时间复杂度小nlog(n), 用桶排可压缩到n freopen("in.txt","r",stdin); //100 55 58 39 18 90 160 150 38 184 freopen("SSTFout.txt","w",stdout); _input(); _work(); return 0; }
这里使用的是建立一个从小到大排好顺序的 可以双向的寻址的链表. 然后每一次更改位置都删除上一个节点. 这样每次寻找都只需要比较 l e f t left left 和 r i g h t right right 的大小就好了. 这样写主要为了降低时间复杂度.
你也可以不对读取的数据进行处理, 而是每次都寻找未被索引的离当前位置最近的磁道(从头到尾查找). 但是这样就会造成极高的时间复杂度. (这样书写很简单, 你也不需要建立链表, 只需要一个数组就可以了. 如果你不在乎时间复杂度建议就暴力查询. 主体的代码片段如下:
bool bo[100]; //标记是否被索引过
int nums[100]; //记录需要索引的磁道号
int first; //第一个磁道
int ide; //标记下一个索引的位置, 初始等于first的下标
int sum = 0; //标记索引过的个数
while(sum < n){ //n表示需要索引的总的磁道个数
int cnt = INT_MAX, ans;
for(int i = 0;i < n;i ++){ //每次都暴力寻找离当前位置最近的磁道
if(cnt < abs(nums[i] - nums[ide]) && bo[i]){
cnt = abs(nums[i] - nums[ide]), ans = i;
}
}
//nums[ans]
bo[ans] = true, ide = ans;
}
给出第一个使用双向链表遍历得到的结果:
start: 100
the next place len nums
90 10
58 32
55 3
39 16
38 1
18 20
150 132
160 10
184 24
平均寻道时间: 27.6
最短寻道时间优先调度算法本身存在的问题: 因为我的示例都是给好了需要访问的磁道, 而未进行后续添加. 实际过程中, 我们需要访问的磁道都是一个动态的过程. 假若我们每次到达指定的磁道后, 又在附近的磁道发出了请求, 那么远的磁道就可能一直存在不访问的情况. 也就是"饥饿"现象.
二. 电梯调度算法
(
S
C
A
N
)
(SCAN)
(SCAN)
使用电梯调度算法,我们必须在最开始就给定一个向外还是向里寻找的优先级. 然后在这个优先级的作用下, 寻找离当前磁盘号最近的磁盘号. (优先级优于大小, 当外道优先级大于内道时, 那么我们需要先全部索引完
f
i
r
s
t
first
first 的外道磁盘号, 再索引
f
i
r
s
t
first
first 的内道磁盘号.
代码演示:
#includeusing namespace std; char trend; int first, cnt, ans, far; double run; vector nums; void _input(){ trend = getchar(); cin >> first; nums.emplace_back(first); while(cin >> cnt) nums.emplace_back(cnt); } void Print(){ if(trend == '+') far = 1; else far = -1; cout << "start: " << nums[ans] << endl; cout << "the next place len nums" << endl; int ide = ans + far; while(ide < nums.size() && ide >= 0){ cout << setw(14) << nums[ide]; cout << " "; cout << setw(8) << abs(nums[ide] - nums[ide - far]) << endl; run += abs(nums[ide] - nums[ide - far]); ide += far; } int c = abs(nums[ide - far] - nums[ans]); far = -far, ide = ans + far; while(ide < nums.size() && ide >= 0){ cout << setw(14) << nums[ide]; cout << " "; cout << setw(8) << abs(nums[ide] - nums[ide - far]) << endl; run += abs(nums[ide] - nums[ide - far]); ide += far; } cout << setiosflags(ios::fixed) << setprecision(1) << "平均寻道时间: " << (run + c) / (nums.size() - 1) << endl; } void _work(){ //排序后，只需要判断一次距离就行 sort(nums.begin() , nums.end()); ans = find(nums.begin() , nums.end() , first) - nums.begin(); Print(); } signed main(void){ freopen("in.txt","r",stdin); //+ 100 55 58 39 18 90 160 150 38 184 freopen("SCANout.txt","w",stdout); _input(); _work(); return 0; }
实际上我们只需要对输入数据排序, 然后分别遍历
f
i
r
s
t
first
first 所在位置的左边或者右边即可. (具体先遍历左边还是右边, 看给定的优先级.
数据输入中的 ‘
+
+
+’ 表示先向外道寻找, 而 ‘
−
-
−’ 理所当然先向里道寻找.
这个算法很简单, 也不需要绕弯子.
结果演示如下:
start: 100
the next place len nums
150 50
160 10
184 24
90 10
58 32
55 3
39 16
38 1
18 20
平均寻道时间: 27.8
三. CSCAN
快期末考试了, 还没开始预习, 这种东西真的会考吗 눈_눈
--over
