BUAA-OO第二单元总结

前言

三次作业中，我前两次的架构和第三次的架构有明显的区别，其中第三次作业的架构可以在 我的博客 和 讨论区 看到具体的介绍。

下文将着重介绍我在前两次作业中的实现。第三次作业连线程都不要了怎么分析

架构分析

第一次和第二次的架构设计如下：

第三次作业的架构设计如下：

迭代需求分析

实际上，通过对过往几届的需求进行分析，我们不难预测三次作业里，最稳定的部分就是调度器的结构和电梯的运行策略（比如 LOOK 策略），而请求的行为是不确定的，比如双轿厢电梯、电梯的重置请求，但这些都不会和我们稳定的部分产生冲突，可以通过在原有代码上“新增”而非“修改” 的方式解决。

可拓展性

事实上，第一次和第二次架构的可拓展性是一般的，因为无论如何我们的电梯都是在实际运行的，我们总是需要维护电梯的稳定运行状态和请求之间的冲突，需要处理这些请求对电梯运行带来的不确定性。从某种意义上来说，我们维护的不是电梯，而是电梯井道。这种设计面对较为复杂的迭代需求（如双轿厢电梯）往往需要对原有的代码进行删改，一般来说这种可拓展性已经可以算是较差了，但考虑电梯的现实意义勉强可以算是可拓展性一般。

第三次作业（完全影子电梯）的可拓展性我认为是较好的，这主要是考虑到完全影子电梯的输出逻辑是面向答案编程的，可以根据不同的需求调整输出的内容和顺序，只要不是涉及到电梯的运行逻辑的迭代需求（比如电梯横向移动或者重置电梯），都可以通过在输出的时候进行调整来应对。

同步块设置与锁的选择

在三次作业中，我都没有使用 Lock 类或者类似的方法处理同步互斥，而是全程使用 synchronized 关键字，这主要是基于以下几点考虑：

• 输入的数据量小（最多两百组请求），进行细度过高的线程控制代价高、收益小，反而还容易出 bug
• 调度器线程与电梯线程的交互是线性、单向与一一对应的，调度器的工作只有分配与唤醒，锁类的性质（与线程绑定而非线程状态绑定）反而不利于实现高并发
• 在这个架构中，线程间交互的主要工作是互斥而非同步，高级锁（比如可重入锁）的性质完全没用

另外，在三次作业中我都是通过实现 Runnable 接口实现多线程的，这主要是基于几点考虑：一是继承 Thread 类的局限性太大，继承以后就无法再次继承其他类（虽然这次作业没用），其最大的优点只在于可以使用 sleep() 方法；二是使用 sleep() 方法不会释放线程的锁，而我们没有这样的需求；三是 sleep() 方法不利于高并发，不如 wait() 方法。既然没有使用 sleep() 方法的刚需，自然应该避免继承 Thread 类这种“杀敌一千，自损八百”的方法。

第一次作业的分析

不难发现，在第一次作业中，线程互斥和同步的重点在于以下三点：

• 电梯线程从调度器的请求池里获取请求

• 调度器分配请求后适时唤醒进入等待状态的电梯

• 程序退出时，适时唤醒进入等待状态的电梯

对于第一个问题，我采用三个队列、一次交互的方法处理。在调度器里维护一个队列，代表已经分配给某个电梯但是该电梯还未获知的请求，在电梯里维护两个队列，分别代表已经获知但还未进入电梯的请求和已经进入电梯的请求。电梯获取已经分配的请求是主动的，会在特定的时间点主动从调度器里获取。那么电梯和调度器共享的资源就只有调度器里维护的“已经分配给某个电梯但是该电梯还未获知的请求”队列，因此我们维护这个队列的线程安全即可。具体来说就是这样：

// --- Distributor ---
static ArrayList<PersonRequest> distibutedQueries = new ArrayList<>();
synchronized (distibutedQueries) {
    distibutedQueries.add(personRequest);
}
// --- elevator ---
synchronized (distibutedQueries) {
    personRequest = distibutedQueries.remove(0);
}

第二和第三个问题的本质是一样的：如何区分 wait(runTime) 和 wait()，并且避免过早地执行 notify() 方法？

