面向對象 | 第二單元 | 總結

• 2020 年 4 月 18 日
• 筆記

第二單元的內容為Java多執行緒設計，主要包括了Java多執行緒的實現方式、多執行緒同步控制、死鎖的產生與消除等問題，以複雜度迭代式遞增的電梯調度問題為載體，鍛煉多執行緒程式的設計、實現、調試的能力。

一、設計策略

我在第二單元相較於第一單元的進步之處在於，三次作業成功實現了同一設計框架下的迭代開發。

在第一次作業中，我就引入了三個執行緒：輸入請求執行緒(RequestInput)、調度執行緒(Dispatch)和電梯運行執行緒(ElevatorRun)，三者之間構成了三種生產者-消費者結構，其中特別要指出的是，Dispatch生成電梯運行指令序列送給ElevatorRun是一個生產者-消費者結構，ElevatorRun更新電梯資訊並送給Dispatch也是一個生產者-消費者結構，這種調度與電梯運行完全分離的設計結構是出於多部電梯的考慮，當存在不止一部電梯時，調度執行緒會依據某一演算法宏觀地進行調度和指令分配，各個電梯只根據各自接收到的指令運行。這裡所說的「電梯運行指令序列」有三大類情況：空序列、上或下一層、上或下一層並且有用戶進出，設計電梯運行指令序列這一結構的目的在於使得Dispatch能夠在最小時間粒度上對ElevatorRun進行安全且高效的閉環控制。

第二次作業輕鬆地繼承了第一次作業的結構，只是ElevatorRun執行緒不止一個，相應的要更改Dispatch中的調度演算法，使之適應多部電梯。在第二次作業中，引入了Algorithm介面，使調度演算法本身完全獨立起來，這樣在調度演算法需要修改或優化時，只需要更改實現了Algorithm的類即可，這裡的多部電梯是完全相同的電梯，Dispatch對於所有電梯的調度是完全同步的，當所有電梯執行完各自的指令序列時，Dispatch才會進行下一次計算、發送指令序列。

第三次作業在原先的結構上進行了比較大的擴展。因為引入了不同種類的電梯，且每種電梯不止一個，設計了介面Elevator和抽象類ElevatorAbstract來管理不同種類的電梯。對於同類電梯，採用第二次作業中的設計結構，即一個調度執行緒（考慮到命名的語義問題，在第三次作業中更名為Schedule）和多個電梯運行執行緒，對於三類電梯而言，設計一個總的請求分配執行緒(Dispatch)，其作用是初步分析所有的請求，按照一定演算法將其分配給某一類電梯的調度執行緒去，當然這中間是經過了緩衝區的（奉生產者-消費者結構為圭臬，所有的執行緒共享訪問都用生產者-消費者結構來實現）。要指出的是，Schedule還承擔了在每一次電梯執行完指令序列後，提取換乘請求並將其送回Dispatch的任務，這是程式中處理換乘的方式。

上面已經提到，所有的共享訪問都是採用生產者-消費者結構來處理的，緩衝區中設計特定的boolean型變數來進行同步控制，比如在Elevator中有readyForCmd，表示ElevatorRun已執行完當前的指令序列，Schedule停止等待並進行下一次調度計算和指令發送，在CommandBuffer中有commandReady，表示Schedule已經完成指令發送，ElevatorRun停止等待並執行指令序列。值得一提的是，關於執行緒結束的設計，在前兩次作業中，採用boolean型變數inputEnd來表示RequestInput輸入結束，當Dispatch獲取到該inputEnd為真時，Dispatch需要完成對當前所有請求（以及電梯正在服務的請求）的調度，然後將lastCommand設置為真，ElevatorRun在獲取到lastCommand為真時，結束執行緒。在第三次作業中，顯然不可以直接採用前兩次的方式，因為存在換乘的問題，RequestInput結束並不代表所有請求都得到了分配，所以設計了一個新的類Total，這個類的對象用來記錄當前未完成請求的個數，Dispatch根據inputEnd以及Total對象中未完成請求的個數來決定是否要終止進程。

