oo_u2总结

第二单元终于结束力，电梯月结束了！！！

第一次作业

薛定谔的电梯

第一次的电梯总是轻松愉快的，乘客指定了需要某部电梯来接送，这意味着我们不需要调度电梯，只需要关注电梯的运行。当然，今年较往年增加了乘客优先级的概念，最后性能分的计算中平均等待时间进化为加权平均等待时间。

整体思路

alt text

架构设计

整体电梯系统依然采用生产者-消费者模型。主输入线程InputThread作为生产者，负责“生成”乘客请求，这里更准确地来说是“接收”我们输入的乘客请求，但是从电梯系统来看，乘客都是主输入线程产生的；电梯线程ElevatorThread作为消费者，负责“清理”乘客请求，也就是将乘客送到目的地；分配器线程DispatchThread作为盘子，接收主输入线程的乘客，同时可供电梯线程获取。不过与传统的生产者-消费者模型相比，我们需要分配器主动分配乘客请求给电梯线程，而不是等待电梯线程来获取。

这是考虑到电梯线程的逻辑复杂。一般的消费者线程只需要简单处理即可继续获取，但对于电梯线程而言，什么时候意味着处理完毕可以继续获取乘客请求？难道是等电梯运送完目前得到的所有乘客请求吗？这无疑会导致电梯错过携带的机会。一个本可以由此次电梯运行携带的请求因为电梯没有主动获取请求而无法得到执行的机会，将导致电梯的效率低下

`InputThread`

电梯的主输入进程，负责调用课程组的API读取请求，如果请求为null说明用户输入已经结束了，可以那么主输入线程也可以结束了

`Dispatcher 1.0`

如上面分析的DispatchThread，如果我们第一次作业采取普适的思路，那么所有需要被分配的请求都来源于我们的输入，一旦主输入线程结束了，我们的分配线程理所应当地也可以结束了，即主输入线程在退出前设置分配线程结束

`Dispatcher 2.0`

由于乘客上下电梯是不需要消耗电量的，为此我专门实现了一个优化—当电梯可以开门时，将所有乘客都驱逐下电梯，然后电梯按照乘客的权重来接乘客（此处乘客权重可以参考后面PLOOK算法的权重）

如何保证电梯不会驱逐所有乘客后直接关门离开？在我的实现思路中，电梯开门并驱逐乘客后需要释放锁并等待400ms再接乘客，这400ms就是重新接收被驱逐乘客的关键，利用这段时间可以将乘客重新加入电梯的请求表中，然后电梯判断调用getInPerson方法后可以重新接收进电梯中
为什么放入主请求表而不是电梯的请求表？这是为了兼容后续的迭代情况，遍览前几届hw6中大都有驱逐所有乘客的某种要求。而因为在第一次作业中，乘客已经被指定了电梯，所以就算放回主请求表也会被发回此电梯的请求表。既然可以为后续作业做打算，何乐而不为

不过值得注意的是，因为电梯也会向主请求表中放入乘客请求，所以DispatchThread需要同时接收到InputThread和ElevatorThread的请求，不能像1.0版本一样，InputThread结束时就结束，那么如何保证在所有电梯运行结束前，DispatchThread仍然保持活跃状态呢

思路一：当所有电梯都处于接收不到乘客请求而等待时，分配线程结束并为所有电梯设置结束标志。尝试了之后发现CTLE了，因为分配线程会一直反复查看电梯线程的状态。那为分配线程新设置一个等待条件不就好了？我认为如果专门为DispatchThread新设置一个等待条件，可能会使得InputThread分配给它的请求迟迟无法分给电梯（其等待在新的等待条件上），有点捡了芝麻丢了西瓜的味道，所以舍弃该思路
思路二：为每个从InputThread获取的乘客请求计数（加一），当且仅当该乘客达到了目标楼层，才视为请求结束了，计数器减一。这个思路最绝妙的地方在于DispatchThread和ElevatorThread状态完全分开了，控制DispatchThread结束的条件只在其本身的属性，只是现在DispatchThread等待的条件变得复杂了，需要同时判断主线程是否输入结束以及全局计数器是否为0，为了避免线程被虚假唤醒（这会导致线程返回null，造成不可挽回的局面），所以等待条件我使用while循环包裹，IDEA帮我优化成了do...while结构

