目录
前言
一、第一次作业分析
1. UML及复杂度分析
二、第二次作业分析
1. UML及复杂度分析
2. 性能优化
2.1 楼层类的实现
2.2 调度算法
3. bug分析
三、第三次作业分析
1. UML及复杂度分析
2. Bug分析
四、评测机的搭建
1. 整体框架
2. 正确性检测
五、多线程的调试
前言
这三周以来的OO多线程 + OS实验关键期 + OS理论课期中考试 + 每周一次去学院路的答辩 + 每周日一上午的行进管乐团训练 + 每周日一晚上的交响乐团排练 + 其它各种琐事让我深感艺术特长生在6系活着的艰难。已经数不清这几周有多少次不到四小时睡眠的极限操作，三次OO作业也全部是ddl当晚才第一次提交，并经历了两次ddl前全天不出寝室肝代码的操作。
咳咳，回到正题。这一单元取消了WF的判定，所有的输入输出格式规范都由课程组提供的类包解决。因此，可以说我们的精力更多的放在了面向对象本身上（虽然从第二次作业开始精力就大部分放在算法上了）。一个清晰的架构在这三次作业中显得尤为重要，松散的架构往往会导致出现各种难以预料的多线程bug。下面分享一下我在做这三次作业中的心得体会。
一、第一次作业分析
虽然第一次作业代码量很小，想完成作业的难度并不大，再加上没有性能要求，且基本没有卡CPU实际运行时间，这次作业基本绝大多数人都能取得满分的成绩，甚至单线程，轮询等方式也能顺利通过这次作业。但是对我而言第一次接触多线程编程还是花了很长时间去理解，主要问题如下：
（1）wait，sleep的区别：是否释放锁？
（2）notify，notifyall的功能及区别？
（3）wait，notifyall所操作的对象到底是谁？
（4）sychronized方法锁与对象锁的理解，锁的到底是哪个对象？
（5）线程安全问题：线程安全的核心是共享对象的处理
（6）线程安全问题：什么时候需要在wait外套上while循环？
（7）线程安全问题：线程安全容器的使用：blockingqueue
上述问题基本都在Thinking in Java中得到了解答，再加上百度和Google，在写第一次作业前我对多线程编程有了一个大概的了解。由于这次作业完全是傻瓜电梯，即逐条执行请求一次只送一人且不涉及捎带、不涉及超载，这就是一个典型的生产者消费者的模型，并且只有一个生产者和一个消费者，因此解决“请求队列”这个共享对象的线程安全问题甚至不需要用wait和notify，只需要用blockingqueue的take和put方法（线程安全的方法）就ok了。稍有难点也是比较容易出bug的地方在于终止请求的处理，并且这也是之后两次作业的难点之一。
对于这次作业而言，如果单纯为了简洁甚至不需要实现调度器类，主线程中开一个模拟请求的线程和一个处理请求的电梯线程，共享一个用blockingqueue维护的请求队列，在官方给PersonRequest类生成的对象放在自己自定义的类中，这个类的一个成员变量用于标志是否是终止请求。电梯收到终止请求，并且把所有人送完，就可以结束电梯线程了。
但在第一次作业中我对结束请求的处理非常粗糙，最后通过主线程来结束电梯线程。在正常情况下，主线程应该只负责把电梯线程和模拟器线程启动，之后它的任务就结束了。这一点也在之后的作业中得到了改正。
UML及复杂度分析
（1）类图
（2）时序图
（3）复杂度分析
这次作业由于问题本身复杂度很小，因此写出的程序复杂度也较低。从SOLID原则的角度分析，这次作业并没有满足SRP（单一责任原则），电梯除了接送乘客之外也揽了调度的活儿，而调度器实则只是一个请求队列，并不能叫做调度器。因此，这次作业也没有满足OCP（开放封闭原则），在第二次作业中几乎进行了整体的重构。
由于本次作业没有被找出来bug，屋内也没有同学出现bug，就跳过这一部分的分析。
二、第二次作业分析
第二次作业增加了捎带请求，并且大大缩短了CPU实际运行时间，因此，这次只要是用轮询或者没有正确的使用wait与notify基本会被卡死。值得一提的是，由于这次作业由于没有主请求的概念，并不需要一个FIFO的请求队列，从一个请求集合里调和放请求的方法也较之前复杂了一些，因此我没有沿用上一次的blockingqueue，而是用Arraylist和sychronized，wait，notifyall手动维护了一个线性安全的请求集合。在这次作业中，好的架构显得尤为重要，这几乎决定了算法优化的空间。这次在架构的设计大概耗费了一整个周日，好处就是第三次作业几乎可以完全沿用第二次的架构，调度算法的优化也取得了还算不错的结果。具体的实现将在接下来的部分总结。
1. UML及复杂度分析
(1) 类图
（2）时序图
（3）复杂度分析
不出意料，由于在优化过程中调度器要对当前不同的情况进行许多特判，电梯也要根据厢内人员状态判断是否开关门，因此调度器确定电梯运行方向的方法和电梯线程的复杂度较高。在之后的研讨课中，学到了wsb大佬的一个小trick可以让代码变得更清晰并且易于扩展：通过enum函数给需要特判的每一个条件取一个有意义的名字，并通过switch-case来执行，这样想到一个优化的trick就可以给它加进去，想删掉的时候就可以很容易地删掉。这不禁让我想起了这段代码（部分）：
像极了当时计组的controller有没有！这也让我陷入了反思，为什么没能把计组中学到的工程思想迁移到OO中来，这说明我在学习中缺乏对知识更深层面的理解，没能将一些思想的精髓熟记于心，这也是我以后在学习中要注意的地方。
2.性能优化
2.1 楼层类的实现
本次作业官方提供的算法为ALS算法，但是这个算法在题目的情景下注定是一个性能很差的算法。为什么这么说呢？我们知道现实生活中的电梯需要遵循的准则之一是要将先发生的请求先执行，因此需要有“主请求”的概念，ALS算法也正是基于“主请求”这一概念而设计的。而在我们的题目中，判断性能的标准是将所有请求执行完的总时间，完全不涉及总请求的概念。也就是说，如果调度算法里还考虑了主请求的成分，那么这一部分的冗余大概率会拖累整体性能。
基于上述情况，实现楼层类是一个很好的选择，并且这样的架构可扩展性非常强。基于楼层类，我的各个线程协作关系如下：
（1）模拟器线程将请求塞到各个楼层中
（2）电梯线程在需要的时候（将电梯里已经没人了），向调度器询问下一步应该朝哪个方向走
（3）调度器在收到电梯的请求后，通过对当前各楼层的人员分布，通过调度算法制定方案，给电梯一个答复
在这样的架构中，可以看到调度算法的代码区域较为集中，因此如果想做性能优化的尝试基本不会影响到整体的架构。
2.2 调度算法
有了上面的架构，就可以开始设计调度算法了。我最后的算法和look算法比较接近（经典的诸如look，scan这些电梯调度算法都可以百度到），主要的思路如下：
（1）当电梯内有人时候，保持之前的运行方向，此时若有可捎带请求便将其捎带（一旦在某楼层停靠，可以将反向请求捎带，这样可以可能会节省一次接人的开关门时间）
（2）电梯没人时，若某楼层还有人，选择离得较近并有请求的楼层，到达前保证不改变方向（否则如果电梯上下交替出现更近的请求则会出现不断转向的情况）；若楼空了，让电梯停住
3. bug分析
由于本次作业没有被找出来bug，所以分享一下同屋同学以及道听途说的bug：
（1）线程安全问题：死锁，漏请求
（2）逻辑漏洞或线程安全问题引发的通向天国的电梯和通向地心的电梯
（3）由于轮询或未意识到的轮询导致CPU超时
三、第三次作业分析
第三次作业要实现多个电梯，且不同电梯可停靠楼层不同且，这就意味着许多请求不能仅由一部电梯完成。楼层类的实现使单电梯向多电梯的扩展变得非常容易，拆分请求的最简单的方式就是把该电梯送不到的乘客放在能送到的楼层，且该楼层能被其它电梯接到。由于时间原因，我最后也只是实现了这种最简单的方式。通过和同学讨论得知，在分配任务这一方面如果事先确定好每个请求应该由哪两个电梯完成，会在强测中取得很理想的性能分。
1. UML及复杂度分析
（1）类图
（2）时序图
（3）复杂度分析
四、评测机的搭建
相信每一位做完多线程作业的同学都会觉得多线程的程序简直难以调试，一直依赖的单步调试也不管用了。此外，如果不能模拟定时投放，那么手动掐秒的测试结果往往参考价值很低。因此，自己搭建评测机做大规模测试几乎是一切调试的基础。在第二次和第三次作业中，我的评测脚本都为中测全部通过的好友发现了比较致命的bug，也算是很开心啦。有了评测脚本后会大大提升调试的速率。例如一些不可复现的bug，如果在程序里恰当的位置输出足够多的调试信息，即使每百组复现一组，只要复现，就可以根据输出的调试信息找到蛛丝马迹。单独拎出来的编译脚本和完整的第三次电梯的评测机已上传至我的git仓库https://github.com/Sonicsss，下载到本地后无需修改任何路径可直接运行（保证程序只有一个main函数入口）。只需将自己代码的src文件夹替换掉该目录下的src文件夹，将需要引入的第三方jar包放在lib目录下就无需做其他更改操作就可以运行啦，操作细节写在了readme中。
1. 整体框架
运行界面如下：
（这里的bin，lib，path，src目录为编译时用）
（1）bomber/mode下的各目录代表不同的弹夹，可以通过编写脚本来生成不同类型的随机数据，例如longInterval装的就是长时间间隔投放请求的测试点，在第二次互测中的屋友也正是在两次请求间隔时间较长时才会出现上天入地的bug，concurrent中装的是同楼层同时间多请求的测试点，hand里放的是一些手工构造的数据，pureRandom中放的是纯随机数据，mix则可以将各类型的数据做一下混合。
1 import os
2 path = os.getcwd()
3 #print mode available to console
4 dirs = os.listdir(path + "\bomber\mode")
5 print("
Choose a bombing mode:
")
6 for dir in dirs:
7 print(dir + " ", end = "")
8 print("
")
9
10 #choose a mode
11 string_mode = input()
12 output_dir = "output\"
13 bullet_dir = "bomber\mode\" + string_mode + "\"
14
15 #bullet amount
16 print("
Input the bullet amount:
")
17 bullet_amount = int(input())
上图为弹夹管理部分的主要代码，通过自动检测路径的方式每次增添弹夹文件夹后无需手动更改路径便可直接将该弹夹增添到攻击选项中。
（2）在第一步中我们构造了各种类型的测试点，第二步可以通过编写定时投放脚本来定时输出请求并重定向到我们的java程序中。注意在每输出一条请求后一定要跟上一条：
sys.stdout.flush()
否则所有的输出都会堆在缓冲区最后一起重定向给java程序，这样就达不到定时投放的效果了。
2. 正确性检测
接下来也是比较关键的就是正确性的检验了，我的评测脚本主要分为以下几个部分：
a.逻辑检测：电梯OPEN、CLOSE、IN、OUT、ARRIVE的动作流程是否符合逻辑，通过有限状态机实现
b.功能检测：对与测试数据和输出分别列一张起始时和结束时楼层人员分布图，看是否所有请求都能被成功执行（思路来自xcb大佬）
c.时间检测
运行结果如下：
五、多线程的调试
多线程的调试可以说是比较令人头疼了，主要的问题是难以复现。这里我的好友经历了一个很迷的问题：bug在本地随机测试复现的概率很低（大概100组一次），但是修复阶段提交到评测机那边的两次每20组都会爆两个点，复现频率大大提高。在研讨课中有同学提出可能是评测机jvm与本地版本不同，导致线程调度顺序包括编译机制比如锁粗化可能都会有差别。回去一看果真不同，我们假期按照指导书给的网址下载的jdk是1.8.0_20x版本的而评测机的环境是1.8.0_101，因此我又在电脑上装了评测机的1.8.0_101版本的jdk。遗憾的是，将好友被爆的几个点重复跑虽然会复现，但频率依然不是很高。看这个问题在之后还是要继续研究。
因此，目前我觉得比较有效的方式还是大规模测试 + System.err.println尽可能充分地输出调试信息，这样一旦出现了bug就可以通过调试信息来推断出蛛丝马迹。