BUAA OO第二单元总结：电梯调度
一、同步块的设置和锁的选择
- 本单元的三次作业我均使用了synchronized关键字封装代码块，在输入线程或电梯线程对公共请求队列进行写操作（增加请求和取出请求）时，需要使用synchronized进行封装。
- 为了避免死锁的出现，在设计中，避免了同时synchronized两个锁的情况。
二、调度器的设计
在三次作业中，我均使用了look算法，并采用了集中调度的方式进行电梯的调度，并且调度器是静态的，而不是一个线程。
- look算法：电梯在1至20层中来回移动，只会完成与电梯运行方向相同的请求，当电梯发现运行方向上没有请求并且电梯内没有乘客时，便会调头。
- 集中调度：所有的电梯共享同一个候乘队列，*竞争所有乘客请求。
电梯每移动一层，便会和调度器进行交互，判断在本楼层是否应该开门、是否应该调头，按照读取的信号进行操作；开门后，调度器会进行判断，并将该电梯允许运载的乘客放入电梯的队列中；此外，新电梯的创建也由调度器来完成。
三、架构及可扩展性分析
由于这三次作业均是在第一次作业的基础上进行的迭代开发，程序架构基本相同（均使用look算法，并采用竞争式的集中调度），这里只介绍第三次作业的架构。
1.UML类图
2.UML时序图
3.运行逻辑简述
- 从UML时序图中可以看出本架构中，输入为一个线程，每个电梯拥有自己的线程，而调度器是静态的，并非一个线程。
- 当一个请求被读入后，将会按照出发层数暂时存在Scheduler内的WaitQueue中。
- 每当电梯运行一个楼层（或是刚开始运行）时，便会从Scheduler中读取需要的信号，作为自己下一步行为的判断依据（如移动、调转方向、开门等）。
- 所有电梯共享WaitQueue，并进行竞争，通俗点来说就是谁抢到乘客，就由谁来运。
- 换乘策略是静态的，并且十分简陋。为了减轻移动巨慢无比的A类电梯的负担，我设置了B电梯允许运载出发楼层为奇数并且目的层数为偶数的乘客到离目的层数最近的奇数层数。此外，没有其他换乘策略。
- 为了达成换乘的效果，当一个请求被B类电梯抢到并且需要换乘时，调度器将会把原请求拆分成两个请求，第一个请求存入电梯的运载队列中，第二个请求存在第一个请求的目标楼层中并进行标记（在第一个请求完成之前，被标记的请求会被电梯无视）。当该B类电梯完成第一个请求后，会将第二个请求的标记清除，此后第二个请求可以由其他电梯（A类或B类）完成。
- 当WaitQueue和电梯的运载队列为空时，该电梯线程便可以终止。
4.可扩展性分析
-
在这三次作业中，由于电梯是一个只需要按照调度器提供的信号运行，当有新的需求出现时，不需要对其中的方法进行大量的修改，因此可扩展性较强。
-
但是，由于采用了集中调度、调度器是静态的，该部分可拓展性并不强。如果添加了新的需求（如可达楼层的修改、换乘的强制要求等），对调度器中的方法需要进行大量的修改，这里需要大量的改进。
四、自己程序的bug分析
这三次作业在强测和互测中均没有被发现bug，总结一下可能是由于以下几个原因：
- 程序逻辑较为简单，需要加锁的地方并不多。
- 尽量避免同时synchronized两个锁的情况，以防出现死锁。
- 使用了wait的方法避免出现轮询。
- 由于架构设计的原因，线程结束的逻辑判断十分简单，不会出现线程无法正常结束的情况。
A组的同学们hack积极性不是很高，出刀次数较少。
五、互测策略
1.与第一单元的差异
首先是结果的不可预测性，由于每次程序运行顺序的不同，每个人的程序每次输出都可能不一样，想要完全准确测试是一件很困难的事情。这充分体现出了多线程的特殊性，和以往学习的代码（如第一单元）具有很大的不同。
2.测试策略
本次互测，我主要通过构造极端数据来进行hack，通过阅读代码，大致了解其调度策略，并寻找可能可以hack成功的极端数据。但是，这种方法效率很低，并且整体效果十分一般。
六、心得体会
- 由于有了第一单元多次重构的教训，从第二单元的第一次作业开始，我便有考虑接下来几次作业的扩展要求，最终成功的避免了代码的重构，这是我这一单元相对于上一单元的重要进步，我对此也较为满意。
- 在线程安全的角度上，通过这三次作业的训练，我对线程安全也有了一定程度的理解，能够成功地避免出现线程安全的问题，这也是这个最大的收获之一。
- 此外，我也感受到迭代开发的难度。在第二单元作业中，我尽量保证了架构的可扩展性。但是，随着迭代开发的次数增多，原本较为简洁、合理的架构逐渐变得臃肿，以至于第三次作业之后的架构可扩展性大大降低。
- 第二单元到此就已经结束了，但OO课程还要继续，希望能够在接下来的学习中继续进步。