文章目錄

• • 前言
  • 第一次作業
  • • 架構
    • • Producer-Consumer模型
      • 調度策略
      • 類圖和時序圖
    • 鎖和同步
    • 復雜度分析
    • tips
    • • 二次詢問
      • 電梯反轉
      • 開門判斷
      • HashMap遍歷刪除
      • 些許優化
    • Bug分析
  • 第二次作業
  • • 架構
    • • 調度器
      • 換乘 + 線程結束
      • 類圖和時序圖
    • 復雜度分析
    • tips
    • Bug分析
  • 第三次作業
  • • 架構
    • 功能實現
    • • 可達性
      • 樓層限制
      • • Semaphore
        • 實現
    • 復雜度分析
    • Bug分析
  • 心得體會
  • 參考

前言

第二單元的主題是電梯調度問題，主要是初步學習多線程的編程思想，解決線程交互和線程安全的問題。早就聽說第二單元多線程是OO的一座大山，榮文戈老師也說過以后上班遇到的程序基本上全都和多線程掛鉤，所以多線程的學習是很關鍵的，給哪個對象加鎖，如何正確且高效地給對象加鎖，都是值得思考的問題。

這一單元的三次作業也是層層遞進，逐步實現了電梯維修、加入電梯、限制電梯可達性和限制樓層服務電梯數量等功能。在本次作業中，我也學會了一些比較常用的設計模式如單例模式和觀察者模式等，以及經典的并發同步模式生產者-消費者模式，使得整個項目的耦合度更低，代碼層次清晰。

第一次作業

第一次作業為模擬多線程實時電梯系統，實現6部電梯對實時加入的乘客請求做出反應，接到乘客并送到指定位置，需要模擬電梯的上下行、開關門以及乘客的進出。

架構

Producer-Consumer模型

首先分析需要將哪些類作為線程運行，首先就是輸入（InputHandler)需要不斷讀取請求，其次就是電梯(Elevator)需要不斷反應請求并模擬運行。

而將這兩個線程連接起來的就是請求(Request)，所以生產者-消費者模型的結構也很清晰了，輸入作為生產者，電梯作為消費者，在兩個之間我們需要一個容器來盛放請求，于是設計請求隊列(RequestTable)作為這個容器，容器有放入請求和取出請求的功能，而之所以容器不作為線程就在于放入和請求這兩個動作的發出者不是容器本身(參考自助餐窗口，柜臺是固定的)。

至此，我們可以得到以下的結構

我采用的是所有電梯共用一個請求隊列的做法，各個電梯自由競爭。

調度策略

電梯調度問題沒有一個全局最優解，總會有一些情況使得一個算法劣于其他的算法。目前有的與電梯調度調度相關的算法有ALS,LOOK,SCAN等，課程組給出的算法是ALS，但往屆學長大多選擇的是LOOK算法，并且我也感覺后者實現的難度要相對低一點，所以選擇了LOOK算法。

具體實現過程——

• 首先電梯有一個初始的運動方向(建議使用$\pm 1$，實現比booolean類型方便)
• 判斷是否需要開門
• 電梯內是否有人出電梯
• 該樓層是否有人的請求方向和電梯的運動方向一致
• 判斷電梯內是否有人
  • 如果有人，那么沿當前方向繼續移動一層
  • 否則，判斷請求隊列是否為空
    • 如果不為空，接著判斷當前方向是否有請求
      • 如果有請求，那么沿當前方向繼續移動一層
      • 否則，變換方向
    • 否則，判斷輸入線程是否結束
      • 如果結束了，那么結束電梯線程
      • 否則，進入等待狀態

如上所述，電梯做出的反應有Open，Move，Reverse，Wait，Over5種，可以設計一個策略類(strategy)來封裝LOOK算法，根據電梯目前的狀態給出電梯需要做出的反應，電梯收到后進行相應的動作。這樣可以使得電梯運行和判斷相分離，電梯本身更加專注于動作，結構層次也更加清晰。

類圖和時序圖

