菜鸡谈OO 第二单元总结

　　“欢迎来到（玄学）多线程的新世界”

Homework1 单部傻瓜电梯调度

• Part1 多线程设计策略

　　　第一次学到了线程这个概念，与之前的编程体验大有不同。最大的区别在于从原本的线性发生程序变成了多个行为并行发生,思考量直接从o(n)变成了o(n^2).值得一提的是，由于这次电梯作业只有一部电梯，而且调度算法极为简单，FAFS（先来先服务）的傻瓜式调度似乎已经不太需要多线程，放到正常单线程里也许才不到百行。不过笔者考虑到今后可能的魔鬼电梯（事实证明确实魔鬼），还是义无反顾的使用了多线程。

　　　第一次多线程编程，参考了经典的生产者消费者模式，使得整个过程事半功倍（果然直接搬*是极好的）。

　　　具体实现也很简单，资源临界区也就是共享对象Dispatcher调度器负责请求队列，生产者是输入处理类，消费者是一部傻瓜电梯。总计三个线程：包括1个主线程，1个输入线程和1个电梯线程。本次作业有了一丝面向对象的味道，笔者实现了6个类。其中Out是一个static类，仅用于输出信息（以防重复输入出错）。输入处理类Request线程实现很简单，由于输入接口是阻塞式的，所以本质只是一个while轮询，每次读到请求r便将其加入dispatcher的队列中。Elevator仅实现电梯的上下开关门的运行逻辑，而Elevatorctrl则负责解析dispatcher调度出的指令，通过run()函数控制电梯。傻瓜调度的dispatcher自然不消说，直接维护一个FIFO队列。Dispatcher类作为共享对象，对其中每一个方法进行加锁，确保了共享对象的线程安全。（锁就完事了。。。）

• Part2 度量分析

　　　本次作业的类图和复杂度如下

　　　好在本次的复杂度降了下来，每个类都只负责对应部分，耦合度没有上一单元那么高。

　　　优点是耦合度低，每一部分的实现都足够简单，不会出现莫名其妙的bug。

　　　缺点是貌似有些类细分的没有必要，诸如elevator和elevatorctrl类的分离没有什么必要，有一丝多此一举的感觉。

　　　时序图(sequence diagram)

　　

• Part3 SOILD原则

　　　SRP(The Single Responsibility Principle)单一责任原则：这次作业实现很多类，每个类确实几乎只做自己的事。dispatcher只维护FIFO队列，request只负责输入请求，elevatorctrl只负责控制电梯。

　　　OCP(The Open Closed Principle)开放封闭原则：老实说这个原则比较抽象，基本符合了可拓展性。封装后不可随意更改。

　　　LSP(The Liskov Substitution Principle)里氏替换原则：除去继承线程类，未使用继承。

　　　DIP(The Dependency Inversion Principle)依赖倒置原则：代码依赖于抽象，作业实现得不好，导致之后需要修改底层代码。

　　　ISP(The Interface Seqreqation Principle)接口分离原则：未使用接口。

• Part4 bug分析

　　　强测中没有发现bug。

　　　本次作业的代码逻辑实在是简单，另一方面又使用了官方的接口杜绝了WF。因此本次作业完成之后，也没有发现太多bug。

　　　值得一提的是，如何安全结束进程。我采用了一种常用而高效的方法——设置线程间通信信号flag。Request线程读到null，flag置为true并且退出；Elevatorctrl线程判断1）请求队列为空 2）捎带队列为空 3）flag为true。这种方法也就一直延续在三次作业中。

• Part5 发现别人的bug

　　　互测中没有发现bug，也没有被发现bug。

　　　考虑到前面所说的实现过于简单粗暴，因此互测中展现了一幅欣欣向荣，佛系狼人的画面。不过疯狂空刀的样子真美！

Homework2 单电梯ALS捎带调度

• Part1 多线程设计策略

