第二单元总结

一、同步设计

​ 三次作业中均只使用了synchronized修饰词来进行线程的同步，并且主要针对读写冲突进行保护。在三次作业中均使用OutputQueue类对输出信息进行封装，保证其线程安全。对于使用最多的共享类RequestQueue，其读写方法getOneRequest、addRequest、removeRequest以及对其属性inputEnd、taskCounter的读写方法都使用synchronized修饰词进行修饰。由于完成了对RequestQueue的同步处理，各级调度器和电梯都可以直接调用RequestQueue类对象的方法而不会产生线程安全问题。

二、调度设计

1.第五次作业调度设计

​ 本次作业中每个座只有一部电梯，Scheduler类仅是为后续作业的扩展做准备，在本次作业中仅是将请求直接分配给唯一的电梯，并无实质性作用，自然也无调度策略可言。

​ 电梯对请求的调度采用look算法，即同方向上有可捎带请求则沿当前方向运行，否则调转方向。本次作业中电梯的调度设计在后续作业中继续沿用。

2.第六次作业调度设计

​ 本次作业开始使用二级调度，即主调度器Scheduler为一级调度器，楼层调度器FloorScheduler和座调度器BuildingScheduler为二级调度器。

​ 当输入类InputThread输入请求时，增加电梯请求会直接执行，增加移动请求则会加入与Scheduler共享的RequestQueue类对象schQueue。这事实上是一个一对一的生产者消费者模型，InputThread是生产者，Scheduler是消费者，schQueue是容器。

​ Scheduler取出schQueue中的请求，根据竖直移动和水平移动的类别分配给对应的座调度器和楼层调度器，表现为将请求添加到座/楼调度器的请求列表requestQueue中。

​ FloorScheduler和BuildingScheduler取出它们的requestQueue请求，根据所管辖电梯的是否空闲、是否捎带、空位数等信息分配给各电梯，表现为将移动请求添加到电梯的候乘列表offList中。

3.第七次作业调度设计

​ 本次作业以第六次作业为基础进行修改。

​ 每个移动请求都加入了当前位置、目标位置、是否已到底中转层（arriveSwitchFloor）属性，当移动请求进入Scheduler时，根据当前位置和最终目标位置设置当前目标位置，使其满足第六次作业移动请求的数据限制。当此乘客移动到当前目标位置后，再次进入Scheduler管理的schQueue，结束移动或重复上述过程。由于本次作业数据的限制，任何请求都至多在三次调度中结束。

​ 具体而言，设置当前目标位置的策略如下：

​ 1）若当前位置与最终目标位置仅楼层不同或仅楼座不同，则将当前目标位置设置为最终目标位置；

​ 2）否则，判断arriveSwitchFloor是否为0；

​ 3）若为0，寻找中转楼层，将当前目标位置设置为当前楼座下的中转楼层，并将arriveSwitchFloor置1；

​ 4）若为1，将当前目标位置设置为最终目标位置楼座下的当前层。

​ 对于上述策略步骤3中寻找中转楼层的算法如下：

​ 1）根据每个楼座所有电梯运行时间的调和平均数估计楼座性能（电梯数越多、单个电梯运行时间越短，则楼座性能越高）；

​ 2）在起始楼层和目标楼层间寻找可达楼层，且满足在高性能楼座运行尽可能多的楼层数；

​ 3）若未找到可达楼层，则寻找最少运行楼层数的可达楼层，运行楼层数相同时，满足在高性能楼座运行尽可能多的楼层数。由于一层有一个可达任意座的横向电梯，因此不存在在此步骤中找不到可达楼层的情况。

​ 当分段请求下达到楼层/楼座调度器时，根据以下策略分配给下辖电梯：

​ 1）若有空电梯，直接将该请求分配给空电梯；

​ 2）否则，若有可捎带且有空位电梯，分配该请求给该电梯；

​ 3）否则，根据电梯剩余容量、等候乘客数、运行速度等参数计算电梯的性能值，分配该请求给性能值最高的电梯。

