【OO】BUAA-OO-U2-电梯调度

BUAA OO U2 单元总结

本单元主题为面向对象中的多线程编程，经过这一单元的训练，我认为要做好多线程编程，可以大体分解为几个要点：理解和掌握多线程中的同步控制机制和线程的不同状态，保证共享对象访问时的线程安全，保证线程和线程交互时的线程安全。
下面根据本次作业中的内容对以上要点进行具体体现。

多线程中的同步控制

关于同步块、锁与线程的状态，我在另一篇博客中有所总结，这里不再赘述。
在本单元的作业中，我采用的均是最基础的synchronized同步块，原因一是这是最初的选择，二是使用读写锁等更高级的锁经过试验在此次作业的体量下不会有肉眼可见的性能改进，于是我没有使用更高级的锁。
对于同步块中的语句，这一点可以说是很需要认真思考并设计的部分，如果有些带锁语句不在同步块中，锁的频繁释放和分配可能会导致意想不到的问题，如果过多的语句放在同步块中，又会导致性能的下降，同时使用不当还会产生死锁风险，因此这对我们的设计和实现都有着很强的要求，经过本单元的训练我体会到的关键点如下：

• 同步块中尽量由原子操作组成
• 同步块中避免对其他锁的获取
• 同步块在顺序代码块中的位置要合适，尽量做到能够集中同步操作

这对设计和实现的过程是个挺强的要求，在实践过程中我觉得需要注意一些问题：

• 对于目前操作持有的锁和尝试获得的锁要保持敏感和清醒
• 对共享对象状态的变化保持敏感
• 当出现线程间的交互时，警惕并排查是否可能会出现死锁

综上，多线程中的同步控制既需要我们有清晰正确的理论知识，更需要在设计和实现过程中遵循一定的原则，保持敏感和清醒，这样才能尽可能少地犯错误。

调度器的设计

调度器这部分的设计我认为很能体现多线程的特点，作为读写的枢纽，如何正确处理读写过程中产生的冲突，如何确定线程的结束，这些都是调度器的设计中需要重点考虑的问题，所以调度器不仅仅是把请求分配给哪部电梯这么简单。

调度策略

我的想法是，尽可能符合直觉和生活经验，因此我没有选择以影子电梯为代表的有些反直觉（对于我的主观感受）的策略，而是使用更符合我的直觉的策略。
我在本单元的迭代过程中使用过两种调度策略，分别是打分调参和随机分配。

打分调参

打分调参是通过分析各个电梯状态，根据含参数的评分标准，评估出最合适的电梯。最初我选择这个方法是因为我觉得这样可以通过黑盒测试，逼近一个全局的最优性能，这可能可以做到比影子电梯的性能还要好一点，并且比较符合直觉和实际应用。
我的具体实现是大量模拟，离线调参，配合评测机中的数据生成模块，通过生成大量的高并发数据点，来对不同参数组合进行测试，通过遗传算法不断进化，实现自动化探索在大量数据下平均表现最优的参数组合。
遗传算法离线调参这样的方法有着明显的缺陷，一是需要大量的时间来进行模拟，二是可扩展性差。根据我的实践，通过模拟使遗传算法逐渐收敛到一个较为稳定的、表现良好的参数组合需要50个小时左右，具体一点是两天不间断地进行模拟。
可扩展性是另一个硬伤，根据不断的迭代，评分标准需要不断做出改变，这就需要重新寻找合适的参数组合，所以尽管调参的表现还不错，但是我还是放弃了这一策略，改用更简单的随机分配。

随机分配

这个策略最初给我的感觉是离谱，凡事总往坏处想，万一一个随机不好导致超时了该怎么办，没有什么思考直接放弃大脑这样做真的合适吗。但是实践证明这是个可用的策略，可以说，在数据量的支持下，随机能够实现宏观上的平均。放弃调参策略后使用随机分配的表现也是相当不错。

读写冲突的处理

调度器需要从请求队列中取出请求，将其放入合适的电梯的候乘表中，这个过程中对请求队列和候乘表这两种共享对象都存在读写，并且电梯线程还可能处于临时调度，升级等特殊状态。
一个很典型的例子是，如果电梯正在临时调度，那么该怎么把请求写入候乘表。这个问题hw2中困扰了我们很多人：六台电梯五台都在调度，如果全分给剩下那一台电梯会导致超时。我一开始的处理方法是如果调度器选择把请求分配给正在临时调度的电梯，那么调度器线程就等待电梯临时调度结束再进行分配，这就导致了阻塞了后续的请求，像临时调度和升级等对开始时间有着明确要求的特殊请求，就会导致其被阻塞。
我想能不能有一些普适性的方法去解决这样的一类问题，而不是局限在电梯调度这里一些具体又细微，针对性的策略。这个时候程序的IO启发了我：我们的终端控制台就是一个典型的读写处理器，当我们复制一大串内容进入时，控制台却能做到在main方法线程IO正常执行又不会影响到控制台的正常IO，是因为控制台的输入进入了缓冲区，main线程的IO通过缓冲区进行。我觉得这就是我想要的普适性方法，于是我的策略是，设置缓冲区，将临时调度时分配给电梯的请求放入缓冲区，等调度结束后再进行统一RECEIVE，进入候乘表。这样便可以避免很多不必要的线程安全问题，实践体验是非常好的！