`ElevatorThread`

虽然本次作业电梯线程叫Elevator，但是为了突出其线程对象的属性，我还是决定将其称呼为ElevatorThread，电梯线程被实现为一个状态机具有如下状态

{MOVE, OPEN, REVERSE, END, WAIT}

于此同时，ElevatorThread存储了当前电梯的所有属性，ElevatorThread访问修改电梯的属性来达成状态机状态转移的过程。
ElevatorThread的职责在于完成DispatchThread分派给它的所有乘客请求，所以在DispatchThread结束后ElevatorThread才可以结束

需要注意下面几个动作的实现逻辑
MOVE

电梯运行动作，由于电梯的方向是一个状态量，所以每次移动应该需要加上direction。MOVE动作执行时实际需要等待400ms，这段时间可以被量子电梯利用（详见量子电梯）

OPEN

电梯开关门动作
这里有一个值得优化的点————开门等，电梯先开门放出乘客后再等待400ms，这样出电梯的乘客可以腾位置给需要进入的乘客，而且因为电梯等待时释放了锁，所以电梯醒后可以接收这400ms内接收的乘客，无需反复开门
由于LOOK算法的要求，电梯同一时间只能接与电梯运行方向相同的乘客。这意味着如果电梯在某楼层释放了所有乘客、且此楼层刚好有乘客需要去往反方向。电梯却需要关门后转向并重新开门接乘客，这无疑浪费了一次开关门的机会，所以可以在电梯开门后再判断一次能否转向，省去一次开关门的时间

WAIT

- 此方法是大坑中的大坑，由于接收请求与电梯执行是不连贯的，所以如果电梯接收到`WAIT`方法后立即去睡觉，可能导致电梯错过被唤醒的时机，而陷入永远的沉睡。当然我在本次作业并未注意到这一点，也导致在`hw6`定位了很久这个`bug`

`Person`

为原有的PersonRequest新建一个类，这是考虑到我的Person类需要记录更多的东西，例如乘客的方向、乘客到达的时间（用于计算权重）等等。而且在第二版本后，乘客中途下电梯是需要改变fromFloor/direction属性的，而课程组的API并未提供此功能

运行策略—PLOOK

首先写了往届学长大力推荐的LOOK算法。此算法的优势在于尽量减少电梯的掉头次数而尽可能地携带乘客。
但是这个策略有一点点小小的缺陷，如果电梯后方突然来了一个优先级特别高的请求可能无法得到及时的处理。
我构想过一个思路：电梯遇到后方有优先级特别高的乘客时，直接掉头去接优先级特别高的乘客，但是电梯将保留与电梯运行方向不一致的乘客。那从这以后，电梯内的乘客方向可以与电梯方向相反，感觉退化为了ALS策略，这至少是我不能接受的。就算不会导致混乱，我们也不能频繁掉头去接高请求的乘客，这样丧失了LOOK策略本身减少掉头的优势。为此我决定只略加修改LOOK策略在空梯时的运行逻辑

原本LOOK在当前电梯为空时，会先检查前方是否还有乘客请求，如果有的话就一定不转向
我修改其运行逻辑为将当前电梯前方的所有人与后方的所有人做一个评分，如果后方的人的得分显著高于前方的人，那么电梯直接掉头去接后方的人

那么这个得分从哪里来呢？我们可以考虑一个乘客

优先级越高，理所应当权重越高
等待时间越长，权重也应该越高
距离目前电梯越近，权重越高
相同情况下，反方向的乘客权重低于正方向的乘客，接反方向的乘客违背了LOOK算法的减少掉头思想，需要给一个惩罚系数

$Score = \frac{pri\times(curTime - arriveTime + \gamma)}{\theta\times abs(curFlr - fromFlr) + turnCost} \\ turnCost = \begin{cases} \alpha\times pri, &\text{ 如果乘客在电梯后方}\\ 0， &\text{ 如果乘客在电梯前方} \end{cases}$

$\gamma$是一个极小的常数，用来保证目前等待时间不为0
$\alpha$是参数，用于确定掉头惩罚系数
$\theta$是参数，用于确定等待时间对于权重的影响

