[TOC] 電梯作業總結程式結構與複雜度的分析第一次作業 1.設計思路第一次作業是電梯作業的第一次，也是我多線程變成的第一次實踐。任務是編寫一個多線程實時電梯系統，採用FAFS的調度方式。由於第一次作業中沒有涉及到多部電梯以及捎帶的情況，因此來說是比較簡單的。我採用的是指導書提示部分中的模式， ...

電梯作業總結

電梯作業總結

程式結構與複雜度的分析

第一次作業

1.設計思路

第一次作業是電梯作業的第一次，也是我多線程變成的第一次實踐。任務是編寫一個多線程實時電梯系統，採用FAFS的調度方式。由於第一次作業中沒有涉及到多部電梯以及捎帶的情況，因此來說是比較簡單的。我採用的是指導書提示部分中的模式，即生產者消費者模式

主線程進行輸入的管理，使用ElevatorInput，負責接收請求並存入隊列
開一個線程，用於模擬電梯的活動，負責從隊列中取出請求併進行執行，執行完後繼續取繼續執行
構建一個隊列，用於管理請求，且需要保證隊列是線程安全的

ElevatorInputHanler

在第五次的作業中，我將主線程main直接作為了輸入管理進程，原因是看到了知道書中的主線程進行輸入的管理，使用ElevatorInput，負責接收請求並存入隊列

Request

在理解了題意和指導書中的模式推薦，我覺得這和我之前在《設計模式——可復用面向對象軟體的基礎》這本書中看到的生產者——消費者模式相近，故我採用了該模式來編寫Request類

Elevator

Elevator類就是電梯類，內部保存著電梯的狀態（如當前樓層），主要完成電梯在接收到請求之後的上下路以及開關門的操作

整體架構圖如下：

2.度量分析

(1)複雜度分析

從圖中可以看出在第一次電梯作業中，我的程式的複雜度在一個合適的範圍，說明我第一次作業的設計是比較合理的

(2)類規模

在第一次作業中我的每個類的規模都在100行以內，比較合理

(3)時序圖

第二次作業

1.設計思路

第二次作業中，電梯仍然是一部電梯，只是演算法上用ALS捎帶演算法代替了FAFS的傻瓜調度，所以整體的架構我還是沿用第一次作業，仍然以生產者消費者模式為主。三各類的功能和第一次作業大體相同，只不過因為ALS演算法而添加了不同的方法，在這裡不過多贅述，整體結構圖如下：

2.度量分析

(1)複雜度分析

Elevator.deal()函數的代碼如下：

private void deal() throws InterruptedException {
        sleep(30);
        queueRequest = request.getQueueRequest(nowFloor);
        if (first) {
            request.getAnother(direction, nowFloor);
        }
        if (queueRequest.size() >= 1) {
            int i = 0;
            boolean isOpen = false;
            while (i < queueRequest.size()) {
                if ((queueRequest.get(i).getFromFloor() == nowFloor
                        && request.getFlag(i) != 0)
                        || (queueRequest.get(i).getToFloor() == nowFloor
                        && request.getFlag(i) != 1)) {
                    isOpen = true;
                    break;
                }
                i++;
            }
            if (isOpen) {
                open(nowFloor);
            }
            i = 0;
            while (i < queueRequest.size()) {
                if (queueRequest.get(i).getFromFloor() == nowFloor
                        && request.getFlag(i) != 0) {
                    movePeople(nowFloor, queueRequest.get(i).getPersonId(),
                            "IN");
                    if (request.getFlag(i) == 1) {
                        request.setFlag(i, 0);
                    }
                    i++;
                    continue;
                }
                if (queueRequest.get(i).getToFloor() == nowFloor
                        && request.getFlag(i) != 1) {
                    movePeople(nowFloor, queueRequest.get(i).getPersonId(),
                            "OUT");
                    queueRequest.remove(i);
                    request.removeFlag(i);
                    continue;
                }
                i++;
            }
            if (isOpen) {
                sleep(timeOpenOrClose * 2);
                close(nowFloor);
            }
            queueRequest = request.getQueueRequest(nowFloor);
            if (first) {
                request.getAnother(direction, nowFloor);
            }
        }
    }

首先，從代碼中很容易看出裡面包含了很多的if分支以及if分支的嵌套，這導致了v(G)的數值很大；並且在函數內部的request.getQueueRequest()函數是對Request實例方法的調用，並且在其中調用了很多的本類中的方法，增加了模塊與模塊之間的調用，所以iv(G)的數值高；總體的導致整體複雜度ev(G)的提高。

