第二單元面向對象作業——性感電梯線上吃人

Part 1：單部可捎帶電梯

多線程設計策略

本次電梯僅僅只有一部運行，因此，在多線程的設計中難度不大，並且，只需採用一對一的生產者-消費者模型即可解決問題。整體的設計大致為：輸入線程作為生產者不斷接受外部請求並投入托盤容器中；調度器線程起到了托盤容器的作用，併在電梯運行中輔助實現可捎帶功能；電梯線程為消費者，接受乘客的請求，並不斷計算目標地點和進行自身移動的處理。

在實現中，為了使電梯線程能夠正確結束，在輸入線程結束前夕，要對電梯線程發送狀態信息，在電梯無任何需要處理的工作後，若檢測到輸入線程已結束運行，則結束自身生命，隨之，調度器這個守護線程也一併結束。

三個線程的主要共用資源為請求等待隊列的一個LinkedList容器，簡單的對他上鎖，即可保證基本的線程安全。而輸入和電梯之間的一個信號傳遞，也是依靠共用資源進行的，這裡需要註意的是：

while (persons.isEmpty() && queue.isEmpty()) {
    if (queue.getNoMoreReq()) { return; }
    synchronized (queue) {
        try {
            queue.wait();
        } catch (InterruptedException e) { e.printStackTrace(); }
    }
}

在電梯結束的判斷和睡眠的執行中，可能會被打斷，在這個時刻中，輸入線程剛好完成了結束標誌的設定，並再次喚醒“睡眠中的電梯”，結束自身運行，此時，控制權返回給電梯，電梯繼續執行，進入睡眠，於是，線程進入永久的睡眠，無人再喚醒他了。為了避免這種情況的發生，最好對上述代碼用一個同步塊套起來。

演算法：對於單部電梯來說，我認為如果容量沒有限制，那麼總是去接送或者去滿足最近的請求，會有著非常好的效果。首先，這種方法可以避免電梯去接一個偏遠的請求而浪費時間，倒不如解決完鄰近密集請求，在空閑時再處理較遠的請求。同時，這樣也能避免新來的請求可能在你的反方向，而去向卻和你的目的大致相同的情況導致走太長回頭路的問題。

可擴展的架構設計

• SRP（單一責任原則）

  Main類只負責初始化和線程的啟動，Input負責對外部請求的獲取、分析，並放入托盤，Output專門為一些封裝的輸出函數，Scheduler負責乘客的分配，Elevator類只用決定去向和自己的移動。整體來說，較好的滿足了SRP原則。

• OCP（開放封閉原則）

  由於首次作業的架構簡單，並且個人認為後面作業的架構設計中，PersonRequest並沒有變化，並且不打算實現多級調度器，因此，個人認為OCP原則暫可無需滿足，也就不預留任何藉口或抽象類。

• LSP（里氏替換原則）

  同上，第一次中沒有派生類相關結構。

• ISP（介面隔離原則）

  同上，大部分類都設計為單例模式，電梯在設計中唯一被他人所調用的部分是對電梯門狀態的判斷，ISP原則暫時無需滿足。在需求不確定的情況下，設計介面是一件困難的事情。

• DIP（依賴倒置原則）

  在我的實現中，三個主要的工作類屬於並行的狀態。

靜態代碼分析

• 代碼規模

  Type Name	Method Name	LOC	CC	PC
  Main	main	10	1	1
  Elevator	Elevator	9	1	1
  Elevator	run	23	5	0
  Elevator	up	10	1	0
  Elevator	down	10	1	0
  Elevator	open	14	1	0
  Elevator	close	10	1	0
  Elevator	move	10	3	0
  Elevator	reTarget	25	6	0
  Elevator	getFloor	3	1	0
  Elevator	getDoor	3	1	0
  Elevator	addPerson	4	1	1
  Elevator	removePerson	7	2	0
  Scheduler	Scheduler	4	1	2
  Scheduler	run	18	3	0
  RequestQueue	pull	11	2	0
  RequestQueue	peek	11	2	0
  RequestQueue	offer	4	1	1
  RequestQueue	getNoMoreReq	3	1	0
  RequestQueue	isEmpty	3	1	0
  RequestQueue	setNoMoreReq	3	1	1
  RequestQueue	getRequestAt	13	3	1
  RequestQueue	containRequestAt	8	3	1
  RequestQueue	getRequestTo	13	3	1
  RequestQueue	containRequestTo	8	3	1
  RequestQueue	findMinFrom	16	4	1
  RequestQueue	findMinTo	16	4	1
  Input	Input	4	1	1
  Input	run	23	3	0

