「BUAA OO Unit 2 HW8」第二單元總結

2022 年 5 月 3 日
筆記
BUAA-OO, Java Programming

「BUAA OO Unit 2 HW8」第二單元總結

「BUAA OO Unit 2 HW8」第二單元總結

Part 0 前言

第二單元多執行緒已經告一段落，本單元中我收穫頗豐，在這裡再次總結記錄。

本篇部落格將分為以下幾個部分，讀者可自取所需：

Part 1 第五次作業
Part 2 第六次作業
Part 3 第七次作業
Part 4 多執行緒心得體會
Part 5 Tricks
Part 6 展望

其中，為了閱讀順暢，我將對象頭、鎖和同步以及執行緒安全——封裝安全輸出類兩個模組放在Part 1 第五次作業的後半部分介紹，但這兩塊內容貫穿始終，請讀者留意。

Part 1 第五次作業

1.1 作業要求

模擬實現支援五座樓，每座十層，且每座有一台電梯可以在本座所有樓層間運行的多執行緒實時電梯系統。

1.2 架構設計

第五次作業類圖如上圖示。

InputThread負責輸入，並將對應的Passenger委派給對應的樓座的WaitTable，對應樓座的電梯Elevator通過對應的WaitTable獲取請求。這裡，我還額外將存儲Passenger的容器封裝為一個PassengerQueue類，這將有利於未來迭代時更換實際上的容器而不更改PassengerQueue的介面。

這次作業中我採用了生產者-消費者模型，具體如下：

生產者：輸入執行緒InputThread
托盤：候乘表WaitTable
消費者：電梯執行緒Elevator

運行流程：生產者輸入執行緒獲取輸入，按照乘客類別不同，分別投放到對應的樓座的托盤候乘表WaitTable，消費者電梯執行緒自己運行，同時掃描其所在的樓座的WaitTable，按照其自身調度隊候乘表中乘客採取接客getPassenger方法。

結束標識：輸入得到ctrl + D結束訊號時，調用所有WaitTable的setEnd()方法，首先結束掉同時滿足對應樓座候乘表沒有未運送乘客且電梯內部沒有乘客的電梯執行緒；對於此時還在運行或不能被停止的電梯執行緒，WaitTable提供方法isEnd()，電梯可以通過該方法知道輸入訊號截止，並最終在對應樓座候乘表沒有未運送乘客且電梯內沒有乘客的時刻停止自身執行緒。

1.3 協作圖

1.4 調度分析

在第一單元中，任務需求較為簡單。考慮到單元訓練的重點是多執行緒設計以及為未來迭代做好準備，我秉持less is more的想法，在比較多種調度策略後最終選擇了LOOK演算法，其在滿足較高的性能的同時實現複雜度較低，這意味著更低的出bug概率以及更好的可擴展性。考慮到網上資料中並沒有詳細描述LOOK具體原理和實現的文章，我這裡簡單談談我的個人認知，可做參考。

當電梯有乘客時，以乘客中目標樓層距離當前樓層最遠的請求為主請求確定目標樓層
當電梯沒有乘客時，首先按照原方向，尋找距離當前樓層最遠的有請求的樓層，找到則確定為目標樓層，這次尋找最終結果有可能會是當前層。如果尋找無果（沿方向的所有層包括本層都沒有請求）則改變方向，繼續尋找。若最後沒有找到，則可以返回一個標誌結束的值表示電梯進入空閑。

1.5 bug分析

自己bug

本次作業在中測、強測和互測中沒有出現bug。最終得分為93.7485，可以看到性能分得分表現欠佳。儘管得分不高，但是本次作業遵循了魯棒性和可擴展性的要求，這為後續迭代開發和維護帶來了便利。

但是在中測的前幾次提交，分別出現了一些bug，以下分別介紹：

使用了`run`而不是`start`方法啟動執行緒

這是一個非常低級的錯誤，產生的原因是第一次寫多執行緒沒有經驗。值得注意的是，run方法是一個方法，其可以被調用這是自然的，但是多執行緒中應當採用start來啟動執行緒。

別人bug

