BUAA_OO_2020_UNIT2

BUAA_OO_2020_UNIT2

一、程式結構分析

• 第五次作業

  UML & Mertrics

  

  

  ​ 電梯的調度問題，實質上就是任務的請求與分配問題，筆者在第五次作業中採用簡單的“生產者-消費者”模型，建立了Din線程作為生產者解析輸入並增加運載請求，建立Elev線程進行輸出，待處理數據由主控類Ctrl維護，並作為電梯“調度器”，前兩者的操作由線程安全的Ctrl負責，後兩次作業也延續這樣的架構，事實是無需重構也應付得了本次迭代。但筆者請求隊列與調度器一體化，且只有一級調度，導致主控類異常臃腫。

• 第六次作業

  UML & Mertrics

  

  

  ​ 仍是老三樣，第六次作業中擴展功能比較容易實現，進行相關類的方法擴寫，主要是實現多電梯線程，筆者Ctrl類的處理不是很好，下一次重寫了Ctrl

• 第七次作業

  UML & Mertrics

  

  

  ​ 架構上沒有大的改動，為實現換乘功能，筆者建立了MyReq類存儲PersonRequst與乘客現處樓號，並面向過程根據換乘地圖為各型電梯建立了樓層映射機制

二、Bug分析

• 第五次作業中主要遇到的是多線程初見的線程調度bug，主要是筆者當時沒有找到精準的notify()條件，居然喚起了RUNNALBE的線程，由於Ctrl是共用的，導致輸入被電梯線程阻塞，好在最終確定了進入wait()的條件。
• 第六次作業筆者體會到了線程安全問題在本單元的重要性，在處理電梯數目輸入時，筆者竟然沒用輸入文檔的ElevatorInput.getElevatorNum(),而是用(new Scanner(System.in)).nextInt(),System.in被輸入介面與Scanner共用，導致輸入緩衝區線程不安全，筆者這次屬實拉了胯了，直接白給愉悅送走
• 第七次作業又出現了惡性bug,當C型電梯上的乘客想去樓4時，筆者直接給他送到樓3，但樓3只有C能去，B接不到，這次強測也是差點翻車了，不過三次作業筆者的整體結構還是可以的，通過嚴格控制synchronized語句塊的分佈與使用，三次作業除了這些bug也沒有出現過死鎖或是數據冒險啥的難以復現的bug

三、互測策略

• 第五次作業功能比較簡單，只要保證簡單的線程調度就只用考慮單電梯調度問題，可以輸入30條從底樓到頂樓的數據測試他人是否完成了捎帶
• 第六次沒進互測，不過筆者認為可以從電梯超載與輸入指令數最大化這兩方面進行hack
• 第七次重點在於線程安全與換乘，可以輸入僅1條需要換乘的指令，測試他人是否在換乘完成前相關電梯線程已退出，更可以圍繞換乘問題，觀察三類電梯樓號的定義域可以發現1,3,15是最特殊的3個換乘點，也可以枚舉所有請求後排除直達請求進行換乘的完備hack

四、對象創建模式

• 第五次作業只建立了輸入線程Din，電梯線程Elev，看到一些朋友把調度器也整成線程我是沒想到的，Din負責向Ctrl輸入數據，併在輸入及結束後喚醒所有WAITING的Elev，Elev的結束條件是沒有待調度請求並且Din在結束後設置了無輸入的全局變數。具體調度策略方面，選用LOOK演算法，但無論SCAN還是LOOK，都損失了一個方向上的請求信息，總感覺不太好。於是之後筆者就真香GREEDY了，打造了純貪心的電梯調度與電梯間調度策略

• 第六次作業改動不多，主要是改變了Ctrl中的數據結構適配多部電梯，另外的重頭戲就是電梯間調度，筆者在本次將單電梯改為貪心電梯，與同學交流中有的是用平均分配、隨機分配來分派任務到各個電梯，但筆者還是採用了電梯間自由地貪心競爭策略。原因是，設想有兩架Elev，一臺空載，一臺載有乘客，從同一樓號出發，對於某一請求而言，載人Elev因為電梯內請求而停靠或轉向的平均概率更高，空載更有可能搶到請求。實際上傳客越少越能直接相應電梯外請求，這有效減小某些電梯一直空轉的幾率，從而自動實現了優先順序任務分配，提高了Elev並行率，每次上一個人也可以Thread.sleep(5)提高並行率。還有就是這樣不用寫二級調度了

• 第七次作業，鑒於要實現換乘，有必要維護需要換乘乘客的當前樓號，於是筆者新建了MyReq類改進PersonRequst,對於上文二、中notify了運行線程的bug，筆者也找到了安全方便的方案

  for (int i = 0; i < elevNum; i++) {
              if (elevs.get(i).getState().equals(Thread.State.valueOf("WAITING"))) {
                  synchronized (elevs.get(i)) {
                      elevs.get(i).notifyAll();
                  }
              }
          }//先判斷是在wait()再notifyAll();
  

  同時要註意線程安全的坑，筆者是保證所有Elev最後一起DEAD的，防止要換乘的電梯早退

  解決線程設計後，煩人的換乘問題來了，各型電梯的樓號定義域A = [-3, 1] ∪ [15, 20],B = [-2, 15] - {3}，C = [1, 8] * 2 - 1，找到換乘點(A ∩ B) ∪ (A ∩ C) ∪ (B ∩ C) = (C - {3}) ∪ {-1, -2},筆者並不想寫二級調度，就建立了地址轉換，考慮Elev對MyReq的解析，我們只要在電梯A-C下完成MyReq在電梯內和在電梯外的樓號轉換就行,實際上完成前者就行，若電梯內getToFloor()非法，就將目的地改為換乘路徑最短的換乘點。電梯外的話，先假設上電梯，轉換後若目標就是當前樓層，就保留原本目的地，否則上電梯。筆者真是懶死了，這類特定情境問題還是最好畫圖分析或打表，別像筆者敗在細節。

五、心得體會

​ 筆者本單元的作業效果並不理想，還是對於線程安全的理解不深，以及沒有註重多線程程式設計中的細節問題導致bug，筆者還是對自己的調度器耿耿於懷，筆者理應實現隊列，調度分離的，這樣的調度器耦合度太高了。