OO 第二单元总结
OO 第二单元总结
1作业综述
本单元作业共计三次，核心内容为迭代开发java程序模拟电梯的运行，要求按固定格式输出电梯运行过程中电梯到达楼层和开关门的信息以及乘客进出电梯的信息。其中，第一次仅仅有5个纵向电梯，第二次在第一次的基础上增加了横向电梯，并且允许动态增加电梯数量，但是乘客只会请求乘坐纵向电梯和横向电梯中的一种，第三次作业在第二次作业的基础上，不仅允许设置新增电梯的速度，容量，而且允许顾客提出换乘请求。可见，开发难度逐渐提高，有着不小的挑战。
2架构设计与分析。
2.1基本思路
很显然，这次作业必须以多线程的方式予以解决。我的思路来源主要是OO实验课的出校申请题目，作业架构从中借鉴了许多。总体来说，我的三次作业都是三个线程，分别为输入线程InputThread，调度器线程scheduler，电梯线程elevator。输入线程InputThread通过处理输入数据，获得乘客和新增电梯的请求request，并且将乘客请求加入waitqueue，用于调度器线程scheduler进行调度，调度器线程scheduler调度的结果便是乘客的各个请求分配到合适的电梯的外部等待队列outqueue中，也就相当于分配给了对应的电梯线程Elevator。最后再由电梯线程逐个处理从属外部队列ouequeue中的乘客请求。
2.2 UML图
StaeUML只给会员提供导出功能，因此不是会员的我只能采用分开截图的方式展示自己的UML图。
第一次作业的UML图如下：
第二次作业的UML图如下：
第三次作业的UML图如下：
2.3时序图
第一次作业时序图如下：
第二次作业的时序图如下：
第三次作业的时序图如下：
2.4迭代分析
由UML图可知，第一次作业与第二次作业架构基本一致，使用的类完全相同。相比第一次作业，第二次作业的主要区别在于：
在等待队列的类RequestQueue中增加了所在楼层floor和种类信息type的属性；
在输入线程InputThread中增加了新增电梯线程的建立过程；
在调度器线程scheduler中更改乘客请求调度方式，由原来的简单根据电梯所在楼座分配更改为在符合乘客请求的电梯种类从属的所有外部队列outqueue中寻找一个人数最少的予以分配；
在输出信息时，要根据电梯的种类选择乘客请求prequest和电梯elevator的不同属性进行输出。
由UML图可知，第三次作业相比第二次改动较大。
相比第二次作业，第三次作业区别主要在于：
新建一个名为TempRequest的类；
在乘客请求类Prequest新增在容器ArrayLis中的TempRequest属性，用于保存为调度器线程scheduler为乘客规划出的分段路线；
在调度器线程scheduler中新增多个方法，以实现对乘客请求的路线规划；
对输入线程InputThread使用了单例模式；
在输入线程InputThread中新增了numPersonRequest属性
以统计总的乘客请求数量，新增的信号量semaphore属性以判定乘客请求是否全部执行完毕，后者也是第三次作业的最大亮点，是解决轮询bug的关键。
2.5线程协作关系
输入线程InputThread通过处理输入数据，获得乘客和新增电梯的请求request，并且将乘客请求加入waitqueue，用于调度器线程scheduler进行调度，调度器线程scheduler调度的结果便是乘客的各个请求分配到合适的电梯的外部等待队列outqueue中，也就相当于分配给了对应的电梯线程Elevator。
对于前两次作业，当输入终止的时候，输入线程InputThread终止，并且修改调度器线程scheduler的属性isEnd为true，在此前提下，当调度器线程scheduler的等待队列属性waitqueue为空时，调度器线程scheduler终止，并且将所有电梯的外部队列outqueue的属性isEnd设置为true。当电梯线程elevator的从属外部队列outqueue和内部队列inqueue都为空，并且其从属外部队列的属性isEnd为true时，电梯线程终止。
第三次作业的不同之处在于，当输入结束时，输入线程InputThread还需借助其信号量属性semaphore确定所有乘客请求执行完毕才会修改调度器线程scheduler的属性isEnd为true并且终止。
3同步块的设置和锁的选择
三次作业中，我都对RequestQueue的所有方法设置为synchronized的方法，并且都在输入线程InputThread和调度器线程scheduler有部分同步语句块。在第三次作业中使用了信号量的对象semaphore，其方法acquire和release都是同步方法，此外为了修复bug在电梯线程elevator中新增了一个同步语句块。
三次作业的同步语句块都以outqueues作为锁（outqueues是外部等待队列outqueue的ArrayList)，因为outqueues是输入线程InputThread和调度器线程scheduler的共享对象且输入线程InputThread对outqueues有写操作（新增电梯线程elevator时）。由于在有人进入电梯后要从该电梯的外部队列outqueue中删除该请求，是一种写操作，因此也需要用outqueue上锁。
4调度器设计
三次作业，我都选择将调度器设置为线程scheduler。
第一次作业，输入线程InputThread将输入中的乘客请求写入待分配队列waitqueue。电梯数量固定为5个，调度器线程scheduler只需依次分析waitqueue中的乘客请求对应的电梯楼座便可将乘客请求分配至相应的外部队列outqueue。由于每一个outqueue都属于一个电梯线程elevator，以上过程也就实现了对乘客请求的调度分配。
第二次作业，电梯是可以临时添置的，电梯类型也新增了横向电梯。在第一次的基础上，调度器线程scheduler需要分析waitqueue中的乘客请求是对应横向电梯还是纵向电梯，如果是纵向电梯，则在所有楼座匹配的外部队列outqueue中寻找一个人数最少的将乘客请求插入其队尾，如果是横向电梯，则在所有楼层匹配的外部队列outqueue中寻找一个人数最少的将乘客请求插入其队尾。
第三次作业，电梯不仅可以临时添置，而且添置的电梯如果是横向电梯，需要设定该电梯能在哪些楼座开关门，更麻烦的是，waitqueue中的乘客请求不再局限于同楼座或者同楼层（也就是乘客请求可能涉及换乘）。因此，调度器线程scheduler成为第三次作业最关键也是最困难的一部分设计。在这里，调度器线程scheduler需要完成规划路线和分配两个功能。waitqueue中的乘客请求也不再仅仅来源于输入线程InputThread，还可能电梯线程elevator，当一个乘客请求的规划路线没有执行全部执行完毕时，该乘客请求从电梯从属的内部队列inqueue中移除时，需要写回waiqueue。那么，面对waitqueue中的乘客请求，调度器线程scheduler首先需要判断该乘客请求是否已经规划了路线，如果已经规划，则直接分配，否则规划路线以后再分配（对应地，在乘客请求的类Prequest中新增了布尔属性planed表示乘客请求是否已经规划）。具体的分配规则是：如果waitqueue中的乘客请求对应的电梯是纵向电梯，则分配方式与第二次作业相同，如果waitqueue中的乘客请求对应的电梯是横向电梯，则应该在能执行该乘客请求规划出的路段中的横向路段请求的横向电梯中（该电梯对应的需同时满足楼层匹配和出发楼座、目的楼座都可以开关门）选择一个从属外部队列outqueue人数最少的将乘客请求分配。
5 Bug分析与修复
本单元作业完成度较高，三次公测只在第三次有一个强测点出现了tle，三次互测只在第二次被hack中了一个点（也是tle）。这两个bug都是因为当乘客请求执行完毕（前两次作业）或者临时执行完毕（第三次作业）时，从电梯从属的外部队列outqueue中移除乘客请求时没有上锁，目前已经修复。
6 关于互测
首先，本人是反对使用codeforce的互测机制，本着人道主义的原则，本人在第二单元从未尝试hack别人，但本着学习和锻炼debug能力的原则，本人还是在本地阅读他人代码并且做相关测试。
测试最有效的自然是事先准备好的自动评测程序，其中随机数据的生成方式主要是在较短时间内的投喂大量的相似乘客请求或者根据稍带策略交叉投喂方向不同的乘客请求。
较之第一单元发现的bug，本单元的bug因为多线程常无法复现。个人认为，在发现bug之后，更改根据bug类型人为构造数据或者在代码相关部分寻找逻辑漏洞或者线程不安全的隐患，这样可以一定程度提高bug复现的概率并且最终解决。
7 心得体会
线程安全的把控实属不易，全部语句同步化程序开销大，选择性同步化又容易遗漏应该同步化的语句造成线程安全问题。只有充分理解共享对象在不同线程中的穿插，才能精准把握语句块上锁的位置，这是需要大量练习和思考来体会的，第二单元的作业仅仅是让我们打开了多线程认知的大门。
我在第二单元的三次作业的层次化设计上相对第一单元进步明显，面向对象的思维初步建立。三次作业没有出现重构问题，迭代开发比较顺利，是一段很好的学习经历，希望将来再接再厉，能够真正学号OO这门课。