电梯调度算法

磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请求等待处理，这时我们就需要采用一种合适的调度算法来使各个进程对磁盘的访问时间最少，考虑到在调度进程中，只涉及到刺头的移动，所以有以下注意点:

1.磁盘调度的目标:就是使磁盘的平均寻道时间最少

2.寻道时间的衡量指标:磁头移动的磁道数来衡量

3.主要的磁盘调度算法有：

1).FCFS算法：根据进程请求访问磁盘的先后次序来调度

2).最短寻道时间优先SSTF算法：访问的磁道与当前所在的磁道距离最短

3).扫描SCAN算法，即电梯调度算法:与当前磁道距离最近并且是在当前扫描方向上的

4).循环扫描CSCAN算法:规定磁头单向扫描，然后立即返回重新开始。

本篇博文主要通过代码的方式直观介绍下上述第三种算法，即电梯调度算法。

首先对于该算法的代码实现，先确定基本流程：算法分为接收新的I/O请求并建立请求I/O表和程序和对I/O请求表中的进程进行电梯调度算法.主要的流程如下：

对于两种分支的选择，主要通过手动输入随机数的方式确定。

之后编写接受请求并建立请求I/O表的程序，I/O请求表主要通过一个TreeSet集合来实现，以下是流程图（具体代码会在最后作为整体程序的一部分出现）：

下面是电梯调度算法的核心代码实现的流程图:

最后，在完成相关的数据初始化工作后就可以进行程序的运行，数据的初始化包括：

1.初始化“请求I/O”表(初始已经有若干进程（3～8个）申请访问相应磁道) 2.设置置当前移臂方向 3.设置当前磁道号。

不废话了，贴上我的源代码:

 [java]  view plain copy 
package 操作系统_磁盘电梯调度算法;  
  
import java.util.Comparator;  
import java.util.Iterator;  
import java.util.Random;  
import java.util.Scanner;  
import java.util.TreeSet;  
  
class PCB {  
    public int id;  
    public int CiDaoNum;  
    public boolean isVisited;  
  
    @Override  
    public String toString() {  
        return "进程号:" + this.id + ",其访问的磁道号:" + this.CiDaoNum+" 是否已被调度："+this.isVisited;  
    }  
  
    public PCB(int id, int ciDaoNum, boolean isVisited) {  
        super();  
        this.id = id;  
        CiDaoNum = ciDaoNum;  
        this.isVisited = isVisited;  
    }  
}  
  
public class Main {  
    public static Scanner scanner = new Scanner(System.in);  
    public static TreeSet<PCB> pcbsOut = new TreeSet<PCB>(new Comparator<PCB>() {  
        @Override  
        public int compare(PCB p1, PCB p2) {  
            if (p1.CiDaoNum >= p2.CiDaoNum)  
                return 1;  
            return -1;  
        }  
  
    });  
    public static TreeSet<PCB> pcbsIn = new TreeSet<PCB>(new Comparator<PCB>() {  
        @Override  
        public int compare(PCB p1, PCB p2) {  
            if (p1.CiDaoNum >= p2.CiDaoNum)  
                return -1;  
            return 1;  
        }  
  
    });  
    public static Random random = new Random();  
    public static boolean isOutDirection;  
    public static int currentCiDaoNum;  
    public static int Count;  
  
    public static void main(String[] args) {  
        // 初始化工作  
        int originalNum = random.nextInt(4) + 4;  
        Count = originalNum;  
        for (int i = 1; i <= originalNum; i++) {  
            PCB temp = new PCB(i, random.nextInt(200) + 1, false);  
            pcbsOut.add(temp);  
            pcbsIn.add(temp);  
        }  
        System.out.println("请求I/O表中已经有以下进程项:");  
        Iterator<PCB> iterator = pcbsOut.iterator();  
        while (iterator.hasNext()) {  
            System.out.println(iterator.next());  
        }  
        isOutDirection = random.nextInt(200) > 100 ? true : false;  
        System.out.println("当前移臂方向为:" + (isOutDirection ? "从内向外" : "从外向内"));  
        currentCiDaoNum = random.nextInt(200) + 1;  
        System.out.println("当前所访问的磁道为:" + currentCiDaoNum );  
  
        System.out.println();  
        System.out.println();  
  
        boolean isGoOn = true;  
        while (isGoOn) {  
            System.out.println("请输入一个0~1的随机数，小于等于0.5表示进行磁盘调度,大于0.5表示进行新进程的请求接收:");  
            double ran = scanner.nextDouble();  
            if (ran <= 0.5)  
                CiPanDiaoDu();  
            else  
                JieShouQingQiu(originalNum + 1);  
            System.out.println("----------------------------");  
        }  
    }  
  
