操作系统实验之磁盘调度

  • 时间:
  • 来源:互联网

实验要求

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

    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为空。最后输出总路程。

        System.out.print("寻道顺序为:" + headAt + " ");
        while (!trackSet.isEmpty()) {
            Iterator<Integer> 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中,最后输出总路程。

    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]<headAt; 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);
    }

实验结果

测试用例

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

马后炮

调试过程

调试基本没有出现很大的问题,主要出现的是一些小细节的地方,比如数组越界等问题,经过调试后便能正常运行。

小结

磁盘调度实验是操作系统三次实验里最简单的一个,主要考察的实际是对调度思想的理解,实际代码的难度并不大,代码上的难点顶多就于数组的遍历。

本文链接http://element-ui.cn/news/show-636253.aspx