都等這么久了，電梯怎么還沒來？？？

一定是電梯調度有問題！那就讓我給它設計一個電梯調度算法。

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

那么電梯調度算法有哪些呢？它們都適用于哪些情況呢？

作者?| Cooper Song

責編 | Elle

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

01、先來先服務算法

先來先服務算法的簡稱是FCFS，是First Come First Serve的縮寫。顧名思義，就是先來到電梯門前的（或者說先按下電梯上下按鈕的）乘客先體驗電梯的服務。

舉個例子，李大爺在1樓按下了向上的按鈕，在此之后張大爺在15樓按下了向下的按鈕，在此之后王大爺又在8樓按下了向下的按鈕。王大爺跟張大爺約好要一起去菜市場買菜。

那么此時，無論電梯現(xiàn)在在幾樓，都會先去1樓接李大爺。

李大爺進入電梯后，無論他要去幾樓（假設李大爺要去20樓），到達目的地（20樓）之后，電梯就會去15樓接張大爺。

張大爺在15樓上了電梯，他要去菜市場買菜，因此他要到1樓，他進了電梯就按下了1樓的按鈕。

于是電梯呼呼呼開始下行，此時還在8樓的王大爺眼睜睜地看著電梯經(jīng)過了8樓繼續(xù)向下運行，竟然無視了他?。?！

張大爺順利到達1樓，此時電梯才向上來到8樓接王大爺，王大爺這才坐電梯到1樓與張大爺會和。

這可把王大爺氣壞了，心里不是在罵物業(yè)傻X，就是在罵寫電梯調度的程序員傻X……

先來先服務算法的弊端在上面這個例子中顯露無遺，但是它也有優(yōu)點呀，優(yōu)點就是簡單，程序員省事！開玩笑的，優(yōu)點就是相對來說比較公平，乘客得到電梯服務的順序一定是先來后到的，不會被人插隊。

02、最短尋道時間優(yōu)先算法

最短尋道時間優(yōu)先算法的簡稱是SSTF，是Shortest Seek Time First的縮寫，顧名思義，就是距離當前電梯位置最近的乘客，會最先得到電梯服務。

大爺們是否能得到電梯的服務，與電梯當前的位置有關。

還是舉上面那個例子，假如在大爺們來到電梯門口前電梯停在1樓。李大爺起初在1樓，無疑是距離電梯最近的，他先上電梯。李大爺來到20樓下了電梯。電梯此時在20樓，距離20樓最近的服務請求來自15樓的張大爺，于是電梯呼呼呼下行來到15樓接上張大爺，此時電梯在15樓，距離15樓最近的服務請求來自8樓的王大爺，這一次電梯沒有無視王大爺，接上了王大爺后，王大爺和張大爺一起開開心心坐到1樓去菜市場買菜去了。王大爺和張大爺一邊說著物業(yè)費沒白交，一邊夸著寫電梯調度的小伙子技術高。

王大爺和張大爺開心了，可把住在30樓的錢大爺氣壞了。原來在三位大爺按完按鈕之后（電梯剛接上1樓的李大爺）就按了按鈕，可是錢大爺看著電梯上行到15樓就改下行了……電梯到達15樓時，所有請求（包含服務請求和目的地到達請求）有這些：張大爺請求到1樓，8樓的王大爺請求上電梯，再就是30樓的錢大爺請求上電梯了。錢大爺距離電梯還差著15層樓呢，按照最短尋道時間優(yōu)先算法電梯肯定要先去8樓接王大爺。接完王大爺電梯肯定離著目的地1樓最近，也不會上去接錢大爺。

按照這樣想下去，如果此時3樓的趙大媽想下樓買菜，錢大爺還得眼睜睜看著電梯從1樓上行到3樓再改下行，估計要是真這樣錢大爺連搬家的想法都有了……

最短尋道時間優(yōu)先算法的弊端在上面這個例子中暴露無遺，那就是距離電梯較遠的乘客，可能永遠不會得到服務（如果電梯附近的樓層一直有服務請求）。

03、掃描算法

掃描算法的簡稱是SCAN，SCAN算法是電梯調度中使用最廣泛的一種算法。SCAN算法與當前電梯移動的方向有關（上行/下行），當前移動方向上距離電梯最短的請求將最先得到服務。電梯調度與操作系統(tǒng)磁盤調度不同的是，磁盤調度僅僅是為了讀寫磁盤，并沒有目的地這一說，而電梯調度是有目的地的。乘客進入電梯后按的樓層，就是目的地到達請求的樓層。

這就是為什么現(xiàn)代化的電梯門口都有兩個按鈕，一個上行，一個下行，乘客按了上行按鈕表示乘客想要上樓，乘客按了下行按鈕表示乘客想要下樓。

因此在SCAN算法中，僅僅在電梯的移動方向上還不行，目的地方向也要與電梯移動方向一致的乘客才有資格先上電梯。這樣在電梯向上行的時候，就只處理向上的服務請求（還有距離最遠的向下的服務請求）和向上的目的地到達請求，等到上行方向上不再有任何請求（包括服務請求和目的地到達請求），電梯再換向成下行。

下行也是如此，在電梯向下的時候，就只處理向下的服務請求（還有距離最遠的向上的服務請求）和向下的目的地到達請求，等到下行方向上不再有任何請求（包括服務請求和目的地到達請求），電梯再換向成上行。

在最短尋道時間優(yōu)先算法舉的例子中，問題得到了相對完美的解決。電梯送李大爺?shù)搅?0樓，就立刻去30樓接錢大爺，接到張大爺后電梯轉為下行，去15樓接了張大爺，又去8樓接了王大爺。李大爺、張大爺、王大爺、錢大爺都很滿意，電梯的利用率也較高。這一次，程序員不再背鍋。

04、結語

磁盤調度與電梯調度有相同的地方，也有不同的地方。我不知道是先有的磁盤調度還是先有的電梯調度，但我能肯定的是，他們兩者之間肯定存在著相互借鑒。

每一種算法都不能讓所有人都滿意，比如在掃描算法中，因為有錢大爺在30樓請求下樓，8樓的王大爺就要眼睜睜地看著電梯經(jīng)過了8樓上行到30樓再回來接他，15樓的張大爺也是眼睜睜地看著電梯經(jīng)過了15樓上行到30樓再回來接他，但是這樣可以讓錢大爺、張大爺、王大爺都相對滿意。

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

針對不同的應用場景，設計或選擇合適的算法，也是優(yōu)秀程序員的優(yōu)良品質之一。

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

筆者還是一名CC++的程序員，如果你想更好的提升你的編程能力，好好學習C/C++編程知識的話！那么你很幸運~

UP在主頁上傳了一些學習C/C++編程的視頻教程，有興趣或者正在學習的小伙伴一定要去看一看哦！會對你有幫助的~

分享（源碼、項目實戰(zhàn)視頻、項目筆記，基礎入門教程）

歡迎轉行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！

編程學習書籍：

編程學習視頻：