面向对象设计与构造OO：Unit2-电梯调度

0 前言

第二单元的内容聚集在掌握多线程的基本知识，如线程的创建、线程的互斥与协作、wait/notify机制等，以及掌握生产者-消费者模式，能设计简单的多线程程序。本单元最难的部分，我认为是多线程同步互斥的实现以及 bug 复现调试。

三次迭代后，线程之间的组织关系如下：

本文将分别介绍分析三次迭代作业，每部分包括需求说明、项目结构、架构设计、性能度量、bug 分析等。最后总结心得体会。

1 第五次作业

1.1 需求说明

以某公司的目的选层电梯系统为背景，从标准输入中读入定时投放的乘客请求信息（起点层、终点层、优先级指数），需要将乘客安排给指定的电梯，在规定的时间内将所有乘客送达。

1.2 项目结构

1.2.1 文件树

src
│  Action.java
│  Elevator.java
│  InputHandler.java
│  MainClass.java
│  OutputHandler.java
│  Person.java
│  RequestQueue.java
│  Strategy.java
└─ Utils.java

1.2.2 UML 类图

为方便呈现，仅展示必要的属性和方法。

1.2.3 UML 时序图

1.3 架构设计

第一次迭代，笔者参考了 [hyggge](「BUAA-OO」第二单元:电梯调度 | Hyggge’s Blog) 学长的大部分思路。总的来说，实现了一个最基础的生产者-消费者模型。两大线程：输入线程 InputHandler 和电梯线程 Elevator ，其中电梯线程有 6 个，对应 6 部电梯。一种托盘：请求队列 RequestQueue ，一共 6 个，分别对应每部电梯。输入线程不断获取请求（生产者），并分配给指定的请求队列（托盘），电梯线程不停地从各自的请求队列获取请求（消费者）。

1.3.1 电梯的运行策略

采用现实生活中电梯的运行算法，LOOK 策略，该算法执行流程如下：

如果电梯当前楼层有人需要进/出，则执行开门：

• 先出：所有目标楼层是当前楼层的乘客出电梯；
• 后进：按照优先级从高到低的顺序，将起始楼层是当前楼层且与电梯运行方向一致的乘客接收，直到满员或没有乘客需要进入。特别地，如果进人前电梯是空的，则电梯的运行方向与第一个进入的人一致。

否则，如果电梯非空，电梯按照其目前的运动方向移动一层。

如果电梯是空的：

• 请求队列有请求。如果请求与电梯运动方向相同，电梯移动一层；如果电梯运动方向前方没有请求，电梯掉头。
• 请求队列无请求。如果输入线程已经结束了，电梯线程结束；反之，电梯等待。

为提高代码的可读性，创建一个 Action 枚举类表示 LOOK 策略提供给电梯的下一步动作。

public enum Action {  
    OVER, MOVE, REVERSE, OPEN, WAIT  
}

电梯线程不断地从 Strategy 策略类获取下一步动作，自身不关心请求队列是否有请求或是电梯内部乘客的情况；策略类不关心电梯动作具体如何实现，仅仅根据请求队列和电梯内部的信息给出下一步指令。符合高内聚/低耦合的思想。

@Override  
public void run() {  
    while (true) {  
        Action action = strategy.look();  
        if (action == Action.OVER) {  
            break;  
        } else if (action == Action.MOVE) {  
            move();  
        } else if (action == Action.REVERSE) {  
            dir = (dir.equals("up") ? "down" : "up");  
        } else if (action == Action.WAIT) {  
            synchronized (requestQueue) {  
                try {  
                    requestQueue.wait();  
                } catch (InterruptedException e) {  
                    e.printStackTrace();  
                }  
            }  
        } else if (action == Action.OPEN) {  
            openAndClose();  
        }  
    }  
}

1.3.2 乘客的存储方式

在请求队列 RequestQueue 中，以 HashMap<Integer, HashSet<PersonRequest>> 存储请求（在上个单元吃亏后，这个单元能 Hash 就 Hash！）。该容器 Key 为乘客的起始楼层，Value 为对应的乘客集合。