Request.getAnother()的代碼如下：

public synchronized void getAnother(int direction, int nowFloor) {
        if (!queue.isEmpty() && queue.get(0) != null) {
            int i = 0;
            while (i < queue.size()) {
                if (queue.get(i) != null) {
                    if ((queue.get(i).getToFloor() - queue.get(i)
                            .getFromFloor()) * direction > 0
                            && (nowFloor - queue.get(i).getFromFloor())
                            * (nowFloor - queue.get(i).getToFloor()) >= 0) {
                        queueRequest.add(queue.get(i));
                        flag.add(-1);
                        queue.remove(i);
                        continue;
                    }
                }
                i++;
            }
        }
    }

從中可以看車裡面的if分支的條件判斷十分複雜，並且存在嵌套，這大大提高了程式調試的難度，我在第二次作業中出現的BUG也正是因為這個方法中的條件判斷出現了問題。

Request.getQueueRequest()方法的代碼如下：

public synchronized ArrayList<
            PersonRequest> getQueueRequest(int nowFloor) {
        while (queue.isEmpty() && queueRequest.isEmpty()) {
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        if (queueRequest.isEmpty()) {
            queueRequest.add(queue.get(0));
            flag.add(1);
            if (queue.get(0) != null) {
                queue.remove(0);
            }
        }
        if (queue.size() >= 1 && queue.get(0) != null) {
            for (int i = 0; i < queue.size(); i++) {
                if (queue.get(i) != null) {
                    if ((queueRequest.get(0).getToFloor() - nowFloor)
                            * (queue.get(i).getToFloor() - nowFloor) >= 0) {
                        queueRequest.add(queue.get(i));
                        flag.add(1);
                    }
                }
            }
            for (int i = 1; i < queueRequest.size(); i++) {
                queue.remove(queueRequest.get(i));
            }
        }
        return queueRequest;
    }

從代碼中可以看到，在這個方法中使用了Elevator類中的成員變數nowFloor，並且其中使用了大量的ArrayList類型的成員變數，這大大提高了這個方法的耦合度，導致了Elevator和Request兩個類之間的依賴關係十分顯著。此外，其中大量的if分支嵌套也大大提高了複雜度。

(2)類規模

從圖中可以看出只有*ELevator**類的行數高於100，我覺得其中的原因主要是由於第二次作業是在第一次作業的架構上進行的功能的添加。這導致了Elevator類中由於捎帶增加了很多方法，以及每個方法的代碼量。

(3)時序圖

第三次作業

1.設計思路

在第三次作業中，要求三部電梯進行調度，並且不同的電梯的可達樓層不一樣，這不僅導致了多線程的線程安全問題，也導致了請求的分配問題。因為一個人的請求有可能需要通過換乘來處理。我的程式主要保證的是正確性，所以犧牲了很大一部分的性能。我解決這種情況的方法是，將這種請求分割為兩個請求，以1層為界，因為所有的電梯都可以到達1層。

並且在整體的結構上，我這次採用的是課件上的Worker-Thread模式，相當於對之前的作業進行了重構。

Main類是主類
Request類是請求類，是對提供的PersonRequest類型的請求的一個封裝，因為考慮到要對請求的起始樓層進行修改
ClientThread類是輸入類，負責將接收到的請求存儲到Channel的請求隊列中
Channel類是整體的調度器，用來將請求跟據不同的情況分配到不同的電梯中，並且在這次作業中，我採用請求隊列和調度器二合為一的方式
WorkerThread類相當於前兩次作業當中的電梯類
-整體程式的架構圖如下：

2.度量分析

(1)複雜度分析

由於第三次作業中的Channel.getAnother()、Channel.takeRequest()和WorkerThread.deal()三個方法和第二次作業中的基本相同，故複雜度不在這裡重覆分析。

WorkerThread.moveElevator()方法的代碼如下：

    private void moveElevator(int floor, boolean doDeal)
            throws InterruptedException {
        while (nowFloor != floor) {
            try {
                if (nowFloor < floor) {
                    int temp = nowFloor;
                    for (int i = 1; i <= stopFloor.get(stopFloor.
                            indexOf(temp) + 1) - temp; i++) {
                        if (nowFloor == -1) {
                            nowFloor = 1;
                            i++;
                        } else {
                            nowFloor = temp + i;
                        }
                        sleep(moveTime);
                        arrive(nowFloor);
                    }
                } else {
                    int temp = nowFloor;
                    for (int i = 1; i <= temp - stopFloor.
                            get(stopFloor.indexOf(temp) - 1); i++) {
                        if (nowFloor == 1) {
                            nowFloor = -1;
                            i++;
                        } else {
                            nowFloor = temp - i;
                        }
                        sleep(moveTime);
                        arrive(nowFloor);
                    }
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
                if (doDeal && nowFloor != floor) {
                deal();
                if (requestQueue.isEmpty()) {
                    break;
                }
            }
        }
        deal();
    }

從中可以很容易的看出導致ev(G)和v(G)兩個複雜度數值大的主要原因就是內部的if分支的嵌套問題。

WorkerThread.run()

 public void run() {
        while (true) {
            try {
                sleep(50);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            if (requestQueue.size() < maxNum) {
                channel.takeRequest(requestQueue,
                        this.getName(), nowFloor, flag, maxNum);
            }
            if (requestQueue.size() == 1 && requestQueue.get(0) == null) {
                break;
            }
            if (requestQueue.isEmpty()) {
                continue;
            }
            try {
                first = true;
                direction = requestQueue.get(0).getFromFloor() - nowFloor;
                logger.debug(direction);
                moveElevator(requestQueue.get(0).getFromFloor(), false);
                first = false;
                Request another;
                while ((another = dealFlag()) != null) {
                    direction = another.getToFloor() - nowFloor;
                    moveElevator(another.getToFloor(), true);
                }
                direction = requestQueue.get(0).getToFloor();
                moveElevator(requestQueue.get(0).getToFloor(), true);
                while (!requestQueue.isEmpty() && requestQueue.get(0) != null) {
                    if (flag.get(0) == 1) {
                        direction = requestQueue.get(0).getFromFloor();
                        moveElevator(requestQueue.get(0).getFromFloor(), true);
                    } else {
                        direction = requestQueue.get(0).getFromFloor();
                        moveElevator(requestQueue.get(0).getToFloor(), true);
                    }
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

與前面的moveELevator()相比，除了因為if分支導致的結構複雜以外，這個函數中由於調用了Channel類的實例channel的方法，導致了兩個類之間的調用關係複雜，依賴程度高，提高了程式的耦合度，而且作為一個線程的run()方法，這樣的高複雜度很容易導致線程安全的問題

(2)類規模

(3)時序圖

程式BUG的分析

在這三次作業的強測和互測階段，我一共只遇到了一種BUG。這個BUG體現在輸出中就是一個人還沒有進電梯就從電梯裡面出來了。我遇到這個BUG是在第二次電梯作業的強測階段，一共有4個測試用例測出了我這個BUG，導致我自己差一點沒進強測。

經過分析，我發現這個BUG出現的原因是在捎帶請求的處理上，出問題的地方是Request類中：

public synchronized void getAnother(int direction, int nowFloor) {
        if (!queue.isEmpty() && queue.get(0) != null) {
            int i = 0;
            while (i < queue.size()) {
                if (queue.get(i) != null) {
                    if ((queue.get(i).getToFloor() -
                            queue.get(i).getFromFloor()) * direction >= 0
                            && (queue.get(i).getFromFloor() - nowFloor)  /***/
                            * direction >= 0 /***/
                            && (queue.get(i).getToFloor() - nowFloor) /***/
                            * direction >= 0 /***/
                            && direction != 0) { /***/
                        requestQueue.add(queue.get(i));
                        flag.add(-1);
                        queue.remove(i);
                        continue;
                    }
                }
                i++;
            }
        }
    }

出問題的部分就是我在代碼中標註出來的。這一部分的條件一開始我沒有加上。我處理捎帶請求的思路是，我的電梯剛開始向著主請求的起始樓層運動，在這個過程中，如果有一個請求的運行方向和我當前電梯運行方向一樣，我就捎帶。但是，我最初沒有加上一個判斷條件：這個捎帶請求的起始樓層必須是還未到達。這就導致了我實際上在隊列中存儲了一個請求作為捎帶請求，但是沒有輸出這個人進入電梯的消息，最終導致了BUG的產生。

互測

自動評測

在這三次的互測過程中，我採用的都是自動化評測的方式。

我的測評機主要分為一下幾個部分：

數據生成器
定時輸入數據
結果檢查

數據生成器

N：請求總數，通過randint聲稱
personId：人員Id，從0開始遞增
Floor：一個列表，裡面存儲著電梯能夠到達的樓層
Time：時間，起始值為0.0
TimeAdd：一個列表，Time的增長幅度，初值為[0.0, 0.1]

每一次迴圈，使用隨機數來選擇0.0或0.1作為時間的增長

用隨機數來選擇起始樓層和終止樓層，如果選擇的樓層一樣則重新選擇直到不同為止
將請求輸出到文件中

定時輸入數據(JAVA)

DealClass
InputClass
Instruction
MainClass
OutputClass

InputClass

返回一個String[]數組，內部保存著所有的輸入

Instruction

指令類
內部有time(double)和ins(String)兩個屬性
time屬性是請求的時間
Ins屬性是請求
構造方法

Public Instruction(double time, String ins) {
    this.time = time;
    this.ins = ins;
}

DealClass

解析輸入的請求
通過正則表達式提取請求中的時間和請求本身
使用instruction的構造方法
返回一個Instruction[]數組

OutputClass

輸出線程
當前時間now初始為0
對於每一個請求，通過sleep的方式控制輸出的前後

Thread.sleep((long)(time * (ins[i].getTime() - now)));
Now = instruction[i].getTime();

結果檢查(python)

初始化一個trueRequest字典和outRequest字典
trueRequest通過解析輸入文件，得到每個人的真正請求
outRequest通過解析輸出文件，得到每個人在電梯運行之後實際執行的請求
PersonId作為鍵值，[fromFloor, toFloor]作為元素，通過對比字典的每一項，如果相同就說明結果正確

Batch命令

javac -cp elevator-input-hw3-1.4-jar-with-dependencies.jar;timable-output-1.1-raw-jar-with-dependencies.jar src/*.java -d src/class
javac -cp elevator-input-hw3-1.4-jar-with-dependencies.jar;timable-output-1.1-raw-jar-with-dependencies.jar TestClass/src/*.java -d TestClass/class
set /a a = 0
:start
echo %a%
data.py
type in.txt |java -classpath TestClass/class MainClass |java -classpath elevator-input-hw3-1.4-jar-with-dependencies.jar;timable-output-1.1-raw-jar-with-dependencies.jar;src/class MainClass > dzh.txt
check.py
if %ERRORLEVEL% == 0 (
    color 47
    goto end
    ) else (
    color 27
    set /a a += 1
    goto start
)
:end

結果展示

有效性

與第一次作業不同，我認為在本次評測過程中，自動化評測是十分必要的。在第一次作業裡面，如果你不會自動評測，通過手動構造樣例最起碼是能夠評測的，但是這次作業如果沒有自動化的方式，光定時輸入一點就很難做到。要想能夠模擬評測的機的定時輸入方式，必須要採用自動化評測的方式才夠準確。如果是單純的靠手輸入，是難以保障準確性的。

但是呢，我認為線程安全方面的BUG，閱讀代碼要比自動評測更有效。因為通過代碼結構的分析，你就能找到這個程式裡面哪些資源是互斥的，哪些線程之間需要同步關係，一旦你找到了其中的BUG，那麼只需要簡單的構造一組樣例就可以hack別人。

總結

本次的三次電梯作業，讓我對多線程有了一個從無到有的實踐。相比第一次作業，我的程式的設計明顯的有了提高，在這三次作業中，我使用過兩個模式：生產者模式和Worker-Thread模式，這使得我的程式的模塊的分工分明，大大降低了BUG修複過程中的困難。並且，在電梯作業的設計過程中，我對請求隊列究竟放在電梯內部還是放在調度器中思考了很久，最終選擇了放在電梯中。我認為這樣的思考是一個很好的鍛煉過程。

並且在這三次作業中我嘗試了自己製作對拍器，也對batch命令有了更深的認識。

但是，在這三次電梯作業中我都沒有去嘗試對電梯的調度進行優化，在研討課上聽了大佬們的LOOK演算法，覺得這一部分的缺漏是一個很大的需要補的地方。並且，對於多線程裡面鎖的使用，我都是直接將方法上了鎖，而沒有採用鎖代碼塊或者採用阻塞隊列這樣更高效率並且更高端的操作，我認為這些都是在以後需要提高的。

OO——電梯作業總結

電梯作業總結

程式結構與複雜度的分析

第一次作業

1.設計思路

ElevatorInputHanler

Request

Elevator

2.度量分析

(1)複雜度分析

(2)類規模

(3)時序圖

第二次作業

1.設計思路

2.度量分析

(1)複雜度分析

(2)類規模

(3)時序圖

第三次作業

1.設計思路

2.度量分析

(1)複雜度分析

(2)類規模

(3)時序圖

程式BUG的分析

互測

自動評測

數據生成器

定時輸入數據(JAVA)

InputClass

Instruction

DealClass

OutputClass

結果檢查(python)

Batch命令

結果展示

有效性

總結