引言

作为一个对时间观念比较注重的本人来说，最忍受不了的事情就是被一些不必要的事情耽误。而最近到公司上班坐电梯的时候常常会遇到一些令人烦躁的情况，这里描述一个活生生的场景吧。某天我刚到公司大厦的门口，按了门口电梯的向上按钮。这时，门口的两门电梯左边的一个是从三楼往上到四楼，右边的一个是停在五楼；原本我想着该是五楼的电梯下来”迎接我“，但是我错了，右边那台一动不动，而只有等左边的到达四楼目的地的时候，才下来接我。我想大家应该都会有这种时候，在坐电梯时会不禁细想到底这部电梯的调度是怎么跑的？为什么会明明有闲置的电梯，还要我等另一台在运作的？为什么明明到了我这里的楼层，电梯却不开门？为什么我要坐电梯上班？ <img src="https://s1.ax1x.com/2018/10/31/iRLxKO.png" width="30" hegiht="30"> 带着这些问题，我就开始查各种资料，撰写这篇文章。由于本人并非研究这方面的专业户，所以以下也只是从简单的调度算法描述。

调度种类

其实电梯的调度和硬盘的寻道逻辑思考是一致的。这里以简单的调度算法，实时调度和非实时调度两个种类来阐述。为了统一描述，我这边都把电梯称为执行者，请求称为消费者，以下都假定是从0层开始，以下只考虑请求响应，不考虑响应后的所请求的到达楼层后续。

非实时调度

FCFS（first come first serve）先来先服务

顾名思义，先来先服务就是指按照消费者请求时间的顺序，执行者先服从时间上最近的一个请求，先为最早请求的消费者服务。

这里先定义一个队列，按照请求的先后顺序，放入请求结构；执行者从队列头开始取出请求，这种方式和FIFO相同，用伪代码说明下：

  Long sum = 0;    //使用总时长
  List list;
  Elevator executor;

  func run() {
      for(i) {    //放入请求
          Req req = {floor = random(i)};
          q.add(req);
      }

      dealWithReq(executor);    //处理
  }

  func dealWithReq(executor) {
      while(!q.isEmpty) {
          Req req = q.remove();
          Long time = runToFloor(executor, req);    //算出到达需要时间
          sum += time;
      }
  }

SSTF（shortest seek time first）最短寻路时间

对于最短寻路，执行者选择下一个消费者的依据是对于目前停留的楼层中，距离最短（也可以认为是时间最短）的一个请求。

废话不多说，这里又以伪代码来简叙述下

  Long sum = 0;    //使用总时长
  List list;
  Elevator executor;

  func run() {
      for(i; i &lt; 10;) {    //放入请求
          Req req = {floor = random(i)};
          list.add(req);
      }

      dealWithReq(executor);    //处理
  }

  func dealWithReq(executor) {
      Req req = list.get(0);
      int j;
      Long spendTime = needTime(executor, req);    //所需时间
      while(!list.isEmpty) {
          for(i = 1; i &lt; list.size;){
              Long spendTimeTemp = needTime(executor, list.get(i));
              if(spendTimeTemp &lt; spendTime) {
                  req = list.get(i);
                  spendTime = spendTimeTemp
              }
          }

          sum += spendTime;
          list.remove(j);
      }
  }

由于 SSTF 是按照条件而非请求顺序去处理，和 FCFS 相比更具有随机性，所以最坏的情况是，某些请求可能长时间都得不到满足；虽然比起 FCFS，它的平均响应时间更短（响应不由顺序决定），但是响应时间的方差更大（随机性更强）。

SCAN 扫描算法
- 由于前两种在非实时调度上都有它的不稳定缺陷，为此SCAN算法可以比较好的解决问题。通过上下往返去响应请求，每次在向下或向上时都知晓当前所有的请求，然后逐个响应。
- 这里就不以伪代码阐述，直接通过一系列请求来说明
- 譬如现在楼层有10层，目前执行者在第1层，请求的列表为
  - [4F向下, 2F向上, 6F向上, 10F向下, 7F向下]
- 向上扫描到顶后，剩余列表为
  - [4F向下, 10F向下, 7F向下]
- 若果在过程中有新的请求为添加为
  - [4F向下, 10F向下, 7F向下, 5F向上, 8F向下]
- 再向下扫描到底，最后为
  - [5F向上]
- 以此类推。
LOOK 算法
- LOOK 作为 SCAN 的变样，在上下往返时，是以扫描后最顶（或最底）请求为末尾，而非整道扫描。
- 譬如上面的例子，[4F向下, 10F向下, 7F向下]，向下时，最终是到4F，而非到1F。这样可以缩短相关的请求时间。

实时调度

与非实时调度相比，实时调度更注重抢占性。优先级高的进程可以无条件的，抢占任何正在执行的，低于自己优先级的进程。
这里主要以 EDF 算法为主，介绍下相关的细节。
EDF （Earliest Deadline First）最早截止时间优先算法
- 与 SSTF 类似，EDF 也是依据时间最短原则去寻找下一个请求；但不同的是，如果有优先级更高（执行时间更短）的请求插入，执行者会中断此前的请求，并响应最高优先级的请求。这里以一个图表来描述。
  
  | 请求 | 请求到达时刻 | 所用时间（D） | | --- | --- | --- | | T1 | 0 | 20 | | T2 | 4 | 8 | | T3 | 10 | 10 |
- 这里的到达时刻和所用时间都是相同的计算单位。首先执行者响应的是 T1 请求，当到达时刻4时，T2 任务进入，而 D2 < D1，此时 T2 会抢占 T1 请求权，执行便会响应 T2。在时刻10，由于 D2 < D3，所以 T3 必须等待 T2 执行完成。到达时刻12，之后再根据当前时间的变化再做请求权的变化，以此类推
- 可以看出来，EDF 比起非实时算法，灵活性更高，对执行者的利用率也更高。不过，基于要进行实时的调度，所用开销会大得多。

结语

其实说实话，我这边也只是基于网上的一些说法做了一个总结。但是实际上的电梯调度，远远比这个复杂得多。考虑的条件除了楼层数、电梯数、电梯内的楼层请求等；还有一些更细致化的条件，譬如楼层热度、楼层优先级、电梯功耗等。看到知乎上的一句话，==一切优化，都要根据target function #c81e1e==，其实各个电梯公司在变量控制上会更加细化，我这边做的这篇也只是纯属基于个人对调度的一点好奇，可以说毫无专业性。 <img src="https://s1.ax1x.com/2018/10/31/iROMIs.png" alt="elevatorsaga" width="450" hegiht="600"> 在查阅相关资料的时候，发现在 github 上有一个关于电梯的 programing game，再简单阅读了 API 和用开发者测试的一个案例来跑后，发现电梯调度真是一个高深的玩意儿，足够硬核，这里是地址。再也不敢吐槽公司的电梯了，溜了溜了。 <img src="https://s1.ax1x.com/2018/10/31/iRO4JI.gif" alt="laotie" width="200" hegiht="200">

电梯调度的一些个人见解

引言

调度种类

非实时调度

实时调度

结语