BUAA OO Unit2 電梯調度_ZenDei技術網路在線

這次作業完成了一個開環可選層電梯調度系統。第二次迭代加入了容量限制、多部電梯，第三次迭代加入了電梯樓層分工、增添電梯請求。 1. 系統架構 MainClass用於對各個子系統的組裝，發送請求至Schedule Schedule用於接收來自MainClass、Executor的信息，更新狀態 Exec ...

這次作業完成了一個開環可選層電梯調度系統。第二次迭代加入了容量限制、多部電梯，第三次迭代加入了電梯樓層分工、增添電梯請求。

1. 系統架構

graph LR MainClass--Requests-->Schedule Executor--Notify-->Schedule Schedule--Update-->Executor MainClass--Create-->Elevators Schedule--Check-->Elevators Executor--Operate-->Elevators Schedule--Adapt-->Method

MainClass用於對各個子系統的組裝，發送請求至Schedule
Schedule用於接收來自MainClass、Executor的信息，更新狀態
Executor監聽Schedule的改變，使用單線程操縱所有電梯，同時將操作結果返回Schedule。
Method為策略模塊，實現同步控制與策略模塊的分離，可以用於適配不同的策略。

2. 同步控制

定時控制

同步控制的主要由Schedule設定，由Executor執行。併發控制的核心為一個阻塞定時監聽器，可實現可調整的定時控制。這個模塊的實現方法參考了java.utils.Timer。

private long scheduledTime = Long.MAX_VALUE;

public synchronized void retrieveNextAction() throws InterruptedException {
    long curTime = System.currentTimeMillis();
    while (curTime >= scheduledTime) {
        wait(scheduledTime - curTime);
        curTime = System.currentTimeMillis();
    }
    scheduledTime = Long.MAX_VALUE;
    return;
}

scheduledTime變數存儲下一次計划動作的時間，規定該時間只減不增。即只保障不存在早於scheduledTime的動作。
retrieveNextAction為阻塞方法，用於Executor阻塞獲取下一次的動作。
存在新的預期執行的動作時，更新scheduledTime，調用notifyAll()，retrieveNextAction重置等待時間/取消等待。
沒有設定動作時序隊列，每次完成時，需要檢索全部可能的動作，並根據執行情況設置下一個scheduledTime。
這樣做的主要優勢在於沒有用到Thread.sleep方法，可以實現任意時刻對請求的及時響應。

另外，除Schedule外，另一個共用變數為Elevator。這裡Elevator類僅用作記錄電梯狀態，提供改變電梯狀態的介面。所有操作由Executor根據Schedule產生，併在敏感操作（如關門-移動序列）的執行過程中進行了上鎖，屏蔽Schedule類的所有請求，保證一致性。

對於電梯移動，在Executor中對Schedule上鎖保證安全性。對於人員流動，使用ConcurrentLinkedList定義可執行隊列保障安全性，併在電梯移動時清空。Executor請求完成後調用相應方法通知Schedule，根據策略更新預期動作。

UML協作圖（Sequence Diagram）

elevator seqUml

* 協作圖中動作可能不滿足正確性，但反應了動作之間的時序關係。

* 2個線程為MainClass主線程和Executor執行線程。Schedule、Elevator為共用變數，被動進行數據調取。

* 還存在Schedule-Elevator之間的調用。

同步控制相關版本迭代

第二次作業：
- 去除了不必要的分支，簡化了定時阻塞器、終止判斷的執行流程，取消了不必要的PersonAction包裝。
- Schedule類中增加了notifyPersonCheckedIn，notifyPersonCheckedOut方法，以適應電梯容量受限導致的策略變化。
- Schedule類內中的電梯相關數據由單一數據轉變為列表控制。訪問數據時使用電梯索引值訪問。
- Executor類內，每次檢測到Schedule類存在新動作時，由檢查單一電梯轉變為檢查全部電梯。實現巨集觀上的電梯併發效果
第三次作業：
- Schedule類中增加評判：人員是否需要從電梯中出去。前兩次作業中只要滿足與人員請求目標樓層相等都要出去。
- Schedule類中增加方法：AddElevator。在全部數據列表中增加一項即可。
- 優化代碼結構，Schedule類使用泛型訪問電梯介面，實現不同種類電梯和對應策略類的匹配。

3. 架構設計

本節以第三次作業的版本為準討論了架構設計和可擴展性。

Unit2 Task3 Interface Uml

需要實現2個介面：IElevator、OperationMethod。

