操作系统课程设计--磁盘调度算法的模拟实现及对比

本来已经做好了个课程设计是银行家算法的，不过由于借给同学抄，被老师发现了，要重做...就选了磁盘高度算法的题目。

实验要求及提示

1 、首先假设磁盘磁道数为 1500 ，磁头初始停止于 0 磁道。

2 、用随机数生成函数产生“磁道号”序列（即磁盘请求的位置），共产生 100 个。其中 50% 位于 0 ～ 499 ， 25% 分布在 500 ～ 999 ， 25% 分布在 1000 ～ 1499 。

 

       3 、计算每种磁盘调度算法下的磁头移动道数

 

本程序主要是模拟实现，还有很多改进的地方，还请大家提出。

 

以下是为满足要求2的随机数生成代码，主要参照网上的方法：

package chow.app;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;

/**
 * 用随机数生成函数产生“磁道号”序列（即磁盘请求的位置），共产生100个。其中50%位于0～499，25%分布在500～999，25%分布在1000～1499。
 * @author Administrator
 */
public class DiskScheduleUtil {

    public static int count = 0;// 需要生成随机数的个数

    public int[] createDiskRequest() {
        int[] tmpRequest = new int[100];
        HashSet<Integer> s = new HashSet<Integer>();
        // 50%位于0～499的序列
        count = 50;
        genRadoms(0, 499, count, s);
        Iterator<Integer> it;
        it = s.iterator();
        int i = 0;
        while (it.hasNext()) {
            tmpRequest[i] = it.next();
            i++;
        }
        // 25%分布在500～999的序列
        count = 25;
        s.clear();
        genRadoms(500, 999, count, s);
        it = s.iterator();
        i = 50;
        while (it.hasNext()) {
            tmpRequest[i] = it.next();
            i++;
        }
        //25%分布在1000～1499的序列
        count = 25;
        s.clear();
        genRadoms(1000, 1499, count, s);
        it = s.iterator();
        i = 75;
        while (it.hasNext()) {
            tmpRequest[i] = it.next();
            i++;
        }
        //用来打乱tmpRequest的顺序
        int[] tmpRequestReturn = new int[100];
        int[] nosortSeq = random2();
        for(int j = 0; j  < 100; j++){
            tmpRequestReturn[j] = tmpRequest[nosortSeq[j]];
            System.out.print("[" + j + "]:" + tmpRequestReturn[j] + " ");
            if (j % 10 == 0) {
                System.out.println();
            }
        }
        return tmpRequestReturn;
    }

    // 生成【begin，end】区间内num个随机数
    public void genRadoms(int begin, int end, int num, HashSet<Integer> set) {
        if (num > (end - begin + 1) || end < begin) {
            return;
        }
        for (int i = 0; i < num; i++) {// 生成num个随机数
            // 调用Math.random()方法
            int temp = (int) (Math.random() * (end - begin + 1)) + begin;
            set.add(temp);// 将不同的数存入HashSet中
        }
        int setLen = set.size();
        // 如果存入的数小于指定生成的个数，则调用递归再生成剩余个数的随机数，如此循环，直到达到指定大小
        if (setLen < count) {
            genRadoms(begin, end, count - setLen, set);// 递归
        }
    }


    public static int[] random2() {
        int send[] = new int[100];
        for(int i = 0; i < send.length; i++){
            send[i] = i;
        }
        int temp1, temp2, temp3;
        Random r = new Random();
        for (int i = 0; i < send.length; i++) // 随机交换send.length次
        {
            temp1 = Math.abs(r.nextInt()) % (send.length - 1); // 随机产生一个位置
            temp2 = Math.abs(r.nextInt()) % (send.length - 1); // 随机产生另一个位置
            if (temp1 != temp2) {
                temp3 = send[temp1];
                send[temp1] = send[temp2];
                send[temp2] = temp3;
            }
        }
        return send;
    }

}

 

以下是FCFS,SSTF,SCAN,C-SCAN各算法的代码，每个算法都返回磁盘移动的磁道数。

 

FCFS算法，first come first service.

package chow.app;

/**
 * first come, first service
 * @author Administrator
 */
public class DiskScheduleFCFS extends DiskScheduleAlgorithm{
    @Override
    public int getCount(final int[] diskReq, int varIndex){
        count = 0;
        curIndex = varIndex;
        for(int i = 0; i < diskReq.length; i++){
            count += Math.abs(diskReq[i] - curIndex);
            curIndex = diskReq[i];
        }
        return count;
    }

}

 

 

