OO-Unit2-多线程电梯 - 面向对象设计与构造 | CircleCoder = 碼農書架 = 仰望星空

# 回顾

随着最后一次 Bug 修复的完成，我的第二单元 “含恨九泉” 了。三次作业的强测都不理想，第二次大胆尝试了影子电梯的策略，性能确实可观，但却给我增添了许多 bug，一直延续到第三次迭代，可谓是赔了时间又折分。

我也深刻反思了一下自己，因为忙其他的事情，这个单元分配给 OO 的时间确实少了许多。尤其是写完通过中测后，没有再构造数据进行测试，只在第二次迭代互测时写了个弱弱的评测机。

虽然这单元的分数很差，但是仍旧学到了很多，比如对于锁、同步块的理解和应用。下个单元继续努力，争取金身

# 同步块和锁

我采用的全部是同步代码块的方式，没有同步方法。

一是考虑到同步方法的范围太大，会使性能下降；
二是同步代码块可以使用自定义的显式锁，便于我们在一个类中定义多个锁，直观地掌握什么锁去做什么事情

关于锁的使用，其实就是为了实现两个功能：

保护共享资源
本次作业中的最主要的共享资源就是分配器 Dispatcher 中的总线程池，也就是生产者 - 消费者模型中的托盘，这是必须要进行加锁的。其次是每个电梯的候乘表，从逻辑上来讲其实不需要加锁保护，因为不存在两个线程同时消费的情况，而且托盘大小也没有限制，所以生产和消费是完全可以并发的。但是生产和消费都会对托盘（候乘表，我的是 ArrayList 类型）进行遍历和修改，不加锁会导致迭代器错误。
等待唤醒机制
拿到锁的线程 wait 后，也只能被其他拿到同一把锁的线程 notify 。掌握这个原理后便可以实现让权等待了，防止轮询超时

# 调度器设计

每当线程池接收到输入的新请求时，便将该请求发往调度器。调度器根据调度策略选择合适的电梯，将该请求发往对应电梯的候乘表中，之后的事情便是电梯线程的了。

第二次迭代用平均分配策略速通中测后，看到助教在讨论区发布的往年帖 ” 影子电梯 “ 后，便决定大胆尝试。往年大神的 6 把锁套娃实在看的我发怵，我实现了一个简易版的。

深拷贝每部电梯。
虽说是 “深”，但也没那么 “深”，深入到候乘表和厢内乘客队列就行，乘客对象采用浅拷贝即可，因为影子电梯不会对乘客作出修改。
对于候乘表和厢内乘客队列的深拷贝需要加锁，避免迭代器错误
重写 Elevator 中的方法，将所有锁和输出语句删掉；设置时间变量，将所有 sleep 改为时间的累加即可
调用 run 方法，当候乘表和乘客队列全部为空时结束，返回总时间

这样调度器收到新请求时，会通过影子电梯策略，将请求发至各个影子电梯模拟运行，选择返回时间最小的，以达到局部最优的效果。

在第二、三次迭代中添加了临时调度和双轿厢改造事件，电梯会将原有乘客踢出去。而被踢出去的乘客如果仍然选择这部电梯的话，或许就不是最优解了。于是会将其直接踢回调度器重新分配

# 架构设计

# 第一次迭代

第一次迭代乘客直接指定电梯，所以没有设计调度器，直接从输入发往各电梯的候乘表

运行策略采用的 LOOK 算法：当前运行方向上有请求就继续前进，否则转向。这次迭代的核心也是该策略的实现

# 第二次迭代

本次迭代架构上变化较大

首先是设计了调度器，实现了调度与运行分离。并且采用了影子电梯策略进行调度

在电梯运行上，本次迭代新增了 SCHE 临时调度这一请求：

我的实现方案是，当电梯收到请求后，立刻停止运行，开始临时调度。到达指定楼层后，开门放出乘客。已到达目标楼层的乘客自然输出 OUT-S 即可，而未到达目标楼层的则会被打回调度器，进行重新分配
乘客的重新分配给我们带来了新的问题，那就是何时结束线程？
- 在第一次迭代中，输入结束后便向各个电梯线程发送 over 信号，每部电梯收到信号并且候乘表和乘客列表均无人后结束线程
- 在第二次迭代中，输入线程和电梯线程之间多了调度器线程，而且电梯线程和调度器线程之间的交互是双向的，故 setOver 不能再向第一次迭代那样了。为此，我在工具类中添加了静态成员变量 sum ，用于记录还未完成的请求数，当输入线程接收到乘客或临时调度时， sum++ ；当乘客到达目标楼层或临时调度结束时， sum-- 。这样，当输入线程结束且 sum 为 0 时，便可向各个线程发送 over 信号了

