BUAA OO 第二單元總結 Part 1 設計策略 這三次作業採用了 主線程獲取請求,多級調度器逐級分派,電梯模擬運行的策略 。具體來說,主線程實例化 類,通過阻塞讀取方式獲得請求 ,之後將請求分配給調度器 ,調度器負責處理請求(既可以自己處理,也可以分配給其他子調度器處理),每一個電梯與一個 綁 ...
BUAA OO 第二單元總結
Part 1 設計策略
這三次作業採用了主線程獲取請求,多級調度器逐級分派,電梯模擬運行的策略。具體來說,主線程實例化ElevatorInput
類,通過阻塞讀取方式獲得請求Request
,之後將請求分配給調度器Scheduler
,調度器負責處理請求(既可以自己處理,也可以分配給其他子調度器處理),每一個電梯與一個ElevatorScheduler
綁定,用於具體的調度、睡眠控制、列印輸出。
本次作業的難點主要有以下幾點:
-
如何控制調度器、電梯線程的終止:簡單的生產者-消費者模型中,生產者不斷生產,消費者不斷消費,不存線上程終止現象;現實中的電梯,一天24小時運行,沒有異常情況也不會終止。但是更多的多線程問題是需要考慮線程終止的。這三次作業也是如此:主線程將所有請求都發送給調度器後,告知調度器準備結束,調度器處理完自己隊列中剩餘請求後,結束線程。
這種一般性的線程生命周期可以用這個比喻來說明:假如你是一個員工,在上班的時候你可能在幹活,也可能閑著,但即使閑著,也不能回家;到了下班時間後,如果你的任務還沒有完成,那就繼續工作(加班),如果完成了,就可以回家了。於是,我們可以抽象出兩個因素:是否空閑(
idle
),是否到達下班時間(在電梯的問題中是輸入是否結束,可用inputEnd
變數表示)。是否空閑是可以自己判斷的,而是否到達下班時間則需要外界的通知。以下討論這種通知輸入結束機制。一種比較容易想到的方法是採用
interrupt
機制while (true) { Request request = elevatorInput.nextRequest(); if (request == null) { scheduler.interrupt(); } else { // pass } }
但是這種方法並不能實現精確控制:我們希望的是,如果調度器在等待下一個輸入(
wait()
函數中),就打斷;而如果它在執行別的任務,比如sleep(100)
,或者是其他的同步任務,就不打斷。雖然在這一單元的作業中沒有出現這種情況,但是多做這種考慮也是合情合理的。另一種方法是專門設定一個
setInputEnd()
方法,由主線程調用,告知調度器輸入結束。class Scheduler { boolean inputEnd = false; Queue<Request> requestQueue; public synchronized void setInputEnd() { this.inputEnd = true; notifyAll(); } public synchronized void addRequest() {} public synchronized void getRequest() { while (requestQueue.isEmpty()) { wait(); } return requestQueue.poll(); } }
我在作業中採用的是這種方法,但是後來發現,其實還可以用一種更加簡潔的方法解決:建立一個
TerminationRequest
類。interface Request {} class PersonRequest implements Request {} class ElevatorRequest implements Request {} class TerminationRequest implements Request {}
這樣,通過歸一化處理,可以用一個隊列來統一管理(更一般的來說,是把所有線程關心的狀態改變的通知都放到統一的容器中管理,對外用同樣的介面,對內採取不同的處理策略)。同時,這種歸一化也方便了線程安全容器的使用。
-
區分兩種獲取請求的模式:在簡單的生產者-消費者模式中,消費者在沒有商品的情況下總是會在共用區中的
wait
函數中等待,但是在實際生活的很多情況下,這種情況是不可接受的——消費者可能還有其他事情要完成,使用wait
函數等待並釋放CPU資源固然是一種進步,但這種方案同時也制約了消費者進行其他活動的自由。回到本單元作業,每一個電梯在行為上都需要實現:獲取新的請求,決定電梯的行為(開門、關門、上行、下行等)。但是這兩種行為並不是時時刻刻都需要進行的:如果電梯局部隊列為空,電梯內部沒有乘客,則電梯處於空閑狀態,此時不需要頻繁決定電梯的行為,只需要等待下一個請求的到來。因此,當電梯空閑時,應當阻塞地讀取請求,即在請求處等待下一個請求;而當電梯忙碌時,則只需要查看並更新請求即可,沒有新請求也不阻塞。這兩種不同的模式,可以自己解決,如:
class ElevatorScheduler { private Queue<Request> queue; private Queue<Request> localQueue; private synchronized Request getRequest(boolean quickRetreat) { if (quickRetreat) { return queue.poll(); // if the queue is empty, return null } else { while (queue.isEmpty()) { wait(); } return queue.poll(); } } }
也可以採用Java內置的
BlockingQueue
來解決:private BlockingQueue<Request> queue; private void update() { if (idle) { localQueue.add(queue.take()); } queue.drainTo(localQueue); }
-
靈活的分配器:第一次作業只有一個電梯;第二次作業有多個電梯,但只有一種型號;第三次作業有不同型號的電梯,每一種電梯型號下的電梯數是不同的。可以這樣認為,第一次作業的電梯只需要一級調度器(直接指揮電梯的調度器),第二次作業的電梯是兩級調度(一級負責電梯見的負載均衡,另一級負責直接指揮電梯),第三次作業的電梯是三級調度(一級總調度器負責換乘相關管理,一級負責同一個類型的電梯的負載均衡,一級負責直接指揮電梯)。如下圖:
為了使得分配更加靈活,給這些
Scheduler
設計一個統一的介面RequestReceiver
即可,至於內部的處理,或分配或自行指揮電梯,請求提供者都不必關心。interface RequestReceiver { void addRequest (Request r); } class CentralScheduler implements RequestReceiver {} class Scheduler implements RequestReceiver {} class ElevatorScheduler implements RequestReceiver {}
-
反饋和閉環控制:在實際多線程編程中,反饋和閉環控制也是十分常見的。本單元作業也不例外:換乘需要進行請求的反饋,即電梯運行一部分請求後,由另一個電梯繼續完成另一部分請求。既然電梯是逐級控制的,電梯處理完自己應該處理的那一部分請求後,需要將請求反饋給上級調度器,由上級調度器進行二次分配。另一方面,調度演算法在進行調度時,也需要考慮各電梯的負載均衡問題,因而電梯也要上報自身的負載情況。
這幾次作業中,可以通過相應線程類提供反饋介面,進行逐級反饋狀態:
interface FeedbackReceiver { void offerFeedback (Feedback fb); void offerRequestFeedback (Collection<PersonRequest> requests); } class CentralScheduler implements RequestReceiver, FeedbackReceiver {} class Scheduler implements RequestReceiver, FeedbackReceiver {}
在反饋反向傳播的時候,每一級
Scheduler
也可以對反饋進行處理,比如作業3中的負載,每一類電梯的負載可以取這一類所有電梯中負載最小的電梯的負載。 -
樓層映射:這個問題其實並沒有什麼面向對象的困難,主要是一個小技巧。每個電梯調度器(直接指揮電梯進行運動的調度器,它實現了調度演算法)有一個映射,實現樓層到樓層下標的快速轉換。
與其通過數學方法實現(分段函數):
int flr_to_ind (int flr) { if (/* some conditions */) { // do something } else if (/* ... */) { // do something } else { // pass } }
不如用Java自帶的方法:
List<Integer> flrs = Arrays.asList(-3, -2, -1, 1, 2, 3); index = flrs.indexOf(flr); flr = flrs.get(index);
Part 2 第三次作業的可擴展性
假如我的第三次作業真正實現了第一部分中所敘述的思想和方法,那麼再進行擴展也不會很複雜了。但事實上我的第三次作業並沒有完全實現這些方法和技巧——程式的主題部分是第五次作業時構建的,之後只做了些小修小補。但是畢竟結構是類似的,也可以做一些分析:
- 實現緊急制動:從
Request
介面下增加一個緊急制動請求的實現,調度器將這一請求分派到對應電梯。電梯到達下一個停靠點時,通過反饋渠道反饋所有的未完成請求,由上層調度器二次分配,同時電梯線程結束運行。 - 更複雜的電梯類型:構造電梯工廠,採用工廠模式,根據所提供的電梯型號生產相應電梯。在調度器方面,增加若幹二級調度器,使每一個電梯類型對應一個調度器。(當然如果類型增量不大,把這一調度器與主調度器合併也是可行的)
- 更大的規模:增加調度級數,實現更細粒度的調度。
從SOLID角度看:
- Single Responsibility Principle:調度器總的說來比較符合這個原則,而電梯類符合度較低。在本人的設計中,電梯類既作為一個容器,管理電梯內的乘客,同時又負責輸出、睡眠,而且請求的管理與
ElevatorScheduler
類的職責部分重疊,耦合過高。在一開始的設計中,電梯的職能被規定為負責輸出和睡眠(因為這兩方面相對固定,可以與易變的ElevatorScheduler
分離,但是在之後的迭代開發中,逐漸職能擴充。 - Open Close Principle:這三次作業在函數層面(即每個類的方法層面)比較符合這一原則,將易變的類和不易變的類分開,迭代開發時主要替換一些函數,不必大規模修改函數。但在類的層次對這一原則符合度較低。在最初的設計中,我本是打算每一個主要的類先寫成抽象類,再通過繼承抽象類進行實現,但最後感覺不太現實,就沒有真正實施,而是直接把抽象類改成具體類……[捂臉](也許小型工程不太容易做到OCP吧,畢竟就那麼幾個類)
- Liskov Substitution Principle:這三次作業關係比較少,但是基本上所有存在的繼承關係都滿足LSP原則了。
- Interface Segregation Principle:其實第三次作業並沒有用到介面,但是如果按照第一部分的分析,每一個調度器都實現
RequestReceiver
、FeedBackReceiver
、Runnable
方法,也算是有一點ISP的意思了。 - Dependency Inversion Principle:畢竟沒有介面,繼承關係也比較少,第三次作業的具體實現其實沒有體現這一原則,不過如果按照第一部分的分析,
main
函數線程只依賴RequestReceiver
介面,也有一點DIP的意思了(雖然沒有實現)。
Part 3 經典度量
考慮到三次作業結構一脈相承,每次迭代又沒有什麼重大改動,就只分析最後一次作業了。
UML圖:
這裡只實現了二級分派結構,其中PersonTransfer
是課程組提供的PersonRequest
類的子類,表示需要換乘的乘客請求。二級分派結構可以解決這三次作業的問題,main函數獲取請求,再由高級調度器分派給低級調度器,低級調度器與電梯類協作,實現look電梯調度演算法。在演算法的實現過程中,需要管理樓層信息、管理用戶請求信息,這些管理由building類和floor類處理,同時設置FloorNumberManager
類,提供一些靜態方法管理樓層映射、可達性查詢等服務。
這種結構的主要問題是沒有處理好電梯類Elevator
和電梯調度器類ElevatorScheduler
之間的關係。電梯調度器類只擁有一個電梯,負責這個電梯更細緻的調度管理,如每一個時間節點,決定電梯上行、下行、開門、關門等動作,主要實現了演算法。但同時,電梯類不僅負責輸出、睡眠,還負責管理電梯內部人員,檢查到達目的地的乘客,反饋電梯內部乘客信息等。在具體實現中,電梯類又將自身容器暴露給電梯管理類,使得兩個類之間耦合度較高。
此外,電梯類Elevator
並沒有成為一個獨立的線程,所以在電梯睡眠時,實際上時是在ElevatorScheduler
線程中睡眠,導致電梯睡眠和電梯調度演算法運行無法並行,降低效率。
複雜度:
可以看出,調度器是比較複雜的類,而調度器中負責演算法的方法又是調度器中比較複雜的方法。但是除了調度器之外,電梯類也比較複雜,這是與設計初衷不符的。原因在上文也提到過,主要是隨著代碼實現的推進,電梯類的職能不斷擴充,與調度類有所交疊,沒有很好處理這一問題。
協作圖:
Part 4 Bug分析
這一單元的作業主要容易出bug的地方包括:
- 程式死鎖,尤其是輸出終止,準備線程結束的時候。
- 偽多線程,主要是指程式實質上是在輪詢,沒有很好實現資源讓出。
- 需求理解偏差。
我在三次作業的強測和互測中均沒有發現bug,但是我的第一次作業(整個課程的第五次作業)有一個非常嚴重的錯誤(強測和互測,由於測試機制固定,都沒有檢測出來):如果所有輸入結束後沒有立刻提供輸入結束信號,程式將會進入死鎖,無法終止。部分代碼如下:
// methods of ElevatorScheduler
public synchronized void setInputEnd() {
this.inputEnd = true;
notifyAll();
}
private synchronized void update(boolean quickRetreat) {
if ( (inputEnd || quickRetreat) && buffer.isEmpty() ) {
return;
}
while (buffer.isEmpty()) {
try {
wait();
/* when the thread is notified, it's still in the while loop */
} catch (InterruptedException e) {
return;
}
}
// some updates here
}
可見,雖然程式退出了wait()
函數,但還是會再次進入wait()
函數,導致死鎖。一個簡單的修複是在while
迴圈上增加一個條件;設計上的修複我在第一部分已經提到過,線程檢測到TerminationRequest
後就不再調用update
函數,把這個問題線上程內部解決。
另一個問題是沒有處理好CPU資源的讓出,表現在輪詢所導致的CPU_TLE
。一般來說,線程空閑時需要等待,可使用wait()
函數,一旦線程需要被喚醒,相應鎖的notifyAll()
函數必須被調用。我在第一次電梯作業的互測中用類似以下數據的數據點發現了兩個A屋的solid bug:
[5.0]1-FROM-2-TO-3
[150.0]2-FROM-14-TO-5
Part 5 測試程式分析
本單元測試程式主要考慮自己的使用,包括三部分:
-
輸入文件的時間映射器,將帶時間的文件輸入映射到時間軸上,實現定時輸入。具體代碼見:https://github.com/YushengZhao/BUAA_OO_elevator_input_mapper
-
電梯模擬器,模擬電梯的真實運行,在運行過程中檢查相關問題。主要思路是:將電梯請求和被測程式輸出轉化成若幹電梯指令,按照時間排序,在模擬器上模擬運行,在運行過程中記錄參數、檢查行為,最終可以給出性能報告。
-
請求指令生成器,可以定製若幹段請求序列,每一段可以設置參數,可參考以下代碼:
def generator(size=10, timescale=10, id_start=1, time_shift=1): # generate one segment of requests pass def generate(): periods = [12,19,8,4,13] sizes = [8,4,10,13,16] s = [] id = 1 time_shift = 0.3 for i, period in enumerate(periods): s += generator(size=sizes[i],timescale=period, id_start=id,time_shift=time_shift) id += (sizes[i]+1) time_shift += (period+0.1)
將這些組件連接起來就可以生成測評機了,但是考慮到自身實際需求,就沒有具體實現了。
一個值得註意的地方:許多同學採用python腳本進行時間映射,我在參考了之前一些學長的博客之後發現,這種方法容易產生時間偏差,時間控制不是很精確,而將時間映射器內嵌到Java語言內部則可以實現更精確的控制。同時,這樣也便於調試。
關於請求生成策略:實際應用中可能會出現不同時段負載不同的情況,我在測評機中按段生成請求,可以模擬這種情況。在進行幾次到幾十次測試後(總請求量1e2
量級),一般沒有什麼顯著問題;進行大量測試(1e3,1e4
量級的測試)也許可以發現一些問題,但考慮到每一個測試所消耗的時間成本,就沒有過多測試了。真正實際應用中,大量的測試肯定是必要的。
這一單元的調試和測試與上一單元相比,主要是多了時間因素,在測試時要考慮輸入隨時間分佈的不同特征,如在一個時間點大量輸入,在一段時間內沒有輸入,等等。而在調試時,由於不能使用斷點調試法,我普遍採用了日誌記錄的方法,增加一個可插拔的logger:
private static final boolean LOGGER = true;
private static final boolean ASSERTION = true;
public static void log(String msg) {
if (LOGGER) {
System.out.println(msg);
}
}
public static void ast(boolean condition, String msg) { // ast == assert
if (ASSERTION && !condition) {
System.out.println("Assertion failed: "+msg);
}
}
或者實現一個帶level
的不同重要性的日誌輸出:
private static final int LEVEL = 5;
public static void log(int level, String msg) {
if (level >= LEVEL) {
System.out.println(msg);
}
}
當然,Java也有相應自帶的日誌記錄機制,不過考慮到這一單元作業並不需要複雜的日誌,就沒有使用了。
Part 6 心得體會
-
多線程方面,我在做電梯第一次作業時花了比較長的時間(甚至一度以為自己就要止步於此了),當時有許多問題想不清楚,最後實現的代碼也有許多邏輯混亂的地方。多線程之所以容易出現各種安全問題,歸根結底還是線程自身行為邏輯複雜,比如,簡單的生產者-消費者模型,基本不會有人寫出線程安全的問題,但是複雜一些的生產者-消費者模型(如消費者在沒有產品時不調用
wait
函數,而是進行其他活動),就容易產生線程安全問題了。因此,根據需求建立簡單通用的線程模型非常重要——簡單的邏輯往往不容易出錯。比如觀察者模式,構建了一個線程發佈消息,若幹線程接收消息的模型;反過來,又有時也需要若幹線程發送消息,某一個線程接收消息的情況,這時便可以採用消息隊列:class Scheduler { private Queue<Message> messageQueue; public synchronized void addMsg() {/*some code here*/} public synchronized Message getMsg() {/*some code here*/} } interface Message {} class Feedback implements Message {} interface Request extends Message {}
所有需要通知
Scheduler
的消息,都通過addMsg
方法傳入,無論其具體內容,之後再由其他函數分別處理。因此,當Scheduler
處理完剩餘任務後,便可以直接在getMsg
方法內等待。 -
設計原則方面,我在完成第一次電梯作業時,並沒有太多的設計原則方面的意識,而由於後兩次作業都沿用第一次作業的結構,所有後兩次作業也沒有體現多少設計原則,這是遺憾的。
-
代碼重構方面,我從這一單元開始堅定了能不重構就不重構的態度。從計組到現在,在各種需要迭代開發的工程中,我總是感覺之前寫的不夠好,想要重構,但又經常忽視了重構的風險以及不重構的可能性。實際開發中,重構肯定是要儘量避免的,在原來的代碼(可能是看似比較亂的代碼)上修改其實才是常態。事實上,看似亂糟糟的代碼其實可能並沒有想象中那麼差。我在第二次電梯作業時曾經嘗試了重構,但是等到真正動手寫重構代碼的時候才發現,如果重構,很多代碼都是差不多的,原來很多設計上的考慮都是很有道理的。
-
演算法方面,這一單元的作業給演算法留出了很大的空間。不過想拿高分並不需要很複雜的演算法。最基本的look演算法,在強測不出現錯誤的情況下,基本就可以達到95分以上了。後兩次作業再加一些負載均衡的考慮,如果沒有錯誤,基本也能拿到95分以上。儘管如此,討論一些演算法也是沒有壞處的:
- 將電梯的列印輸出/睡眠與電梯運行邏輯解耦。這樣做的目的是,可以在不真正運行電梯的前提下(運行一個虛擬電梯),估計電梯的總運行時間,進一步地,加入一個請求後的總運行時間。理論上,這樣總是可以做到局部最優規劃。而且這種估計是不依賴於特定演算法的,靈活性比較強。
- 用馬爾可夫決策過程建模。這樣做是考慮到現在有許多針對馬爾可夫決策過程(Markov Decision Process)的演算法可供使用。
當然這些演算法都是我沒有實現的,畢竟課程的主要目的也不是演算法。
其他:
- 有些問題其實並不是OOP的問題,有些bug其實也不是因為線程安全。比如look演算法,我就花了不少時間實現、調試。
- 很多時候模仿現實世界的實體和關係也是一種很好的方法。比如,給電梯安排一個
Building
,給每一個Building
安排若幹Floor
,並提供“向上的按鈕”和“向下的按鈕”介面,就像現實生活中的電梯一樣。電梯不知道一個樓層有多少人,只知道某一樓層有沒有人想上樓、有沒有人想下樓。 - 第二點的想法雖然對我們寫作業很有幫助,但是這是不是就是在參考真正給電梯寫程式的編程人員的代碼架構呢?其實課程的者幾次作業,我都是或多或少參考了前一屆同學的博客,假如沒有這種參考,我又能寫出什麼樣的結構呢?