在电梯线程 Elevator 中，以 HashMap<Integer, HashSet<Person>> 存储乘客。该容器 Key 为乘客的目标楼层，Value 为对应的乘客集合。

这么组织可以很快地找到需要的乘客，不需要花很多时间遍历。

1.3.3 量子电梯

这是一种对运行时间的小优化。普通电梯系统需要在两次移动之间等待 0.4s，在开关门之间等待 0.4s，而这些时间可以用来执行在这期间可能需要进行的计算操作。

以开关门为例，量子电梯的思想是：开门后，记录当前时间。中间经过乘客进出等操作，可能需要花费或长或短的时间。准备关门时，如果当前时间已经过了 0.4s 了，则不再重复等待，如果当前时间不够 0.4s，则等待对应的剩余时间。

long curTime = System.currentTimeMillis();  
if (preTime == -1) {  
    try {  
        sleep(400);  
    } catch (InterruptedException e) {  
        e.printStackTrace();  
    }  
} else if (curTime - preTime < 400) {  
    try {  
        sleep(400 - curTime + preTime);  
    } catch (InterruptedException e) {  
        e.printStackTrace();  
    }  
}

1.3.4 架构的优缺点

优点：LOOK 策略易于实现，且能达到不错的效果。生产者消费者模型简单直接，鉴于本次作业本身不太复杂的原因，数据冒险问题易于解决。本次强测取得了非常不错的成绩（90+）。

缺点：加锁混乱，对线程之间同步互斥问题理解不深刻，为第二次迭代惨败埋下伏笔！

1.4 性能度量

代码规模：

运行时间：本次作业不存在调度，且大部分同学都使用了 LOOK 策略，没有很多可以讨论的空间。针对满足优先级指数，笔者在“从请求队列获取一个请求”的操作中入手，即取出优先级指数最高的那个人。

1.5 bug 分析

强测出现了一个 bug：实现量子电梯时，将初始时间设为 1，使用评测机没能测出来（因为评测机参数设置为互测，互测要求第一个请求在 1s 后出现，而公测第一个请求在 0s 后出现）导致被 hack！

2 第六次作业

2.1 需求说明

在之前的基础上，不再为每个乘客指定电梯，需要自己设计调度算法将其分配给合适的电梯；新增临时调度 sche，收到该请求的电梯需要尽快移动到指定的维修楼层，将所有乘客赶出电梯，进行一段时间的维修后才能继续工作。

2.2 项目结构

2.2.1 文件树

src
│  MainClass.java
│
├─thread
│  │  Dispatcher.java
│  │  InputHandler.java
│  │
│  └─elevator
│          Action.java
│          Elevator.java
│          Person.java
│          Strategy.java
│
├─tray
│      RequestQueue.java
│      WaitQueue.java
│
└─utils
        OutputHandler.java
        Util.java

2.2.2 UML 类图

为方便呈现，仅展示必要的属性和方法。

2.2.3 UML 时序图

2.3 架构设计

本次作业进行了重构。（因为强测因为死锁惨败！）先介绍重构前后保留的架构：

2.3.1 电梯的调度策略

部分博客将这个称为分派策略，为避免歧义，先说明该部分解决的是请求应该分给哪部电梯。

主流的调度策略有四种：

• 随机分配：直接随机数指定调给哪部电梯，缺点是如果出现了 bug，难以复现，毕竟每一次运行分配的结果都不一样；优点是如果本身代码没有很致命的错误，如果出现 bug 了重新交一发说不定能通过（x）
• 均匀分配：先分配给 1 号电梯，然后 2 号，…… 6 号，然后 1 号……如此循环，可以达到非常中庸的效果，而且很容易实现，效果也还可以，性价比超高！
• 影子电梯：在考虑分配的时候，复制一份当前电梯的所有参数（影子），然后模拟运行，计算不同抉择运行时长或耗电量，比较后得到一个局部最优解。优点，这种算法确实大部分情况下能得到最好的结果，缺点是难以实现，很容易引入 bug，而且在第三次迭代加入双轿厢之后局部最优不一定推出全局最优。
• 调参电梯：通过某种方式给每种选择打分，选择分数最高的那个。笔者没有研究过，仅仅在研讨课上听同学分享提到，据说效果还可以？

