今天看到一篇文章，感覺很有意思，拿來給大家分享，也從一個側面看出程序員這個職業的辛苦，長時間高強度工作，加班更是家常便飯，且行且珍惜。
都等這么久了，電梯怎么還沒來？？？一定是電梯調度有問題！那就讓我給它設計一個電梯調度算法。 電梯調度與操作系統中的磁盤調度是有聯系的。我大概在三年前就想過電梯調度的問題，那時我剛搬入高層住宅，然而當時我的專業功底還不夠扎實，也沒有深入研究。直到現在我接觸了操作系統中的磁盤調度算法，我才聯想到了電梯調度算法。異曲同工，殊途同歸，無非都是調度。在磁盤調度中，移動的是磁頭指針（相對的說），而在電梯調度中，移動的是電梯。 那么電梯調度算法有哪些呢？它們都適用于哪些情況呢？ 先來先服務算法 先來先服務算法的簡稱是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樓再回來接他，但是這樣可以讓錢大爺、張大爺、王大爺都相對滿意。 在這樣一種應用情景下，先來先服務算法和最短尋道時間優先算法都會讓其中的一位大爺或幾位大爺強烈不滿。 針對不同的應用場景，設計或選擇合適的算法，也是優秀程序員的優良品質之一。 用計算機科學領域的算法看待生活中的實際問題，也許就是計算思維的體現吧。