# 第三次迭代

这次的整体架构和第二次迭代基本没有区别

因为真实电梯和影子电梯都要对 Stratge 进行传参，第二次迭代时传入的是成员变量，这次迭代会导致参数过多而扣风格分，所以改为直接传入电梯对象。为了统一，真实电梯和影子电梯必须实现同一个接口，即新增的 AncestorElevator 类

本次迭代新增的请求是双轿厢改造，具体细节后面再说

# UML 协作图

# 双轿厢电梯

# 大致思路

有以下两种思路：

两个电梯改造完后合并为一个特殊的电梯类进行管理，便于防止相撞
两个电梯改造完后仍然是两个独立的线程，只是要避免相撞

考虑到两个电梯在各自的区域是独立运行的，而且同步和不想撞也不难实现，本人采用了第二种思路

# 如何改造？

这个很简单，为电梯类增加成员变量 middleFloor 、 bottomFloor 、 topFloor ，前者代表双轿厢电梯的中间共有楼层，若未进行改造则设为 null ；后两者代表电梯的可运行范围

由于运行范围的改变， Strategy 也要随之改变。当电梯到达 middleFloor 后，应判断此时电梯内是否有人。若有人，且运行方向超出电梯活动范围，则返回换乘动作：将乘客打回调度器

	// 判断是否有乘客进入电梯，或者到达目标楼层
	if (canOpen(nowFloor, requestTable, num, passengerTable, direction)) {
	return Advice.OPEN;
	}
	String middleFloor = elevator.getMiddleFloor();
	String bottomFloor = elevator.getBottomFloor();
	String topFloor = elevator.getTopFloor();
	// 如果电梯里有人
	if (num != 0) {
	if (nowFloor.equals(middleFloor)) {
	if (nowFloor.equals(topFloor) && direction == -1) {
	return Advice.MOVE;
	} else if (nowFloor.equals(bottomFloor) && direction == 1) {
	return Advice.MOVE;
	} else {
	return Advice.TRANSFER;
	}
	}
	return Advice.MOVE;
	}
	// 如果电梯里没有人
	else {
	//.....
	}

# 同步开始与结束

这是双轿厢改造的第一个难点

两部电梯收到调度器发送的改造请求后，会立刻将电梯内的乘客打回，而我们必须要等两个电梯都完成这项工作后，才能输出 UPDATE-BEGIN 。这里我们就需要用锁来实现同步了：

在工具类中设置 6 个静态变量，作为计数器，分别对应 6 部电梯。当电梯完成改造前的准备后，计数器便加 1。

若两个电梯的计数器之和不为 2，说明当前电梯进度领先，需要等待另一部电梯；
否则说明当前电梯落后，另一部早已准备好，唤醒它即可。注意等待和唤醒的锁要一致！

然后由 A 电梯输出 UPDATE-BEGIN

	public void updateBegin() {
	if (this.num != 0) {
	// 开门打回电梯内的乘客
	}
	this.received = 0;
	// 准备工作完成，计数器自增
	Tools.addMap(this.elevatorID, 1);
	int elevatorAId = this.updateRequest.getElevatorAId();
	int elevatorBId = this.updateRequest.getElevatorBId();
	// 用同一把锁，默认是 A 的锁
	Object updateLock = Tools.getLockMap(elevatorAId);
	synchronized (updateLock) {
	if (Tools.getMap(elevatorAId) + Tools.getMap(elevatorBId) != 2) {
	try {
	updateLock.wait();
	} catch (InterruptedException e) {
	throw new RuntimeException(e);
	}
	} else {
	updateLock.notifyAll();
	}
	}
	this.isUpdateBegin = true;
	if (this.elevatorID == elevatorAId) {
	TimableOutput.println(String.format("UPDATE-BEGIN-%d-%d", elevatorAId, elevatorBId));
	}
	}

巧妙之处就在于等待唤醒的这个 if-else ，分别对应了进度领先的电梯和进度落后的电梯

同理，同步结束也是这样实现，不再赘述

# 避免相撞

