不断发展的城市里，越来越多的人口和与之俱来的上层需求，使建筑堆砌得越来越高。尤其是一些寸土尺金的地方，向天空拓展生存空间，是容纳更多人口，并实现人民美好生活的希望的有效方法。

由于容纳了大量的人口，密集的高层建筑里，会发生频繁的货物的流动，如何处理这些流动将影响货物流转的效率。

越来越高的建筑，如何把货物运到高处值得思索

高层建筑里货物的运输可以分为三个部分：垂直向的电梯上下，到达当前层后到第一个目标的时间，在当前层的顺序运送和交换。理想下货物到达任意层后都沿着当前层的哈密顿回路行走，即出电梯后遍历当前层的每一个房间再回到电梯。

货物在同一层的运行基本取决于这一层里人和货物的运行速度，在当前层的顺序运送和交换只取决于货物的运行速度以及货物的具体多少。这些都是由货物自身性质决定的。

因为同一层的货物可以通过等待到货物累积尽可能多，并把这一层里的货物运输都集中在一条哈密顿回路上实现在最少的时间内完成运送和交换，从而提高同一层的货物的运输效率。这是相对容易实现的。

因此对于高层建筑的货物运输，最关键的就是垂直向的电梯上下的运作，下面将主要讨论这个问题。

在此定义，货物的装载和卸载均视为一个请求。

类似于把货物搬上搬下最辛苦又最关键

电梯的运行算法有很多种，它们都反映着我们如何解决垂直运动的问题。

最简单的算法是先进先出算法（FIFO），这种也是最公平的算法，它的运行顺序是按照不同楼层的请求的到达顺序排序的，先请求的先服务。这也是电梯上下最基本的原则。

也可以增加优先级，使得一些时效性比较高的货物可以获得更加高的优先使用电梯的权利。这种方法只需要控制不同货物请求的时间差即可实现。

这些算法虽然会出现上上下下很多次的情况，但是当货物运输请求相对单一时，这种算法的效率影响不大，并且实现相对简单。因而作为电梯调度的基础算法。

但是其由于严格按照请求的顺序排列，因此往往会出现大量的上下方向切换，而且当请求很密集的时候，往往会出现因频繁上下处理不同的请求，效率急剧下降的问题。

为了解决大量请求效率下降的问题，后面提出了很多种算法。

最短服务时间优先算法（SSTF）可以通过先满足离当前位置最近的请求，通常能够实现电梯上下总层数更小的目的。并且可以使得距离当前楼层更近的请求先满足，当两边的请求距离都相同时，选择更早请求的。

这种方式的利用效率很高，往往能够实现在移动尽可能少的情况下把货物运输到目的地。不过由于一些离当前电梯楼层较远的请求，往往要很长的时间才能等到电梯，仍然有请求很密集时，因为电梯需要处理新请求而上上下下，导致效率下降的问题。

后面的算法都实现了尽可能单方向的运作，并且能够兼容新的请求，可以使电梯在一个方向上的运力更大。

扫描算法（SCAN）的特点是，电梯最开始会往指定的方向移动，一直处理沿途顺向的请求，直到到达方向上最后一个请求的楼层，才改变方向处理反向的请求。

如果电梯最开始指定的方向默认是最近的请求的方向，则其与SSTF算法是一样的，而且其稳定性更好，除了刚刚错过电梯的新请求外，都可以在处理既有请求的沿途被满足。

如果货物的上和下的量都非常大，以至于出现频繁上下影响效率的情况，还可以通过C-SCAN算法实现上下分离。

其特点是在SCAN算法的基础上，限制了单一的电梯只能往一个方向运输货物，在到达最后一个请求的时候，先回到这个方向上的第一个请求，再继续处理接下来的请求。虽然单一的C-SCAN算法会导致一些运行时间的开销，但是如果能够同时使用向上和向下的C-SCAN算法，将彻底解决上下行冲突问题。

上面这些算法是垂直向的电梯上下的基础

上面的算法在处理电梯上下的运作的同时，要考虑面对电梯运行时插入的新请求如何处理的问题。一种静态的方式是把电梯开始处理当前请求之后加入的新请求装入一个新队列，等到当前请求都处理完了，才处理新队列里的请求。这种方式虽然会导致后处理的队列等待时间长，但是对于计算机的磁盘而言，能解决请求频繁落在同一个磁道造成的饥饿问题，而且不需要经常中断当前的访问。

而由于电梯的新请求总是随机发生的，完全可以灵活地让电梯一边处理既有请求一边顺方向处理新请求（尤其是SSTF算法和SCAN算法）。并且电梯可以通过估计货物装载卸载时间实现类似SSTF算法的功能，即最短访问时间优先算法（SATF）。

下面举例，有一座建筑有128层，其中0-7层为地下，8-127层为地上，地面对应8层。初始时电梯在地面，下面写出货物运输请求的发出时间、目标楼层、装卸时间（单位为秒），以及对应不同算法下电梯的运行方式。定义每上下一层的时间是1秒，第一个请求发出时，电梯开始移动。

可以看到，SSTF算法、SCAN算法和C-SCAN算法都能够实现货物高效地垂直运输，SATF算法的移动层数虽然略多，但能够确保装卸时间更短的货物先被运输。

上面这些算法只是高层建筑里货物运送的一些模型，而且只考虑到单台电梯的运作。如果有多台电梯，可以通过电梯之间的协作，例如优先把请求分配给最近且顺向的电梯等，实现货物运送的同步性。另一方面，高层建筑里的电梯还会采取差异化停靠楼层以实现不同楼层的请求的分开运行。

总之，在我们通过向天空寻求生存空间的过程中，高效垂直移动的策略能让我们活用垂直建筑空间，创造垂直空间的货如轮转。

电梯算法提升了垂直方向运输的效率，构成著繁荣的美好生活

参考资料：

William Stallings著，陈向群、陈渝译，操作系统——精髓与设计原理（第九版），电子工业出版社，2021

知乎专栏：Angeline：据说程序员等电梯的时候都想过调度算法，网友：还真是

知乎问答：电梯算法是怎样的？