​ 特殊地，本次作业中添加任务计数器taskCounter作为进程结束的依据。当总调度器分配一个阶段性移动请求时，taskCounter自加1；当电梯完成一个阶段性移动请求时，taskCounter自减1。当输入结束、请求序列为空且任务计数器值为0时，所有线程都会结束运行，进程结束。

三、架构模式

1.架构展示

​ 由于第五次作业和第六次作业是第七次作业的子集，故在此仅展示第七次作业的架构以及三次作业的迭代关系。

第七次作业UML类图（省略构造方法、Getter、Setter）：

第五次作业架构：

​ 仅有图中(Building)Scheduler、(Vertical)Elevator、RequestQueue、(Move)Request、InputThread、OutputQueue、OutputLine类，满足本次作业的基本要求。

第六次作业架构：

​ 在第五次作业的基础上添加了Scheduler、FloorScheduler、HorizontalElevator类，满足横向运输需求，且二级调度架构基本形成，但总调度器Scheduler的调度逻辑非常简单，仅需根据运输类型（横向/纵向）将运输请求分配给楼层/楼座调度器即可。

第七次作业架构：

​ 基本沿用第六次作业架构，仅对Scheduler调度逻辑进行修改，具体调度策略见上文“调度设计”部分。

2.协作关系

第七次作业UML协作图：

四、bug分析

1.自己的bug

​ 第五次作业和第六次作业中都未发现bug。

​ 但是在第七次作业中由于测试数据构造不足，出现了致命bug，导致强测得分极低：楼层调度器在给横向电梯分配请求时没有判断开门信息，从而导致横向电梯接收到无法运输的请求而在楼座中无限循环运行。

​ 发现此问题后，解决办法比较简单，仅需在楼层调度器分配请求处加入判断语句即可。

2.别人的bug

​ 主要结合自己遇到的bug和理论课学习中提到的可能出现的bug构造数据进行测试，同时构造逻辑较复杂的请求集合以及同一时间输入大量请求的数据以测试代码的逻辑正确性和线程安全性。

五、心得体会

1.线程安全

​ 这一单元我仅利用了synchronized修饰词对涉及到读写冲突的方法上锁，且并未发现线程安全问题。

​ 由于课程组对CPU使用时间的限制，我使用wait-notifyAll方式进行程序编写，避免了死锁和轮询的发生。

​ 在第六次作业完成时，发现了程序无法结束的问题，即忙等问题。经过排查，发现由于过早对第七次作业进行预判且没有配套完整的迭代措施（如增加taskCounter作为程序结束标志之一），导致总调度器线程和电梯线程之间没有反馈路径，从而总调度器无法知道请求是否以及全部完成。经过删除一些多余代码段后，程序结束逻辑保持与第五次作业相同，问题得以解除。

​ 本单元的不足之处在于，上锁的方式较为单一，显得比较笨重和呆板；而且没有使用其他锁的类型，导致对相关问题的理解不够深入，仅停留在了解决基本问题的层面。这样做虽然对于任务驱动的工程而言并无大碍，但对于个人的思维拓展和能力提升是不利的。

2.层次化设计

​ 汲取了第一单元的经验，在完成本单元作业时，我有意为后续的迭代拓展预留了空间，有效避免了重构。

​ 在第六次作业时，已经初步形成二级调度的架构，总调度器-楼层/楼座调度器-电梯的层次化设计让移动请求更有条理地被分配到合适的位置。每个层次只需各司其职，接收来自上一级的请求，并反馈本级的必要信息，既有利于维护线程安全和功能正确，也加强了代码的扩展性和可读性。

​ 在第七次作业时，二级调度的层次化设计的优势更加突出，一个复杂的请求在经过一次从上到下的调度和运输后就会变简单，而被重新置于顶层再次调度。在经过有限次（不超过三次）层次化调度后，该请求会被简化为同楼座的运输，回归了第五次作业的基本功能。这种类似于递归下降的总调度策略也是一种层次化的设计，与线程的层次化设计相结合，让代码的维护与扩展更易展开。