OO-Unit2-Summary

前言

本次作业要求使用java多线程编程，通过使用同步块和锁，编写合适的调度策略等一系列操作完成对电梯的模拟。

homework_5

要求

• 六部电梯可以任意穿梭于1-11楼，初始时刻均处于1层，每个电梯限乘6人

思路

拿到题目的瞬间大概有三个想法:电梯主导的运行方式(自由竞争) or 调度器dispatcher主导的运行方式 or 调度器dispatcher决定大概方向,电梯自主决定运行方式(模拟等调度算法)。在第一次做homework_5的时候，我选择了调度器决定电梯运行方式的调度方式。通过调度器算法直接决定Elevator的Tofloor来确定电梯的运行方式，将一切复杂的东西交给调度器。但是由于对锁的认识不到位，导致了一些死锁，最终导致了一次较为惨痛的失利。

乘客调度思路

乘客调度思路即将把乘客分配到合适电梯的策略，通常来讲会先判断是否对乘客进行捎带，之后再确定好分配的具体电梯。具体分配方式为:找出电梯中delta = Math.abs(toFloor - curFloor) + Math.abs(toFloor - PersonRequest.fromFloor)最小的电梯，但是如果该电梯正在远离PersonRequest且存在电梯其正在靠近PersonRequest且其delta不大于最小delta的某个系数倍，则将该乘客分配至该电梯。(该系数大概率需要大量数据调参，但是我偷懒模拟了大概情况选择了2)

其实在听了第六周的讨论课之后，我听到了wbx同学介绍的模拟算法模拟电梯，我瞬间意识到了自己的算法其实就是一个超级简化版本的模拟，但是由于是调度器完全决定电梯运行方式，电梯几乎就是一个调度器意志的无情执行器，这完全不符合多线程之间相互协作的要求，过高的耦合度也导致了死锁的产生，最终导致了调度思路没有继续下去。

 public void dispatch() {
     synchronized(requestQueue) {
         if (!this.requestQueue.isEmpty()) {
             for(int i = 0; i < this.requestQueue.getPersonRequests().size(); ++i) {
                 PersonRequest personRequest = this.requestQueue.getPersonRequests().get(i);
                 if (this.hashMap.get(personRequest) == -1 && !this.pass(personRequest)) {
                     this.unPass(personRequest);
                 }
             }
         }
     }
 }

public void unPass(PersonRequest personRequest) {
     int min = 114514;
     int dir = personRequest.getToFloor() - personRequest.getFromFloor();
     int mini = 0;
     int mindir = 0;
     boolean flag = false;
     if (hashMap.get(personRequest) == -1) {//Person isn't distributed
                 //select the least distance between elevator.ToFloor and person
         if (flag) {
             if (elevator.getDirection() == 0 && elevator.getState() == State.WAITING) {
                 synchronized(elevator) {
                     elevator.notify();
                 }
             }
             if (//different direction or waiting) {
                 elevator.setToFloor(personRequest.getFromFloor());
             }
         }
     }
 }

电梯运行思路

在homework5中，我的电梯的主要方法有open(),close(),move(),In(),Out()，我的电梯的运行方向是由ToFloor和curFloor之间的大小关系决定的，而ToFloor由调度器决定，没有任何运行策略，路途中有下电梯的自然下电梯，所以可以说我的电梯没有脑子

同步块和锁的选择

我选择了synchronized同步块，主要作用在requestQueue类的读写操作，dispatcher调用电梯状态参量，但是由于在刚开始接触多线程时缺乏对线程不安全行为认知，在elevator部分方法中出现了read modify write的经典线程不安全行为，在需求池中出现了Arraylist为NULL的异常。

框架具体实现

下面是类图和流程图：

问题

乍一看，其实没有很明显的问题，但是只要仔细看每个线程中的变量就能轻易发现，我的线程之间基本上可以说是互相包含，互相调用，互相读写，这本是非常低级的错误，我在仔细学习了多线程基本知识之后也了解到了死锁的含义，但是框架已经搭建完成，在用评测机进行自动化测试之后，大约1k条至多出现3.5个tle且无法复现，所以我被蒙蔽了双眼，误以为死锁已经基本排查干净，出现卡死的现象是多线程的常见行为，其实根本不应如此

测试 & bug & debug

测试的主要方法是println判断CTLE轮询，编写正确性验证代码判断结果，自己生成一些高并发度的数据测试。之后讨论区出现了评测机，遂白嫖，测试的过程中发现在1k条中可能有10条左右的TLE，我以为这是多线程的机制，实则不然，好的多线程在压力测试下多次测试也应该能输出正确的结果，我当时不以为然，于是在强测中出现了巨大的bug。