　　　这次作业加入了捎带算法，具体的捎带指导书给出了一种方法作为时间上限。我上网查找了电梯调度的算法，其实并没有静态的最优解，每一种调度算法其实都会有负优化的情况。考虑到不那么随机的随机强测点炸Tbase，我选择了比较好写而且很稳的直接照搬指导书的算法。显然这也和我自己的水平比较相符:)。

　　　多线程同步与上次实现其实并无差异，仍然是输入线程和电梯运行线程。两个线程协同处理请求队列。因为上次代码完成的很不错（其实很烂），需要修改的仅为调度方法，也就是如何从请求队列中取出请求。ALS请求的原则如下：

1. 电梯运行按照主请求，这一步与Homework完全一致。
2. 电梯运行过程中，若请求队列中有请求目的方向与主请求目的方向相同，则将请求置入捎带队列。
3. 主请求结束后，需要选择新的主请求。若捎带队列为空，则选择请求队列最新的请求；若不为空，则选择捎带队列中最新的请求。

　　　这次作业中，Elevatorctrl线程维护自己的捎带队列，新加了主请求和捎带队列的实现逻辑。这次重点考虑的是CPU时间，笔者直接延续了上一次的while-sleep轮询，虽然损一些性能，但是无脑（发出摸鱼的声音）。

• Part2 度量分析

　　　具体的方法复杂度如下：

　　　复杂度分析，很直观就看出来Elevatorctrl和Elevator的复杂度一手拉高了平均值。这两个类的拆分其实没有必要，两者其实要做的是一件事情，两个类之间要实现通信就会导致类之间耦合度变高。最终就导致了你给我你的数据成员，我给你我的数据成员，为了维护类而花费了大量精力，第三次我就直接删掉了Elevator。

　　　这次的优点其实延续了上次代码，可拓展性其实不低。

　　　缺点就是类拆分得过细，而且算法选择其实不好。

　　　时序图如下：

　　

• Part3 SOLID原则

　　　SRP(The Single Responsibility Principle)单一责任原则：这次作业照搬了上次的代码架构，基本符合。

　　　OCP(The Open Closed Principle)开放封闭原则：封装后不可随意更改，有一定的可拓展性，代码框架也几乎没变。

　　　LSP(The Liskov Substitution Principle)里氏替换原则：除去继承线程类，未使用继承。

　　　DIP(The Dependency Inversion Principle)依赖倒置原则：代码依赖于抽象，这次作业实现得还是不好，导致第三次修修改改。

　　　ISP(The Interface Seqreqation Principle)接口分离原则：未使用接口。

• Part4 bug分析

　　　强测中没有发现bug。

　　　由于笔者选择的是指导书上的算法，实现起来也并不困难。本地测试出的bug集中在主请求替换上，尤其是主请求的开关门问题。笔者引入了一个door变量表示门的开关状态，解决了这个问题。采用了丢性能分保命的咸鱼策略，强测没有炸点，但是性能分确实爆炸。

• Part5 发现别人的bug

　　　互测中没有发现bug，也没有被发现bug。

　　　这一次互测，其实也是疯狂空刀保命。然而这次与第一次不同，空刀的原因在于测试确实很困难。人工测试已经沦为不可能的事情。我又没有掌握核心科技，因此只能空刀刷活跃度保命。

Homework3 多电梯魔鬼调度

• Part1 多线程设计策略

　　　魔鬼电梯还是来了。多电梯虽然是情理之中，但是如此鬼畜的多电梯却是意料之外。

 public static final ArrayList<Integer> afloor = new ArrayList<>(
             Arrays.asList(-3, -2, -1, 1, 15, 16, 17, 18, 19, 20));
 public static final ArrayList<Integer> bfloor = new ArrayList<>(
             Arrays.asList(-2, -1, 1, 2, 4, 5, 6, 7,
                     8, 9, 10, 11, 12, 13, 14, 15));
 public static final ArrayList<Integer> cfloor = new ArrayList<>(
             Arrays.asList(1, 3, 5, 7, 9, 11, 13, 15));