在互測中，我主要通過評測機用大範圍隨機數據進行檢驗，沒有檢查出錯誤，但是有同學被其他屋內同學hack到，這意味著隨機數據的局限性。

1.6 對象頭、鎖和同步

榮文戈老師上課介紹了對象頭的相關知識，查閱相關資料後簡要整理如下：

對象實例結構

Java的實例對象儲存在Heap中，其結構如上圖示。

鎖和同步

如上圖示，對象頭部分儲存的資訊包含最近持有該對象鎖的執行緒ID。而我們使用的synchronized包含三種情況，分別是：

修飾實例方法：作用於當前對象實例加鎖，進入同步程式碼前要獲得當前對象實例的鎖
```
synchronized void method() {
  // CODE
}
```
修飾靜態方法：給當前類加鎖，會作用於類的所有對象實例，進入同步程式碼前要獲得當前 class 的鎖。

class資訊存儲在method area中。
```
synchronized void staic method() {
  // TODO
}
```
修飾程式碼塊：指定加鎖對象，對給定對象/類加鎖。synchronized(this|object) 表示進入同步程式碼庫前要獲得給定對象的鎖。synchronized(類.class) 表示進入同步程式碼前要獲得 當前 class 的鎖
```
synchronized(this) {
  // TODO
}
```

通過以上資料，我們可以更加清楚加鎖是如何進行和記錄的。

參考資料

對象鎖

包括方法鎖(默認鎖對象為this,當前實例對象)和同步程式碼塊鎖(自己指定鎖對象)。

方法鎖形式

synchronized修飾普通實例方法，鎖對象默認為this

public synchronized void method() {
    // CODE
}

程式碼塊形式

手動指定鎖定對象，可以是this，也可以是其他對象

synchronized (obj) { // obj可以為this或其他對象
    // CODE
}

類鎖

指synchronized修飾靜態的方法或指定鎖對象為Class對象。這種情況下，所有對象共用一把鎖。

靜態方法形式

public static synchronized void method() {
    // TODO
}

程式碼塊形式

synchronized (classA.class) {
    // TODO 
}

參考資料

關鍵字: synchronized詳解

1.7 執行緒安全——封裝安全輸出類

指導書中提示到，官方提出的輸出包執行緒不安全，即，獲得時間戳和輸出不是原子操作，可能出現時間戳和輸出內容不匹配的情況。經過lxh助教的提示，我們有以下兩種思路處理這個問題。

每次調用加鎖

第一種思路，我們可以在每次調用的時候都加鎖，這樣可以解決上述問題。得益於我們本次作業的輸出較為簡單，所以這樣也不會顯得很麻煩，但是當我們要包裝為「原子操作」的類方法很多時，或者，祖傳程式碼很長而我們只知道方法的介面的時候，可能會比較麻煩，以下介紹第二種方法。

封裝輸出類

單例模式

關於單例模式介紹，可以參考菜鳥教程-單例模式

封裝

利用單例模式，我們可以設計一個安全輸出類，這個類只有一個對象，提供的方法的參數同我們想要使執行緒安全的類的方法的參數完全相同，並使方法為synchronized的，這樣就可以保證每次調用同一個全局對象的方法，且是執行緒安全的。

CODE:

import com.oocourse.TimableOutput;

public class OutputThread {

    private static OutputThread outputThread = new OutputThread();

    private OutputThread(){}

    public static OutputThread getInstance() {
        return outputThread;
    }

    public synchronized void println(String msg) {
        TimableOutput.println(msg);
    }
}

Tip：構建上述OutputThread類後，我們仍需要在MainClass開頭調用TimableOutput.initStartTimestamp();。

化簡

實際上，為了使方法更具有普適性（適應要封裝為執行緒安全類的類有較多方法）以及應用完整的單例模式，上述程式碼在本例中略顯冗餘，可以如下化簡：

import com.oocourse.TimableOutput;

public class OutputThread {
    public synchronized void println(String msg) {
        TimableOutput.println(msg);
    }
}

Part 2 第六次作業

2.1 作業要求