中测的过程中出现了轮询导致CTLE的情况，判断好notify的时机和判定正确的终止条件即可。

强测RTLE了十二个点，勇猛无敌的拿下了三十八分的强测成绩，主要是在电梯读取调度器中的分配数组，调度器读取电梯状态互相进行了synchronized导致了死锁，想要修好这类bug就必须去除电梯读取调度器的过程，因为调度器想要分配乘客必须获取电梯的当前状态，必须要去除一定量的锁。我对elevator加入了一个对应的waitList，具体的运行方式交给电梯。由于实在积重难返，我决定进行一次重构式的修复bug。

互测中由于在C房，刀中别人大概二十刀，主要问题基本都是线程不安全行为导致的RE,死锁和无捎带策略带来的RTLE

homework_5.5

思路

电梯调度策略

自由竞争策略，时间和等待时间大概率不会太差，但是电量一定超标，由于第一次作业的暴死，我已经不敢要求太多了。当RequestQueue中有PersonRequest时，空的Elevator会按照Look算法寻找相应的电梯并且向其移动，Look算法主要按照下面几条准则:

1. 同向的PersonRequest会捎带上

2. 当将所有乘客运送结束后，如果当前方向仍然有乘客，继续按照该方向行动，如果该方向没有乘客，则reverse调转方向，若还是没有同方向乘客，则wait等待合适的时机到来。

其中有一点：当多个电梯同时到达乘客所在楼层时，可能出现多个电梯同时开门的情况，会造成性能损失，于是我在open之前使elevator提前获取乘客进入对应的waitList，等到open之后再具体进入。这也暗示了其实大多数调度策略都是相似的:即在合适的时刻将乘客放到电梯的waitList上，而自由竞争的时刻是在其进入电梯前一刻，这或许是各种策略的共性。

同步块和锁的选择

还是选择了synchronized关键字，主要包括RequestQueue的读取，添加方法，避免在RequestQueue方面出现多个线程同时读写的线程不安全行为，而且在自由竞争的调度策略下，调度器只是个摆设，最终整个程序的锁的结构大概是:

RequestQueue-(synchronized)-->Dispatcher-(synchronized)-->Elevator --(synchronized)-> RequestQueue <---(synchronized)--Input 

在调度器唤醒时，电梯类无法获得RequestQueue的锁，由此可见，在这样的结构下，绝不可能出现环形锁从而导致死锁，只要在Elevator获得RequestQueue锁的部分保证避免经典的read modify write等线程错误即可。而在经过一次讨论课之后，我对读写关系也有了一个新的认知：当一个变量尝试去读取一个线程的状态的时候如果想要避免死锁，可以尝试将读取改成线程的写操作，将读取自身状态的方法加上synchronized关键字，这样可以避免线程之间的相互读取从而避免死锁。

协作图

bug & debug

homework5.5仅仅出现在了修复bug环节和hw_6,7中，在修复bug的过程中没有出现任何问题，很快解决了问题，在hw_6,7中，在该框架的基础上也没有出现比较大的硬伤，每次开发符合老师所要求的增量开发，几乎没有太多修改的地方。

homework_6

要求

• 六部电梯可以任意穿梭于1-11楼，初始时刻均处于1层，每个电梯限乘6人

• 可以新增电梯，其运行速度，容量，初始楼层都是由Request决定的

• 新增Maintain维修指令，当电梯接收到指令后需要在两次arrive内将所有乘客放出来，并且该电梯将不会再次运行。

思路

Maintain指令的实现

在我看来Maintain指令主要有两个主要的问题:

1. 如何将Maintain信号传入Elevator

2. 在Maintain之后的后续乘客该何去何从？

第一个问题的答案主要有两种方法:

1. RequestQueue将Maintain指令传给Dispatcher或者Elevator，改变其状态，使其进行removeAll()的操作同时除去RequestQueue中的Maintain指令。

2. Elevator主动读取RequestQueue类似自由竞争读取PersonRequest的操作，找到对应id的Maintain指令，在进行RemoveAll()方法之后将Maintain除去RequestQueue。

两种方法都是可行的，只要第一种方法不加多余的锁也不会导致死锁，但是在讨论课上，我了解到一位同学的想法：Elevator相当于一个黑盒，绝不允许其被他人读，只允许他对别的类写，这样Elevator除了notify绝对不会被其他类锁住。这样可以从根源上断绝环形死锁的可能。所以我选择了第二种方式。

