电梯调度算法

起源

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

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() 来实现延时触发的效果，好在这里只有两个动作需要回调，否则代码的嵌套深度会达到惊人的程度。

小结

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