秉持着宁愿少性能分也不能有一个 bug的思想，笔者毅然决然选择了均匀分配。一句话就实现了：

preElevatorId = preElevatorId == 6 ? 1 : preElevatorId + 1;

2.3.2 临时调度

为了实现临时调度，在 Action 中新增了 SCHE 动作。电梯收到 sche 后，会执行完整的临时调度动作，包括 receive 取消，移动至目标楼层，开门，清空乘客，关门。

private void sche() {  
    // sche begin  
    ScheRequest scheRequest = requestQueue.handelSche();  
    final int scheFloor = util.floor(scheRequest.getToFloor());  
    final int scheSpeed = (int) (Math.round(scheRequest.getSpeed() * 10) * 100);  
    outputHandler.println(String.format(  
        "SCHE-BEGIN-%d", id));  
    preTime = System.currentTimeMillis();  
    // receive cancel  
    ArrayList<PersonRequest> cancelList = requestQueue.cancel();  
    for (PersonRequest personRequest : cancelList) {  
        waitQueue.addRequest(personRequest);  
    }  
    // move  
    //...
    // open door  
    outputHandler.println(String.format(  
        "OPEN-%s-%d", util.floor(floor), id));  
    preTime = System.currentTimeMillis();  
    // people out  
    schePeopleOut();  
    // close door  
    outputHandler.println(  
        String.format("CLOSE-%s-%d", util.floor(floor), id));  
    preTime = System.currentTimeMillis();  
    // sche end  
    requestQueue.scheEnd();  
    outputHandler.println(  
        String.format("SCHE-END-%d", id));  
    waitQueue.scheFinish();  
}

关于 receive 取消，直接将电梯与主请求队列 WaitQueue 相连，把出来的乘客还回去就可以了。

注意到电梯调度的一个细节是：如果电梯正在 sche，就跳过它给下一个分配。这么处理有一个很严重的弊端，考虑这种情景：5 个电梯都在 sche，此时涌入大量请求，那么所有请求都分给了 6 号电梯，导致电梯忙闲不均匀，超时！于是笔者给调度器 Dispatcher 加了一个等待的逻辑，如果在忙就等待一下，设计不当导致出现锁的嵌套，死锁了！在和室友交流思路后，痛心疾首地重构了：

2.3.3 receive 缓冲池

在单位请求队列 RequestQueue 中，设置两个容器，一个是接收了但未 receive 的请求，一个是接收了且 receive 输出了的请求。也就是说，调度器可以无视电梯是否在 sche，直接无脑均匀分配到缓冲池 buffer 中，电梯也不急着输出 RECEIVE ，而是等电梯有空的时候（不在 sche，每两次动作之间）进行一次 receive，将所有缓冲池中的请求放到已 receive 的容器，且输出 RECEIVE。电梯获取运行策略时，Strategy 也只考虑已经 receive 了的容器。这样就完美解决上面提到的情景了。

public Action look() {  
    /* requestQueue has ScheRequest to be handel: */  
    if (requestQueue.isSche()) {  
        return Action.SCHE;  
    }  
    elevator.receive();  
    /* need in or out:  
     * in: only the elevator is not full and person same direction     * out: person in elevator arrive */    if (elevator.needOut() || elevator.needIn()) {  
        return Action.OPEN;  
    }  
    /* if elevator has person:  
     * direction changed when people in out */    if (!elevator.isEmpty()) {  
        return Action.MOVE;  
    }  
    /* if elevator is empty: */  
    /* if no person received: */    if (requestQueue.noReceive()) {  
        /* no more Request */  
        if (requestQueue.isEnd()) {  
            return Action.OVER;  
        } else {  
            return Action.WAIT;  
        }  
    }  
    /* there is person received, go to get him! */  
    if (elevator.requestSameDir()) {  
        return Action.MOVE;  
    } else {  
        return Action.REVERSE;  
    }  
}

