程序猿在等电梯时都在想什么？

点击上方蓝字设为星标

都等这么久了，电梯怎么还没来？？？一定是电梯调度有问题！那就让我给它设计一个电梯调度算法。

电梯调度与操作系统中的磁盘调度是有联系的。我大概在三年前就想过电梯调度的问题，那时我刚搬入高层住宅，然而当时我的专业功底还不够扎实，也没有深入研究。直到现在我接触了操作系统中的磁盘调度算法，我才联想到了电梯调度算法。异曲同工，殊途同归，无非都是调度。在磁盘调度中，移动的是磁头指针（相对的说），而在电梯调度中，移动的是电梯。

那么电梯调度算法有哪些呢？它们都适用于哪些情况呢？

先来先服务算法的简称是FCFS，是First Come First Serve的缩写。顾名思义，就是先来到电梯门前的（或者说先按下电梯上下按钮的）乘客先体验电梯的服务。

举个例子，李大爷在1楼按下了向上的按钮，在此之后张大爷在15楼按下了向下的按钮，在此之后王大爷又在8楼按下了向下的按钮。王大爷跟张大爷约好要一起去菜市场买菜。

那么此时，无论电梯现在在几楼，都会先去1楼接李大爷。

李大爷进入电梯后，无论他要去几楼（假设李大爷要去20楼），到达目的地（20楼）之后，电梯就会去15楼接张大爷。

张大爷在15楼上了电梯，他要去菜市场买菜，因此他要到1楼，他进了电梯就按下了1楼的按钮。

于是电梯呼呼呼开始下行，此时还在8楼的王大爷眼睁睁地看着电梯经过了8楼继续向下运行，竟然无视了他！！！

张大爷顺利到达1楼，此时电梯才向上来到8楼接王大爷，王大爷这才坐电梯到1楼与张大爷会和。

这可把王大爷气坏了，心里不是在骂物业傻X，就是在骂写电梯调度的程序员傻X……

先来先服务算法的弊端在上面这个例子中显露无遗，但是它也有优点呀，优点就是简单，程序员省事！开玩笑的，优点就是相对来说比较公平，乘客得到电梯服务的顺序一定是先来后到的，不会被人插队。

最短寻道时间优先算法

最短寻道时间优先算法的简称是SSTF，是Shortest Seek Time First的缩写，顾名思义，就是距离当前电梯位置最近的乘客，会最先得到电梯服务。

大爷们是否能得到电梯的服务，与电梯当前的位置有关。

还是举上面那个例子，假如在大爷们来到电梯门口前电梯停在1楼。李大爷起初在1楼，无疑是距离电梯最近的，他先上电梯。李大爷来到20楼下了电梯。电梯此时在20楼，距离20楼最近的服务请求来自15楼的张大爷，于是电梯呼呼呼下行来到15楼接上张大爷，此时电梯在15楼，距离15楼最近的服务请求来自8楼的王大爷，这一次电梯没有无视王大爷，接上了王大爷后，王大爷和张大爷一起开开心心坐到1楼去菜市场买菜去了。王大爷和张大爷一边说着物业费没白交，一边夸着写电梯调度的小伙子技术高。

王大爷和张大爷开心了，可把住在30楼的钱大爷气坏了。原来在三位大爷按完按钮之后（电梯刚接上1楼的李大爷）就按了按钮，可是钱大爷看着电梯上行到15楼就改下行了……电梯到达15楼时，所有请求（包含服务请求和目的地到达请求）有这些：张大爷请求到1楼，8楼的王大爷请求上电梯，再就是30楼的钱大爷请求上电梯了。钱大爷距离电梯还差着15层楼呢，按照最短寻道时间优先算法电梯肯定要先去8楼接王大爷。接完王大爷电梯肯定离着目的地1楼最近，也不会上去接钱大爷。

按照这样想下去，如果此时3楼的赵大妈想下楼买菜，钱大爷还得眼睁睁看着电梯从1楼上行到3楼再改下行，估计要是真这样钱大爷连搬家的想法都有了……

最短寻道时间优先算法的弊端在上面这个例子中暴露无遗，那就是距离电梯较远的乘客，可能永远不会得到服务（如果电梯附近的楼层一直有服务请求）。

扫描算法的简称是SCAN，SCAN算法是电梯调度中使用最广泛的一种算法。SCAN算法与当前电梯移动的方向有关（上行/下行），当前移动方向上距离电梯最短的请求将最先得到服务。电梯调度与操作系统磁盘调度不同的是，磁盘调度仅仅是为了读写磁盘，并没有目的地这一说，而电梯调度是有目的地的。乘客进入电梯后按的楼层，就是目的地到达请求的楼层。

这就是为什么现代化的电梯门口都有两个按钮，一个上行，一个下行，乘客按了上行按钮表示乘客想要上楼，乘客按了下行按钮表示乘客想要下楼。

因此在SCAN算法中，仅仅在电梯的移动方向上还不行，目的地方向也要与电梯移动方向一致的乘客才有资格先上电梯。这样在电梯向上行的时候，就只处理向上的服务请求（还有距离最远的向下的服务请求）和向上的目的地到达请求，等到上行方向上不再有任何请求（包括服务请求和目的地到达请求），电梯再换向成下行。

下行也是如此，在电梯向下的时候，就只处理向下的服务请求（还有距离最远的向上的服务请求）和向下的目的地到达请求，等到下行方向上不再有任何请求（包括服务请求和目的地到达请求），电梯再换向成上行。

在最短寻道时间优先算法举的例子中，问题得到了相对完美的解决。电梯送李大爷到了20楼，就立刻去30楼接钱大爷，接到张大爷后电梯转为下行，去15楼接了张大爷，又去8楼接了王大爷。李大爷、张大爷、王大爷、钱大爷都很满意，电梯的利用率也较高。这一次，程序员不再背锅。

结语

磁盘调度与电梯调度有相同的地方，也有不同的地方。我不知道是先有的磁盘调度还是先有的电梯调度，但我能肯定的是，他们两者之间肯定存在着相互借鉴。

每一种算法都不能让所有人都满意，比如在扫描算法中，因为有钱大爷在30楼请求下楼，8楼的王大爷就要眼睁睁地看着电梯经过了8楼上行到30楼再回来接他，15楼的张大爷也是眼睁睁地看着电梯经过了15楼上行到30楼再回来接他，但是这样可以让钱大爷、张大爷、王大爷都相对满意。

在这样一种应用情景下，先来先服务算法和最短寻道时间优先算法都会让其中的一位大爷或几位大爷强烈不满。

针对不同的应用场景，设计或选择合适的算法，也是优秀程序员的优良品质之一。

用计算机科学领域的算法看待生活中的实际问题，也许就是计算思维的体现吧。

原文始发于微信公众号（五分钟学算法）：程序猿在等电梯时都在想什么？