电梯算法简介

当磁头正在由里向外移动时，电梯调度算法所选择的下一个访问对象应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样由里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向，由外向里移动。这时，同样也是每次选择在当前磁道之内，且距离最近的进程来调度。 ——摘自百度百科
网上大多将电梯调度算法和扫描算法看作同一个算法，我们老师讲的时候将它们作了区分。扫描算法：需要扫描到该方向的最后一个磁盘才能返回，电梯算法则只要扫描到该方向欲访问的最后一个磁道就可以返回。
例如：磁盘有200个柱面，编号为0-199，当前移动臂在143号柱面上，向0方向移动。请求访问序列：86，147，91，177，94，150，102。
电梯调度算法访问的磁道面顺序为：102，94，91，86，147，150，177。
扫描算法访问的磁道面顺序为：102，94，91，86，0，147，150，177。

题目

假定一个磁盘有200个柱面，编号为0一199，在完成了磁道125外的请求后，当前正在磁道143处为一个请求服务。若请求队列的先后顺序为86，147，91，177，94，150，102，175，130。采用电梯调度算法写出磁头移动的顺序，并计算存取臂移动总量。

代码实现

我用java实现的是界面化，这样运行的时候大概可能看起来比较直观吧

• 定义柱面类Cylinder.java

public class Cylinder {//柱面号public int number;//初始化public Cylinder(int number) {this.number = number;}
}

• 主类Elevator.java

界面初始化：

TextField tf1;
TextField tf2;
//显示界面的TextField队列
private ArrayList<TextField> textFields = new ArrayList<TextField>();
public void showUI(){//窗口初始化javax.swing.JFrame window  = new javax.swing.JFrame();window.setSize(800, 1000);window.setTitle("电梯算法");window.setDefaultCloseOperation(3);window.setLocationRelativeTo(null);JPanel jPanel = new JPanel();jPanel.setPreferredSize(new Dimension(0, 100));jPanel.setBackground(Color.white);Label l1 = new Label("Previews:");Label l2 = new Label("Now:");tf1 = new TextField("143");tf2 = new TextField("125");jPanel.add(l1);jPanel.add(tf1);jPanel.add(l2);jPanel.add(tf2);Button button1 = new Button("START");button1.setPreferredSize(new Dimension(100, 60));jPanel.add(button1);Button button = new Button("NEXT");button.setPreferredSize(new Dimension(100, 60));jPanel.add(button);JPanel jPanel2 = new JPanel();//设置网格布局GridLayout gridLayout = new GridLayout(10,20,0,3);jPanel2.setLayout(gridLayout);//添加TextView作为柱面for(int i=0;i<200;++i){TextField textField = new TextField(""+i);jPanel2.add(textField, gridLayout);textFields.add(textField);}jPanel2.setBackground(Color.blue);window.add(jPanel,BorderLayout.NORTH);window.add(jPanel2, BorderLayout.CENTER);window.setVisible(true);button.addActionListener(this);button1.addActionListener(this);}

调用showUI()方法后，显示的窗口是这样的：
初始化访问序列

//存储柱面号的数组
private int a[] = new int[]{86,147,91,165,177,94,150,102,175,130};
//这个后面会用到
int b[] = new int[]{86,147,91,177,94,150,102,165,175,130};
//需要访问柱面的队列
private ArrayList<Cylinder> cylinderlist = new ArrayList<Cylinder>();
//初始化访问的柱面
public void init(){cylinderlist = new ArrayList<Cylinder>();for(int i=0;i<a.length;++i){Cylinder cylinder = new Cylinder(a[i]);cylinderlist.add(cylinder);}//使用匿名类排序Collections.sort(cylinderlist, new Comparator<Cylinder>() {public int compare(Cylinder h1, Cylinder h2) {return h1.number-h2.number;}});//将要访问的柱面设为红色for(int i=0;i<b.length;++i){textFields.get(b[i]).setBackground(Color.RED);}//当前柱面号设为灰色textFields.get(now).setBackground(Color.gray);
}

寻找下一个要访问的柱面号
如果现在是向外移动（向199号方向移动），选择大于当前柱面号的访问者中柱面号最小者

private int now = 125;//当前柱面号
private int previews =143;//之前完成的柱面号服务请求
public void findMin(){//赋值给完成的柱面号previews = now;//之前已经用匿名类排序后，只要选择队列中该位置的后一个元素就可以了int no = 0;for(int i=cylinderlist.size()-1;i>=0;--i){Cylinder cylinder = cylinderlist.get(i);if(cylinder.number>=now)no = i;}Cylinder c = cylinderlist.get(no);//访问到后将选中的柱面移除访问序列cylinderlist.remove(no);//将选中的柱面号赋值给当前移动臂在的位置now = c.number;
}

如果现在是向里移动（向0号方向移动），选择小于当前柱面号的访问者中柱面号最大者，类似

public void findMax(){previews = now;int no = 0;for(int i=0;i<cylinderlist.size();++i){Cylinder cylinder = cylinderlist.get(i);if(cylinder.number<=now)no = i;}Cylinder c = cylinderlist.get(no);cylinderlist.remove(no);now = c.number;
}

改变图形界面移动的颜色

public void display(){//判断如果是向里移动if(previews-now<0){//循环为之前完成的柱面号至当前柱面号for(int k=previews;k<now;++k){//将当前TextField的颜色置为灰色TextField textField2 = textFields.get(k+1);textField2.setBackground(Color.GRAY);//将刚才访问过的TextField颜色置为白色TextField textField = textFields.get(k);textField.setBackground(Color.WHITE);//休眠时间，可以调整移动的速度try {Thread.sleep(100);} catch (InterruptedException e) {// TODO Auto-generated catch blocke.printStackTrace();}}}//与上面类似if(previews-now>0){for(int k=previews;k>now;--k){TextField textField2 = textFields.get(k-1);textField2.setBackground(Color.GRAY);TextField textField = textFields.get(k);textField.setBackground(Color.WHITE);try {Thread.sleep(100);} catch (InterruptedException e) {e.printStackTrace();}}}
}

为按钮加点击事件

public void actionPerformed(ActionEvent e) {//获取点击事件String event = e.getActionCommand();//判断点击了哪个按钮switch (event) {case "NEXT":if(cylinderlist.size()>0){//向外移动调用findMin()方法if ((now-previews)>0&&now!=199){findMin();//输出看一下结果System.out.println("previews:"+previews+" now:"+now);//显示效果display();}else {//向里移动调用findMax()方法findMax();System.out.println("previews:"+previews+" now:"+now);display();}}else{System.out.println("已完成");}break;case "START"://获取文本框中的数字previews = Integer.parseInt(tf1.getText());now = Integer.parseInt(tf2.getText());	//初始化init();System.out.println(now+" "+previews);break;default:break;}}

调用方法

public static void main(String[] args) {Elevator elevator = new Elevator();elevator.showUI();}

到这所有的代码就写完了，加起来不会超过200行。如果嫌点击太慢，可以弄个循环，循环次数为访问队列的长度。想计算总共移动的量，可以定义一个变量，初始值定义为0，每次移动的时候增加|now-previews|。

效果图