程序员等电梯时竟然想这事儿

每天早上，那些差5分钟就迟到的程序员，在等电梯时，一般会想两件事：

第一，在心里骂电梯慢；

第二，在心里暗算着电梯调度如何优化；

今天就为大家科普一下电梯调度算法，为在等电梯之余，打发时间做出一点贡献。（电梯调度算法可以参考各种硬盘换道算法，下面内容整理自网络）

传统电梯调度算法

1.1 先来先服务算法（FCFS）

先来先服务（FCFS-First Come First Serve）算法，根据乘客请求乘坐电梯的先后次序进行调度。它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，是一种最简单的电梯调度算法。

优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求得不到满足的情况。这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，性能就会严重下降，甚至恶化。

1.2 最短寻找楼层时间优先算法（SSTF）

最短寻找楼层时间优先（SSTF-Shortest Seek Time First）算法，它注重电梯寻找楼层的优化；这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。

在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“饿死”现象。

1.3 扫描算法（SCAN）

扫描算法（SCAN） 是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。

效率比较高，但它是一个非实时算法。扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的。

扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻找楼层时间优先算法小，从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法稳定。

1.4 LOOK 算法

LOOK 算法是扫描算法（SCAN）的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。

但当 LOOK 算法发现电梯所移动的方向上不再有请求时立即改变运行方向，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。

1.5 SATF 算法

SATF（Shortest Access Time First）算法与 SSTF 算法的思想类似，唯一的区别就是 SATF 算法将 SSTF 算法中的寻找楼层时间改成了访问时间。

SATF 算法考虑到了电梯运行过程中乘客上梯时间的影响。

实时电梯调度算法

2.1 最早截止期优先调度算法

最早截止期优先（EDF-Earliest Deadline First）调度算法是最简单的实时电梯调度算法，它的缺点就是造成电梯任意地寻找楼层，导致极低的电梯吞吐率。

它响应请求队列中时限最早的请求，是其它实时电梯调度算法性能衡量的基准和特例。

2.2 SCAN-EDF 算法

SCAN-EDF 算法是 SCAN 算法和 EDF 算法相结合的产物。它的效率取决于有相同 deadline 的数目，因而效率是有限的。

2.3 PI 算法

PI（Priority Inversion）算法将请求队列中的请求分成两个优先级，它首先保证高优先级队列中的请求得到及时响应，再搞优先级队列为空的情况下在相应地优先级队列中的请求。

2.4 FD-SCAN 算法

FD-SCAN（Feasible Deadline SCAN）算法首先从请求队列中找出时限最早、从当前位置开始移动又可以买足其时限要求的请求，作为下一次 SCAN 的方向。

这种算法忽略了用 SCAN 算法相应其它请求的开销，因此并不能确保服务对象时限最终得到满足。

电梯问题的需求分析

4.1 电梯的初始状态

本人设置的电梯的初始状态，是对住宅楼的电梯的设置。

(1)建筑共有21层，其中含有地下一层（地下一层为停车场）。

(2)建筑内部设有两部电梯，编号分别为A梯、B梯。

(3)电梯内部有23个按钮，其中包括开门按钮、关门按钮和楼层按钮，编号为-1，1，2，3，4……20。

(4)电梯外部含有两个按钮，即向上运行按钮和向下运行按钮。建筑顶层与地下一层例外，建筑顶层只设置有向下运行按钮，地下一层只设置有向上运行按钮。

(5)电梯开关门完成时间设定为1秒。电梯到达每层后上下人的时间设定为8秒。电梯从静止开始运行到下一层的时间设置为2秒，而运行中通过一层的时间为1秒。

(6)在凌晨2：00——4：30之间，如若没有请求信号，A梯自动停在14层，B梯自动停在6层。

(7)当电梯下到-1层后，如果没有请求信号，电梯自动回到1层。

4.2 电梯基本功能

每一架电梯都有一个编号，以方便监控与维修。每一架电梯都有一实时监控器，负责监控电梯上下，向电梯升降盒发送启动、制动、加速、减速、开关电梯门的信号。若电梯发生故障，还应向相应的电梯负责人发送求救信号。

4.3 电梯按钮功能

电梯内部的楼层按钮：电梯内部对应每一个楼层的按钮成为楼层按钮。

电梯内部开门按钮：乘客按下开门按钮，电梯门将打开，让用户离开。

电梯内部关门按钮：乘客需要按下关门按钮，让电梯门关闭，使电梯进入运行状态。设置电梯的自动关门时间为8秒。

电梯外部向上按钮：此按钮表示上楼请求，当按下此按钮时，如果电梯到达按下此按钮的楼层。

电梯外部向下按钮：此按钮表示下楼请求，当按下此按钮时，如果电梯到达按下此按钮的楼层。