SSTF算法，shortest seek time first

package chow.app;

/**
 * shortest seek time first 最短寻道时间优先算法
 * @author Administrator
 */
public class DiskScheduleSSTF extends DiskScheduleAlgorithm {

    @Override
    public int getCount(final int[] diskReq, int varIndex) {
        count = 0;
        curIndex = varIndex;
        int[] tmpDiskReq = new int[diskReq.length];
        for(int tInt = 0; tInt < diskReq.length; tInt++){
            tmpDiskReq[tInt] = diskReq[tInt];
        }
        for (int i = 0; i < tmpDiskReq.length; i++) {
            int index = getNearestIndex(curIndex,tmpDiskReq);
            count += Math.abs(curIndex - tmpDiskReq[index]);
            System.out.print(tmpDiskReq[index]+" ");
            if(i%10==0)
                System.out.println();
            curIndex = tmpDiskReq[index];
            tmpDiskReq[index] = -1;
        }
        return count;
    }

    //返回距离当前最近的索引
    public int getNearestIndex(int tmpIndex,final int[] tdiskReq) {
        int min = 1500;
        int temp = 0;
        int index = -1;
        for (int i = 0; i < tdiskReq.length; i++) {
            if (tdiskReq[i] != -1) {
                temp = Math.abs(tmpIndex - tdiskReq[i]);
                if (temp < min) {
                    min = temp;
                    index = i;
                }
            }
        }
        return index;
    }
}

 

 

SCAN算法，又叫做“电梯算法”，我是处理完最远一个请求就返回另一方向继续处理。也有教材上是一直移动到末端才转方向的。

/**
 * SCAN 电梯算法，先不断移到一端（尽头），再移到另一端（另一尽头）
 * 简化：默认为先大数端后向0端；不移到末端，只移到最外一个请求就转向
 * @author Administrator
 */
public class DiskScheduleSCAN extends DiskScheduleAlgorithm{
    @Override
    public int getCount(final int[] diskReq, int varIndex) {
        count = 0;
        curIndex = varIndex;
        int leftMin = curIndex, rightMax = curIndex;
        for(int i = 0; i < diskReq.length; i++){
            if(diskReq[i] > curIndex && diskReq[i] > rightMax){
                rightMax = diskReq[i];
            }else if(diskReq[i] < curIndex && diskReq[i] < leftMin){  // 小于等于curIndex
                leftMin = diskReq[i];
            }
        }
        if(curIndex==leftMin){
            count = rightMax - curIndex;
        }else{
            count = (rightMax - curIndex) + (rightMax - leftMin);
        }
        return count;
    }
    
}

 

 

C-SCAN算法，SCAN算法的变种

package chow.app;

/**
 * C-SCAN, 是SCAN的变种，当碰头移到另一端时，马上返回到磁盘开始，返回时不处理请求
 * @author Administrator
 */
public class DiskScheduleC_SCAN extends DiskScheduleAlgorithm{
    @Override
    public int getCount(final int[] diskReq, int varIndex) {
        count = 0;
        curIndex = varIndex;
        int leftMax = lowIndex, rightMax = curIndex;
        for(int i = 0; i < diskReq.length; i++){
            if(diskReq[i] > curIndex && diskReq[i] > rightMax){
                rightMax = diskReq[i];
            }else if(diskReq[i] < curIndex && diskReq[i] > leftMax){  // 小于curIndex
                leftMax = diskReq[i];
            }
        }
        if(curIndex==leftMax){
            count = rightMax - curIndex;
        }else{
            count = (rightMax - curIndex) + (highIndex - lowIndex) + leftMax;
        }
        return count;
    }
}

 

以上是关键代码，其它的界面是在netbeans6.7上完成的。下面上传最终生成的jar文件。

评论

2 楼 bosshida 2010-12-27  

heming_way 写道

你好搞笑啊，我也选的银行家算法，不过现在还是蛮纠结，是不是我的题目选得太简单了，

呵呵，做银行家算法如果能实现得比较好，也是有点难度的。

1 楼 heming_way 2010-12-27  

你好搞笑啊，我也选的银行家算法，不过现在还是蛮纠结，是不是我的题目选得太简单了，