第二个问题的解决方法主要是改变Elevator线程的结束条件。在第5.5次作业中，我电梯结束的条件是RequestQueue.isEmpty() && Personin.size() == 0但是由于Maintain指令可能会将PersonRequest反哺回到RequestQueue，电梯线程可能在线程结束后仍然出现没有送达的乘客。因此我考虑将结束的条件加上NoMaintain()的信号，保证需求池中不存在Maintain指令，则所有电梯中的人都可以一趟送到，这个条件判断是一个限制性很强的条件，并不接触到电梯运行的本质，遂在第七次作业被放弃更改。

AddElevator指令的实现

这个比较简单，创建一个新的Elevator线程即可。

流程图

测试 & bug & debug

测试主要采用白嫖了讨论区的多线程评测机，大量测试高并发度的数据，保证了即使在一秒内输入200+条消息也不会出现TLE的情况，高并发度大当量的数据测试后，程序的可靠性是值得信赖的。

本次中测，强测和互测中没有出现bug。

互测中刀中同学两刀，其问题使在Maintain操作之后乘客从电梯出去所在楼层不是curFloor而是其fromFloor。

互测中的意外发现

发现了评测机的bug：在Maintain操作之后离开电梯的PersonRequest再次上电梯时，不会对PersonRequest的curFloor做正确性检验。比如

[   3.4335]OUT-1-5-1//从五楼下去
[   3.6336]CLOSE-5-1
[   3.6440]MAINTAIN_ABLE-1
[   5.1000]OPEN-1-3
[   5.1000]IN-1-1-3//他应该在五楼被接进去

这样的数据是不会报错的，但是这显然是不正确的，也算是意外发现，小小的收获。（当然也反馈给助教gg了）

homework_7

要求

• 对电梯新增了Access属性，采用掩码(mask)的方式来限制电梯的可达性。这导致了换乘的可能性

• 限制了每一层电梯开门的数量必须小于$M_x$，每一层只进人（或者说不出人）的数量必须小于$N_x$。

思路

限制开门电梯数量的实现

采用了Semaphore信号量的性质，开出两个Semaphore数组，通过Semaphore.acquire(int curfloor)方法和Semaphore.release(int curfloor)来进行信号量的获取与释放，完美的解决了这个问题。

public class Global {
    private final Semaphore[] semaphore1 = new Semaphore[15];

    private final Semaphore[] semaphore2 = new Semaphore[15];