　　　每个电梯的运行楼层如上，每个电梯都有自己的载重和运行速度。

 Elevator elevator1 = new Elevator('A', 400, 6, dispatcher);
 Elevator elevator2 = new Elevator('B', 500, 8, dispatcher);
 Elevator elevator3 = new Elevator('C', 600, 7, dispatcher);

　　　然而最要命的其实是电梯换乘问题。以作业中最为鬼畜的3楼为例，ID-FROM-2-TO-3就需要拆做ID-FROM-2-TO-1,ID-FROM-1-TO-3。具体分析策略如下：任意一个请求都可以分为直达请求和需拆分请求。而一个需拆分请求必然可以由两部电梯完成，两条指令需要注意先后顺序，只有第一条指令执行完毕，第二条指令才能进入。因此为Request增加了状态参量。

　　　从线程角度来看，本次线程协同与前两次并无大异。一个电梯线程变成三个电梯线程，线程之间要维护共享对象请求队列。因为笔者采用了抢夺式调度，每个电梯都维护自己的请求队列和队内队列，三个电梯请求队列通过共享对象通信。线程安全也是通过加synchronized锁，利用java自己的强力工具方便地解决线程安全问题。每当一个电梯请求被获取，另外两个就需要被删除；拆分请求的前一条请求被获取，除去对应的第二条请求其他同ID的请求被删除。

　　　优化算法则是另一个复杂的问题了。比如三部电梯的速度各有不同，载重量限制了盲目分配，拆分请求时中间楼层的选择，拆分第二条请求的执行时间等等。菜鸡的我决定直接交给电梯自己随缘调度（佛系）。还是正确性保命:)。

• Part2 度量分析