这是双轿厢改造的第二个难点

注意到本次迭代特意修改了 RECEIVED 约束，允许在中间共享楼层的电梯随意移动，这也算是一种提示吧。我的实现如下：

首先，双轿厢电梯不得在中间楼层停留等待。这需要修改 Strategy ，当候乘表和乘客队列都空时，原本电梯是要等待的，现在需要判断是否在中间楼层；如果在，则需要移动到相邻楼层，避免占用。

	if (num == 0 && requestTable.isEmpty()) {
	if (requestTable.isOver()) {
	return Advice.OVER; // 如果结束，电梯线程结束
	} else if (nowFloor.equals(middleFloor)) {
	if (nowFloor.equals(topFloor) && direction == -1) {
	return Advice.MOVE;
	} else if (nowFloor.equals(bottomFloor) && direction == 1) {
	return Advice.MOVE;
	} else {
	return Advice.REVERSE;
	}
	} else {
	return Advice.WAIT; // 电梯线程等待
	}
	}

但还是可能会出现碰撞，这个时候我们便要效仿同步开始与结束的策略了

在电梯移动的方法里，当我们计算出电梯将要到达的楼层后，若发现其伙伴电梯正在那一层（即中间共享楼层），那么

我们需要等待；当伙伴电梯移动后再去唤醒。注意等待和唤醒的锁要一致！

public void move() {
    // 移动0.4s
    // 计算将要到达的楼层
    int floor = Tools.mapping(this.nowFloor) + this.direction;
    if (this.brotherShareLock != null) {
        synchronized (this.brotherShareLock) {
            this.nowFloor = Tools.mapping(floor);
            if (this.brotherElevator.getNowFloor().equals(this.nowFloor)) {
                try {
                    this.brotherShareLock.wait();
                    sleep(1);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            } else {
                this.brotherShareLock.notifyAll();
            }
            TimableOutput.println(String.format("ARRIVE-%s-%d",
                    this.nowFloor, this.elevatorID));
        }
    } else {
        this.nowFloor = Tools.mapping(floor);
        TimableOutput.println(String.format("ARRIVE-%s-%d", this.nowFloor, this.elevatorID));
    }
}

巧妙之处也是在于 if-else ，分别对应了需要等待的电梯和执行唤醒的电梯（后者并不一定需要让位，这里是为了简便，在 else 里统一唤醒）

注意到，等待的电梯在 wait() 后，又休眠了 1s ，这是为了应对评测而设计的缓冲区。否则可能会输出两个电梯同一时间 ARRIVE ，但如果让位电梯的输出在后的话，评测机会判定为相撞

# 调度策略修改

双轿厢的改造使得电梯的运行区域缩减，这需要修改乘客请求的调度策略。

在遍历拷贝影子电梯时

若乘客的起始楼层不在此电梯范围内，则直接 continue
若乘客的起始楼层恰好是此电梯的中间楼层，则同样 continue ，负责电梯接进来马上打回，浪费时间，有死循环风险

影子电梯的时间计算也受到了换乘的影响，对于换乘的乘客我们总不能让他再进一次影子电梯，这种套娃实在太麻烦了；但如果忽略的话，那计算时间会比真实时间少很多。

所以对于有换乘乘客的影子电梯，我给它们的时间增加 3s ，以模拟换乘后的时间

# BUG 分析

# 我的 bug

第一次迭代出了点小 bug，策略类考虑了电梯限员，但电梯执行时忘记了，好在扣分不多

第二次迭代就很惨了，影子电梯没写好，导致其中出现了死循环，直接 CTLE

第三次迭代更惨：

真实电梯在换 h 乘前没有把到达目标楼层的乘客送到，而是直接打回。导致影子电梯接收到起始层和目标层相同的乘客。而我的电梯没有考虑这种不合法的请求，所以又死循环了（寄
UPDATE END 未设置缓冲区，导致同时输出但顺序不对的情况，评测机会判错

# 多线程 debug 方法

最大的困难就是 bug 难复现，尤其是概率死锁的 bug 导致的 RTLE ，我只会用瞪眼法检查

而 CTLE 就简单多了，要么是死循环，要么是没 wait 导致轮询超时。在每个 while 里 sout 就好了

对于输出合法性的检查，人力判断还是太费脑了，于是我采用实时模拟，检验状态转移是否合法的方式编写了 checker ，节省了大量精力