BUAA OO 第二单元总结
BUAA OO 第二单元总结
Part 1 设计策略
这三次作业采用了主线程获取请求，多级调度器逐级分派，电梯模拟运行的策略。具体来说，主线程实例化ElevatorInput类，通过阻塞读取方式获得请求Request，之后将请求分配给调度器Scheduler，调度器负责处理请求（既可以自己处理，也可以分配给其他子调度器处理），每一个电梯与一个ElevatorScheduler绑定，用于具体的调度、睡眠控制、打印输出。
本次作业的难点主要有以下几点：
如何控制调度器、电梯线程的终止：简单的生产者-消费者模型中，生产者不断生产，消费者不断消费，不存在线程终止现象；现实中的电梯，一天24小时运行，没有异常情况也不会终止。但是更多的多线程问题是需要考虑线程终止的。这三次作业也是如此：主线程将所有请求都发送给调度器后，告知调度器准备结束，调度器处理完自己队列中剩余请求后，结束线程。
这种一般性的线程生命周期可以用这个比喻来说明：假如你是一个员工，在上班的时候你可能在干活，也可能闲着，但即使闲着，也不能回家；到了下班时间后，如果你的任务还没有完成，那就继续工作（加班），如果完成了，就可以回家了。于是，我们可以抽象出两个因素：是否空闲（
idle），是否到达下班时间（在电梯的问题中是输入是否结束，可用inputEnd变量表示）。是否空闲是可以自己判断的，而是否到达下班时间则需要外界的通知。以下讨论这种通知输入结束机制。一种比较容易想到的方法是采用
interrupt机制while (true) { Request request = elevatorInput.nextRequest(); if (request == null) { scheduler.interrupt(); } else { // pass } }但是这种方法并不能实现精确控制：我们希望的是，如果调度器在等待下一个输入（
wait()函数中），就打断；而如果它在执行别的任务，比如sleep(100)，或者是其他的同步任务，就不打断。虽然在这一单元的作业中没有出现这种情况，但是多做这种考虑也是合情合理的。另一种方法是专门设定一个
setInputEnd()方法，由主线程调用，告知调度器输入结束。class Scheduler { boolean inputEnd = false; Queue<Request> requestQueue; public synchronized void setInputEnd() { this.inputEnd = true; notifyAll(); } public synchronized void addRequest() {} public synchronized void getRequest() { while (requestQueue.isEmpty()) { wait(); } return requestQueue.poll(); } }我在作业中采用的是这种方法，但是后来发现，其实还可以用一种更加简洁的方法解决：建立一个
TerminationRequest类。interface Request {} class PersonRequest implements Request {} class ElevatorRequest implements Request {} class TerminationRequest implements Request {}这样，通过归一化处理，可以用一个队列来统一管理（更一般的来说，是把所有线程关心的状态改变的通知都放到统一的容器中管理，对外用同样的接口，对内采取不同的处理策略）。同时，这种归一化也方便了线程安全容器的使用。
区分两种获取请求的模式：在简单的生产者-消费者模式中，消费者在没有商品的情况下总是会在共享区中的
wait函数中等待，但是在实际生活的很多情况下，这种情况是不可接受的——消费者可能还有其他事情要完成，使用wait函数等待并释放CPU资源固然是一种进步，但这种方案同时也制约了消费者进行其他活动的自由。回到本单元作业，每一个电梯在行为上都需要实现：获取新的请求，决定电梯的行为（开门、关门、上行、下行等）。但是这两种行为并不是时时刻刻都需要进行的：如果电梯局部队列为空，电梯内部没有乘客，则电梯处于空闲状态，此时不需要频繁决定电梯的行为，只需要等待下一个请求的到来。因此，当电梯空闲时，应当阻塞地读取请求，即在请求处等待下一个请求；而当电梯忙碌时，则只需要查看并更新请求即可，没有新请求也不阻塞。这两种不同的模式，可以自己解决，如：
class ElevatorScheduler { private Queue<Request> queue; private Queue<Request> localQueue; private synchronized Request getRequest(boolean quickRetreat) { if (quickRetreat) { return queue.poll(); // if the queue is empty, return null } else { while (queue.isEmpty()) { wait(); } return queue.poll(); } } }也可以采用Java内置的
BlockingQueue来解决：private BlockingQueue<Request> queue; private void update() { if (idle) { localQueue.add(queue.take()); } queue.drainTo(localQueue); }灵活的分配器：第一次作业只有一个电梯；第二次作业有多个电梯，但只有一种型号；第三次作业有不同型号的电梯，每一种电梯型号下的电梯数是不同的。可以这样认为，第一次作业的电梯只需要一级调度器（直接指挥电梯的调度器），第二次作业的电梯是两级调度（一级负责电梯见的负载均衡，另一级负责直接指挥电梯），第三次作业的电梯是三级调度（一级总调度器负责换乘相关管理，一级负责同一个类型的电梯的负载均衡，一级负责直接指挥电梯）。如下图：
为了使得分配更加灵活，给这些
Scheduler设计一个统一的接口RequestReceiver即可，至于内部的处理，或分配或自行指挥电梯，请求提供者都不必关心。interface RequestReceiver { void addRequest (Request r); } class CentralScheduler implements RequestReceiver {} class Scheduler implements RequestReceiver {} class ElevatorScheduler implements RequestReceiver {}反馈和闭环控制：在实际多线程编程中，反馈和闭环控制也是十分常见的。本单元作业也不例外：换乘需要进行请求的反馈，即电梯运行一部分请求后，由另一个电梯继续完成另一部分请求。既然电梯是逐级控制的，电梯处理完自己应该处理的那一部分请求后，需要将请求反馈给上级调度器，由上级调度器进行二次分配。另一方面，调度算法在进行调度时，也需要考虑各电梯的负载均衡问题，因而电梯也要上报自身的负载情况。
这几次作业中，可以通过相应线程类提供反馈接口，进行逐级反馈状态：
interface FeedbackReceiver { void offerFeedback (Feedback fb); void offerRequestFeedback (Collection<PersonRequest> requests); } class CentralScheduler implements RequestReceiver, FeedbackReceiver {} class Scheduler implements RequestReceiver, FeedbackReceiver {}在反馈反向传播的时候，每一级
Scheduler也可以对反馈进行处理，比如作业3中的负载，每一类电梯的负载可以取这一类所有电梯中负载最小的电梯的负载。楼层映射：这个问题其实并没有什么面向对象的困难，主要是一个小技巧。每个电梯调度器（直接指挥电梯进行运动的调度器，它实现了调度算法）有一个映射，实现楼层到楼层下标的快速转换。
与其通过数学方法实现（分段函数）：
int flr_to_ind (int flr) { if (/* some conditions */) { // do something } else if (/* ... */) { // do something } else { // pass } }不如用Java自带的方法：
List<Integer> flrs = Arrays.asList(-3, -2, -1, 1, 2, 3); index = flrs.indexOf(flr); flr = flrs.get(index);
Part 2 第三次作业的可扩展性
假如我的第三次作业真正实现了第一部分中所叙述的思想和方法，那么再进行扩展也不会很复杂了。但事实上我的第三次作业并没有完全实现这些方法和技巧——程序的主题部分是第五次作业时构建的，之后只做了些小修小补。但是毕竟结构是类似的，也可以做一些分析：
- 实现紧急制动：从
Request接口下增加一个紧急制动请求的实现，调度器将这一请求分派到对应电梯。电梯到达下一个停靠点时，通过反馈渠道反馈所有的未完成请求，由上层调度器二次分配，同时电梯线程结束运行。 - 更复杂的电梯类型：构造电梯工厂，采用工厂模式，根据所提供的电梯型号生产相应电梯。在调度器方面，增加若干二级调度器，使每一个电梯类型对应一个调度器。（当然如果类型增量不大，把这一调度器与主调度器合并也是可行的）
- 更大的规模：增加调度级数，实现更细粒度的调度。
从SOLID角度看：
- Single Responsibility Principle：调度器总的说来比较符合这个原则，而电梯类符合度较低。在本人的设计中，电梯类既作为一个容器，管理电梯内的乘客，同时又负责输出、睡眠，而且请求的管理与
ElevatorScheduler类的职责部分重叠，耦合过高。在一开始的设计中，电梯的职能被规定为负责输出和睡眠（因为这两方面相对固定，可以与易变的ElevatorScheduler分离，但是在之后的迭代开发中，逐渐职能扩充。 - Open Close Principle：这三次作业在函数层面（即每个类的方法层面）比较符合这一原则，将易变的类和不易变的类分开，迭代开发时主要替换一些函数，不必大规模修改函数。但在类的层次对这一原则符合度较低。在最初的设计中，我本是打算每一个主要的类先写成抽象类，再通过继承抽象类进行实现，但最后感觉不太现实，就没有真正实施，而是直接把抽象类改成具体类……[捂脸]（也许小型工程不太容易做到OCP吧，毕竟就那么几个类）
- Liskov Substitution Principle：这三次作业关系比较少，但是基本上所有存在的继承关系都满足LSP原则了。
- Interface Segregation Principle：其实第三次作业并没有用到接口，但是如果按照第一部分的分析，每一个调度器都实现
RequestReceiver、FeedBackReceiver、Runnable方法，也算是有一点ISP的意思了。 - Dependency Inversion Principle：毕竟没有接口，继承关系也比较少，第三次作业的具体实现其实没有体现这一原则，不过如果按照第一部分的分析，
main函数线程只依赖RequestReceiver接口，也有一点DIP的意思了（虽然没有实现）。
Part 3 经典度量
考虑到三次作业结构一脉相承，每次迭代又没有什么重大改动，就只分析最后一次作业了。
UML图：
这里只实现了二级分派结构，其中PersonTransfer是课程组提供的PersonRequest类的子类，表示需要换乘的乘客请求。二级分派结构可以解决这三次作业的问题，main函数获取请求，再由高级调度器分派给低级调度器，低级调度器与电梯类协作，实现look电梯调度算法。在算法的实现过程中，需要管理楼层信息、管理用户请求信息，这些管理由building类和floor类处理，同时设置FloorNumberManager类，提供一些静态方法管理楼层映射、可达性查询等服务。
这种结构的主要问题是没有处理好电梯类Elevator和电梯调度器类ElevatorScheduler之间的关系。电梯调度器类只拥有一个电梯，负责这个电梯更细致的调度管理，如每一个时间节点，决定电梯上行、下行、开门、关门等动作，主要实现了算法。但同时，电梯类不仅负责输出、睡眠，还负责管理电梯内部人员，检查到达目的地的乘客，反馈电梯内部乘客信息等。在具体实现中，电梯类又将自身容器暴露给电梯管理类，使得两个类之间耦合度较高。
此外，电梯类Elevator并没有成为一个独立的线程，所以在电梯睡眠时，实际上时是在ElevatorScheduler线程中睡眠，导致电梯睡眠和电梯调度算法运行无法并行，降低效率。
复杂度：
可以看出，调度器是比较复杂的类，而调度器中负责算法的方法又是调度器中比较复杂的方法。但是除了调度器之外，电梯类也比较复杂，这是与设计初衷不符的。原因在上文也提到过，主要是随着代码实现的推进，电梯类的职能不断扩充，与调度类有所交叠，没有很好处理这一问题。
协作图：
Part 4 Bug分析
这一单元的作业主要容易出bug的地方包括：
- 程序死锁，尤其是输出终止，准备线程结束的时候。
- 伪多线程，主要是指程序实质上是在轮询，没有很好实现资源让出。
- 需求理解偏差。
我在三次作业的强测和互测中均没有发现bug，但是我的第一次作业（整个课程的第五次作业）有一个非常严重的错误（强测和互测，由于测试机制固定，都没有检测出来）：如果所有输入结束后没有立刻提供输入结束信号，程序将会进入死锁，无法终止。部分代码如下：
// methods of ElevatorScheduler
public synchronized void setInputEnd() {
this.inputEnd = true;
notifyAll();
}
private synchronized void update(boolean quickRetreat) {
if ( (inputEnd || quickRetreat) && buffer.isEmpty() ) {
return;
}
while (buffer.isEmpty()) {
try {
wait();
/* when the thread is notified, it's still in the while loop */
} catch (InterruptedException e) {
return;
}
}
// some updates here
}
可见，虽然程序退出了wait()函数，但还是会再次进入wait()函数，导致死锁。一个简单的修复是在while循环上增加一个条件；设计上的修复我在第一部分已经提到过，线程检测到TerminationRequest后就不再调用update函数，把这个问题在线程内部解决。
另一个问题是没有处理好CPU资源的让出，表现在轮询所导致的CPU_TLE。一般来说，线程空闲时需要等待，可使用wait()函数，一旦线程需要被唤醒，相应锁的notifyAll()函数必须被调用。我在第一次电梯作业的互测中用类似以下数据的数据点发现了两个A屋的solid bug：
[5.0]1-FROM-2-TO-3
[150.0]2-FROM-14-TO-5
Part 5 测试程序分析
本单元测试程序主要考虑自己的使用，包括三部分：
输入文件的时间映射器，将带时间的文件输入映射到时间轴上，实现定时输入。具体代码见：https://github.com/YushengZhao/BUAA_OO_elevator_input_mapper
电梯仿真器，模拟电梯的真实运行，在运行过程中检查相关问题。主要思路是：将电梯请求和被测程序输出转化成若干电梯指令，按照时间排序，在仿真器上模拟运行，在运行过程中记录参数、检查行为，最终可以给出性能报告。
请求指令生成器，可以定制若干段请求序列，每一段可以设置参数，可参考以下代码：
def generator(size=10, timescale=10, id_start=1, time_shift=1): # generate one segment of requests pass def generate(): periods = [12,19,8,4,13] sizes = [8,4,10,13,16] s = [] id = 1 time_shift = 0.3 for i, period in enumerate(periods): s += generator(size=sizes[i],timescale=period, id_start=id,time_shift=time_shift) id += (sizes[i]+1) time_shift += (period+0.1)
将这些组件连接起来就可以生成测评机了，但是考虑到自身实际需求，就没有具体实现了。
一个值得注意的地方：许多同学采用python脚本进行时间映射，我在参考了之前一些学长的博客之后发现，这种方法容易产生时间偏差，时间控制不是很精确，而将时间映射器内嵌到Java语言内部则可以实现更精确的控制。同时，这样也便于调试。
关于请求生成策略：实际应用中可能会出现不同时段负载不同的情况，我在测评机中按段生成请求，可以模拟这种情况。在进行几次到几十次测试后（总请求量1e2量级），一般没有什么显著问题；进行大量测试（1e3,1e4量级的测试）也许可以发现一些问题，但考虑到每一个测试所消耗的时间成本，就没有过多测试了。真正实际应用中，大量的测试肯定是必要的。
这一单元的调试和测试与上一单元相比，主要是多了时间因素，在测试时要考虑输入随时间分布的不同特征，如在一个时间点大量输入，在一段时间内没有输入，等等。而在调试时，由于不能使用断点调试法，我普遍采用了日志记录的方法，增加一个可插拔的logger：
private static final boolean LOGGER = true;
private static final boolean ASSERTION = true;
public static void log(String msg) {
if (LOGGER) {
System.out.println(msg);
}
}
public static void ast(boolean condition, String msg) { // ast == assert
if (ASSERTION && !condition) {
System.out.println("Assertion failed: "+msg);
}
}
或者实现一个带level的不同重要性的日志输出：
private static final int LEVEL = 5;
public static void log(int level, String msg) {
if (level >= LEVEL) {
System.out.println(msg);
}
}
当然，Java也有相应自带的日志记录机制，不过考虑到这一单元作业并不需要复杂的日志，就没有使用了。
Part 6 心得体会
多线程方面，我在做电梯第一次作业时花了比较长的时间（甚至一度以为自己就要止步于此了），当时有许多问题想不清楚，最后实现的代码也有许多逻辑混乱的地方。多线程之所以容易出现各种安全问题，归根结底还是线程自身行为逻辑复杂，比如，简单的生产者-消费者模型，基本不会有人写出线程安全的问题，但是复杂一些的生产者-消费者模型（如消费者在没有产品时不调用
wait函数，而是进行其他活动），就容易产生线程安全问题了。因此，根据需求建立简单通用的线程模型非常重要——简单的逻辑往往不容易出错。比如观察者模式，构建了一个线程发布消息，若干线程接收消息的模型；反过来，又有时也需要若干线程发送消息，某一个线程接收消息的情况，这时便可以采用消息队列：class Scheduler { private Queue<Message> messageQueue; public synchronized void addMsg() {/*some code here*/} public synchronized Message getMsg() {/*some code here*/} } interface Message {} class Feedback implements Message {} interface Request extends Message {}所有需要通知
Scheduler的消息，都通过addMsg方法传入，无论其具体内容，之后再由其他函数分别处理。因此，当Scheduler处理完剩余任务后，便可以直接在getMsg方法内等待。设计原则方面，我在完成第一次电梯作业时，并没有太多的设计原则方面的意识，而由于后两次作业都沿用第一次作业的结构，所有后两次作业也没有体现多少设计原则，这是遗憾的。
代码重构方面，我从这一单元开始坚定了能不重构就不重构的态度。从计组到现在，在各种需要迭代开发的工程中，我总是感觉之前写的不够好，想要重构，但又经常忽视了重构的风险以及不重构的可能性。实际开发中，重构肯定是要尽量避免的，在原来的代码（可能是看似比较乱的代码）上修改其实才是常态。事实上，看似乱糟糟的代码其实可能并没有想象中那么差。我在第二次电梯作业时曾经尝试了重构，但是等到真正动手写重构代码的时候才发现，如果重构，很多代码都是差不多的，原来很多设计上的考虑都是很有道理的。
算法方面，这一单元的作业给算法留出了很大的空间。不过想拿高分并不需要很复杂的算法。最基本的look算法，在强测不出现错误的情况下，基本就可以达到95分以上了。后两次作业再加一些负载均衡的考虑，如果没有错误，基本也能拿到95分以上。尽管如此，讨论一些算法也是没有坏处的：
- 将电梯的打印输出/睡眠与电梯运行逻辑解耦。这样做的目的是，可以在不真正运行电梯的前提下（运行一个虚拟电梯），估计电梯的总运行时间，进一步地，加入一个请求后的总运行时间。理论上，这样总是可以做到局部最优规划。而且这种估计是不依赖于特定算法的，灵活性比较强。
- 用马尔可夫决策过程建模。这样做是考虑到现在有许多针对马尔可夫决策过程（Markov Decision Process）的算法可供使用。
当然这些算法都是我没有实现的，毕竟课程的主要目的也不是算法。
其他：
- 有些问题其实并不是OOP的问题，有些bug其实也不是因为线程安全。比如look算法，我就花了不少时间实现、调试。
- 很多时候模仿现实世界的实体和关系也是一种很好的方法。比如，给电梯安排一个
Building，给每一个Building安排若干Floor，并提供“向上的按钮”和“向下的按钮”接口，就像现实生活中的电梯一样。电梯不知道一个楼层有多少人，只知道某一楼层有没有人想上楼、有没有人想下楼。 - 第二点的想法虽然对我们写作业很有帮助，但是这是不是就是在参考真正给电梯写程序的编程人员的代码架构呢？其实课程的者几次作业，我都是或多或少参考了前一届同学的博客，假如没有这种参考，我又能写出什么样的结构呢？