由前方所有乘客与后方所有乘客的得分来决定电梯是否掉头，且必须要后方乘客分数远大于前方乘客分数，这样既可以保证能够处理后方高要求的乘客，又不会频繁掉头

$\frac{Score_{behind}}{Score_{ahead}} > \beta$

运行策略—量子电梯

从我对量子电梯的理解，量子电梯的优点主要有两点

考虑了程序运行的时间，将其计入等待时间（好吧，这点可以忽略不计）
等待过程释放锁，苏醒后可以进行二次决策

头一回听“量子电梯”这个概念大概就是一头雾水，但实际上量子电梯是利用了时间戳来榨取剩余时间，资本电梯（）
举个栗子，我们对于MOVE这个动作进行分析，从最一般的角度来看，两个楼层之间电梯需要走400ms，所以想当然让电梯在输出前先睡400ms就好了

if (advice == Advice.MOVE) {
    Thread.sleep(400);// 先睡400ms
    ... //do something
    TimableOutput.println("ARRIVE-" ...);
}

但是这样其实多消耗了do something的时间以及上一次动作到本次接收建议之间的时间（但是说实话，这点时间省了和没省一样…），不过下面的理解很重要，对于实现量子电梯第二个优势很有帮助
电梯在两个楼层间移动需要400ms，可以理解为我们输出的ARRIVE语句距离最近的ARRIVE/CLOSE语句至少相隔400ms，那么我们完全可以记录重要输出语句的时间戳，利用时间戳的差值更准确表示等待的时间
...//do something
long now = System.currentMillis();
if (now - actStamp < 400) {
Thread.sleep(400 - (now - actStamp));
}
actStamp = TimableOutput.println("ARRIVE-..."); //重新更新时间戳

总所周知，Thread.sleep方法休眠是不会释放锁的，这意味着我们电梯在执行某些动作的间隔中，请求表中不能放入额外的请求，这可能会导致我们错失某些方便携带的请求，例如

// all received by elevator1
[1.0] 1-PRI-10-FROM-F1-TO-F7
[1.6] 2-PRI-10-FROM-F1-TO-F6

1号电梯在1.0时接收到了1号乘客请求，于是它直接在F1开门了，400ms后1号乘客进入了。也就是在1.4时电梯准备向F2出发了。但是1.6时二号乘客也到了，如果在一般情况下，我们需要等到电梯1.8到达F2时才能接收到2号乘客的请求，此时已经无法回头了，于是我们只能先送了1号乘客然后跑下来送2号乘客
有没有办法让1号电梯等一等2号乘客呢？有的兄弟有的。正如我们之前所说的，电梯不再使用sleep方法睡眠，而是采用wait方法，这样等待的过程中电梯可以释放锁。等到电梯睡醒了之后我们不再直接输出ARRIVE，而是再去获取一次建议

最后，关于电梯睡在哪的问题，可是使用ReentrantLock配套的Condition，我们单独开一个Condition让电梯睡在上面

Lock lock = new ReentrantLock();
Condition waitQueue = lock.newCondition(); //WAIT队列
Condition actQueue = lock.newCondition(); //动作时等待队列

这样我们只需要超时等待在actQueue上即可，而一般等待请求输入唤醒时我们等待在waitQueue即可，优雅！
时序分析

bug分析

第一次作业其实是有bug的，但是强测和互测都没有测出来

WAIT建议与执行动作不是原子化的

第二次作业

神秘的影子电梯

alt text

整体思路

`Schedule`

此类如之前的Person功能一致，用于拓展原有的ScheRequest的若干功能。但是实现完Schedule后，相应的问题接踵而至。因为第一次作业请求表们等等都采用的是容纳Person，而我们当然不可以让Schedule继承于Person，那么需要给请求表单独开一个容纳Schedule的队列吗？

我的选择是不，因为这样主请求表将变得极为复杂，判空条件需要两个队列（Person、Schedule）同时为空。而且将请求派发出来也会面临先分发那个队列的问题、等待的条件将越来越复杂。
这并不是我希望看到的，所以我决定重构第一次作业的代码。让Person与Schedule同时继承于PassengerRequest类，主请求表只负责分发PassengerRequest，而判断其去处放在了DispatchThread中
这更加符合各个线程的功能，DispatchThread就应该负责判断请求的类型并放入合适的电梯中，而InputThread只需要负责接收我们传递的请求即可

