BUAA_OO_2021_ 第二單元 - 難度巔峰之多執行緒電梯
寫在前面
早就耳聞了面向物件課程第二單元的難度，在面臨一個全新的領域——多執行緒時，或多或少都會手足無措吧，對于一個普普通通的計算機專業的學生來說，沒有大佬們對于代碼強大的理解與拓展能力，只能看著入門教程一點點自學，十分痛苦，多虧了廖雪峰老師網站的java多執行緒入門，我才對多執行緒思想有了些許體會，但俗話說“師傅領進門，修行在個人”，對于這個單元的作業，最最重要也是最最基礎的就是 wait() 和 notifyAll() 的使用來對執行緒進行調度；另一個最最重要也是最最基礎的就是 synchronized() ，對于鎖的使用還是十分抽象的，但經過了這三次作業的摸索，我對這二者有了一個較深的理解，
oo上機時的實驗代碼也給我帶來了非非非常大的幫助（雖然后來被錘有bug）上課時老師給的多執行緒的例子難免非常簡單， 而實驗代碼清晰的架構以及對多執行緒的操作的示例都給我前兩次作業帶來了很大的啟示，如果學弟學妹們無意中刷到了這篇博客，聽學長一句勸：不要死磕自己丑到爆的架構，在入門的時候借鑒借鑒優秀代碼，會事半功倍，
一、同步塊的設定與鎖的選擇
三次作業使用的同步鎖是synchronized() ，而未使用Lock，
synchronized()可修飾的物件有：
- 修飾一個代碼塊：被修飾的代碼塊稱為陳述句同步塊，其作用范圍是使用大括號{}括起來的代碼，作用的物件是
synchronized(object)中的object， - 修飾一個方法：被修飾的方法稱為同步方法，其作用范圍是整個方法，作用的物件是呼叫這個方法的物件，
- 修飾一個靜態方法：作用范圍是整個靜態方法，作用物件是這個類的所有物件，
- 修飾一個類：作用范圍是整個類中所有方法，作用物件是這個類的所有物件，
三次作業的同步塊統一采用的是使用 synchronized() 鎖住代碼塊，而非給方法加鎖，更沒有給類加鎖，一是為了性能考慮，畢竟加鎖的代碼塊越小越好，二是我想鍛煉一下自己對于synchronized() 的理解，給小塊代碼加鎖，雖然對于互斥問題的解決更加復雜，但這也正是多執行緒編程的精髓，
總體而言，這三次中都存在的電梯安全問題是輸入執行緒和電梯執行緒對于等待佇列的讀寫操作，
在三次作業的電梯類中，我采用的是Look演算法進行調度，因此在每次有新請求進入電梯后，都要對要去的最高（最低樓層）進行更新，但整個程序都是對于本部電梯內部屬性的操作，并沒有導致執行緒沖突，只有在第七次作業中加入了換乘操作，才導致了不同電梯之間的執行緒安全問題，
下面介紹具體到每一次作業中的呈現形式：
第五次作業
本次作業架構比較簡單，只有一部電梯因此共享物件并不多，
共享物件有：waitQueue（等待佇列）
waitQueue的同步問題主要涉及以下幾點：
-
inputThread執行緒在輸入后需要將需求 寫入 waitQueue，并喚醒電梯
synchronized (waitQueue) { if (request == null) { waitQueue.close(); waitQueue.notifyAll(); try { elevatorInput.close(); } catch (IOException e) { e.printStackTrace(); } return; } else { waitQueue.addRequest(request); waitQueue.notifyAll(); } } -
elevator執行緒需要讀取 waitQueue中是否有人，若沒人則需要
wait()synchronized (waitQueue) { if (elevatorRequests.isEmpty() && waitQueue.noWaiting() && waitQueue.isEnd()) { return; } if (waitQueue.noWaiting()) { try { waitQueue.wait(); } catch (InterruptedException e) { e.printStackTrace(); } } } -
elevator執行緒需要讀取 waitQueue在某一層的人，如果有滿足上電梯條件的請求，則還需要將請求寫出 waitQueue
由于對于waitQueue的讀寫操作涉及演算法核心，因此不附代碼
第六次作業
本次作業增加了多部電梯，因此增加了Scheduler調度器類，來對各個請求進行分配，架構與前一次單部電梯相比復雜了不少，也造成了更多的執行緒安全問題，
共享物件有：totalQueue（請求總佇列），waitQueue（每部電梯單獨的等待佇列）
所有同步問題如圖：
從圖中可知各個執行緒對于總等待佇列和各個電梯的等待佇列的執行緒安全沖突問題，因此在每次讀寫操作時，都要使用synchronized() 解決同步問題，如：
//Scheduler調度器執行緒中：
synchronized (totalQueue) {
if (totalQueue.isEnd() && totalQueue.noWaiting()) {
for (Elevator elevator : elevators) {
WaitQueue waitQueue = elevator.getWaitQueue();
synchronized (waitQueue) {
waitQueue.notifyAll();
}
}
return;
}
if (totalQueue.noWaiting()) {
try {
totalQueue.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
} //解除總等待佇列的鎖，可以繼續進行輸入
//Elevator電梯執行緒中：
synchronized (waitQueue) {
if (elevatorRequests.isEmpty() && waitQueue.noWaiting()
&& totalQueue.isEnd() && totalQueue.noWaiting()) {
return;
}
if (waitQueue.noWaiting() || (type == 1 && !totalQueue.isEnd())) {
try {
direction = 0;
waitQueue.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
direction = waitQueue.getRequest(0).getToFloor()
- waitQueue.getRequest(0).getFromFloor();
}//解除電梯等待佇列的鎖，調度器可以繼續進行分配
第七次作業
本次作業增加了電梯的種類屬性，為了優化性能，因此增加了換乘策略，造成了不同電梯間互相改變等待佇列的執行緒安全問題，
共享物件有：totalQueue（請求總佇列），waitQueue（每部電梯單獨的等待佇列）
所有同步問題如圖：
從圖中可以看出，由于增加了A類電梯和B類電梯之間的換乘策略，導致了在不同電梯之間也會產生執行緒安全問題，因此除了上文給出的第六次作業中的代碼外，還會出現以下形式的同步塊與鎖的設定：
//換乘操作
int toFloor = request.getToFloor();
int fromFloor = floor;
int id = request.getPersonId();
PersonRequest newRequest = new PersonRequest(fromFloor, toFloor, id);
elevatorRequests.remove(request);
TimableOutput.println("OUT-" + request.getPersonId() + "-" + floor + "-" + idNumber);
i--;
synchronized (totalQueue) {
totalQueue.getRequests().add(0, newRequest);
totalQueue.notifyAll();
}
二、調度器設計
第五次作業
“就一部電梯，調度器有啥用呢？”
開始做第五次作業之前，我就是這樣想的，于是把已經建好的Scheduler類默默刪掉了，
事實也是這樣，一部電梯的確不需要調度，而這次作業的核心應當是對于單部電梯調度演算法的設計，比如指導書給出的als演算法，以及最常用，性能也不錯，容易實作的look演算法（這三次作業的Random模式使用的都是look演算法，真香！）而調度器這東西，雖然知道在后面一定會再加上，也知道在第一次添上調度器的話有利于之后作業的拓展，但俗話說：“一口吃不成胖子，”我知道自己水平咋樣，就不如剛剛接觸多執行緒的時候，整個簡單點的架構吧~
于是第五次作業并沒有調度器，所有輸入的請求直接進入等待佇列，等待電梯的臨幸，
下面介紹一下三種模式下電梯的運行策略：
- Night
Night 模式的兩大特點：
- 目的樓層確定（都是一樓）
- 所有乘客同時到達
因此可以將其看作靜態請求，對于處理靜態請求，總會有一個最優解，而我采取的策略是
電梯從高處往低處接，每次接六個，如果不足六個則接完就結束
這個策略十分簡單，性能也還不錯，然而對于Night 模式還是有別的最優解的，只是代碼會復雜很多，而在我能力范圍之內，這種策略的性價比很高，
- Morning
Morning模式的最大問題是，人并不是一口氣都到一樓，而是動態添加的，
由于是動態模型，不同人的演算法可能會造成很大的性能差異，而我采取了一種比較穩妥地方法：
等人
只有當來了六個人，電梯滿員時，才會發車，否則就一直等著，除非識別到已經停止輸入了，這種方法帶來的一個玄學問題是：無法保證在等人的程序中是不是有時間能夠把電梯上的人先送上去，但如果要實作這樣的機制的話，代碼量應該是十分驚人的，我也就沒有再深究，
- Random
我采用了傳統電梯搭載的look 演算法，并在其基礎上進行了些許優化，其運行策略如下：
1、獲取等待佇列中所有上行請求的最低層 和所有下行請求的最高層 ，并判斷電梯當前所處位置離誰更近，然后去往更近的那個樓層，并改變電梯的運行方向次序，
2、電梯按照選擇好的運行次序運行，并把目標樓層設定為電梯中所有請求的目的樓層的最高層，
3、電梯在每一層進行遍歷：首先遍歷電梯中的請求有沒有目的樓層是該樓層的，并處理出電梯的請求；然后遍歷等待佇列中有沒有前往樓層方向與電梯運行方向相同的，并在該樓層上電梯的請求，若有，則上電梯；若請求的目的樓層要高于目前電梯運行要去的最高樓層，則將電梯的最高樓層屬性更新，
4、當電梯到達目標樓層（即所有請求的最高樓層或最低樓層）后，電梯掉頭，重復上述行為，
這種演算法與日常生活中的電梯十分相似，也很好理解，經過實踐，性能也說得過去，
第六次作業
第五次作業欠下的債，早晚都要還的，
第六次作業要把請求們按照一定的策略分給多部電梯了，因此需要設計調度器以及調度器演算法，來實作請求的調度，
調度器的遇到的難點如下：
? 1、如何制定合理的分人策略，是影響電梯性能的最關鍵因素
? 2、如何處理好調度器執行緒與電梯執行緒、調度器執行緒與輸入執行緒之間的矛盾，是電梯能否順利運行的關鍵因素
制定的分人策略如下：
- Night
Night模式的分配策略比較容易想到，畢竟是靜態請求，
? 1、將總請求佇列中的人從高往低排序
? 2、按照每六個為一組，輪流分給各部電梯
這樣做也會遇到些許問題，比如無法統一處理高層請求，對于人數較少的情況無法調動所有電梯，但我認為這些問題導致的性能差異微乎其微，便沒有再進行優化，
- Morning
實在沒有想出完美的解決辦法，于是采取將請求均分給所有電梯的調度策略，
? 1、每次提取出總等待佇列的第一個請求，進行處理，
? 2、遍歷所有的電梯的等待佇列，選擇等待請求最少的電梯
? 3、將提取出的請求分配給所選擇的電梯
? 4、重復上述操作，直到總請求佇列為空
這樣的策略有顯而易見的性能問題，比如每部電梯為了等夠6個人，等待的時間特別長，
- Random
Random模式的調度策略比較復雜，我總體按照的是“順路原則”進行分配，具體分配程序如圖：
雖然并不能保證這樣的演算法是最優的，但可以保證順路原則的的確確提高了很多性能，
第七次作業
換乘！換乘！換乘！
隨著換乘演算法的加入，第二單元作業難度達到了高潮，
難道非換乘不可嗎？當然不是，最簡單的調度方法便是：
? 1、所有符合高樓層條件的請求一律給C類電梯
? 2、所有奇數層到奇數層的請求一律給B類電梯
? 3、其它所有請求一律給A類電梯
這樣，第七次作業的調度器就更改完畢啦！
我按照這樣的調度策略，寫了第七次作業的原始版本，并得到了不換乘的性能時間，然后便開始設計換乘調度策略，
? 1、所有符合C類電梯的請求，直接分配給請求最少的C類電梯，不換乘
? 2、所有奇數層到奇數層的請求，直接分配給請求最少的B類電梯，不換乘
? 3、所有偶數層到偶數層的請求，直接分配給請求最少的A類電梯，不換乘
? 4、所有偶數層到奇數層的請求，先分配給A類電梯，運送到最鄰近的奇數樓層后，換乘給B類電梯
? 5、所有奇數層到偶數層的請求，先分配給B類電梯，運送到最鄰近目的地的偶數樓層后，換乘給A類電梯
哈哈，換乘也不過如此嘛！
真的不過如此嗎？
不是！且不說這種換成策略的性能問題，單看整個換乘程序，明明是為了換乘而換乘啊！我提交了“優化后”的這個版本，果然不出我所料，這個版本的性能比不優化的原始版本還要差...沒錯，我的換乘策略是負優化，又考慮到第一單元就是由于各種優化演算法才導致了強測出鍋，我得到了一個結論：如果能力不足，謹慎優化！
三、從功能設計與性能設計的平衡方面，分析和總結自己第三次作業架構設計的可擴展性
第七次作業UML圖
第七次作業UML協作圖
本次的架構設計為“消費者——生產者模型”，生產者為InputThread 執行緒，消費者為Elevator 執行緒，并不復雜，
關于可擴展性，在這樣的架構之下，分配調度演算法與運行演算法分離，一定程度上提升了可擴展性，但總的來說，可擴展性還是不高的，畢竟在寫程式的程序中有著“反正寫完這三次就沒了”的心里，沒有太多考慮程式的可擴展性，
四、分析自己程式的BUG
第五次作業
未發現自己程式bug，也未被hack，并且代碼提交一次通過，沒進行debug，（所以下次作業就飄了）
第六次作業
BUG警告！ 本次作業強測稍炸，出現的鍋是由于morning演算法的行程結束問題，導致4個morning模式的測驗樣例執行緒沒能正常結束，從而導致rtle，這個bug是我測驗的時候樣例過弱導致的，很明顯也很容易de的一個bug，竟然被放生到強測中，真的不應該，
第七次作業
未發現自己程式bug，也未被hack，但在寫程式中出現過輪詢導致的tle的bug，原因是wait() 方法呼叫條件有誤造成程式沒有正常進行等待，
在debug程序中，的確出現過死鎖的問題，出現了鎖的嵌套，并且同步塊過大，就十分有可能出現死鎖，而且有的死鎖竟然很難復現，這給我的debug造成了一定的困擾，好在我及時定位到了bug，并絞盡腦汁地把嵌套的鎖拆開，不惜犧牲一些性能，也要保證執行緒安全，
五、分析發現別人程式bug所采用的策略
由于本單元作業的輸入是隨機投放的，這就導致只要不是C組，想要hack別人，就只能借助評測機了，可能是由于評測機生成的樣例太弱，這三次作業都沒能成功hack別人，
我也曾經嘗試過肉眼debug，但由于別人的代碼架構和我的代碼或多或少有些區別，而且也沒有注釋，導致肉眼debug變得十分困難乃至不可能完成，我也著重查看了鎖嵌套的情況，并思考有沒有死鎖情況的發生，但同學們的代碼都很強，并沒有發現有什么例外，
遙想上個單元，三次作業都沒使用評測機，只是通過自己的火眼金睛，即使在A組，都能成功hack別人，但在多執行緒這個單元，肉眼不太管用了，甚至評測機的效率都不太高了...
六、心得體會
- 執行緒安全問題是多執行緒編程最重要的問題之一，執行緒不安全的多執行緒是沒有意義的，當然，如果把所有的類都用
synchronized()鎖起來，執行緒也就百分百安全了，但也就由多執行緒退化成單執行緒了...如何在盡可能優化性能的前提下保證執行緒安全，是一件值得琢磨的事，這也許就是多執行緒的魅力吧， - 層次化設計在多執行緒中是必須的，畢竟要把每一個層次抽象出來，每一個執行緒也都分工明確，一個好的架構對于多執行緒而言是前提，多學幾個架構也沒啥壞處，但把模板架構與具體任務結合起來的時候，就要花一點心思了，
- 本單元作業又跟上一單元一樣，在第二次作業翻車，肯定是有點遺憾的，不過還有兩個單元呢，希望之后的單元別再翻車了嗚嗚嗚，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/280206.html
標籤：面向對象