大致流程如上圖所示，無論是放入請求還是輸入結束，都會使得請求隊列喚醒電梯，而電梯都會根據策略來進行下一步動作。

鎖和同步

本次作業采用的是使用synchronized取得對象鎖，避免線程安全問題，保證同一時間不會出現兩個線程對同一對象寫或者讀寫。

synchronized有三種加鎖的方式——

修飾實例方法：作用于當前對象實例加鎖，進入同步代碼前要獲得當前對象實例的鎖

synchronized void method(){}

修飾靜態方法：作用于當前類的所有實例，進入同步代碼前要獲得當前類的鎖

synchronized static void method(){}

修飾一個代碼塊：給指定的類或者對象加鎖，在進入同步代碼前需要獲得指定類或者對象的鎖

synchronized(obj or example.class){//TODO }

修飾實例方法與在方法內修飾整個代碼塊取得當前實例的鎖類似，而修飾靜態方法與在方法內修飾整個代碼塊取得當前類的鎖類似。

需要注意的是實例的鎖與類的鎖不同，實例的鎖屬于這個實例，類的鎖屬于類(廢話)。講這個的目的就是為了說明，當一個線程訪問加鎖的靜態方法時，另一個進程依然可以訪問加鎖的實例方法，兩者不沖突。當然加鎖的方法和不加鎖的方法也不會沖突。

需要加鎖的位置就是有多個線程進行讀寫的共享數據，在本次作業種顯然是請求隊列，有輸入的寫，以及電梯的讀寫，為了保證每次操作的正確性，我們在進行讀寫之前都要對請求隊列加鎖，保證進行的是原子操作(執行過程不會被打斷)。本次作業將請求隊列內部涉及修改和讀取修改變量的方法都加了鎖，在外部對需要保證請求隊列狀態的代碼塊上了鎖。

notifyAll的操作只在修改了共享變量之后存在。

復雜度分析

主要出在策略類中，因為涉及大量的if-else判斷以及for循環遍歷樓層的請求隊列，所以這部分復雜度略高。

tips

二次詢問

因為各個電梯共用一個請求隊列，并且策略類將詢問和執行分開了，所以可能會出現多個電梯在同一個樓層都給出開門的指示，但是顯然只有一個電梯會接到人(接人操作上鎖，所以不會出現接到同一個人)，其他的電梯就只開門和關門，這樣會白白增加耗電量(雖然自由競爭本身會出現多個電梯都向一個請求跑，耗電量巨大)。一種解決方法就是在開門的操作內部，先對請求隊列上鎖，然后再次詢問策略類當前動作是否還應該是開門，如果是才將人取出，進行接下來的操作。

synchronized (requestTable) {Advice advice = scheduler.getAdvice(curFloor,curNum,direction,eleMap.get(curFloor));if (advice != Advice.OPEN) {return;}tmpQueue = requestTable.take(curFloor,direction,curNum - curQueue.size()); }

電梯反轉

在電梯沒人判斷當前方向上是否有人的時候，不應該包含當前樓層，否則電梯直接沿著當前方向走了，會出現升天或者遁地的情況。

開門判斷

為了簡便，在策略內判斷是否有人進入的時候，傳入的當前樓層人數包括可能下電梯的人，所以可能因為超載判斷為不需要開門，不過沒關系，因為如果有人回下電梯的話就一定會開門，在取人的時候減去下去的人數即可。(要是沒有二次詢問這個操作的話，直接按順序下人上人不用特意減，可惜刪不得)

HashMap遍歷刪除

在從請求隊列中取人的時候我使用了如下操作

for (PersonRequest person : curQueue) {if (curNum + tmpQueue.size() == Tool.capacity) {break;}if ((person.getToFloor() - curFloor) * direction >= 0) {tmpQueue.add(person);curQueue.remove(person);} }

即一邊遍歷一邊刪除，但是運行的時候會出現java.util.ConcurrentModificationException的報錯，于是去網上查找了相關資料。

簡單來說就是HashMap內部維護了一個modCount變量，迭代器里維護了一個expectedModCount變量，初始兩者相同，每次HashMap移除和新加元素的時候modCount會自增，此時迭代器里的expectedModCount不變，而迭代器遍歷的時候會用到nextNode()方法，當兩個值不等的時候就會拋出異常。

基本上JAVA集合類在遍歷時不用迭代器進行刪除都會報錯，這樣是為了防止高并發情況下，多個線程同時修改集合導致數據不一致。

解決方法就是使用迭代器進行遍歷和刪除，迭代器的刪除也會先判斷兩者值是否相等，然后調用HashMap的removeNode()方法，最后會令expectedModCount=modCount，這樣就不會出現錯誤了。

Iterator<PersonRequest> it = curQueue.iterator();while (it.hasNext() && curNum + tmpQueue.size() < Tool.capacity) {PersonRequest person = it.next();if ((person.getToFloor() - curFloor) * direction >= 0) {tmpQueue.add(person);it.remove();} }

或者使用線程安全的currentHashMap替代HashMap，或者在遍歷結束后再遍歷取出來的列表對請求隊列進行刪除。

些許優化

在研討課時，有同學提出既然自由競爭會出現1個請求喚醒6部電梯的情況，那么每來一個請求不使用notifyAll而是使用notify就可以減少耗電量，我覺得有道理，不過貌似這樣就不像自由競爭了，雖然也和直接分配不同，總的來說還是一個不錯的提議。

其次就是另一個同學提出在電梯取人的時候可以不直接鎖整個隊列，而是將對應樓層的隊列鎖住，這樣其他樓層的電梯也可以在此時取人，雖然優化可能不是很明顯，不過想法很好，顯然要是為了正確性鎖住整個隊列是更好的，比較無腦，為了性能的話就要將需要鎖的部分想清楚，不然正確性可能沒法保證。

Bug分析

中測中出現上述有關HashMap刪除的錯誤，強測和互測沒有出現Bug，強測得分97.1553，還是比較出乎我的意料，畢竟自由競爭耗電量確實難蚌。

第二次作業

第二次作業在第一次作業的基礎上需要模擬電梯系統擴建和日常維護時乘客的調度，同時電梯增加速度和容量參數。

架構

調度器

為了實現擴建和維護功能就需要一個統領所有電梯的容器，來記錄目前還在運行的電梯，于是設計了調度器(Scheduler)，同時由于第一次作業6部電梯一起搶一個請求實在讓我挺難受的，所以我決定讓調度器同時擔任分發請求的任務，讓每部電梯都有自己的乘客隊列，于是產生了以下結構

相比于第一次作業，輸入得到請求有三種分別是PersonRequest、ElevatorRequest、MaintainRequest，不同的請求處理方式肯定事不同的，于是在哪個部分對請求進行分類就是一個問題，我采用的方式是在調度器內進行分類處理，于是輸入和請求隊列基本上就不需要改動，然后電梯依賴的請求隊列變成了乘客隊列也只是相當于換了個名字，總的來說原則就是讓每個類的職責清晰明了。

換乘 + 線程結束

因為維修請求的存在，電梯可能放出沒有到達目的地的乘客，所以會出現乘客需要換乘的情況，處理還是比較簡單，直接將沒有到達目的地的乘客更改出發樓層然后重新丟進請求隊列即可，調度器會將其作為一個新的請求讀取并分配。

但是隨之而來就出現了另一個問題，電梯線程在何時結束，之前的結束判斷是電梯內沒人并且請求隊列為空且輸入結束，但是在本次作業請求來源不再只是輸入，還可能是換乘的乘客，所以需要改變結束判斷。

可以發現，雖然有換乘但是總的乘客數是不變的，于是可以設計請求計數(RequestCount)維護一個count，當輸入向請求隊列放入乘客的時候令count+1，當電梯將乘客送到目的地之后令count-1，于是結束判斷就變成了輸入結束且count=0。

由于JAVA沒有全局變量這個概念，所以可以使用 單例模式 實現全局變量，本次作業 請求隊列和請求計數都使用了單例模式(靜態變量和方法實現在本次作業也可以，不過兩者略有區別，在此不做討論)。

有一點需要吐槽的是，課程組給出的PersonRequest不支持修改出發樓層，于是我自己寫了一個Person，沒什么不同只是為了修改，當然重新實例化一個PersonRequest也是可行的。(不過這個名字有點長，我不是很喜歡)

類圖和時序圖

復雜度分析

調度器的run內部根據請求隊列的狀態判斷是結束線程還是等待還是處理請求，if-else語句導致復雜度較高。

tips

• 本次作業中每個電梯都有自己的乘客隊列，所以不再需要二次詢問。
• 理論課上講解了讀寫鎖的使用，能夠允許多個線程同時進行讀，不過現在jdk版本下synchronized效率也挺高的，也就沒進行更改。
• 這次作業要采用自由競爭也是可以的，由輸入對請求分類然后進行操作即可，不過架構不是很好看就是了，提這個的目的只是覺得我的調度沒有用到速度這一參數，自由競爭在這方面還是有一定優勢。
• 在接到維修指令之后需要立即將電梯從調度器中刪除，防止有新的請求放入其中。

Bug分析

中測的時候出現了以下bug

• 調度器在請求隊列中wait，請求計數不能直接喚醒，需要先獲得請求隊列的鎖(我感覺這一部分我寫的比較混亂)
• 因為我自己寫了Person，但是調度器在處理的時候忘記判斷了，導致換乘的乘客沒有處理，雖然我加了assert，但是運行的時候沒加-ea參數，導致沒及時發現錯誤。(值得一提的是課程組貌似也沒有這個參數，所以找錯還挺麻煩的，不過這是一個好習慣)

強測沒有問題得分95.1183，互測出現了程序無法結束的問題，我找了很久也不知道問題出現在哪。

分配策略我采用的是純隨機(random)，運氣不好的話可能都分到一部電梯去了。

第三次作業

第三次作業在第二次作業的基礎上，限制了電梯的可達性(只能在一些樓層開門服務)和樓層的最多服務電梯數。

架構

這次作業的架構沒有什么調整，增加的功能都可以放在已有的模塊中進行實現，故UML類圖和時序圖可以參照第二次作業。

功能實現

可達性

雖然規定了電梯只能在某些樓層開門服務，但在遇到維修的時候也是可以突破這個限制的，所以為了統一性我們不應該讓可達性成為電梯的內置屬性，而是通過調度器分配符合電梯可達性的乘客，讓其看上去是滿足要求的，實際上電梯都是功能完全的，能夠在任意樓層開門。

那么問題就在調度器如何進行分配了，由于可達性的存在可能會出現乘客一趟不能到達目的地的情況，于是很自然的想到給乘客增加一個當前目的地的屬性，對于這個屬性的選取有很多種考量方法，我采用的和課程組類似——尋找最少換乘次數的策略，然后選擇已有請求最少的電梯進行分配。

首先在調度器內維護一個二維數組map[i][j]表示有幾部電梯能夠從i樓到j樓，每次增加或者刪除一個電梯就根據它的可達性對map進行更新

private void updateMap(int access,int type) {for (int i = Tool.minFloor;i <= Tool.maxFloor;i++) {if (accessible(access,i)) {for (int j = Tool.minFloor; j <= Tool.maxFloor;j++) {if (accessible(access,j)) {map[i][j] += type;}}}} }

對于最少換乘次數dis[i][j]的計算可以簡單的使用floyd即可，賦初值部分

for (int i = Tool.minFloor;i <= Tool.maxFloor;i++) {for (int j = Tool.minFloor;j <= Tool.maxFloor;j++) {dis[i][j] = i == j ? 0 : map[i][j] != 0 ? 1 : 114514;} }

算完最短路關于選擇目的地采用map[from][i] != 0 && dis[from][i] + dis[i][to] == dis[from][to]判斷即可，最后會返回一個可行的目的地，但是正規來講的話應該返回一個集合，這樣后續分配會更加均勻。

需要注意的是，設置當前目的地后電梯的策略類的判斷同向也應該做出相應修改，其次每次請求被調度器取出時都會重新規劃，而不是規劃出總的路線，因為如果路線中的電梯被維修了就需要重新規劃，為了簡便就每次都算一次。

樓層限制

本次作業限制一層樓同時只有4個服務(開門)的電梯，2個只接人($set \sube new_set $)的電梯，后者屬于前者，因為在我的實現中出去的乘客不會被馬上接進來，所以只接人電梯相當于是沒有出去的人。

Semaphore

實驗課上介紹了Semaphore(信號量)的使用，鎖的存在使得同一時間只有一個線程能夠操作這個對象，而如果想要多個線程同時使用的話，就需要信號量了。信號量內部維護了一個計數器存著可以訪問的共享資源的數量，線程要想訪問共享資源就需要獲得信號量，如果計數器大于0則允許訪問并將計數器-1，如果計數器等于0則線程進入休眠，當某個線程釋放信號量之后休眠的進程會被喚醒并嘗試獲取信號量。

Semaphore semaphore = new Semaphore(10,true); // 信號量總數，是否公平(先到的先獲得) semaphore.acquire(); // 獲取信號量 semaphore.release(); // 釋放信號量

獲得信號量之后一定要釋放。

實現

有兩種限制，所以對每層樓都需要兩個信號量記為s1(4,true),s2(2,true)，當電梯需要開門的時候，如果是普通的電梯只需要獲得s1即可，而只接人電梯則需要先獲得s1再獲得s2(順序好像沒關系)，關門的時候再釋放相應信號量即可，信號量都放在了請求計數中。

復雜度分析

getDispatchGoal是求下一個目的地的部分，內部有挺多的循環嵌套和if-else判斷。

Bug分析

三次測試都沒問題，強測得分95.2392，不過用hhl同學的評測機總會是不是出現線程無法正常結束的情況，通過輸出信息發現是有乘客被吃掉了，放入了電梯但是并沒有去接他，最后也沒有發現是哪出問題了。

心得體會

• 三次作業電梯運行、策略、輸入以及請求隊列部分原有的代碼基本上都不會發生太大改變，主要的變化在于電梯增加維修的能力，調度器更換調度策略還有結束的判斷等，不過只要大的框架定了后續的迭代也就比較簡單了。可以發現的是后續迭代課程組對沒有調度器的自由競爭并不是很友好，如果不在第二次作業進行重構的話，第三次作業需要改動的東西就更多了。不過架構的確定還是蠻看經驗的，也不能說某一個架構就一定好，不過還是應該盡量滿足solid原則。

• 性能方面，我還是為了簡單和易于實現起見，犧牲了部分性能，調度采用自由競爭、隨機分配和均勻分配，有的同學采用影子電梯(復制所有電梯狀態，模擬判斷請求的最優分配方式)，聽說得分挺高的，不過本來電梯調度就沒有全局最優，我認為首要的還是應該保證架構，有了比較好的架構，換一個調度器也不是很麻煩的事，就像榮文戈老師說的，分工好之后要是這個調度不行就換個程序員做調度器。

• 總的來說，相比于第一單元，這一單元感覺架構更加清晰，各個模塊耦合度不高，功能也相對清晰，更有面向對象的感覺。不過這次作業還是留下了一點遺憾，就是第二三次作業的bug還是沒找出來，這也讓我感到多線程的艱難。

參考

「BUAA-OO」第二單元:電梯調度 | Hyggge’s Blog

「BUAA OO Unit 2 HW8」第二單元總結 - 被水淹沒的一條魚

HashMap遍歷的時候使用map.remove會報錯

為什么 HashMap 不能一邊遍歷一邊刪除？

總結

以上是生活随笔為你收集整理的[BUAA OO Unit 2 HW8] 第二单元总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。