模擬實現支援五座樓，每座十層，每座有一台基礎電梯可以在本座所有樓層間運行，支援加裝可在所有不同樓座同一層間運行的電梯，支援加裝縱向電梯的多執行緒實時電梯系統。

與第五次作業相比，本次作業的迭代要求為：

支援加裝可在所有樓座運行的橫向電梯
支援加裝可在所有樓層運行的縱向電梯
支援同一層不同樓座的乘客需求

2.2 架構設計

第六次作業UML類圖如上圖示。

本次作業基於第五次作業迭代而來，沒有進行大規模重構，因此主要介紹設計思路和迭代變化。

新需求分析

第二次作業的變化主要包括：增加橫向電梯種類並支援在同樓層不同座之間的乘客需求和支援動態增加（縱向和橫向）電梯數量。

對於第一個需求，我們秉持開閉原則，增設Elevator父類，縱向電梯ElevatorCol和橫向電梯ElevatorRow分別繼承它，只需在子類重寫run方法即可。

對於第二個需求，我們採用工廠模式，通過ElevatorFactory生產具有我們需要的功能的電梯。

請求群

對於同樓座（層），我們首先定義請求群的概念，一個請求群內的所有請求對該群內的所有電梯均可視（即電梯都有接到該請求的能力），群內所有電梯都可接待所有請求。

類虛擬空間

同時，為了簡化調度負擔及結構複雜度，我們借用OS中虛擬空間的思路。

對於群內的電梯，其可視所有請求，並且不認為有其他電梯，這樣即可不更改第一次電梯中的LOOK策略，並便於應用自由競爭的調度策略，這將在下一部分簡述。同時，通過類物理空間的理念，我們通過請求是否被真實滿足來避免產生衝突，保證了架構的安全性。

設計的核心理念

正確性、易維護性和可迭代性是我們架構設計的核心思想，秉持less is more的思路，我們儘可能在邏輯上簡化調度策略，在實現難度和迭代維護難度與性能方面做取捨平衡，最終選擇LOOK和自由競爭的策略。

讀寫鎖

在上述介紹中，電梯們對於所屬請求群內的候乘表讀相比寫更頻繁，可以採用讀寫鎖來進一步優化提升性能。

但是在實際驗證中，我們發現讀寫鎖對於性能提升非常有限，甚至在數據波動時反而會劣於synchronized。為了便於迭代和維護，最終我們仍選擇全部使用synchronized實現，這是一種在架構魯棒性和相對高性能之間的取捨。

2.3 協作圖

如上圖示為本次作業協作圖。

可以注意到，本次作業和第五次作業相比，設計和迭代是線性的，沒有改變架構和思路，這體現了我們架構較為優越的可擴展性和魯棒性。

2.4 調度分析

橫向LOOK

縱向LOOK在Part1 第五次作業 1.4調度分析中已經介紹過，這裡主要介紹縱向LOOK：

當電梯有乘客時，依然希望尋找其中目標樓座距離當前樓座最遠的請求為主請求，但是這裡的距離不應該是簡單的加減法，可以加上模運算（注意若出現負數直接取模不符合我們的要求）：
```
dis = (target - nowBuilding + 5) % 5;
```
當電梯沒有乘客時，原則上仍然按照第一次的方法尋找，只是如果第一次向上的盡頭是10層，這一次順時針盡頭應該變為 (now + 2) % 5；向下的盡頭是1層，這一次逆時針盡頭應該變為(now - 2 + 5) % 5。

LOOK的性能在隨機大數據中有較好的表現，同時易於實現。

自由競爭

上文中，我們介紹了請求群和虛擬空間的想法，在這基礎上，我們介紹自由競爭的具體實現。

對於每台電梯（無論橫縱），其均按照自己的LOOK進行調度運行；當其在訪問本請求群內的請求時，不會考慮別的電梯是否正在前往其中某個請求，而只考慮是否滿足自己的調度來運行。這樣，我們只需要在電梯arrive每層的時候訪問請求群內的請求即可，若其接到了請求，則在請求群內移除；若某格請求被其他電梯接走，而其事實上是使本電梯運行的動力，那麼至多付出一層的代價，本電梯就會重新訪問請求群並基於LOOK獲得新的運行方向。

