OO第二单元作业分析——并发与多线程
序：多线程究竟“多”了什么？
首先还是要澄清一下并行（Parallel）和并发（Concurrency）的区别，许许多多的网站或者教材对于这两个概念都下了科学而准确的定义，却往往还是令人摸不到头脑，至少我曾经一阵子就觉得似乎只要是一堆事情同时进行就是并发或者并行。因此，从实用主义角度出发，这里我不在贴任何权威性的定义，而只是给出一个比较易懂的例子，但相信你看完之后一定能懂：
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。并行：你一边听着OS理论课，一边肝OO的作业，同时嘴里还在吃着早点，这叫并行，即你确实在同时进行多项任务。
并发：你只在听OS理论课，发现老师讲的内容太简单不用听的时候，就抓紧时间写几行OO代码，这叫并发，即你只是一段时间进行多项任务，而不一定同时。
有一种关于并发的较为普遍的看法认为，并发能够降低任务的完成时间。这显然是不正确的，因为任务本身与调度是无关的，调度所解决的只是一系列任务完成的总效率。所以如果说多线程究竟多了什么，应该是多了资源利用率，公平性和便利性。天下没有免费的午餐，相应的，还多了更多的麻烦（安全性，竞态条件，死锁，饥饿，活锁......）。
关于更多的线程安全策略与分析我们将结合电梯的作业具体来看，这里首先先给出几种解决临界资源访问的方式，因为由于本单元仍是多线程的基础任务，因此不会出现很多高级的线程问题需要我们考虑，而共享资源访问却是无论如何避免不了的。
1，内置锁（Intrinsic Lock）：线程进入同步代码块之前会自动获得锁，退出（或者抛出异常）时自动归还，同一时刻最多只能有一个线程持有锁，其余线程如想要进入需阻塞。
2，利用原子变量类（Atomic）：注意原子变量尽管本身不可打断，但是多个原子操作语句仍会产生安全问题，因此原子类适用于该变量语句相对较少的方法（比如用作计数器）。
public class AtomicTest{ private static AtomicInteger count = new AtomicInteger(0); public void test(){ ... count++; // count统计test方法调用次数 } }Atomic
3，volatile类：保证每次读取都会返回最后写入的值（即保证数据有效性），比内置锁更轻量级，且可简化代码实现。
volatile boolean isfound; ...... while (!isfound) { keepFinding(); }volatile
4，不可变对象（Immutable Object）：不存在线程安全问题，即便是缺乏同步的发布过程。
public class FinalTest{ public final int n; public FinalTest(int m) { this.n = m; } }final
一、电梯设计策略分析
1.1 单部多线程傻瓜调度（FAFS）
由于是多线程任务的开山之作，因此此次作业相对简单，直接套用生产者-消费者模型就可以解决。其中，生产者`Button`负责接收输入并存放到调度器当中，消费者则是Elevator，从调度器当中取出指令并运行。显然，由于存在共享对象请求队列，因此加锁是必须的，这里我们选择内置锁：
public class Scheduler { private static LinkedBlockingQueue<PersonRequest> requestQueue; public synchronized void put(PersonRequest pr) {...} public synchronized PersonRequest get() {...} }View Code
不足之一是画蛇添足地又使用了阻塞队列（BlockingQueue）进行操作。事实上由于已经使用了同步代码块，再加上一种原子操作可能会带来不必要的混乱，而且在安全性上没有任何好处。
1.2 单部多线程可捎带调度（ALS）
第二次作业对于调度算法有了一定的要求，即至少要满足捎带请求。我们在这里采用的是Look算法。电梯在运行时候，会先拿到一个请求作为主线程，此后在运行到每一层的时候，如果有与当前运行方向同向的请求，则会进行捎带（反方向则不予理睬，主请求除外）。此外如果主请求结束而电梯中仍有请求未到达终点，则选择其中目标楼层距离当前楼层最远的作为新的主请求，直至所有指令全部满足。这个时候再从调度器的等待队列中取一个新的请求作为主请求，如果没有则会wait，直到被notify或者结束（这里不要用Busy Waiting会占用大量处理及资源！）。选取主请求在理论上看似累赘，实际上能够使得我们的实现思路变得更加清晰，易懂，尤其是在涉及到电梯运行方向转变的时候。
此次我们的线程仍然只有两个：电梯和按钮。事实上，在多线程交互的角度而言，第二次作业相对第一次作业而言并没有增加难度或者复杂度。
1.3 多部多线程智能电梯
这一次作业的复杂性再度上了一层楼：三部电梯，且它们的载客量，运行速度，停靠楼层都不尽相同。这不仅意味着不少请求可能需要我们通过拆分来完成，而且在调度算法的优化上也增加了更多的空间（比如，尽可能让快的电梯运送，以及三个电梯工作量平均等等）
这里我们的Button类终于不再摸鱼了（前两次都只是接个输入，相比于电梯类一个白痴一个上帝）。Button类在接到一个指令后，会根据需要转换成相应的一个Request类。这里的Request是我们新定义的数据结构，为了解决官方给出的PersonRequest无法新建或者编辑（也就意味着，无法拆分）的难题。如果发现需要换乘，那么我们会构造两个Request类来代替旧的请求，中转楼层为满足下式最小的楼层：
speed1 * Math.abs(transfer - from) + speed2 * Math.abs(transfer - to)
其中from,to,transfer分别是出发层，目标层和中转层，speed1,speed2分别是换乘前后电梯的运行速度。这个算法的缺陷在于没有考虑电梯到出发层的情形，然而考虑到电梯楼层的动态性，这已经几乎是我们能做到的最佳了。
Button类的另一个任务便是将转换后的请求加入合适的队列。调度器中保存有四个队列：arrayA,arrayB,arrayC,arraywait。考虑到运行速度A>B>C，我们按照如下的优先级进行调度：
A > B > C > (A→B) = (B→A) > (A→C) = (C→A) > (B→C) = (C→B)
优先级越大的如果可以，则加入相应的队列（显然这样未必是最佳，不过那种级别的优化还是交给高手解决吧！）。换乘的应当注意，为避免数据冒险，我们不能仅仅将某个请求拆分成两个请求，而是在此基础上，第二阶段的请求会加入等待队列arraywait，此后当第一阶段请求允许完毕后，第二阶段的请求才从arraywait中出来并加入相应的队列。
事实上，arrayA并不意味着只有A电梯能够获取指令，不论是捎带还是取主指令，只要A电梯不空且在本电梯运行范围内，那么B,C就可以取获取A的指令。同理C也可以获取B的指令（但是A不能获取B,C的，因为显然，这些指令A电梯一定无法满足）。这样，我们就解决了均衡调度的问题。
说了这么多，还是放一张（纯手绘）UML时序图直观来看吧：
下面再谈谈线程安全的问题。
共享资源有四个：三个电梯的请求队列和等待队列。
public synchronized Request get(char elevatorid...) { ArrayList<Request> temparray; if (elevatorid == 'A') { temparray = arrayA; } else if (elevatorid == 'B') { temparray = arrayB; } else { temparray = arrayC; } ... // deal temparray }View Code
如上，我在这里的处理是将get()方法整个作为同步代码块锁住，事实上这是没有必要的，显然，每个电梯取指令只涉及自己的队列而与其他两队无关（如下图所示），因此这里内置锁的使用有些不当：代码的执行性与并发行很糟，尽管保证了安全性。这种过于保守的并发被称为不良并发（Poor Concurrency）
二、基于度量的结构分析
2.1 类图构架分析
采用IDEA自带的UML功能。生成的三次作业的类图如下：
典型的消费者-生产者双线程模式。往后两次作业都是基于第一次的架构。
虽然复杂了不少，但依然是单例模式。方法数量显著增加，因为这个时候如果将全部功能全部集中与run()中已经不合适了。
第三次类图结构上复杂了许多。基本思路是Button类会将输入处理，转化为Request类，并交给调度器Scheduler类安排。随后Elevator类从调度器中取出Request处理。第三次作业功能复杂，但我们的架构相比之下仍然简洁，但同时可扩展性会很差。
2.2代码量统计分析
我们采用插件Statistic进行各个类以及整体的代码量统计。
相比于第一次，第二次作业Elevator类和Scheduler类的代码量显著增加，而Button并没有什么变化（因为第二次作业输入仍然不许处理，这里没有考虑到可扩展性）。
Request类只是一个数据结构，因此代码量很少也在意料之中。第三次作业代码量再次接近均衡。
2.3 方法与类的复杂度矩阵
2.4 基于SOLID原则的评价
SRP（Single Responsibility Principle）指的是每个类或者方法都应当只有一个明确的职责，每个方法或类都专注于自己的工作，尽可能降低耦合度，这样便能避免许多因逻辑不封闭而引发的问题（这往往令人感到十分苦恼，因为很难发现）。此次作业中，第一次作业的SRP显然做的不够好，当然这和第一次作业的电梯比较简单，基本无需考虑模块化有关。第二，三次作业情况明显有所改善，从类图中我们可以看出，以第三次的智能电梯类Elevator为例，setOrientation在刚启动时设置电梯运行方向，此后每到达一层如果允许停留，getInArray，getOutArray会分别获得在本层进入（捎带），出来的乘客。如果有人进出，那么就会调用openTheDoor开门，人员出入以及关门。一切处理完毕之后，调用moveTheElevator离开本层，继续运行。各个方法各司其职，配合妥当，为排除故障提供了不少便利。除了Elevator类，调度器和输入类Button也可谓分工合理。
OCP（Open Close Principle）强调可扩展性，目标是扩展应该是基于现有代码的基础上增加新的方法以实现新的功能，而无需修改已有的实现。就本单元作业而言，第一次作业这方面表现很好，基本上只需要加上捎带相关的方法（获得捎带，电梯转向等等）就可以直接用到第二次作业。相比之下，至少对于Elevator类而言第二次作业移植到第三次作业就麻烦不少：仅仅就捎带方法gethitch()而言，就需要额外考虑电梯容量限制，捎带者目标楼层在不在本电梯可停靠范围内，捎带队列的选择（作业二只有一个请求队列，而作业三变成了四个，前面已经说过，有些电梯应当考虑多个队列的人是否可稍带）等等。相比而言，调度器类Scheduler和输入类Button就表现良好：前者各个方法基本无需改动，只需要接收一个参数，指示对于哪个队列进行操作即可。这里我传入的是字符变量elevatorid（’A’表示A电梯，以此类推）。Button类OCP良好的更大因素在于前两次实在太基础了，随便加什么功能都不必改写原有的。
LSP（Liskov Substitution Principle）指的是任何出现父类的地方，如果以子类代替父类都不会导致相应的程序出现错误。此次作业我并没有涉及继承与多态，因此不予讨论。
ISP（Interface Segregation Principle）关于接口功能的耦合度要求，同样这里因为不涉及而不予讨论。
DIP（Dependency Inversion Principle）不佳，第三次作业中，Request相当于只是一个数据结构，因此无论是输入类还是电梯类都很依赖于其中的方法。
三、程序bug分析
3.1 历次出现的bug
第二次作业：优化炸了！！！
我的初衷是设计一个“接人”的优化：每到一层，如果发现比当前楼层之前的一层（如果电梯在上行就是第一层，反之下行则是高一层）有请求与当下运行方向一致，则会过去将其专门接过来。这个优化本身并没有多大价值，因此这里完全没有必要。
第三次作业：审题！审题！审题！
开门之后，先进后出。说到这里，相信聪明的你已经知道我看到强测分数之后的心理阴影面积了。
3.2 寻找bug方法
在多线程任务中，显然分析的方法已经不适用了——这并不意味着我们可以完全不看代码，而是测试的时候应该注意将重点放在举例测试之上。因此，多利用评测机生成数据，然后进行测试才是王道。
四、心得体会
如果说此次作业给了我什么教训的话，我想应该是细节决定成败。对于电梯运行的每个步骤，每个过程都应该尽可能理顺，并且自己想清楚每一个细节的实现与出错的可能。如果马马虎虎对待，便会得到惨不忍睹的结果。此外，是绝不能满足于“通过中测”，因为那个根本不是中测而是基本不测。一定要通过大量数据或者最好是测评机对于程序进行检验——许多时候，一个小小的问题就可能使得全局沦陷。