`Elevator`

本次作业最重要的类，意为电梯实体。原先ElevatorThread内部的属性几乎全部转移到Elevator中，我认为一个线程对象只应该负责最基本的线程运行，对于其内部属性的管理则应该使用另一个对象，至少我认为这样的重构是更符合各司其职这个准则的

reqTable：容纳电梯请求表对象
inside：容纳电梯内部属性

同时注意到`MainReqTable`仍然放在`ElevatorThread`中，这是因为考虑到主请求表不应该作为电梯的一个属性，我认为这个主请求表仅仅是用于电梯状态的转移

原先用于保护电梯请求表的锁可以外移到Elevator中，即保证对于请求表的修改仍然是互斥进行的、不存在两个线程同时访问请求表（指ElevatorThread和DispatchThread），而对于获取电梯内部属性inside，我并未使用锁保护。因为电梯的内部属性同一时刻还是只有ELevatorThread这一个线程进行修改/读取，自然不需要上锁

电梯此时的状态（Schedule）
电梯此时的乘客状态（获取不需要锁）
电梯所在楼层（获取不需锁）
电梯速度（获取不需要锁）
电梯方向（获取不需要锁）
上次行动的时间戳（不需要获取）

锁机制的改变（这一点在hw5之后，hw6之前，可以从git提交看出）

Elevator类包含ReentrantLock以及两个Condition对象：waitQueue (用于等待新请求或结束信号) 和actQueue (用于 move, open/close, scheduleEnd 等动作的定时等待)
ElevatorThread在每次getAdvice和action调用前后都会获取和释放这个lock，保证了决策和执行的原子性（也是为了模拟的准确性）
Dispatcher(通过ShadowStrategy) 在分配前也会获取所有电梯的lock

`Inside`

电梯内部属性类，最开始并没有打算封装此类，而是想要将所有电梯的内部属性直接放在Elevator中。但是考虑到迭代场景，未来电梯的内部属性可能持续增加，可能导致Elevator类内部复杂度过高，所以额外封装了一个Inside属性。

新增SCHE动作

电梯新增Schedule属性指示是否处于临时调度状态
SCHE_START

以下操作对于请求表是一个原子操作，不允许被打断（防止影子电梯获取不到精确值）
获取请求表中的ScheduleRequest，并设置为Schedule
设置电梯的运行速度
清空电梯请求表中的所有请求
此时判断是否需要进行一次开门放出乘客（.upd 还有加入刚好可以到达指定楼层的乘客）
释放锁之后再将所有请求加入主请求队列，否则可能会有死锁
- （想一下似乎没有问题，但是为了保险，大概是因为Dispatch线程虽然会获得MainReqTable和reqTable的锁，但是不会同一时间去请求两把锁，而是轮流请求）

SCHE_END

进行开门放人、关门操作（人都删除，待会再加回主请求表）
清除电梯的Schedule（同时记得清除ScheRequest加入主请求是的count++）
将buffer内容写回请求表（需要补输出RECEIVE）

策略类加入SCHE_START、SCHE_END两个状态，同时需要接收Schedule作为参数
判断逻辑最先加入Schedule != null的判断，调度开始后一定不能受到其他影响
然后判断调度是否要开始了

调度策略—影子电梯

影子电梯调度策略，即通过模拟电梯运行得到的各个参数来对每部电梯进行评分，分配给电梯评分高的电梯。
正如学长所说，电梯在模拟时是需要时间的，与此同时ElevatorThread也是在同步运行的，此时ElevatorThread会对Elevator内部的属性进行更改。此时我们发现，电梯内部的属性不再是只有ElevatorThread一个线程进行访问与修改，所以现在inside属性也需要上锁了。为了简单，因为调度器需要获取电梯的请求表和inside属性，所以我们直接将Elevator的锁给调度器。

预检查

获取所有Elevator的锁
优先将请求分配给将要SCHE的电梯，也即电梯请求表中有Schedule的电梯
如果有多个可以搭载的电梯，优先分配给目的楼层刚好可以是该乘客的电梯（因为此时调度的电梯还可以负责送这个人），否则随机

深克隆

在预检查前，我们就已经获得所有Elevator的锁

