纸上得来终觉浅，多线程要多测试

博客撰写基本要求：
- 总结分析三次作业中同步块的设置和锁的选择，并分析锁与同步块中处理语句之间的关系
- 总结分析三次作业中的调度器设计，并分析调度器如何与程序中的线程进行交互；总结分析三次作业中的调度策略，并分析自己的调度策略是如何适应时间、电量等多个性能指标的
  - 结合线程协同的架构模式（如流水线架构），分析和总结自己
    - 三次作业架构设计的逐步变化和未来扩展能力画UML类图
    - 画UML协作图(sequence diagram)来展示线程之间的协作关系（别忘记主线程）
    - 识别出三次作业稳定的内容和易变的内容，并加以分析
- 分析自己程序出现过的bug以及自己面对多线程程序的debug方法
- 心得体会。从线程安全和层次化设计两个方面来梳理自己在本单元三次作业中获得的心得体会

注意：在编写完博客并发布在CSDN之后，请在选择要作为作业提交的博客，点击提交。

架构思路总结

本单元作业，我采取了一种专精调度器的路线，调度器知晓程序内几乎所有类、线程的数据，并根据这些数据进行全局的调度，其包括：

为指定请求分派特定的电梯
唤醒、终止特定的电梯线程
指定电梯运行的掉头楼层（抵达该楼层就进行转向）
拆解不可直达请求为局部最优路线并分配电梯

实现这样一个看起来全能全知的调度器就意味着它需要掌握大量数据，否则很难做出合理的调度。所以设计模式上我采取了一种”一家独大“的黑板模式：电梯类与生产者类持续进行数据的实时更新，调度器则根据这些实时数据做出判断。

为了减少死锁的发生，我限制了所有信息的流动方向：仅允许调度器这块黑板被外界访问，调度器只能向黑板上写数据，不能主动申请获取外界信息。单方向的信息传递保证死锁不会在这样的架构中产生。同时我并没有将调度器类转变为线程，而是以数据字段与众多处理方法组成，不同的数据更改会使用调度器类的不同方法，从而进行下一步的调度。

同步块的设置与锁的选择

总结分析三次作业中同步块的设置和锁的选择，并分析锁与同步块中处理语句之间的关系

在三次作业中，我均使用了互斥锁 synchronized 进行代码同步块的保护。原有想重构为效率更高的 ReentrantLock 或可释放指定线程便于高效调度的 LockSupport 或更高端的读写锁 ReentrantReadWriteLock ，但是最后都因为原来架构压得有点死而放弃（

在本轮作业迭代中，我在生产者类、调度器类与电梯类中都出现了锁，但这些锁全部指向调度器类，并且只设置了一个调度器。也就是说，无论发生怎样的线程交互，都只能申请访问一个锁，所以根本不可能出现死锁状况，大家都在等着调度器那一把锁而已。

为了保证线程安全，我将调度器内的所有方法都使用了 synchronized 关键字进行包装，但其他的类除了电梯类 wait() 调度器锁时需要同步外，均未出现同步方法/同步块。

各个类获取锁的目的

生产者类：
- 向调度器中的请求队列中添加新的请求（乘客请求）
- 更新调度器类中的电梯集合（ADD、MAINTAIN）
电梯类：
- 向调度器中写入当前自身状态（楼层、方向、运行与否等）
- 从调度器中读取自身的下一步状态（运动方向/状态、MAINTAIN等）
- 更新调度器中的请求队列（MAINTAIN、换乘下客）

调度器设计与线程交互

总结分析三次作业中的调度器设计，并分析调度器如何与程序中的线程进行交互；总结分析三次作业中的调度策略，并分析自己的调度策略是如何适应时间、电量等多个性能指标的

调度器设计

本单元采用黑板模式进行设计。各个类都将信息交互集中于黑板之上，生产者写入请求，调度器调度请求，电梯获取自身预定的运动细节。由此，黑板便成了整个程序最大的、也是唯一的共享数据类。

三次作业中，调度器都建立在提到的共享数据类 “黑板” 之上。通过生产者和电梯的数据更新，调度器能够掌握全部线程的几乎全部信息，并根据信息设计调度策略。

线程交互与信息传递

由于有且仅有一个共享数据类——黑板，所以程序内的信息流动都与这个数据类相关。

在设计本单元架构时，我考虑的第一个问题实际上是死锁，不知道同学们有没有因为程序死锁而难以推进的时候。为了解决这种困扰，我直接简单粗暴的将所有信息访问的方向固定为单向：生产者、电梯只能更新调度器内数据，或读取调度器产生的信息，正如在前面锁的部分提到的一样。这样做线程交互的难度能有所降低。

其实当时还并不理解这样做的原理是什么，直到第八周理论课上，我才发现自己采取的架构和老师谈到的黑板模式十分相近。具体的信息流动如下：

假装有图.jpg

但实际上，随着工程代码量与类的增多，黑板上记录的东西会越来越复杂，想来看黑板的人也会越来越多，这样必然会导致多线程交互效率下降，同时也会导致黑板与离着黑板最近的调度器类复杂度升高。

调度策略与性能指标