    public void acquireSemaphore1(int curFloor) {
        try {
            semaphore1[curFloor].acquire();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public void acquireSemaphore2(int curFloor) {
        try {
            semaphore2[curFloor].acquire();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public void releaseSemaphore1(int curFloor) {
        semaphore1[curFloor].release();
    }

    public void releaseSemaphore2(int curFloor) {
        semaphore2[curFloor].release();
    }
    
}

换乘的dfs实现

我采用了对电梯进行深度优先搜索的方法解决换乘的问题。这次的掩码可以很好的解决电梯换乘问题中的电梯转换楼层。下面是主要步骤：

1. 通过dfs找出所有适用于换乘的Access数组，选出换乘次数最少的一个

2. 将Access数组转化为只有一位为1的Access数组，代表每一步的目标楼层。将该PersonRequest的fromfloor作为第一项，tofloor作为最后一项。

3. 新建Person类，将该数组的前两项放入start和end，即，只保留第一步走的楼层，将电梯的出入逻辑由PersonRequest.toFloor() == curFloor改成Person.getEnd() == 1 << (curFloor - 1)，将运行逻辑从楼层转化为掩码。

public class Person extends Request {
    private final PersonRequest personRequest;

    private int start;

    private int end;
}

private void dfs(ArrayList<ArrayList<Integer>> arrayList, int depth, int start,
                     int end, int[] flag, ArrayList<Integer> elevatornum) {
        if (depth > 5) {
            return;
        }//深度大于5，直接返回
        int access = 0;
        int size = elevatornum.size();//掩码数组，用以存储电梯性质从而规划具体路径
        for (int i = 0; i < size; i++) {
            access |= accessElevator.get(elevatornum.get(i));
        }
        int size1 = elevatorArrayList.size();
        for (int i = 0; i < size1; i++) {
            Elevator elevator = elevatorArrayList.get(i);
            if (!elevator.isAlive() || elevator.isMaintain()) {
                continue;
            }
            int access1;
            if (((access & accessElevator.get(i)) != 0) || (depth == 0)) {
                access1 = access | accessElevator.get(i);
            } else {
                access1 = 0;
            }
            if ((access1 & start) == 0) {
                continue;
            }
            if (flag[i] != 0) {
                continue;
            }//一些剪枝
            flag[i] = 1;
            elevatornum.add(i);
            if ((access1 & (start | end)) == (start | end)) {
                //存入结果数组
            } else {
                dfs(arrayList, depth + 1, start, end, flag, elevatornum);
            }
            elevatornum.remove(elevatornum.size() - 1);
            flag[i] = 0;
        }
    }

结束条件的选定

如果按照第六次作业中的NoMaintain作为结束，则当维修结束后的乘客需要换乘时，大多数电梯已经终止线程，会导致路径规划无法规划出合适的道路。因此我采用了HashSet<PersonId>用以标记乘客是否到达目的地，当HashSet.size == 0的时候终止线程。

框架

测试 & bug & debug

测试上主要靠评测机和手捏数据测试，这次测试有一点小小的缺陷就是没有对换乘的情况进行高并发度的测试，忽略了Maintain指令的延迟性，强测错了两个点。

bug:在无全能电梯的情况下Maintain由于电梯被维修是有延迟的，导致可能将乘客规划给了已经被维修的电梯，改一下语句顺序即可。

互测中发现房友的bug，但是不可复现，交上去也没反应。但是从舍友的代码中大概了解到部分同学的代码在限制单层楼人数的时候线程不安全，程序直接卡死。

多线程bug & debug技巧

CTLE

CTLE主要原因有两点:轮询和过于宽松的notify-wait，考虑好每个wait和notify的条件基本可以避免，可以在每个wait-notify和run方法的开头加入System.out.println，如果输出行数过于离谱，可以借此定位轮询或者过度消耗资源的地方。

RTLE

主要是两种情况:

1. 死锁，死锁可以借助jconsole工具直接检查死锁，也可以在设计时就考虑直接避免环形锁的出现避免死锁的发生。

2. 线程未结束，主要在于线程结束的条件，注意不要提前结束线程，考虑好wait或者sleep的条件，可以通过时间相差幅度较大的数据或将Maintain等指令靠后放置的数据进行测试。

WA & RE

主要是线程不安全行为导致的，第七次作业中，我曾经长时间无法把某个指定的乘客放置到对应的楼层，最后经过排查是在限制楼层人数时并未使用线程安全的Semaphore而是使用数组进行限制，出现了明显的read modify write线程不安全行为，导致乘客在不同线程中的状态不同，有些线程认为他已经进入了电梯，但是实则不然，改成信号量即可。因此在日常多线程编程中，需要养成保持线程安全的习惯。

调试

虽然单步调试在多线程中几乎没用，但是对单个线程而言，调试还是可行的，譬如在第七次作业中规划路径的行为是可以通过单步调试找到一些线程未能按照希望早早结束，剩下的基本可以在譬如break之类的语句之前加上System.out加以判断即可。

难以复现的各种bug

最好当然还是通过排查代码逻辑

心得体会

homework_5

1. 写代码之前要搞清楚多线程的基础知识，熟悉死锁，线程不安全等各种常见错误再开始写。

2. 需要保持线程之间联系的清晰简洁，避免线程之间的过多耦合，每个线程应该协作运行，而非一个线程大权独揽。

homework_5.5

重构不可怕，屎山才可怕

homework_6

1. 测试时可以考虑高并大当量数据

2. 线程结束条件需要考虑清楚

homework_7

1. 选择线程安全的方式去编写程序

2. 注意线程协作之间可能存在的延迟，合理规划语句顺序。

调度策略

自由竞争好写，运行时间和等待时间大概率不差，但是电量极高。重构时间紧迫的无奈之选。

框架中的变与不变

变

1. homework_5和homework_5.5中发生了大规模的重构，从电梯运行逻辑到乘客分配策略基本上变了个遍。

2. 线程结束的条件逐渐放宽，之后考虑其实每次都可以将所有乘客送达作为线程结束条件。

3. PersonRequest和电梯运行逻辑在第七次作业中出现了较大的变化，由于我将PersonRequest加上规划路径的前两部整体换成了Person，电梯送达乘客的逻辑改成了对Person的目标楼层的掩码进行判断。

不变

1. 电梯移动逻辑在homework5.5之后没有发生改变，通过direction进行判断。

2. 需求池的基本方法逻辑没有发生改变。

3. 乘客分配逻辑在homework5.5之后均为自由竞争。

4. 调度器从头到尾都是摆设

收获与展望

从第一次的惨痛失利，到后两次的差强人意，进步可以算是不小了，我深刻意识到了多线程编程与以往程序之间的巨大区别，而且也贡献出了OO生涯第一次重构。一个好的程序，应该饱经风霜而不倒，即使再变态的数据也应该能顶住压力，而想要写出好的程序，需要在动笔时就早早规划好大致的思路并且在写的时候保持好的习惯，理论与实践应当结合，绝不能无脑直接开写，否则迟早吃亏。

希望能在之后的OO继续进步。