for (Lock lock : locks) {
    lock.lock();
}

接下来为了保证影子电梯分配不会影响原有的电梯，我们将“被暂停”的电梯复制一份，即深克隆。为此专门给Elevator以及其所有的从属属性实现clone方法

正在`SCHE`的电梯

由于本次互测的时间限制特别长，所以我身边几乎所有人都没有实现向正在进行SCHE的电梯分发请求，但是有时这部电梯可能刚好是最适合的电梯。抱着既然已经实现影子电梯就需要将其实现准确的态度，我考虑了正在SCHE的电梯，并为每一部电梯专门设置buffer缓冲区。在电梯结束SCHE动作后会将缓冲区的乘客重新加入请求表中

实现这个思路也是十分简单的，检测到电梯的schedule属性不为空时，那么将乘客加到电梯的缓冲区而不是直接加到请求表中

执行动作

因为我在实现ElevatorThread时全部采用了wait方法进行等待，所以无法继承ElevatorThread并重写方法以实现简单的模拟，为此我重新开了Shadow电梯专门用于模拟时电梯的运行。
startTime = currentMillis：影子电梯开始时间
time = currentMills：影子电梯目前的时间，所有操作对这个事件更改
actStamp：上一次动作的时间戳，因为这个时间戳大概率小于影子电梯开始的时间

MOVE动作，记录时间戳，等待方法改为时间累加方法
OPEN动作，记录时间戳，
SCHE_END动作，记录时间戳，等待方法改为时间累加方法

影子电梯的初始化

由于我们运行电梯被抢夺锁的时机是不确定的，就会存在即使我们将所有电梯运行方法上锁，电梯还是可能在运行过程中被获取锁，这是因为我们消耗等待时间的方法是wait方法。我并不打算改为不释放锁的sleep方法，不打算向影子电梯模拟妥协。所以为了保证影子电梯结果的最最最准确性，我决定对影子电梯第一个动作进行特殊处理（因为这个动作有可能是现实电梯未能完成的动作）

一般情况下电梯未执行任何操作时获取锁，此时进入影子电梯直接获取建议即可
在电梯进行操作等待时间内获取锁进行模拟，此时需要分情况
- 电梯在schdeuldEnd开关门间隔释放锁，并进入影子电梯模拟。此时需要继续执行scheduleEnd操作，只是不需要记录scheduleEnd开门时的时间戳（这个时间戳被记录在现实电梯中，这样可以更准确地模拟时间）
- 电梯在OpenAndClose时开关门间隔进入电梯。同理此时需要继续执行OpenAndClose操作，同样不需要重新记录电梯开门地时间戳（同上）
统一在人员加入电梯前进行一次获取建议，进行初始化操作，因为加入人之后建议可能发生变化，但我们此时需要的是准确的模拟前真实电梯接收的最后一条建议

影子电梯的评价得分

首先我们考虑了每部电梯送完所有乘客需要的时间，这对应着课程组要求中t_final程序结束时间
其次我们考虑电梯完成所有操作所消耗的电量，这对应着课程组要求中w电梯消耗的电量
最后为了准确考虑wt加权平均等待时间，我是这样认为的：计算某一个电梯单独的平均等待时间误差是特别大的，所以我们需要考虑所有的电梯（整个电梯系统）。此时将某部电梯的wt我们不妨这样计算，计算此部电梯加入乘客后的wt和其他所有电梯不加入乘客运行的wt综合起来

因为考虑了wt，所以每一部电梯都需要运行两次，一次是不加入乘客的模拟运行、一次是加入乘客的模拟运行，等到所有12次模拟结束后我们再一同计算电梯的得分
尽量不要使用过多线程模拟，充分利用线程池，由于线程池的大小开得太大，导致强测时有部分点因为开不出线程而挂掉了，但是好在助教和老师善解人意。

时许分析

alt text

bug分析

本次作业强测出了一个神奇bug，因为影子电梯模拟开的线程过多导致OS无法开出线程了

这个问题实际上通过缩小线程池的容量就可以解决，同时感谢学长和老师的不杀之恩

自己使用测评机也测出了bug

还是hw5没发现的问题，获取WAIT建议与执行操作不是原子操作
影子电梯模拟忘记删人导致模拟停不下来

第三次作业