    private static void JieShouQingQiu(int id) {  
        System.out.println("请输入进程要访问的磁道号(保证磁道号在1~200内且不要与现有进程的磁道号重复)：");  
        int Num = scanner.nextInt();  
        PCB temp = new PCB(id, Num, false);  
        pcbsOut.add(temp);  
        pcbsIn.add(temp);  
        Count++;  
        System.out.println("该进程已被成功添加至请求I/O表!!");  
        System.out.println();  
        System.out.println();  
        System.out.println("目前请求I/O表已经具备以下表项:");  
        Iterator<PCB> iterator = pcbsOut.iterator();  
        while (iterator.hasNext()) {  
            System.out.println(iterator.next());  
        }  
        System.out.println("此时磁臂方向为：" + (isOutDirection ? "从内向外" : "从外向内") + ".");  
        System.out.println("此时磁臂所在磁道的号码为：" + currentCiDaoNum );  
          
    }  
  
    private static void CiPanDiaoDu() {  
        if (Count <= 0) {  
            System.out.println("请求I/O表已空，请添加请求后再进行磁盘调度或者退出程序。");  
            return;  
        }  
        System.out.println("开始在" + currentCiDaoNum + "磁道上并" + (isOutDirection ? "从内向外" : "从外向内") + "上查询--");  
        Iterator<PCB> iterator = null;  
        boolean isFindWithOneDirection = false;  
        PCB mindPCB = null;  
        if (isOutDirection) {  
            iterator = pcbsOut.iterator();  
            while (iterator.hasNext()) {  
                PCB pcb = iterator.next();  
                // 从内向外找,跳过已经找调度过的进程  
                if (pcb.isVisited)  
                    continue;  
                // 当磁道号小于磁臂所在的磁道号时，一直向外遍历寻找  
                if (pcb.CiDaoNum < currentCiDaoNum) {  
                    mindPCB = pcb;  
                    continue;  
                }  
                // 只要找到一个大于等于磁臂所在的磁道号的进程时，就立马退出  
                isFindWithOneDirection = true;  
                mindPCB = pcb;  
                break;  
            }  
            if (!isFindWithOneDirection)  
                isOutDirection = false;  
        } else  
        // 磁臂从外向内  
        {  
            iterator = pcbsIn.iterator();  
            while (iterator.hasNext()) {  
                PCB pcb = iterator.next();  
                // 从内向外找,跳过已经找调度过的进程  
                if (pcb.isVisited)  
                    continue;  
                // 当磁道号小于磁臂所在的磁道号时，一直向外遍历寻找  
                if (pcb.CiDaoNum > currentCiDaoNum) {  
                    mindPCB = pcb;  
                    continue;  
                }  
                // 只要找到一个大于等于磁臂所在的磁道号的进程时，就立马退出  
                isFindWithOneDirection = true;  
                mindPCB = pcb;  
                break;  
            }  
            if (!isFindWithOneDirection)  
                isOutDirection = true;  
  
        }  
        // 上述while循环退出时，没找到时pcb为反方向上距离currentCiDaoNum最近的没被访问的进程  
        // 找到时pcb为磁臂方向上离currentCiDaoNum最近的没被访问的进程  
  
        // 当mindPCB为空时表明所有磁道号均大于磁臂所在的磁道号,这时取pcbsOut第一个元素即可  
        if (mindPCB == null) {  
            mindPCB = pcbsOut.first();  
        }  
        if (!isFindWithOneDirection) {  
            System.out.println("在当前方向上没有查询到，转变磁臂方向查找," + "找到在" + mindPCB.CiDaoNum + "磁道上且进程编号为" + mindPCB.id + "的进程。");  
        } else {  
            System.out.println("在当前方向上找到符合要求的进程," + "其所在磁道号为：" + mindPCB.CiDaoNum + ",进程编号为:" + mindPCB.id);  
        }  
        mindPCB.isVisited=true;  
        currentCiDaoNum = mindPCB.CiDaoNum;  
        Count--;  
        System.out.println("此时磁臂方向为：" + (isOutDirection ? "从内向外" : "从外向内") + ".");  
        System.out.println("此时磁臂所在磁道的号码为：" + currentCiDaoNum );  
    }  
}  