前言 所謂軟體過程模型就是一種開發策略，這種策略針對軟體工程的各個階段提供了一套範形，使工程的進展達到預期的目的。對一個軟體的開發無論其大小，我們都需要選擇一個合適的軟體過程模型，這種選擇基於項目和應用的性質、採用的方法、需要的控制，以及要交付的產品的特點。一個錯誤模型的選擇，將迷失我們的開發方向。 ...
由於本人廢話比較多，所以提供一個目錄
BUAA_OO_U1_Summary一 / 架構設計1.0> 題目解析1.1> HW51.1.1> 做法分析1.1.2> 獲取請求1.1.3> 請求分配1.1.4> 電梯調度1.1.5> 托盤（緩衝區）1.1.6> 輸出1.1.7> 類圖1.2> HW61.2.1> 迭代開發1.2.2> 請求分配 1.3.3> 橫向電梯調度1.3.4> 類圖1.3> HW71.3.1> 迭代開發1.3.2> 請求拆解1.3.3> 請求分配1.3.4> 電梯調度1.3.5> 如何結束1.3.6> 架構圖1.4> 順序圖二 / 捉蟲大戰2.1> 自測bug2.2> 互測bug三 / 度量分析3.1> 代碼長度3.2> 複雜度分析四 / 心得體會
一 / 架構設計
1.0> 題目解析
-
有人要坐電梯
-
電梯要儘量快的把他們送到目的地
-
電梯有豎向的，也有環形的，環形電梯有可到達樓座的限制
1.1> HW5
1.1.1> 做法分析
我們現在有電梯和很多在一定時間和一定地點出現的有一定需求的乘客。需要做的就是在電梯不超載的前提下儘量快速地完成所有人的請求。
而根據訓練所給出的兩種設計模式的提示，本人首先利用了大量時間學習生產-消費者模式，並嘗試思考出如何進行第五次作業的編碼。這個過程歷時過長，導致最後留給調試的時間不多，只是將將通過了中弱測，併在強測迎來了慘死，當然，這是後話了。
為了套用這個生產-消費者模式，首先需要解決的問題是誰是生產者，誰又是消費者，他們在生產什麼又在消費什麼。
一開始本人以為生產消費針對電梯上面的空位，人下電梯則空位是被生產，人上電梯則空位被消費。但是轉念一想，發現了問題。如果人乘客電梯，那麼乘客是消費者，電梯是生產者。但如果乘客下電梯了，電梯是消費者，乘客是生產者，角色並不固定，並不能利用此設計模式進行編碼。很顯然，對於這個被生產消費的物品，本人選錯了。
那我們繼續來觀察整個電梯運行事件中出現又消失了的事件——乘客的需求。在這樣的條件下，生產者固定，為到達電梯口想要從這裡出發去別的樓層的乘客；消費者固定，為運輸這個乘客到達目的地，滿足其需求的電梯。所以，我們的代碼需要做的事情就是在乘客輸入請求後，把請求分配電梯，讓電梯處理請求。這三件事，即整個代碼中要用到的三個線程，串其這三條線程，貫穿於整個程式之中的，便是裝有請求的托盤，而用於按時間戳遞增的順序輸出信息的，便是線程安全輸出類。
1.1.2> 獲取請求
讀入線程。我們只需要把乘客的請求讀入，放上托盤。
這個線程設計到的難點是，如何在輸入停止後，通知另外兩個線程沒有新請求了，大家處理完手頭的任務就可以下班跑路了一事，即線程結束的問題。這裡的方法在訓練的代碼中有詳細的指導，於是本人便毫不猶豫地將其搬了過來，大概思路為：如果當前讀入表示沒有新的請求，則將所有的電梯待處理隊列的狀態設為結束態。當電梯的處理隊列為空且狀態為結束態時，直接退出線程。
1.1.3> 請求分配
分配器線程。我們需要把乘客的請求分類，分發給不同的電梯處理。
在此次作業中，有5棟獨立的樓，裡面分別由一個電梯，於是這個分配器需要做的事情就是把每個請求扔到對應的樓座里的電梯那裡。在當前這個每個電梯互相獨立互不幹擾的前提下，此線程的實現並沒有什麼難點和需要註意的地方。
1.1.4> 電梯調度
電梯線程。我們需要讓電梯跑起來，去接每個乘客從自己的起始地點開始上電梯，到達自己的目的地，出電梯。
這裡是本次作業中最難最難最難的部分，本人幾乎所有的時間都利用在思考如何編寫這個電梯的調度上了。畢竟，我可以讓我的電梯每次指處理一個請求，然後享受RTLE的洗禮，並繼續硬著頭皮思考如何調度電梯。在當時較為絕望的境況下，本人並不能夠理解ALS的調度方法中的主請求是如何被設置併在代碼中實現這一點，也未能相處如何編寫在大量往屆學長學姐的博客中撲騰到的LOOK演算法，但本人並沒有放棄，而是利用了三天時間仔細的和自己講述、辯論，並編寫、調試。在此非常樂意記錄一下自己的分析過程。
抽象來看，所有的調度不過是狀態的轉換。從乘客的請求方面，有未進電梯（請求等待）、進入電梯（處理請求中）和出電梯（完成請求）三個狀態；從電梯的運行方面，有原地等待（等待請求），接人（獲得請求），運行（處理請求），開/關門這四個狀態。對這些狀態如何互相轉化進行設計，形成一個狀態機，則電梯就可以完成基本的運作了。
《狀態機》
而調度的關鍵在於接人的順序，這也是所有演算法著重處理的地方。
本人的想法很貪心，但是是沒有被證明過的那種（應該可以證明有更優解但我並沒有仔細思考），可能更加貼近LOOK一些：
-
電梯在等待狀態下：
-
選擇出發樓層距離1層和10層位置最近的請求（為了一趟多接一些人）
-
滿足上條的情況下，選擇出發樓層距離電梯當前位置最近的請求
-
滿足上條的情況下，選擇目的樓層距出發樓層最近的請求（為了一趟多接一些人）
-
如果沒有這樣的請求，則繼續等待
-
-
電梯在上行狀態下：
-
選擇移動方向為上行的請求
-
滿足上條的情況下，選擇出發樓層不低於當前電梯所在樓層的請求
-
滿足上條的情況下，選擇目的樓層距出發樓層最近的請求
-
如果沒有這樣的請求，則繼續上行，完成當前的請求
-
-
電梯在下行的狀態下：
-
選擇移動方向為下行的請求
-
滿足上條的情況下，選擇出發樓層不高於當前電梯
-
滿足上條的情況下，選擇目的樓層距出發樓層最近的請求
-
如果沒有這樣的請求，則繼續下行，完成當前的請求
-
但是，必須承認的一點是，其性能分比較糟糕。
但是，只有這樣一個方案，對於最終形成代碼依舊有一定困難：比如，代碼在什麼時候進行這個狀態的檢測並去詢問有沒有可以捎帶的人呢？所以，更詳細來說：
-
電梯初始為等待狀態
-
按規則獲取請求
-
得到請求
-
到達請求的起始層
-
若電梯未滿，按規則獲取新的請求
-
得到新的請求
-
向著當前新的請求的起始層移動
-
若電梯未滿，按規則獲取新的請求
-
每次移動一層
-
到達樓層的時候判斷是否有請求要出電梯 / 進電梯
-
後出後進，先下後上，弘揚中華民族的傳統美德（為了保證不超人數）
-
-
沒有新的請求則直接處理當前請求
-
-
沿當前方向繼續按層運行，到電梯中所有人都出去為止
-
電梯狀態再次設為等待
上面的流程不斷重覆，直到獲得了等待隊列為空且沒有新的請求了的信號，則退出線程，結束電梯的調度任務。
1.1.5> 托盤（緩衝區）
在生產-消費者模式中，形象化描述起來就是托盤；換成操作系統就可以稱作臨界區，在本人的代碼中，被稱為緩衝區。
這個部分的難點在於需要避免數據競爭，保證線程安全，因為緩衝區涉及到乘客請求的放入和分配器對請求的拿取。所以對於所有在緩衝區內的方法，都需要加鎖，防止多個線程交錯調用產生各種各樣的不安全行為。在這裡，由於本人沒有使用一些保證了部分存取方法安全的容器類型，而是直接使用了ArrayList，所以對於所有方法都添加了sychronized關鍵字。
同時，在本人的托盤中存在一個最大容量的屬性。當托盤中存儲的請求到達了這一最大值，會讓當前放入托盤的動作進入等待狀態，待請求被取走一些再繼續放入。其目的是為了催促消費者即電梯不要堆積任務，儘快完成，理論上聽起來有些作用，但在實際測試中對於提升效率的用處並不大。
1.1.6> 輸出
保證時間戳遞增的輸出方法。
一開始本人並沒有單獨的輸出類。但是在第五次強測結果出來並獲得了時間戳不遞增的結果之後，本人悔改了。時間戳不遞增的問題在本地從未出現過，但是多線程同時輸出，難免會有不安全的問題，所以確實需要一個為了保證線程安全的輸出方法。解決方法很簡單，只需要對這個被多個線程調用的輸出方法加上sychronized修飾即可。
1.1.7> 類圖
相對於第一單元的作業，這個架構相對更加清晰一些。
可以看出，代碼由主類、讀入線程（生產者）、調度器、緩衝區、消費者、安全輸出類構成。
Main：負責創建緩衝區，併在此基礎上創建讀入、調度器、消費者線程。 Request：包裝一個請求。後來在互測的時候才意識到，可以直接繼承官方包裡面的類，使用其中的方法，不用自己再單獨寫一個。 Allocator：分配器，按樓座為各個消費者分配緩衝區內的請求。 MyBuffer：緩衝區，內部設有put和get方法，用於存放所有請求，同時也可以作為一個用來存放請求的容器被使用。 Producer：生產者，即讀入線程，用於讀取輸入的請求並put進緩衝區；同時在讀入結束時發出結束線程的信號。 Consumer：消費者，即電梯，內部設置有電梯的運行方式即各個電梯狀態下應該有的行為。 Output：線程安全輸出類。
1.2> HW6
1.2.1> 迭代開發
在這次作業中，新增了環形電梯。但是即使有了環形電梯，由於題目限制，我們依舊可以認為每個樓座互相獨立，同樣的，每層樓也互相獨立。環形電梯與縱向電梯之間也互相獨立。所以，環形電梯除了可以環形運動以外，和第五次作業並無太大區別。
所以，題目新增的需求要求我們從兩個方面對第五次作業的代碼進行迭代更新：請求的分配和橫向電梯的調度。
1.2.2> 請求分配
首先，對橫向的請求和縱向的請求，這種區分還是很明顯的，此處就不加以贅述了。
這裡的請求分配重在如何把請求分配給同一層 / 同一樓座中的多座電梯中。指導書提供的思路是按餘數進行平均分配。本人一開始採取了隨機分配的方法，但交到評測姬中發現時間都非常慢，於是後來換成了向等待隊列最短的電梯中放入請求。原因主要在於，這樣比較好實現。在第五次作業的時候，本人也暢想過自由競爭的實現方法，但是真正到了需要實現的時候，卻並不能形成一個很清晰的思路（但從互測時的觀察來看，自由競爭確實快了很多）；同樣的，還有提前預估各部電梯處理完手頭的請求需要的時長，根據時長的長短分配請求的做法，也需要較強的程設能力和清晰的思維，對於本人這種周六才解決完RTLE的蒟蒻來說實在是沒有時間思考了。
1.3.3> 橫向電梯調度
其實對於橫向電梯，和縱向電梯並無太大區別，主要需要解決的問題就是怎麼轉圈。
本人的公式推導在六作業中是有誤的，導致電梯可能會選擇更長的一側（如從C到A選擇CDEA的路徑）運行，使得性能分不太好看。後來再次破環成鏈，重新推導了一遍，得到了正確的公式（Q：clockWise；C：counterClockWise）：
((st - nd + 5) % 5 > (nd - st + 5) % 5 ? 'Q' : 'C');
而至於處理請求的順序，和前文提到的縱向電梯別無二致，在此也不再重覆了。
1.3.4> 類圖
Main：負責創建緩衝區，併在此基礎上創建讀入、調度器、消費者線程。 MyRequest：為了不和官方包撞名字，所以改成了MyRequest，直接繼承了官方包提供的PersonRequest，但是增加了一些對於請求運動方向、請求的狀態等屬性的記錄。 Allocator：分配器，按樓座為各個消費者分配緩衝區內的請求。 MyBuffer：緩衝區，內部設有put和get方法，用於存放所有請求，同時也可以作為一個用來存放請求的容器被使用。 Producer：生產者，即讀入線程，用於讀取輸入的請求並put進緩衝區；同時在讀入結束時發出結束線程的信號。 Consumer：消費者，即電梯，內部設置有電梯的開關門和達到樓層的行為。 Lift：縱向電梯，設計單獨的縱向電梯運行方法。 Belt：環形電梯，名字取材於機場里可見的自動人行道電梯或者說傳送帶一類的平面傳輸裝置，設計單獨的環形電梯運行方法。 Output：線程安全輸出類。
1.3> HW7
1.3.1> 迭代開發
本次作業中，為了完成一個請求，乘客可能需要換乘了。並且，環形電梯對可到達的樓座進行了設置。
所以，題目新增的需求依舊要求我們從兩個方面對第六次作業的代碼進行迭代更新：請求的分配和橫向電梯的調度。
但是在分配請求之前，多了一個拆解請求的問題。
1.3.2> 請求拆解
奔著不求性能分只求過的心態，本人直接進行了一個圖論的撰寫。
一開始想用floyd，後來發現一開始設計的時候維度設計錯了又換成了dijkstra，等維度設計對了又懶得換回floyd了。不過數據量較小，所以跑最短路速度還能忍。
本人的做法很暴力也很靜態。首先，是建圖的環節。由於有5個樓座和10個樓層，於是我們將A座1層映射為1，A座2層映射為2，B座一層映射為11，以此類推，公式即為：(building - 'A') * 10 + floor;。對於可以到達的樓層，則根據該電梯的容量和運行速度屬性加權建邊（所以是靜態的，這裡的權重蒟蒻也沒能好好設計，所以可能浪費了很多性能）。然後便是跑最短路的過程，是一個非常普通的dijkstra，但是其中每次進行鬆弛操作的時候都需要記錄路徑，以便獲得最短路徑的具體行走方法，用於最終獲得請求的拆解結果。
請求拆解的結果是，所有分請求必須按順序執行，但保證每個分請求的[起點座 == 終點座] + [起點層 == 終點層] == 1，這樣對於之前的請求分配和調度演算法改動最小（適合比較懶的蒟蒻，不適合喜歡性能分的大佬）。
所以，可以看到以前單個請求的存儲方式不再能滿足這個設計了。本人改用了請求序列來存放一個讀入的請求被拆解的結果，但是每次只處理改隊列的隊首請求，然後依次處理後續請求，每處理完畢則刪除，直至清空整個隊列。
1.3.3> 請求分配
這裡和上一次作業的區別在於，眾多電梯中需要挑出那些個能運送這個請求的電梯，否則就會像本人一樣失去強測的分數。
所以，先特判出能送這個乘客的電梯，然後再選擇等待隊列最短的電梯，放入這個請求。
1.3.4> 電梯調度
由於本人的實現方法，在獲得請求的時候就已經把請求拆解成為可以套用第六次作業的調度方法來處理的請求了，所以第七次作業中的電梯調度沒有做新的修改。
但是這樣的風險非常大，最後得到的性能分也是兩極分化嚴重。
1.3.5> 如何結束
在本次作業中，由於一個請求可能對應一個有多項的請求序列，所以需要更加註意的地方是如何判斷當前的所有請求都被處理完了，以結束當前電梯的線程，同時保證線程結束時沒有人還在等待換乘或還卡在電梯里沒能到達目的地。這裡本人選用了上機中提供的代碼使用的信號量來解決這樣的問題。請求的總數在讀入線程中是可以被記錄並清楚確定的。那麼，每次清空一個請求序列的時候，釋放一個“資源”；需要結束線程的時候，判斷是否有資源可以被獲取，如果有就拿，沒有就等著，直到有請求被處理完畢釋放“資源”，就可以給拿取了。其中判斷次數為請求的總數。
多線程的信號量可以保證，在整個進程結束時，所有的請求都被處理完畢。
1.3.6> 架構圖
這次作業的類又變得更加豐富了起來。
Main：負責創建緩衝區，併在此基礎上創建讀入、調度器、消費者線程。 Unit：包裝一個請求。直接繼承了官方包提供的PersonRequest，但是增加了一些對於請求運動方向、請求的狀態等屬性的記錄。 MyRequest：請求序列，存有一個請求經過最短路處理後得到的所有分請求。 Allocator：分配器，按樓座為各個消費者分配緩衝區內的請求。 MyBuffer：緩衝區，內部設有put和get方法，用於存放所有請求，同時也可以作為一個用來存放請求的容器被使用。 Producer：生產者，即讀入線程，用於讀取輸入的請求並put進緩衝區；同時在讀入結束時發出結束線程的信號。 Consumer：消費者，即電梯，內部設置有電梯的運行方式即各個電梯狀態下應該有的行為。 Consultant：顧問。思考良久都沒能想出一個適合的名字，最後對這個拆解請求的程設法最短路徑運行者付與了顧問一職，深表敬畏。 Output：線程安全輸出類。
1.4> 順序圖
由於三次作業是迭代設計，但是對於線程之間的交互和處理順序從本質上將沒什麼區別，故在此指放一張第七次作業對應代碼的順序圖，以示本人多線程作業的思路。
首先，在讀入一個乘客的請求之後，跑最短路，將請求拆解，放入緩衝區。在讀入一個新增電梯的請求之後，新增一個電梯並運行該線程，同時重新建圖。
第二，分配器從緩衝區拿取請求，將其放入對應電梯的等待序列。
第三，電梯按照其調度策略處理該請求，若該請求仍需換乘，則重新放回緩衝區，繼續處理；否則，完成此任務，釋放資源，信號量+1。期間不斷山城輸出。
第四，若讀取到線程結束，則設置所有等待隊列的狀態為結束態，並回收所有資源。
二 / 捉蟲大戰
本次作業中，本人並未嘗試編寫評測姬，一則是作業難度大導致沒有時間再去大量測試了，二則是沒有研究明白如何使用popen，無法做到通過自己寫的評測姬實時投放請求。這也導致了很嚴重的後果，即本人的代碼被強測和互測hack得千瘡百孔不忍直視。
最最重要的bug來源依舊是沒有仔細閱讀指導書。
2.1> 自測bug
這個部分用來記錄自己出現過的bug。
首先在第五次作業中，本人理解錯了到達一層需要輸出arrive信息這句話的意思，並且沒有詳細閱讀樣例，導致這個蒟蒻設計的電梯只在需要開門出入人的層才輸出了arrive信息，以至於丟失所有性能分，併在互測房中獲得了被hack20/20的好成績。其次，由於本地測試並未出現輸出線程不安全的情況，於是本人沒有意識到封裝線程安全類的必要性，在強測中出現時間戳不遞增的問題。第三，本人的調度設計非常糟糕，榮獲了不少RTLE，在修複的時候也廢了不少心思，最後意識到，當時設計的捎帶處理邏輯每次選取的只是同方向且能捎帶的，是時間最早的而不是距離最近的，於是顯而易見，這樣的調度很熱愛已讓電梯陷入反覆橫跳的境地，浪費時間。在修改完請求處理順序的邏輯之後，便順利的修複了所有的bug。
第六次作業中，本人首先利用了第五次作業bug修複的代碼預覽處，解決了一個由於手抖打錯，把每次處理本層到下一個請求的起始樓層的方法寫成了處理從本層到下一個請求的目的地樓層，從而（調了一天）導致的RTLE問題，在強測中終於取得了一個可堪入眼的成績。其次，嘗試解決了橫向電梯不沿最短方向運行的問題，是解決了一些手頭的數據但也沒有完全解決所有問題，在前文已經闡述過了。
第七次作業中，依舊出現了RTLE的問題，而且令人絕望的是115s的時間要求本人的代碼需要117s跑完。問題依舊出在調度策略上，每次只處理一個請求，致使時間被拉長。
所以說，整個第二單元都是被可惡的RTLE包圍的狀態，在互測和強測中我因為線程不安全的問題除了第一次的輸出時間戳不遞增的問題外並未被hack出來，可能主要的問題還是別的錯誤太多了吧（嘆氣）。
2.2> 互測bug
第五次作業，由於當時已經意識到自己是一個掛在強測房裡的靈魂，於是早早倒下，沒有再出刀。
第六次作業中，本人意欲大開殺戒，但是並未造出什麼可靠的數據，只是把所有關於橫向電梯的數據都喂給了各個程式併發現了有RTLE的情況，最後發現是該戰友的電梯以為還有乘客沒上來，一直在空轉。所以線程的結束是一個很重要的問題。
第七次作業中，本人也是暴力造出了所有可能的數據，並挑選了運行時間最長的50條請求，針對一位同志的超乘、另一位同志的不使用新電梯所以會RTLE的問題、第三位同志的輪詢還有同層的橫向請求無輸出的情況進行了攻擊。當然，觀察到房內每個人的成功率都在66%，蒟蒻也早該意識到她這次的強測所遭遇的不測。
三 / 度量分析
3.1> 代碼長度
同比代碼行數多了很多，每次迭代的工程量都不小，但是裡面不乏很多重覆的可以整合的代碼。
3.2> 複雜度分析
可見，三次作業的複雜度都不低，這裡只選取了總表和有紅色標出的部分表格。
複雜度高的地方主要為電梯調度方法和程設法的圖論顧問，蒟蒻目前除了繼續提取類似代碼以外也確實沒有什麼解決辦法了。同樣的，複雜度高的地方出錯概率也高，這點在這次的bug中也有很好的印證。
四 / 心得體會
本單元意圖教會我什麼是多線程，如何處理多線程。
或許，蒟蒻只能說或許，她可能懂得了一點點多線程的入門，懂得了一點點為什麼要上鎖（解決數據競爭）、怎麼上鎖（同步塊、讀寫鎖等）；兩個線程的執行順序是怎樣的（隨機），線程又是怎麼被調度的（可能同期的OS課涉及這類內容更多）；線程怎麼互相讓位（wait/sleep），又怎樣喚醒（notifyAll）；為什麼會出現線程不安全（隨機性強，鎖上的不准確），怎麼產生的死鎖（都在等待）、活縮（都在乾自己的事情，但無法互相喚醒交互）、輪詢（不使用wait/notify）等等不正常的現象。至少她現在以不像剛剛拿到一份training中錯誤的多線程代碼時和該程式期待著它的完結一樣絕望了，她已經掌握了一點點調試多線程的方法，無論是隨地分發System.out.println()
所以，這個單元的設計是成功的，但從所獲得的成績來看，本人是失敗的。
但她真的只得到了挫敗感嗎？並不，在一次次電梯超出邏輯的運行方式中她也在磨煉自己的性子，靜下來調試、研究，從奇異的輸出中獲取樂趣，從捉蟲成功中獲取動力；在一次次作業的push下努力學習設計模式，從工廠模式、組合模式到生產-消費者模式、觀察者模式、單例模式、裝飾器模式，這些奇怪的抽象概念一點點變得清晰，雖說在運用中仍有許多困難，理解中仍有許多障礙，但是獲取知識的過程遠比獲得成績單的打擊要快樂許多。