在研讨课中，笔者分享了这种思路，老师指出这种 buffer 的思想在实际工程应用中很常用，并提出了另一种思路：如果 requestQueue 发现电梯此时条件不能接收请求，就不断地把调度器送来的请求“扔回去”。

2.3.4 加锁实现同步互斥

第一次迭代中，笔者加锁混乱，导致第二次扩展出现嵌套锁导致了死锁。深入思考后，结合实验代码，总结了一个比较规范的加锁模型：

• 给共享对象的方法加锁：给且只给共享对象的所有方法加锁。共享对象指的是会被多个东西访问其属性的对象（也就是托盘），在我的 hw6 架构中，共享对象是 WaitQueue 和 RequestQueue ，我对它们的所有方法都加上了 synchronized。
• 什么时候需要 notifyAll：notifyAll 只存在于同步块中，也就是只在共享对象的方法中出现。我们知道 notifyAll 的作用是唤醒这个对象，什么时候需要唤醒呢？就是你的状态发生改变后。简单来说，如果共享对象的某个方法只读其属性，不需要 notifyAll ；如果共享对象的某个方法写其属性，需要 notifyAll。
• 在哪里 wait：在共享对象的方法中 wait ，这样保证了 wait 等待的是该共享对象的改变，而 notifyAll 唤醒的是该共享对象的等待，两者对应了，不会出现线程饥饿。例如，调度器 Dispatcher 不停地使用 WaitQueue 的 fetch 方法获取一个请求，那么在 fetch 方法中就设置好 wait ，也即是 fetch 方法是阻塞读取的。
• 规避嵌套锁：嵌套锁容易导致死锁，因此将需要嵌套锁的情况展开为新的生产者-消费者模型，这部分在 hw7 中具体展开。
• 线程的行为：为避免轮询（不停执行 while 循环），需要设置阻塞读取的方法，也即是上面提到的 wait 。除此之外需要设置结束标志，在这里 break。这是每个线程需要有的两部分。

以 Dispatcher 线程为例：

@Override  
public void run() {  
    while (true) {  
        if (waitQueue.isEmpty() && waitQueue.inputIsEnd() && waitQueue.scheEnd()) {  
            for (RequestQueue requestQueue : requestQueues) {  
                requestQueue.over();  
            }  
            util.debug("Dispatcher exiting!");  
            break;        }  
  
        Request request = waitQueue.fetch();  
        if (request == null) {  
            continue;  
        }  
        distribute(request);  
        util.debug("Dispatcher polling");  
    }  
}

WaitQueue 的 fetch 方法：

public synchronized Request fetch() {  
    Request request = null;  
    if (!scheRequestList.isEmpty()) {  
        request = scheRequestList.remove(0);  
    } else if (!personRequestList.isEmpty()) {  
        int maxPriority = 0;  
        int maxIndex = 0;  
        // find max priority request
        request = personRequestList.remove(maxIndex);  
    } else if (!inputIsEnd || scheNum != 0) {  
        // util.debug(String.valueOf(scheNum));  
        try {  
            util.debug("WaitQueue waiting!");  
            wait();  
            util.debug("WaitQueue wake up!");  
        } catch (InterruptedException e) {  
            throw new RuntimeException(e);  
        }  
    }  
    notifyAll();  
    return request;  
}

2.3.5 架构的优缺点

你说的是重构之后的架构吗？好的，这个架构很不错。可扩展性很强，因为笔者此时已经悟出了怎么加锁，基本不会出现死锁问题了。只是线程结束标志容易出问题hhh。

重构后 bug 修复一次过！

2.4 性能度量

代码规模：

运行时间：均匀分配好！其次缓冲池的加入避免了那些高并发的点的 hack。

2.5 bug 分析

最大的 bug 就是上面提到的 5 个电梯 sche 的情景，这里不再赘述。