二、擴展性分析

總體上講，我認為第三次作業的程式構架是不錯的。SRP原則要求每一個類應該盡量承擔單一的功能，符合得比較好，有改進的地方在於Elevator介面和它的實現類，Elevator介面里其實有兩大類方法，一類方法是含有與電梯運行密切相關的(up, down, in, out, open, close)，還有一類是與多執行緒（Elevator為ElevatorRun和Schedule所共享）共享變數密切相關，這其實可以再細分為兩個類。OCP原則要求軟體應該盡量通過增加軟體實體的方式進行功能擴展，而不是通過修改軟體實體的方式，程式在這方面則與具體的功能擴展有關，下面從不同情形的功能擴展分析可以看出程式在針對一些情況下很符合OCP原則，而在其它一些情況下卻無法符合OCP原則，總體上講，在程式構架設計之初，並沒有考慮到擴展性的問題，所有OCP原則符合情況並不好。LSP原則要求使用基類對象的方法必須能在不了解衍生類的條件下使用衍生類，這一原則符合得較好，程式為電梯和可到達樓層序列分別設計了兩個基類ElevatorAbstract和FloorAbstract，這兩個基類實現介面Elevator和Floor，程式的其它部分基本只使用Elevator和Floor對象。ISP要求一個介面對應一組高度內聚的操作，除了前面提到的兩個介面外，程式還有一個Occupied介面，用於處理電梯執行特定動作是花費時間的問題，Floor和Occupied對於ISP的符合程度較好，而上文分析過的Elevator則對ISP原則符合程度較差。DIP原則要求高層邏輯模組應該不依賴於底層模組的細節，這一原則符合得比較好。

1、更多類型的電梯

對於這種情況的處理幾乎是完美的，程式設計了Elevator和Floor兩大介面，分別用於管理不同類型的電梯和不同的可停靠樓層序列，當出現新類型的電梯時，只需要增加新的類實現Elevator和Floor介面，程式其它部分只會出現極少數的改動，當然這些極少數的改動也是可以避免的，比如設計工廠來管理管理Elevator的創建，在Floor里添加靜態方法來替換演算法中對於實現了Floor介面的所有類分別調用某一方法的操作。

2、特殊請求

主要有兩種特殊的請求，某一電梯在完成當前的服務後進入一定時長的維修狀態，某一電梯立即放下所有的請求並進入維修狀態。對於後一種情況的處理很容易的，程式對Request類進行了二次封裝，構成RequestInfo類，這個類能夠記錄用戶在出電梯時的樓層，如果該樓層與用戶目標樓層不同，則需要換乘，這一設計直接解決了立即進入維修狀態的問題。對於前一種情況處理起來則比較困難，Schedule完全控制了同一種類所有電梯的運行方式，而Schedule中Algorithm的對象完成了每一部電梯上行、下行、上人、下人的計劃，所以為了解決這一問題，這兩個類需要較大的改動。

3、優先順序請求

存在不同優先順序的用戶請求，這本質上是針對演算法而言的，只需要在Algorithm的實現類中對演算法進行修改即可，或者乾脆重新寫一個Algorithm的實現類替換掉原來的即可。

三、程式結構分析

可以看到，ElevatorAbstact,Dispatch,MyAlgorithm這三個類的複雜程度是比較高的。對於ElevatorAbstact類，上文也提到過，其實可以拆分成兩大類以降低複雜度；Dispatch完成了對所有請求的預分配功能，如果將分配演算法本身提取出來成為單獨的一類，就能夠降低其複雜度；MyAlgorithm集成了整個複雜的電梯調度演算法，如果按照調度步驟進行劃分，也可以分為結構較為簡單的幾個類，然後由一個上層的類進行封裝並實現Algorithm介面。