OperationMethod需要對canGetIn、canGetOff、nextfloor詢問做出答覆，接收addElevator、 notifyRequestReceived兩個輔助更新請求。
IElevator需實現運行時間查詢、電梯情況查詢、電梯操作、人員操作相關方法。
實際上Elevator類已經實現IElevator，一些特殊種類的電梯可以進行重寫通過相關方法實現。同時Elevator的類型可以藉助泛型通過Schedule傳遞到OperationMethod，實現策略類與電梯的一一對應。

第三次作業通過繼承的方法已經實現了樓層限制電梯，以及針對3中樓層限制電梯的方法不同方法。

功能-性能平衡

由於採用了策略與調度分離的架構，使得在實現相應功能的同時，為策略的制訂保留了很大的空間，同時允許對不同的策略進行試驗。但在策略制訂的過程中，可擴展性做的不是很好，功能的調整往往需要策略做出較大的調整，在前幾次作業中均進行了策略重構，可能也與使用的策略具有較高的特殊性有關。

準則異常

單一責任準則：Schedule類和Executor類是所有請求實現的關鍵路徑，對進一步添加請求不理想，應考慮建立請求介面，將請求執行步驟抽象為【電梯操作-調度更新-時間等待-新的請求】。

介面隔離：應考慮將策略介面拆分成發送策略介面、接受數據改變介面。

需求擴展方法

對於後續的擴展，可以根據擴展的類型進行版本迭代。

級別1：具有不同樓層限制規則的電梯、更新評價方法。

擴展ElevatorRestricted.Type枚舉類型，編寫新的MethodTypeD，調整MethodTask3分配策略。
級別2：新的限制規則電梯/樓梯、不定時電梯。

建立新的Elevator類，重寫Elevator相關方法，較大規模的調整MethodTask3分配策略，編寫新的MethodTypeD。
級別3：新的請求類型。如：停用電梯、更改請求

在Schedule類中增添新的方法適配請求，檢查Executor類的執行過程是否符合新條件下的請求要求。考慮IElevator、OperationMethod介面中是否需要增添方法適配請求。

如果請求的類型較多，可以考慮建立請求介面，將請求執行步驟抽象為【電梯操作-調度更新-時間等待-新的請求】過程，在Executor和Schedule中設立相應設施。
級別4：新的調度維度。如：水平電梯

建立新的調度策略。重構電梯類，將一維操作改為2維，併在所有訪問位置進行修改。

4. 度量分析

類複雜度（Weighed Method Complexity）

第一次作業	第二次作業	第三次作業

第一次作業中對2種策略進行了測試，最終選用了略微優化的Als策略。另一種策略過於複雜而且效果不是很好。第二次作業中對ALS策略進行了調整，以適配多電梯，效果類似於LOOK策略，但實現後導致MethodAlsMultiple複雜度過高。第三次作業將策略分成主策略和子策略，類複雜度可以接受，MethodAlsMultiple基本未作修改。

方法複雜度（Cyclomatic Complexity）

第一次作業	第二次作業	第三次作業

這幾次作業設計中Executor線程需要完成全部動作的發送，工作量較大，一開始放在了run方法，儘管後來做出了一些步驟的提取，仍舊有很多步驟被留在了run方法中，導致複雜度較高，這個是不恰當的。

另外，在第三次作業中，部分優化方法直接進行了重覆邏輯的複製粘貼，在一個方法內引用了較多外部參數，還需要進一步重構。

迴圈依賴

第一次作業	第二次作業	第三次作業

第一次作業由於分包不太恰當，導致根目錄和子包出現了迴圈依賴，同時策略類和調度器也存在迴圈應用。第二次作業調整了Timer類的分包，建立了策略類和調度器的共有引用類，解決了這個問題。第三次作業由於子類實現了主類的內部介面，而主類有又持有子類的引用導致迴圈引用（所以根據規範應該把內部介面放在外部，或者編寫額外的工廠類組裝主類、子類）。

類結構圖

第一次作業：實驗了2個方法：ALS和動態規劃。PersonAction抽象的不太恰當。Timer類分包不太恰當。

uml1

第二次作業：PersonRequest嵌套提供的PersonRequest，用於實現一些特殊/虛擬的的請求。層級關係較第一次作業更好。但Elevator有待進一步抽象。

uml2

使用介面-繼承的方式進行了迭代更新。層次結構進一步優化。不過MethodTask3和SubMethod關係有待調整（之前已經闡述）。MainClass引用過多，應建立初始化相關類。