3 第七次作业

3.1 需求说明

在之前的基础上，新增双轿厢改造 update，即将两个电梯合并到同一个电梯井，一个在上面一个在下面，规定换乘楼层 transferFloor ，两个电梯的共享区域就是换乘楼层，其他楼层不共享，需要避免两个电梯相撞。

3.2 项目结构

3.2.1 文件树

│  MainClass.java
│
├─thread
│  │  Dispatcher.java
│  │  InputHandler.java
│  │
│  └─elevator
│          Action.java
│          Elevator.java
│          Person.java
│          Strategy.java
│
├─tray
│      Communication.java
│      RequestQueue.java
│      Shaft.java
│      WaitQueue.java
│
└─utils
        OutputHandler.java
        Util.java

3.2.2 UML 类图

3.2.3 UML 时序图

3.3 架构设计

3.3.1 双轿厢改造总览

与 sche 一样，新增一个 Action 为 UPDATE ，进行整体操作（就地停下，开门，赶人，等待一段时间，更新信息，关门）。新增共享对象 Shaft 电梯井，存储一个或两个电梯的信息。

3.3.2 改造时电梯之间的通讯

题目要求，在两部电梯都停下后再输出 UPDATE-BEGIN，在两部电梯都完成改造后再输出 UPDATE-END。这涉及了两部电梯之间的通讯，是一个“哲学家进餐问题”，倘若设计不当会出现锁的嵌套导致死锁。

这里笔者设计了一个通讯类 Communication，使用两个 HashMap<UpdateRequest, Integer>，一个是改造请求对应的两部电梯准备好的数量，一个是改造请求对应的两部电梯完成改造的数量。当 Value 到达 2 就可以进行相应的输出操作。这样处理后，两部电梯各自都既是读者也是写者，通讯类就是它们的共享对象。（这么说来这里可以用读写锁 lock 的！但我依然用的是 synchronized）。当一部电梯完成了对应操作但另外一个电梯没有完成，在共享对象中 wait 即可。

3.3.3 电梯井如何防撞

电梯井 Shaft 作为两个电梯的共享对象，存储了共享楼层的信息。当某个电梯位于共享楼层，其标记为“被占用”。如果电梯想进入共享楼层，需要检查是不是“被占用”再行动。

对于已经位于共享楼层的电梯，采取“主动让出”策略。即如果这个电梯做完了事情，准备在 transferFloor 中 WAIT 了，那么用 RELIEVE “接触占用请求“替换之，电梯收到这个请求后就会移出共享楼层。

3.3.4 双轿厢电梯调度

调度器的逻辑需要补充，针对双轿厢电梯：

• 如果乘客的起始楼层在该电梯运行范围内，则放心分配给这个电梯。
• 如果乘客的起始楼层不在该电梯运行范围内，则分配给它的”伙伴电梯“。

电梯运行策略需要修改，针对双轿厢电梯：

• 如果乘客的目标楼层在电梯运行范围内，照常下电梯。
• 如果乘客的目标楼层不在电梯运行范围内，在换乘楼层处下电梯。

于是结束了！均匀分配是很好的宝宝。

3.4 性能度量

代码规模：

运行时间：至少不会因为非死锁或没能结束的原因超时。

3.5 bug 分析

本次强测结果较好（90+）果然不卷性能才是 OO 的真谛（x）。

全随机评测机也能找到一两个 bug。

4 心得体会

电梯月就这么结束了。好神奇好奇妙。

这单元的表现其实比上个单元要好。唯一一次通宵改 bug 也是结果稀烂的第二次迭代。事实证明，选择大于努力，交流借鉴大于闭门造车。

倘若在着手写第二次迭代的时候，先好好研究好了实验代码的加锁策略，或许这段体验会平淡不少。OO 课再一次让我体会到了优秀的设计思路的必要性。

致谢

1. Musel’s blog（感谢提供第一次迭代思路和怎么画时序图）
2. Hyggge’s Blog（感谢提供怎么把时序图画好看bushi）