這是第三次作業的執行緒協作圖，清晰地描繪執行緒構架和依賴關係，前文已經有過簡單的描述。主執行緒啟動Request,Dispatch,Schedule這三類執行緒，ElevatorRun由管理該類型電梯的Schedule啟動，程式啟動之初，每類Schedule各自啟動一個Elevator，之後根據電梯請求啟動新增的Elevator。
這是第三次作業的UML類圖，為了將結構和重要的依賴關係清晰地展現出來，省去了部分屬性、方法和類。可以看到，執行緒與執行緒之間一律構成生產者-消費者結構，這是在程式設計之初決定的——統一用生產者-消費者結構處理執行緒共享訪問的問題。另外值得注意的是，對於Elevator介面，有一個ElevatorAbstract抽象類來實現，ElevatorAbstract又被ElevatorA,ElevatorB,ElevatorC所繼承，管理可停靠樓層序列的Floor也運用了這樣一個介面、一個抽象類、三個類的設計結構。

四、漏洞分析

綜合三次作業從程式調試的初期到強測漏洞修復中間出現的重要漏洞，大致可分為兩類：多執行緒漏洞和演算法漏洞。

在程式初步完成之後的調試初期，多執行緒漏洞比較明顯，某些執行緒無法啟動、某些執行緒無法結束、動態新增的執行緒無法正常運行、調度執行緒無法正常運行，這類漏洞一般表現為程式沒有輸出或只有極少輸出，也就是死鎖。我採用的主要調試手段是在程式中一些重要位置增加輸出資訊，比如在每個執行緒的啟動和結束時輸出資訊，在執行緒進入wait()和離開wait()時輸出資訊，這些資訊基本能夠直接確定死鎖發生的位置，再進一步分析程式碼邏輯即可以確定死鎖的原因。

System.out.println(getName() + ": start");//執行緒啟動時輸出
System.out.println(getName() + ": end");//執行緒結束時實處
System.out.printlen(threadName + ": start waiting for xxx");//執行緒進入wait()時輸出
System.out.printlen(threadName + ": end waiting for xxx");//執行緒離開wait()時輸出

值得一提的是，第三次作業在強測時出現了一個與執行緒同步相關的多執行緒問題，這是三次作業中唯一一個與死鎖無關的多執行緒漏洞，也是我在調試初期和中測中沒能發現的漏洞。漏洞表現為運行時錯誤，或者個別動態新增電梯的Schedule和ElevatorRun「錯位」了一個指令序列，比如一個從3樓到5樓的用戶請求，電梯在4樓接入用戶、6樓放出用戶。經過對程式碼邏輯的靜態分析，發現這一漏洞出現的根源在於Schedule向各個電梯獲取並復原readyForCmd資訊的時機不對，原先這一操作放在動態新增電梯前，導致同一個計算循環內，動態新增電梯的readyForCmd欄位無法復原，在極少數情況下程式會出現前述的表現，將這一操作移至計算循環的末尾就解決了問題。

關於演算法漏洞，主要是調度演算法和請求分配演算法的邏輯不完備或者效率低下的問題，與多執行緒本身沒有關係。在程式設計之初，我針對管理可停靠樓層序列的Floor進行了安全保護，當電梯運行到不合法的樓層時，程式立即輸出相關錯誤資訊然後終止運行，這一設計在程式調試的初期起到了不小的作用，幫助找到了演算法中的一些漏洞。還有就是針對一些特殊的請求（部分換乘請求），最初的演算法是存在漏洞的，針對特別的換乘請求進行調試，很容易發現並修復演算法的漏洞。

在hach別人的程式碼的過程中，我會針對自己程式碼出現過的漏洞構造測試樣例，比如一些特殊的換乘請求，也會針對RTLE進行測試，構造一些對於調度演算法效率要求較高的測試樣例。

五、心得體會

第二單元多執行緒編程在程式碼邏輯複雜度、程式碼量、調試難度上都要比第一單元提升很多，我花在第二單元上的時間相應也增加了很多，就程式架構的可擴展性和可迭代性而言，第二單元相較於之前是有進步的。多執行緒方面的漏洞是比較大的麻煩，尤其是上述提到的關於執行緒同步的漏洞，花費了很大時間才發現漏洞的原因。總體上說，通過第二單元的訓練，基本上熟悉了Java多執行緒程式設計、實現和調試。