« 回到博客列表

电梯调度算法

Tags: algorithm

查看源码

起源

之所以会想到这么个主题,纯粹是因为前两天坐电梯的时候,脑子里某条神经炸出来一团莫名的火花。灵感这东西,不定什么时候说来就来。

SCAN 调度算法

电梯调度的核心是SCAN算法,这是操作系统用于磁盘调度的算法之一。看到“操作系统”和“算法”两个词估计有人就要打退堂鼓了,不要怕,SCAN算法的核心思想非常简单,就是在一条路上来来回回的走,一个方向上走到头之后换反方向再走到头,如此往复。看,不难吧?

要实现这个算法,主要需要两样东西:一个数组,以及一个“不撞南墙不回头”的算法。有人用两个数组分别存放上行和下行的队列,一个空了换另一个,这也是可以的,但一个数组就能解决的问题,为什么要用两个呢?

1. 等待队列

我们先来看数组的部分,关键代码如下:

var queue = [];
var goingup = true;
var running = false;

function dial(floor) {
  if (queue.indexOf(floor) < 0) {
    queue.push(floor);
    queue.sort();
    if (!running) {
      checkStatus();
    }
  }
}

我用一个数组queue来保存所有被按下的楼层,无论是在电梯外还是电梯内按的。dial()函数同样适用于电梯内外的所有楼层按钮,只要按下,都按照其中的逻辑添加到queue中。

dial()函数的第一层判断,主要是为了解决同一楼层不同位置的按钮(电梯内1个,电梯外1~2个)都按下的情况,任何一个按下就够了,避免重复添加,否则就会出现门刚关上又打开的情况。queue.sort()这一步很关键,它确保了前进方向上楼层都是以楼层数为序的,而不是以添加顺序为序(这是电梯调度算法的特点,也许有的朋友并不知道)。这里因为数据量不大,因此不深究排序算法的复杂度,直接使用Array类的原生方法。

2. “不撞南墙不回头”的算法

checkStatus()用于更新一些状态变量的取值,用于决定电梯是否开始运行,以及什么时候该回头了。running用于记录当前电梯的运行状态,初始状态为false,因为假定它停在一楼。只要有任何一层楼被按下,即数组queue非空,电梯就处于运行状态。goingup用于记录电梯是上行还是下行,上行为true,下行为false,初始状态为true,因为假定它停在一楼,向上的可能性最大。在顶层和底层时固定回头,对于中间的楼层,就看当前前进方向上时候还有没有灭掉的灯,如果有,就继续走,否则回头。对于停止状态下的电梯,暂时不管它的状态。函数中的其它变量和函数看名字就知道用途了,不多解释。

function checkStatus() {
  running = ( queue.length > 0) ? true : false;

  if(currentFloor == MIN_FLOOR) {
    goingup = true;
  } else if (currentFloor == MAX_FLOOR) {
    goingup = false;
  } else {
    (  goingup && (!running || currentFloor < getMaxInQueue(queue)) ) ? goingup = true  : goingup = false;
    ( !goingup && (!running || currentFloor > getMinInQueue(queue)) ) ? goingup = false : goingup = true;
  }
}

3. 主函数

接下来的事情就很简单了,我设定了一个定时器,每秒钟运行一次主函数,执行电梯的移动和停靠等动作,代码如下:

var timer = null;

function run() {
  if(running) {
    if (queue.indexOf(currentFloor) > -1) {
      ding(currentFloor);
    } else {
      goingup ? moveUp() : moveDown();
      updateFloorInfo();
    }
    checkStatus();
  }
}

function ding(floor) {
  if (timer)
    clearInterval(timer);
  lightsOut(floor);
  removeFromQueue(queue, floor);
  openDoor();
  setTimeout(function(){
    closeDoor();
    setTimeout(function(){
      timer = setInterval(run, 1000);
    }, 3000);
  }, 4000);
}

function moveUp() {
  if ( currentFloor < MAX_FLOOR ) {
    currentFloor++;
  }
}

function moveDown() {
  if ( currentFloor > MIN_FLOOR ) {
    currentFloor--;
  }
}

timer = setInterval(run, 1000);

对于运行中的电梯,run()函数首先检查当前楼层时候被按下,即currentFloor是否存在于数组queue中,存在则调用ding(floor)函数,暂停计时器,熄灭该楼层按钮的灯光,将该楼层从数组中移除,开门,关门,重启计时器。否则根据行进方向向上或向下移动一层,并更新楼层计数器。注意:由于JavaScript本身并不支持类似sleep(milis)这种用于暂停的函数,而回调机制又都是异步的,因此只能通过嵌套的setTimeout()来实现延时触发的效果,好在这里只有两个动作需要回调,否则代码的嵌套深度会达到惊人的程度。

小结

至此,程序的主要逻辑部分就已经完成了。在项目中我还做了一些可视化的效果,例如开门关门的动效、楼层信息的显示、电梯位置的显示、按钮的电量和熄灭等等,更过内容请查看完整项目,预览和代码的链接在文章的一开始就已经给出。