第二单元电梯调度作业
写在前面
在近三周，我们进入了面向对象程序设计第二单元（电梯调度）。在本单元，我首次接触了多线程的编程思想与实践。多线程的思想非常重要，使用多线程分工处理工作，线程间相互通信、协作可以大大提高程序的运行效率。但随之而来的是线程安全问题的保证。
第二单元作业围绕电梯调度，从“傻瓜”（FAFS）单电梯，到可携带（ALS）电梯，再到多部多线程智能（SS）调度电梯...总体来说就是使用多线程和合适的调度算法使电梯高效。下面我将介绍我电梯调度作业中的思路与代码架构，和调度算法，再根据Metrics度量来分析我的程序架构，简单介绍本单元实验的测试情况，最后总结心得体会。
一、设计思路与架构
第一单元表达式求导的练习，让我们深刻认识到代码构架的可扩展性的重要。在着手本单元作业时，我尽量让自己的构架可以向多电梯方向扩展，进而有了这三次作业的代码构架体系。
在第五次作业中，我使用了三个线程，分别为InputHandler线程来读入请求，Schedule调度器线程来处理请求并把请求分配给电梯，还有Elevator电梯线程进行乘客的运送。
同时，我使用了枚举类定义电梯的状态和乘客的（进出）方向
并定义了三元组结构来处理指令，即把id-FROM-from-TO-to分解为，IN-from-id和OUT-to-id这两个三元组作为电梯执行的命令。
对于调度器和电梯的关系方面，我采用了老师推荐的调度器单例方式，让InputHandler和（各个）电梯Elevator共享同一个调度器。
总请求队列为单例的调度器中的成员变量，同时各个电梯拥有自己要处理的请求的队列这个成员变量。InputHandler把请求放入调度器的请求队列中，调度器再把指令分发给各个电梯中（放入各个电梯的请求队列当中）
最后单例了输出类Output让各个电梯调用方便输出。
具体的结构入下图所示：
第六次作业，要求电梯具有捎带功能。在构架上本是不需要进行修改的。但为了节省CPU时间，方式暴力轮训。我使用了老师推荐的观察者模式。
让调度器Schedule成为输入线程InputHandler的观察者，当InputHandler有输入后，使用notify唤醒调度器线程。同样的，电梯为电梯请求队列的观察者，当电梯队列中增添了指令后，唤醒电梯进行指令的处理。
更改后的结构如下：
第七次作业要求多部电梯多线程智能调度，代码构架除了增加了电梯的数量，规定一些电梯私有成员变量的值以外，代码构架完全可以支持其功能，但是由于有换乘的存在，要标记人在哪一层，所以我增加了一个Map<Integer,Set>结构存储各层等待的乘客。
结构图如下所示：
二、调度算法
本次实验的性能部分主要取决于电梯调度算法，我认为所谓电梯调度算法，要分为电梯运行算法和调度器分配指令的算法。下面我将分别介绍我所使用的"算法"（大概可以被称为算法吧？...）和一些想法。
电梯运行：
我使用了LOOK算法， LOOK 算法是当电梯所移动的方向上不再有请求时才改变运行方向。所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成，免去了电梯频繁的来回移动。是一种平均意义上比ALS更优的算法，尤其是在电梯没有容量限制的条件下。
这个电梯运行的算法我沿用了本单元三次作业，效果好像还可以...不过是在平均意义上的，但其在第二次和第三次作业中都有着比较明显的问题。在第二作业中，由于LOOK要上下扫，而ALS是先服务主请求，如果这两个方向相反，则更近的一方可能更快。所以ALS可以构造很多比LOOK运送更快的请求顺序，但由于互测中取消了Tmax的限制让我和很多人一样免除了一阵腥风血雨...第三次作业中，主要是因为电梯有了容量的限制，如果反方向请求的人进入电梯，长时间从电梯中出去，这样占用了电梯容量（少捎带同一方向请求的人），造成了电梯效率的下降。
任何一种调度算法都尤其优劣势，可以构造成使之运行速效率不高的数据，所以想全面提高电梯运行效率，需要多种调度算法综合使用，选取最优。（在第二次作业中支持输出流，魔鬼三电梯）
调度器分配：
第三次作业中由于有多部电梯，并且各部电梯可以到达的楼层不同，所以有些请求不能直达，需要进行换乘。调度器负责给给三部电梯分配指令，也要处理人的换乘问题。
对于一条请求，我首先判断能否直达，
如果可直达，则在可直达的电梯中，根据优先级进行选择。优先级排序为电梯A>B>C，同向可捎带>STOP>异向，如果电梯满员，则判断该请求要上的层数是否有（有几个）人要出。如果不能进入电梯，则优先级减一。以此规则选择优先级最高的电梯，将此条指令分配给它。具体如下图：
如果不可直达，则要选择中间层进行换乘，由于发现三部电梯都经停1，15层，我选择从这两层中选择一层进行调度。具体实现如下图：
这样的选择显然非常简单，但效率并不是最高的，因为如果from和to都在1到15之间，则应该在1到15间的某一层进行换乘，会节省去1或15折返的时间。但是我经过测试，发现效率并没有显著的提升，（我猜可能是由于将乘客集中于1,15层更加方便携带...）
这个分配算法使决定第三次作业性能的关键，想要把性能提高需要非常综合的算法，但由于我比较菜不敢用非常复杂的调度算法，然后就没有然后了...
三、复杂度分析
总的来说，经过第一单元的练习，我们的代码已经逐渐的面向对象，第二单元多线程作业构架也逐渐合理，但一些复杂度高的问题还是存在。
1、基于CK标准度量
（1）CBO 对象类之间的耦合
Metrics测试显示我本次代码构架的耦合度有了一定的提升，Scheduler和Elevator类的CBO值稍高。
（2）DIT与NOC
本单元作业中我没有使用自己构建的抽象类或接口，使用的都是Java封装好的Thread，Runnable，Observer，Observable等类。
（3）WMC 加权方法数 与 RFC 类的响应集的大小
测试显示我的WMC值和RFC值还是飘高，我认为这是因为电梯运行和调度调度算法都需要建立大量的规则（方法），还有很多私有成员变量的get与set，这是导致我Schedule和Elevator(Command)的方法很多的原因。
2、方法复杂对的分析
从测试数据可以看出，对比上一单元的方法复杂度情况，我的代码有了一定程度的提高（飘红的方法比较少），主要是由于构架比较合理（或者是简单），方法分块较为合理。
四、关于测试
多线程作业对我们的bug调试带来了很大的挑战，断点很难帮助我们找到bug了，需要我们进行自动化测试。
我的测试策略是先对所有楼层进行遍历测试，然后再进行随机测试。
我自我测试中，出现过诸如电梯“鬼畜跳动”（电梯算法问题），不能成功退出（结束的判定），请求未处理完（调度线程未唤醒电梯线程），开关门判定（open判定问题）等等问题。但有幸的是在强侧和互测当中没有出线bug。
在互测当中，我主要是看看各位“屋友”的构架和调度策略，然后随机数据进行测试。测出来的bug很有限（1个），也较为难以复现（是有一定几率死锁的问题）。
总体来说非常和谐。
五、总结与体会
本单元作业，初次接触多线程，电梯调度作业非常适合上手。三个线程协调工作非常经典，让我初步的尝试使用了多线。多线程首先要理解线程间的状态转化，阻塞，就绪，执行等转台的相互转化关系和条件，学习使用java中Thread类的各种方法进行线程的控制。更重要的是线程安全，使用synchronized对临界区加锁是之互斥，或采用线程安全的容器，保证临界区的互斥和多线程的安全。
本单元作业中，延续了上一单元的设计代码构架的要求，我们提前设计好的可扩展性构架让我们节约了很多时间。但是本单元实验对算法的要求更高了。为了保证效率，电梯的运行，调度器分配请求都需要我们设计算法进行优化。并且此优化需要综合考虑各方面的情况，采取多种算法进行分析，综合调度才能保证在各种情况下做到效率更有。这是需要我加强的地方。本单元作业中，我还学习到了一些新的设计模式，如单例模式、观察者模式等。设计模式有助于我们更加工程化的设计代码结构，实现需要的功能。
总体来说我认为本单元的体验还是比较好的，构架与算法综合要求，也更加的有趣。但我在性能方面优化的还不够充分，需要进一步提高。