• 複雜度分析

  Type Name	NOF	NOM	LOC	NC	DIT	LCOM	FANIN	FANOUT	OCavg
  Main	0	1	12	0	0	-1	0	4	1
  Elevator	8	12	138	0	0	0	2	2	2
  Scheduler	2	2	26	0	0	0	1	2	2
  RequestQueue	2	12	113	0	0	0.16667	4	0	2.3333
  Input	1	2	30	0	0	0	1	1	2
  Output	0	6	20	0	0	-1	1	0	1

• UML類圖

  

  本次設計了Input、Output、Elevator、Scheduler以及RequestQueue這幾個類，首先，保證了Input、Scheduler和Elevator三個線程類具有較低的耦合性，這從類圖和上述度量分析中都能看出。其次，設計了Output類專門用來封裝輸出函數，可以很好地進行代碼復用。同時，構造了RequestQueue，對容器進行線程安全的數據管理，因此在設計中會稍微複雜一些。總體上看，整個設計的耦合性較低，分工明確，在未來可能具有的新的功能中，也不是難以擴展的。

• UML協作圖

  

  main線程主要用來初始化和啟動線程，這在設計部分已經闡述過。主要的線程協作部分在於輸入、調度和電梯線程。具體內容如上。

bug分析

• 自己程式中的bug

  本次作業中在公測和強測中都沒有bug出現，並且除了策略部分提到的一個關於線程安全的點，在代碼編寫中也十分順利，但是在幫助同學查找bug時，發現了一種有問題的線程同步方式，我們在讀取輸入的請求時，如果現階段沒有輸入，則會阻塞住等待下一個輸入的到來，而有的同學將這條由外部包所實現的阻塞語句包含在了內部代碼的臨界區中，導致其他線程一直無法獲得鎖，直到讀取到EOF退出臨界區，其他程式才得以複活，這是極為不可取的。

• 互測中的bug

  此次互測極為安靜，只有1、2個hack點。多線程的hack不能像以前的程式一樣做特殊樣例了，可能在不斷的隨機數據中，才會引發程式的不安全的線程問題。我利用python生成隨機數據，並解析時間點定時發送給待測程式，以達到模擬評測機的效果，然而，運氣不好，沒有hack到別人。

  在互測結束後，看到別的同學hack到的數據，結合他們的代碼可以看出，主要問題不是線程安全帶來的，而是調度演算法出了bug，這是此次作業的主要bug。

Part 2：多部可捎帶電梯

多線程設計策略

本次作業僅僅改變了電梯的數量，在請求到來前會提供給程式需要啟動的電梯數量。本次線程安全主要在於多個電梯對共用資源的競爭問題，然而，我的設計中，即使直接生成並啟動多個電梯，也能夠保證線程安全。

演算法：單電梯調度依舊為前一次作業的處理最近請求，對多個電梯的乘客調度，我選擇了爭搶式的實現方式。在最初實現時，我計劃利用Person類構造一種被標記但是未進入電梯的狀態，來調度乘客進入電梯，然而，由於電梯有著一定的容量限制，不能很好地將乘客標簽化的分配，同時，由於我的單部電梯調度演算法的原因，電梯的走向不如look演算法那樣穩定，因此這種設計帶來了巨大的麻煩。於是我想到給每部電梯單獨建立等待隊列的方式，讓每個隊列只與特定的那個電梯可見，簡化了標簽化乘客帶來的極其複雜的條件判斷，但是，結果確實殘酷的，這麼搞根本沒有讓電梯自己去爭搶乘客的方法快，我想原因大致是強測中的數據隨機性很高，這樣爭搶讓電梯可以較為平均的分佈在每一層，使得局部請求能夠快速處理，以此提高了性能。

可擴展的架構設計