我的解决方法是关注线程状态。java 里线程也是一个对象，也就是 Thread 类的一个实例。通过调取对象的 getStatus() 方法可以获知该线程的状态。这个状态是细化的，区分了 TIMED_WAITING 和 WAITING 状态。通过对状态的判断，我们就可以避免“误唤醒”。

Thread thread = new Thread(elevator);
thread.start();
...
Thread.Status status = thread.getStatus();
if (status.euqals(Thread.Status.WAITING)) elevator.notify();
// 如果电梯在无限期等待就唤醒电梯，否则等待电梯自己来拿

但是，考虑这样的一个问题：如果我们的电梯线程处于将要进入无限期等待的前一刻，而此时调度器获知电梯线程状态是 RUNNING，导致电梯线程无法被唤醒怎么办？

// --- elevator ---
// do something <------------------------------------------- now at
synchronized (this) { wait(); }
// --- Distributor ---
Thread.Status status = thread.getStatus(); // <------------- now at & status = RUNNING !
if (status.euqals(Thread.Status.WAITING)) elevator.notify();

解决方案是我们扩大临界区，我们要求电梯一旦进入无限期等待的前置判断阶段（比如判断请求是否为空）就对自己上锁，不允许调度器获取状态，也就是互斥。

// --- elevator ---
synchronized (this) {
    // do something <------ now at
    wait();
}
// --- Distributor ---
synchronized (this) { // <- have to wait until wait() executed or elevator leaves critical section
    Thread.Status status = thread.getStatus();
    if (status.euqals(Thread.Status.WAITING)) elevator.notify();
}

第二次作业的分析

第二次作业在第一次作业的基础上新增了需要我们自主调度请求和重置电梯的需求。其中重置电梯可以被认为是电梯的一种特殊运行状态，就像移动、上下客和开门一样，唯一的区别在于需要等待 1200 ms。

在重置电梯的时候，需要把电梯里和等待队列里的请求全部放回总的请求池里重新分配。这里有一个实现的细节：如果直接在电梯线程里调用调度器的 addRequest(PersonRequest request) 方法会产生死锁，因为这个方法会直接对请求进行分配，分配方法（影子电梯）在模拟的时候需要获得对应电梯的锁，而这个锁此时又被电梯占用。

解决方法是在电梯里面开一个子类，用来执行把请求放回请求池的这个工作。这个类不占用电梯线程的锁，因此不会产生死锁。在重置的时候，电梯线程先把请求给到这个类，再执行重置请求 wait(1200)。

public class Elevator implements Runnable {
    // ...
    private synchronized void execReset() throws InterruptedException {
        // 参数设置
        if (!inElevator.isEmpty()) {
            Print.open(atFloor, id);
            for (Passenger request : inElevator) {
                /*
                 * 电梯内乘客清空，输出 OUT 信息
                 * 具体的执行是：如果请求的到顶层就是这层，就直接删除（结束请求）
                 * 否则，把请求放回等待队列（inQueue）
                 */
            }
            wait(Constant.timeOpenClose);
            Print.close(atFloor, id);
        }
        SubElevator subElevator = new SubElevator(inQueue);
        inQueue.clear();
        new Thread(subElevator, "sub" + id).start();
        // 开始重置
        wait(Constant.timeReset);
        // 重置结束
    }

    private class SubElevator implements Runnable {
        private ArrayList<Passenger> ps = new ArrayList<>();

        public SubElevator(ArrayList<Passenger> ps) {
            this.ps.addAll(ps);
        }

        @Override
        public void run() {
            for (Passenger p : ps) {
                Distributor.addRequest(p.toPersonRequest());
            }
        }
    }
}

我的调度策略是影子电梯和（有限）量子电梯结合，因此需要在模拟的时候控制实际的电梯线程不会发生状态转换。利用电梯线程在运行（状态转换）的时候需要获取自身的锁的特点，通过在模拟前对六个电梯上锁来保证在模拟结束是电梯的状态不会发生改变。

synchronized (elevator1, elevator2, ..., elevator6) // get best solution & add to its queue

第三次作业的分析

在我第三次作业的实现中，线程的工作是“打印输出信息”，因此同步块的设置就很简单了，只需要遵循“打印输出时不模拟（改变输出信息），模拟时不能打印输出”的原则。如何实现？答案是和第二次作业一样，利用线程在运行的时候需要获取自生的锁这一特点进行处理即可。

