第二单元博客作业

第五次作业

UML类图:

架构思路：

本次作业只有固定的五台纵向电梯，处理的请求之间相互独立，故处理起来较为简单。线程的设计整体基于生产者消费者模式，输入通过一个线程暂存到buffer请求队列中，五台电梯各开一个线程（在主线程中就可以设置好），模拟电梯的自主运行，同时分别维护自己的候乘队列和电梯内人员队列，再构造一个调度器线程用于将buffer中的请求分配到对应楼座的电梯中。

在这种架构下，输入线程和调度器线程共享请求队列buffer，调度器线程和每个电梯线程共享一个候乘队列。为了方便，我封装了一个基本线程安全的请求队列类，来实现这几个共享队列，除了在电梯类中进行一些诸如遍历队列的较复杂操作时需要对队列类实例加锁以保证一系列操作的原子性，其他加取请求的地方只需调用队列类中线程安全的方法即可，无需加锁。

为了避免轮询，使用wait+notifyAll机制。当尝试取队列中的请求时，若队列为空，且未收到输入终止信号，即可在该队列实例上wait，解除占用等待新的请求加入，相应地，加取请求又或是写入输入终止信号这种能更新队列实例状态的写操作需要及时执行notifyAll，唤醒等待进程，让其处理新的请求或是终止。

关于电梯的运行策略，我采用指导书上标准的ALS策略，为了实现方便修改了少许逻辑。

UML时序图：

可以看到，输入线程与调度线程依赖共享队列buffer传递消息，调度线程与电梯线程依赖共享的候乘队列传递消息；大部分情况下，各个线程的运行相对独立，各自完成所负责的功能。

第六次作业

UML类图：

架构思路：

本次作业相比上次作业增加了横向运输的请求以及动态增加电梯的请求，乍一看很复杂，但稍微分析一下就会发现由于横向请求是纯粹的，实际上与纵向请求可以完全独立分开处理。

仿照纵向电梯的实现容易实现一个横向电梯类负责处理横向运输请求，对于输入的请求，由调度器根据其类型分配到对应的电梯即可，这样看来相比前一次作业仅仅是电梯数变多罢了。

另外，由于需要动态增加电梯，不像上一次作业中一座楼仅有一部电梯情况简单直接在主线程中开启即可，需要建立新的数据管理结构。对此我的做法是对楼座和楼层分别建模，每个楼座实例管理对应的纵向电梯列表，每个楼层实例管理对应的横向电梯列表，在这两个类中分别实现增加电梯的方法，这样当调度器检测到增加电梯的请求时就可以通过调用对应实例的此方法完成请求。

对于单个电梯的运行策略，纵向电梯沿用了之前的ALS策略，横向电梯也类似地实现了指导书上的捎带策略。对于在同一楼座或同一楼层有多个电梯正在运行的情况，调度器通过调用楼座（层）实例的dispatch方法将请求传递给该实例，在dispatch方法中将请求分配至“最空闲”的电梯的候乘队列中。这里的“最空闲”我是通过电梯实例中候乘队列人数加上电梯内人数之和来衡量的，和越小表示越空闲，虽然这种衡量方式看起来比较简单粗暴，但是的确可以最大限度地避免某些电梯“摸鱼”的情况出现，故整体性能还是可以接受的。

UML时序图：

由于第六次作业相比第五次作业主要复杂在数据管理结构上，消息的协作本质基本没有大的变化，故不再给出时序图。

第七次作业

UML类图：

架构思路：

这次作业增加了电梯速度、容量、横向电梯可开关门信息的自定义，同时乘客请求不一定是纯粹的纵向或横向运输能解决的，需要进行换乘。

对于速度容量以及开关门信息这些电梯属性，直接在电梯类中修改即可，较为简单(不过需要注意横向电梯运行时，在不能开门的楼座不能停下更新载人状态)；不过换乘的实现就较为复杂了，为了充分利用之前的架构，我选择在我看来比较自然的动态换乘方法：调度器接收请求后根据请求所处位置与请求最终目标位置为请求选择一个合适的暂时目标位置，并将其投入相应的楼座（层），由某部电梯送达暂时目标位置，之后电梯判断送达的请求位置是否与请求的最终目标位置重合，若是，申报请求处理结束，否则，将请求重新投回，可以证明，每个请求至多通过三部电梯运送必能到达目的地。

在不是很考虑性能问题的前提下，难点在于请求如何再次投入，以及由于再次投入带来的无法简单根据输入线程取到空行设置结束符的问题（因为即使外界不再输入请求，由于换乘需要，电梯会反馈新的请求），我的解决方案是首先将之前输入线程与调度器线程共享的缓冲区buffer包装成单例模式，这样在电梯线程中重投请求就变得十分简单；判断输入结束方面，我利用单例模式建立了一个请求计数器来记录已完成但未查收的请求个数，初始计数为0，代表已完成0个请求，计数器类中有两个重要方法，一个是release方法，是计数加一（同时需要notifyAll），代表完成一个请求，由电梯线程将请求送至最终目标时调用；一个是acquire方法，若计数大于零令计数减一，计数为零则wait，代表查收一个完成的请求，由输入线程在输入结束后调用等同于输入乘客请求个数的次数，表示查收所有输入的请求。这样通过让输入线程在没有查收到所有请求已完成时等待，最后再设置输入结束标志就可以解决所有问题。

UML时序图：

大致的消息传递结构不变，区别有如下几点：

Buffer利用单例模式作为全局变量，增加从电梯线程向Buffer的请求传递（由于换乘）；

设置RequestCounter类管理输入线程的终止，电梯线程完成请求时调用release向其传递消息，输入线程记录外部请求数量，调用require查收完所有请求再setEnd。

锁的选择以及调度器的设计：

在本单元我仅仅使用了synchronized关键字来实现互斥锁的功能，并未使用一些更复杂的自定义锁（主要是怕出错），但是已经足够了。在我看来，最优的加锁方式是包装线程安全类，对常用方法本身加锁，这样可以避免外部调用时繁杂的加锁问题，不过需要注意，除非线程安全类的方法设计的十分完美，当出现例如外部的循环中调用方法时，为了保证整体操作的原子性还是需要整体加锁的。关于锁什么对象，比较简单且符合直觉的方法就是对共享对象加锁，保证对共享对象的访问是互斥的。

调度器的话每个人的实现可能区别很大，甚至很有可能没有一个明显的调度器类。至于我的实现（主要指后两次作业），创建了一个调度线程，负责从缓冲区取请求放到合适的楼座（层）（实际上就是选择调用谁的调度方法），而具体分配到哪部电梯通过调用楼座（层）类中的调度方法进行分配。

BUG分析

第五次作业我犯了很多人犯的错误，忘了对输出方法进行线程安全的封装，导致互测被hack；

第六次作业没有发现bug；

第七次作业发现了一个性能上的bug（其实是五六次作业沿用过来的），导致电梯不能在空乘后快速接取下一个乘客，于是强测有一个点些微超时。

总的来说，本单元没有出现什么大的逻辑错误，我自己还是比较满意的。

心得体会：

本单元我接触到了java的多线程编程，这种编程的方式对我来说完全是一种崭新的视角。虽然一开始有点难理解（更难调试），但是随着理解的深入，越发感受到多线程编程技巧的一些巧妙之处：无论是生产者消费者模式、流水线模式等设计模式，还是SOLID设计思想，都引发了我的不少思考。当然最令人高兴的还是自己的代码能够依照自己的想法正确运行，bug逐渐减少的过程。