在单元初就被告知今年的性能指标增加了一个用电量的限制。旨在加重调度器在程序设计中的地位，弱化所有电梯饿虎扑食的自由竞争的使用。这更加坚定了我要写一个全局调度器的决心，主要是不觉得写调度器优质规划是一件很酷的事情吗（并不）

再加上原本的传统性能指标：运行时间和等待时间。多数情况下，电梯移动更少的楼层能消耗更少的时间，所以我希望电梯能少跑一层就少跑一层（省电）；乘客能早接一下就早接一下（省时间）。

由此确定了基本的思路为：

能近就近，能省就省

（乘客选用距离最近的电梯，电梯运行中考虑移动最少的楼层数）

决定采用调度器全局调度的方式后，实际上后续迭代的请求分配策略几乎没有发生改变：

准备工作：电梯在移动/休息过程中将自身状态实时写到黑板上
调度启动：生产者向黑板写入请求，告知调度器开始规划
规划思路：为请求分配等待最短时间就能搭上的电梯
- 遍历所有电梯，能否装下这个乘客（过程中会不会超载），若超载则被筛除
- 根据请求楼层/运动方向、电梯楼层/运动方向、电梯掉头时预计抵达的楼层，计算当前电梯接收请求所用的时间
- 将请求分配给所需时间最短者（保证局部最优），并更新电梯掉头预计抵达的楼层（请求终点站与原本预计抵达楼层间的比较），以便电梯掌握运动路线，同时便利下次分配

这种做法，实际上和往年学长们的影子电梯/模拟做法类似，只不过这种做法精确度不如纯模拟，但是实现难度要比复制一遍电梯内容并全局模拟的难度还是要低不少的。这里唯一需要比模拟做法多考虑的点就是电梯超载：

试考虑以下场景：电梯停靠于1层，首先为其分配6个5-11层的请求令电梯满载，在电梯运行到2层时再输入一个3-11层的请求，显然电梯此刻为空，同时显然把7个请求全部分给这台电梯，会超载，或剩下一个请求等这台电梯回来接他。

假装有图.jpg

这样做的效果显然不如第一次就把请求分配给另一台电梯，那么如何表示当前有空间的电梯，在未来某一刻会满载呢？我使用了两个数组代表上行/下行过程中电梯在某个楼层时的人数，然后根据分配的请求进行动态变化，如果某一层达到capacity说明电梯在该层会出现满员状态。具体细节就不展开说了，有了思路后实现还是很轻松的。

在第三次作业中，加入了强制换乘请求，我的处理方式是将所有可联通（换乘）的电梯当作图中的两个连接的节点，然后从请求起始楼层所有可达的电梯出发，求到终止楼层所有可达电梯的多源对多源可达路径（全部可达路径，做法可参考这一篇文章）。再按照换乘次数递增的方式排序路线并拆分每一个请求的第一次换乘段，查看能否分配。

总体来说性能还是蛮不错了，至少有人上来错仨点还能拿84+（

架构分析与协作图

结合线程协同的架构模式（如流水线架构），分析和总结自己

三次作业架构设计的逐步变化和未来扩展能力画UML类图
画UML协作图(sequence diagram)来展示线程之间的协作关系（别忘记主线程）
识别出三次作业稳定的内容和易变的内容，并加以分析

UML 类图

类图中不包含[]标记的是第一次第一次的架构，方括号内数字代表这个字段/方法在第几次作业中加入

通过三次迭代作业的类图可以发现，迭代过程中并没有增添过多的类，处理方式大多为增添函数以满足请求。

在拓展方面上，可以考虑迭代前两年作业中出现过的横向电梯，为此可能需要做出以下调整：

改良电梯间的图结构，使其能支持更复杂的换乘需求
增添新的横向电梯类，优化电梯信息类以兼容两类电梯

UML 协作图

UML 协作图如下，本架构中，调度器 Manager 并不属于运行中的线程，只不过因为方法与交互太多，导致它看起来好像在持续运行一样（）

ProcessUML

代码中稳定/易变的内容

