OO第二次博客作業——電梯調度

前言

最近三周，OO課程進入多線程學習階段，主要通過三次電梯調度作業來學習。從單部電梯的傻瓜式調度到有性能要求的調度到多部電梯的調度，難度逐漸提升，對同學們的要求逐漸變高，我們對線程的理解也逐漸加深。下麵筆者將對三次作業分別進行總結。

一、單部多線程傻瓜調度（FAFS）電梯

說明：本次作業需要模擬一個多線程實時電梯系統，從標準輸入中輸入請求信息，程式進行接收和處理，模擬電梯運行，將必要的運行信息通過輸出介面進行輸出。本次作業對性能要求非常寬鬆，不需要進行優化處理。

構思：由於不考慮性能，在Main中每收到一個輸入，新開啟一個Request線程，Request線程調用電梯類Elevator的work方法。其中work方法是synchronized的方法，所以一個請求未處理完前其他請求被阻塞。

程式複雜度：

由於演算法簡單，複雜度較低。

程式依賴：

在依賴上表現良好。

評價：線上程安全性上很完美，並且完成了所有功能，沒有bug。缺點在於性能不夠優秀XD。這次作業算是多線程的一次小練手，熟悉了多線程編程方法。

二、單部多線程可捎帶調度（ALS）電梯

說明：本次對電梯性能有一定要求，需要我們自行設計演算法或使用A Little Smart演算法。

構思：考慮到對性能的要求，使用的是類Look演算法。具體而言，電梯掃描同一方向的請求至無同向，然後反向。根據這一思路，設計了5個類。Main創建Controller和Elevator兩個線程。Controller負責接收輸入，並向RequestList中存入請求。Elevator掃描RequestList並取出請求。

程式複雜度：

平均複雜度尚可，在電梯類中有少數方法複雜度稍高。主要是遍歷請求列表和while迴圈電梯上下運行導致的，不可避免。

依賴：

代碼行數：

評價：在強測中出現了一個bug：同時間輸入大量請求，而調度器未能全部同時接受導致超時。分析：電梯上下樓、開關門時白白占用RequestList的鎖，應該讓調度器繼續運作。調整了鎖的分配，如關門時讓電梯wait一定時間，此時調度器可以占用鎖。

總結：由於對鎖的分配沒有思考到位，沒有最大化優化臨界資源使用率，導致在極端情況下性能出現問題。

三、多部多線程智能（SS）調度電梯

說明：本次作業有多部電梯，對性能要求放鬆了，將重點放線上程安全和同步的設計上，在於最大限度降低耦合，每個對象只應該管自己該管的事。

構思：延續上次作業的思路，對每個電梯分配一個請求隊列，調度器可以觀察3個請求隊列，並選擇性寫入。電梯在乘客換乘時調用調度器進行添加請求。這樣一來，就最大限度地降低了耦合。只有請求隊列是共用資源，容易處理線程的同步。

類圖：

 複雜度：

在遍歷請求列表時複雜度變大，總體較好。

依賴：

Controller與Elevator共用請求隊列。

行數：

評價：

強測出現bug，發生了死鎖。排查後發現問題在於在添加請求這一方法上偶然出現互相持有資源導致。調整synchronized的範圍，使死鎖的必要條件消失（請求資源前放棄資源）解決了bug。

總結：

在設計程式時沒有預防死鎖這一bug的出現，說明對線程同步的考慮仍然不夠周到。然而失敗是最好的老師，在這一次作業完成後，認識到構思程式時，應更加謹慎、全面地考慮線程安全問題。

Bug攻防

採用測評機發現bug，在最後一次閱讀代碼發現了bug。

心得體會

（1）保證線程安全。

　　做好資源的分配，尤其是預防死鎖的出現。

（2）集中化數據管理。

　　將一組單獨寫成一個類便於管理，例如電梯的狀態。

（3）在底層類實現方法，提供介面，頂層類直接調用，讓自己的代碼更有層次感、