写的死锁最多的一次作业

alt text

整体思路

本次作业要求实现双轿厢电梯，最难的部分就是双轿厢的“同步”与“互斥”了

所谓同步，指双轿厢在初始接受UPDATE请求后，有且只能输出一条语句。如果两个轿厢的运行线程是分开的，那么必然需要先到的线程等后到的线程，并由后到的线程输出
所谓互斥，指双轿厢不能同时位于换乘层，而只能互斥地到达。意味着两个线程必须抢夺换乘资源，并在离开换乘层时释放资源，唤醒等待的线程

无论是哪个操作都必须要实现两个线程间的通信，为此新开一个类TransPlatform(~~转换桌~~)，需要组合成双轿厢的两部电梯拥有同一个TransPlatform实例，使用TransPlatform进行传递消息

电梯同步与互斥都需要等待，那电梯等待在什么地方呢？是返回Advice.WAIT使其等待在自己的请求表上，还是在TransPlatform中新开一个等待队列呢。当时主要考虑到影子电梯需要使用电梯的锁（~~万恶的影子电梯~~），我希望电梯等待时可以释放锁，如果采用第二种方案，则会出现电梯拿着自己锁同时睡在TransPlatform上，所以我采用了第一种方案

电梯的同步

怎么让两部电梯只输出一次语句呢，正如上面所言，我选择将输出语句放在TransPlatform中，而且只允许后到的线程输出。判断是否是后到的线程只需要维护一个被互斥访问的计数器即可

lock.lock();
try {
    if (hasBeginNum == 1) {
        TimableOutput.println("UPDATE-BEGIN-" + ids.get(0) + "-" + ids.get(1));
        quitAllReq(elevator.getType());
    } else if (hasBeginNum == 0) {
        savePersons(elevator);
    }
    hasBeginNum++;
} finally {
    lock.unlock();
}

hasBeginNum初始为0，只有当目前有一个线程访问过这个方法（也即开始UPDATE），才会输出，这样就保证了两部电梯只输出一次UPDATE-BEGIN
至于savePersons和quitAllReq方法主要是用于同步两个电梯清空请求表的操作，因为指导书规定，只有当UPDATE-BEGIN输出后，才能视为所有RECEIVE到的请求被取消，所以先开始UPDATE的电梯需要将自己的请求表清空并放在TransPlatform中，等待后到的电梯一起重新放回主请求表中
欸？不是说好要等待吗，等待的语句去哪里了？这里我考虑到UPDATE-BEGIN与UPDATE-END之间还有若干语句，这些语句也会影响两个电梯线程的进度快慢，所以我选择在输出UPDATE-END时将两个线程同步

为了能让先到的线程乖乖睡觉，我为每个电梯增加了一个属性waitForTrans，意为是否因为双轿厢原因而等待（~~好草率的翻译~~），先到的线程将自己的这个属性设置为True，后到的线程将先到的线程的此属性设置为False，并唤醒它。

// isWaitForTrans
lock.lock();
try {
    return waitForTrans;
} finally {
    lock.unlock;
}

//setWaitForTrans
lock.lock();
try {
    waitForTrans = wait;
    if (!wait) {
        waitQueue.signalAll();
        // 此时不需要等待了，需要立即唤醒
    }
} finally {
    lock.unlock();
}

//需要唤醒另一个线程
lock.lock();
try {
    if (hasEndNum == 1) {
        if (isNotShadow) {
            endStamp = TimableOutput.println("UPDATE-END-" + ids.get(0) + "-" + ids.get(1));
        }
        hasEndNum++;
        //other.setWaitForTrans(false); //唤醒另一个线程
        return true;
    } else {
        hasEndNum++;
        elevator.setWaitForTrans(true);
        return false;
    }
} finally {
    lock.unlock();
}

这里埋下过一个惊天隐患（），其实按理来说应该是hw6埋下的。我在hw6实现了影子电梯，为了保障影子电梯的准确性，电梯更改自己属性时需要获取自己的锁，所以电梯在进行UPDATE操作时也是先获取了自己的锁。那么如果按照被注释的实现方案，电梯在唤醒另一个电梯时（持有该电梯的锁）同时持有自己的锁，典型的ABA问题直接死锁了
为此我只能将唤醒操作延至电梯释放自己的锁后，而且为了避免一部电梯同时获取两把锁的困境，后续我将大部分和TransPlatform有关的操作放在运行策略类中，并将获取建议操作与电梯运行操作分开（又是一个隐患）