上述設計較為精簡，在面對大數據時表現均衡；同時，省去了中央調度的設計，類分散式的思路使得電梯自行運動而無需被指派任務；並且對電梯數量沒有任何限制，覆蓋了作業要求的15部要求。

2.5 bug分析

自己bug

本次作業在中測、強測和互測中沒有出現bug。最終得分為96.2015，可以看到性能分得分優於上次，我認為這是自由競爭策略的優勢。儘管得分不高，但是本次作業遵循了魯棒性和可擴展性的要求，這為後續迭代開發和維護帶來了便利。

但是在中測的前幾次提交以及本地評測姬隨機測試中出現了一些bug，以下分別介紹：

空開關門

空開關門指的是，在自由競爭的模式下，多個電梯奔向同一個請求，在極小的時間內開門，但是人只進了一個電梯，而沒得到人的電梯便會再關門，此即空開關門。事實上，這並不算錯誤，但是會嚴重影響性能~~和觀感~~。

這個問題算是自由競爭模式下的典型問題。解決辦法是：將判斷有人可以進和真正將人放入封裝為原子操作。具體來講，在判斷當前樓層是否需要開門時，一旦判定有人可以接待，便直接將其從waitTable取走，在open後再真正將人in進來。得益於這樣的設計以及鎖的特性，不會存在多部電梯同時訪問到一個請求從而判斷自己可以開門而造成錯誤。

別人bug

本次作業共成功hack7次，分別是三位同學的bug。評測方法主要是評測機隨機測試。

忘記關門

有一位同學忘記關門，應該是迭代時只改了縱向沒改橫向。

RTLE

有兩位同學的電梯會在某些數據下在樓層間反覆橫跳，最終RTLE。有趣的是，其中一位同學的這個bug並不能穩定復現，該數據點交上去複測若干次才最終hack到。

可以看出，隨機數據測試具有一定可靠性，在讀程式碼找bug困難時不失為一種好的選擇。

Part 3 第七次作業

3.1 作業要求

模擬實現支援五座樓，每座十層，每座有一台基礎縱向電梯可以在本座所有樓層間運行，一層有一台可達全部樓座的中轉橫向電梯，支援加裝可在同一層間運行的橫向電梯，支援加裝縱向電梯，支援電梯包括速度、容量在內的自定義屬性，支援橫向電梯可達樓座的自定義屬性，支援起點終點間樓座不同樓層不同請求的換成需求的多執行緒實時電梯系統。

與第六次作業相比，本次作業的迭代要求為：

支援所有電梯自定義速度和容量屬性
支援橫線電梯自定義可達樓座屬性
一層加裝可達全部樓座的中轉橫向電梯

3.2 架構設計與新需求分析

本次作業架構設計如上圖示。可以看出，整體結構基本沒有發生變化，只為部分類增加部分內容。

支援自定義屬性

只需要在電梯類內部新增屬性即可。

支援自定義可達樓座

通過公式((M >> (P -'A')) & 1) + ((M >> (Q -'A')) & 1) == 2判斷是否可達即可。

值得注意的是，在支援自定義可達樓座後，同一層的橫向電梯應當所屬不同的WaitTable。

舉例而言，一個可達A和E的五樓橫向電梯與一個可達A和B的五樓橫向電梯對於需求為A-5 -> E->5的請求的處理應當是不同的，不滿足起點終點樓座均可達的請求不應當被電梯「看到」，這也是筆者的一個重要bug，將在後面介紹。

支援換乘

需要對請求進行劃分，對於一般的請求而言，需要「三段式」，即From Floor From Building -> From Building Middle Floor ; From Building Middle Floor -> To Building Middle Floor ; To Building Middle Floor -> To Building To Floor。

具體到策略，有靜態分配和動態分配兩種。靜態分配即請求從輸入執行緒獲得時就已經劃分好；動態分配即每次規劃一段路，規划下一段時要重新計算。