// --- Printer ---
@Override
public synchronized void run() {
    while (true) {
        while (!printInfo.isEmpty()) {
            // ...
            wait(time);
            // ...
        }
        if (exit) { break; }
        try { wait(); }
        catch (InterruptedException e) { e.printStackTrace(); }
    }
}
// --- elevator ---
public void addPassanger(Passenger passenger) {
    synchronized (printer) {
        // 更新输出信息
    }
}

完全影子电梯的线程交互仅限于此。

调度器

调度器设计

在我的设计里，调度器与 InputThread 是一体的，也与 MainThread 是一体的。调用过程如下：

class MainClass {
    public static void main(String[] args) {
        for (Request request = elevatorInput.nextRequest(); request != null; request = elevatorInput.nextRequest()) {
            Distributor.addRequest(request);
        }
        Distributor.exit();
    }
}

public class Distributor {
    public static void addRequest(Request request) {
        if (request instanceof PersonRequest) {
            // 处理 PersonRequest 请求
        } else {
            // 处理 Reset 请求
        }
    }
}

处理 PersonRequest 的工作流程如下：收到请求（addRequest() 方法被调用）-> 获得六部（双子）电梯的锁（即暂停电梯运行） -> 获取六部电梯的状态（在第三次作业里则是调用 simulate() 方法）-> 得到性能值（结束时间）-> 衡量性能值并确定分配的电梯 -> 将请求加入调度器里对应的队列等待电梯主动获取（在第三次作业里则是调用双子电梯的 addPerson() 方法更新输出信息）-> 释放锁，让电梯继续运行。

处理 ResetRequest 的工作流程则较为简单，当调度器收到重置请求时直接将 Reset 请求传给电梯 elevators.get(reset.getElevatorId() - 1).reset(reset)。

调度策略

第一次作业没啥调度策略可言的。在后两次作业里，我的调度策略都是影子电梯，通过衡量电梯结束运行的时间来决定应该把请求分配给某个电梯。

影子电梯实际上是可以做到多因素的综合衡量的，比如耗电量实际上也是可以在模拟的时候算出来的，但是我没考虑耗电量的问题，一方面是懒，另一方面是我认为意义不大（我认为耗电量的最主要作用是防止电梯无目的地乱窜，这在第二次作业里就已经通过 RECEIVE 的方法解决了）。往届和同届的实践也证明了运行时间对性能分的影响远大于耗电量。

调度器与线程交互

调度器与线程的交互较为简单：调度器将请求放入指定的队列（buffer），然后等待电梯线程主动获取即可。

双轿厢处理

见 我的博客 和 讨论区。

完全影子电梯通过对输出进行合并处理，在代码里内嵌一个仅包含楼层判断功能的评测机来保证输出合法。

双子电梯得到请求后，对于乘客的请求则根据出发楼层和方向选择 A、B 电梯中的一个分配；对于重置请求则将请求同时传递给两个电梯。然后对于任意一种请求，都需要更新传递给输出线程的输出信息。在这个过程中，双子电梯将会在把请求传递给两台电梯之后，分别运行两个电梯的模拟方法，得到两个电梯的输出信息。在这个过程中，两个电梯都是孤立的，不知道另外一个电梯的状态，因此可能发生电梯冲突的情况，需要将两个电梯的输出信息合并使最后输出在控制台的信息合法。

如何合并输出？

这是完全影子电梯最为与众不同的一点。我们不通过电梯本身完成碰撞的避免，而是通过对输出内容进行检查来完成这个工作，相当于代码里有个评测机。

当我们检测到输出冲突的时候，冲突一定发生在换乘楼层。我们假设换乘楼层是 5 楼，A 先到达，B 后到达，此时检测到输出冲突：

• 假如 A 后续会移动到 4 层，将 B 移动到 5 楼的行为（和后续 B 的所有行为）推迟到 A 移动到 4 层之后，这可以通过调整 B 输出信息的时间戳做到
• 假如 A 后续没有移动的计划，则在 A 最后一次关门之后添加移动到 4 层的行为（即加入这样的一条输出），将 B 移动到 5 楼的行为（和后续 B 的所有行为）推迟到 A 移动到 4 层之后
• 如果没有冲突，就将两者的输出按照时间戳的先后顺序合并