稳定内容：
- 电梯运行逻辑：在三次作业中，电梯都采用了检查方向 - 移动 - 上下客 - 检查方向的循环进行电梯的移动，同时电梯 MAINTAIN 逻辑也只在添加时进行了编写，后续没有改动
- 电梯上下客逻辑：电梯检测每个请求是否标记为自身携带，如果是则进入电梯；检查自身队列，如果目的地是当前楼层则释放；这部分逻辑也没有发生过改变
- 计算最优电梯逻辑：针对每一个请求，每台电梯都会计算接收请求所用时间长短，并分配电梯，这个逻辑也大致没有变化，只在第二次作业中将时间由固定值改为电梯属性
易变内容：
- 请求读入逻辑：在第一次作业中请求只有 PersonRequest 一种，只需要考虑读取乘客请求并更新队列即可；在第二次作业中，增加了 ADD 、 MAINTAIN 请求，需要分类并处理增删电梯逻辑与对应的方法；在第三次作业中， ADD 电梯的逻辑更加复杂，需要额外考虑电梯的可达楼层。每次作业迭代都发生了改变。
- 线程终止逻辑：与请求输入相关的终止逻辑变更也较大。第一次作业中只要输入停止，就一定意味着线程可以处理完当前请求后结束；第二次作业中，必须考虑 MAINTAIN 电梯仍然会在输入结束后释放乘客，而这部分乘客需要回填请求队列，这就产生了新的请求；第三次作业中回填的情况也发生在不可直达请求的换乘过程中：换乘请求下车后仍需要回填请求序列。
- 第三次作业中的请求拆分逻辑：虽然这部分逻辑只在最后一次作业出现，但是我尝试过各种不同的方法，感觉也有必要做一些总结：
  - “电梯井”逻辑：按照电梯ID + 楼层号的方式创建节点，同时创建一个只连接可停靠在该层电梯的换乘大厅， dfs 找出所有可行路线，并排序最少换乘路线；但这个做法时间复杂度过高，处理单个请求都可能 CTLE ，无奈不得不放弃
  - 电梯邻接链表：同学分享的思路，将每一层构建一个节点，各层能停的电梯划分在楼层后，再根据所有能上的电梯继续寻找下一个能上的电梯，直至能够抵达最终目的楼层，回溯路径
  - 多源 - 多源 dfs：最后采用的方法，之前在前面写过了就不水了

bug 记录与多线程 bug 修复

分析自己程序出现过的bug以及自己面对多线程程序的debug方法

bug记录

在第一单元互测中，大家的常用攻击方式都是短时间大量投喂1 - 11之类的请求卡 RTLE。本地测试没出现过被卡的情况，但在互测中还真被刀了。在助教的帮助下我意识到可能的原因是生产者 - 电梯之间处理 notifyAll() 的速度差异。

在我的架构中，对于一个读入的请求会计算其搭乘的电梯 ID ，同时根据 ID 去唤醒指定的电梯，具体来说就是在黑板的一块公共空间写下电梯号，每个电梯按顺序查看是不是自己，再决定会不会醒来。但如果生产者的运转速度过快，有可能导致 A 乘客的 ID 还没有被所有电梯看完， B 乘客的 ID 就覆盖了旧 ID ，有可能A的电梯就醒不过来了。但当时采用了一种不合适的修改思路：使用 sleep() 降低生产者速度。

因为这次修改不够充分，类似的问题出现在第三次作业中，最后的bug修复我把公共的空间改为了每个电梯只查看自己的一小块私有黑板，这样不会频繁更改，才是最好的办法。

debug方法

一定要多 println() .jpg

打印共享数据类的各个所需状态都是debug的一种选择。其中我认为最好用的是根据可能出错的电梯ID和乘客ID，直接输出当时电梯内外的所有状态，大体为：

if (elevator.getId() == specialEid && request.getId() == specialRid) {
    System.println("message you want to see");
}
// 这里的 specialId 都是具体的数字

其次就是多做场景复原，回溯错误发生前的一段时间，看一看错误电梯的行为。通过配合前面的特定print效果还是挺不错的，因为既不会打印出满屏输出，同时也能看到一些关键的信息。

心得体会

心得体会。从线程安全和层次化设计两个方面来梳理自己在本单元三次作业中获得的心得体会

线程安全

这单元的作业中，很多同学都出现了死锁的状况，原因大部分是复杂的线程间信息交互。而且都是在持有锁的同步块内索取其他对象的锁，确实容易出错（）规范信息交互方式、合理使用同步块和锁，注意单个函数逻辑，我认为是处理交互的重中之重。

再比如有佬采用了每个请求的每秒都生成一个线程，我觉得这是对自己架构设计的磨练与宝贵经验；虽然我距离这样把线程用活的程度还有很远，但我觉得这样架构中的信息交互与安全性实在值得我们学习。

其次是保证读写操作不会被其他操作干扰，实际上这个还比较好处理，需要注意一次读写操作的范围，对于单个对象来说可能是一个 return ，一个赋值；而对于容器来说，一次读写就应该对应着一次遍历了，在遍历途中实际上都不应该允许容器被改变。

层次化设计

在考虑线程之间的协作时，为了避免线程本身拥有太多信息导致交互臃肿，我选择了一个单独的电梯信息类对单个电梯所拥有的一系列属性进行包装，并且把这个信息类放在黑板中。电梯线程类本身不具有太多信息，查询、更新状态都需要去黑板查看，这样保证了线程交互的简便性。

其余的层次化主要体现在调度器类这个黑板上，黑板拥有不同的字段，这些字段是对应的下一级的类，它们分别代表着黑板上的不同种类信息。总的来说层次化设计在本次作业架构中不是很明显。

结语

oo最让人难熬的电梯月到这里就算告一段落了，我认为这个单元学到的线程协作知识很有价值，不仅在学习过程中了解到了更多的设计模式，同时也知晓了线程/进程的概念、线程间信息传递的安全问题，是十分宝贵的经验。还有两个单元，不要懈怠就好了。

能看到最后的我觉得大概率是助教giegie吧，在这我想对每一位助教说声谢谢，在电梯月的摸爬滚打少了你们的帮助真的会寸步难行。接下来两个单元也要救救我哦（逃