程式猿在等電梯時都在想什麼？

高校俱樂部 今天

以下文章來源于程式人生 ，作者Cooper Song

作者 | Cooper Song

責編 | Elle

出品 | 程式人生（ID：coder_life）

都等這麼久了，電梯怎麼還沒來？？？一定是電梯排程有問題！那就讓我給它設計一個電梯排程算法。

電梯排程與作業系統中的磁盤排程是有聯系的。我大概在三年前就想過電梯排程的問題，那時我剛搬入高層住宅，然而當時我的專業功底還不夠紮實，也沒有深入研究。直到現在我接觸了作業系統中的磁盤排程算法，我才聯想到了電梯排程算法。異曲同工，殊途同歸，無非都是排程。在磁盤排程中，移動的是磁頭指針（相對的說），而在電梯排程中，移動的是電梯。

那麼電梯排程算法有哪些呢？它們都适用于哪些情況呢？

先來先服務算法

先來先服務算法的簡稱是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樓再回來接他，但是這樣可以讓錢大爺、張大爺、王大爺都相對滿意。

在這樣一種應用情景下，先來先服務算法和最短尋道時間優先算法都會讓其中的一位大爺或幾位大爺強烈不滿。

針對不同的應用場景，設計或選擇合适的算法，也是優秀程式員的優良品質之一。

用計算機科學領域的算法看待生活中的實際問題，也許就是計算思維的展現吧。