uml3

5. BUG分析

第一次作業中，中測階段的bug主要為題目理解不當，沒有正確的使用輸出包，強測互測沒有發現Bug。

第二次作業中，強測互測階段也沒有發現Bug。

第三次作業中，強測階段沒有發現bug，但互測階段發現了兩個較為嚴重的bug。一個是電梯容量定義錯誤，然而在之前的中測強測中由於數據較為均勻、稀疏，加上C電梯利用率較少沒有被測出來，自測時也沒有再做檢查。另一個是上電梯後，儘管已經通知了調度器更新，但在調度器更新函數的編寫時沒有考慮換乘問題，導致換乘時可能出現一個人上兩個電梯的情況，在更新函數中加入一個刪除相同請求就可以了。這個可能原因是前兩次作業調度器編寫時內聯邏輯過多導致魯棒性不高，環境改變後忘記了相關內聯邏輯。

6. 測試

簡易評測樣例定時讀入類

使用自己編寫的ScannerX實現了一個簡易的定時輸入，滿足基本的測試需求。在test模塊中，將main函數中的ElevatorInput替換為ScannerX即可測試。定時輸入使用sleep進行定時，在第一次調用時初始化，根據當前時間進行修正。

測試策略

手動數據：構造少量邊界性數據
隨機測試：生成一些數據，在時間邊界投放。作業3中隨機測試偏向於高頻生成邊緣樓層（如3樓、-3樓、15+樓等）。
覆蓋性測試：覆蓋作業3中所有的換乘情況

實際上第二第三次互測中均沒有發現其他人的bug，可能是強測成績比較好分到的屋大佬較多...第一次互測中由於定時輸入沒有做時間修正導致hack數據時間不准確，沒有hack上。

和第一單元測試相比，這次測試評測機搭建更為麻煩一些，不像第一單元直接使用sympy計算就可以驗證正確性，同時樣例投放也更加困難一些。這導致測試的效率下降了一些。

7. 心得體會

多線程程式

這次是第一次完整地編寫多線程協同程式。在併發程式的編寫中，需要仔細地考慮衝突問題，但如果對於每一個語句都進行考慮顯然是不划算的。一方面是經典模型引入，例如讀者、寫者問題，生產者、消費者問題的解決方法，一方面是系統架構的獨立性。如果將一個大的併發問題拆解成幾個獨立的鏈條，僅需考慮鏈條與鏈條的併發、鏈條內部的互訪問，便可以“分而治之”，運用相關模型逐個擊破。

優化策略

在第一次作業中一開始嘗試使用動態規劃的思想進行優化，然而實際上效果並不是很理想，而且複雜度很高，後來採用了改進的ALS策略。實際上和緩存機制類似，由於我們並不知道未來可能存在什麼請求，因此無法將其轉化成背包問題，在請求來臨前就實現最優調度。ALS和LOOK等方法看似和動態規劃相比不是最優，但和SJF、FIFO等演算法類似，都是一種基於已知內容的可行優化策略。

在第二次第三次優化的過程中，基礎上採用了ALS演算法的定向捎帶原則，並借鑒粒子群優化演算法的思想，對空閑電梯制定了打散策略，空閑電梯運動方向受到來自於其他電梯，與電梯容量、距離相關的壓力的影響，使電梯容量傾向於在電梯運行空間內均勻分佈，以減少調度時間期望。同時第三次作業不同種類的電梯制定了單獨的策略，一個重要的策略是減少A類電梯空轉時間。最終在強測中均獲得了99分以上的成績。

這兩個方法還有很大的改進空間。這幾次作業優化的主要路線都集中於如何應對未來可能的請求，而對當前已有的請求策略並不是最優。第三次作業的請求分配也存在問題，可能與當前最優偏離較大，但在隨機數據情況下偏離不太明顯。另一個優化路線是何澤欣同學的基於模擬的估價函數，模擬不同狀態下電梯運行時間以完成評判。如果可以建立一個歷史與未來的請求相結合的分配方法可能會有更好的效果。

實際上優化一個策略函數是一個比較複雜的問題，特別是針對未來的請求期望。或許可以有一些機器學習的方法，例如梯度下降法加以解決，完成對策略函數的擬合。

P.S.如果針對強測，考慮到助教、同學之間的博弈，均衡應該是完全隨機的數據，這個也是打散演算法較為重要的原因。

BUAA OO Unit2 電梯調度