• unit 2 总结
  • 同步块的设置和锁的选择
  • 调度器设计
  • 架构模式
  • 程序的bug
  • 发现他人bug的策略
  • 心得体会

unit 2 总结

本次OO第二单元实现的主要任务为模拟了一个多线程电梯运行的基本场景，基于“生产者-消费者模式”实现了满足不同的电梯调度以及运行策略达到满足用户上下楼、换乘等请求的电梯。

不得不说比起往届的博客，可以看出这届的助教还是收手了的，让我们在这一单元的编程充实快乐但又不失必要的痛苦，体会到多线程独特的魅力，对此我深表感激(doge)。

由于本单元的一些问题比较共性，主要集中在线程安全一块，所以本次作业将不采用分作业分析的形式，改用按点总结。

同步块的设置和锁的选择

在HW 5和HW 6中我仅采用了实验中给出的同步控制方法：

public synchronized void addRequest(Request request) {
    requests.add(request);
    notifyAll();
}

public synchronized Request getOneRequest() {
    if (requests.isEmpty()) {
        try {
            wait();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    if (requests.isEmpty()) {
        notifyAll();
        return null;
    }
    /*=====balabala=====*/
    notifyAll();
    return /*=====balabala=====*/;
}

为了保证线程安全，利用synchronized对增加和拿取请求的方法进行修饰，保证同一时刻只能有一个线程对共享队列（调度器向总请求队列 / 调度器向楼层或楼座的队列 / 电梯向楼座或楼层的队列）进行访问。

在电梯或者调度器索取请求的时候，假如队列为空，若此时isEnd()为true，则直接结束线程，否则等待被setEnd()方法notifyAll后结束线程或者被addRequest()方法notifyAll后处理该请求，如此一来在没有请求到来时电梯和调度器即可保持wait，避免了轮询的情况。

笔者在这一单元的作业中把对共享队列的每一个操作全部独立了，没有存在方法中互相调用的情况，原因是怕写着写着莫名其妙地死锁了。后来查阅发现java中线程获得对象的锁是以线程为单位的，同一个线程对同一个对象锁是可重入的，同一个线程可以获取同一把锁多次，也就是可以多次重入。这多好，大大降低了我们死锁的情况，或者说写出了死锁说明我们逻辑太菜了。

然而，用synchronized修饰方法同时约束了读和写操作，一定程度上降低了程序的效率。这是我们不希望的，于是我在HW 7中在对迪杰斯特拉算法的图进行维护的时候采用了ReentrantLock的读写锁机制：

public int[][] getSpath() {
    int[][] updatedPath;
    rlock.lock();
    try {
        updatedPath = spath;
    } finally {
        rlock.unlock();
    }
    return updatedPath;
}

public void initial() {
    wLock.lock();
    try {
        /*=====balabala=====*/
    } finally {
        wLock.unlock();
    }
}

由于在笔者的算法里，对每个请求都需要利用迪杰斯特拉求得的最短路径数组来获得最短路径，而该数组又仅在增加横向电梯的时候需要更改，使用synchronized修饰显然会使请求之间相互阻碍，因此采用读写锁机制控制。读时不能写，写时不能读，平时可以同时读，提高效率。

调度器设计

HW 5:

• 由于HW 5的每个楼座只有一部电梯，实际上并没有涉及到调度策略，调度器仅仅是识别请求并分发，性能分主要取决于电梯本身的运行策略。笔者开了一个Schedule线类用于从总请求队列识别相应的请求并将其添加到到对应楼座的等待队列中。

HW 6：

• 在HW 6中，由于同一楼层和楼座之间可能有多部电梯，涉及到多部电梯会共享一个楼座队列的情况。这里我采用了线程安全的平均分配策略。笔者建立了两层级的调度器结构，首先第一层总调度器Schedule从总的请求队列中识别请求的归属楼座，将该请求分配到第二层级调度器楼座的队列中，再由楼座的队列根据均分算法分配到每个电梯的waitQueue中，这样每部电梯事先就在调度层面被安排好了要接取的乘客，不会出现多部电梯争抢的情况，胜在线程安全。
• 但是由于是事先安排，电梯是“懒汉式”的，即有需求才会动，与共享队列中争抢的“饿汉式”相比，平均分配更多的等待意味着更少的概率在中途捎带上乘客，意味着电梯的性能效率偏低，因此笔者在HW 7中采取了共享队列的写法。

class Building extends Thread {
    private ArrayList<Elevator> elevators;
	/*=====利用count计数实现均分=====*/
    if (request instanceof PersonRequest) {
        elevators.get(count).addOutRequest((PersonRequest) request);
		count = (count + 1) % num;
    }
}

HW 7:

• 笔者在HW 7中改用了共享队列的调度策略将HW 6中的两层调度器改为一层，所有的请求由Schedule类统一分发到对应的楼座 / 楼层，同时将Schedule类设计为饿汉式的单例模式供其他类通过getInstance()方法调用向内增加等待分发的请求，如：输入类InputThread和电梯类Elevator完成一个阶段的请求后。
• 在调度器类Schedule接到请求后，通过识别第一阶段的任务确定其应被投喂的楼层 / 楼座，并将请求加入到对应楼座的等待队列中，电梯线程在识别到有能搭载的乘客时就会前往迎接。又由于采用synchronized对拿取请求的过程约束，保证了电梯按序拿取，避免竞争。

public class Schedule extends Thread {
    private static final Schedule SCHEDULE = new Schedule();
    
    public static Schedule getInstance() {
        return SCHEDULE;
    }
    
    public void initial() {
        /*=====对调度器各项数据进行初始化=====*/
    }
    
    public synchronized void addRequest(RequestTable requestTable) {
        this.waitQueue.addRequest(requestTable);
        notifyAll();
    }
}

架构模式

HW 5

• 仅有输入线程、电梯线程以及一个总的调度器
• 请求传递：
  • 调度器负责从总的等待队列拿取请求，并将其分发给每个电梯的等待队列，采用生产者-消费者模式。
• 信息交互：
  • 调度器接受InputThread的结束信号并通过setEnd方法结束电梯线程。

HW 6

• 迭代：
  • 实现了要求的增加电梯请求与横向电梯，与HW 5相比增加了一层调度器用于实现“平均分配”的策略。
• 请求传递：
  • Schedule调度器在从总等待队列拿取请求后分派给对应楼座的调度器，楼座调度器根据当前计数值count决定均分给哪一部电梯。
• 信息交互：
  • 由InputThread线程结束开始，逐级对调度器调用setEnd方法，逐级关停线程。

HW 7

• 迭代（大改）：
  • 新建一个类Graph用于维护电梯和能到达的地点组成的50 * 50的图，利用迪杰斯特拉（dijkstra）算法计算点与点之间的最短路径用于请求分解。
  • 新建了一个RequestTable类用于对Request进行一层封装，利用迪杰斯特拉求得的最短路径将当前请求拆分为单楼座/单楼层的独立请求，并对请求计数。
  • 新建了一个RequestCounter类用于计数请求数与已完成的请求数，用于输入结束后结束电梯线程。
  • 将二级调度器改回一级调度器，采用共享队列的调度算法。
• 信息交互：
  • 当输入线程结束后，启动RequestCounter线程，该线程重复循环直到统计到已完成请求数与总请求数相等时调用电梯的setEnd方法以结束电梯线程。

UML协作图：

程序的bug

HW 5:

• 在本次作业的本地测试、系统强测未发现bug。但是在互测中被hack了一刀RTLE，程序没有正常结束，本地尝试复现未果，应该是测评机线程调度的问题，笔者推测在线程安全上没有维护好。

HW 6:

• 本次作业笔者采用了平均分配的调度策略，以牺牲了部分性能分为代价保证了线程的安全，再加上电梯的运行逻辑并无差错，最终本地测试并没有发现bug，强测、互测都没有被hack到，平安度过。

HW 7:

• 本次作业因为受好友蛊惑为了拉满性能分，笔者改用了电梯自由竞争的策略。但是由于是多部电梯竞争抢乘客搭载，会涉及到对于楼座的等待队列的线程安全维护的问题。
• 在一开始完成HW 7的时候，笔者在请求队列内isEnd()和isEmpty()方法中均像实验一写了notifyAll，导致了同一楼座的多部电梯在没有请求到来时本来应该等待，却又因为其他的电梯在调用队列的isEnd和isEmpty方法判断线程是否结束时而被唤醒，如此相互唤醒导致轮询。并且这一轮询bug并不会影响实际的运行时间，导致笔者在用HW 6的强测点测试的时候才发现。笔者在思索后发现，过多的notifyAll反而是画蛇添足。其实当目前的操作并没有改变队列成员状态的时候我们没必要通知其他的等待线程，因此笔者将返回值为null和isEnd()和isEmpty()两个方法内的notifyAll语句删除，得以通过HW 6的强测，解决了该bug。
• 但是非常遗憾，共享队列还是有bug……由于横向电梯具有可达性的特点，笔者在写横向电梯拿取乘客时传入了switchInfo参数，会导致电梯由于可达性返回为null而啥事不干直接进入下一层循环，导致轮询。目前的解决办法笔者想到了两种：
  • 摆烂策略：让电梯“没事走两步”，使横向电梯向一个方向保持运动，能接客就接。虽然电梯一直在运行，但是其实是经历一次循环后进入了move的状态睡了speed * 1000，相当于在这段时间内只进行了一次循环，避免了轮询。而且“没事走两步”有其效率的合理性——投喂的请求在哪一楼座是概率均等的，让电梯保持运动的状态有概率在乘客请求到来时出现在距离更近的地方。因此在bug修复时笔者发现“没事走两步”的代码与之前性能上不相上下，在部分点上甚至远优于前一版。
  • 正经策略：在setMoveType()（设定电梯下一步行动状态的方法）中加入如下判定：当电梯内没有乘客时遍历等待队列，如果没有可供搭载的乘客即wait，如此避免轮询。

/*===============横向电梯轮询bug时拿取请求的逻辑==================*/
public synchronized RequestTable getRowElevatorRequest(ArrayList<RequestTable> 		inElevator,char curBuilding, int capacity,char floorDes, int switchInfo) {
    if (requests.isEmpty()) {
        return null;
    }
    Iterator<RequestTable> iterator = requests.iterator();
    while (iterator.hasNext()) {
   		RequestTable request = iterator.next();  
        RequestTable tmp = request.readFirst();
        int check = (1 << (tmp.getFromBuilding() - 'A')) | (1 << (tmp.getToBuilding() - 'A'));
        /*=====判断条件：可达 + 楼座符合 + 容量没超=====*/
        if (tmp.getFromBuilding() == curBuilding && inElevator.size() < capacity &&
            ((check & switchInfo) == check)) {
                iterator.remove();
                notifyAll();
                return request;
            }
        }
        return null;
    }

发现他人bug的策略

与第一单元表达式作业相比不同的是，第二单元的电梯作业为对简单场景的模拟，侧重点在多线程的安全问题，电梯的运行逻辑非常简单，以至于基本不会出现运行逻辑正确性的问题。本单元的测试应当着重于有关线程安全的调度策略，即重点构造数据针对可能出现的死锁和轮询进行测试。

测试策略以手搓构造数据为主、自动化测评为辅。笔者在这一单元第一次尝试写测评机，由于对Python代码十分不熟悉，因此写得磕磕绊绊。利用自动化测评，成功找到了同组一个数组越界的bug，推测是在增加电梯时对内部队列的初始化问题。

测评机逻辑：

• 数据生成器：
  • 按照给定要求生成请求即可，常量池非常简单，只涉及五个楼座和10层，利用rand函数随机选取即可。
• 正确性检查
  • 逻辑判定：
    • 利用有限状态机判定Arrived, Open, Close, In, Out几种语句的输出顺序；
    • 判断乘客是否准确到达了目的地；
    • 判断电梯线程结束了是否还有乘客的请求没有完成；
    • 判断是否有人没有进电梯但是出去了……（其他电梯惊魂灵异事件）；
  • 时间判定：
    • 利用Python的time函数获取程序的运行时间，再利用管道PIPE结合课程组提供的官方包进行标程运行时间获取，利用给定的时间最大时间判定公式判断是否RTLE。
    • 不足的是不会查询CPU的时间，部分轮询的状态无法检测到。

心得体会

OO真是太好玩辣！

实验的代码太香辣！

• 线程安全角度：
  • 死锁的bug特别好找。
  • 轮询的bug非常难解决，需要对线程间相互协作的关系了解地非常彻底，慢慢跟着流程走一遍才好找bug。后来发现可以利用中间过程加信号量输出的办法，在所有的while(true)循环后面加上一句输出，亲测非常好找到对应的bug。
  • notifyAll没必要加太多，对于现状没有改变的过程没有必要，甚至是不应该使用notifyAll来唤醒其他的线程，以免出现轮询的现象。
• 迭代的角度：
  • 每一次的作业都不能偷工减料，否则要么面临强测和互测被hack，要么因为架构问题在下一次的作业中要加倍补偿回来。
  • 均分策略与共享队列各有千秋，实际上没必要为了一点性能分迭代去追求共享队列，最后强测和互测被hack反而得不偿失。

“故天将降大任于是人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行拂乱其所为，所以动心忍性，曾益其所不能。” ——《孟子》

艰辛的第二单元多线程编程已经过去，不应该停滞不前，向前看吧，努力认真完成后面的作业，以这句话与诸君共勉。