• SRP（單一責任原則）

  此次程式框架與第一次基本相同，僅僅是將原來的容器單獨拆分出來，設計獨立的等待隊列和電梯艙體，較好的完成了SRP原則。

• OCP（開放封閉原則）

  這次電梯僅僅要求是增加數量，與第一次類似，沒有涉及擴展性（對下次作業的要求已經瞭解了，打算用多參數的constructor和工廠模式實現不同電梯的擴展）。

• LSP（里氏替換原則）

  同上，沒有繼承或實現的類。

• ISP（介面隔離原則）

  同上。

• DIP（依賴倒置原則）

  在我的實現中，三個主要的工作類屬於並行的狀態。

靜態代碼分析

• 代碼規模

  Type Name	Method Name	LOC	CC	PC
  Main	main	15	2	1
  Elevator	Elevator	9	1	1
  Elevator	run	23	5	0
  Scheduler	Scheduler	4	1	2
  Scheduler	run	19	3	0
  Scheduler	containRequest	11	4	0
  RequestQueue	getRequestAt	11	3	1
  RequestQueue	containRequestAt	8	3	1
  RequestQueue	findMinFrom	16	4	1
  Person	Person	6	1	4
  Person	getPersonId	3	1	0
  Person	getFromFloor	3	1	0
  Person	getToFloor	3	1	0
  Person	getStatus	3	1	0
  Person	setStatus	3	1	1
  PassengerList	PassengerList	3	1	1
  PassengerList	getRequestTo	11	3	1
  PassengerList	containRequestTo	8	3	1
  PassengerList	findMinTo	16	4	1
  Input	Input	4	1	1
  Input	run	31	5	0
  Input	getElevatorNumber	3	1	0

• 複雜度分析

  Type Name	NOF	NOM	LOC	NC	DIT	LCOM	FANIN	FANOUT
  Main	0	1	17	0	0	-1	0	0
  Elevator	10	13	148	0	0	0	0	0
  Scheduler	2	3	38	0	0	0	0	0
  RequestQueue	0	3	37	0	0	-1	0	0
  Person	7	6	30	0	0	0	0	0
  PassengerList	0	4	40	0	0	-1	0	0
  Input	3	3	43	0	0	0	0	0
  Output	2	5	19	0	0	0	0	0

• UML類圖

  

  其他類的職責和依賴關係基本與第一次相同，唯一的改動是將原來的托盤容器拆分出來，讓他只去完成作為托盤的使命，而PassengerList則去完成管理電梯內乘客的使命，並且增加的Person類，更好地管理和封裝請求。沒有一個介面確實不是很專業，但個人認為，沒有一個龐大的任務需求作為前提，強硬的加入介面去實現，有種臃腫且殺雞用牛刀的感覺。

• UML協作圖

  

  本次線程間的協作與第一次類似。

bug分析

• 自己程式中的bug

  本次公測和強測中依舊沒有bug出現，性能分也不差。在實現此次任務中，如策略一節所述，我有實現過其他兩種方法，然而可以明顯感覺到，給乘客制定標簽，會讓多個線程的共用資源異常的多，對於資源鎖的處理不僅麻煩，而且漏洞百出，另外，那種實現破壞了整個架構，遂放棄。單獨為每個電梯提供獨立等待隊列的方法，讓線程間的共用資源保持在了第一次的水準上，大大簡化了鎖的設置，然而，在性能上的劣勢讓我放棄了他，但這種設計是第三次完成的基礎。

• 互測中的bug

  此次互測房間內依舊很安靜，僅僅只有4刀之少，大部分同學的問題都是調度中失去了方嚮導致不斷地死迴圈。有一位同學是由於線程的過早結束，導致乘客沒有結束運送，獲得了WA。本次依舊使用暴力的自動化評測，沒有刀到人，由於沒有精力深入代碼的原因，放過了這些有問題的同學。

Part 3：多部多類別動態增設可轉運電梯

多線程設計策略