线程结束的判断

在本次作业的实现中，各个线程除了请求输入装置可以自行结束以外，调度器线程和电梯线程都需要手动根据条件判断来结束。而电梯线程的结束依靠调度器发送的结束信号。在三次迭代过程中，调度器判断结束的条件都需要改变，如果简单地去根据某些共享对象的状态，很容易出现无法解决的线程安全问题。
我的思路是还是以生产者-消费者关系作为思考的出发点，第二、三次作业本质上就是让电梯也成为调度器的生产者，而不仅是请求输入装置这一个生产者，所以正确的判断应该是所有的生产者均不会再生产时，调度器才应该正确结束，发送结束信号。而判断生产者均不会再生产，具体到实现上，我的做法是维护产生生产的请求数量，如：临时调度请求数量、升级请求数量、换乘请求数量。这些数量不全为0时说明电梯线程仍然处于生产状态，调度器不能结束。

线程架构

在这三次迭代的过程中，保持不变的是整体上的两级生产者消费者模型，电梯的状态机LOOK调度算法等，迭代过程中主要的变化还是在电梯的特殊行为，如临时调度、升级等。
临时调度时改变的主要是调度器和电梯这两个线程之间的交互关系，升级时还有着两台电梯间的线程交互。一旦涉及线程交互，便可能会出现一些问题。

双轿厢

对于双轿厢的问题，主要有以下几点：改造开始和结束的同步、两个轿厢运行时不碰撞、换乘请求的分配。
改造开始和同步和两个轿厢运行时不碰撞的关键实现是相同的，都是通过对象锁实现。改造开始的同步实现中，先准备好的电梯需要等待后准备好的电梯，通过对象锁配合wait-notify可以很好地实现同步开始。轿厢运行不碰撞的实现，思路是很自然的，两个轿厢在换乘楼层是互斥的，这和锁和同步有着异曲同工之妙，所以可以通过同一个对象锁实现。获得锁的轿厢可以获得进入换乘楼层的权限，当然，既然同步块结束时会释放锁，那么轿厢也应该主动从换乘楼层离开，这和指导书配合得很好。
关于换乘请求的分配，其实也很简单，不过需要注意之前提到的需要维护换乘请求的数量，因此要保证同一换乘请求不被重复记录，这可以通过集合来实现；也要注意不要忽视某些换乘请求。

Bug与Debug

Bug

我出现的Bug主要是死锁问题，反思主要原因，还是设计和实现的过程中不够警觉，常常是上午写一部分，下午再写的时候就忘了目前持有的锁，出现锁的嵌套，导致死锁。还是要有主动判断的意识，防止死锁的出现。还有一些问题比如输出信息的时机。其他的一些问题比如线程的结束条件和阻塞在前面都有所提及。

Debug

关于Debug，多线程的Debug通过断点机制是无法调试的，我采用的最多的还是向控制台输出，将输出穿插在线程的运行过程中，这样不会影响线程的正常执行。对于死锁，可以通过IDEA自带的快照工具，通过对死锁时刻的快照，可以很清楚地看到每个线程持有锁和等待锁的情况，从而发现问题。

心得体会

线程安全

一定在进行编码和设计实现的过程中保持强烈的线程安全意识，不能滥用同步块，有些简单的原子操作可能需要获取锁，但是放入监视其他锁的同步块中就有可能导致死锁，还是要保证同步块里尽量不去获取别的锁，各自的同步块尽量集中把各自的事情做完。

层次化设计

本次作业中的层次化设计我感觉主要是设计架构和方法上的层次化，架构上清晰的生产者消费者架构能够极大地便利问题的理解，有助于思路的产生。而电梯作为一个具有复杂行为的迭代线程对象，对其行为进行层次化设计使代码的扩展性更强，满足开闭原则。

实践经验

优秀的代码是需要不断打磨的，不加雕琢的代码在我目前的水平来看不能解决所有问题，一定要耐心地对程序做好复盘检查和测试，不能因为偷懒忽视这一重要的环节！而做这一切事情都需要时间，没有充足的时间很难把事情做好，只会变得草率。要不断提高处理生活中高并发请求的能力。继续加油！