已知电梯获取建议为Advice.WAIT时会睡在waitQueue上，电梯接收到其他请求会被唤醒。考虑如下场景，电梯接收到Advice.WAIT但还没睡时，新的请求恰好加入进来。因为电梯还没睡，所以新的请求唤醒了个寂寞。但是等电梯真的睡了之后，再也没有办法唤醒它了，简称电梯睡死了

在hw6中，我直接将获取建议与电梯运行绑定在了一起，防止了这种错误的发生

但是通过上上面的分析，电梯必须避免在使用TransPlatform时获取到自己的锁（因为有些操作需要获取另一部电梯的锁），最终我决定使用有条件的等待方案，将获取建议操作不上锁

elevator.getLock().lock();
try {
    if (!elevator.isEnd() &&
        !elevator.hasScheduleRequest() &&
        elevator.isWaitPassengerEmpty() &&
        elevator.getPassengers().isEmpty()) {
        
        elevator.isWaiting();
    }
} finally {
    elevator.getLock().unlock();
}

核心思路是在睡觉前再判断一次是否真的需要睡觉（），好处是获取建议和电梯运行终于可以分开了；坏处是但凡少考虑一种情况你的电梯还得睡死（尤其是hw7条件更加复杂，我就以各种奇葩的方式睡死，有些真的难以发现。而且就算使用测评机测出了问题，采用多线程复现也很困难，最困难的一次48进程跑了3000次居然都没有触发）

最后附上一张逆天睡觉图

elevator.getLock().lock();
try {
    if ((!elevator.isEnd() && // 电梯线程未结束
        !elevator.hasUpdateRequest() && // 电梯未接收到UPDATE请求
        !elevator.isUpdating() && //电梯仍然在完成执行UPDATE
        !elevator.hasScheduleRequest() && // 电梯未接收到SCHE请求
        elevator.isWaitPassengerEmpty() && // 电梯侯乘表为空
        elevator.getPassengers().isEmpty()) || // 电梯内无乘客
        elevator.isWaitForTrans()) { // 电梯因双轿厢交互而等待
        
        elevator.isWaiting();
    }
} finally {
    elevator.getLock().unlock();
}

曾经各种离谱bug包括但不限于电梯想要去换乘层却被判定为需要等待新的乘客请求而睡死、电梯等待UPDATE-END通知却被判定为需要等待新的乘客请求而睡死、电梯接收到SCHE请求但是选择睡觉、电梯接收到UPDATE请求但是依然选择睡觉
悄咪咪地说，~~你让电梯每200ms醒一次可以解决所有问题，而且是不会触发轮询的~~，不过我们当然不可以这样做，对吧，你也想写出完美的多线程电梯吧

UPDATED：今天上课突然想到，为什么不再获取一次建议？？？

elevator.getLock().lock();
try {
    Advice toDo = strategy.getAdvice();
    if (toDo == Advice.WAIT) {
        elevator.isWaiting();
    }
} finally {
    elevator.getLock().unlock();
}

这里需要注意的是，由于我说过我们的运行策略类可能会获取双轿厢另一部电梯的锁，所以你的策略类最好可以有一个屏蔽的开关，毕竟我们如果只判断是否是Advice.WAIT，实际上是不需要那么多的判断的（例如是否是否达到换乘层、离开换乘层），例如getAdvice(true)/getAdvice(false)

电梯的互斥

其实可以将换乘层理解为一种临界资源，两个线程轮流使用这种临界资源。所以互斥的逻辑也就水到渠成了。电梯将要访问换乘层时先给TransPlatform发送一个信号，表示想要获取换乘资源，如果获取成功则移动否则等待；同理当电梯目前不处于换乘层时应立即释放换乘资源，并唤醒可能因此等待的电梯

// 请求换乘资源
lock.lock();
try {
    if (type == -1 || type == elevator.getType()) {
        type = elevator.getType();
        return true;
    } else {
        elevator.setWaitForTrans(true);
        return false;
    }
} finally {
    lock.unlock();
}