最后，把合并好的输出交给输出线程并释放锁，输出线程会根据时间戳自动计算出输出后需要等待的时间。

bug 与 debug

三次作业没出现线程安全的 bug，开香槟~。

第二次作业有几个挺愚蠢的 bug，比如输出的电梯和乘客编号顺序搞反了。

一个有意义的 bug 是重复开门，通过检查 Print.open() 方法的引用定位到了两个引用处：电梯里的 enter() 方法和 leave() 方法。错误输出出现在乘客进入之前，因此判断是 enter() 方法出错了。经过检查 enter() 方法没有错误，遂检查 enter() 的引用。最后定位到：

diff --git a/Elevator.java b/Elevator.java
index 632f4a9..04f7e74 100644
--- a/Elevator.java
+++ b/Elevator.java
@@ -51,7 +51,7 @@ public class Elevator implements Runnable {
                 status = Constant.Status.OPEN;
                 waitAtTime = System.currentTimeMillis();    
                 wait(Constant.timeOpenClose);
-                enter(preJudge);
+                enter(quantumJudge);
                 Print.close(atFloor, id);
             } else if (preJudge) {
                 if (Constant.timeOpenClose > this.speed) {

确定是传入的参数错误，传错变量了。

第三次作业出现了一个飞天 bug 和把所有请求分配给同一个电梯的 bug。

由于此时采用了完全影子电梯，我直接把 bug 复现了一遍，并且打印出对应的输出列表。

第一个问题的解决如下：经过检查发现电梯没有及时转向（保持上次模拟结束的残留方向），因此在模拟开始时修改电梯运行方向。

第二个问题的解决更简单：打印出调度器模拟得到的性能值，发现所有正在重置的电梯的结束时间都是 LONG_MAX，于是检查 simulate() 方法，发现其中有关重置电梯的代码

if (printer.isReset()) {
    time += Math.max(0, Constant.timeReset - System.currentTimeMillis() + printer.getArriveA());
}

用到了 arriveA，即 A 电梯上次输出 ARRIVE 的时间戳，而在电梯重置前这个数值会被设置为 LONG_MAX（另有他用）。

简单的解决方法就是直接不考虑这个了，把这三行删掉就行了。教训是不要太喜欢复用变量，下次还敢

减少了对多线程的依赖就是好，啥都能复现

心得体会

由于架构的简单和线程调用的线性，我没有遇到任何的线程安全问题，甚至还在第三次作业里基本实现了单线程的电梯。另一方面，在互测的过程中，我也遇到了严重的线程安全无法复现的问题（9 组数据刀 6 个人，一小时拍出的 bug 数据都快要上百组了，楞是刀不中）。从这个层面上来看，线程安全并不是一个我们需要在 OO 课程里提心吊胆的问题，只要保证自己的线程安全问题触发概率较低就能过强测。尽管与课程组目的不符，这就是现阶段线程安全问题在 OO 课程里的实际表现：线程安全问题严重却得不到表现。

但我认为线程安全问题依然是多线程编程里一个体现程序员水平的重点，或者说，没有线程安全问题就没必要下大功夫学习多线程编程了。

解决线程安全问题的方法则因人而异，大部分情况下都离不开对代码的静态分析，说难听点就是瞪眼法。但这种做法是有效而低效的，需要花费程序员大量的时间去思考线程交互的过程，而这一过程又对程序员的能力提出了较高的要求。

我认为避免线程安全问题的最终解决方案是避免多线程，进一步地说，避免多线程的交互内容。如同完全影子电梯的实现一样，尽可能让两个线程的共享资源变少，由此从根本上避免线程安全问题。总不能告诉我就一个共享资源你都搞不定吧

从层次化的角度来说，一个好的调用层次可以极大地减少线程安全问题发生的可能性。比如一个线性、单向的调用链几乎不可能发生死锁。而一个好的调用层次则离不开一个好的架构，通过合理的层次划分和封装，可以减少线程安全问题发生的可能性。

完全影子电梯淦爆课程组！