操作系统实验之磁盘调度

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
| 1.3k | 5 min

实验要求

  • 选择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

马后炮

调试过程

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

欢迎分享

猜你喜欢
码字不易，请我喝杯咖啡呗？