操作系统实验之磁盘调度

实验要求

  • 选择1~3种磁盘调度算法(先来先服务法、最短寻道时间优先、电梯算法)模拟实现磁盘调度;
  • 能够输入当前磁头的位置、磁头移动方向、磁道访问请求序列等;
  • 计算磁头移动的总磁道数;
  • 能够显示磁盘调度结果(磁头依次访问的磁道号顺序等)

我选择了先来先服务法FCFS、最短寻道时间优先SSTF、电梯算法SCAN三种调度算法,代码用Java实现。

源码已上传到本人github上,建议先看源码。

实验原理

代码结构

HardDrive类表示磁盘,其私有成员有tracks表示访问序列数组,trackSet表示磁道访问集合,用HashSet实现Set接口,headAt表示磁头处于磁道位置,direction表示在SCAN调度算法里磁头移动的方向,distance表示磁头移动的总距离,method表示调度方法 ## 代码思路 ### 整体思路 用tracks数组表示访问序列,用于FCFS调度。trackSet用于遍历访问序列,获得每次离磁头最近的磁道。headAt在每次移动磁头后记录位置,distance用来保存每次headAt移动前后距离的绝对值的累加和。

构造一个HardDrive对象,并将参数tracks、headAt、direction、method参数带入,根据调度方法不同输出不同的结果。

FCFS

先来先服务调度比较简单,用数组表示顺序访问序列,遍历数组,输出下一个数组元素i,计算数组该元素i和当前headAt距离并保存到distance中,修改磁头headAt位置。遍历结束后输出distance。

1
2
3
4
5
6
7
8
9
10
private void FCFS() {
System.out.print("寻道顺序为:" + headAt + " ");
for (int i : tracks) {
System.out.print(i + " ");
this.distance += Math.abs(headAt - i);
headAt = i;
}
System.out.println();
System.out.println("总路程=" + this.distance);
}

SSTF

最短寻道时间优先调度使用trackSet,遍历trackSet每次选出一个离磁头最近的磁道并输出,把距离累加到distance中,将磁头移到该磁道,将该磁道从trackSet中移除,直到trackSet为空。最后输出总路程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    System.out.print("寻道顺序为:" + headAt + " ");
while (!trackSet.isEmpty()) {
Iterator iterator = trackSet.iterator();
int chosenOne = iterator.next();
while (iterator.hasNext()) {
int t = iterator.next();
if (Math.abs(t - this.headAt) < Math.abs(chosenOne - this.headAt))
chosenOne = t;
}
System.out.print(chosenOne + " ");
this.distance += Math.abs(this.headAt - chosenOne);
this.headAt = chosenOne;
trackSet.remove(chosenOne);
}
System.out.println();
System.out.println("总路程=" + this.distance);
}

SCAN

电梯调度算法首先将当前访问序列进行冒泡排序,然后在排序后的数组中找到当前磁头的序号head,根据输入的磁头移动方向分别移动并输出,同时把距离累加到distance中,最后输出总路程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
private void SCAN() {
System.out.print("寻道顺序为:" + headAt + " ");
int[] orderTracks = this.tracks.clone();
for (int i = 0; i < orderTracks.length; i++) {
for (int j = i + 1; j < orderTracks.length; j++) {
if (orderTracks[i] > orderTracks[j]) {
int t = orderTracks[i];
orderTracks[i] = orderTracks[j];
orderTracks[j] = t;
}
}
}
int head = 0;
for (int i = 0; i < orderTracks.length&&orderTracks[i]
head++;
}
if (direction) {
for (int i = head; i < orderTracks.length; i++) {
System.out.print(orderTracks[i] + " ");
this.distance += Math.abs(this.headAt - orderTracks[i]);
this.headAt = orderTracks[i];
}
for (int i = head - 1; i >= 0; i--) {
System.out.print(orderTracks[i] + " ");
this.distance += Math.abs(this.headAt - orderTracks[i]);
this.headAt = orderTracks[i];
}
} else {
for (int i = head; i < orderTracks.length; i++) {
System.out.print(orderTracks[i] + " ");
this.distance += Math.abs(this.headAt - orderTracks[i]);
this.headAt = orderTracks[i];
}
for (int i = head - 1; i >= 0; i--) {
System.out.print(orderTracks[i] + " ");
this.distance += Math.abs(this.headAt - orderTracks[i]);
this.headAt = orderTracks[i];
}
}
System.out.println();
System.out.println("总路程=" + this.distance);
}

实验结果

测试用例

1
int[] tracks = {98, 183, 37, 122, 14, 124, 65, 67};

测试结果

FCFS

1.FCFS 2.SSTF 3.SCAN 请输入调度算法:1 请输入磁头起始位置: 53 请输入方向(0.左 1.右): 0 寻道顺序为:53 98 183 37 122 14 124 65 67 总路程=640

Process finished with exit code 0

SSTF

1.FCFS 2.SSTF 3.SCAN 请输入调度算法:2 请输入磁头起始位置: 53 请输入方向(0.左 1.右): 0 寻道顺序为:53 65 67 37 14 98 122 124 183 总路程=236

Process finished with exit code 0

SCAN

1.FCFS 2.SSTF 3.SCAN 请输入调度算法:3 请输入磁头起始位置: 53 请输入方向(0.左 1.右): 0 寻道顺序为:53 37 14 65 67 98 122 124 183 总路程=208

Process finished with exit code 0

马后炮

调试过程

调试基本没有出现很大的问题,主要出现的是一些小细节的地方,比如数组越界等问题,经过调试后便能正常运行。 ## 小结 磁盘调度实验是操作系统三次实验里最简单的一个,主要考察的实际是对调度思想的理解,实际代码的难度并不大,代码上的难点顶多就于数组的遍历。


欢迎分享

码字不易,请我喝杯咖啡呗?