// 释放换乘资源
lock.lock();
try {
    if (type == -1 || type != elevator.getType()) {
        return false;
    } else {
        type = -1;
        int type = elevator.getType();
        Elevator other = elevators.get(1 - type);
        other.setWaitForTrans(false);// 这里需要唤醒
        return true;
    }
} finally {
    lock.unlock();
}

不过这里唯一需要注意的是，释放换乘资源操作请求了另一部电梯的锁，所以一不留神就可能触发死锁，为此我的解决方案是仅仅在获取建议时调用这些方法。例如原本电梯需要返回Advice.MOVE时我们需要额外增加一下判断，如果即将到达的楼层是换乘层则需要先请求换乘资源，未请求到直接返回Advice.WAIT

电梯调度

电梯调度的算法我还是采用了影子电梯调度。不过对于双轿厢电梯，我将它们组成了一个组合，共同调度，而对于一个乘客请求，我将其分为两部分分别加入两个轿厢的运行中，以求最大限度的模拟

不过对于影子电梯的换乘等待时间极难模拟，想通过时间戳模拟但是失败了，情况稍微有些复杂，索性对于需要等待的情况全部增加400ms
由于影子电梯拿锁的时机是不确定的，所以会存在waitForTrans还未触发先被抢了锁，然后就出现了两部电梯waitForTrans同时为True，或者一部电梯将要唤醒另一部电梯，然后进入影子模拟后，需要被唤醒电梯实际未被唤醒。对此我决定在进入影子电梯模拟时先对waitForTrans进行初始化，只有当某部电梯恰好处于换乘层时，其姊妹电梯的waitForTrans才被设置为True，否则两部电梯的waitForTrans都为False

时序分析

alt text

bug分析

本次作业强测和互测都没有出现bug
首先线下自己用测评机测出了很多bug

例如上面列出的死锁问题
电梯再获取锁之后getAdvice导致了隐藏的死锁

值得一提的是，互测房间里其余所有人都有死锁bug。但是有些人触发的概率太低，导致我一直没刀中他们。甚至有一个本地1/2概率出锅的点，交了16发都没有刀到那个哥们，有点可惜，希望以后互测能增加评测的次数

稳定与易变

就我的三次迭代而言，最稳定的部分就是InputThread主输入线程和电梯的运行策略，其余所有都是易于改变的部分
电梯的调度策略，会根据不同的请求类型进行微调
电梯的请求表，也会根据不同的请求类型进行微调
电梯的内部属性，根据不同的要求进行增添属性

心得体会

就线程安全而言，其实在第一次作业中感受并不是很深。不仅是因为第一次作业要求简单，而且往届学长已经总结出了一套优雅的实现方案。实在不行也可以通过synchronized块一次全锁住了。但是随着作业迭代的深入，各个线程的要求更加复杂，尤其再装载了影子电梯这种重量大的调度策略，hw6的bug虽然少但是我本人debug极度痛苦，清明都在debug。但是随着对线程安全理解的深入，很多原来比较模糊的概念逐渐清晰。就像第三次作业出现了无数线程安全的bug，但是在hw6的拷打后竟也觉得没那么困难了

多线程debug关键在于复现困难，个人采用多线程测评机+print大法。因为我遇到的每个bug都是比较难复现的（痛苦），总之有一个好的测评机不仅是hack他人绝佳的工具，更是debug的好工具了吧

电梯再见，~~再也不想见到电梯了~~

oo_u2总结

第一次作业

整体思路

架构设计

InputThread

Dispatcher 1.0

Dispatcher 2.0

ElevatorThread

Person

运行策略—PLOOK

运行策略—量子电梯

时序分析

bug分析

第二次作业

整体思路

Schedule

Elevator

Inside

新增SCHE动作

调度策略—影子电梯

预检查

深克隆

正在SCHE的电梯

执行动作

影子电梯的初始化

影子电梯的评价得分

时许分析

bug分析

第三次作业

整体思路

电梯的同步

电梯的互斥

电梯调度

时序分析

bug分析

稳定与易变

心得体会

`InputThread`

`Dispatcher 1.0`

`Dispatcher 2.0`

`ElevatorThread`

`Person`

`Schedule`

`Elevator`

`Inside`

正在`SCHE`的电梯