從可擴展性、和性能方面看，動態分配優於靜態分配，但綜合實現難度、優化程度以及魯棒性，我最終選擇較為容易實現的靜態分配方法。

3.3 協作圖

如上圖示為本次作業協作圖。

可以注意到，本次作業和第六次作業相比，設計和迭代是線性的，沒有改變架構和思路，這體現了我們架構較為優越的可擴展性和魯棒性。

我們主要擴展了分段請求在沒有真正完成時要再次加入WaitTable重新等待電梯運送。

3.4 調度分析

本次作業中沿用了第六次作業的縱向與橫向LOOK以及自由競爭演算法，整體思路沒有變化。

值得一提的是，對於橫向電梯，其在計算候乘表中請求時需要先額外考慮是否起點和終點均可達，若不滿足，則忽視該請求。

3.5 bug分析

自己bug

本次作業在中測、強測和互測中沒有出現bug。最終得分為93.7454，可以看到性能分不高，我認為這是樸素調度的劣勢。儘管得分不高，但是本次作業遵循了魯棒性和可擴展性的要求，這為後續迭代開發和維護帶來了便利。

但是在中測的前幾次提交以及本地評測姬隨機測試中出現了一些bug，以下分別介紹：

CTLE

前置背景：setEnd()是輸入執行緒結束時給所有WaitTable()設置end布爾值為真的方法；isEnd()是WaitTable提供的查詢end布爾值是否為真的方法。

在本次作業中，出現了較為嚴重的CTLEbug。具體而言，是多部電梯的判斷wait的條件中的isEnd()等方法中有notifyAll()，這意味著如果目前有兩台電梯，但是沒有請求，第一部電梯判斷條件滿足進入wait，但是其判斷過程中喚醒了正在wait的第二部電梯，這樣彼此喚醒最終導致CTLE。

解決辦法：只設置和保留必要的notifyAll()。

究其本源，我們在前兩次作業的setEnd()方法中設置notifyAll()是為了喚醒並結束候乘表空、電梯空且電梯wait的執行緒；isEnd()方法是為了保證電梯在運行的循環節開頭每次可以判斷是否輸入已經結束，如果輸入結束、候乘表空且電梯內人員運送完畢，即可結束執行緒。

因此，我們發現，其實isEnd()方法並不需要notifyAll()，經過這樣的分析論證，我們刪去了許多贅余的notifyAll()，最終強測所有數據點的CPU時間均在2.5s以下。

執行緒結束

在本次作業中，執行緒結束是一個易出鍋的地方：儘管輸入結束、當前候乘表空、當前電梯空，但這並不意味可以結束該電梯執行緒，因為可能其他電梯會將未處理完的請求重新置入本候乘表。

解決辦法：設置Counter類，作為單例模式對已輸入請求和完全處理結束請求計數，取代輸入執行緒結束的setEnd()方法和訊號。

別人bug

本次作業共成功hack9次，分別是兩位同學的bug。評測方法主要是評測機隨機測試。

RTLE

和第六次作業類似的bug，面對較為有壓力的數據會超時。

另外有一位同學的bug最終沒有能夠復現，他實現了模擬電梯運行過程，自行計算時間來縮短IO的影響，但是會在某些情況產生開關門時間不足等情況，不過課程組評測姬沒有復現也就無所謂了。

Part 4 多執行緒心得體會

多執行緒基本原理

本單元中，最重要的收穫是邁出了多執行緒從0到1的這一步。在本單元學習之前，我僅僅從概念上對多執行緒有一些樸素的認識，但經過本單元的理論課、實驗課研討課以及作業的短平快訓練，我已經能夠初步認識、設計和實現簡單的多執行緒邏輯。

多執行緒debug

多執行緒會有一些單執行緒不會出現的問題，比如輪詢、死鎖等，我在作業中也出現過輪詢等問題，在老師、助教和同學們的無私幫助下一步一步解決了在這些問題並有所長進。

多執行緒思維