本次電梯增加了允許停留的層數，改變了不同類型電梯的容量、速度等參數，我構造了一個工廠類完成了對不同類型電梯的構造。由於有些電梯無法接送乘客所在地或目的地的，因此利用第二次作業實現的電梯分離式請求隊列，將每次到來的請求進行分析並送入合適的電梯等待隊列中，而每個單獨的隊列依舊採用最短請求演算法（同前兩次）。在選擇合適的電梯時，我採用優先選擇能夠直達的電梯，但由於for迴圈的固定性，這樣可能導致多個同種電梯的等待隊列過於擁擠，因此使用了Collections.shuffle()對電梯容器進行打亂，這種隨機打亂的方式利用隨機性很好的保證了乘客請求進入電梯等待隊列的平均分佈。

本次電梯線程間的共用資源增加了電梯容器這一部分，由於電梯增加指令的引入，管理所有電梯的容器在不斷增加（修改），而我們為了調度乘客請求，也需要不斷遍歷這個容器，然而，這個容器的使用不需要要保證讀寫前後的次序問題，只需要保證對他的讀寫是一個原子性操作即可，因此我使用了CopyOnWriteArrayList來保證操作的原子性，同時，這個容器在使用for迴圈時可以刪除容器內元素而不會產生異常，讓某些操作變得更加簡單。

可擴展的架構設計

• SRP（單一責任原則）

  這次程式的各個類基本與第二次沒有太大差異，主要是ElevFactory的增加，來進行電梯的初始化，並且修改了Scheduler，讓其主要職責為將InputQueue中的請求分配給合適的電梯等待隊列。較好的滿足了SRP原則。

• OCP（開放封閉原則）

  電梯種類的加入，讓每個電梯都有自己不同的屬性，這個辭彙告訴我們，實際上電梯的具體功能沒有任何改變，變化的只有移動時間、可達樓層、載客容量這些電梯具有的屬性，我們的方法以及其內部的代碼不需要做任何的改變，因此，這次擴展我直接利用構造器修改具體field，不進行類的繼承。雖然確實沒有滿足OCP原則，但OCP原則的適用性也是需要考慮的。

• LSP（里氏替換原則）

  理由同上，但是，從第一次作業以來，我都保證了在調度不斷替換的情況下，電梯不需要做任何改變，就可以進行適配，也許這是一種LSP更廣泛的抽象（大噓。

• ISP（介面隔離原則）

  同上，沒有介面啊。

• DIP（依賴倒置原則）

  電梯章節各個類的依賴關係其實十分特殊，在我的實現中，沒有一種通用的類去做介面讓高層次的類依賴。例如，托盤這個類和電梯內部乘客的容器這個類，對他們的調用中，主要在意的分別是乘客的所在地、目的地，這是兩種完全不同的需求，因此，我沒有做一個介面。

靜態代碼分析

• 代碼規模

  Type Name	Method Name	LOC	CC	PC
  ElevFactory	createElevator	19	4	3
  InputQueue	InputQueue	2	1	0
  InputQueue	run	27	5	0
  InputQueue	getInstance	3	1	0
  InputQueue	personInit	11	3	1
  InputQueue	putQueue	4	1	1
  InputQueue	takeQueue	11	2	0
  Main	main	9	1	1
  Elevator	Elevator	14	1	6
  Elevator	run	23	5	0
  Scheduler	Scheduler	2	1	0
  Scheduler	run	22	4	0
  Scheduler	getInstance	3	1	0
  Scheduler	isOff	3	1	0
  Scheduler	setOff	3	1	1
  Scheduler	tellAllElevatorsOff	5	2	0
  Scheduler	allElevatorsAreEmpty	8	3	0
  Scheduler	schedule	46	10	1
  RequestQueue	getRequestAt	13	3	1
  RequestQueue	containRequestAt	8	3	1
  RequestQueue	findMinFrom	16	4	1
  PassengerList	PassengerList	4	1	2
  PassengerList	offer	12	3	1
  PassengerList	getRequestTo	13	4	1
  PassengerList	containRequestTo	8	3	1
  PassengerList	findMinTo	16	4	1
  PassengerList	isAbleToBerth	3	1	1

