Unit 2 Summary
Unit 2 Summary
by Mike Liu
代碼分析
總的來看，本單元三次作業的架構沒有大的變化。
主要的類（線程）有三個：主類（讀入線程）MainClass，電梯Elevator和電梯控制器Controller。
- 每個電梯線程均和一個控制器線程形成一一對應關系。
- 主類負責讀入請求，并隨即決定將請求分配給某一部電梯，加入該電梯的控制器的請求隊列中。當輸入結束時，讀入線程即結束。
- 控制器負責根據電梯的狀態來將請求送入/取出電梯。當電梯線程結束時，控制器才結束。
- 電梯自動根據電梯內部的請求確定目標樓層并運行；當內部沒有請求時，自動從控制器處獲得一個目標樓層；每到達一層時，會自動根據電梯內部請求和控制器中已有的請求決定是否開門。只有當控制器中沒有請求且輸入已經結束時，電梯線程才結束。
控制器中的請求隊列使用ConcurrentLinkedQueue儲存，每次電梯開門時即遍歷該隊列，將需要進電梯的請求從中移除并送入電梯。
Homework 5
Preview
本次作業較為簡單，調度策略的核心在于電梯如何確定主請求。
靜態分析
-
方法分析
Method CONTROL ev(G) LOC V v(G) Controller.Controller(Elevator) 0 1 4 13 1 Controller.addRequest(PersonRequest) 0 1 4 19 1 Controller.endInput() 0 1 4 11 1 Controller.endRequest() 0 1 3 8 1 Controller.feedPerson() 2 1 14 167 4 Controller.getMainRequest(int) 6 4 29 528 9 Controller.requestEnded() 0 1 3 24 2 Controller.run() 6 1 24 166 7 Controller.someoneToGetIn(int) 2 3 10 120 4 Elevator.Elevator() 0 1 4 16 1 Elevator.doorClose() 3 2 14 89 3 Elevator.doorOpen() 3 2 15 99 3 Elevator.endService() 0 1 3 8 1 Elevator.getController() 0 1 3 8 1 Elevator.getFloor() 0 1 3 8 1 Elevator.getHead() 0 1 3 8 1 Elevator.getIn(PersonRequest) 0 1 5 46 1 Elevator.getMainRequest() 6 1 24 292 9 Elevator.getMainRequestFromController(boolean) 7 1 25 322 13 Elevator.getOffAll() 3 1 16 202 5 Elevator.goOneFloor() 3 2 16 133 5 Elevator.isOpen() 0 1 3 15 1 Elevator.run() 2 1 11 79 5 Elevator.serviceEnded() 0 1 3 8 1 Elevator.someoneToGetOff() 2 3 8 51 3 MainClass.main(String[]) 3 3 15 99 3 -
類分析
Class CBO DIT LCOM LOC NOAC OCavg Controller 3 2 1 101 7 2.33 Elevator 2 2 1 169 14 2.31 MainClass 2 1 1 17 1 3 -
類圖
![hw5]()
設計策略
可以看出，復雜度主要體現在電梯的getMainRequest函數；該函數是第一次作業調度策略的核心。
- 當電梯內部有請求時，該函數取出電梯內請求隊列中到達樓層距當前樓層最遠的一個作為主請求；
- 當電梯內部無請求時，該函數通過
getMainRequestFromController流程，調用控制器的Controller.getMainRequest函數，從控制器獲得一個目標樓層。當控制器中無請求時，電梯線程進行wait，直到控制器中有新的請求，或所有輸入結束。
Homework 6
Preview
本次作業加入了多部電梯，核心在于請求的分配。
靜態分析
-
方法分析
Method CONTROL ev(G) LOC V v(G) Controller.Controller(Elevator) 0 1 4 13 1 Controller.addRequest(PersonRequest) 0 1 4 19 1 Controller.calcWeight(PersonRequest) 3 1 19 436 6 Controller.endInput() 0 1 4 11 1 Controller.endRequest() 0 1 3 8 1 Controller.feedPerson() 4 4 17 185 5 Controller.getMainRequest(int) 6 4 29 528 9 Controller.requestEnded() 0 1 3 24 2 Controller.run() 6 1 24 166 7 Controller.someoneToGetIn(int) 2 3 10 120 4 Elevator.Elevator(String) 0 1 5 28 1 Elevator.doorClose() 3 2 15 105 3 Elevator.doorOpen() 3 2 15 105 3 Elevator.endService() 0 1 3 8 1 Elevator.getController() 0 1 3 8 1 Elevator.getFloor() 0 1 3 8 1 Elevator.getHead() 0 1 3 8 1 Elevator.getIn(PersonRequest) 1 2 8 99 2 Elevator.getMainRequest() 6 1 24 292 9 Elevator.getMainRequestFromController(boolean) 7 1 25 322 13 Elevator.getNumOfPerson() 0 1 3 11 1 Elevator.getOffAll() 3 1 18 247 5 Elevator.goOneFloor() 3 2 16 208 7 Elevator.isFull() 0 1 3 19 1 Elevator.isOpen() 0 1 3 15 1 Elevator.run() 4 3 13 109 7 Elevator.serviceEnded() 0 1 3 8 1 Elevator.someoneToGetOff() 2 3 8 51 3 MainClass.main(String[]) 10 5 40 668 9 RequestComparator類中只包含了一些用來比較兩個請求的靜態方法，此處不列。 -
類分析
Class CBO DIT LCOM LOC NOAC OCavg Controller 4 2 1 123 8 2.7 Elevator 2 2 1 187 16 2.39 MainClass 2 1 1 42 1 8 RequestComparator 1 1 3 44 9 1.67 -
類圖
![hw6]()
設計策略
可以看出，本次作業相較上一次，主類（讀入線程）的復雜度有了很大提升，因為其負責了請求的分配。
由于是多部電梯，且每部電梯有載客量限制，因此分配主要考慮的因素主要有兩點：一是當前電梯及其控制器中已有的請求數，二是新請求捎帶其他請求/被其他請求捎帶的能力。
綜上所述，本次作業采用了加權隨機的分配策略，具體策略如下：
- 每讀入一個新的請求，根據該請求為每個電梯計算一個權重\(weight\)：該權重最大值為1000，由兩部分組成：其中已有請求數\(numWeight\)貢獻70%，可稍帶/被捎帶的能力\(coverageWeight\)貢獻30%。
- 已有請求數貢獻的權重\(numWeight = 700\times2^{-totnum/9}\) ，其中 \(totnum\) 為電梯及其控制器中當前已有的請求數之和。
- 可稍帶/被捎帶的能力貢獻的權重
\(coverageWeight = 300\times\begin{cases}1, \text{當前請求起止于電梯當前層到目標層之間，且同向}\\0.75, \text{當前請求起于電梯當前層到目標層之間，且同向}\\0.5, \text{當前請求起止于電梯目標層之后，且同向}\\0.5\times2^{-diff/3},\text{其他 其中diff為當前目標層與請求起始層的樓層差絕對值}\end{cases}\)；
RequestComparator類中的靜態方法即是來完成對不同情況的判斷。
得到每個電梯的權重后，用隨機數決定將請求分配給哪部電梯；被分配到的概率和權重成正比例關系。決定后，隨即將該請求加入對應電梯的控制器的請求隊列。
之所以采用隨機策略，主要出于兩點考慮：一是權重計算本身并不精確，沒有用數據進行測試，只是憑感覺；二是調度時間本身受到很多不確定性因素影響，即使權重最高也不一定最優，因此用隨機的方式避免一些最壞情況發生。非常遺憾，由于本次作業出現了其他致命錯誤，導致強測全部WA，沒有能夠驗證該策略的效果。
Homework 7
Preview
第三次作業的核心是停層限制和換乘；因此核心是完成對請求的拆分，其余機制和功能不變。為了便于拆分請求，引入了自定義的請求類MyRequest，封裝了PersonRequest原有的接口，增添了對前驅/后繼請求的引用，以及對請求的激活功能。
靜態分析
-
方法分析
Method CONTROL ev(G) LOC V v(G) Controller.Controller(Elevator) 0 1 4 13 1 Controller.addRequest(MyRequest) 0 1 4 19 1 Controller.calcWeight(MyRequest) 3 1 19 436 6 Controller.endInput() 0 1 4 11 1 Controller.endRequest() 0 1 3 8 1 Controller.feedPerson() 7 5 20 254 7 Controller.getMainRequest(int) 8 5 30 567 10 Controller.requestEnded() 0 1 3 24 2 Controller.run() 6 1 24 166 7 Controller.someoneToGetIn(int) 2 3 9 124 5 Elevator.Elevator(String,String) 9 2 28 247 5 Elevator.doorClose() 3 2 15 105 3 Elevator.doorOpen() 3 2 15 105 3 Elevator.endService() 0 1 3 8 1 Elevator.getController() 0 1 3 8 1 Elevator.getFloor() 0 1 3 8 1 Elevator.getHead() 0 1 3 8 1 Elevator.getIn(MyRequest) 1 2 8 99 2 Elevator.getMainRequest() 7 1 25 332 10 Elevator.getMainRequestFromController(boolean) 7 1 25 322 13 Elevator.getNumOfPerson() 0 1 3 11 1 Elevator.getOffAll() 3 1 20 269 5 Elevator.getType() 0 1 1 11 1 Elevator.goOneFloor() 3 2 16 208 7 Elevator.isFull() 0 1 3 19 1 Elevator.isOpen() 0 1 3 15 1 Elevator.run() 4 3 13 137 8 Elevator.serviceEnded() 0 1 3 8 1 Elevator.someoneToGetOff() 3 4 9 102 5 MainClass.main(String[]) 14 8 54 894 13 MyRequest.Link(MyRequest,MyRequest) 0 1 4 25 1 MyRequest.MyRequest(PersonRequest,String) 0 1 4 11 1 MyRequest.activate() 1 1 4 30 1 MyRequest.activateNext() 1 2 4 26 2 MyRequest.getFromFloor() 0 1 3 15 1 MyRequest.getPersonId() 0 1 3 15 1 MyRequest.getToFloor() 0 1 3 15 1 MyRequest.getVia() 0 1 1 4 1 MyRequest.getViaType() 0 1 1 11 1 MyRequest.isActive() 0 1 3 15 1 MyRequest.setVia(Elevator) 0 1 1 8 1 -
類分析
Class CBO DIT LCOM LOC NOAC OCavg Controller 5 2 1 126 8 3 Elevator 3 2 2 227 17 2.63 MainClass 4 1 1 56 1 12 MyRequest 5 1 3 38 10 1.09 RequestComparator 2 1 3 44 9 1.67 RequestSplitter 3 1 1 262 1 4 RequestSplitter.Node 1 1 0 13 0 1 -
類圖
![hw7]()
總的來說，本單元各線程分工比較明確，在類的設計上沒有特別的注意點。
設計策略
-
換乘拆分
-
用圖的思想，將每一層和每類型電梯在每一層的停靠點作為圖的結點，進出電梯、電梯上下運行的過程作為圖的邊。
-
為了最大限度地減少換乘，將表示電梯上下運行的邊長度設為實際運行需要的時間，將從樓層進出電梯的邊長度設為一個很大的值。
-
將每一層視為起點，分別跑一次SPFA，求出到其他各層的最短路徑。若無需換乘，則只求出需乘坐的電梯型號；若需要換乘（本題目中最多換乘一次），則求出兩次需乘坐的電梯型號和換乘樓層。
該部分其實可以內嵌在Java程序中進行。但由于用Java描述算法過于臃腫，且為了減少不必要的CPU開銷，本次作業書寫了額外的C++代碼用于執行SPFA算法最短路并打表，并將打表結果轉化為Java語句，寫入了
RequestSplitter類的static域。 -
-
請求設計
MyRequest中封裝了PersonRequest，并且存儲了前驅請求prev和后繼請求next的引用。當一個初始請求被拆分成兩個新請求時，調用MyRequest.Link方法分別設置兩個請求的next和prev為對方。- 當一個請求的
prev不為null時，表示該請求的前驅請求尚未完成，現在不能調度。 - 當一個請求的
prev為null時，表示該請求的前驅請求已完成或沒有前驅請求，現在可以調度。 - 當一個請求的
next不為null時，表示該請求有后繼請求；該請求結束（出電梯）后，將后繼請求的prev置為null，使得后繼請求可以被調度。
這樣，只需要在調度器中添加判斷條件（當前請求是否有前驅請求）即可，其余皆可繼承之前的作業。
- 當一個請求的
功能設計與性能設計
從功能角度來看，由于第一次作業的架構就具有很好的一般性，導致電梯系統的兼容性很強：只需要做好請求的分配即可，無需調整整體的架構。這樣的好處在后兩次迭代中也顯現出了優勢，每次迭代修改的代碼量很少。這樣即使后期有更多功能需求，也便于擴展；只需要修改上層的邏輯。
從性能角度來看，由于必須在請求讀入時就確定分配方案，調度機制不能機動地考慮到實時的情況，只能根據預定的方案和目前電梯的狀況來進行分配，顯然缺乏一些靈活性，且不是性能最優解。當然，可以通過后期修改參數來調整分配策略，使性能不斷優化；也可以設置不同的參數，來適應不同工作情況。
總體來說，本單元作業更傾向于功能設計，犧牲了部分性能。但還可以增加一些附加機制，如將已進入控制器的請求重新分配等，來提高性能。以及，由于寫第一次作業時對多線程還不夠熟悉，一些同步關系比較混亂，基礎架構還存在提升的空間；尤其是電梯線程和控制器線程的配合，還可以有更好的解決方法。
時序圖
Bug分析
Homework 5
強測和互測中均未出現bug。
Homework 6
本次作業中出現了一個bug，導致強測所有測試點WA。
在主類（讀入線程）中，同時使用了Scanner(System.in)讀入電梯個數和ElevatorInput(System.in)讀入電梯請求，產生了緩沖區沖突。
在中測時，由于同時進行評測的進程較少，讀入線程被及時調度：Scanner讀取第一個整數時，后續請求還未被輸入，此時Scanner只取走這個整數到緩沖區；之后的請求被ElevatorInput取走，運行正常。
在強測時，由于同時進行評測的進程較多，觀察到第一條輸出的時間戳往往為數秒之后，說明讀入線程未被及時調度：Scanner讀取第一個整數時，后續請求已經被輸入，此時Scanner為了提高讀入效率，將請求也取入了緩沖區；當ElevatorInput讀入時，就取不到Scanner緩沖區中的前幾個請求，導致了程序錯誤。
事后我也和助教討論了這一bug，提出了我的一些關于評測的疑問，不過我們的助教似乎不太擅長回答問題。其實我們曾經就遇到過類似的情況，比如cin比scanf慢，是因為cin要保持某種和scanf的同步，來使得兩種輸入可以同時使用而不出現錯誤；可以理解為二者用這種同步來保證不會將輸入被不正當地取入緩沖區。如果用std::ios::sync_with_stdio(false)來關閉同步，cin就和scanf速度相當，但不能混合使用。
Homework 7
強測全部通過；由于上一次作業沒有進入互測，導致了一些可能是遺留的bug，在本次互測中體現出來。
- 電梯開門運行邏輯不嚴密，在某些情況下到達目標層后不開門，導致卡住不動。
- 調度器每執行一次循環中的
feedPerson動作就必然喚醒一次電梯，導致電梯在暫時沒有請求時不斷wait - 被喚醒 - wait - 被喚醒……；更改后，只有在的確有人被feed入電梯的情況下才喚醒電梯，否則不喚醒。
由于采用了隨機策略，在某些情況下復現bug有一定的難度。調試時，主要采用了分時段手動輸入+print輸出的方法，主要查找線程等待與喚醒相關的部分，十分有效。
心得體會
第一次接觸到多線程編程，有很多概念需要重新理解。編程思路也和單線程編程有很大的區別：提前的架構設計非常重要，因為后期迭代開發時重構帶來的成本過高，設計時必須想清楚協作邏輯，留下良好的兼容性。
除了多線程編程思想之外，也是用一次強測爆0的成本意識到了一些問題，比如輸入輸出涉及的一些原理。
總之，多線程編程的思維量大幅度提升，需要考慮的問題也增多；要掌握這項技術還需要多加練習。
posted on 2020-04-18 13:10 Stitch11752 閱讀(155) 評論(0) 收藏 舉報
浙公網安備 33010602011771號