　　　魔鬼电梯带来的就是复杂度爆炸:(，笔者分析的是调度器和电梯的耦合度太高，两者之间需要相互传递信息。我认为这是因为直接延续了上一次代码架构，不过方法的复杂度其实也没有出现第一单元的普遍偏高的问题。只有getreq的复杂度较高，采取了重载之后避免了大量的条件逻辑。另外一个Prequset类是重新写的带构造函数的Request类（当时写的时候没有更新接口！！）。

　　　优点是实现逻辑简单，直接交由队列争夺。

　　　缺点是调度器和电梯的耦合度过高，二者功能有所交叉，且优化算法太差，都是直接采用ALS调度。

　　　时序图如下：

　　

• Part3 SOLID原则

　　　SRP(The Single Responsibility Principle)单一责任原则：这次作业照搬了上次的代码架构，但是电梯确实魔鬼，导致了调度器和电梯实现功能的确略有纠葛。

　　　OCP(The Open Closed Principle)开放封闭原则：封装后不可随意更改，有一定的可拓展性，代码框架也几乎没变。

　　　LSP(The Liskov Substitution Principle)里氏替换原则：除去继承线程类，未使用继承。

　　　DIP(The Dependency Inversion Principle)依赖倒置原则：代码依赖于抽象，这次作业是踩了前两次的坑，我反思自己的代码水平的确不高，一旦更改需求，就需要修改底层代码，日后应当注意这个抽象与代码逻辑的关系。

　　　ISP(The Interface Seqreqation Principle)接口分离原则：未使用接口。

• Part4 bug分析

　　　强测中没有发现bug。

　　　这一次的代码其实应该重构的，不停的给曾经的程序打补丁，带来的问题就是一堆莫名其妙的bug。不过好在这一次我们班的同学们团结在一起搭建起了评测姬。实现了自动化评测的我们仿佛掌握了核心科技。自动化评测也帮我找出了很多bug，不过时间仓促，没有来得及完善自己的代码，只能对代码修修补补，不过好在也勉强苟过了强测，就是性能分低了点。

　　　说一个本地测试的bug，问题出在线程安全。由于笔者直接延续while-sleep循环，而且在一处条件语句中使用了共享对象，if块里又对共享对象做写操作。导致评测时，陷入while死循环，解决方法便是使用synchronized锁锁住了if块。

• Part5 发现别人的bug

　　　互测中发现两个bug，没有被发现bug。

　　　方法是采用了大量随机数据进行测试，另外重点测试选取一个时间点投放大量数据情况下程序的调度能力。（掌握核心科技~）

　　　只能说，评测姬还是好用（rua~）。实名感谢评测姬小组，一起努力鸭！

心得体会

• 线程安全

　　　接触多线程的感觉，很妙。有一种玄学的妙不可言，在测试环节更有体会。也许恰好就是这样一个时间节点，线程之间恰好发生了冲突。在你de出bug后，你只能说妙啊，然后骂自己一句菜。

　　　这其实就提醒我们：在问题发生之前，就应该避免线程问题。通过synchronized锁，对每一步可能出现线程冲突的地方加锁，共享对象中的方法更是有加锁的必要。

　　　注意到三个点：原子性（任意一组操作，要不全部执行，要不全部不执行，中途不可间断）；可见性（当多个线程并发访问共享变量时，一个线程对共享变量的修改，其它线程能够立即看到）；顺序性（程序执行的顺序按照代码的先后顺序执行）。java通过锁lock和同步块synchronized实现原子性，通过volatile关键字实现可见性，通过两者协同完成顺序性。

• 设计原则

SRP	The Single Responsibility Principle	单一责任原则
OCP	The Open Closed Principle	开放封闭原则
LSP	The Liskov Substitution Principle	里氏替换原则
DIP	The Dependency Inversion Principle	依赖倒置原则
ISP	The Interface Segregation Principle	接口分离原则

　　　SOLID原则是针对面向对象编程的五大依赖关系管理。具体内容如上表。面向对象的设计直观体现在类与类之间的关系。如果关系混乱复杂（比如说我的代码），那么一旦需要变化一处代码功能，往往就需要牵一发动全身。虽然这次代码不再此次重构，但是每次修补确实是低效而且衍生出更多的bug。

　　　这五条原则并不是金科玉律，而更像是一种在更高层面上的指导方针。在这些纲领性原则束缚下，面向对象程序才有更加面向工程化的处理问题能力。而我显然把所有原则都给冒犯了，所以写出糟糕的代码也是情理之中。单一责任强调了类只应该注意自身的功能，不要越俎代庖，单一责任保证了每一个类实现起来都足够简单，在前两次作业中业务逻辑并不复杂的情况下我确实是这样的，而第三次作业的调度器和电梯就交叉了（bug就疯狂翻涌）。开放封闭原则强调了类是可扩展的，但不可改变。维护一个可变对象的成本是很大的，也带来了更多的麻烦，笔者就使用了很多可变对象。。。里氏替换原则强调了父类子类的关系，子类可以扩展父类的功能，但不要轻易变动父类的功能，这单元笔者没有使用继承(线程继承除外)，因此没有体现里氏替换原则。依赖倒置原则就我看来很抽象，依赖于抽象，在一个类中实例化依赖关系，就会增加这两个类的耦合，笔者的Elevatorctrl就实例化了Elevator，两者纠葛不清，直到第三次作业才删除了Elevator。接口分离原则，保证接口最小，接口之间相互分离。我也没有使用接口，因此也没有体现。

想说的话。。。

　　　继21天速成java编程之后，我学选修了21天速成多线程。短短三周，让我一个完全没有接触过多线程的人，写出了还不算太赖的多线程程序，OOP真是我爸爸。当然对于多线程的理解还是太浅！冲冲冲，据说是不是已经过了OO课的顶峰(?)，摸鱼预备！继续前行，还有半个学期，共勉！