• 複雜度分析

  Type Name	NOF	NOM	LOC	NC	DIT	LCOM	FANIN	FANOUT	OCavg
  ElevFactory	3	1	24	0	0	0	2	2	5
  InputQueue	3	6	63	0	0	0.67	4	4	2.16667
  Main	0	1	11	0	0	-1	0	3	1
  Elevator	13	17	191	0	0	0	2	5	1.94118
  Scheduler	4	8	98	0	0	0.375	3	5	2.875
  RequestQueue	0	3	39	0	0	-1	3	1	3.33333
  Person	9	10	46	0	0	0	5	0	1
  PassengerList	1	6	59	0	0	0.67	1	2	2.66667
  Output	1	5	18	0	0	0	2	0	1

• UML類圖

  

  對於類的構造，基本上其職責與依賴與第二次相同，主要增設了ElevFactory工廠類來根據電梯類型初始化和啟動電梯線程，整個結構的設置，依賴關係的處理，以及各個類的解耦，都做得不差，唯一的缺憾可能是沒有一個介面在我的實現之中，對於介面，我還是保留個人觀點，但是在後續可能出現的需求中，例如乘客的不同行為、調度器可能實現多級調度，以及電梯類型進一步的多樣化（不能只改變參數了，實現起來意義不大），確實需要介面來保證設計的美觀和合理。

• UML協作圖

  

  協作方式基本不變，改變了傳輸停止信號的方式。

bug分析

• 自己程式中的bug

  本次強測中沒有bug，但是在互測中被抓住了一個遺留了三次作業的bug，在調度中將對乘客所在地的獲取，錯寫成了目的地的獲取，在極為特殊的例子中，產生了死迴圈。線程安全部分沒有問題出現，但其實，只要清晰地明白各個線程的共用資源情況，以及運行時的順序依賴，就可以構造安全且無死鎖的併發代碼，有時候，畫一畫寫一寫，真的有助於自己的理解。

• 互測中的bug

  這次互測hack別的同學的策略，除了兩次都沒有意義的自動化測試工具，我決定在他們的代碼中查找線程安全的問題，於是，好巧不巧，發現了一位認為電梯的名字只有“X1”、“X2”、“X3”的同學，於是我構造了一個會導致TLE的數據，即47個從-3到20的乘客請求，並且加入了X10、X11、X12三個A類電梯，萬萬沒想到，他直接RunTimeError了，但又抓出兩位似乎不能很好處理一次性大量相同請求的調度的同學，他們各個都TLE了。個人認為，大家的問題大多都在於調度演算法的bug，線程安全做的確實不差。

Part 4：收穫與感想

這個寒假中，在隨意學習Java的過程中，小小的做了一個IM即時通訊聊天軟體，可以滿足在互聯網上的一對一的單人聊天，並且保存離線聊天記錄，支持上線好友提醒，以及消息通知等，這個軟體是我對多線程的第一次嘗試，對多個線程的資源競爭和死鎖等知識還不怎麼瞭解，本來以為多線程啊也不過如此，在這三次電梯作業的迭代開發中，我才真正體悟到併發程式真正的困難所在，我們在這個單元的學習中，主要需要解決的困難，就是對共用資源的同步，以及線程空閑時的等待和安排任務後的喚醒，多線程的理解不難，個人認為，難度在於你有時不能考慮到共用資源附近可能出現的所有線程競爭的情況，少考慮一點，程式就有可能崩掉。

其次，接著上面的話，我覺得課程的安排似乎缺少了一點關於併發程式中過大的同步區域導致的性能問題，其實，一步步分析代碼，儘可能減小臨界區的大小，或者使用樂觀鎖、高級的併發容器等Java自帶的實現功能，來接近更快速、更高效的併發執行，這也是我們日後工作中可能遇到的問題，高併發、高可用、高性能，將會是未來程式開發的難點之一。

最後，回顧三次作業，收穫了不低的強測分數，也更加瞭解了多線程的韻味兒，唯一略微遺憾的是，在這三次開發中，沒有體會到明顯的設計感，想要做一個要介面有介面，要派生類有派生類、層次分明、結構清晰的框架，但由於多線程的安全問題需要仔細考慮、又耗費著大量時間思考調度的安排，當然個人認為有一點點原因在於題目需求的電梯實際上不需要如此複雜的設計吧。《Java編程思想》這本大黑書隨著課程推進少了一章又一章，希望最後的我有一個嶄新的改變吧。