本單元的電梯問題是一個經典的多執行緒問題，並且其沒有最有調度的特點讓我們能夠更好地離開固有的單純計算和查找最優解的思路，我們在真實工程需求中可能往往只需要一個局部最優解和一個「看起來性能達標」的策略即可以不差的性能滿足設計要求。而在這之上，我們更多地需要考慮架構和設計層面的問題，不能為了性能上的「蠅頭小利」開架構的倒車，放棄了對可迭代性、可維護性和魯棒性的要求。

當然，以上只是個人淺見，事實上演算法等領域依然有非常值得探索和研究的課題，不過對於工程來說，或許有時需要做一些取捨。

執行緒安全封裝

本單元作業中有一個有趣的點：課程組提供的輸出類是不安全的。從這個角度我窺得大型工程開發的一角：絕大多數時候我們不可能從頭開發或者直接重構一個已經安全運行多年的大型項目，而這時候我們會面臨在這基礎上迭代開發的需求。SOLID原則告訴我們，對於已經久經考驗、安全運行的程式碼最好不要做任何改動，而一些祖傳的程式碼或許並不支援多執行緒，因此我們需要將其封裝為執行緒安全的。

這一部分榮文戈老師在理論課上曾有介紹，即，將不安全的部分Wrapper一下，就變得安全了。而在課下作業中，通過請教林星涵助教，我具體明白了榮老師上課所說的Wrapper的含義，相關內容匯總為一篇帖子發在討論區中並得到加精，這也讓我非常開心。

Part 5 Tricks

在本單元作業實現中，有一些~~不怎麼高級的~~小技巧~~但很有用~~，在這裡記錄和分享。

數據投喂包使用批處理代替手動輸入cmd命令

使用數據投喂包測試時每次在命令行輸入datainput_student_win64.exe | java -jar code.jar較為繁瑣，在Windows中可以通過寫bat文件後每次雙擊來代替重複輸入命令的操作。

`run.bat`

datainput_student_win64.exe | java -jar code.jar
pause

直覺上比較類似sh腳本文件。第二行pause的作用是運行完之後不退出命令行介面。

用記事本等編輯器寫好上述文件後，雙擊run.bat即可運行。

腳本最後一行若再加上cmd \k能讓命令行介面可以繼續使用。

隨機數據評測機

在多執行緒單元，隨機數據評測機依舊發揮穩定，雖然不太能構造出極端樣例卡RTLE等，但是對於廣域壓力測試可靠性效果顯著，這也幫助我在第六、七次作業成功hack了多位同學。

plantUML繪圖

在本次作業中需要繪製協作圖，processOn和starUML固然是很好的選擇，但是plantUML為我們提供了利用程式碼生成雖然不那麼個性化和精細化但是很達標的快速繪製協作圖的方法，可以參考這兩篇文章PlantUML畫圖軟體簡介和PlantUML簡述。

Part 6 回顧與展望

第二單元以實時交互電梯問題為載體，通過短平快的三次迭代作業讓曾是多執行緒小白的我快速上手多執行緒，完成從0到1的改變，在此再次感嘆課程組設計的精妙並表達由衷的感謝。

本單元作業較往年主要新增了橫向電梯的需求，儘管乍一看來非常嚇人，但只要多思考多討論，便也不是不可跨越的難關。

不同於第一單元，本單元中我始終沒有重構。儘管重構是改善程式碼品質的重要方法，但是基於已經成熟的，經過考驗的架構迭代開發顯然可以避免相當多無謂的bug，這也是一種取捨和平衡。

儘管在第一單元的展望中我希望不要拖ddl，但是第七次作業還是直到中測截止前2h才最終定稿，依舊非常驚心動魄，希望未來可以儘可能調度好個人時間和安排，盡量避免這種情況。

在本單元作業中，老師、助教和同學們給予了我非常大的幫助，可以說沒有大家的幫助，我不可能完成這一單元的任務，再一次向大家表示由衷的感謝。另外，我也更深層地體會到了合作、討論和有效溝通的重要性。在一年級時，我很少會和大家討論和分析程式碼相關任務，一般單打獨鬥就走下來了，但是二年級的計組和OOOS讓我更深一步體會合作的重要性，希望在未來可以繼續和大家一起討論，一起進步。

Tags: BUAA-OO Java Programming